Cryptosystem

• US 4,514,592 A
• Filed: 07/14/1982
• Issued: 04/30/1985
• Est. Priority Date: 07/27/1981
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Miyaguchi, Shoji
• Primary Examiner(s): Cangialosi, Sal
• Application Number:
  US06/398,016
• Time in Patent Office: 1,021 Days
• Field of Search: 178/22.11, 178/22.14
• US Class Current: 380/30
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

A cryptosystem for the RSA cryptography which calculates C≡M^e mod n and, for this calculation, performs an operation C=M₁ ×M₂ mod n. An operation ##EQU1## is performed in the order j=l, l-1, . . . 1 to obtain last R₁ as the result of the calculation M₁ ×M₂ mod n. The calculation ##EQU2## is performed in a quotient calculating unit, and the calculation M₁ ×M₂,j '"'"'+2.sup.λ R_j+1 -Q_j ·n is performed in a main adding unit. Where, variable R_j may be divided into two parts R_j,0 and R_j,1. In this way, the multiplication and the division are simultaneously conducted, thereby to raise the calculation speed.

Claims

1. An encryptosystem in which integers M, e and n (0≦

M<

n) are applied to M-, e- and n-registers;

variables C and M₂ are stored in C- and M₂ -registers;

the integer e being represented by ##EQU86## (e_i =1 or

     0);

the variable C is initially set to 1;

repetitive calculations are performed in accordance with the following Steps (1) and (2) for each value i in the order i=k, k-1, k-2, . . . 1, 0;

in Step (1) an operation C≡

M₁ ×

M₂ mod n is performed with M₁ =C and M₂ =C;

in Step (2) the value of e_i is checked and if e_i =1, the operation C=M₁ ×

M₂ mod n is further performed with M₁ =C and M₂ =M; and

said repetitive calculations are completed with i=0, producing the last C in the form of C≡

M^e mod n;

wherein a quotient calculating unit, a main adding unit and a controller are provided for performing the operation C≡

M₁ ×

M₂ mod n, said main adding unit having an adding register for storing a variable R_j ;

wherein, in order to perform the following operation in the order j=l, l-1, l-2, . . . 1, thereby to obtain the last R₁ in the form of C≡

M₁ ×

M₂ mod n;

##EQU87## where [ ] is a Gaussian symbol, [x] the largest possible integer smaller than or equal to x, and λ and

l constants, said quotient calculating unit is connected to said C-, M₂ - and n-registers and said main adding unit and performs an operation ##EQU88## said main adding unit is connected to said quotient calculating unit and said C-, M₂ - and n-registers and forms an operation M₁ ×

M₂,j '"'"'+2.sup.λ

R_j+1 -Q_j ·

n, and said controller performs control for obtaining said C by the respective calculations of said quotient calculating unit and said main adding unit.

2. A cryptosystem according to claim 1 wherein first and second adding registers are provided as said adding register;

said variable R_j is divided into R_j,0 and ##EQU89## R_j,0 and R_j,1 are stored in said first and second adding registers; and

said main adding unit performs the following operation;

##EQU90##

3. A cryptosystem according to claim 2 wherein said quotient calculating unit comprises a pre-processing section and a post-processing section connected thereto, said pre-processing section being supplied with said n to calculate [2^u ÷

[n·

2^-m ]]=v (m and u being constants) and said post-processing section being supplied with said R_j+1, M₁, M₂,j '"'"' and v to calculate Q_J " by approximation setting ##EQU91## in the case of ω

=0 and, in the case of ω

=1, setting ##EQU92## and setting as said Q_j ##EQU93## (S being a constant and Q_j "=Q_j -δ

holding and δ

being an integer), and wherein compensating calculation means is included for obtaining, from said R₁,R₁ +δ

·

n which satisfies 0≦

R₁ +δ

·

n<

n.

4. A cryptosystem according to claim 3 wherein said pre-processing section is a memory which is read out using [n·

2^-m ] as its address.

5. A cryptosystem according to claim 2 wherein λ

=1 and ω

=0;

said quotient calculating unit is means supplied with said M₁, δ

_j, n and R_j+1, for obtaining an approximate value Q_j " of Q_j such that the calculation result obtained by calculating [2R_j+1 ·

