JPH08147266A - Method and device for calculating power remainder - Google Patents

Abstract

PURPOSE: To provide the method and device for enabling the arithmetic of a power remainder due to a redundant binary arithmetic method even when the most significant bit of a normal is not '1'. CONSTITUTION: When a normal N is inputted, the leading position of a bit '1' in the normal N is detected by a first octet leading '1' detecting part 8, that position is shifted to high order by a bit shift amount deciding part 9 and a bit shift part 11 for input and stored in a normal N register 21 so that the most significant bit can be '1' and when outputting a remainder R, the remainder R stored in a remainder R register 24 is shifted to low order just for the same number of bits as the input time of the normal N and outputted by the bit shift amount deciding part 9 and a bit shift part 16 for output.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and apparatus for performing a high-order modular exponentiation operation with a large number of digits at high speed by utilizing a redundant binary operation method.

[0002]

2. Description of the Related Art A power-residue calculation can be executed by repeating multiplication and residue calculation. However, when performing multiplication and residue calculation with a large number of digits at high speed, the problem of carry propagation delay for carry / borrow carry becomes remarkable. become. Therefore, conventionally, various calculation methods have been proposed which are designed to prevent carry propagation. One of them is a redundant binary calculation method (for example, IEEE JOURNAL OF SOLID-STATE CIRCUITS, Vol.25). ,
No.3, June, 1990, A.Vandemeulebroecke, E.Vanzieleg
hem, T. Denayer and PGAJespers “A New Carry-Free
Division Algorithm and its Application to a Singl
e-Chip 1024-b RSA Processor ”).

[0003]

However, this redundancy 2
In the base operation method, there is a constraint that the most significant bit of the modulus must always be "1" when performing division or remainder calculation, and as a result, the number of bits of the modulus is limited.

It is an object of the present invention to provide a method and apparatus for enabling a power-residue operation by a redundant binary operation method even if the most significant bit of the modulus is not "1".

[0005]

In the present invention, in order to achieve the above object, a number A consisting of a modulus N and a natural number equal to or less than the modulus N is used.
, And a power exponent B, and a modulo exponentiation operation R = A ^B mod using the redundant binary operation method in which the modulus N is limited to d bits.
In a power-and-residue calculation method and apparatus for performing N and outputting at least the remainder R of the calculation result, the data of the modulus N is fetched into the input front stage data storage means for every m bits from the higher order, and the data of the modulus N is calculated by Whether or not a bit is input is measured by the data count means, and it is detected at which bit from the beginning of the data first fetched in the input front stage data storage means, "1" first appears, and the detected number of bits is determined. Determined as a bit shift amount, sequentially transferring the data in the input front stage data storage means to the input rear stage data storage means,
The data in the input front stage data storage means is the lower m bits, the data in the input rear stage data storage means is the upper m bits, and the 2 m bits are shifted to the upper side by the bit shift amount, and 2 m bits after the shift. Storing the upper m bits of the data of m in the m-bit shift data storage means,
After the completion of the data input of the law N, the value of the data counting means and m
The difference from the capacity / m of the bit shift data storage means is stored in the shift amount storage means as a shift amount, and the data of the m bit shift data storage means is shifted upward by the value of the shift amount storage means in units of m bits to obtain the modulus. The data of the number A is stored in the storage means, and the data of the number A is fetched into the input front-stage data storage means every m bits, and the number of m bits of the data of the number A is input is measured by the data count means to obtain the input front-stage data. The data in the storage means is sequentially transferred to the input rear stage data storage means, the data in the input front stage data storage means is the lower m bits, the data in the input rear stage data storage means is the upper m bits, and the 2 m bits are Shifting to the upper part by the bit shift amount, and storing the upper m bits of the shifted 2m-bit data in the m-bit shift data storage means, After the data input of A is completed, the data of the m-bit shift data storage means is shifted upward by the value of the shift amount storage means in units of m bits and stored in the number storage means, and the data of the power exponent B is stored in the power exponent storage means. The number of bits of the data of the power exponent B is directly fetched and stored, measured and stored by the data counting means, and the stored binary data of the modulus N, the number A, and the power exponent B is used for the redundant binary. The arithmetic means is caused to perform a power-residue operation, the remainder R of the operation result is stored in the remainder storage means, and the data of the remainder R is fetched from the remainder storage means into the output preceding stage data storage means for every m bits from the higher order and output. The data in the front stage data storage means is sequentially transferred to the output rear stage data storage means, and the data in the output front stage data storage means is set to the lower m bits, and the data in the output rear stage data storage means is set to the upper m bits. As bets, and outputs shifted to lower its 2m bits only the bit shift amount.

