JP2006091086A - Semiconductor device with montgomery inverse element arithmetic unit, and ic card - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To solve the problem that it takes time to perform a multiple-length precision integer operation for calculating a Montgomery inverse element and leak information due to a time difference of processing is generated depending upon an operation result. <P>SOLUTION: By a Montgomery inverse element arithmetic system by conventional technology, the direction of subtraction is determined after multiple-length precision integers are compared with each other, and then an operation is carried out. Namely, it is guaranteed that an intermediate result of the operation is always a positive value, but the multiple-length precision operation can directly be performed without making the large/small comparison by allowing the intermediate result to be a negative value, thereby decreasing the number of operations between multiple-length precision integers. <P>COPYRIGHT: (C)2006,JPO&NCIPI

Description

  The present invention relates to a semiconductor device equipped with a Montgomery inverse arithmetic unit, and particularly relates to cryptographic processing of a tamper resistant device such as a highly confidential IC card.

Cryptographic processing includes multiple multiplication precision remainder multiplication, and much of the processing time is spent on remainder multiplication. As a method of performing multi-precision precision multiplication, Montgomery modular multiplication is often used in which modular multiplication can be performed without calculating a high-cost division during calculation. Therefore, the Montgomery type inverse element by Euclidean algorithm (E.Savas, CK Koc, "The Montgomery Modular Inverse-Revised", IEEE Transactions) on COMPUTERS, VOL.49, NO.7, JULY 2000). 1 and 2 are Montgomery-type inverse element calculation algorithms using the extended Euclidean mutual division method according to the conventional method.
In the Montgomery inverse calculation method using the Euclidean mutual division method, assuming that the modulus is a and the value to calculate the inverse is b, k = 0, p = 1, r = 0, u = a, q = 0, s = 1 , V = b as an initial value,

なる関係がなりたつ。最終的にmod aした値のみが必要なので、式(1)、式(2)の両辺のmod a を取ると、

The relationship becomes. Since only the value that was finally mod a is required, taking the mod a on both sides of Equation (1) and Equation (2),

となる。
初期値からスタートし、ｕの値が１となるまで繰り返し次の演算を行う。
処理(1) ｕが偶数であれば、ｕを右シフトし、ｋの値を＋１する。ｋが＋１された後も式(4)が成り立つように、ｓ←２ｓとし、処理(5)に移行する。ｕが偶数で無い場合は、処理(2)へ移行する。
処理(2) ｖが偶数であれば、ｖを右シフトし、ｋの値を＋１する。ｋが＋１された後も式(3)が成り立つように、ｒ←２ｒとすし、処理(4)に移行する。ｕが偶数で無い場合は、処理(3)へ移行する。
処理(3) 処理(3)にたどり着くのは、ｕ、ｖの両者が奇数の場合のみである。したがって、ｕ、ｖの差を計算すると、必ず偶数となる。まず、ｕ＞ｖの場合は、式(4)から式(3)を引き、両辺を２で割った値で、ｒとｕの値を更新する。具体的には、右辺はｕ←（ｕ−ｖ）／２、左辺はｒ←ｒ＋ｓとして、２で割る代わりに、ｋ←ｋ＋１とする。ｋが＋１された後も、式(4)が成り立つように、ｓ←２ｓとし、処理(5)に移行する。ｕ＞ｖでない場合は、処理(4)へ移行する。
処理(4) ここにたどり着くのは、ｕ、ｖが共に奇数で、ｕ≦ｖの場合のみである。式(3)から式(4)を引き、両辺を２で割った値で、ｓとｖの値を更新する。具体的には、右辺はｖ←（ｖ−ｕ）／２、左辺はｓ←ｓ＋ｒとして、２で割る代わりに、ｋ←ｋ＋１とする。ｋが＋１された後も、式(3)が成り立つように、ｒ←２ｒとし、処理(5)に移行する。
処理(5) ｖの値が０より大きい場合は、処理(1)へ移行する。
以上の処理により、ａが奇数で、ａとｂが互いに素である場合は、ｖ＝０になると、必ずｕ＝１となる。処理(1)から処理(4)のいずれかが１回処理されると、ｕもしくはｖの大きさが半分以下になる。しがたって、ａのビット数をｎ、ｂのビット数をｍとすると、最大ｎ＋ｍ＋１回の計算により、ｖ＝０にたどり着く。右辺の計算は、拡張ユークリッド互除法の演算と等価であるので、ａとｂが互いに素でない場合には、１１２０でｕが１以上の値となり、エラーとなる。ｕ＝１では、式(3)は

