Maryland's Defense Patent Database

The defense community in Maryland is an R&D powerhouse.

Use this database to see the innovative patents that are poised for commercialization.

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

Patent image
NSA

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*.

Inventors: 
Solinas, Jerome A.
Patent Number: 
Technical domain: 
Communications
FIle Date: 
2002-06-28
Grant Date: 
2006-04-04
Grant time: 
1,376 days
Grant time percentile rank: 
25
Claim count percentile rank: 
4
Citations percentile rank: 
1
'Cited by' percentile rank: 
1
Assignee: 
NATIONAL SECURITY AGENCY