[0006]

In the arithmetic unit using the conventional redundant binary arithmetic method, the most significant bit of the modulus is limited to "1". for that reason,
The number of modal bits is also uniquely limited. On the other hand, according to the modular exponentiation operation method and apparatus of the present invention, it has means for arbitrarily shifting and inputting the modulus, and by using this, the most significant bit is always "1" when storing the modulus. Can be. Therefore, it is possible to execute a power-residue operation with any bit length as long as it is equal to or less than the bit length of the modulus register, and to perform a power-residue operation using a redundant binary number without limiting the bit length in the modulus. Will be able to.

[0007]

DESCRIPTION OF THE PREFERRED EMBODIMENTS By adding a parameter input / output correction unit of the present invention to a redundant binary arithmetic unit which has been conventionally used for four arithmetic operations having a large number of bits and requiring high-speed processing, a bit length equal to or smaller than a modulus register can be obtained. If so, it is possible to perform a modular exponentiation operation with no limit on the bit length of the modulus.

First, it is shown that the modular exponentiation operation with a modulo arbitrary bit length can be executed by combining multiplication and remainder calculation.

The power-residue calculation R = A ^B mod N is such that k ≧ i ≧ 1 when k-bit power exponent B data is input.
Using, and ^{_{B = b k × 2 k-}} 1 + b k-1 × 2 k-2 + ...... + b i × 2 i-1 + ...... + b 2 × 2 1 + b 1 × 2 0, Can be obtained by That is, the power-residue calculation can be obtained by repeating multiplication and remainder calculation.

As described above, the bit length of the modulus N must be equal to the bit length of the redundant binary arithmetic unit in order to execute this arithmetic processing by the redundant binary arithmetic method. When the length is shorter than the bit length of the redundant binary arithmetic unit, j is determined so that N · 2 ^j is equal to the bit length of the redundant binary arithmetic unit, By executing, the target operation of R = A ^B mod N can be executed.

[0011] performs an operation of A ^B mod N as羃乗remainder operation, describes an example of outputting the remainder R of the calculation result. This example can be divided into the following phases: (1) Input of three parameters required for operation to parameter register (2) Parameter conversion for inputting each parameter to redundant binary operation unit (3) Power-residue operation in redundant binary operation unit (4 ) Output of Calculation Result Hereinafter, each phase will be described.

FIG. 1 shows an embodiment of the present invention, in which 1 is a parameter input / output correction unit, 2 is a parameter register unit, 3 is a parameter conversion unit, 4 is an improved redundant binary arithmetic unit,
Reference numeral 5 is a state transition control unit.

FIG. 2 shows the details of the parameter input / output correction unit 1 and the parameter register unit 2. Here, an example is shown in which data input / output is performed by an 8-bit data bus.

The counter section 6 counts up the input 8-bit data. The input front stage buffer unit 7 has 8
This is a register that stores bit data. The first "1" octet detecting unit 8 detects which bit from the beginning of 8-bit data has "1". The bit shift amount determination unit 9 determines the bit shift amount from the value of the first octet head “1” detection unit 8. Input post-stage buffer unit 1
0 is a register that stores 8-bit data.

