JPH03250314A - Arithmetic unit for multiplication remainder - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Summary] Regarding a modular multiplication calculation device that can reduce hardware and perform high-speed processing, the purpose of this invention is to reduce the scale of the hardware without sacrificing high speed. mod n) (n is Km bits, A
.

B<n) (m = 1.2...) is a multiplication remainder arithmetic device that performs the multiplication remainder, and is a high-order multiplication unit that divides Km bits of A and B into m pieces each bit (1 word). A multiplication circuit that sequentially multiplies words with B to obtain Km+K bit partial products m times, and K m obtained at the output of the multiplication circuit.
-i- Of the K-bit data, the bit data overflowing the Km bit is used as the search bit, and the value of the Km+K-bit data where the lower Km bits are all O's and the upper bit is the search bit is determined by the remainder method. A first method that obtains the intermediate result of a KmXK-bit multiplication remainder operation by adding the remainder table that outputs the remainder result that is the remainder after dividing by n, and the output Km bits of the remainder table and the lower Km bits of the partial product. an adder, a shift means for shifting the intermediate result by bits to higher order digits, a second adder for adding the shift result of the shift means and a partial product of bits to Km-1- for the next word; and a correction circuit that corrects the intermediate result obtained by the first adder to select a remainder, and the first adder adds the lower Krr+ bits of the output of the second adder and the output of the remainder table. By repeating m times the operation of bit-shifting the intermediate result obtained by using the shift means and adding it again to the partial product output from the multiplication circuit in the next cycle by the second adder, KmxK is obtained.
The system is configured to obtain intermediate results of m-bit remainder multiplication operations, and finally use a correction circuit to converge the results to less than the modulus n of the remainder, thereby performing the multiplication remainder operations at high speed.

[Industrial application field]

TECHNICAL FIELD The present invention relates to a modular multiplication arithmetic device that reduces hardware and is capable of high-speed processing.

Public key cryptography is known as a convenient encryption and authentication algorithm for communication data. In this public key encryption method, when encrypting communication data, the sender encrypts the message using a key that has been made public in advance by the other recipient, and the recipient only knows the public key, which is different from the public key. The received message is decrypted using a secret key. In this way, public-key cryptography differs from conventional cryptography in which the same key is managed between the sender and the receiver, and the receiver only has to manage one key that only the receiver knows and is secure. It is a high-quality encryption method. The R3A cryptosystem (R, L, Rivest, A, Shamir and
L.

Adleman), but in this method, the algorithm is based on operations that repeat multi-digit multiplication and remainder operations several hundred times. For this reason, it is necessary to perform remainder calculations at high speed, and a method using a remainder table is shown in FIG. 9.

In the same figure, in encryption, user A multiplies plaintext M e times using a multiplication remainder calculation device 91, and divides the resulting product by n to calculate the remainder C=M@(mad n), resulting in a ciphertext (C
), and in decryption, user B multiplies the ciphertext (C) d times using the multiplication remainder arithmetic unit 92, calculates the remainder M=Cd (mod n) by dividing the product by n, and obtains the decrypted text (M
). Here, user B's public key e1 user B
The relationship between the secret lid of
It is necessary to satisfy the relationship expressed by -1))).

The modular multiplication calculation device according to the present invention is particularly effectively applied to the above-mentioned public key cryptosystem.

[Conventional technology]