It becomes.
Starting from the initial value, the next calculation is repeated until the value of u becomes 1.
Process (1) If u is an even number, u is shifted right and the value of k is incremented by one. After k is incremented by 1, s ← 2s is set so that Expression (4) is satisfied, and the process proceeds to the process (5). If u is not an even number, the process proceeds to process (2).
Process (2) If v is an even number, v is shifted to the right and the value of k is incremented by one. Even after k is incremented by 1, r ← 2r is set so that the expression (3) is satisfied, and the process proceeds to the process (4). If u is not an even number, the process proceeds to process (3).
Process (3) Process (3) is reached only when both u and v are odd numbers. Therefore, when the difference between u and v is calculated, it is always an even number. First, when u> v, the value of r and u is updated by subtracting equation (3) from equation (4) and dividing both sides by 2. Specifically, u ← (u−v) / 2 on the right side and r ← r + s on the left side, and k ← k + 1 instead of dividing by 2. Even after k is incremented by 1, s ← 2s is set so that Expression (4) is satisfied, and the process proceeds to processing (5). If u> v is not satisfied, the process proceeds to process (4).
Process (4) The process arrives here only when u and v are both odd and u ≦ v. The value of s and v is updated by subtracting the equation (4) from the equation (3) and dividing both sides by 2. Specifically, the right side is v ← (v−u) / 2 and the left side is s ← s + r, and instead of dividing by 2, k ← k + 1. Even after k is incremented by 1, r ← 2r is set so that Expression (3) is satisfied, and the process proceeds to processing (5).
Process (5) When the value of v is larger than 0, the process proceeds to process (1).
With the above processing, when a is an odd number and a and b are relatively prime, u = 1 is always obtained when v = 0. When any one of the processes (1) to (4) is processed once, the size of u or v becomes half or less. Therefore, assuming that the number of bits of a is n and the number of bits of b is m, v = 0 is reached by a maximum of n + m + 1 calculations. Since the calculation on the right side is equivalent to the operation of the extended Euclidean algorithm, if a and b are not prime, u becomes a value of 1 or more in 1120, and an error occurs. When u = 1, equation (3) becomes

となり、両辺に

And on both sides

を掛けると、

Multiply

を得る。モンゴメリ型逆元で求めたいのは、

Get. What we want to find with the Montgomery inverse

であるので、図２に示される処理フローにより、補正を行う。
まず

Therefore, correction is performed according to the processing flow shown in FIG.
First

を乗じ、

Multiplied by

を得る。
具体的には、（ｋ−ｎ）回右シフトを行うことにより、式(8)を乗じる。右シフトを行う際に、値が偶数の場合は、最下位ビットが０であるので、右シフトをそのまま行えるが、値が奇数の場合は、最下位ビットが１であるので、右シフトをそのまま行うことはできないため、ａを加算して偶数にした後、右シフトを行う。モンゴメリ逆元補正処理の処理フロー図２に示す。２０２０でループカウンタを設定し、２０３０でループカウンタのチェックを行う。２０４０、２０５０、２０６０の処理は、ｒの値を右シフトするための処理で、右シフト可能なように、奇数の場合は法ａを加算して、偶数に変換する。ｋ−ｎ回右シフトを行う。 最後に、符号を反転させるためにａから式(9)を引き、

Get.
Specifically, the equation (8) is multiplied by performing a right shift (k−n) times. When performing a right shift, if the value is an even number, the least significant bit is 0, so the right shift can be performed as it is. However, if the value is an odd number, the least significant bit is 1, so the right shift is performed as it is. Since it cannot be performed, right shift is performed after adding a to an even number. FIG. 2 shows a processing flow of Montgomery inverse element correction processing. The loop counter is set at 2020, and the loop counter is checked at 2030. The processes 2040, 2050, and 2060 are processes for shifting the value of r to the right, and in the case of an odd number, the modulus a is added and converted into an even number so that the value can be shifted to the right. Shift right kn times. Finally, subtract equation (9) from a to reverse the sign,

を得る。図２では、２０８０でこの処理が行われる。

Get. In FIG. 2, this processing is performed at 2080.

Japanese Patent Laid-Open No. 10-207689 "The Montgomery Modular Inverse-Revisited", IEEE Transactions on COMPUTERS, VOL.49, NO.7, JULY 2000

In public key cryptosystems represented by RSA and ECC, cryptographic processing is performed by computation on a finite element field. In the cryptographic process, an output value is calculated for an input value using a part of the parameters as secret information. For example, in RSA encryption, the decryption formula
M = C ^d mod N
The ciphertext C can be converted into plaintext M by calculating, but in this formula, the exponent d is secret information, and if the value of this d is known, in RSA cryptography, N is the public key. Therefore, anyone can return the cipher C to the plaintext M using the decryption formula. Further, as a method for speeding up the operation by utilizing the fact that N is a product of two large prime numbers p and q, a speed-up method using CRT (Chinese Remainder Theorem) is known. In the CRT operation, the operation on the modulo N is divided into the operation of the modulo p and the modulo q, and finally the two operation results are combined to obtain the same result as the operation on the modulo N. When the public exponent of RSA is e, the secret exponent d is calculated by being divided into d _p = e ⁻¹ mod (p−1) and d _q = e ⁻¹ mod (q−1).