The input bit shift unit 11 is a barrel register having a 16-bit input and an upper 8-bit output, and the shift amount is determined by the bit shift amount determining unit 9. The byte shift unit 12 is a register capable of arbitrarily shifting 8-bit data to the higher order in 1-byte units. The byte shift amount storage unit 13 stores the byte shift amount when the modulus N and the number A are input.

The output front-stage buffer section 14 is a register for accumulating 8-bit data. The output post-stage buffer unit 15 is a register that stores 8-bit data. The output bit shift unit 16 is a barrel register with 16-bit input and upper 8-bit output, and the shift amount is determined by the bit shift amount determination unit 9.

The modulus N register 21 is a register for storing the modulus N. The number A register 22 is a register for storing the number A. The power index B register 23 is a register for storing the power index B. The remainder R register 24 is a register for storing the remainder R of the calculation result.

FIG. 3 shows details of the parameter conversion unit 3 and the improved redundant binary arithmetic unit 4.

Redundant binary representation modulo N register 31 is redundant 2
This is a register for storing the modulo N of the decimal notation. The redundant binary representation number A register 32 is a register for storing the redundant binary representation number A. The redundant binary representation remainder R register 33 is a register for storing the redundant binary representation remainder R. The initialization circuit 34 initializes the remainder R register 24. The register 35 stores the bit length of the power index B. The register 36 stores the modulo N bit length (n).

The improved redundant binary operation unit 4 is an improvement of the parameter input of the redundant binary operation circuit which has been conventionally used. The redundant binary number multiplication unit 41 executes multiplication by the redundant binary number. The redundant binary number division unit 42 executes division by the redundant binary number. Redundant binary multiplication parameter input unit 43
Is input to the redundant binary number multiplication unit 41 by using the remainder R or the number A of the redundant binary representation as a multiplier. The multiplicand register 44 uses the remainder R of the redundant binary representation as the multiplicand to generate the redundant binary number multiplication unit 4
Enter 1. The dividend register 45 inputs the modulus N of the redundant binary representation as the dividend to the redundant binary number division unit 42. The redundant binary number intermediate calculation result register 46 stores the intermediate calculation result in the redundant binary representation. The intermediate calculation result register 47 stores the intermediate calculation result in a normal binary number.

FIG. 4 shows an overall operation flowchart of the present embodiment, and FIG. 5 shows a detailed operation flowchart at the time of modular exponentiation calculation. The operation will be described below according to these.

(1) Input of Three Parameters Required for Calculation into Parameter Register First, input of parameters is started before the calculation (S1).
Here, the state transition control unit 5 instructs the initialization of the counter unit 6 that counts the number of input bytes. The state transition control unit 5 determines whether the input parameter is the input of the modulus N or the power index B (S2).
And the instruction content differs depending on whether it is law N or not (S3),
Initially assume that a mod N input is made. Also, after that,
The state transition control unit 5 instructs the counter unit 6 to count up until the input of parameters is completed.

If the state transition control unit 5 is a mod N input,
The initialization of the bit shift amount determination unit 9 is instructed (S4).
When the number A or the power exponent B is input, the bit shift amount determination unit 9 maintains the same state.

The state transition control unit 5 inputs the first 1 input to the input front stage buffer unit 7 via the 8-bit data bus.
Byte data only 1st octet “1” detection unit 8
, And the first octet head “1” detection unit 8 detects which bit from the head of the fetched 8-bit data is the first “1”. At this time, the detected value (0 to 7) is used in the bit shift amount determination unit 9, and in the bit shift amount determination unit 9, the value from the first octet head “1” detection unit 8 is “0”. If the bit shift amount is "0", if "1", the bit shift amount is "1",
Is determined (S5).

The 1-byte data stored in the input front-stage buffer section 7 is transferred to the input rear-stage buffer section 10 before the next 1-byte data is input. The state transition control unit 5 gives an instruction to input the data of the second and subsequent bytes after the transfer is completed. If there is the next data, the second octet is input to the input front stage buffer unit 7.

