Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-23
2001-11-13
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S606000
Reexamination Certificate
active
06317769
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to an apparatus for processing a Rivest, Shamir, and Adelman (RSA) cryptographic system at high speeds, and more particularly to an apparatus for calculating Bc (mod n) which is needed in the RSA cryptographic system.
2. Prior Art
In order to process the RSA cryptographic system, the following equation (1) needs to be calculated for three numerical values, n, B, and C of longer than 512 bits.
B
c
(mod
n
) (1)
The value of Eq. (1) becomes 1, when n is a prime greater than B and C is equal to (n−1). Also, when C=n, the value of Eq. (1) becomes B. That is, the value becomes as follows:
B
n−1
≡1(mod
n
)
B
n
≡B
(mod
n
).
These are known as a Fermat's principle.
In the case where n is the product of two primes p and q, the value of Eq. (1) becomes 1, when B is relatively prime with (p−1) and (q−1) and C is a multiple of (p−I)−(q−1). Also, when the value of Eq. (1) is divided by (p−1)·(q−1) and the reminder is 1, the value becomes equal to the original value B. That is, n can be solved into two factors, such as n=p·q, and if (B, k)=1 (note: the greatest common divider is 1) and k=(p−1)·(q−1), the following equations are established for the k.
B
k
≡1(mod
n
)
B
k+1
≡B
(mod
n
).
This is referred to as an Euler's theorem. The Fermat's principle forms part of the Euler's theorem.
Now, if the following e and d exist, e can be employed as an encryption key and d as an decryption key.
e·d≡
1(mod
k
)
That is, a value encrypted in e can be decrypted by d. Also, since conversely a value encrypted in d can be decrypted by e, communication can be performed between specific two, while opponents are being confirmed with each other.
For example, when B is encrypted and sent,
B
e
≡M
(mod
n
)
is calculated and M is sent. Then, at the receiving side,
M
d
≡B
ed
≡B
(mod
n
)
is calculated and B is decrypted. Note that (B, e)=1 and (B, d) 1.
In the case of a process such as authentication to confirm opponents, by using an X which is known to both the transmitting side calculates,
X
d
≡N
and transmits N. Then, the receiving side calculates N
e
, and if x can be derived from
N
e
≡X
ed
≡X,
it can be confirmed that the receiving side is communicating with a right opponent. Note that (B e)=1 and (B, d)=1.
If a single set of e and d such as this is found, e and d will be raised to the power of m, respectively, and em and dm will be employed as a set of new keys. The number of sets of keys (em, dm) is about (p−1)·(q−1), and since this number is sufficiently large, sets of keys (em, dm) can be assigned to communication paths by 1 to 1. Here, if a value of n is determined, a set of the remainders of (em, dm) modulo (p−1)·(q−1)=k can be generated by the same hardware. That is, the following equations can be generated.
e
m
≡em
(mod
k
)
d
m
≡dm
(mod
k
)
In the RSA cryptographic system, encryption and decryption can be performed by the same hardware, there is reversibility, and it is difficult for a person who does not know a key to solve a cryptograph. For these reasons, the RSA cryptographic system has been extensively used.
An example of an apparatus, which actually makes a calculation by using principles such as this, is disclosed in Japanese Published Examined Patent Application No. 7-86822. Now, preparations for the following description are made. For example, it is understood at once that the remainder of 8×9 modulo 7 is 2 (=8×9−7×10). If this calculation is expressed by a binary expression, the remainder of 8×9 modulo 7 is equivalent to the remainder of 1000×1001 modulo 0111. When this is simply calculated, multiplication is first performed as shown in FIG.
5
. If such calculation is performed, a 7-bit register will be needed for multiplication of 4 bits×4 bits. Therefore, when a greater number of bits are calculated by hardware, a load on the hardware becomes larger. Hence, as shown in
FIG. 6
, in step 1, 1000 (8) is fetched and the remainder of 1000 (8) is calculated modulo 0111 (1001, which is a complement of 2 of 0111, is added), so 0001 is obtained. Then, in step 2, 0001 is shifted (that is, “doubled”) and the remainder of 0010 is calculated modulo 0111. In this stage, since 0010 is smaller than 0111, 0010 is obtained as it is. In step 3, 0010 is shifted (that is, “doubled”) and the remainder of 0100 is calculated modulo 0111. In this stage, since 0100 is smaller than 0111, 0100 is obtained as it is. In step 4, 0100 is shifted (that is, “doubled”) and the remainder of 1000 is calculated modulo 0111. As a result, 0001 is obtained. Next, when the result 0001 of step 1 corresponding to the least significant bit (LSB) where 1 exists in 1001 (9) and the result 0001 of step 4 corresponding to the most significant bit (MSB) where 1 likewise exists in 1001 are added, 0010 (2) can be obtained. The aforementioned calculation can be performed by using a 4bit (or 5-bit if a carry bit is included) register. The result of the shift and MOD calculations corresponding to bit positions at which 1 exists among 1001 (9) has been added. However, even if the remainder of 1001 (9) modulo
7
were first calculated (in this example, 0010 is obtained) and then the result (result of step 2 in this example) of the shift and MOD calculations corresponding to bit positions at which 1 exists among 0010 are added, the same result (0010 in this example) would be obtained.
In view of the foregoing points, the apparatus shown in Japanese Published Examined Patent Application No. 7-86822 will be described with FIG.
8
. Since it is assumed that M(mod n)=C is calculated, this description is made according to the assumption. M is input by a numerical value input and is input to a multiplicand register
1
. The output of this register
1
is input to a remainder arithmetic unit
3
, in which the aforementioned shift and MOD calculations are performed. In order to perform the MOD calculation, n has been input to a divisor register
2
as a divisor input. Note that since subtraction is performed, a complement of 2 of n is input. Then, the result of the remainder arithmetic unit
3
is input to the multiplicand register
1
through a multiplicand selector
11
. This processing is iterated by the number of bits of M.
Also, M is set to a multiplier register
10
through an input register
7
, a register
8
, and a multiplier register
9
. The result of the remainder arithmetic unit
3
corresponding to a bit at which 1 exists since the LSB in this M is input to a cumulative remainder arithmetic unit
4
through a remainder selector
12
. In this cumulative remainder arithmetic unit
4
, the result of the remainder arithmetic unit
3
is added to the result of a cumulative remainder register
5
and the remainder of n is calculated, and the result is stored in the cumulative remainder register
5
. This corresponds to the addition processing described last in the example of 8×9 (mod 7). If the foregoing process is performed by the amount of the bits of M, M×M (mod n) will be calculated and the result will be output to the cumulative remainder register S. If it is desired that M
2
(mod n) is calculated, the result will be input to the output register
13
and the processing will be ended.
However, calculation is usually performed according to the bits of the exponent e input to an exponent register
6
. Therefore, for power arithmetic, the multiplier selector
9
deals in sequence with each of the bit outputs which lead from the most significant bit (MSB) of the exponent register
6
to the least significant bit (LSB). When the logic value is 0, the previous cumulative remainder value S (this is stored in the multiplicand register
1
) stored in the cumulative remainder register
5
is set to the multiplier register
10
. As a conse
Kobayashi Yoshinao
Nijima Hideto
Satoh Akashi
Herzberg Louis P.
International Business Machines - Corporation
Malzahn David H.
Scully Scott Murphy & Presser
LandOfFree
Apparatus for calculating of Bc (mod n) with repeatedly... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for calculating of Bc (mod n) with repeatedly..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for calculating of Bc (mod n) with repeatedly... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2608636