Method of elliptic curve cryptographic key exchange using reduced base tau expansion in non-adjacent form

Abstract

A method of cryptographic key exchange by two users agreeing on an elliptic curve of the form y,+xy=x,+ax,+1, where “a” is a member of a field F,, where the elliptic curve is defined over a field F,m, where m is an integer; agreeing on a point G as the base point of the elliptic curve, where the point G is of order q, and where q is an integer; generating a private integer x,by a first user; reducing x,by mod (&tgr;,−1) in the form of w+z&tgr; by the first user; generating a base tau expansion, in non-adjacent form, of the modular reduced x,by the first user; multiplying G by the base tau expansion of the modular reduced x,; transmitting the product to the second user; receiving, by the first user, a value y,from the second user that is based on a private integer x,of the second user, where the received value is computed in a similar manner as was the product transmitted to the second user; multiplying, by the first user, x,by the value received from the second user in order to form a common secret point; multiplying, by the second user, x,by the value received from the first user in order to form the common secret point; and the two users each deriving the same cryptographic key from the common secret point.