Registers – Calculators – Input-output calculator to indicator – printer – etc.
Reexamination Certificate
2001-12-18
2004-08-10
Frech, Karl D. (Department: 2876)
Registers
Calculators
Input-output calculator to indicator, printer, etc.
C708S490000
Reexamination Certificate
active
06772942
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to an arithmetic circuit, and more particularly to a circuit for increasing the speed for modular multiplication in a public-key cryptosystem.
Public-key cryptography (asymmetrical cryptography) is generally used to maintain the confidentiality and guarantee the digital authenticity of information being transmitted. Public-key cryptography is a system for transmitting information and a cryptographic method for transmitting information using a pair of keys consisting of a public key and a secret key. A sender uses the public key of a recipient to encrypt a text, and when the cipher text is decrypted, a secret key known only to the recipient is used. According to the public-key cryptography, since (a) unlike the common-key cryptography (symmetrical cryptography) there is no need for correspondents to share and employ a single common key and (b) widespread disclosure of a public key involves no appreciable risk, the maintenance of secrecy while communicating with an unlimited number of persons is possible. Further, when public-key cryptography is employed for digital authentication or to prepare a digital signature, the credibility and trustworthiness of a person with whom one is not acquainted can be established. Therefore, it can readily be asserted that public-key cryptography is a requisite technique for a network supported by a communication system, such as the Internet, and for business transactions that are entered into in such a network.
RSA is the most popular public-key cryptography. The safety afforded by RSA is based on a discrete logarithm problem for a very large integer, or on the difficulty encountered in factoring primes. For example, plaintext M is encrypted into ciphertext C by using a public key (e,n) in accordance with the relational equation C=M
e
(mod n), (M is formed as a block that it is smaller than the integer n). To decrypt the ciphertext C, a discrete logarithm problem (while using a, y and p, find x that satisfies y=a
x
(mod p)) must be performed, and the amount represented by O(2
SQRT(log n)
) must be solved (SQRT is a function for providing a square root). When the integer n is a value having a length that is at least equal to or greater than 512 bits, and that preferably is equal to or greater than 1024 bits, code breaking within a practical time is difficult.
However, when a secret key (d,n) is employed that has the following relationship with the public key (e,n), ed(mod lcm(p−1,q−1))=1, n=pq (wherein p and q are satisfactorily large prime numbers), the plaintext M can be easily obtained by using the relational equation M=C
d
(mod n) (wherein lcm(a,b) provides the least common product of a and b).
By using a binary representation of an exponent, and the modular-squaring operation and the modular-multiplication operation are repeated, so that at most twice the bit length of the exponent is required for the modular-multiplication operation.
However, even the above described modular-exponentiation operation requires more calculations than are required for symmetrical cryptography, such as DES (Data Encryption Standard). Therefore, the preparation and use of as efficient an algorithm as possible is demanded.
The Montgomery multiplication method is a method for increasing the speed of the modular-squaring operation and the modular-multiplication operation in the above modular-exponentiation operation. The Montgomery multiplication method, as described in “Modular Multiplication Without Trial Division”, by Peter L. Montgomery, Mathematics of computations, Vol. 44, No. 170 April 1985, pp. 519-522, is a method whereby addition, multiplication and a shift operation are repeated to perform the modular-multiplication operation while requiring fewer calculations than are required by division for which subtraction is repetitively performed. The essential calculation portion P≡XYR
−1
(mod n) of the Montgomery multiplication is shown below using pseudo code 1.x. It should be noted that in P≡XYR
−1
(mod n), R=(2
r
)
m
and N≡−n
−1
(mod 2
r
). Further, it should be noted that a line number is added to the left of each line in the pseudo code (this provision is hereinafter applied).
(1.1) p=0;
(1.2) for (i=0; i<m; i++){
(1.3) t=(p
0
+x
i
y
0
) N(mod 2
r
);
(1.4) P=(P+x
i
Y+t·n)/2
r
;
(1.5)}
(1.6) if (P≧n) P=P−n;
As is shown in the pseudo code 1.x, the repetitive calculation of the essential portion is performed as follows. First, X is divided into m blocks x
i
(X=(x
m−1
, x
m−2
, . . . , x
1
, x
0
)), and a partial product addition of (x
i
Y) with Y is repeated m times (line numbers 1.2 to 1.5). At this time, a product “t·n” is added each time to make p
0
equal to 0, where p
0
is the lowest block of the intermediate results P (line number 1.4). In this case, t is defined in line 1.3. Further, P is shifted to the right r bits, i.e., is multiplied by 2
−r
(line number 1.4). It should be noted that since 2
−rm
=R
−1
is obtained by performing the r-bit shift operation m times.
Assuming that a 32-bit multiplier is used to perform the Montgomery multiplication of 512 bits, a loop is repeated 512/32=16 times. In the above pseudo code, 32 bits×512 bits, such as x
i
·Y or t·n, is shown for simplification; actually, however, Y and n, of 512 bits each, are divided into 32-bit blocks for calculation. That is, in the calculation the partial product, addition of P is a double loop for which m=16. An example process for performing the Montgomery multiplication using a double loop is shown below using pseudo code 2.x.
(2.1) P=0;
(2.2) for (i=0; i<m; i++){
(2.3) t=p
0
+x
i
y
0
(mod 2
r
);
(2.4) t=t·N(mod 2
r
);
(2.5) c=0;
(2.6) for(j=0; j<m; j++){
(2.7) tmp=p
j
+x
i
y
j
+c;
(2.8) tmp=tmp+t·n
j
;
(2.9) if (j!=0)p
j−1
=tmp(mod 2
r
);
(2.10) c=tmp/2
r
;
(2.11)}
(2.12) P
m−1
=c;
(2.13)}
(2.14) if (P≧n) P=P−n;
In this case, X, Y and n are divided into m blocks, i.e.,
X=(x
m−1
, x
m−2
, . . . x
1
, x
0
)
Y=(y
m−1
, y
m−2
, . . . y
1
, y
0
)
n=(n
m−1
, n
m−2
, . . . n
1
, n
0
)
Assuming one multiplier is employed, two product additions are required for the calculation of the intermediate result tmp. Variables p
j
, x
i
, y
j
, t and n
j
are r-bit length numbers, and variable c is a carry from a lower block. In the above pseudo code 2.x, in one iteration of the j-loop, the addition of the 2r-bit length numbers x
i
·y
j
and t·n
j
and the addition of the r+1-bit length number p
j
and c are performed (line numbers 2.6 to 2.11), so that following the product addition the intermediate result tmp is a 2r+1-bit length number. The lower r bits of tmp are stored as variable p
j
, and the upper r+1 bits are stored as the variable c (line numbers 2.9 and 2.10).
In contrast, the addition of x
i
·y
j
and t·n
j
can be performed as two separate loops, as is shown in the following example, using pseudo code 3.x.
(3.1) P=0;
(3.2) for (i=0; i<m; i++){
(3.3) c=0;
(3.4) for (j=0; j<m; j++){
(3.5) tmp=p
j
+x
i
·y
j
+c;
(3.6) p
j
=tmp(mod 2
r
);
(3.7) c=tmp/2
r
;
(3.8)};
(3.9) p
m
=c; c=0;
(3.10) t=p
0
·N(mod 2
r
);
(3.11) for (j=0; j<m; j++){
(3.12) tmp=p
j
+t·n
j
+c;
(3.13) if (j!=0)p
j−1
=tmp(mod 2
r
);
(3.14) c=tmp/2
r
;
(3.15)};
(3.16) p
m−1
=p
m
+c;
(3.17)};
(3.18) if (P≧n) P=P−n;
In the pseudo code 3.x example, the variable p
j
has the r-bit length, and the variable tmp has the 2r-bit length.
In either case, fo
Satoh Akashi
Takano Kohji
Capella Steven
Frech Karl D.
Labaze Edwyn
LandOfFree
Arithmetic circuit to increase the speed of a modular... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arithmetic circuit to increase the speed of a modular..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic circuit to increase the speed of a modular... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3359193