When 2 bytes of data in the input rear stage buffer unit 10 and the input front stage buffer unit 7 are prepared, the 8 bits of the input rear stage buffer unit 10 are set to the upper 8 bits (first octet), and the input front stage buffer unit is set. A total of 16 bits of data in which 8 bits of 7 are lower 8 bits (second octet) are transferred to the input bit shift unit 11. The input bit shift unit 11 outputs the data shifted upward by the bit shift amount determined by the bit shift amount determination unit 9.

The output is input from the LSB side of the byte shift unit 12. Then, only the upper 8 bits of the output of the input bit shift unit 11 are input to the byte shift unit 12. As a result, even if the input first octet is a decimal number "1 to 255", the value input to the byte shift unit 12 is a decimal number "128 to 25".
5 ", and the first bit is always" 1 ".

From the third octet onward, the byte shift unit 12 is passed through the counter unit 6, the input front stage buffer unit 7, the input rear stage buffer unit 10, the input bit shift unit 11 so as to follow the second octet. Entered in. Or later,
This operation is continued until all data is input, and the state transition control unit 5 detects the end of input of the last data.

In the case of data input of modulo N, the first octet input to the byte shift unit 12 is shifted by one byte so that the first octet is moved to the uppermost position, and the correction shift of the parameter is made by supplementing "0" in the vacant place. Is performed (S8). In this way, the parameter length is measured (S6), and the state transition control unit 5 stores the parameter length (S7). This parameter length is stored in the byte shift amount storage unit 13.

At the time of data input of modulus N, modulus N register 21
When data of the number A is input, parameters are stored in the number A register 22 (S9). Since the number A may be input after the modal N is input, the process returns to step S2 when the number A is further input, and ends otherwise (S10).

The parameters of the number A are inputted after the parameters of the modulus N are inputted, and the process is almost the same as that of the case of the modulus N. The only difference from the case of the modulus N is the method of determining the bit shift amount in the input bit shift unit 11 and the byte shift amount in the byte shift unit 12, and the bit shift amount in the case of the number A is the modulus N. The value determined in that case is used as it is. Therefore, the first "1" octet detection unit 8
Does not work. After inputting the data of the number A, the input bit shift unit 11 bit-shifts by the value of the bit shift amount determination unit 9 (S11), and the byte shift unit 12 performs the bit shift by the value of the byte shift amount storage unit 13. The correction shift is performed (S8).

With respect to the input of the power index B, it is not necessary to shift and input such as the modulus N and the number A, and therefore, the output of the counter unit 6 directly stores the parameters in the power index B register 23 (S9). ). Input of the three parameters is completed as described above.

(2) Parameter conversion for inputting parameters to the redundant binary operation unit The redundant binary operation is different from the binary representation normally used.
Two bits represent normal one bit data. Therefore,
It is necessary to convert the normal binary representation to the redundant binary representation.
The parameters stored in the modulus N register 21 and the number A register 22 are converted into redundant binary representations and stored in the redundant binary representation modulo N register 31 and the redundant binary representation number A register 32.

(3) Powered Residue Calculation in Redundant Binary Operation Unit The multiplicand register 44 of the redundant binary multiplication unit 41 is always input with the data of the redundant R-residue R register 33.
The data of the modulo N register 31 in the redundant binary representation is always input to the dividend register 45 of the redundant binary divider 42. The multiplication result of the redundant binary multiplication unit 41 is always input as the divisor of the redundant binary division unit 42.

When the calculation is started (S121), first,
The remainder R register 24 and the remainder R register 33 in the redundant binary representation are initialized to "1" by the initialization circuit 34 (R
= 1, i = k) (S122).

