US 7,024,559 B1Granted

Method of elliptic curve digital signature using expansion in joint sparse form

AssigneeThe United States of America as represented by the National Security Agency

InventorJerome A. Solinas

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method of generating and verifying a cryptographic digital signature using joint sparse expansion by a signer first selecting a field, an elliptic curve over the field, a point P of order q on the elliptic curve, w, k. Next, generating W=wP and K=kP. Next, transforming K to K*. Next, combining K*, W, and a message M to produce h. Next, combining K*, W, and M to produce c. Next, generating, s by either s=hw+ck (mod q), s=(hw+c)/k (mod q), or s=(hk+c)/w (mod q). Next, forming the digital signature as (K*,s). Next, a verifier acquires the field, the elliptic curve, P, W, M, and (K*,s). Next, computing h and c. Next, selecting (n0, n1) as either (sc−1 (mod q), −hc−1 (mod q)), (cs−1 (mod q), hs−1 (mod q)) or (−ch−1 (mod q), sh−1 (mod q)). Next, generating binary expansions of n0 and n1 in joint sparse form. Next, computing, Q=n0P+n1W via twin multiplication and a double-add-subtract method with the binary expansions in joint sparse form. Next, transforming, Q to Q*. Lastly, verifying, the digital signature if Q*=K*.

Claims12

Dependent claims

A method of generating and verifying a cryptographic digital signature using joint sparse expansion, comprising the steps of:

a) selecting, by a signer, a finite field;
an elliptic curve defined over the selected finite field, where the number of points on the elliptic curve is divisible by q, where q is a prime number;
a point P of order q on the elliptic curve;
an integer w;
and an integer k;
b) generating, by the signer, a point W=wP and a point K=kP;
c) transforming, by the signer, K to a bit string K*;
d) combining, by the signer, K*, W, and a message M in a first manner to produce h, where h is an integer modulo q;
e) combining, by the signer, K*, W, and the message M in a second manner to produce c, where c is an integer modulo q;
f) generating, by the signer, s using an equation selected from the group of equations consisting of s=hw+ck (mod q), s=(hw+c)/k (mod q), and s=(hk+c)/w (mod q);
g) forming, by the signer, the cryptographic digital signature as (K*,s);
h) acquiring, by a verifier, the finite field, the elliptic curve, the point P, the point W, the message M, and the cryptographic digital signature (K*,s);
i) computing, by the verifier, h and c in the same manner as the signer did in step (d) and step (e), respectively;
j) selecting, by the verifier, a pair of components (n0, n1) from the group of pairs of components consisting of (sc−1 (mod q), −hc−1 (mod q)), (cs−1 (mod q), hs−1 (mod q)) and (−ch−1 (mod q), sh−1 (mod q)), where the pair of components selected corresponds according to position to the equation selected in step (f);
k) generating, by the verifier, binary expansions of n0 and n1 to minimize a number of nonzero columns for the binary expansions;
l) computing, by the verifier, a point Q=n0P+n1W via twin multiplication and a double-add-subtract method with the binary expansions generated in step (k);
m) transforming, by the verifier, Q to Q* in the same manner as K was transformed to K* in step (c);
and
n) verifying, by the verifier, the cryptographic digital signature (K*,s) if Q*=K*, otherwise rejecting the cryptographic digital signature (K*,s).

16 more elements

A method of generating and verifying a cryptographic digital signature using joint sparse expansion, comprising the steps of:

a) selecting, by a signer, a finite field;
an elliptic curve defined over the selected finite field, where the number of points on the elliptic curve is divisible by q, where q is a prime number;
a point P of order q on the elliptic curve;
an integer w;
and an integer k;
b) generating, by the signer, a point W=wP and a point K=kP;
c) transforming, by the signer, K to a bit string K*;
d) combining, by the signer, K*, W, and a message M in a first manner to produce h, where h is an integer modulo q;
e) combining, by the signer, K*, W, and the message M in a second manner to produce c, where c is an integer modulo q;
f) generating, by the signer, s using an equation selected from the group of equations consisting of s=hw+ck (mod q), s=(hw+c)/k (mod q), and s=(hk+c)/w (mod q);
g) forming, by the signer, the cryptographic digital signature as (h,s);
h) acquiring, by a verifier, the finite field, the elliptic curve, the point P, the point W, the message M, and the cryptographic digital signature (h,s);
i) computing, by the verifier, c in the same manner as the signer did in step (d) and step (e), respectively;
j) selecting, by the verifier, a pair of components (n0, n1) from the group of pairs of components consisting of (sc−1 (mod q), −hc−1 (mod q)), (cs−1 (mod q), hs−1 (mod q)) and (−ch−1 (mod q), sh−1 (mod q)), where the pair of components selected corresponds according to position to the equation selected in step (f);
k) generating, by the verifier, binary expansions of n0 and n1 to minimize a number of nonzero columns for the binary expansions;
l) computing, by the verifier, a point Q=n0P+n1W via twin multiplication and a double-add-subtract method with the binary expansions generated in step (k);
m) transforming, by the verifier, Q to Q* in the same manner as K was transformed to K* in step (c);
and
n) combining, by the verifier, M, Q*, and W to produce h* in the same manner as M, K*, and W were combined in step (d);
and
o) verifying, by the verifier, the cryptographic digital signature (h,s) if h=h*, otherwise rejecting the cryptographic digital signature (h,s).

18 more elements

Dependencies are inferred from the claim text.