초록 ▼

A cryptosystem for the RSA cryptography which calculates C≡Me mod n and, for this calculation, performs an operation C=M1×M2 mod n. An operation [Figure] where M′2,j =M2,j -wdjllwd(j-1)lRl+1 =0, and w1 as the result of the calculation M1×M2 mod n. The calculation [Figure] is performed in a quotient

A cryptosystem for the RSA cryptography which calculates C≡Me mod n and, for this calculation, performs an operation C=M1×M2 mod n. An operation [Figure] where M′2,j =M2,j -wdjllwd(j-1)lRl+1 =0, and w1 as the result of the calculation M1×M2 mod n. The calculation [Figure] is performed in a quotient calculating unit, and the calculation M1×M2,j′+2lj+1-Qjㆍn is performed in a main adding unit. Where, variable Rj may be divided into two parts Rj,0 and Rj,1. In this way, the multiplication and the division are simultaneously conducted, thereby to raise the calculation speed.

대표청구항 ▼

A cryptosystem in which integers M, e and n (0≤M2 are stored in C- and M2-registers; the integer e being represented by [Figure] (ei=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

A cryptosystem in which integers M, e and n (0≤M2 are stored in C- and M2-registers; the integer e being represented by [Figure] (ei=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≡M1×M2 mod n is performed with M1=C and M2=C; in Step (2), the value of ei is checked and if ei=1, the operation C≡M1×M2 mod n is further performed with M1=C and M2=M; and said repetitive calculations are completed with i=0, producing the last C in the form of C≡Me mod n; said cryptosystem comprising a main adding unit including at least an M1ㆍM2,j calculating section for calculating M1×M2,j′, a -Qjㆍn calculating section for calculating -Qj″×n, a selector for selecting one of the calculation results M1ㆍM2,j′and -Qj″ㆍ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 M1ㆍM2,j′is selected by said selector, an operation Z=Z+M1×M2,j′is performed in the order j=1, 2, . . . l to obtain M1ㆍM2≡Z, then Rl+1 of [Figure] [Figure] is applied to said adding register, said calculation result -Qj″ㆍn is selected by said selector, said quotient calculating unit comprises a calculating section for calculating Xj=[2lㆍRjㆍ2-m]+S (S being a constant) and a calculating section for calculating [Figure] and said quotient calculating unit is controlled by said controller to calculate Qj″=[Xj×v×2-u]+1 when Xj≥0 Qj″=[Xj×v×2-u] when Xj or Qj″=[Xj×v×2-u]+1 when Xj>0 Qj″=[Xj×v×2-u] when Xj≤0 and calculate Rj=2lㆍRj+Rj-Qj″ㆍn in the order j=l, l-1, . . . 1; wherein compensation calculation means is included for calculating, when R1≥0, R1=R1+n until R1≥0 is obtained; wherein said main adding unit is divided into a plurality of sliced sections of the same function, said M1 and n are applied to said sliced sections while being sequentially divided for each fixed width of their integers, said M2,j′and Q″are applied to said sliced sections in common to them, said sliced sections each perform said operations Z=Z+M1×M2,j′and Rj=2lRj+1+Zj-Qj″ㆍn for the M1, n, Qj″and M2,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 Rj.