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