Method for implementing the chinese remainder theorem
View Patent ↗The modular exponentiation function used in public key encryption and decryption systems is implemented in a standalone engine having at its core modular multiplication circuits which operate in two phases which share overlapping hardware structures. The partitioning of large arrays in the hardware structure, for multiplication and addition, into smaller structures results in a multiplier design comprising a series of nearly identical processing elements linked together in a chained fashion. As a result of the two-phase operation and the chaining together of partitioned processing elements, the overall structure is operable in a pipelined fashion to improve throughput and speed. The chained processing elements are constructed so as to provide a partitionable chain with separate parts for processing factors of the modulus. In this mode, the system is particularly useful for exploiting characteristics of the Chinese Remainder Theorem to perform rapid exponentiation operations. A checksum mechanism is also provided to insure accurate operation without impacting speed and without significantly increasing complexity. While the present disclosure is directed to a complex system which includes a number of features, the present application is particularly directed to a method for performing modular exponentiation which takes advantage of processing element chain partitioning and the Chinese Remainder Theorem.
1. A digital processing method for determining A mod N using a calculating engine having two inputs x and y and which produces an output x y 2 −mk mod N, where n is the number of bits in the binary representation of N, where k is the size of the words processed by said engine in bits, and where m is the smallest integer for which mk≧n+2, said method comprising the steps of:
operating said engine with inputs 1 and A 0 to produce a first result, where A 0 is the low order bits in the representation of A as A 1 2 mk +A 0 ;
adding said first result to A 1 to produce a second result, where the addition is modulo N; and
operating said engine with inputs being said second result and 2 +2mk mod N, whereby the output of said engine is A mod N.
2. A digital processing apparatus for determining A mod N, where A is a binary number having the form A 1 2 mk +A 0 , said apparatus comprising:
a calculating engine having two inputs x and y, and which produces an output x y 2 −mk mod N, where n is the number of bits in the binary representation of N, where k is the size of the words processed by said engine in bits, and where m is the smallest integer for which mk≧n+2;
a register for storing the output from said engine;
a modulo N adder having as a first input the output from said calculating engine or said register, and having said A 1 as a second input;
means for controlling the inputs to said engine over at least two cycles of its operation so as to selectively supply various inputs to said engine, said inputs being selected from the group consisting of the constant 1, the constant 2 +2mk , the output from said register and the output from said adder, said selection operating in sequence so as to produce A mod N in said register.
3. A digital processing method using a calculating engine for operations modulo an integer for determining A B mod N where N is the product of two prime numbers, N p and N q , said method comprising the steps of:
determining A p as A mod N p ;
determining A q as A mod N q ;
determining B p as B mod (N p −1);
determining B q as B mod (N q −1);
determining A pB as (A p ) Bp mod N p ;
determining A qB as (A q ) Bq mod N p ; and
determining A B as A qB +N q ((A pB −A qB ) mod N p ) U mod N p , where U=(1/N q ) mod N p wherein in said method at least one of said first six determining steps is carried out with the use of said calculating engine having two inputs x and y, and which produces an output x y 2 −mk mod N, where n is the number of bits in the binary representation of N, where k is the size of the words processed by said engine in bits, and where m is the smallest integer for which mk≧n+2.
4. The method of claim 3 in which each one of said first six steps is carried out with the use of said engine.
5. An apparatus for determining A B mod N where N is the product of two prime numbers, N p and N q , said apparatus comprising:
A digital calculating engine having two inputs x and y, and which produces an output x y 2 −mk mod N, where n is the number of bits in the binary representation of N, where k is the size of the words processed by said engine in bits, and where m is the smallest integer for which mk≧n+2;
a first register for storing A as an input to said engine;
a second register for storing N p as an input to said engine;
a third register for storing N q as an input to said engine;
a fourth register for storing U=(1/N q ) mod N p as an input to said engine;
a fifth register for storing B q =B mod (N q −1) as an input to said engine;
a sixth register for storing B p =B mod (N p −1) as an input to said engine; and
means for storing intermediary results and for controlling the inputs to said engine over a plurality of cycles so that an output of said engine is A B mod N.