In the case of an implementation that uses ciphertext C as it is for computation, if ciphertext C that is specially selected so that many bits are 0 and only some bits are 1 is observed, current consumption during computation is observed. Thus, the secret indices d _p and d _q can be estimated. Since the definition of the inverse element and the secret exponent d _p is less than or equal to p-1, the natural number k such that 1 <k ≦ e
ed _p = (p-1) k + 1
And solving for kp,
kp = ed _p + k-1
It becomes. Since the value of N is the product of the prime numbers p and q, gcd (ed _p + k-1, N) is calculated while changing the value of k from 1 to e, and when the value of gcd is other than 1, p is obtained, and the value of q can be easily obtained from q = N / p.
d = e ^-1 mod (p-1) (q-1)
I know the secret key more. In order to prevent such an attack, a random number r is prepared,
C _p = C mod p
Instead of
C _p r ^e mod p
To calculate and finally remove the effect of r,
r ^-1 mod p
There is a countermeasure technique of multiplying by. If p can be estimated in the process of calculating r ⁻¹ mod p, the secret key d can be calculated after all. As a method of computing the inverse element, a method using the extended Euclidean mutual division method is generally used. However, in the extended Euclidean mutual aid method, since the internal state at the end of the calculation is known, the calculation process up to that is If known, the modulo value can be calculated backwards. In the case of r ^-1 mod p, it means that the modulus value p can be estimated.
Therefore, in the extended Euclidean mutual assistance method and the algorithm obtained by extending the extended Euclidean mutual assistance method, it is important for security to hide the operation procedure from the outside.

  In the Montgomery inverse operation method according to the prior art, it is necessary to calculate either u−v or v−u based on the determination result after comparing the size of u and v having a large bit length. In order to compare the magnitudes of u and v, it is necessary to subtract multiple precision integers. If it is determined that u ≦ v after determining the magnitude relationship between u and v, v− It is necessary to recalculate or to reverse the sign of the calculation result. In the step of calculating uv or uv, since u and v are both odd numbers, the value of uv is an even number. When sign inversion of even values is performed, carry propagation always occurs, so that it is difficult to calculate at high speed. Further, when uv is calculated for speeding up and sign inversion processing is performed as necessary, there is a difference in calculation time due to the magnitude relationship between v and u. This difference becomes leak information, and secret information can be estimated. In addition, both an adder and a subtracter for multiple precision integers are required.

In the Montgomery inverse operation method according to the prior art, the magnitudes of u and v are compared in order to ensure that the intermediate results u and v are always positive values. In Montgomery-type inverse element operation, even or odd numbers of u or v are important information. Even if they are negative values, even / odd numbers are determined by only the least significant bit as well as positive values. it can. Therefore, uv is not calculated, but uv is always calculated. If the result is negative, correction is performed when uv is next calculated. In the improved Montgomery inverse operation method of the present invention, it is possible to replace the determination of u and v with the sign of the value of v by allowing the value of v to be negative. Since the code can be determined by examining only the most significant bit, the amount of calculation can be greatly reduced as compared with a size comparison that requires subtraction. The true value of v is equal to the absolute value of v.
Further, since the processing performed after the determination of the most significant bit of v performs almost the same calculation regardless of the determination result, the leak information becomes extremely small.
As the Montgomery inverse, the final required value is

であるが、従来技術によるモンゴメリ逆元演算では、

However, in the Montgomery inverse operation according to the prior art,

を求めた後に、

After asking for

を計算して、

To calculate

を求めている。ｓ、ｒについても負の値を取ることを容認すると、直接

Seeking. Accepting negative values for s and r, directly

が求められるようになる。
従来技術によるモンゴメリ逆元演算では、ここで得られるｒの値は、
０＜ｒ＜２ａ
であるので、ａ以下になるように、
ａ≦ｒ
である場合は、
ｒ←ｒ−ａ
を計算する。一方、ｓ、ｒに負の値を容認した場合、式(3)、式(4)のｂを(−ｂ)に置き換え、式(3)を

Will be required.
In the Montgomery inverse operation according to the prior art, the value of r obtained here is
0 <r <2a
So, so that it is below a,
a ≦ r
If
r ← r−a
Calculate On the other hand, if negative values are accepted for s and r, b in equation (3) and equation (4) is replaced with (−b), and equation (3) is

とおき、式(4)を

And formula (4)

とし、式(17)、式(18)が成り立つように、ｒとｓの初期値をそれぞれ、符号を反転し、
ｒ＝−０＝０
ｓ＝−１
とする。ｕ＝１と成ったとき、式(17)は、

And the signs of the initial values of r and s are reversed so that the equations (17) and (18) hold,
r = −0 = 0
s = -1
And When u = 1, equation (17) becomes

となるので、ｒの値は、

Therefore, the value of r is

となる。また、ｒやｓの値は、常に直前のｒ、ｓを２倍にした値であるか、ｓとｒを加算した値であるので、必ず負の値になり、値の範囲は、
−２ａ＜ｒ＜０
となる。この値を０≦ｒ＜ａとするには、まず
ｒ←ｒ＋ａ
の補正を行い、さらに補正後も
ｒ＜０
である場合に、
ｒ←ｒ＋ａ
をもう一度計算する。従来技術によるモンゴメリ逆元の最後で、オーバーフローをチェックするための大小判定が必ず必要なのと同様、本発明でも
ｒ←ｒ＋ａ
の補正が必須であるため、計算量的にはほぼ等価であるが、本発明では加算のみで補正が出来るという利点がある。すなわち、ｓ、ｒについて負の値を認める場合、多倍長精度整数演算器としては加算器のみがあれば、逆元計算が実現できる。

