Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1998-08-04
2001-06-26
Barron, Jr., Gilberto (Department: 2131)
Cryptography
Particular algorithmic function encoding
Public key
C713S180000, C708S492000
Reexamination Certificate
active
06252960
ABSTRACT:
The present invention relates to the subject of compression and decompression. In particular, this disclosure provides for compression and decompression of elliptic curve data points such as might be used in electronic cryptography systems, where information (usually in the form of a text message, a digital signature or key, or other information) is encoded or decoded.
BACKGROUND
Cryptography systems are commonly used for providing secret communication of a text message or a cryptographic “key,” or for authenticating identity of a sender via a digital signature. Once encoded, information is generally stored in a computer file (on a disk, for example) or transmitted to a desired recipient. So-called “public key cryptography” uses two asymmetric “keys,” or large numbers, consisting of a public key and private key pair. If the public key is used to encode information according to a known algorithm, then the private key is usually needed by the recipient to decode that information, and vice-versa. Public key cryptography relies upon complex mathematical functions by which the public and private keys are related, such that it is extremely difficult to derive the private key from the public key, even with today's high speed processing computers.
One type of public key cryptography system is based upon elliptic curve representations and related mathematics and processing. As an end product of such processing, at least one coded block of information is created and represented as a data point having both X and Y coordinates, with each coordinate being a number between zero and 2
N
−1; if a large quantity of information is to be enciphered, there may be many such points, each point represented by at least 2N bits of information. For typical present day elliptic curve cryptography systems, N is typically on the order of one hundred and sixty, and future applications may use a much greater value for N.
In these cryptographic systems, a finite field is also chosen
F
2
N
,
where N denotes the number of binary bits used by a computer to represent an element of the finite field. An irreducible generator polynomial or order N is then selected which defines the arithmetic operations in the field. The coefficients of an equation defining an elliptic curve are then selected, and a point P (having X and Y coordinates) on the elliptic curve. Once these terms are chosen, a “point addition” operation is defined, and from it a “point and multiplication” operation is thereby defined,
kP=P+P+P+ . . . +P,
i.e., P is added to itself P−1 times. With these terms, a private key consisting of one number, such as the number k, and a public key consisting of the product of the point P and the private key (the product being constrained by the finite field and the elliptic curve chosen) may be selected and used for public key cryptographic applications.
Cryptography generally does not address compact storage or transmission of data, which is the subject of “data compression.” Data which is “compressed” occupies relatively less storage space and requires fewer transmission resources (i.e., time, bandwidth, storage, etc.) than uncompressed data. Without compression, transmission of relatively more information can lead to greater consumption of resources and frequency of errors. Modern day cryptography systems typically do not rely upon data compression, and they therefore leave some room for improvement.
Accordingly, a need exists for an elliptic curve processing system that compresses and decompresses coded data to a greater extent than known systems. Such a system should have application to cryptography systems which rely upon or process elliptic curve representations, enabling more efficient storage and transmission of encoded data. Still further, such a system should have the capability of compressing X and Y elliptic curve data coordinates, each having N bits, to a single representation having at most N bits in the aggregate. The present invention solves this need and provides further, related advantages.
SUMMARY
The present invention solves the foregoing needs by providing methods for compressing and decompressing elliptic curve data points, such that X and Y coordinates normally each represented by N bits of data each may be represented by N bits in the aggregate. Accordingly, the present invention provides for more efficient storage and transmission of elliptic curve data, and should find ready application to cryptography systems used in secret exchange of symmetric or asymmetric keys in particular.
One form of the present invention provides a method of compressing elliptic curve X and Y coordinate data, the X coordinate data consisting of N bits and the Y coordinate data consisting of at least 1 bit. Normally, elliptic curve processing systems use a predefined generator polynomial which identifies the finite field, as well as at least one predefined elliptic curve constant which identifies the elliptic curve. Given this information, this first form of the invention relies upon a vector which is constant for the finite field of interest and which satisfies the constraint that the product of the vector with any X coordinate data equals a constant (e.g., a special trace which is derived from the one or more elliptic curve constants). In response to the vector, a particular bit position of the X coordinate data is selected and discarded, and a binary value representing Y coordinate data is inserted in the particular bit position. This first form of the invention outputs the elliptic curve data as compressed data having no more than N bits, yet which represents a complete X and Y coordinate pair.
In more particular features of the invention, X and Y coordinates provided as elliptic curve coordinate data may each consist of N bits of data. The Y coordinate is identified as one of two possible quadratic solutions for the elliptic curve under consideration, and is replaced with a single binary bit of data which enables full reconstruction of the correct Y coordinate value. The method also may be implemented as instructions stored on machine readable media, e.g., as software or firmware, or with the assistance of digital hardware.
In still more specific features of the invention, the vector used to select a particular bit position can be computed based on the traces of the powers of a “generator.” The vector may be pre-supplied as a header for a compressed elliptic curve point, stored in a specific location (e.g., in a file or on a public website), or may be calculated only as to the number of bits needed to select the particular bit position. Importantly, in certain cases, e.g., where N is odd, the least significant bit (“LSB”) of the vector will necessarily be equal to “one,” and so full computation of a vector is not required, but the particular bit position can be selected based on inherent selection of a vector (e.g., having a LSB equal to “one”). Alternatively, if computed by the system, the trace of each power of a generator can be computed from smallest to largest power, only until the first “one” is determined. Each of these features is encompassed by the present invention.
A second form of the invention provides a method of decompressing an elliptic curve data point having X and Y coordinates, but represented by N bits in the aggregate. In this second form of the invention, a particular bit position is also “selected” based on constraints identified above (e.g., a vector can be stored or supplied with a compressed elliptic curve data point), and used to provide a Y coordinate value. From a special trace value computed for the elliptic curve, the true value of a X coordinate bit (for the particular bit position) can be derived, enabling full reconstruction of N bits of X coordinate data. The bit representing the Y coordinate value may be used, together with a quadratic equation for the elliptic curve, to completely reconstruct N bits of Y coordinate data.
Other forms of the invention are also defined by the claims, appended hereto.
The invention may be better
Barron Jr. Gilberto
Hewlett--Packard Company
Leaning Jeffrey S.
Schuyler Marc P.
LandOfFree
Compression and decompression of elliptic curve data points does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression and decompression of elliptic curve data points, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression and decompression of elliptic curve data points will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2498577