2^-m ]+[δ

_j ·

M₁ ·

2^-m ]-[Q_j ·

n·

2^-m ] while changing Q_j successively varies in sign with respect to a reference value; and

compensating calculation means is included for obtaining, from said R₁, R₁ +δ

·

n which satisfies 0≧

R₁ +δ

·

n<

n (δ

being an integer).

6. A cryptosystem according to claim 3 or 5 wherein said main adding unit comprises an M₁ ·

M₂,j calculating section for calculating M₁ ×

M₂,j '"'"', a-Q_j ·

n calculating section for calculating -Q_j "×

n, said first and second adding registers for storing variables R_j+1,0 and R_j+1,1, means for multiplying the contents R_j+1,0 and R_j+1,1 of said first and second adding registers by 2.sup.λ

, a carry save adder for adding together the resulting 2.sup.λ

·

R_j+1,0 and 2.sup.λ

·

R_j+1,1, the calculated M₁ ×

M₂,j '"'"' and the calculated -Q_j "×

n and storing the addition result in said first and second adding registers, and a carry propagation adder for adding two outputs from said carry save adder and storing the addition result in said C-register;

said compensating calculation means comprises a selector for selecting one of the contents of said first and second adding registers, R_j+1,0 and R.sub. j+1,1, and said 2.sup.λ

-multiplied values, 2.sup.λ

·

R_j+1,0 and 2.sup.λ

·

R_j+1,1, for input to said carry save adder, means for making zero one of M₁ and M₂,j '"'"' applied to said M₁ ·

M₂,j '"'"' calculating section, means for setting -Q_j applied to said -Q_j "·

n calculating section to +1, and means for selecting R_j+1,0 and R_j+1,1 by said selector at the time of compensating calculation, making one of M₁ and M₂,j '"'"' to be zero and -Q_j to be +1, and activating said carry save adder and said carry propagation adder to perform an operation R₁ +δ

·

n.

7. A cryptosystem according to claim 3 or 5 wherein said main adding unit comprises an M₁ ·

M₂,j calculating section for calculating M₁ ×

M₂,j '"'"', a -Q_j ·

n calculating section for calculating -Q_j "×

n, said first and second adding registers for storing the variable R_j+1,i (i-0,

     1), a carry save adder for adding 2.sup.λ

·

R_j+1,i (i=0,

     1) obtained by multiplying R_j+1,i (i=0,

     1) by 2.sup.λ

, the calculated M₁ ·

M₂,j '"'"' and the calculated -Q_j "·

n and storing the addition result in said first and second adding registers, and a carry propagation adder for adding two outputs from said carry save adder and storing the addition result in said C-register; and

said compensating calculation means comprises a first selector for selecting either the one output from said carry save adder or the content of said C-register, a second selector for selecting either the other output from said carry save adder or n applied to said -Q_j ·

n calculating section, and means for selecting the content of the C-register and the n by said first and second selector, respectively, during compensating calculation, and activating said carry propagation adder to perform an operation R₁ +δ

·

n.

8. A cryptosystem according to claim 2 wherein said main adding unit comprises an M₁ ·

M₂,j calculating section for calculating M₁ ×

M₂,j '"'"', a -Q_j ·

n calculating section for calculating -Q_j "×

n, said first and second adding registers for storing the variable R_j+1,i (i-1,

     0) a carry save adder for adding 2.sup.λ

R_j+1 obtained by multiplying R_j+1,i by 2.sup.λ

, the calculation result of said M₁ ·

M₂,j calculating section and the calculation result of said -Q_j ·

n calculating section and storing the addition result in said first and second adding registers, and a carry propagation adder for adding two outputs from said carry save adder and storing the addition result in said C-register.

9. A cryptosystem according to claim 8, further including a selector for selecting one of the calculation results of said M₁ ·

M₂,j calculating section and said -Q_j ·

n calculating section and supplying the selected calculation result to said carry save adder, and means for adding the selected calculation result and said 2.sup.λ

·

R_j+1 and adding the addition result, for each j, with the other calculation result selected by said selector.

10. A cryptosystem according to claim 2, 3 or 5 wherein said main adding unit is divided into a plurality of sliced sections of the same function;

said M₁ and n are divided into every fixed width of their binary integers and sequentially applied to said sliced sections;

said M₂,j '"'"' and Q_j are applied to said sliced sections in common to them;

