Patent ID: 6243467
Filing Date: 2001-06-05
Classification: G06F,H04L

Abstract:
A method of generating a digital signature for transmission to a recipient, comprising the steps of:a) selecting an elliptic curve, where the elliptic curve is of the form y.sup.2 +xy=x.sup.3 +a(x 2)+1, where ""a"" is a member of a field F.sub.2, where the elliptic curve is defined over a field F.sub.2 m, and where m is an integer;b) selecting a point G on the elliptic curve as a base point, where the point G is of order q, and where q is an integer;c) generating a private signature key x and a message M;d) reducing x by mod (.tau..sup.m -1) in the form of w+zt;e) generating a base tau expansion, in non-adjacent form, of the result of step (d);f) multiplying G by the result of step (e) to form a point y on the elliptic curve;g) computing h=Hash(M), where ""Hash"" is a secure one-way hash function;h) generating a private integer k;i) reducing k by mod (.tau..sup.m -1) in the form of w+zt;j) generating a base tau expansion, in non-adjacent form, of the result of step (i);k) multiplying G by the result of step (j) to form a point K on the elliptic curve, where K=(K.sub.x,K.sub.y);l) computing R=(K.sub.x mod q);m) returning to step (h) if R=0, otherwise proceeding to the next step;n) computing S=(k -1)(h+xR);o) returning to step (h) if S=0, otherwise proceeding to the next step; andp) transmitting y, q, M, R, and S to the recipient, where the pair (R,S) is the digital signature for the message M.