JP3277220B2 - Operation method of remainder multiplication device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a calculation method of a remainder multiplication device which can perform processing using a small amount of memory.

[0002]

2. Description of the Related Art In a general-purpose computer or a system using a general-purpose microprocessor, A, B, N
Given, A and B are smaller than N, and A ×
Consider the case where the product of A and B, which is BmodN, is obtained modulo N. A, B, and N are written to the corresponding memories, and the intermediate progress C is also written to the corresponding memories. And
A, B, N, and C correspond to Ai, Bi, Ni,
N represented by Cj (0 ≦ i ≦ n−1, 0 ≦ j ≦ m−1)
Alternatively, it is divided into m blocks and expressed as follows.

(Equation 1) Next, it is assumed that each of Ai, Bi, Ni, and Cj is represented by an integer from 0 to r-1 using r as a radix. At this time, the next product C is calculated.

(Equation 2) Next, division is performed to obtain a result of the remainder multiplication in which C <N.

(Equation 3) Here, “x” is a symbol indicating the largest integer not exceeding x.

[0003]

As described above, A × B
When the product of A and B, modN, is obtained with respect to the modulus N, C in the middle of the calculation is also written into m blocks of the memory. In such a case, as the memory area of C,
Since up to 2n blocks are required for m blocks, IC
In a system using a card or the like, it is difficult to use the system because the memory area is limited. An object of the present invention is to solve such a conventional problem and to provide a calculation method of a remainder multiplication device capable of executing a calculation even when a memory area is limited.

[0004]

In order to achieve the above object, a method of calculating a remainder multiplication device according to the present invention comprises a memory area as a register corresponding to input variables A, B, N and work variables C, i; An arithmetic circuit for performing data write / read processing to the memory and addition / subtraction multiplication / division between the memories and comparison, and the input variables A and B are smaller than N;
When the product of A and B, which is A × BmodN, is obtained modulo N, A, B, and N are written in the corresponding memories, and the progresses C and i are also written in the corresponding memories. Ai, Bi, Ni, Cj (0 ≦ i ≦
n−1, 0 ≦ j ≦ m−1), divided into n to m blocks,

(Equation 1) And each of Ai, Bi, Ni, and Cj is represented by r as a radix.
Is represented by an integer from 0 to r−1, and r / 2 ≦ N _n−1
When m is n + 2, processing is performed in the following order between the arithmetic circuit and the corresponding memory area. That is, (1) C is initialized to 0 and i is n-
1 is stored, (2) C is multiplied by r, and C is updated with a value obtained by adding A × Bi to this value. (3) Upper digit r × C _{n + 1} + Cn of C
Is divided by a divisor obtained by adding 1 to the upper digit N _n-1 of N.
And r × Q × N is subtracted from C, and (4) the upper digit r of C
A quotient Q is obtained by dividing × C _{n + 1} + Cn by a divisor obtained by adding 1 to the upper digit N _n−1 of N, and subtracting r × Q × N from C, (5)
Significant digit r × Cn + C _n-1 is higher digit N _n-1 to a value to the divisor obtained by adding multiplied by r-1 one of N and C, i.e. (r-1) (N
_When the value is equal to or larger than ( _n-1 +1), (r-1) * N is subtracted from C, (1) is subtracted from (6) i, and when (7) i is positive or 0, the process returns to (2) above. (8) When C <N, the following (12)
And (9) subtracting Q × N from C by the quotient Q obtained by dividing the upper digit r × Cn + C _n−1 of C by the divisor obtained by adding 1 to the upper digit N _n−1 of N, and (10) C If <N, proceed to (12) below,
(11) N is subtracted from C, and the process returns to (10).
Is the result of the remainder multiplication of A × BmodN.

[0005]

In the present invention, starting from i = n-1,
The following equation is executed. C ← r × C + A × Bi (4) That is, the sum of the multiplication result of A × B and the multiplication result of r × C is Are stored in the area C as an intermediate result. Next, the following equation is calculated. C ← C−Q × N (5) That is, the remainder obtained by subtracting the product of the quotient Q and the modulus N from C is represented by C
Accumulates in the area. This calculation reduces the required memory area of C. Then, reduce i one by one, i
= N−2, n−3,..., 2, 1 are repeatedly executed in the above equations (4) and (5). At this time, the following equation (6) is divided.

(Equation 4) The use of the quotient Q in the above equation (6) is the most important feature of the present invention. Addition, subtraction, expressed by the above equations (4) and (5),
By multiplication, processing can be performed in order from the upper partial product of A × B, so that the number m of blocks of C can be reduced to about n.
Further, since the quotient Q of the above equation (6) is used, the relationship of the following equation (7) is established, and C processed in the above equation (5) does not have to be calculated even though the upper digits are approximated. And is always guaranteed to be positive. For this reason, the process for handling a negative value of C is not required, and the process is simpler than in the case where C / N is directly handled.

(Equation 5)

[0006]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 2 is a block diagram of a modular multiplication device to which the present invention is applied. 2, reference numeral 11 denotes an arithmetic circuit, 1
0 is a memory area. A, B,
C ₀ -C _{n + 1} , N _0-
There are areas of N _n−1 , A _{0 to} A _n−1 , B _{0 to} B _n−1 and i.
In addition to the arithmetic circuit 11, there is a control circuit for performing a series of processes, but the description is omitted. FIG. 1 is a processing flowchart of a modular multiplication apparatus according to an embodiment of the present invention. Although FIG. 1 illustrates the radix as r, for example, when 8 bits are one block, r = 256 = 2 = 8
It corresponds to the case of the power. (A) A, B, and N are given in advance (Step 10)
1). (B) Next, 0 is set in each block area of C, and n is set in the area of i.
-1 is accumulated (step 102). Perform operations in order from the top. (C) C is multiplied by r, and C is updated with a value obtained by adding A × Bi to C. (D) r × Q × N is subtracted from C by a quotient Q obtained by dividing the upper digit C _{n + 1} ‖Cn of C by a divisor obtained by adding 1 to the upper digit N _n−1 of N. Incidentally, it is _{C n + 1 ‖Cn = rC n} + 1 + Cn.
(E) r × Q × N is subtracted from C by a quotient Q obtained by dividing the upper digit C _{n + 1} ‖Cn of C by a divisor obtained by adding 1 to the upper digit N _n−1 of N (step 103).