FIG. 10 shows an outline of the configuration of a conventional example using a remainder table. In this conventional example, in the case of calculating A X B (mod n), it is assumed that A, B, and n are each 512-bit positive integers, and that the basic unit is a 32 x 32-bit multiplier. . In FIG. 10, the conventional high-speed parallel multiplication remainder calculation device is composed of three parts: a multiplication processing section 101, a remainder processing section 102, and a subsequent stage processing section 103. In the multiplication processing unit 101, a 512 x 512 bit multiplier 104 is configured using a plurality of 32 x 32 bit multipliers, and A x B (512
The multiplication is performed by x 512t="cut", and the 1024-bit multiplication result is added to a.

The lower 512 bits of the 1024 bits of the multiplication result are directly sent to the 520-bit adder 10 in the remainder processing section 102.
5, and the upper 512 bits are sent to 1 every 32 bits.
Divided into 6 parts, 16 remainder table circuits 106-
1 to 106-16. Remainder table circuit 10
The configuration of each of 6-1 to 106-16 is shown in FIG.
This is shown in detail in Figure 2.

Each remainder table circuit 106-i includes 16 remainder table modules 111-1 to 1, as shown in FIG.
Each remainder table module has a remainder table containing contents obtained by dividing the 512 bits of the remainder result into 32-bit units.

In each remainder table module 111-j, as shown in FIG.
Each digit of each bit is the remainder table 121-1 to 121-8.
is entered in either. Each remainder table is filled with 4
The bit value is used as an address, and the remainder result, which is the remainder obtained by dividing the 32-bit value corresponding to that address by the modulus n of the remainder, is output. Eight remainder tables 121-1 to 121
The outputs of -8 are tournament-added by adders 122 to 128 and output as a total of 35 bits.

In this way, in the remainder processing unit 102, each remainder table module outputs 35 bits for 32 bits obtained by dividing the 512-bit input into 16 pieces.
Since each remainder table circuit 106-i outputs 560 bits, there is a difference of 48 bits between the number of input bits and the number of output bits. Therefore, there is an overlap of 3 bits between each output of the remainder table circuit. Also, since there are 16 remainder table circuits 106-1 to 106-16,
Considering the addition of these outputs, the outputs of the remainder table circuits 106-1 to 106-16 and the multiplication processing unit 101
A total of 520 bits are added to the lower 512 bits of the output of
A bit adder is required.

Returning to FIG. 10, the result of addition performed by the 520-bit adder 105 is sent to the subsequent processing circuit 103.

With the manual power of the post-processing circuit 103, A X B (+nod
Since the format is i) plus a multiple of n, processing is performed to keep this value within n. The upper 8 bits of this 520-bit addition result are entered into the remainder table 108, and the output 512 bits and 520 bits are added to the adder 10.
By adding the lower 512 bits of the output of 5 in adder 109, a 513-bit result is obtained.

This result is A X B (mod n), A X B (
mod n) + n, AX B (mocl n)
+2n, so adder 111.11
In step 2, the sign of the result of adding -n and -2n to the output of the adder 109 is checked in the judgment circuit 112, and by selecting the negative output, the value of A×B (mad n) can be determined by the selector. Select to obtain the modulus result, which is 512 bits x 512 bits divided by n.

[Problem to be solved by the invention]

As explained in the above prior art, in the conventional multiplication remainder calculation circuit, the multiplication processing unit 101 performs 512 bits x 512
After multiplying by 1024 bits and obtaining the result, the remainder is calculated by referring to the remainder table.
Although it is fast, the scale of the multiplier 104, adder 105, etc. is enormous, and the remainder table 108 must also have all 512 hits, so the circuit scale is large and the circuit scale is required to be small. In some cases, it is difficult to realize this, and when LSI is implemented, the chip division method and control become complicated.

The purpose of the present invention is to reduce the hardware scale and achieve high speed in a multiplication remainder arithmetic device based on the concept of obtaining the final multiplication remainder result after obtaining intermediate multiplication remainders of partial products using a remainder table. The purpose is to provide a structure that can be easily expanded according to processing needs.

[Means to solve the problem]

FIG. 1 is a block diagram of the principle of the present invention. The figure shows a multiplication remainder arithmetic device that performs the multiplication remainder of A×B (mod n) (A, B, n are Km bits) (m=1.2...). is Km bits A and B
A multiplication circuit that multiplies the divided bits of Krn+K bits to obtain a partial product of Krn+K bits, 2 is the Krn+K bit data obtained at the output of the multiplication circuit 1, and the Knn bits of data overflowing from the Knn bits. As the search bit, Km+
A remainder table that outputs a remainder result that is the remainder obtained by dividing the value of K bits of data in which the lower Km bits are all 0 and the upper bits are the search bits by the modulus n of the remainder, 3
is the output Km bits of remainder table 2 and the lower Km of the partial product.
A first adder which obtains an intermediate result of a KmXK-bit multiplication remainder operation by adding bits; 4 is a shift means for shifting the intermediate result to the upper bit digit; A second adder 6 which adds Km+K-bit partial products for the word , is a correction circuit which corrects the intermediate result obtained by the first adder 3 and selects a remainder. The intermediate result obtained by adding the output of the second adder 5 and the output of the remainder table 2 by the first adder 3 is bit-shifted by the shifting means 4, and then the intermediate result obtained by adding the output of the second adder 5 and the output of the remainder table 2 is bit-shifted by the second adder 5. By repeating the operation of adding to the partial product output from multiplier adder 1 m times in the cycle of Km
Obtain the intermediate result of the multiplication remainder operation of ×Km bits, and finally,
By using the correction circuit 3 to keep the result below the divisor n, the multiplication remainder calculation is performed at high speed.

A bit adder is added to the multiplier adder 1 to store the bit carry, and the configuration is configured to obtain the partial product of Km x K I (I = 1.2, 4゜8...m) bits,
One extended remainder table 4 is provided in the remainder table 2, in which the data of the upper KI bits of the partial product of KI bits are manually entered bit by bit as addresses, and the output of the extended remainder table is added to the output of the upper extended remainder table. KmxKI (
1=1.2, 4.8, . . . m) by performing m calculations, an expandable multiplication remainder arithmetic device is obtained.

[For production]

When performing multiplication, instead of performing all multiplications, find the partial product divided into m times from the top, and refer to the remainder table with the bits that exceed the bit width of the processing unit in the partial product.
The remainder of the partial product is calculated, this result is added to the partial product of the next stage, and the remainder of the addition of the partial products is determined using the overflowing bits of the addition result.

Further, by adding an adder to the partial product calculation circuit so that the partial product can be added to the partial product from the upper partial product calculation circuit, the width of the partial product can be expanded.

By using a method that calculates partial products and refers to the remainder table without performing multiplication all at once, it is only necessary to have a remainder table of a size corresponding to the number of overflowing bits, and nm
In the case of partial products of xn, the size of the remainder table can be reduced to 1/m compared to the conventional method. Also, in this case, the number of multipliers is also 1. /m is enough. When relatively high speed is not required or when small hardware is required, the scale of the multiplication circuit and remainder table can be reduced instead of increasing the number of calculations. Furthermore, by configuring the width of the partial product to be expandable, when high-speed use is desired, multiplication and reference to the remainder table can be performed at the same time, allowing expansion to suit various speeds.

〔Example〕

FIG. 2 is a block diagram showing the configuration of a modular multiplication calculation device according to an embodiment of the present invention. As shown in the figure, the apparatus according to the embodiment of the present invention includes a multiplication circuit 200, a remainder control circuit 2
10, a remainder table 220, and a subsequent processing section 230.

Here, assuming that the basic processing unit is 32 bits (1 word - 32 bits), the multiplier B can be expressed as follows.

B=B;sx 2"' +BI4X 2""10...
...10B, X 232+ Bo (1) Therefore, A×B (modn) is the partial product M1= A X B
It is expressed as follows using +.

A×B (modn) = (... ((MIs(mod
n)X2”)+M, 4) (modn)X2”-・+
Mo) (modn) (2) This device calculates the remainder of the partial product using the remainder table according to the above equation (2). However, when doing the remainder,
In the intermediate calculation, the residual result is not kept below n, but is kept below n in the final processing stage in the post-processing section 230.

The multiplication circuit 200 includes a register (RF-A) 201 that stores a 512-bit multiplicand, a register (RF-B) 202 that stores a 512-bit multiplier B, and a register (RF-B) 202 that stores a 512-bit multiplicand, and a register (RF-B) 202 that stores a 512-bit multiplicand. ． 、、、、
A15) and the multiplier B in 32-bit units (B
32-bit multiplier 203, 32-bit adder 204, and 32-bit register 20.
5, a 32-bit adder 206, a 32-bit register 207, and a 1-bit carry register 208.

First, B15 is input to one input of the multiplier, and A15. A14. ,,,, A
0 is input manually, and the value of B15 remains unchanged until AO is input.

The lower 32 bits of the 32-bit x 32-bit multiplication output from the multiplier 203 are input to the adder 204, and the upper 3
Two bits are input to adder 206.

The lower 32 bit adder 204 adds the lower 32 bits of the current multiplication output and the upper 32 bits of the previous multiplication output stored in the register 207, and stores the result in the register 205. In the first multiplication, register 207 is empty, so adder 204 simply passes the lower 32 bits.

The upper 32 bit adder 206 combines the 32 bits of the current multiplication output, the carry IJ-C generated in the previous addition stored in the register 208, and the carry port generated in the lower bit adder 204. The result is stored in the register 207. At this time, the carry generated by adder 206 is stored in register 208. As a result, the partial product of 8×B,5 is calculated.

As the output of the multiplication circuit 200, the registers 205 to 5
The 12-bit x 32-bit partial product A x B, 5 is first output, then A x Lt is output, and hereafter A x B
It is output sequentially up to o.

213 and 214, a remainder table 215 with a search bit width of 32 bits, an internal remainder table 216,
It is composed of a 32-bit shifter 217.

First, the partial product A x B, 5 is transferred from the multiplication circuit 200 to the adder 211 of the remainder control circuit 210 . The remainder control circuit stores the lower 512 bits of the partial product in a register file (RFI) 212 and transfers the 32 bits exceeding the 512 bits to the remainder table 215.

The detailed structure of the remainder table 215 is shown in FIG.

In FIG. 3, the remainder table 215 includes four remainder tables 31 to 34 and an adder 35 for tournament addition.
~37 bits, and the sent 32 bits are
In this embodiment, the unit of division is 8 bits, and the data is divided into four parts and input into the remainder tables 31 to 34 as addresses. Each of the four remainder tables 31 to 34 has the 8-bit address of each digit as the upper bit and the lower bit (5
12 bits, 520 bits, 528 bits, and 536 bits) are all 0, and a value of 512 bits is stored, which is the remainder modulo n. Examples of data stored in each remainder table and details of the storage format can be found in Chapter 6.
As will be described later in a specific example with reference to FIG. 7 and FIG. 7, the 512-bit remainder for each 8-bit upper address is divided into 16 32-bit units and stored.

The 32 bits sent to the remainder table are divided into four parts of 8 bits each and input into each of the remainder tables 31-34 as upper addresses. When the upper address is set, the 4-bit lower address specifying the digit of the remainder result is sequentially incremented and output starting from the lower word.

The remainder outputs from the four remainder tables are carried into carry-save adders 35, 36. and 37, and are sequentially output in units of 32 bits starting from the lower word as an output of a maximum of 514 bits.

A carry-saved adder is an adder that adds a carry due to an overflow of the added value of the lower bits to the added value of the upper bits. For example, 85E7 + B
When calculating BB3 = 1719A, first add the lower 8 bits to get ET + 83 = 19A, output 9A of the lower 8 bits as the first word, then add the upper 8 bits to get 85 + BB In this case, the overflowed 1 of the upper 4 bits of the calculated addition result of the lower 8 bits is also added to the light. and,
The lower 8 bits 71 of the obtained value 171 are output as the second word. The upper 4 bits of the value 171 become the output of the third word. In this way, the addition result 1719A is obtained.

In the above embodiment, the 32 input bits, which are the overflow portion of the output of the multiplication circuit 200, are divided into 4 parts every 8 bits and input into the remainder tables 31 to 34. It may be configured to do so. However, in this case, the memory capacity of the remainder table becomes enormous. Further, the 32 overflow bits may be divided into any number of bits, such as 2 bits, 4 bits, etc., as necessary. How many overflow bits are divided and manually stored in the remainder table is determined by the relationship between the memory capacity of the remainder table and the processing speed.

Returning to FIG. 2, in the remainder control circuit 210, the adder 214 adds the maximum 514 bits of output from the remainder table 215 and the lower 512 bits of the partial product from the adder 213 to obtain the intermediate remainder result of the partial product. get. Here, the reason why the result is called an intermediate remainder result is that the result is not within the modulus n of the remainder, but is the result of adding a positive multiple of n to the remainder result. While the intermediate remainder result is obtained by referring to the remainder table 215, the multiplication circuit 200 obtains the partial product A×B+4 of the next digit. Next, the adder 211 adds the partial product of A x B Ia and the intermediate remainder result of A x B + 5 shifted by 32 bits (actually, the timing of addition is delayed by one cycle). The result of addition is a maximum of 547 bits, resulting in a 35-bit error. For this reason, in addition to the 32-bit remainder table described above, a 3-bit internal remainder table 216 is provided.

The output of the 3-bit internal remainder table 216 is added to the lower 512 bits of the partial product in the adder 213 while the remainder table 215 performs tournament addition of the remainder table output to obtain a 513-bit result. This result and the output of the remainder table 215 are added by an adder 214, and AX
Obtain the remainder of (BISX232+B14). If this operation is repeated 16 times until the partial product of A x Bo
The 515-bit value as the intermediate remainder of ×B is sent to the adder 2.
14 (see equation (2) above).

The post-processing unit 230 processes the lower 511 output of the adder 214.
A register 231 that stores bits, a multiple table 232 that uses 4-bit input as an address, and 512 bits of output from the multiple table and the lower 51 bits from register 231.
an adder 233 that adds 1 bit;
The multiplication remainder result obtained from the output of 3 or the multiplication remainder result 1n
A register 234 stores the value of , an adder 235 adds -n to the output of the adder 233, a register 236 stores the output of the adder 235, and the output of the register 234 or the output of the register 236 is checked by a sign check. It is composed of a selector 237 that selects and outputs.

The multiple table 232 has the same configuration as the remainder table,
Of the 515 bits obtained as the output of the adder 214, the multiple number table 232 is referred to using a total of 4 bits, including the overflowing 3 bits and the most significant bit of the 512 bits. Adder 23
By adding the 512 bits of the multiple table output and the lower 511 bits of the output of the adder 214 in step 3, the value of the multiplication remainder result or the multiplication remainder result +n is obtained and stored in the register 234. In parallel with the storage, the adder 235 adds -n to this result and stores it in the register 236. Then, by checking the sign of the value stored in the registers 234 and 236 and drawing it from the registers 234 and 236, the multiplication remainder result is obtained.

In the above, at the end, 1 is added to the overflow bit as a multiple table.
The number of times the multiple table is retrieved by adding 4 bits is 2.
, and the result of the multiplication remainder is obtained in the same way.

As is clear from the above description of the present invention, according to the embodiment of the present invention, the multiplication circuit calculates partial products and calculates intermediate remainders by repeatedly referring to the remainder table for each partial product. , the final remainder is calculated in the subsequent processing section, so the circuit scale of the multipliers, adders, etc. in the multiplication circuit is significantly reduced compared to the conventional method.

If it is desired to further increase the processing speed of the embodiment shown in FIG. 2, the multiplication circuit and remainder control circuit shown in FIG. 2 may be arranged in parallel and expanded as shown in FIG.

When expanding circuits in parallel to increase speed, the basic processing unit can be 64 bits or 128 bits, which are multiples of 32 bits, depending on the number of parallel circuits.

256 bits, 512 bits, etc.

In the embodiment shown in FIG. 4, a plurality of multiplication circuits 200-1
．． 200-2.200-3.200-4 are arranged in parallel, and the configuration of each multiplier circuit for calculating partial products is as follows, except that a carry-save adder 209 is added to the output side of each multiplier circuit. Same as Figure 2. This circuit 209 is configured to be able to calculate nmxnk (k=1.2°4...16) partial products by adding it to the output of the upper partial product multiplier circuit. In this embodiment, the explanation will be made for the case of 4 parallel circuits.
In 00-4, the partial product of A×B+s is calculated, and in the next extended multiplication circuit 200-3, A×B14.200-2 te is A x B! 3, 2001, the partial products of A×BI2 are calculated, and by adding each partial product, A X (B+sX 296+BI4X 264+BI
3X 232+B,. ) is calculated as the partial product. In this case, the partial product is 512+128 bits, and the top 1 of this partial product is
28 bits overflow.

With the overflowing 128 bits, the remainder table 220 and expansion remainder table 2 are
20-1, in this case, the remainder table is also expanded and becomes a 128-bit extended remainder table 215-1 to 215-1.
5-4 and adders 216-1 to 216-4), the result of adding the output of each extended remainder table to the output of the upper extended remainder table, and the lower 5 of the output of the adder 209.
Performs addition with 12 bits. Even in the case of expansion, the second embodiment is the same as the first embodiment except that the width of the remainder table for overflow bits and the width of the multiple table that are drawn from the second time onward become wider because the number of remainder table outputs increases.

