Cryptography – Particular algorithmic function encoding
Reexamination Certificate
2000-10-02
2004-08-24
Barrón, Gilberto (Department: 2132)
Cryptography
Particular algorithmic function encoding
C380S259000, C380S030000, C380S028000, C380S285000, C380S278000, C713S171000, C713S168000
Reexamination Certificate
active
06782100
ABSTRACT:
This invention relates to a method of accelerating operations in a finite field, and in particular, to operations performed in a field F
2
m
such as used in encryption systems.
BACKGROUND OF THE INVENTION
Finite fields of characteristic two in F
2
m
are of interest since they allow for the efficient implementation of elliptic curve arithmetic. The field F
2
m
can be viewed as a vector space of dimension m over F
2
. Once a basis of F
2
m
over F
2
has been chosen the elements of F
2
m
can be conveniently represented as vectors of elements zero or one and of length m. In hardware, a field element is stored in a shift register of length m. Addition of field elements is performed by bitwise XOR-ing (⊕) the vector representations and takes one clock cycle.
Digital signatures are used to confirm that a particular party has sent a message and that the contents have not been altered during transmission.
A widely used set of signature protocols utilizes the ElGamal public key signature scheme that signs a message with the sender's private key. The recipient may then verify the signature with the sender's public key.
Various protocols exist for implementing such a scheme and some have been widely used. In each case however the recipient is required to perform a computation to verify the signature. Where the recipient has adequate computing power this does not present a particular problem but where the recipient has limited computing power, such as in a “Smart card” application, the computations may introduce delays in the verification process. Public key schemes may be implemented using one of a number of groups in which the discrete log problem appears intractable but a particularly robust implementation is that utilizing the characteristics of points on an elliptic curve over a finite field. This implementation has the advantage that the requisite security can be obtained with relatively small orders of field compared with for example with implementations in Z
p
→
and therefore reduces the bandwidth required for communicating the signatures.
In a typical implementation a signature component s has the form:
s=ae+k
(mod
n
)
where:
P is a point on the curve, which is predefined parameter of the system;
k is a random integer selected as a short term private or session key, and has a corresponding short term public key R=kP;
a is the long term private key of the sender and has a corresponding public key aP=Q;
e is a secure hash, such as the SHA hash function, of a message m and short term public key R; and
n is the order of the curve.
The sender sends to the recipient a message including m, s, and R and the signature is verified by computing th value R′=(sP−cQ) which should correspond to R. If the computed values are equivalent then the signature is verified.
In order to perform the verification it is necessary to compute a number of point multiplications to obtain sP and eQ, each of which is computationally complex.
If F
q
is a finite field, the elliptic curves over F
q
can be divided into two classes, namely supersingular and non-supersingular curves. If F
q
is of characteristic 2, i.e. q=2
M
, then the classes are defined as follows.
i) The set of all solutions to the equation y
2
+ay=x
3
+bx+c where a,b,c&egr;F
q
, a≠0, together with a special point called the point at infinity O is a supersingular curve over F
q
.
ii) The set of all solutions to the equation y
2
+xy=x
3
ax
2
+b where a,b&egr;F
q
, b≠0, together with a special pointed called the point at infinity O is a nonsupersingular curve over F
q
.
By defining an appropriate addition on these points, we obtain an additive abelian group. The addition of two points P(x
1
,y
1
) and Q(x
2
,y
2
) for the supersingular elliptic curve E with y
2
+ay−x
3
+bx−c is given by the following:
If P(x
1
,y
1
)⊖E; then define −P=(x
1
,y
1
+a),P+O=O+P=P for all P&egr;E.
If Q=(x
2
,y
2
)⊖E and Q≠−P, then the point representing the sum of P+Q, is denoted (x
3
,y
3
), where
x
3
=
{
(
y
1
⊕
y
2
x
1
⊕
x
2
)
2
⊕
x
1
⊕
x
2
(
T
≠
Q
)
or
x
3
=
{
x
1
2
⊕
b
7
a
2
(
P
=
Q
)
and
y
3
=
{
(
y
1
⊕
y
2
x
1
⊕
x
2
)
⊕
(
x
1
⊕
x
3
)
⊕
y
1
⊕
a
(
P
≠
Q
)
or
y
3
=
{
(
x
1
2
⊕
b
a
)
⊕
(
x
1
⊕
x
3
)
⊕
y
1
⊕
a
(
P
-
Q
)
The addition of two points P(x
1
,y
1
) and Q(x
2
,y
2
) for the nonsupersingular elliptic curve y
3
+xy=x
3
+ax
3
+b is given by following:
If P=(x
1
,y
1
)&egr;E then define −P=(x
1
,y
1
+x
1
). For all P&egr;E, O+P=P+O=P. If Q=(x
2
,y
2
)⊂E and Q≠−P, then P+Q is a point (x
3
,y
3
), where
x
3
=
{
(
y
1
⊕
y
2
x
1
⊕
x
2
)
2
⊕
y
1
⊕
y
2
x
1
⊕
x
2
⊕
x
1
⊕
x
2
a
(
P
≠
Q
)
or
x
3
=
{
x
1
2
⊕
b
x
1
2
(
P
=
Q
)
]
and
y
3
=
{
(
y
1
⊕
y
2
x
1
⊕
x
2
)
⊕
(
x
1
⊕
x
3
)
⊕
x
3
⊕
y
1
(
P
≠
Q
)
or
y
3
=
{
x
1
2
(
x
1
⊕
y
1
x
1
)
⊕
x
1
⊕
x
3
(
P
=
Q
)
Now supersingular curves are preferred, as they are more resistant to the MOV attack. It can be seen that computing the sum of two points on E requires several multiplications, additions, and inverses in the underlying field F
2
m
. In turn, each of these operations requires a sequence of elementary bit operations.
When implementing cryptographic operations in ElGamal or Diffie-Hellman schemes or generally most cryptographic operations with elliptic curves, one is required to compute kP=P+P+ . . . +P (P added k times) where k is a positive integer and P&egr;E. This requires the computation of (x
3
,y
3
) to be computed k−1 times. For large values of k which are typically necessary in cryptographic applications, this has previously been considered impractical for data communication. If k is large, for example 1024 bits, kP would be calculated by performing 2
1024
additions of P.
Furthermore, in a multiplicative group, multiplications and inversions are extremely computationally intensive, with field inversions being more expensive than field multiplications. The inversion operation needed when adding two points can be eliminated by resorting to projective coordinates. The formula for addition of two points however, requires a larger number of multiplications than is required when using affine coordinates.
In a paper entitled “Elliptic Curve Cryptosystems and Their Implementation” by Vanstone et al., published in The Journal of Cryptology, a method is described for adding two points by converting to projective coordinates and thus eliminating the inversion computation. However the overall gain in speed by elimination of the inversion is at the expense of space. Extra registers are required to store P and Q and also to store intermediate results when doing the addition. Furthermore, this method requires the use of the y-coordinate in the calculation.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a method and apparatus in which some of the above disadvantages are obviated or mitigated.
It is a further object of the invention to provide a method of multiplying finite field elements, and which may be implemented relatively efficiently on a processor with limited processing capability, such as a smart card or the like.
It is a still further object of the present invention to provide a method and apparatus in which signature verification may be accelerated in elliptic curve encryption systems.
In accordance with this invention there is provi
Antipa Adrian
Gallant Robert
Mullin Ronald
Vanstone Scott
Barrón Gilberto
Certicom Corp.
McArdle Joseph M
Pillsbury & Winthrop LLP
LandOfFree
Accelerated finite field operations on an elliptic curve does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accelerated finite field operations on an elliptic curve, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accelerated finite field operations on an elliptic curve will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3362638