Patent ID: 7062043

Claim:
A method of generating and verifying a cryptographic digital signature using coefficient splitting, comprising the steps of: a) selecting, by a signer, a finite field; b) selecting, by the signer, an elliptic curve, where the elliptic curve is defined over a field of integers modulo p and divisible by a prime number q, known by the signer and a verifier, and where the elliptic curve is selected from a group of elliptic curves consisting of a first type and a second type; where the elliptic curves of the first type are defined by y^2=x^3+A*x (mod p), where A is an integer modulo p, and there exists a number w and integers h and k such that, if (x,y) is a point on the curve for which q*(x,y) is the identity point O, then (2^d)*(x,y)=k*(x,y)+h*(−x,w*y); where the elliptic curves of the second type are defined by y^2=x^3+B (mod p), where B is an integer modulo p, and there exists a number w and integers h and k such that, if (x,y) is a point on the curve for which q*(x,y) is the identity point O, then (2^d)*(x,y)=k*(x,y)+h*(w*x,y); c) selecting, by the signer, a point P, an integer w 1 , and an integer k 1 ; d) generating, by the signer, a point W=w 1 P via coefficient splitting; e) generating, by the signer, a point K=k 1 P via coefficient splitting; f) transforming, by the signer, K to a bit string K*; g) combining, by the signer, K*, W, and a message M in a first manner to produce h 1 , where h 1 is an integer modulo q; h) combining, by the signer, K*, W, and the message M in a second manner to produce c, where c is an integer modulo q; i) generating, by the signer, s using an equation selected from the group of equations consisting of s=h 1 w 1 +ck 1 (mod q), s=(h 1 w 1 +c)/k 1 (mod q), and s=(h 1 k 1 +c)/w 1 (mod q); j) forming, by the signer, the cryptographic digital signature as (K*,s); k) acquiring, by the verifier, the finite field, the elliptic curve, the point P, the point W, the message M, and the cryptographic digital signature (K*,s); l) computing, by the verifier, h 1 and c in the same manner as the signer did in step (g) and step (h), respectively; m) selecting, by the verifier, a pair of components (n 0 , n 1 ) from the group of pairs of components consisting of (sc −1 (mod q), −h 1 c −1 (mod q)), (cs −1 (mod q), h 1 s −1 (mod q)) and (−ch 1 −1 (mod q), sh 1 −1 (mod q)), where the pair of components selected corresponds according to position to the equation selected in step (i); n) generating, by the verifier, the point n 0 P via coefficient splitting; o) generating, by the verifier, the point n 1 W via coefficient splitting; p) summing, by the verifier, the point computed in step (n) and the point computed in the step (o) and designating the sum Q; q) transforming, by the verifier, Q to Q* in the same manner as K was transformed to K* in step (f); and r) verifying the cryptographic digital signature (K*,s) if Q*=K*, otherwise rejecting the cryptographic digital signature (K*,s) as unverified.