Method of elliptic curve digital signature using coefficient splitting

Abstract

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 w, and an integer k. Next, generating, via coefficient splitting, a point W=wP and a point K=kP. Next, transforming, K to a bit string K*. Next, combining K*, W, and a message M in a first manner to produce h, and in a second manner to produce c. Next, generating s be either s=hw+ck(mod q), s=(hw+c)/k(mod q), or s=(hk+c)/w(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 hand c. Next, selecting (n, n) from (sc(mod q), −hc(mod q)), (cs(mod q), hs(mod q)) or (−ch(mod q), sh(mod q)). Next, generating the point nP via coefficient splitting. Next, generating the point nW 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.