[0007] (f) The upper digit Cn‖C _{value n-1} is multiplied by the high-order digit N _n-1 to r-1 to the divisor obtained by adding 1 N and C, i.e. (r-1) (N _{n- If} it is equal to or greater than ₁ + 1), (r-1) * N is subtracted from C (steps 104 and 105).
It should be noted that Cn _- 1Cn _-1 = r.times.Cn + Cn _-1 . (G) 1 is subtracted from i (step 106). That is, the operation proceeds to the calculation of the next digit. (H) When i is positive or 0, the process returns to step 103 (step 107), where C is multiplied by r, and C is updated with a value obtained by adding A × Bi to this. (I) When C <N, that is, when the value of C is smaller than the modulus N (step 108), the value of C is output as the result of the remainder multiplication (step 112). (Nu) Conversely, if C ≧ N, the upper digit Cn‖C _n−1 of C is set to N
Then, Q × N is subtracted from C by a quotient Q obtained by dividing the upper digit N _n−1 by 1 with a divisor (step 109). (L) When C <N (step 110), the value of C is output as the result of the remainder multiplication (step 112). (C) If C ≧ N, N is subtracted from C (step 111), and the process returns to step 110 to determine whether C <N again. (F) If C <N, C is output as the result of the modular multiplication of A × BmodN, and the processing is terminated (step 112). Thus, a series of remainder multiplication processes is completed.

Hereinafter, specific examples of the present invention will be described. 624
An example of × 623 mod 625 will be described. Radix r = 10 (1
0) is taken as an example. Incidentally, De - data _{structures, C = C 4 ‖C 3 ‖C} 2 ‖C 1 ‖C 0 N = N 2 ‖N 1 ‖N 0 = 6‖2‖5 A = A ₂ ‖A ₁ ‖A ₀ = 6‖2‖4 B = B ₂ ‖B ₁ ‖B ₀ = 6‖2‖3 Since there is no fear of misunderstanding because of the decimal system, the description of the delimiter ‖ is omitted below. (A)-of the above embodiment
The remainder multiplication is performed according to the procedure (f). (A) A, B, and N are given in advance (as described above). (B) Next, 0 is set in each block area of C, and n is set in the area of i.
Store -1. C = 00000, i = 2, Perform the operation in order from the top. (C) C is multiplied by r, and C is updated with a value obtained by adding A × Bi to C. C = 00000 + 624 × 6 = 03744 (d) r × Q × N is converted from C by a quotient Q obtained by dividing the upper digit C _{n + 1 of} C by the divisor obtained by adding 1 to the upper digit N _n−1 of N. Reduce. Incidentally, it is _{C n + 1 ‖Cn = rC n} + 1 + Cn. Q =
Since “03/7” = 0, C remains unchanged. (E) r × Q × N is subtracted from C by a quotient Q obtained by dividing the upper digit C _{n + 1} ‖Cn of C by a divisor obtained by adding 1 to the upper digit N _n−1 of N. Thereby, the remainder of the result of the division is obtained. Since Q = “03/7” = 0, C remains unchanged. (F) higher digit Cn‖C _n-1 indicates the high-order digits N _n-1 to a value to the divisor obtained by adding multiplied by r-1 one of N and C, i.e. (r-1)
When the value is equal to or more than the value of (N _n-1 +1), from C, (r-1)
× N is reduced. It should be noted that Cn _- 1Cn _-1 = r.times.Cn + Cn _-1 . From 37 <9 × 7, C remains as it is. (G) Subtract 1 from i. That is, the operation proceeds to the calculation of the next digit. i = 2-1 = 1 (h) When i is positive or 0, the process returns to (c).

