JPH0786822B2 - Power residue arithmetic circuit - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a modular exponentiation arithmetic circuit, and more particularly to a modular exponentiation arithmetic circuit to be used in a public key cryptosystem.

(Prior Art) As is well known, various means for ensuring the security of information to be handled have been studied in data communication systems and computer systems, and one method is to encrypt information.

From the viewpoint of key management and usage, conventional encryption methods that use the same encryption key and decryption key and public methods that use a public encryption key and a secret decryption key There is a key encryption method. Public-key cryptography eliminates the drawbacks of conventional cryptography, and typical algorithms include
There is an RSA method proposed by Rivest, Shamir, Adleman and others.

The RSA cryptosystems have a relationship of 0 <M <n and 0 <e <n, and M ^e mod n = C (1) using integers M, e and n, which are represented by equal bit lengths. This is a method of performing a modular exponentiation operation to obtain a remainder C and encrypting it. It is said that the integers M, e and n each require 400 bits or more in binary in order to secure sufficient security. It

As a “power-residue arithmetic circuit” used in this RSA cryptosystem, for example, “high-order extended Bo
Exponentiation modular arithmetic LSI using oth algorithm ”(Proceedings of the Workshop on Cryptography and Information Security, 1987 7
Moon, pp.133-142) is known. This is provided with a residue table in view of the fact that the operation of the above formula (1) results in the repetition of the residue multiplication of a × b mod n (2), and the remainder in the part where the multiplicand exceeds the bit length of the divisor. The calculation is performed in the remainder table, the result is added to the value of the multiplicand that does not exceed the bit length of the divisor, the multiplication result is multiplied to obtain the product, and the operation is repeated as the next multiplicand. By doing so, the desired remainder C is to be obtained.

(Problems to be Solved by the Invention) However, the above-described conventional modular exponentiation operation circuit has a problem that the circuit configuration becomes large for the following reason.

First, the remainder calculation is performed using a remainder table composed of RAM, etc. This remainder table has a capacity that increases as the bit length of the product of the multiplication results of the remainder calculation becomes larger than the bit length of the divisor. Need to increase.

Further, it is conceivable that the bit length handled in the circuit will be up to about twice the bit length of the numerical value that is raised to the power by multiplication. As a result, the number of bit shift units and adders for multiplication increases.

The present invention has been made in view of such a problem, and an object thereof is to provide a modular exponentiation arithmetic circuit capable of reducing the circuit scale.

(Means for Solving the Problem) In order to achieve the above object, a power-residue arithmetic circuit of the present invention has the following configuration.

That is, the modular exponentiation operation circuit of the present invention has a relationship of 0 <M <n and 0 <e <n, and uses M ^e, n e and n, which are represented by equal bit lengths, respectively.
A power-residue calculation circuit that performs a power-residue calculation to obtain C = C; the power-residue calculation circuit initializes a numerical value M externally input in bit serial as a multiplicand and the subsequent calculation process. A multiplicand register in which either the remainder value or the cumulative remainder value generated in step 1 is stored as a multiplicand; a divisor register in which a numerical value n input from outside in bit serial is stored as a divisor; and an output of the multiplicand register A remainder calculator for dividing the output by the divisor register to obtain a remainder; an exponent register for storing a numerical value e input from the outside in bit serial as an exponent of a power; storing the numerical value M input from the outside in bit serial An input register that responds to each bit output from the most significant bit to the least significant bit of the exponent register in accordance with its logical state A multiplier selector that selectively outputs either the input register or the accumulated remainder value; a multiplier register that stores the output of the multiplier selector as a multiplier; each bit output from the least significant bit to the most significant bit of the multiplier register In response to the logical value "1", the remainder selector selects and outputs the output of the remainder operator, and when "0", the remainder selector selects and outputs a zero value input; A cumulative remainder calculator for obtaining a remainder by dividing the sum of the remainder values by the output of the divisor register; and a storage for storing the output of the cumulative remainder calculator and outputting it as the accumulated remainder value. A remainder register; outputs the remainder value output from the remainder operator to the multiplicand register, and outputs the accumulated remainder each time the operation of the most significant bit of the multiplier register is completed. A multiplicand selector for outputting to the multiplicand register; and an output register for outputting the accumulated remainder value when the operation of the least significant bit of the exponent register is finished to the outside as a final operation result value. It is characterized by.

A number register functioning as a buffer is arranged between the input register and the multiplier selector, and the numerical value M input in bit serial to the input register is set in the number register in bit parallel. You can

(Operation) Next, the operation of the modular exponentiation operation circuit of the present invention configured as described above will be described.

