Patent ID: 7062043
Filing Date: 2006-06-13
Classification: H04L

Abstract:
1. 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 d) generating, by the signer, a point W=w e) generating, by the signer, a point K=k 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 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 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 m) selecting, by the verifier, a pair of components (n n) generating, by the verifier, the point n o) generating, by the verifier, the point n 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.