Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-12-15
2004-11-30
Malzahn, D. H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C380S028000
Reexamination Certificate
active
06826586
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computation of a point doubling operation of elliptic curve point scalar multiplication.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever.
2. Background Art
Computer systems are useful for performing mathematical operations (add, subtract, multiply, divide) on operands. Often the operands are polynomials. A polynomial is a mathematical expression of one or more algebraic terms each of which consists of a constant multiplied by one or more variables raised to a nonnegative integral power (e.g. &agr;+bx+cx
2
). The task of performing mathematical operations on polynomial operands is difficult in the sense that it is not simply a matter of multiplying or dividing two simple numbers. There are a number of schemes that provide methods for performing mathematical operations on polynomials. However, there are situations for which no suitable schemes have been provided.
One situation that requires the manipulation of polynomials is the encryption and decryption of data in a cryptosystem and digital signatures for verification of the sender. A cryptosystem is a system for sending a message from a sender to a receiver over a medium so that the message is “secure”, that is, so that only the intended receiver can recover the message. A cryptosystem converts a message, referred to as “plaintext” into an encrypted format, known as “ciphertext.” The encryption is accomplished by manipulating or transforming the message using a “cipher key” or keys. The receiver “decrypts” the message, that is, converts it from ciphertext to plaintext, by reversing the manipulation or transformation process using the cipher key or keys. So long as only the sender and receiver have knowledge of the cipher key, such an encrypted transmission is secure.
A digital signature is a bit-stream generated by a cryptosystem. It is attached to a message such that a receiver of the message can verify with the bit-stream and be assured that the message was indeed originated from the sender it claims to be. A “classical” cryptosystem is a cryptosystem in which the enciphering information can be used to determine the deciphering information. To provide security, a classical cryptosystem requires that the enciphering key be kept secret and provided to users of the system over secure channels. Secure channels, such as secret couriers, secure telephone transmission lines, or the like, are often impractical and expensive.
A system that eliminates the difficulties of exchanging a secure enciphering key is known as “public key encryption.” By definition, a public key cryptosystem has the property that someone who knows only how to encipher a message cannot use the enciphering key to find the deciphering key without a prohibitively lengthy computation. An enciphering function is chosen so that once an enciphering key is known, the enciphering function is relatively easy to compute. However, the inverse of the encrypting transformation function is difficult, or computationally infeasible, to compute. Such a function is referred to as a “one way function” or as a “trap door function.” In a public key cryptosystem, certain information relating to the keys is public. This information can be, and often is, published or transmitted in a non-secure manner. Also, certain information relating to the keys is private. This information may be distributed over a secure channel to protect its privacy, (or may be created by a local user to ensure privacy). Some of the cryptosystems that have been developed include the RSA system, the Massey-Omura system, and the El Gamal system.
ELLIPTIC CURVES
Another form of public key cryptosystem is referred to as an “elliptic curve” cryptosystem. An elliptic curve cryptosystem is based on points on an elliptic curve E defined over a finite field F. Elliptic curve cryptosystems rely for security on the difficulty in solving the discrete logarithm problem. An advantage of an elliptic curve cryptosystem is there is more flexibility in choosing an elliptic curve than in choosing a finite field. Nevertheless, elliptic curve cryptosystems have not been widely used in computer-based public key exchange systems due to their late discovery and the mathematical complexity involved. Elliptic curve cryptosystems are described in “A Course in Number Theory and Cryptography” (Koblitz, 1987, Springer-Verlag, N.Y.).
In practice an Elliptic Curve group over Fields F(
2
m) is formed by choosing a pair of a and b coefficients, which are elements within F(
2
m). The group consists of a finite set of points P(x,y) which satisfy the elliptic curve equation
y
2
+xy=x
3
+&agr;x
2
+b
together with a point at infinity, O. The coordinates of the point, x and y, are elements of F(
2
m) represented in m-bit strings. Since F(
2
m) operates on bit strings and the field has a characteristic 2, computers can perform arithmetic in this field very efficiently. The arithmetic in F(
2
m) can be defined in either a standard basis representation or optimal normal basis representation. This description uses the standard basis representations for purposes of discussion. All elliptic curve point coordinates are represented as polynomials with binary coefficients.
The Elliptic Curve Cryptosystem relies upon the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP) to provide its effectiveness as a cryptosystem. Using multiplicative notation, the problem can be described as: given points P and Q in the group, find a number k such that P
k
=Q; where k is called the discrete logarithm of Q to the base P. Using additive notation, the problem becomes: given two points P and Q in the group, find a number k such that kP=Q.
In an Elliptic Curve Cryptosystem, the large integer k is kept private and is often referred to as the secret key. The point Q together with the base point P are made public and are referred to as the public key. The security of the system, thus, relies upon the difficulty of deriving the secret k, knowing the public points P and Q. The main factor that determines the security strength of such a system is the size of its underlying finite field. In a real cryptographic application, the underlying field is made so large that it is computationally infeasible to determine k in a straight forward way by computing all the multiples of P until Q is found.
The core of the elliptic curve geometric arithmetic is an operation called scalar multiplication which computes kP by adding together k copies of the point P. The scalar multiplication is performed through a combination of point-doubling and point-addition operations. The point-addition operation adds two distinct points together and the point-doubling operation adds two copies of a point together. To compute, for example, 11 P=(2*(2*(2P)))+2P=P, it would take 3 point-doublings and 2 point-additions.
Point-doubling and point-addition calculations require special operations when dealing with polynomial operands. Algebraic schemes for accomplishing these operations are illustrated below in Table 1.
TABLE 1
Point addition: R = P + Q
Point Doubling: R = 2P
S = (y
P
− y
Q
) * (1/(x
P
+ x
Q
))
S = x
P
+ y
P
* (1/x
P
)
x
R
= s
2
+ s + a + x
P
+ x
Q
x
R
= s
2
+ s + a
y
R
= s * (x
P
+ x
R
) + x
R
+ y
P
y
R
= x
p
2
+ (s + 1) * x
R
If Q = −P, R = P + (−P) = O,
If x
P
= O, then R = 2P = O, infinity
infinity
The two equations for S in the table are called the slope-equations. Computation of a slope equation requires one modular polynomial i
Malzahn D. H.
Zagorin O'Brien & Graham LLP
LandOfFree
Method for efficient computation of point doubling operation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for efficient computation of point doubling operation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for efficient computation of point doubling operation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3338409