More specifically, the output from adder 209 is sequentially output in units of 32 bits, and the lower 512 bits are output from adder 2.
11 to the register 212, and the next overflow bit, 32 bits, is stored in the extended remainder table 215-
The next 32 overflow bits are sent to the extended remainder table 215-3, the next 32 bits are sent to the extended remainder table 215-2, and the next 32 bits are sent to the remainder table 215-1. Sent.

Each adder 216-4 to 216-. 1, the remainder result is added to the upper remainder result with a delay of one cycle. As a result, the output of the adder 216-1 is obtained by adding up all the same digits of the remainder table, and the adder 214 adds this to the lower 512 bits of the partial product.

Thereafter, the same operation as in the first embodiment described above is performed to obtain A×B (modn) as the output of the selector 237.

As described above, even when the multiplication circuit is expanded according to the second embodiment, the operation is the same as the first embodiment except that the width of the remainder table and the width of the multiple table become wider.

In addition, in the embodiment shown in FIG. 2, 16 cycles were required to obtain the partial products, but in this embodiment, the processing time is only 4 cycles, and the throughput is further improved.

FIG. 5 is a block diagram showing the basic configuration for explaining the modular multiplication operation according to the embodiment of the present invention using an actual numerical example, and the processing unit is not 32 bits as in the first embodiment. The structure is the same as that in FIGS. 2 and 3, except that it is in 8-bit units, and the reference numerals of the components are indicated by adding a to the numbers. This is the reference number and correspondence of the element. In addition, in FIG. 5, for the sake of simplicity, the register 231.2 is
34 and 236 are omitted.