The operation of (M ^e mod n) shown in the above equation (1) is
Basically, it is to obtain (M ² mod n), that is, (M × M mod n). Therefore, when C, M, and n are positive integers represented by Q-bit binary numbers and n> M, C =
M × M mod n is obtained as follows.

If m _i is the number of the i-th (i is an integer of 0 or more) bit of M, 2 ⁱ M mod n = M _i to obtain the remainder M _i of the M × M partial product m _i × M. Although it is necessary to perform the operation of (3), this expression (3) can be expressed as 2M _i-1 mod n = M _i (4). Therefore, And the remainder C can be obtained. The present invention seeks to obtain a desired residue based on the sequential multiplication / division method shown in the equation (5), which is completely different from the sequential multiplication / division method studied in the conventional example.

In the remainder calculator, the output of the multiplicand register is divided by the output of the divisor register to obtain the remainder, and the remainder is set in the multiplicand register via the multiplicand selector, and the remainder is similarly obtained.
In the calculation loop that repeats this, the calculation of the above formula (3) is executed.

Then, the remainder value output one by one from this operation loop to the remainder selector is taken as a product (m _i × 2 ⁱ M mod n) with the corresponding bit (the above m _i ) of the multiplier register in the remainder selector, and this is accumulated. The sum of the previous accumulated remainder value S _i-1 stored in the arithmetic remainder register is divided by the output of the divisor register in the accumulation remainder calculator, and the result of this calculation is the current accumulation remainder. The value S _i is stored in the cumulative remainder register. That is, the cumulative remainder calculator executes the calculation of the following formula (6).

S _i = (S _i-1 +2 ⁱ m _i M mod n) mod n (6) The remainder calculation in the remainder calculator and the cumulative remainder calculator is performed by adding the two's complement of the divisor. .

First, the numerical value M stored in the input register is input to the multiplier register via the multiplier selector and set as the multiplier. Therefore, for all bits of the multiplier register, the equation (6)
When the calculation is performed, it indicates that the calculation of the equation (5) is completed, and the cumulative remainder value as the calculation result is set in the multiplicand register via the multiplicand selector. When the numerical value e set in the exponent register is the value 2, the operation result of M ² mod n is output from the output register. Generally, when the operation of the formula (1) is performed, the numerical value e The contents of the multiplier register are changed and operated according to the logical state of each bit of.

That is, in the exponentiation operation, the multiplier selector sequentially responds to each bit output from the most significant bit to the least significant bit of the exponent register, and when the logical value is “0”, it is stored in the cumulative remainder register. The accumulated remainder value S (which is set in the multiplicand register) is set in the multiplier register.
As a result, S × S mod n processing is executed. When the logical value is "1", the previous accumulated remainder value S is first set in the multiplier register to obtain S × S mod n, and then the numerical value M which is the contents of the input register is set in the multiplier register. Then, {(S × S mod n) × M} mod n is obtained. In the operation of this multiplier selector, in the bit array from the most significant bit to the lower bit of the numerical value e which is the exponent, when the logical value of the bit is “0”, the previous value may be simply squared. This is based on the characteristic that when the value is "1", the previous value is squared and M is multiplied.

As described above, according to the modular exponentiation arithmetic circuit of the present invention,
A desired remainder calculation can be performed without using the remainder table as in the conventional example. Further, the remainder calculation is performed by a simple addition process. The bit length handled inside the circuit is only L bits (L is an integer larger than 2) longer than the bit length of the divisor.
Therefore, the circuit scale can be significantly reduced as compared with the conventional circuit.

(Examples) Examples of the present invention will be described below with reference to the drawings.

FIG. 1 shows a modular exponentiation arithmetic circuit according to an embodiment of the present invention.

In the above formula (1), M, e, n and C are respectively positive integers represented by Q-bit binary numbers, and M <n from the definition of the RSA encryption method.

Numerical value M is initially set in the multiplicand register 1 and the input register 7. In addition, the divisor register 2 has a numerical value n
However, the numerical value e is supplied to the exponent register 6 from the outside and the numerical value is set.

Numerical values supplied from the outside are supplied in bit series in order to reduce the number of pins. In this embodiment, a register number 8 which functions as a buffer is provided between the input register 7 and the multiplier selector 9. That is, in the input register 7, the numerical value M input in bit serial is set in bit parallel and set in the numerical register so that the input register 7 can be prepared for the numerical value input required for a new operation.

