Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-11-04
2004-09-21
Darrow, Justin T. (Department: 2132)
Cryptography
Particular algorithmic function encoding
C380S030000, C713S176000, C708S492000, C708S523000, C708S653000
Reexamination Certificate
active
06795553
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus for modular inversion which is carried out for information security, for example, in digital cryptosystems and digital authentication systems which use encryption key generation, digital signature and blind signature schemes, and elliptic cryptosystem and so forth. The invention also pertains to a recording medium with the modular inversion method recorded thereon.
In the field of information security it is well-known that the calculation of modular inverse over a prime finite field GF(p) (where p is a prime) or residue class ring Z/NZ (Z is a group of integers and N is a positive integer) takes a wide variety of forms, some of which will be described below.
(a) Generation of sum (x
3
, y
3
) of two points (x
1
, y
1
) and (x
2
, y
3
) on an elliptic curve E/GF(p):
&lgr;=(
y
2
−y
1
)/(
x
2
−x
1
)mod
p
(a-1)
x
3
=&lgr;
2
−x
1
−x
2
mod
p
(a-2)
y
3
=&lgr;(
x
1
−x
3
)−
y
1
mod
p
(a-3)
(b) Part of signature generation of digital signature system ESIGN:
y=w
/(
kx
k−1
)mod
p
(b-1)
where x is an integer 1≦x≦pq−1, w is an integer in the range of 0≦w≦p−1, k&egr;Z, and p and q are primes.
(c) Blind signature generation of digital signature system RSA:
s′=
(
r
e
m
)
d
mod
N
(c-1)
s=s′/r
mod
N
(c-2)
where r and m are integers 0≦r and m≦N−1, and e and d are integers 1≦e and d≦&phgr;(N)−1, respectively.
The above examples use modular multiplications and modular inversions. The Montgomery method has been proposed to efficiently calculate modular residues. Listed below are definitions of some types of modular inversion that suit the Montgomery method.
Normal inversion
i
1
(X) = X
−1
mod N
Kaliski inversion
i
2
(X) = X
−1
B mod N
Montgomery inversion
i
3
(X) = X
−1
B
2
mod N
where B=2
n
, n is the number of bits of N, N<B<2N and X&egr;Z/NZ The modular inversion mentioned herein includes any types of modular inversion as well as the above. Replacing the N with a prime p, the abovementioned inverse will be an inverse over GF(p). The following description will be given only of Z/NZ
Conventionally, for inputs X and N where X is equal to or greater than zero and smaller than N, a modular inverse of X over Z/NZ is calculated, for example, using an extended binary GCD method (extended binary Greatest Common Divisor method, an algorithm for producing X
−1
2
k
mod N and k, the former being expressed by bgcd(X, N)) The following example will be described in connection with the calculation of a Montgomery inverse.
Method 1:
Step 1: Calculate S and k by
S=bgcd
(
X, N
)=
X
−1
2
k
mod
N
(1)
where n≦k≦2n.
Step 2: Calculate a modular inverse R by
R=S
2
2n−k
mod
N=N
−1
2
2n
mod
N
(2)
Step 1 is a process of executing the extended binary GCD algorithm for the inputs X and N. Since 2n−k>0, Step 2 is to calculate multiplication by power of 2.
The calculation (b) can also be used to obtain a Montgomery inverse by the method 2 shown below.
Incidentally, when d<0,
(a) Multiplication by power of 2: X2
d
mod N
(b) Division by power of 2: X2
−d
mod N
the calculation (b) can be done faster than (a).
Method 2:
Step 1:
Y=X
2
−n
mod
N
(3)
Step 2:
S=bgcd
(
Y, N
)(=
X
−1
2
n+k
mod
N
) (4)
Step 3:
R=S
2
−(k−n)
mod
N
(=
X
−1
2
2n
mod
N
) (5)
Since k−n≧0, Step 3 performs a division by power of 2.
If the multiplication (a) and the division (b) consumes the same amount of time, then Method 1 involving the smaller number of steps enables the calculation to be made in a shorter time than in the case of using Method 2. In practice, however, since the division (b) can be conducted in a shorter time, it is presumed that the modular inversion by Method 2 may sometimes be processed in a shorter time.
Assuming that N is too large a value to calculate or process by an ordinary computer or processor at a time, the amounts of time for the calculations (a) and (b) increase as d becomes larger.
For example, in the case of using a method in which elementary operations are
(a)′ Multiplication by 2: X2 mod N
(b)′ Division by 2: X2
−1
mod N
and the calculation (a)′ is carried out d times as the calculation (a), the time for calculation (a) is d times longer than the time for calculation (a)′. Similarly, the time for calculation (b) is d times longer than that for calculation (b)′. The operations corresponding to calculations (a)′ and (b)′ will hereinafter be referred to as an elementary operation.
Method 2 conducts division by power of 2 instead of performing multiplication by power of 2 in Method 1, but needs to perform the elementary operation a larger number of times than does Method 1.
For example, when k=1.41n (It has been experimentally demonstrated that k and n bear this relation on average.) Method 1 performs the Bgcd algorithm, and besides, the elementary operation 0.59 times in Step 2. On the other hand, Method 2 performs the elementary operation n times in Step 1 and 0.41 n times in Step 3 in addition to the Bgcd algorithm, and hence it conducts the elementary calculation a total of 1.41n times. Accordingly, there is no possibility of Method 2 becoming faster than Method 1 unless the division by power of 2 is considerably faster than the multiplication by power of 2 (more than 2.3 times faster in the above example). Conversely, even if means for speeding up the multiplication by power 2, though not feasible at present, is available, no speedups are possible if only the division by power of 2 occurs.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a calculating method which permits reduction of the time for modular inversion necessary for information security, a modular inversion apparatus using the method, and a recording medium with a program recorded thereon for implementing the method.
Another object of the present invention is to provide a modular inversion method which enables multiplication and division by power of 2 to be performed efficiently and hence in a short time, a modular inversion apparatus using the method, and a recording medium with a program recorded thereon for implementing the method.
Still another object of the present invention is to provide a modular inversion method which enables an extended binary GCD to be calculated efficiently and hence in a short time, a modular inversion apparatus using the method, and a recording medium with a program recorded thereon for implementing the method.
The modular inversion method, the apparatus using the method and the program recorded on a recording medium for implementing the method according to a first aspect of the present invention:
(a) calculate Y, for n-bit input values X and N, by the following equation using a predetermined value t
Y=X
2
−t
mod
N;
(b) calculate an extended binary GCD for said Y and N by the following equation to obtain S and k
S=bgcd
(
Y, N
)=
Y
−1
2
k
mod
N;
and
(c) perform the following equation using said S, k and t
R=S
2
−(k+t−m)
mod
N, m=
0,
n,
or 2
n
and output said R as the modular inversion result.
According to a second aspect of the present invention, in the above modular inversion a division of input values S and N by power of 2 represented as S
2−w
mod N, w being a predetermined number of bits to be calculated or processed at a time, comprises the steps of:
(a) calculating n′=−N
−1
mod 2
w
for input values S and N;
(b) calculating s′=Sn′ mod 2
w
from said n′ and S;
(c) calculating q=S+s′N from said s′, S and N; an
Kobayashi Tetsutaro
Morita Hikaru
Connolly Bove & Lodge & Hutz LLP
Darrow Justin T.
Nippon Telegraph and Telephone Corporation
LandOfFree
Method and apparatus for modular inversion for information... 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 and apparatus for modular inversion for information..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for modular inversion for information... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3227142