US 7,379,546 B2 · Method for XZ-elliptic curve cryptography

Abstract

Given a set of elliptic curve points defined over a field F(p) and represented in projective coordinate, a method is presented which allows the embedding of data bits in both the X-coordinate and the Z-coordinate of the elliptic curve point when represented in projective coordinate. This makes the number of points that satisfy an elliptic curve equation and which can be used in the corresponding cryptosystem proportional to p2 rather than p. This can be used to either increase security by making the bit positions where data bits are embedded known only to the sender and receiver. Alternatively, it can be used to increase the number of data bits that can be encrypted per single elliptic curve point encryption. In another alternative, it can also be used to reduce p. Also, it can be used as a countermeasure by randomizing the bit positions where data bits are embedded. A similar formulation can be developed for elliptic curves over fields F(2m), as well as special elliptic curves such as Montgomery curves.

A method for encrypting and decrypting a message bit string in an information processing system for communicating securely over an insecure communication channel between a pair of correspondents who perform shared key cryptographic operations by implementing respective ones of a pair of complimentary mathematical cryptographic operations utilizing a shared key, said method comprising the steps of:

providing a pair of complimentary mathematical cryptographic operations;
assembling a data string including information to be transferred from a sending correspondent to a receiving correspondent;
performing a complimentary mathematical operation using points on an elliptic curve defined over a finite field and represented in projective coordinates, and wherein an addition of points on the elliptic curve is defined in projective coordinates;
and
forwarding the defined group of points over a communication channel to a receiving correspondent and performing the other of the pair of corresponding complimentary mathematical cryptographic operations to decrypt the data;
and
where the elliptic curve points in projective coordinates are represented using three coordinates, (X,Y,Z), wherein X, Y and Z are elements of F(p) represented in N-bit strings, and which includes a step where extra message bits are embedded in the Z coordinate in addition to the message data bits that are embedded in the X coordinate;
embedding a message bit string into the X and Z coordinates of an elliptic curve point which is designated as the message point, (XmYmZm);
providing a shared key k and a base point (XbYbZb) and computing the scalar multiplication (XbkYbkZbk)=k(XbYbZb);
computing a cipher point (XcYcZc) using (XcYcZc)=(XmYmZm)+k(XbYbZb);
sending appropriate bits of the X-coordinate, Xc and the Z-coordinate Zc of the cipher point (XcYcZc) to a receiving party;
using the shared key k and the base point (XbYbZb) computing the scalar multiplication (XbkYbkZbk)=k(XbYbZb);
computing the message point (XmYmZm) using (XmYmZm)=(XcYcZc)+(−k(XbYbZb));
recovering the message bit string from Xm and Zm;
in which the message bit string is divided into strings of length of M-bit where (2N−L)>M>(N−L);
in which a M-bit message string is further divided into two strings m1m2, where the length of string m1 must be no more than (N−L) bits, while the length of string m2 must be no more than (N−1) bits;
and
which includes the steps of:
assigning the value of the bit string of m2 to Zm using the following procedure:
i. assign the value of the bit string m2 to Rm,
ii. using Legendre test to determine if Rm has a square root,
iii. if Rm has a square root set Zm=Rm otherwise set Zm=gRm where g is any non-quadratic value in the underlying finite filed,
and compute a Z2m and bZ3m
assign the value of the bit string of m1 to Xm
compute T=X3m+(aZ2m)Xm+(bZ3m);
using Legendre test to see if T has a square root;
if T has a square root assign one of the roots to Y, if not continue incrementing Xm and repeating the computation of T until T has a square root.

24 more elements

Method for XZ-elliptic curve cryptography

Life of this patent

Method for XZ-elliptic curve cryptography

Life of this patent

Abstract

Claims6