First, the following processing is performed in the arithmetic unit including the multiplicand register 1, the divisor register 2, the remainder arithmetic unit 3, and the multiplicand selector 11. In the equation (3) and the equation (4), n
Note that> M, M mod n = M ₀ is M mod n = M ₀ = M. Further, 2M ₀ mod n = M ₁ is expressed as 2M mod n = M ₁ from M ₀ = M, and 2M <2n. Similarly, 2M _i-1 <2n. Therefore, it can be understood that performing mod n processing represented by equations (3) and (4) is equivalent to subtracting n from 2M _i-1 . At this time, if n can be subtracted from 2M _i-1, the answer is M _i, and if it cannot be subtracted, 2M _i-1 is directly used as M _i . The remainder calculator 3 performs this processing.

That is, the Q-bit multiplicand stored in the multiplicand register 1 is input to the remainder calculator 3. Further, the divisor n stored in the divisor register 2 is converted into a two's complement. Therefore, first, the addition of the numerical value M and the two's complement of the numerical value n is performed to obtain M mo
run dn

As a result, if the most significant bit is “1”, n can be subtracted from M, so M ₀ is the subtraction result. On the contrary, if the most significant bit is “0”, it means that the subtraction could not be performed, and M is the subtraction result. In this way, the remainder calculator 3 obtains the remainder value M ₀ or the same M and outputs it to the multiplicand register 1 via the remainder selector 11 in the form of shifting it by 1 bit to the left to set a new multiplicand. As a result, the operation of 2M mod n is continuously executed. After that, the same calculation is repeatedly executed. Thus to, in the formula (3), 2 ⁰ M~2 remainder value to ^Q-1 M is determined continuously, they remainder selector 12
Is output one by one.

The remainder selector 12 sequentially responds to each bit output from the least significant bit to the most significant bit of the multiplier register 10, and when the logical value is “1”, selectively outputs the output of the remainder arithmetic unit 3 and outputs “0”. In this case, 0 value input is selected and output. That is, the product (m _i × 2 ⁱ M mod n) of the remainder value output from the remainder calculator 3 and the corresponding bit (m _i ) of the multiplier register 10 is obtained, and this is the accumulated remainder calculator 4 To enter.

In the cumulative remainder calculator 4, this product (m _i × 2 ⁱ M mod n) and the previous cumulative remainder value S stored in the cumulative remainder register 5 are stored.
The sum of _i-1 and (S _i-1 +2 ⁱ m _i M mod n) is obtained, and the 2's complement of the numerical value n output from the divisor register 2 is added to the result, and the result is that the logical value of the most significant bit is If it is "1", the addition result is the cumulative remainder value S _i of this time, and the logical value of the most significant bit is "0".
Then, the sum is set as the cumulative remainder value S _i of this time. These are stored one by one in the cumulative remainder register. That is, the above formula (6)
Is performed for all the Q bits of the multiplier register 10, and the process of a.times.b mod n (Equation (2)) for one time is completed, whereby the multiplicand selector 11 is controlled. As a result, the accumulated remainder value S at the time of completion is the multiplicand selector 11
It is output to the multiplicand register 1 via the and also to the multiplier selector 9.

Next, the process of "exponentiation" is shown. The multiplier selector 9 responds to each bit output from the most significant bit (MSB) to the least significant bit (LSB) of the exponent register 6 in accordance with the logical state of the output of the number register 8 and the cumulative remainder register 5. Select one of the outputs and output it to the multiplier register 10.

Specifically, it is as follows. Now, considering that M is raised to the power of 733, However, if 733 is expressed in a binary number, then 733 = (1011011101) ₂ (8). Then, the following is found from the relationship of equation (7) and equation (8). That is, in the bit array from the most significant bit to the least significant bit, when the logical value of that bit is "0", the previous value is simply squared, and when the logical value is "1", the previous value is It can be understood that it suffices to square the value and calculate M. Therefore, the multiplier selector 9
When the logical value of the output bit of the exponent register 6 is “0”, the output of the cumulative remainder register 5 is selected. When the logical value of the output bit is “1”, the output of the cumulative remainder register 5 is selected first. Then, the output of the number register 8 is selected.
Although the most significant bit output of the exponent register 6 is always "1", there is no cumulative remainder value in the cumulative remainder register 5 in the first processing, and M × in the first processing. M mod
n. Therefore, in the first processing, the processing for the most significant bit is omitted and the output of the number register 8, that is, the numerical value M is set in the multiplier register 10.

