Patent ID: 7024559
Filing Date: 2006-04-04
Classification: H04L

Abstract:
1. 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 (n k) generating, by the verifier, binary expansions of n l) computing, by the verifier, a point Q=n 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).