It becomes. Also, the values of r and s are always values obtained by doubling the preceding r and s, or are values obtained by adding s and r, so they are always negative values.
-2a <r <0
It becomes. In order to make this value 0 ≦ r <a, first, r ← r + a
And after the correction r <0
If
r ← r + a
Calculate again. In the present invention, r ← r + a is the same as the determination of the magnitude for checking the overflow is always required at the end of the Montgomery inverse by the prior art.
However, the present invention has an advantage that the correction can be performed only by addition. That is, when negative values are recognized for s and r, the inverse element calculation can be realized if there is only an adder as the multiple precision integer arithmetic unit.

  According to the present invention, it is possible to realize Montgomery-type inverse element calculation hardware and Montgomery-type inverse element calculation software with a small amount of leak information.

    FIG. 3 shows an embodiment of the present invention. When the modulo is a and the Montgomery inverse of b is calculated, when the processing of FIG.

が得られる。処理の流れは従来技術によるモンゴメリ逆元演算とは、ｕおよびｖが奇数である場合の処理が異なる。図２では、３３００で囲われた処理に相当する。本発明では、常に（ｕ−ｖ）／２を計算し、結果が正の値の場合は、結果をｕに格納し、結果が負の場合は、結果をｖに格納する。常に（ｕ−ｖ）／２を計算するので、ｖの値が正の場合はそのまま（ｕ−ｖ）／２を計算するが、ｖの値が負の場合は、減算ではなく、加算を行う。従来技術によるモンゴメリ逆元演算との違いは、ｖの値に負の値が現れるか否かだけであり、ｖの値が負数になった場合でも、絶対値を計算すれば、従来技術によるモンゴメリ逆元計算で現れる値と同一の値となる。
また、ｖの値自体は、モンゴメリ演算の終了判定のみで用いるので、負の値を格納しても問題にならない。

Is obtained. The processing flow is different from the Montgomery inverse operation according to the prior art in the case where u and v are odd numbers. In FIG. 2, this corresponds to the process surrounded by 3300. In the present invention, (u−v) / 2 is always calculated, and if the result is a positive value, the result is stored in u, and if the result is negative, the result is stored in v. Since (u−v) / 2 is always calculated, if the value of v is positive, (u−v) / 2 is calculated as it is. However, if the value of v is negative, addition is performed instead of subtraction. . The only difference from the Montgomery inverse operation according to the prior art is whether or not a negative value appears in the value of v. Even when the value of v becomes a negative number, if the absolute value is calculated, This is the same value that appears in the inverse calculation.
Further, since the value of v is used only for the end determination of the Montgomery calculation, it does not matter if a negative value is stored.

  FIG. 5 and FIG. 7 show an embodiment in which the portion 3300 of the embodiment of FIG. 3 is implemented by hardware.

  FIG. 5 shows an embodiment of the present invention, which is an embodiment in which the processing of 3300 in the processing flow of FIG. The processing of 3080 in FIG. 3 determines whether v is a negative number by checking the most significant bit of the value v stored in 5010, and determines whether u and v are added or subtracted. To tell. In 5040, the type of operation is determined in accordance with the signal 5030, and the arithmetic right shifter 5060 shifts the value by 1 bit to the right.

  Here, the arithmetic shift is used because the value to be shifted can take a negative value. In the Montgomery-type inverse element calculation method according to the prior art, as shown in FIG. 4 (circuitization of 1300 in FIG. 1), since u and v are always controlled to be positive values, shifting is performed with a simple logical shifter. However, in the present invention, a negative number may be input, and it is necessary to save a sign flag (MSB). The obtained calculation result is temporarily stored in a storage means w (5070) different from u and v. Whether to store the value of w in u or v depends on whether the value of w is a positive value, zero, or a negative value. The selector 5100 is controlled by the OR circuit 5080 to store w on the v side when the value of w is zero or negative.

  FIG. 6 is an explanatory diagram relating to a method of calculating the term (−v) when calculating (−v) instead of calculating u = u−v and calculating u−v using only the adder. Indicates. The value of v is always an odd number when the portion 3300 in FIG. 3 is executed. This is done only when the v or u value is even, and only the part enclosed by the 3200 dotted line is executed, and the part enclosed by the 3300 dotted line is the first time when both u and v are odd. This is because it is executed.

  In odd sign inversion processing, carry propagation does not occur. In the sign inversion process, all the bits are inverted and +1 is performed. However, when all the odd-numbered bits are inverted, the least significant bit is always 0. Therefore, no carry occurs even when +1 is performed.

  FIG. 7 shows an embodiment of the Montgomery inverse element calculation apparatus that realizes the processing of the portion 3300 in FIG. 3 by using the sign inversion method in FIG. At 7030, the most significant bit is inverted, and the result is subjected to xor with bits other than the least significant bit of v by the exclusive logic circuit of 7040. The intention of this circuit is that when the value of v is negative, the value of v is sent as it is to the adder 7060 and the sum with u is calculated to calculate (u−v), and the value of v is non-negative. In this case, since the output of 7030 is 1, bits other than the least significant bit of v are inverted by the exclusive logic circuit of 7040. (U−v) is calculated by inverting the sign of v of a non-negative value, sending it as −v to the adder 7060, and calculating the sum with u. The calculation result of (uv) is arithmetically shifted to the right by 1 bit by the arithmetic right shifter 7080, and (uv) / 2 is stored in w.

  FIG. 8 shows a case where a Montgomery inverse element having a bit length n = 5 is obtained for b = 17 using a Montgomery inverse element operation method according to the prior art shown in FIGS. Intermediate results are shown. 8010 in FIG. 8 corresponds to the reference numerals in FIGS. The final result is stored in r,