The data of the remainder R register 33 in the redundant binary representation is input to the redundant binary multiplication parameter input unit 43 of the redundant binary multiplication unit 41. After the input, multiplication and division are performed in the redundant binary multiplication unit 41 and the redundant binary division unit 42 (S
123), the intermediate result is output to the redundant binary operation intermediate result register 46.

This operation (R _{i + 1} = {R _i · (R _i ·
2 ^j )} mod (N · 2 ^j ): where j = value of byte shift amount storage unit 13 + value of bit shift amount determination unit 9) is output to the redundant binary number arithmetic intermediate result register 46, The result returned to the binary representation of is the mid-operation result register 4
7 is output. This value becomes the data of the next remainder R register 24. The data in the remainder R register 24 is redundant 2 again
Converted to a binary representation, the redundant binary representation of the remainder R register 33
Stored in.

Looking at the first bit of the data in the power index B register 23, if it is not "1" (b _i = 1) (S12
4) Skip this work.

The data of the number A register 32 in the redundant binary representation is input to the redundant binary number multiplication parameter input unit 43, and the multiplication / multiplication
Division is performed (S125), and the calculation (R _{i + 1} = {A ·
The result of (R _i · 2 ^j )} mod (N · 2 ^j )) is output to the redundant binary number intermediate processing result register 46, and the result returned to the normal binary number representation is output to the intermediate processing result register 47. .

The value of the leading bit of the data in the power index B register 23 is discarded, and the next bit is set as the leading bit. At the same time, the value of the power index B bit length register 35 is 0 (i = 0).
Otherwise, decrement by 1 (i = i-1) and return to. i = 0
If so, this phase ends (S126, S12).
7, S128).

(4) Output of calculation result The value of the remainder R register 24 is the calculation result obtained. However, since this value is multiplied by 2j, reverse correction is performed as follows when outputting parameters.

According to an instruction from the state transition control unit 5, the first octet of the operation result in the remainder R register 24 is fetched into the output front stage buffer unit 14. Next, the first octet captured in the output front stage buffer unit 14 is transferred to the output rear stage buffer unit 15, and the second octet is captured in the output front stage buffer unit 14.

The 8 bits of the output rear-stage buffer section 15 are the upper 8 bits (first octet), and the 8 bits of the output front-stage buffer section 14 are the lower 8 bits (second octet).
The total 16-bit data is shifted to the lower order by the output bit shift unit 16 according to the value from the bit shift amount determination unit 9 determined when the modulus N is input. Then, only the upper 8 bits of the output of the output bit shift unit 16 are output as 8-bit data. As for the number of octets of data to be output, the value of the counter unit 6 when the modulus N is input is decreased and output until it becomes 0 (S13 to S17).

The parameter outputs of modulo N and number A other than the calculation result are exactly the same as the case of the output from the remainder R register 24. Further, since the power of the power index B is not bit-shifted or byte-shifted, it is directly output from the power index register 23.

[0045]

As described above, according to the present invention, while utilizing the advantage of the redundant binary arithmetic method, that is, the multiple-speed high-speed arithmetic operation, the disadvantage is the highest method of the modular exponentiation operation. It is possible to solve the constraint that the bits are limited to “1”, that is, the bit length is limited to a fixed value.

[Brief description of drawings]

FIG. 1 is a configuration diagram showing an embodiment of the present invention.

FIG. 2 is a configuration diagram showing details of a parameter input / output correction unit and a parameter register unit.

FIG. 3 is a configuration diagram showing details of a parameter conversion unit and an improved redundant binary arithmetic unit.

[Fig. 4] Overall operation flowchart

FIG. 5 is a detailed operation flowchart at the time of modular exponentiation calculation.

[Explanation of symbols]

