The United States of America as Represented by the National Security Agency

The United States of America as Represented by the United States National Security Agency

Robert W Reiter

Jerome Anthony Solinas

A method of generating and verifying a digital signature by selecting an elliptic curve; selecting a point G; generating x and M; reducing x; generating a base tau expansion, in non-adjacent form, of the reduced x; multiplying G by the expansion; computing h&equals;Hash(M); generating k; reducing k; generating a base tau expansion, in non-adjacent form, of the reduced k; multiplying G by the expansion of k to form K&equals;(K,,K,); computing R&equals;(K,mod q); returning to the step of generating k if R&equals;0, otherwise computing S&equals;(k{circumflex over ( )}&minus;1)(h&plus;xR); returning to the step of generating k if S&equals;0, otherwise transmitting y, q, M, R, and S; receiving y, q, M, R, and S; proceeding with the next step if 0<R<q and 0<S<q, otherwise not verifying the digital signature and stopping; forming h&equals;Hash(M); computing f&equals;((S{circumflex over ( )}&minus;1) mod q), b&equals;(hf mod q), and t&equals;(Rf mod q); reducing b and t; generating a base tau expansion, in non-adjacent form, of the reduced b; multiplies G by the result of the last step to form a point B; reduces t; generates a base tau expansion, in non-adjacent form, of the reduced b and t; multiplying G by the expansion of t; computing V&equals;B&plus;T, where V&equals;(V,,V,); computing v&equals;(V,mod q); and verifying the digital signature if v&equals;R, otherwise not verifying the digital signature.

Method of elliptic curve cryptographic digital signature generation and verification using reduced base tau expansion in non-adjacent form

A method of cryptographic key exchange by two users agreeing on an elliptic curve of the form y,&plus;xy&equals;x,&plus;ax,&plus;1, where &ldquo;a&rdquo; is a member of a field F,, where the elliptic curve is defined over a field F,m, where m is an integer; agreeing on a point G as the base point of the elliptic curve, where the point G is of order q, and where q is an integer; generating a private integer x,by a first user; reducing x,by mod (&tgr;,&minus;1) in the form of w&plus;z&tgr; by the first user; generating a base tau expansion, in non-adjacent form, of the modular reduced x,by the first user; multiplying G by the base tau expansion of the modular reduced x,; transmitting the product to the second user; receiving, by the first user, a value y,from the second user that is based on a private integer x,of the second user, where the received value is computed in a similar manner as was the product transmitted to the second user; multiplying, by the first user, x,by the value received from the second user in order to form a common secret point; multiplying, by the second user, x,by the value received from the first user in order to form the common secret point; and the two users each deriving the same cryptographic key from the common secret point.

Growing community of inventors

Woodbine, MD, United States of America

Robert W Reiter