Thus, in the exponentiation operation, the multiplier selector 9 sequentially responds to each bit output from the most significant bit to the least significant bit of the exponent register 6 and stores it in the cumulative remainder register 5 when its logical value is “0”. The previous accumulated remainder value S that has been set is set in the multiplier register 10. As a result, S × S mod n processing is executed. When the logical value is "1", first, the previous accumulated remainder value S is set in the multiplier register 10 and S × S mod
Then, n is obtained, and then the numerical value M which is the contents of the number register 8 is set in the multiplier register 10 to obtain {(S × S mod n) × M} mod n. Then, when the process for the least significant bit of the exponent register 6 is completed, the desired calculation result is output from the output register 13.

In the exponentiation operation for Q bits, the processing for the most significant bit can be omitted, so that it is sufficient to perform the processing for Q-1 bits.

When the logical value of the bit is "1", the processing of "square and multiply by M" is performed twice, so all bits are "1".
Is the maximum number of calculations. (Q-1) × 2 = 2
(Q-1) times. In addition, one modular exponentiation operation is Q
It consists of a remainder operation. Therefore, a maximum of 2 (Q-1) * Q = 2Q (Q-1) remainder operations are performed on one M consisting of Q bits. However, since all of them are addition processes, the number of bits handled by the arithmetic units, registers, etc. does not become so large. At most L than the bit length of the divisor
(L is an integer greater than 2) It is only bit longer, and the circuit scale does not increase unlike the conventional example circuit.
It is possible to reduce the size.

(Effects of the Invention) As described above, according to the modular exponentiation arithmetic circuit of the present invention, the characteristic that the RSA encryption method is used, that is, the value to be exponentiated is smaller than the divisor, The remainder of the partial product corresponding to each bit of is calculated and output by simple addition in the remainder calculator, and also in the cumulative remainder calculator, the remainder output from the remainder calculator is sequentially added to obtain the accumulated value. Since the processing for obtaining the remainder of is performed, the desired remainder calculation can be performed without using the remainder table as in the conventional example. Since the remainder calculation is performed by a simple addition process, the bit length handled inside the circuit need only be L bits (L is an integer greater than 2) longer than the bit length of the divisor. Therefore, there is an effect that the circuit scale can be significantly reduced as compared with the conventional example circuit, and the device in which the present circuit is mounted can be downsized.

[Brief description of drawings]

FIG. 1 is a configuration block diagram of a modular exponentiation arithmetic circuit according to an embodiment of the present invention. 1 ... Multiplicand register, 2 ... Divisor register, 3 ... Remainder calculator, 4 ... Accumulation remainder calculator, 5 ... Accumulation remainder register, 6 ... Exponent register, 7 ... Input register, 8 ...
… Numeric register, 9 …… Multiplier selector, 10 …… Multiplier register, 11 …… Multiplicand selector, 12 …… Remainder selector, 13
...... Output register.

Claims (2)

[Claims] 1. An integer M and an e which have a relation of 0 <M <n and 0 <e <n and are represented by equal bit lengths.
And a power-residue arithmetic circuit that obtains a remainder C by performing a power-residue calculation such that M ^e mod n = C; the power-residue arithmetic circuit uses a numerical value M input from outside in bit serial as a multiplicand. A multiplicand register that is initialized and stores either a remainder value or an accumulated remainder value generated in the subsequent arithmetic process as a multiplicand; a divisor that stores a numerical value n input from outside in bit serial as a divisor A register; and a remainder calculator for dividing the output of the multiplicand register by the output of the divisor register to obtain a remainder;
An exponent register for storing the numerical value e input from the outside in bit serial as an exponent of an exponent; An input register for storing the numerical value M input from the outside in bit serial; the most significant bit to the least significant bit of the exponent register A multiplier selector that sequentially responds to each bit output up to and outputs either the input register or the accumulated remainder value according to its logical state; a multiplier register that stores the output of the multiplier selector as a multiplier; In response to each bit output from the least significant bit to the most significant bit of the multiplier register, when the logical value is "1", the output of the remainder arithmetic unit is selectively output, and when it is "0", the zero value input is performed. A remainder selector that selectively outputs the output of the remainder selector and the accumulated remainder value are divided by the output of the divisor register to obtain a remainder. An accumulator residue register for storing the output of the accumulative residue calculator and outputting it as the accumulated residue value; and outputting the residue value output from the residue calculator to the multiplicand register. A multiplicand selector that outputs the accumulated remainder value to the multiplicand register each time the operation on the most significant bit of the multiplier register is completed; and the accumulation when the operation on the least significant bit of the exponent register is completed. A modular exponentiation arithmetic circuit, comprising: an output register for outputting a remainder value as a final operation result value to the outside; 2. A number register functioning as a buffer is arranged between the input register and the multiplier selector, and the numerical value M input in bit serial to the input register is bit parallel to the number register. The modular exponentiation arithmetic circuit according to claim 1, which is set.