said sliced sections each perform a calculation R_j =M₁ ×

M₂,j '"'"'+2.sup.λ

R_j+1 -Q_j "×

n for the M₁, n, Q_j, M₂,j '"'"' and R_j+1 applied to them; and

said sliced sections are each connected to a higher-order one of them via a connection signal line for applying thereto one part of the result of said calculation.

11. A cryptosystem according to claim 10, wherein an adder for performing the addition in the calculation R_j =M₁ ×

M₂,j '"'"'+2.sup.λ

R_j+1 -Q_j "×

n in each sliced section is composed of a plurality of carry save adders;

the number of bits of each of an input and an output signal line of said carry save adder is selected larger than the number of binary bits of the fixed width of said integers; and

means is included for supplying the most significant one of binary bits of the fixed width of said integers on the low-order side in the output signal line of each carry save adder to a corresponding one of the carry save adders of the higher-order sliced sections via a part of said connection signal line, and for applying said most significant bit applied from the lower-order sliced sections to the corresponding carry save adder, for applying λ

bits of the last stage output signal line of said carry save adder to the higher-order sliced section via the other part of said connection signal line to apply a signal of said λ

bits from the lower-order sliced section to the last-stage output of said carry save adder.

12. A cryptosystem according to claim 10 wherein said sliced section each include an M₂ -register for input therein said divided M₂.

13. A cryptosystem according to claim 12 wherein said sliced sections each include a selector controlled by said e_i to select one of said M and C for input to said M₂ -register.

14. A cryptosystem according to claim 13 wherein said sliced section each includes an M-register for storing said divided M.

15. A cryptosystem according to claim 13 wherein said sliced sections each include an n-register for storing said divided n.

16. A cryptosystem according to claim 13 wherein said sliced section each include an e-register for storing said divided e.

17. A cryptosystem according to claim 13 wherein said sliced sections each include a C-register for storing said divided C.

18. A cryptosystem according to claim 13 wherein said sliced sections each include at least one part of said quotient calculating section, and only one of said quotient calculating sections of said sliced sections is made operable.

19. A cryptosystem according to claim 13 wherein said sliced sections each include said controller, and only one of said controllers of said sliced sections is made operable.

20. A cryptosystem in which integers M, e and n (0≧

M<

n) are applied to M, e and n registers;

variables C and M₂ are stored in C- and M₂ -registers;

the integer e being represented by ##EQU94## (e_i =0 or

     1);

the variable C is initially set to 1;

repetitive calculations are performed in accordance with the following Steps (1) and (2) for each value i in the order i=k, k-1, k-2, . . . 1, 0;

in Step (1) an operation C≡

M₁ ×

M₂ mod n is performed with M₁ =C and M₂ =C;

in Step (2), the value of e_i is checked and if e_i =1, the operation C≡

M₁ ×

M₂ mod n is further performed with M₁ =C and M₂ =M; and

said repetitive calculations are completed with i=0, producing the last C in the form of C≡

M^e mod n;

said cryptosystem comprising a main adding unit including at least an M₁ ·

M₂,j calculating section for calculating M₁ ×

M₂,j '"'"', a -Q_j ·

n calculating section for calculating -Q_j "×

n, a selector for selecting one of the calculation results M₁ ·

M₂,j '"'"' and -Q_j "·

n, an adding register and an adder for adding the content of said adding register and the output of said selector and storing the addition result, in said adding register, a controller, and a quotient calculating unit;

wherein the main adding unit is controlled by said controller so that a 0 is applied as a variable Z to said adding register, said calculation result M₁ ·

M₂,j '"'"' is selected by said selector, an operation Z=Z+M₁ ×

M₂,j '"'"' is performed in the order j=1, 2, . . . l to obtain M₁ ·

M₂ ≡

Z, ##EQU95## (λ

being constant) is applied to said adding register, said calculation result -Q_j "·

n is selected by said selector, and an operation R_j =2.sup.λ

R_j+1 +Z_j -Q_j "·

n is performed in the order j=l, l-1, . . . 1;

wherein said main adding unit is divided into a plurality of sliced sections of the same function, said M₁ and n are divided into every fixed width of their binary integers and sequentially applied to said sliced sections, said M₂,j '"'"' and Q" are applied to said sliced sections in common to them, said sliced sections each perform said operations Z=Z+M₁ ×

