Method of elliptic curve cryptographic digital signature generation and verification using reduced base tau expansion in non-adjacent form

Abstract

A method of generating and verifying a digital signature by selecting an elliptic curve; selecting a point G; generating x and M; reducing x; generating a base tau expansion, in non-adjacent form, of the reduced x; multiplying G by the expansion; computing h&equals;Hash(M); generating k; reducing k; generating a base tau expansion, in non-adjacent form, of the reduced k; multiplying G by the expansion of k to form K&equals;(K,,K,); computing R&equals;(K,mod q); returning to the step of generating k if R&equals;0, otherwise computing S&equals;(k{circumflex over ( )}&minus;1)(h&plus;xR); returning to the step of generating k if S&equals;0, otherwise transmitting y, q, M, R, and S; receiving y, q, M, R, and S; proceeding with the next step if 0<R<q and 0<S<q, otherwise not verifying the digital signature and stopping; forming h&equals;Hash(M); computing f&equals;((S{circumflex over ( )}&minus;1) mod q), b&equals;(hf mod q), and t&equals;(Rf mod q); reducing b and t; generating a base tau expansion, in non-adjacent form, of the reduced b; multiplies G by the result of the last step to form a point B; reduces t; generates a base tau expansion, in non-adjacent form, of the reduced b and t; multiplying G by the expansion of t; computing V&equals;B&plus;T, where V&equals;(V,,V,); computing v&equals;(V,mod q); and verifying the digital signature if v&equals;R, otherwise not verifying the digital signature.