(C) C is multiplied by r, and C is updated with a value obtained by adding A × Bi to C. C = 10 × 03744 + 624 × 2 = 38688 (d) Q = “38/7” = 5, C = 38688−5 × 10
× 625 = 074438 (e) Q = “07/7” = 1, C = 38688-1 × 10
× 625 = 01188 (f) From 11 <9 × 7, C remains unchanged. (G) i = 1-1 = 0 (h) Since i is 0, the process returns to (c). (C) C is multiplied by r, and C is updated with a value obtained by adding A × Bi to C. C = 10 × 01188 + 624 × 3 = 13752 (d) Q = “13/7” = 1, C = 13752-1 × 10
× 625 = 07752 Q = “07/7” = 1, C = 075502-1 × 10 × 62
5 = 01252 (e) From 12 <9 × 7, C remains as it is. (G) i = 0-1 = -1 (h) Since i is negative, go to (l). (I) Since C = 01252> N = 625, the value of C is larger than the modulus N, so go to (nu). (Nu) The upper digit Cn‖C _n-1 of C is set to ₁ as the upper digit N _n-1 of N.
Q × N is subtracted from C by a quotient Q divided by a divisor obtained by adding Q = “12/7” = 1, C = 01252-1 × 625 = 0
0627 (l) Since C = 00627> N = 625, go to (W). (W) subtract N from C. C = 00627-625 = 0
0002. Here, the process returns to (l). (R) From C = 00002 <N = 625, go to (F). (F) Output C as the result of the remainder multiplication of A × BmodN, and terminate. C = 00002 is output as a result. The above is a series of remainder multiplication processes.

As described above, in the present embodiment, it is possible to execute the remainder multiplication processing with a limited range of the memory area. For example, in the fields of encryption and authentication, there is a method in which the difficulty of factorization of a factor or the difficulty of a discrete logarithm problem is used as a basis for security. In such a method, a large modulo multiplication is indispensable from the viewpoint of ensuring security, but in an environment where the memory area is limited, its arithmetic processing becomes difficult. However, according to the present invention, the above problem can be solved because the remainder multiplication process can be performed using a limited range of memory area. Further, even when a sufficient memory area exists, the system can be configured by selectively using a small memory having a high access speed and a large number of memories having a low access speed from the viewpoint of securing economy. But there are benefits.

[0011]

As described above, according to the present invention,
Since the remainder multiplication can be performed in a limited range of memory area, the remainder multiplication can be performed even in a system having a limited memory area such as an IC card.

[0012]

[Brief description of the drawings]

FIG. 1 is a flowchart of a modular multiplication process according to an embodiment of the present invention.
It is a chart.

FIG. 2 is a block diagram of an arithmetic unit to which the present invention is applied.

[Explanation of symbols]

 Reference Signs List 10 memory area 11 arithmetic circuit A, B input variable N method variable C, i work variable r radix

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) G06F 7/52 310 G06F 7/72

Claims (1)

(57) [Claims] 1. An input variable A, B, N and a work variable C,
A memory area as a register corresponding to i and an arithmetic circuit for performing data write / read processing to the memory and addition / subtraction / multiplication / division between the memories and comparison are used, and input variables A and B are smaller than N, and A × A and B become BmodN
When the product of N is obtained modulo N, A, B, N are written in the corresponding memory, and the intermediate progresses C, i are also written in the corresponding memory, and A, B, N, C correspond to Ai, Ai, respectively. B
Divided into n to m blocks represented by i, Ni, Cj (0 ≦ i ≦ n−1, 0 ≦ j ≦ m−1), And each of Ai, Bi, Ni, and Cj is represented by r as a radix.
Is represented by an integer from 0 to r-1, and r / 2≤Nn-1
Wherein when m is n + 2, processing is performed in the following order between the arithmetic circuit and a memory area corresponding to the arithmetic circuit. (1) Initialize C to 0, accumulate n-1 in i, (2) Update C by a value obtained by multiplying C by r and adding A × Bi to this, and (3) Upper digit of C r × Cn + 1 + Cn is replaced by the upper digit Nn−1 of N
To obtain a quotient Q obtained by dividing by 1 and subtracting r × Q × N from C. (4) The upper digit r × Cn + 1 + Cn of C is converted to the upper digit Nn−1 of N
The quotient Q obtained by dividing by 1 to the divisor is obtained, and r × Q × N is subtracted from C. (5) The upper digit r × Cn + Cn−1 of C is the divisor obtained by adding 1 to the upper digit Nn−1 of N Multiplied by r−1, that is, (r−
1) When the value is equal to or larger than the value of (Nn-1 + 1), (r−
1) subtracting N, (6) subtracting 1 from i, (7) when i is positive or 0, return to (2) above , (8) when C <N, proceed to (12) below, (9) Q × N is subtracted from C by a quotient Q obtained by dividing the upper digit r × Cn + Cn−1 of C by a divisor obtained by adding 1 to the upper digit Nn−1 of N. (10) When C <N, Proceeding to (12) below, (11) N is subtracted from C, and the process returns to (10). (12) Let C be the result of the remainder multiplication of A × BmodN.