Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-07-17
2001-07-17
Barron, Jr., Gilberto (Department: 2131)
Cryptography
Particular algorithmic function encoding
C380S030000, C713S174000, C708S492000
Reexamination Certificate
active
06263081
ABSTRACT:
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 a multiplication apparatus that performs the necessary calculation for encryption and digital signature techniques which use an elliptic curve
(2) Prior Art
Secret communication techniques allow communication to be performed without the content being revealed to third parties. Digital signature techniques, meanwhile, enable a receiver to verify the validity of the communicated content by confirming that the information is from the stated sender. Such signature techniques use an encryption technique 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 brief, public key techniques use different keys 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 logarithmic problem”. Representative examples of the discrete logarithmic 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
(Spinger-Verlag, 1987). A discrete logarithmic problem based on an elliptic curve is explained below.
The elliptic curve logarithmic problem is as follows. (E(GF(p)) is the elliptic curve E defined in the finite field GF(p), with the element G, given by dividing the order of E by a large prime number, being set as a base point. This being so, the problem is to find an integer x that satisfies the relationship
Y=xG
where the element Y is also given by the elliptic curve E and such value x actually exists.
The reason a discrete logarithmic problem assists in the security of public key encryption is that the above calculation is extremely difficult for a large finite field GF(p), with such calculation corresponding to the calculation of the inverse, or “hard direction”, of a one-way function.
The following is a description of the Elsamal signature technique which uses a discrete logarithmic problem based on an elliptic curve.
FIG. 13
shows a conventional configuration for the ElGamal signature algorithm based on an elliptic curve. This procedure is described in detail below.
(1) Settings by the Center
First, a prime number is set as p, an elliptic curve on the finite field GF(p) is set as E, and an element with the order q of E(GF(p)) is set as G. The public key of user A is set as Y
a
=x
a
G, while the secret key of user A is set as x
a
. The center announces the prime number p, the elliptic curve E and the base point G as system parameters, and A informs other users of his public key Y
a
.
(42) Signature Generation
1. Random number k generated.
2. R
1
=kG=(r
x
,r
y
) and s=m+r
x
*x
a
/k (mod q) calculated.
3. (R
1
,s) transmitted together with message m as signature.
(3) Signature Verification
Check to see whether sR
1
=mG+r
x
Y
a
is satisfied.
As can be seen from the above example, a signature technique based on an elliptic curve requires the calculation of the total of kG that is a “multiple” of the fixed point G and r
x
Y
a
which is a multiple of the arbitrary point P (which in the above conventional example corresponds to the public key Y
a
). Two conventional methods for performing these calculations are described below.
The first method calculates a multiple of the fixed point G, and is described in detail in E. F. Brickell, D. M. Gordon, K. S. McCurley and D. B. Wilson,
Fast Exponentiation with Precomputation
(Advances in Cryptology-Proceedings of Eurocrypt '92, Lecture Notes in Computer Science, 1993, Springer-Verlag, pages 200-207).
First Conventional Method
The following is a simplified explanation of this first conventional method.
A 160-bit prime number is set as p, an elliptic curve on the finite field GF(p) is set as E. G and kG, which are elements of E(GF(p)), are calculated.
Step 1—Generation of Pre-Computation Table
A provisional calculation table is generated by calculating G
i
=(16
1
)G (where i=1, . . . ,40)
Step 2—Calculation of kG
A 160-bit positive integer k is expressed as
k=k
0
+k
1
*16+k
2
*16
2
+ . . . +k
40
*16
40
(where −7≦k
0
, . . . ,k
40
≦8)
kG is calculated by the following routine.
(Step 2-1)
B=A=&Sgr;sign (k
i
)G
i
(total for i where k
i
=8)
(Step 2-2)
d=7
(Step 2-3)
The following processing is performed while d≧1.
A=A+&Sgr;sign (k
i
)G
i
(total for i where k
i
=±d)
B=B+A
d=d−1
Return to Step 2-3
In this case kG is found as B=kG.
In the above method, a calculation which doubles a provisional total is not necessary, so that the procedure can be achieved through addition alone, although this means in that 44 calculations are required. Since there are cases where these additions are more time-consuming than when doubling is performed, the above procedure is not especially efficient.
A method for calculating exponential powers of an arbitrary point Y
a
on an elliptic curve is described in Koyama, Tsuruoka,
Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method
, Advances in Cryptology-Proceedings of Crypto'92, Lecture Notes in Computer Science, 1993, Springer-Verlag, pages 345-357. This is explained in detail below.
Second Conventional Method
The following is a simplified explanation of this second conventional method.
A 160-bit prime number is set as p, an elliptic curve on the finite field GF(p) is set as E, and the elements P and kP of the curve E(GF(p)) are calculated.
This prime number p is expressed in binary as
k=k
0
+k
1
+2+k
2
*2
2
+ . . . +k
159
*2
159
=[k
159 . . .
k
2
k
1
k
0
]
(where k
0
, . . . ,k
159
=0,1)
(Step 1)
This binary number is transformed into an addition-subtraction expression.
A bit sequence B which forms part of k is found from the lower-order k
i
bit
B=[1, . . . ,b
i
, . . . ,1]
When #B
1
−#B
0
≧3, the bit sequence is transformed into T(B) as shown below.
T(B)=[1,0, . . . ,t
i
, . . . ,−1], t
i
=b
i
−1
Here, #B
1
and #B
0
respectively express the number of “1” values and “0” values included in the partial bit sequence B. After transformation, k becomes T.
(Step 2—Division into Windows)
The value T is expressed as T=[t
160
, . . . ,t
2
,t
1
,t
0
] and the value T is scanned starting from the MSB (Most Significant Bit).
The bits are analyzed in order towards the LSB (Least Significant Bit) starting from the first bit with the value “1”, with the bit sequence being divided just before the first bit with the value “0” to appear within the following four bits. If no “0” value appears in the following four bits, these four bits are set as a window.
(Step 3—Pre-Computation Table Generated)
Values of sP where (s=3,5, . . . ,15) are calculated and are set as the pre-computation table.
(Step 4—kP Calculated)
T is analyzed starting from the MSB, and a value in the pre-computation table is added for each window in turn. After each addition, the result is multiplied by a power of two.
In this conventional example, however, there are many windows, meaning that a large number of additions need to be performed in Step 4. As a result, this calculation is as inefficient as the previous method of finding a multiple of a fixed point value.
SUMMARY OF THE INVENTION
It is a primary object of the present invention to provide a calculation apparatus that can efficiently calculate a multiple of a fixed point and a multiple of an arbitrary point which are required by encryption methods and signature methods that use ellipti
Miyaji Atsuko
Ono Takatoshi
Barron Jr. Gilberto
Matsushita Electric - Industrial Co., Ltd.
Price and Gess
Seal James
LandOfFree
Elliptic curve calculation apparatus capable of calculating... 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 calculation apparatus capable of calculating..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Elliptic curve calculation apparatus capable of calculating... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2506845