Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1999-03-04
2001-04-03
Hayes, Gail (Department: 2767)
Cryptography
Particular algorithmic function encoding
Public key
C380S028000
Reexamination Certificate
active
06212277
ABSTRACT:
This application is based on an application No. 10-053204 filed in Japan, the content of which is hereby incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an encryption technique for maintaining the security of information, and in particular relates to an encryption/decryption technique, a digital signature/verification technique, and a key agreement technique which use an elliptic curve.
2. Description of the Related Art
<Public-Key Encryption>
Data communication that uses computer and communication techniques has become pervasive in recent years. Secret communication or digital signature techniques are used in such data communication. Secret communication techniques allow communication to be performed without the communicated content being revealed to third parties. Digital signature techniques, meanwhile, enable a receiver to verify whether the communicated content is valid or whether the information is from the stated sender.
Such secret communication or digital signature techniques use a cryptosystem called public-key encryption. Public-key encryption provides a convenient method for managing the separate encryption keys of many users, and so has become a fundamental technique for performing communication with a large number of users. In secret communication based on public-key encryption, different keys are used for encryption and decryption, with the decryption key being kept secret and the encryption key being made public.
Here, one of the founding principles for the security of public-key encryption is the so-called “discrete logarithm problem”. Representative examples of the discrete logarithm problem are problems defined over finite fields and problems based on elliptic curves. Such problems are described in detail in Neal Koblitz,
A Course in Number Theory and Cryptography
(Springer-Verlag, 1987).
<Discrete Logarithm Problem based on Elliptic Curve>
A discrete logarithm problem based on an elliptic curve is as follows.
E(GF(p)) is the elliptic curve E defined over the finite field GF(p), with an element G, given when the order of E is exactly divided by a large prime number, being set as a base point. This being so, the problem is to calculate an integer x that satisfies
Y=x*G
(Formula 1)
where Y is a given element on the elliptic curve E and such an integer x actually exists.
Here, p is a prime number and GF(p) is a finite field that includes p elements. Note that in this specification the sign * represents exponentiation of an element included in an elliptic curve, so that x*G=G+G+ . . . +G where the element G is cumulated x times.
The reason a discrete logarithm problem assists in the security of public-key encryption is that the above calculation of x is extremely difficult for a large finite field GF(p).
<ElGamal Signature Scheme Which Uses Discrete Logarithm Problem Based on Elliptic Curve>
The following is a description of the ElGamal signature scheme which uses a discrete logarithm problem based on an elliptic curve.
FIG. 1
is a sequence diagram showing the digital signature procedure by the ElGamal signature scheme.
A user A
110
, a management center
120
and a user B
130
are connected together via a network.
First, a prime number is set as p, an elliptic curve over a finite field GF(p) is set as E, a base point of E is set as G, and the order of E is set as q. Which is to say, q is the smallest positive integer that satisfies
q*G=
0 (Formula 2)
Note that a point (∞,∞) whose x and y coordinates are both ∞ is called “point at infinity” and expressed as 0. When an elliptic curve is regarded as a group, 0 acts as “zero-element” in addition operations.
(1) Generation of Public Key by Management Center
120
Using a secret key xA given by the user A
110
beforehand, the management center
120
generates a public key YA for the user A
110
according to Formula 3 (steps S141-S142).
YA=XA*G
(Formula 3)
The management center
120
then announces the prime number p, the elliptic curve E and the base point G as system parameters, and reveals the public key YA of the user A
110
to the user B
130
(steps S143-S144).
(2) Generation of Signature by User A
110
The user A
110
generates a random number k (step S145).
The user A
110
then calculates
R
1=(
rx,ry
)=
k*G
(Formula 4)
(step S146), and finds s that satisfies
s×k=m+rx×xA
(mod
q
) (Formula 5)
(step 147), where m denotes a message to be sent from the user A
110
to the user B
130
.
The user A
110
sends (R1,s) as a signature to the user B
130
together with the message m (step S148).
(3) Verification of Signature by User B
130
The user B
130
verifies the validity of the user A
110
that is the sender of the message m, by judging whether Formula 6 is satisfied (step S149).
s*R
1
=m*G+rx*YA
(Formula 6)
Here, Formula 6 derives from
s
*
Ri
=
{
(
(
m
+
rx
×
xA
)
/
k
)
×
k
}
*
G
=
(
m
+
rx
×
xA
)
*
G
=
m
*
G
+
(
rx
×
xA
)
*
G
=
m
*
G
+
rx
*
YA
(
Formula
7
)
<Computational Complexity of Addition and Doubling in Elliptic Curve Exponentiation>
In the above ElGamal digital signature scheme which uses a discrete logarithm problem based on an elliptic curve, elliptic curve exponentiation is repeatedly performed to generate the public key and the signature and to verify the signature. For example, xA*G in Formula 3, k*G in Formula 4, s*R1, m*G and rx*YA in Formula 6 are such elliptic curve exponentiation. For details on elliptic curve exponentiation, see “Efficient Elliptic Curve Exponentiation” in Miyaji, Ono & Cohen,
Advances in Cryptology
-
Proceedings of ICICS'
97,
Lecture Notes in Computer Science,
pp.282-290 (Springer-Verlag, 1997).
Formulas used in elliptic curve exponentiation will be explained below.
Let
y{circumflex over ( )}
2=
x{circumflex over ( )}
3
+&agr;×x&bgr;
be the equation of an elliptic curve. In this specification, the sign represents a repeated multiplication, so that 2{circumflex over ( )}3=2×2×2.
Let P=(x1,y1) and Q=(x2,y2) be two arbitrary points on the elliptic curve and R=(x3,y3) be a point defined by R=P+Q.
When P≠Q, R=P+Q is an addition operation using addition formulas that are
x
3={(
y
2
−y
1)/(
x
2
−x
1)}{circumflex over ( )}2
−x
1
−x
2
y
3={(
y
2
−y
1)/(
x
2
−x
1)}(
x
1
−x
3)−
y
1
When P=Q, on the other hand, R=P+Q=P+P=2×P, so that R=P+Q is a doubling operation using doubling formulas that are
x
3={(3×1{circumflex over ( )}2+&agr;)/2
y
1
}
2
−
2
×
1
y
3={(3×1{circumflex over ( )}2+&agr;)/2y1
}(
x
1−
x
3)−
y
1
Note that the above operations are performed on a finite field where the elliptic curve is defined.
As shown in the addition formulas, when performing the addition operation over the elliptic curve in the 2-tuple coordinates called affine coordinates, it is necessary to perform one division over the finite field. One division over a finite field requires an average of 10 times as much computational complexity as one multiplication over the finite field.
To reduce this computational complexity, 3-tuple coordinates called projective coordinates are used instead.
Projective coordinates are 3-tuple coordinates made up of X, Y, and Z, wherein if a number n and two points (X,Y,Z) and (X′,Y′,Z′) satisfy the relationship
X′=nX, Y′=nY, Z′=nZ
then
(X,Y,Z)=(X′,Y′,Z′)
Projective coordinates (X,Y,Z) correspond to affine coordinates (x,y) as follows:
(x,y)→(x,y,1)
(X,Y,Z)→(X/Y,Y/Z) (where Z≈0)
Here, the sign &rarr
Hayes Gail
Matsushita Electric - Industrial Co., Ltd.
Price and Gess
Seal James
LandOfFree
Elliptic curve transformation device, utilization device and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Elliptic curve transformation device, utilization device and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Elliptic curve transformation device, utilization device and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2495034