が得られる。

Is obtained.

  FIG. 9 is an embodiment of the present invention, and when the Montgomery inverse of bit length n = 5 is obtained for b = 17 using a = 23 as the modulo by the processing flow of FIGS. 3 and 2. Intermediate result. Compared to FIG. 8 of the Montgomery inverse calculation according to the prior art, the same intermediate result and final result are obtained except that the value of v becomes negative.

10 and 11 show the flow of the embodiment of the present invention. A difference from the first embodiment is that s = −1 is substituted for s = 0 as an initial value in 10020.
As a result, when the flow of FIG.
k> n and finally

を得るためには、図１１に示される改良版モンゴメリ型逆元補正処理を行う。図１１に示される改良版モンゴメリ逆元補正処理は、図２の従来技術によるモンゴメリ逆元補正処理とは、最後に結果の符合を反転するための２０８０の処理がない点が異なる。

Is obtained, the improved Montgomery-type inverse element correction process shown in FIG. 11 is performed. The improved Montgomery inverse element correction process shown in FIG. 11 differs from the Montgomery inverse element correction process according to the prior art of FIG. 2 in that there is no 2080 process for inverting the sign of the result.

  FIG. 12 shows an intermediate result when a Montgomery inverse element having a bit length n = 5 is obtained for b = 17 with a = 23 modulo according to the flow of FIGS. 10 and 11. The final result is obtained without the processing corresponding to 2080.

  A feature of the embodiments of FIGS. 10 and 11 is that the multiple precision integer operation only requires an adder. Therefore, when implementing multiple-precision arithmetic in software, since there is only one type of operation, it is possible to perform the operation in the same routine. For example, the attacker can specify the address of the code of the program currently used for the operation from leak information. Even if they can be distinguished, there is no leakage due to the type of operation. Even when hardware is implemented, the scale of the hardware is reduced because the arithmetic unit for multiple precision integers is only an adder.

  FIGS. 13A to 13C show an embodiment of the prior art, which is an embodiment in which the processing flow of FIG. 1 is made into a circuit. According to the flow 1030, the following processing is performed while v is greater than zero. First, in FIG. 13A, if the least significant bit of u is 0, the selector 13040 selects the value of u, the selector 13070 is set to select the output of the selector 13040, and the right shifter 13080 sets 1 The value converted to / 2 is stored in the u storage unit 13020 through the selector 13130. As shown in FIG. 13C, the value of s is selected by the selector 13150, and the left shifter 13160 is selected. Through the selector 13120 and stored in the s storage unit 13230.

  In FIG. 13A, when the least significant bit of v is 0, selector 13040 selects the value of v and selector 13070 is set to select the output of selector 13040. The value converted into is stored in the v storage means 13010 through the selector 13130. As shown in FIG. 13C, the value of r is selected as the value of s by the selector 13150 and passes through the left shifter 13160. And stored in the r storage means 13220 through the selector 13110. In FIG. 13A, when the least significant bits of u and v are both 1, they are compared by the comparison circuit 13030. When u> v, the selector 13050 selects u and the selector 13060 selects v. The subtraction circuit 13170 calculates uv, and the selector 13070 selects the output of the subtraction circuit 13170, so that the right shifter 13080 outputs (u−v) / 2, and the selector 13130 outputs u storage means. 13020 side is selected, the value of u in u storage means 13020 is updated, r + s is calculated by adder 13140 and doubled by left shifter 13160 as shown in FIG. After updating the value of r in the r storage means 13220, the selector 13150 selects the value of s, and the value is changed by the left shifter 13160. Is multiplied, via a selector 13120, the value of s for s storage means 13,230 is updated.

  In FIG. 13A, when u ≦ v, the selector 13050 selects v, the selector 13060 selects u, the subtraction circuit 13170 calculates v−u, and the selector 13070 outputs the output of the subtraction circuit 13170. By selecting, the right shifter 13080 outputs (v−u) / 2, the selector 13130 selects the output as the v storage means 13010 side, the value of v in the v storage means 13010 is updated, and FIG. As shown in FIG. 6, after the adder 13140 calculates r + s and doubles it by the left shifter 13160, the selector 13150 updates the value of s in the s storage unit 13230 through the selector 13120, and then the selector 13150 selects the value of r. The value is doubled by the left shifter 13160, and the value of 13220s of the r storage means is updated through the selector 13110. Thereafter, as shown in FIG. 13B, 1 is added to the value of k stored in the k storage unit 13090 by the adder 13100 and the result is stored in the k storage unit 13090.

  FIG. 14 shows an IC card 14010 on which an IC card chip 14020 having a built-in Montgomery inverse operation device according to the present invention is mounted.

  FIG. 15 is an example of a system block diagram 15010 of the IC card chip shown in FIG. This system block includes a CPU 15020, a ROM 15030, a RAM 15040, and an EEPROM 15050 as storage means, a remainder multiplication coprocessor 15060, and a serial communication circuit 15070.