M₂,j '"'"' and R=2.sup.λ

R_j+1 +Z_j -Q_j "·

n for the M₁, n, Q_j " and M₂,j '"'"' applied to them, said sliced sections are each connected to a higher-order one of them via a first connection signal line for applying thereto one part of the calculation result Z, and said sliced sections are each connected to a lower-order one of them via a second connection signal line for applying thereto the calculation result R_j.

22. A cryptosystem according to claim 20 wherein first and second adding registers are provided as said adding register;

said variable R_j is divided into R_j,0 and ##EQU99## R_j,0 and R_j,1 are stored in said first and second adding registers; and

said main adding unit performs the following operation;

##STR1##

21. A cryptosystem in which integers M, e and n (0≦

M<

n) are applied to M, e and n registers;

variables C and M₂ are stored in C- and M₂ -registers;

the integer e being represented by ##EQU96## (e_i =0 or

     1);

the variable C is initially set to 1;

repetitive calculations are performed in accordance with the following Steps (1) and (2) for each value i in the order i=k, k-1, k-2, . . . 1, 0;

in Step (1) an operation C≡

M₁ ×

M₂ mod n is performed with M₁ =C and M₂ =C;

in Step (2), the value of e_i is checked and if e_i =1, the operation C≡

M₁ ×

M₂ mod n is further performed with M₁ =C and M₂ =M; and

said repetitive calculations are completed with i=0, producing the last C in the form of C≡

M^e mod n;

said cryptosystem comprising a main adding unit including at least an M₁ ·

M₂,j calculating section for calculating M₁ ×

M₂,j '"'"', a -Q_j ·

n calculating section for calculating -Q_j "×

n, a selector for selecting one of the calculation results M₁ ·

M₂,j '"'"' and -Q_j "·

n, an adding register and an adder for adding the content of said adding register and the output of said selector and storing the addition result in said adding register, a controller, and a quotient calculating unit;

wherein a 0 is applied as a variable Z to said adding register, said calculation result M₁ ·

M₂,j '"'"' is selected by said selector, an operation Z=Z+M₁ ×

M₂,j '"'"' is performed in the order j=1, 2, . . . l to obtain M₁ ·

M₂ ≡

Z, then R_l+1 of ##EQU97## is applied to said adding register, said calculation result -Q_j "·

n is selected by said selector, said quotient calculating unit comprises a calculating section for calculating X_j =[2.sup.λ

·

R_j ·

2^-m ]+S (S being a constant) and a calculating section for calculating ##EQU98## and said quotient calculating unit is controlled by said controller to calculate

space="preserve" listing-type="equation">Q.sub.j "=[X.sub.j ×

v×

2.sup.-u ]+1

when

space="preserve" listing-type="equation">X.sub.j ≧

0

space="preserve" listing-type="equation">Q.sub.j "=[X.sub.j ×

v×

2.sup.-u ]

when

space="preserve" listing-type="equation">X.sub.j <

0

or

space="preserve" listing-type="equation">Q.sub.j "=[X.sub.j ×

v×

2.sup.-u ]+1

when

space="preserve" listing-type="equation">X.sub.j >

0

space="preserve" listing-type="equation">Q.sub.j "=[X.sub.j ×

v×

2.sup.-u ]

when

space="preserve" listing-type="equation">X.sub.j ≦

0

and calculate R_j =2.sup.λ

·

R_j +R_j -Q_j "·

n in the order j=l, l-1, . . . 1;

wherein compensation calculation means is included for calculating, when R₁ ≧

0, R₁ =R₁ +n until R₁ ≧

0 is obtained;

wherein said main adding unit is divided into a plurality of sliced sections of the same function, said M₁ and n are applied to said sliced sections while being sequentially divided for each fixed width of their integers, said M₂,j '"'"' and Q" are applied to said sliced sections in common to them, said sliced sections each perform said operations Z=Z+M₁ ×

M₂,j '"'"' and R_j =2.sup.λ

R_j+1 +Z_j -Q_j "·

n for the M₁, n, Q_j " and M₂,j '"'"' applied to them, said sliced sections are each connected to a higher-order one of them via a first connection signal line for applying thereto one part of the calculation result Z, and said sliced sections are each connected to a lower-order one of them via a second connection signal line for applying thereto the calculation result R_j.