1 ... Parameter input / output correction unit, 2 ... Parameter register unit,
3 ... Parameter conversion unit, 4 ... Improved redundant binary operation unit, 5 ...
State transition control unit.

 ─────────────────────────────────────────────────── ─── Continuation of front page (72) Yoshiyoshi Yamanaka 1-1-6 Uchisaiwaicho, Chiyoda-ku, Tokyo Nihon Telegraph and Telephone Corporation (72) Inventor Shoichi Oyama 1-14-5 Kichijojihonmachi, Musashino-shi, Tokyo No. NTT Electronics Technology Co., Ltd.

Claims (6)

[Claims] 1. A number A consisting of a modulus N and a natural number less than or equal to the modulus N.
, And a power exponent B, and a modulo exponentiation operation R = A ^B mod using the redundant binary operation method in which the modulus N is limited to d bits.
In the power-of-residue calculation method of performing N and outputting at least the remainder R of the calculation result, the data of the modulus N is taken into the input front-stage data storage means for every m bits from the higher order and the number of m bits of the data of the modulus N is input. It is detected by the data count means, and it is detected at which bit from the beginning of the data first fetched in the input front data storage means, "1" first appears, and the detected number of bits is bit-shifted. The data in the input front stage data storage means is sequentially transferred to the input rear stage data storage means, and the data in the input front stage data storage means is set to the lower m bits and the data in the input rear stage data storage means is set. As the upper m bits, the 2m bits are shifted to the upper side by the bit shift amount, and the upper m bits of the 2m-bit data after the shift are m bits. Stored in Futodeta storage means, after data input completion law N, the value of the data counter means and m
The difference from the capacity / m of the bit shift data storage means is stored in the shift amount storage means as a shift amount, and the data of the m bit shift data storage means is shifted upward by the value of the shift amount storage means in units of m bits to obtain the modulus. The data of the number A is stored in the storage means, and the data of the number A is fetched into the input front stage data storage means for every m bits, and the number of m bits of the data of the number A is input is measured by the data counting means. The data in the storage means is sequentially transferred to the input rear stage data storage means, the data in the input front stage data storage means is the lower m bits, and the data in the input rear stage data storage means is the upper m bits. The bit shift amount is shifted upward, and the upper m bits of the shifted 2m-bit data are stored in the m-bit shift data storage means. After completion of inputting the data of the number A, the data of the m-bit shift data storage means is shifted to the upper part by the value of the shift amount storage means in units of m bits and stored in the number storage means, and the data of the power exponent B is stored as the power exponent. The number of bits of the data of the power of the exponent B is measured and stored by the data counting means, and the stored data of the modulus N, the number A, and the power of the power B are used for redundancy. The binary operation means is caused to perform a power-residue operation, the remainder R of the operation result is stored in the remainder storage means, and the data of the remainder R is fetched from the remainder storage means into the output front-stage data storage means for every m bits from the higher order, The data in the output front stage data storage means is sequentially transferred to the output rear stage data storage means, and the data in the output front stage data storage means is set to the lower m bits, and the data in the output rear stage data storage means is set. Position as m bits, 羃乗 remainder operation method and outputting shifted to lower its 2m bits only the bit shift amount. 2. The data of modulus N is fetched from the higher order by m bits into the output front stage data storage unit from the higher order storage unit, and the data in the output front stage data storage unit is sequentially transferred to the output rear stage data storage unit, The data in the output front stage data storage means is the lower m bits, and the data in the output rear stage data storage means is the upper m bits, and the 2 m bits are shifted to the lower side by the bit shift amount determined at the time of data input and output. The power-residue calculation method according to claim 1, wherein 3. A number A of data from the number storage means is taken into the output front stage data storage means every m bits from the higher order, and the data in the output front stage data storage means is sequentially transferred to the output rear stage data storage means, The data in the output front stage data storage means is set to the lower m bits, and the data in the output rear stage data storage means is set to the upper m bits, and 2 m bits thereof are shifted to the lower side by the bit shift amount determined at the time of the data input of the modulus N. The power-residue calculation method according to claim 1, wherein the power-residue calculation is performed. 4. The power of the power index B from the power index storage means is fetched into the output front stage data storage means every m bits from the higher order, and the data in the output front stage data storage means is sequentially transferred to the output rear stage data storage means. 2. The power-residue calculation method according to claim 1, wherein the data in the output front-stage data storage means is output as the lower m bits and the data in the output rear-stage data storage means is output as the upper m bits as they are. 5. A number A consisting of a modulus N and a natural number less than or equal to the modulus N.
, And a power exponent B, and a modulo exponentiation operation R = A ^B mod using the redundant binary operation method in which the modulus N is limited to d bits.
In a power-of-residue arithmetic unit that performs N and outputs at least the remainder R of the operation result, input pre-stage data storage means for taking in data of modulus N or number A for every m bits from the higher order, and data of modulus N or number A Data counting means for measuring how many m bits have been input and how many bits of power of the exponent B have been input, and at what bit from the beginning of the data of the modulus N that has been initially stored in the input front data storage means. First "1" bit detecting means for detecting whether "1" first appears, bit shift amount determining means for determining the number of bits detected by the first "1" bit detecting means as a bit shift amount, and input front stage Input rear stage data storage means for receiving the data in the data storage means next, and input rear stage data storage in which the data in the input front stage data storage means is the lower m bits Redundant binary using 2m-bit upper shift means that shifts the data in the stage to the upper m bits by the shift amount determined by the bit shift amount determining means, and data of modulus N, number A, and exponent B Redundant binary operation means for performing a power-residue operation according to the operation method, and 2m-bit data after being shifted by the 2m-bit higher-order shift means or a residue R obtained from the redundant binary operation means.
Alternatively, in addition to this, an m-bit shift data storage means for storing the upper m bits of the data of the modulus N or the number A or the power of the exponent B, and the value of the data count means and m
A shift amount storage means for storing a difference from the capacity / m of the bit shift data storage means as a shift amount, and a remainder R of an operation result from the m bit data shift storage means, or a modulus N or a number A or a power exponent B
Output front stage data storage means for fetching the data of the above from every m bits, output rear stage data storage means for receiving the data of the output front stage data storage means next, and data in the output front stage data storage means for the lower order m. 2 m-bit lower shift means for shifting only the remainder R, the modulus N, and the number A of the operation result to the lower bit by the bit shift amount determined by the bit shift amount determination means, with the data in the output rear stage data storage means as the upper m bits. And a modular exponentiation calculation device comprising: 6. A modulus N-redundant binary conversion means for converting a modulus N into a redundant binary representation, a number A-redundant binary conversion means for converting a number A into a redundant binary representation, and a remainder R to a redundant 2 Number A-redundant binary conversion means for converting into a binary representation, operation result storage means for storing the remainder R of the operation result, initialization means for initializing the content of the operation result storage means to "1", and k bits When the power of the power of B is input, k ≧ i ≧
Using i which is 1, B = b _k × 2 ^k-1 + b _k-1 × 2 ^k-2 + ... + b _i × 2 ^i-1 + ... + b ₂ × 2 ¹ + b ₁ × 2 ^0, and i = K, the remainder R and the modulus N of the operation result are made into a redundant binary representation, and the same number of bits as the number of bits stored in the modulus N is changed from the upper bits to R × 2 ^dk = (R × R × 2 ^dk ) mod
(N × 2 ^dk ), and if b _i = 1, R × 2 ^dk = (A × R × 2 ^dk ) mod (N ×
2 ^dk ), subtracting i by 1 and repeating the above calculation until it becomes 0. N × 2 ^dk bits redundant binary exponentiation remainder means, and full addition for returning redundant binary numbers to normal binary numbers 6. The modular exponentiation means according to claim 5, further comprising redundant binary arithmetic means including means and an arithmetic result output means for outputting as a modular exponentiation arithmetic operation result for obtaining a higher order dk of the arithmetic result storage means. Arithmetic unit.