The figure which shows the Montgomery type | mold inverse element calculation procedure by a prior art. The figure which shows the correction | amendment process procedure used by the Montgomery type | mold inverse element calculation by a prior art. The figure which shows one Example of the Montgomery type | mold inverse element calculation procedure of this invention. The Montgomery type inverse element calculation circuit diagram by a prior art. The figure which shows one Example of the Montgomery type | mold inverse element calculation circuit of this invention. Explanatory drawing of a sign inversion system. The figure which shows one Example of the Montgomery type | mold inverse element calculation circuit of this invention. Transition diagram of internal variables of Montgomery type inverse element calculation according to the prior art. The transition figure of the internal variable of the Montgomery type inverse element calculation of this invention. The figure which shows one Example of the Montgomery type | mold inverse element calculation procedure of this invention. The figure which shows one Example of the Montgomery type | mold inverse element calculation procedure of this invention. The transition figure of the internal variable of the Montgomery type inverse element calculation of this invention. The u, v calculation circuit diagram of the Montgomery type inverse element calculation circuit by a prior art. The k calculation circuit diagram of the Montgomery type inverse element calculation circuit by a prior art. The r, s calculation circuit diagram of the Montgomery type inverse element calculation circuit by a prior art. The figure which shows IC card. The system block diagram of the chip | tip for IC cards.

Explanation of symbols

1010 ... Montgomery inverse operation processing start point,
1020 ... Internal variable initialization processing,
1030 ... end determination processing,
1040 ... even judgment of u,
1050 ... Update processing of u and s when u is an even number,
1060 ... even judgment of v,
1070 ... Update processing of v and r when v is an even number,
1080: Judgment of magnitude of u and v,
1090 ... Update processing of u, r, s when u> v,
1100 ... Update processing of v, s, r when u ≦ v,
1110 ... 2 power update,
1120 ... Inverse element existence determination,
1130: Error end point,
1140: Determination of necessity of overflow correction,
1150: Overflow correction processing,
1160: Processing end point,
2010 ... Montgomery inverse correction start point,
2020 ... Loop counter initialization,
2030 ... Loop end determination,
2040 ... odd number judgment,
2050: Correction processing from odd number to even number,
2060: processing to divide the result by 2;
2070 ... Loop counter update,
2080 ... sign inversion processing,
2090 ... processing end point,
3010 ... Improved Montgomery inverse processing start point,
3020 ... Internal variable initialization processing,
3030: Inverse element calculation determination process,
3040 ... Even judgment of u,
3050 ... Update processing of u and s when u is an even number,
3060 ... even judgment of v,
3070 ... Update processing of v and r when v is an even number,
3080 ... v code determination,
3090 ... calculation processing of w when v is non-negative,
3100 ... calculation processing of w when v is negative,
3110 ... w code determination processing,
3120 ... Update processing of u, r, s when w is a positive value,
3130... Updating process of v, r, s when w is zero or negative value,
3140 ... 2 power update,
3150 ... Inverse element existence determination,
3160: Error end point 3170: Necessity determination of overflow correction,
3180 ... overflow correction processing,
3190: Processing end point,
4010 ... v storage means,
4020 ... u storage means,
4030 ... Subtraction operation circuit with carry flag output,
4040 ... Carry flag signal,
4050, 4060 ... selector,
4070: Subtraction operation circuit,
4080 ... Right shifter 4090 ... Selector,
5010 ... v storage means,
5020 ... u storage means,
5030 ... Most significant bit,
5040: Arithmetic operation circuit,
5050 ... Zero flag signal,
5060: Arithmetic right shifter,
5080 ... OR circuit,
5090 ... selection signal,
5100 ... selector,
6010 ... Original data,
6020 ... the least significant bit,
6030: All bit inverted data,
6040 ... the least significant bit,
6050 ... sign inversion data,
6060 ... least significant bit,
7010 ... v storage means,
7020 ... u storage means,
7030: Inverter,
7040: exclusive OR,
7050 ... Least significant bit 7060 ... Adder,
7070: Zero flag signal,
7080: Arithmetic right shifter,
7090 ... w storage means,
7100: most significant bit,
7110... OR circuit,
7120 ... selection signal,
7130 ... selector,
8010 ... execution step position,
9010 ... execution step position,
10010 ... Improved Montgomery inverse processing start point,
10020 ... Internal variable initialization processing,
10030 ... Inverse element calculation determination process,
10040 ... Even judgment of u,
10050 ... Update processing of u and s when u is an even number,
10060 ... even judgment of v,
10070 ... Update processing of v and r when v is an even number,
10080 ... v code determination,
10090 ... calculation processing of w when v is non-negative,
10100 ... Calculation processing of w when v is negative,
10110 ... w code determination processing,
10120 ... Update processing of u, r, s when w is a positive value,
10130... Updating process of v, r, s when w is zero or negative value,
10140 ... 2 power update,
10150 ... Inverse element existence determination,
10160: Error end point,
10170 ... negative number correction processing,
10180: Determination of end of negative number correction process,
10190 ... Processing end point,
11010 ... Montgomery inverse correction correction start point,
11020 ... Loop counter initialization,
11030 ... Loop end determination,
11040 ... odd number judgment,
11050 ... Correction processing from odd number to even number,
11060 ... processing to divide the result by 2;
11070 ... Loop counter update,
11090 ... processing end point,
12010 ... execution step position,
13010 ... v storage means,
13020 ... u storage means,
13030 ... Size comparison means,
13040, 13050, 13060, 13070 ... selector,
13080 ... Right shifter,
13090 ... k storage means,
13100 ... adder,
13110, 13120, 13130, 13150 ... selector,
13140 ... Adder,
13160 ... Left shifter,
13170 ... subtractor,
13220 ... r storage means,
13230 ... s storage means,
14010 ... IC card,
14020, 15010 ... IC card chip,
15020 ... CPU,
15030 ... ROM,
15040 ... RAM,
15050 ... EEPROM,
15060 ... residue multiplication coprocessor,
15070: Serial communication circuit.

