Calculating apparatus and method of encrypting/decrypting communication data by using the same

A calculating apparatus for calculating a residue obtained by dividing a product of a first integer and a second integer by a third integer, comprising:

• first input means for inputting a first bit data representing the first integer by dividing the first bit data into bit portions each having a first predetermined number of bits;
• second input means for sequentially inputting a second bit data representing the second integer by a second predetermined number of bits;
• a plurality of storage means each for storing respective bit portions of a third bit data representing an intermediate result;
• a plurality of multiplying means each for sequentially multiplying respective bit portions of said first bit data inputted by said first input means with the second predetermined number of bits of the second bit data sequentially inputted by said second input means;
• a plurality of circuit means each for outputting respective bit portions of a residue obtained by dividing, a bit portion of the third bit data higher than the most significant bit of a fourth bit data representing the third integer, supplied from a predetermined one of said plurality of storage means, by the third integer;
• and
• a plurality of adding means each for adding a lower bit portion of a bit data shifted by the predetermined number of bits, stored in one of said plurality of storage means, a higher bit portion of a bit data stored in another one of said plurality of storage means, a product supplied form one of said plurality of multiplying means and one of the bit portion of the residue outputted from one of said plurality of circuit means, each of said storage means storing a result of the addition by said adding means as a new third bit.

A calculating apparatus for calculating a residue obtained by dividing a product of integers A and B by an integer N including a plurality of processing elements, each of a plurality of said processing elements comprising:

• first input means for inputting a first bit data representing a predetermined one of the bit portions according to the respective processing element, obtained by dividing the integer A into bit portions each having a first predetermined number of bits;
• second input means for sequentially inputting a second bit data representing the integer B by a second predetermined number of bits through a preceding processing element;
• storage means for storing a third bit data and outputting the third bit data to a following processing element;
• third input means for receiving an output from the preceding processing element;
• multiplying means for sequentially multiplying the first bit data inputted by said first input means with the predetermined number of bits of the second bit data inputted by said second input means;
• circuit means for outputting a predetermined one of the bit portions according to the respective processing element, obtained by dividing a residue obtained by dividing the third bit data supplied from the storage means in the predetermined processing element, by the third integer;
• and
• adding means for adding a lower bit portion of the third bit data supplied from said storage means, a lower bit portion of a product supplied from said multiplying means, an output from said circuit means, a higher bit portion of the third bit data supplied from the storage means of the preceding processing element, and a higher bit portion of a product supplied from the multiplying means of the preceding processing element, said storage means storing a result of the addition by said adding means as a new third bit data.

A communication method comprising the steps of:

• obtaining bit data representing a cryptogram C=M.sup.e mod N for bit data representing information M. to be transmitted from given integers e and N by a repetition of modular multiplication of two integers while making N to be a modulo;
• and
• transmitting the bit data representing cryptogram C, said modular multiplication of the two integers comprising the steps of:
• inputting a first bit data representing the first integer;
• sequentially inputting a second bit data representing the second integer by a predetermined number of bits;
• sequentially multiplying the first bit data with the predetermined number of bits of the second bit data;
• obtaining a residue by dividing a bit portion of double of a third bit data in a register, higher than the most significant bit of a bit data representing the integer N, by the integer N;
• adding a bit portion of the double of the third bit data in the register not higher than the most significant bit of the bit data representing the integer N, a result of the multiplication and the obtained residue to one another;
• and
• storing the result of said addition as a new third bit data in said register.

A communication method comprising the steps of:

• receiving bit data representing a cryptogram C;
• obtaining bit data representing information M=C.sup.d mod N for the received bit data representing cryptogram C from given integers d and N by a repetition of modular multiplication of two integers while making N to be a modulo said modulo multiplication of the two integers comprising steps of:
• inputting a first bit data representing the first integer;
• sequentially inputting a second bit data representing the second integer by a predetermined number of bits;
• sequentially multiplying the first bit data with the predetermined number of bits of the second bit data;
• obtaining a residue by dividing, a bit portion of double of a third bit data in a register, higher than the most significant bit of a bit data representing the integer N, by the integer N;
• adding a bit portion of the double of the third bit data in the register not higher than the most significant bit of the bit data representing the integer N, a result of said multiplication, and the obtained residue to one another;
• and
• storing the result of the addition as a new third bit data in said register.