Patent ID: 8102998

Claim:
A method for elliptic curve scalar multiplication in an elliptic curve cryptosystem implemented over an insecure communications channel, comprising the steps of: (a) selecting positive integers L x and L y wherein L x and L y are not both equal to 1, and wherein L y ≠3 if L x =2; (b) storing the positive integers L x and L y in computer readable memory; (c) selecting a projective coordinate system; (d) representing coordinates of a point P=(x,y) on an elliptic curve of the form F(x,y)=y 2 −x 3 −ax−b=0 defined over a finite field as projective coordinates according to transforms x = X Z L x ⁢ ⁢ and ⁢ ⁢ y = Y Z L y , respectively, wherein X, Y and Z are orthogonal projective coordinates in the selected projective coordinate system, and wherein the orthogonal projective coordinates are defined by expressing the elliptic curve in the orthogonal projective coordinates as Y 2 Z 3L x -2 x =X 3 +aXZ 2L x +bZ 3L x ; (e) adding together K copies, K being a scalar, of the point P(X,Y L x ,Z L y ) to obtain the scalar multiplication product KP; (f) storing the scalar multiplication product KP in the computer readable memory; (g) converting the scalar multiplication product from parameterized projective coordinates P(X, Y,Z L x ,Z L y ) to affine coordinates P(x,y); (h) maintaining the scalar K as private and making the point P(x,y) and the scalar multiplication product KP public for establishing elliptic curve public-key agreement; (i) embedding a plaintext message onto a point on the elliptic curve to form a message point; and (j) adding the message point to the scalar multiplication product KP in order to encrypt the plaintext message, the encrypted plaintext message being stored in the computer readable memory.