Claims (12)

A first integer a;
A second integer b which is relatively prime with the first integer a;
An integer n satisfying a <2 ⁿ modulo the first integer a,
When the inverse element of the second integer b is an integer b- ¹ ,
In a semiconductor device including a Montgomery-type inverse element arithmetic unit that calculates a third integer r that is r≡b ⁻¹ · 2 ⁿ mod a,
5 storage units u, v, r, s, w for storing integer values of n bits length,
Having two storage units k and i that can express values from 0 to 2n and store at least {log ₂ (n)} + 1-bit integer values;
Step (1) The initial state of the stored values in the storage units u, v, r, s, and k is
U = a, v = b, r = 0, s = 1, and k = 0,
Step (2) If v is 0, the process of Step (8) is performed,
If v is a value other than 0, the process of step (3) is performed.
Step (3) If the value of u is an even number, an operation of u = u / 2 and s = 2s is performed,
Proceed to step (7)
If the value of u is not an even number, the process of step (4) is performed.
Step (4) If the value of v is an even number, the calculation of v = v / 2 and r = 2r is performed, and the step
Proceed to step (7),
If the value of v is not an even number, the process of step (5) is performed.
Step (5) If the sign of v is non-negative, after calculating w = (u−v) / 2, the step
(6)
If the sign of v is negative, the operation of w = (u + v) / 2 is performed and then the step is performed.
(6)
Step (6) If the sign of w is negative or zero,
After calculating v = w, r = r + s, and r = 2r, step (7)
Proceed to processing
When the sign of w is positive, the calculation of u = w, r = r + s, r = 2r is performed.
Then, proceed to step (7).
Step (7) Set k = k + 1, and proceed to Step (2).
Step (8) It is determined whether u is 1 and if u is other than 1, there is no inverse element
To complete the process
If u is other than 1, proceed to step (9).
Step (9) It is determined whether r> a. If r> a, r = r−a,
Proceed to step (10),
If r ≦ a, the process proceeds to step (10).
Step (10) Set i = 0 and perform the process of Step (11).
Step (11) It is determined whether i <k−1. If i <k−1, step (1)
4)
If i <k−1, the process of step (12) is performed.
Step (12) If r is an odd number, set r = r + a and perform the process of Step (13).
If r is an even number, the process of step (13) is performed.
Step (13) r is shifted right and the result is set to r, i = i + 1, and step (1
Perform the process of 1)
Step (14) r = a−r, r is the execution result, and the process is terminated.
An inverse element calculation unit that executes the processes of steps (1) to (9) above;
A semiconductor device comprising a Montgomery-type inverse element arithmetic unit having an inverse element correction unit that executes the processes of steps (10) to (14). Having a sign inverting unit for inverting the sign;
In step (5), instead of the arithmetic processing for setting w = (u−v) / 2, after calculating v ′ = − v by the sign inversion unit, the arithmetic processing for w = (u + v ′) / 2 is performed. The semiconductor device according to claim 1, further comprising a Montgomery-type inverse element arithmetic unit that executes.   3. The semiconductor device according to claim 2, wherein the sign inversion unit includes a Montgomery-type inverse element arithmetic unit that performs sign inversion by inverting all bits other than the least significant bit of v. An adder and a subtractor, and in step (5),
determining the sign of v using the most significant bit of v, and selecting one of the addition unit and the subtraction unit according to the result of the determination;
If the sign of v is non-negative, after calculating w = (u−v) / 2, the process proceeds to step (6).
The Montgomery-type inverse element arithmetic unit that performs the processing of step (6) after performing the operation of w = (u + v) / 2 when the sign of v is negative. Semiconductor device. A first integer a;
A second integer b which is relatively prime with the first integer a;
An integer n satisfying a <2 ⁿ modulo the first integer a,
When the inverse element of the second integer b is an integer b- ¹ ,
In a semiconductor device including a Montgomery-type inverse element arithmetic unit that calculates a third integer r that is r≡b ⁻¹ · 2 ⁿ mod a,
5 storage units u, v, r, s, w for storing integer values of n bits length,
Having two storage units k and i that can express values from 0 to 2n and store at least {log ₂ (n)} + 1-bit integer values;

