NSA

A method of generating and verifying a cryptographic digital signature using coefficient splitting. The digital signature is formed by first selecting a finite field, an elliptic curve of a first type or a second type, a point P, an integer w1, and an integer k1. Next, generating, via coefficient splitting, a point W=w1P and a point K=k1P. Next, transforming, K to a bit string K*. Next, combining K*, W, and a message M in a first manner to produce h1, and in a second manner to produce c. Next, generating s be either s=h1w1+ck1 (mod q), s=(h1w1+c)/k1 (mod q), or s=(h1k1+c)/w1 (mod q). Next, forming the cryptographic digital signature as (K*,s). The digital signature is verified by acquiring the finite field, the elliptic curve, the point P, the point W, the message M, and the cryptographic digital signature (K*,s). Next, computing h1 and c. Next, selecting (n0, n1) from (sc−1 (mod q), −h1c−1 (mod q)), (cs−1 (mod q), h1s−1 (mod q)) or (−ch1−1 (mod q), sh1−1 (mod q)). Next, generating the point n0P via coefficient splitting. Next, generating the point n1W via coefficient splitting. Next, summing the points computed in the last two steps and designating the sum Q. Next, transforming Q to Q*. Lastly, verifying the digital signature (K*,s) if Q*=K*. Otherwise rejecting the cryptographic digital signature (K*,s) as unverified.

Inventors:

Solinas, Jerome A.

Patent Number:

Technical domain:

Communications

FIle Date:

2002-06-28

Grant Date:

2006-06-13

Grant time:

1,446 days

Grant time percentile rank:

26

Claim count percentile rank:

5

Citations percentile rank:

1

'Cited by' percentile rank:

2

Assignee:

NATIONAL SECURITY AGENCY