Patent Number:
6,252,960
Title:
Compression and decompression of elliptic curve data points
Abstract:
In elliptic curve processing systems, information is typically processed to yield elliptic curve data points, with X and Y coordinates each represented by N bits, N typically being 160 or more. Valid Y coordinates must satisfy a quadratic equation for any given X coordinate, such that any Y data may be represented by its corresponding X coordinate and a single additional byte or bit. In accordance with this disclosure, a vector t is chosen for which the dot product between t and any X coordinate is equal to a constant. The vector t is used in a compression mode of the preferred embodiment to select a bit position in X coordinate data with the X bit at that location being discarded and the Y coordinate information being stored in its place. As a result, an extra byte of data is not needed and any elliptic curve data point may be represented by N bits only. In a decompression mode of the preferred embodiment, the vector t and the constant are calculated and used both to extract and fully reconstruct Y coordinate information and to reproduce the previously discarded X coordinate bit. The system disclosed herein has application to elliptic curve cryptography.
Inventors:
Seroussi; Gadiel (Cupertino, CA)
Assignee:
Hewlett-Packard Company
International Classification:
G06F 7/72 (20060101); G06F 7/60 (20060101); H04L 009/30 ()
Expiration Date:
06/26/2018