Step (1) The initial state of the stored values in the storage units u, v, r, s, and k is
Respectively, u = a, v = b, r = 0, s = −1, and k = 0.
Step (2) If v is 0, the process of Step (8) is performed,
If v is a value other than 0, the process of step (3) is performed.
Step (3) If the value of u is an even number, after calculating u = u / 2 and s = 2s,
Proceed to step (7).
If the value of u is not an even number, the process of step (4) is performed.
Step (4) If the value of v is an even number, after calculating v = v / 2 and r = 2r,
Proceed to step (7).
If the value of v is not an even number, the process of step (5) is performed.
Step (5) If the sign of v is non-negative, after calculating w = (u−v) / 2,
Perform step (6),
If the sign of v is negative, after performing the operation w = (u + v) / 2,
Step (6) is processed.
Step (6) If the sign of w is negative or zero,
After calculating v = w, r = r + s, r = 2r, step
Proceed to processing (7)
When the sign of w is positive, the calculation of u = w, r = r + s, r = 2r was performed.
Later, proceed to step (7).
Step (7) Set k to k + 1 and proceed to step (2).
Step (8) It is determined whether u is 1 and if u is other than 1, there is no inverse element
To complete the process
If u is other than 1, proceed to step (9).
Step (9) Set r = r + a and proceed to step (10).
Step (10) It is determined whether r <0. If r <0, the process of step (9)
Go to
If r ≧ 0, the process proceeds to step (11).
Step (11) Set i = 0, perform the process of Step (11),
Step (12) It is determined whether i <k−1. If i <k−1, step (1)
3)
If i <k−1, the process of step (15) is performed.
Step (13) If r is an odd number, set r = r + a and perform the process of Step (14).
If r is an even number, the process of step (14) is performed.
Step (14) After calculating r = r / 2 and i = i + 1, the process of step (12) is performed.
Do the
Step (15) terminates the process using r as an execution result,
An inverse element calculation unit for executing the processes of steps (1) to (10) above;
A semiconductor device comprising a Montgomery-type inverse element arithmetic unit having an inverse element correction unit that executes the processes of steps (11) to (15).   In step (5), the arithmetic processing having an odd integer sign inverting unit and w = (u−v) / 2 is performed by inverting the sign of v (−v) and adding u. 6. The semiconductor device according to claim 5, further comprising a Montgomery-type inverse element arithmetic unit that performs arithmetic processing of w = (u + (− v)) / 2 by performing an arithmetic right 1-bit shift later. A multi-precision precision adder and a NOT operator that inverts all bits,
The step (1) includes a Montgomery-type inverse element arithmetic unit that performs an arithmetic process of v = a + NOT (b) +1 instead of an arithmetic process of v = (ab). 5. The semiconductor device according to 5. A first integer a;
A second integer b which is relatively prime with the first integer a;
An integer n satisfying a <2 ⁿ modulo the first integer a,
When the inverse element of the second integer b is an integer b- ¹ ,
In a semiconductor device including a Montgomery-type inverse element arithmetic unit that calculates a third integer r that is r≡b ⁻¹ · 2 ⁿ mod a,
A u register in which a is set as an initial state;
V register in which b is set as an initial state;
An r register set to 0 as an initial state;
An s register in which 1 is set as an initial state;
K register set to 0 as an initial state;
a bit shifter that executes a specified one of u right shift, s left shift, v right shift, and r left shift;
a process of subtracting the contents of the v register from the u register, a process of adding the contents of the v register to the u register, a process of adding the contents of the s register to the r register, a process of adding 1 to the k register, a process of adding a to the r register, and an arithmetic unit that executes a specified process of adding 1 to i;
Whether the sign of the most significant bit of v is positive, whether v is 0, whether v is even, whether u is even, whether v is positive, whether u is 1, whether r is A determinator that determines whether positive, r is even, and i is greater than (k−1);
A semiconductor device comprising a Montgomery-type inverse element arithmetic unit having a control unit that controls the bit shifter, the arithmetic unit, and the determination unit. A first integer a;
A second integer b which is relatively prime with the first integer a;
An integer n satisfying a <2 ⁿ modulo the first integer a,
When the inverse element of the second integer b is an integer b- ¹ ,
In a semiconductor device including a Montgomery-type inverse element arithmetic unit that calculates a third integer r that is r≡b ⁻¹ · 2 ⁿ mod a,
A Montgomery inverse operation unit that inputs the integers b and k and the modulus a to obtain the inverse element X = b ⁻¹ · 2 ^k mod a;
A Montgomery inverse correction unit for calculating a division result r = b ⁻¹ · 2 ⁿ mod a by inputting the obtained inverse X and modulus a;
The Montgomery inverse operation unit includes a u register that stores a as an initial state,
A v register that stores b as an initial state;
a w register for storing the operation results of u and v;
and at least a determination unit that determines whether u and v are odd numbers,
As a result of the determination by the determination unit, the u register and the v register that store u and v determined to be odd numbers;
The sign of the most significant bit of the v register is determined, the result of the determination and the u and v are input, and if the result of the determination is positive, the operation of u + v is executed, and the result of the determination is In the negative case, an arithmetic operation unit that performs an operation of uv,
A shifter for shifting the output from the arithmetic operation unit to the right;
A w register for storing a calculation result from the shifter;
A semiconductor device having a Montgomery-type inverse operation unit including a selector that performs a determination process of storing the value in a u register when w is negative and storing the value in a v register when w is nonnegative. An exclusive logic circuit that inverts the most significant bit of v with respect to the value of the v register and performs an XOR operation with bits other than the least significant bit of v,
The semiconductor device according to claim 9, further comprising a Montgomery-type inverse element operation device that inputs an output of the exclusive logic circuit to the arithmetic operation unit.   An IC card on which the semiconductor device according to claim 1 or 5 is mounted.   An IC card on which the semiconductor device according to claim 8 is mounted.

Images