Figures 6A to 6D are the remainder table (T
l> 31a, (T2) 32a, (T3)
33a, and (T4) Diagram showing the contents of 34a, No. 6I
3 is a diagram showing the contents of the internal table 216a, and FIG. 6F is a diagram showing the contents of the multiple table 232a.

In table T1 shown in FIG. 6A, the remainder data when the manual address is 00 is the remainder 0000 obtained by dividing 10-bit data with 00 as the upper 2 bits and lower 8 bits as all O's by n.

The remainder data when the input address is 01 is the remainder 32E9 obtained by dividing 10 bit data by n, with 01 as the upper two bits and the lower eight bits as all 0s.

The remainder data when the manual address is 10 is the remainder 65D2 obtained by dividing the 10-bit data with 10 as the upper 2 bits and the lower 8 bits as all O's by n.

The remainder data when the input address is 11 is the remainder 988B obtained by dividing 10 bits of data by n, with 11 as the upper 2 bits and the lower 8 bits as all O's.

In table T2 shown in FIG. 6B, the manual address uses the overflow bits, the third and fourth bits of the 8 bits, as the address, so the dividend is such that the upper 2 bits are the input address and the lower 10 bits are all 0s. is the value of

Hereinafter, in FIGS. 6C and 6D, the value of the dividend is such that the lower 12 bits and lower 14 bits are all 0, respectively.
The top two bits are the human address.

In the 66th E1 internal table, the remainder obtained by dividing a total of 19 bits, the upper 3 bits equal to the manual address and the lower 16 bits, all O's, by n is stored as shown.

In the multiple table of FIG. 6F, the remainder obtained by dividing a total of 11 bits, the upper 4 bits equal to the input address and the lower 7 bits, all O's, by n is stored as shown.

FIG. 7 is a diagram illustrating the actual table storage format for table T1. In the same figure, in table T1, the lower 8 of the residual data for a 2-bit address input are
The bit and the upper 8 bits are stored separately. In order to distinguish between the lower and upper parts of the residual data, a 1-bit word designation bit is provided at the lower end of the 2-bit address input, and the surplus data is read out in word units (8-bit units) using this word designation bit. For example, the remainder data corresponding to address 01 is 32E9, but in the storage format shown in FIG. 7, by setting the word designation bit to 0 when the address input is 01, the day of the lower 8 bits is first output, Next, by incrementing the word designation bit, 32 of the upper eight bits are read out.

FIG. 8 is a diagram showing an example of actual multiplication remainder calculation when the tables shown in FIGS. 6A to 6F are used in the multiplication remainder calculation device of FIG. 5. In the figure, numerical values are expressed in hexadecimal unless otherwise specified.

Multiplier A is A373, multiplicand B is B2H2, divisor n is CD
17, the multiplier A to explain the calculation of A X B (mod n) is A373. Multiplicand B is B2 6. A case will be described in which 8X B (mod n) is calculated with the divisor n being CD17.

Assuming that the lower 8 bits of multiplicand B are 81 and the upper 8 bits are 82, in this example B2=82. B1=86.

First, in the first partial product calculation, the multiplication circuit 200a
(D output output, A X B2 = (A873)
82 = 751FF6 (16 bits + 8 bits) is obtained. The upper 8 bits of this output, 75 (01110101 in binary notation), are overflow bits, and are manually input by dividing into four 2-pit bits into the four remainder tables 31a to 34a. As a result, the remainder table 31a contains the lower two
It can be seen from the table of FIG. 6A that bit 01 is input as the address and data 32E9 is output.

Similarly, in the remainder table 32a, address 01 is manually input,
Data CBA4 is output, address 11 is input to the remainder table 33a, data 8883 is output, address 01 is input to the remainder table 34a, and data B5E
7 is output. When these outputs are tournament-added, (B587+BBB3) + (CBA4+32
E9) = 27072 is obtained as the output of the adder 37a in Fig. 5, and when this and the lower 16 bits (IFF6) of the output of the multiplication circuit 200a are added by the adder 214a, 29010 is obtained as the first partial product. is obtained.

In the second partial product calculation, A
3) X B6 = 975752 (16 bits + 8
bit) is obtained at the output of the multiplier adder 200a, and 29 bits are obtained by shifting the first partial product by 8 bits.
01000, the output of the adder 211a becomes 32
77452 is obtained, and its upper 12 bits are 327 (
011001.00111 (in binary notation) is an overflow bit, and is input to the four remainder tables 31a to 34a by dividing it into four parts each consisting of two bits starting from the lower bit. The old 1s in the upper 3 bits of the overflow bits are stored in the internal table 216.
It is manually operated by a. As a result, 9 from the remainder table 31a
88B, remainder table 32a to CBA4, remainder table 33a to C17F, internal table 216a to 83
EE is output respectively. The output of the internal table 216a is 74 which is the lower 16 bits of the output of the adder 211a.
52 to obtain F940 at the output of the adder 213a. The outputs of the remainder tables 311-34a are tournament-added to obtain 225 DB as the output of the adder 37a. The output of the adder 213a and the output of the adder 37a are added by the adder 214a, resulting in 3181E. The upper 7 bits (0110001 in binary notation)
) and the upper 4 bits (0110) of the multiple table 23.
Subtract 2a to get 988B. This value is added to the lower 16 bits IE1ε of the output of the adder 214a, and the adder 2
B2O2 is obtained at the output of 33a. If you subtract n from this value, it becomes -E9C2, a negative number, so the value B without adding -n
Let 6D9 be the remainder result.

〔Effect of the invention〕

As is clear from the above description, in the modular multiplication arithmetic device according to the present invention, the circuit scale in the basic configuration is significantly reduced compared to the conventional one, and the basic configuration can be expanded if the processing speed is desired to be increased. This makes it possible to change the speed of the multiplication remainder. In other words, when high-speed processing is required, it is possible to increase the speed by adding a multiplication circuit unit and a remainder table, and the configuration of the multiplication remainder operation can be changed depending on the required speed and circuit size. Equipment can be provided.

The field of application of the modular multiplication calculation device according to the present invention is not limited to the public key cryptosystem described above.

[Brief explanation of drawings]

FIG. 1 is a block diagram of the principle of the present invention. FIG. 2 is a block diagram showing the configuration of a multiplication remainder arithmetic device according to an embodiment of the present invention. FIG. 3 is a block diagram showing the configuration of the remainder table circuit shown in FIG. FIG. 4 is a block diagram showing the configuration of a multiplication remainder calculation device according to another embodiment of the present invention. FIG. A block diagram showing the arithmetic unit; Figures 6A to 6F are diagrams showing the contents of each table in Figure 5; Figure 7 is a diagram showing the actual table storage format; Figure 8 explains actual numerical calculations. 9 is a principle diagram of public key cryptography which is the background of the present invention. FIG. 10 is a block diagram showing a configuration example of a conventional multiplication remainder calculation device. FIG. Block diagram showing an example of the configuration of a table circuit. FIG. 12 is a block diagram showing an example of the configuration of the conventional remainder table module shown in FIG. In the figure, 1... Multiplication circuit, 2... Remainder table, 3... First adder, 4... Shifting means, 5... Second adder.

Claims (1)

[Claims] 1, A×B (mod n) (n is Km bits, A, B<
n) (m=1, 2,...) multiplication remainder arithmetic device, which divides Km bits A and B into m pieces every K bits (1 word), from the upper word. Multiply with B in order to obtain K
A multiplication circuit (1) that obtains a partial product of m+K bits m times, and of the Km+K bit data obtained at the output of the multiplication circuit (1), the K bit data that exceeds the Km bit is used as a search bit, and the Km+K bit is searched. Lower Km of data
A remainder table (2) that outputs a remainder result that is the remainder obtained by dividing the value of the bit with all 0 bits and the upper K bits as the search bit by the modulus n of the remainder; and Km bits output from the remainder table (2). A first adder (3) that obtains an intermediate result of a Km×K bit multiplication remainder operation by adding the lower Km bits of the partial product; and a shifter that shifts the intermediate result by K bits to the upper digits. means (4); and a second adder (5) for adding the shifted result of said shifting means (4) and the partial product of Km+K bits for the next word.
), and a correction circuit (6) that corrects the intermediate result obtained by the first adder (3) and selects a remainder, and the lower Km bits of the output of the second adder (5). and the remainder table (2
) by the first adder (3), the intermediate result obtained by adding the output of By repeating the operation of adding m times to the partial product output from the multiplication circuit (1) in a cycle, an intermediate result of Km x Km bit multiplication remainder operation is obtained, and finally, using the correction circuit (3), A multiplication remainder calculation device that performs multiplication remainder calculations at high speed by keeping the result within the modulus n of the remainder. 2. The multiplier circuit (1) stores the K bit carry.
By adding a bit adder, Km×KI (I=1,2,4
, 8...m) bit partial products are obtained, and the remainder table (2 ), and by adding an adder for adding the output of the extended remainder table to the output of the upper extended remainder table,
An expandable multiplication remainder arithmetic device capable of performing the multiplication remainder of Km×KI (I=1, 2, 4, 8, . . . m) in I calculations.