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

Claim 2

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; second input means for sequentially inputting a second bit data representing a second integer by a predetermined number of bits; storage means for storing a third bit data; 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 residue obtained by dividing, a bit portion of the third bit data shifted by the predetermined number of bits, higher than the most significant bit of a fourth bit data representing the third integer supplied from said storage means, by the third integer; and adding means for adding a bit portion of the third bit data shifted by the predetermined number of bits, not higher than the most significant bit of the fourth bit data supplied from said storage means, a product supplied from said multiplying means and the residue outputted from said circuit means, said storage means storing a result of an addition by said adding means as a new third bit data.

Claim 3

A calculating apparatus according to claim 1 wherein said predetermined number of bits is 1 bit.

Claim 4

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.

Claim 5

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.

Claim 6

A calculating a apparatus according to claim 3 wherein said second predetermined number of bits is 1 bit.

Claim 7

A calculating apparatus according to claim 3 wherein each of said plurality of circuit means has tables whereby respective bit portions of residues obtained by dividing the bit portion of the third bit data higher than the most significant bit of the fourth bit data corresponding to the third bit data can be read.

Claim 8

A calculating apparatus according to claim 3 wherein each of said plurality of multiplying means includes a logic gate circuit.

Claim 9

A calculating apparatus according to claim 3 wherein each of said multiplying means includes a memory for storing products of two bit data which can be read out in accordance with supplying the same two bit data.

Claim 10

A calculating apparatus according to claim 3 wherein the bit data of the lower bit portion which is received by said adding means is a result of a previous addition performed by said adding means and the bit data of the higher bit portion which is received by said adding means is a carry generated due to an addition performed by another adding means.

Claim 11

A calculating apparatus according to claim 3 wherein each of said plurality of said adding means performs simultaneously and adds the lower bit portion of a previous addition performed by said adding means and the carry generated due to a previous addition performed by another adding means.

Claim 12

A calculating apparatus according to claim 3 wherein each of a plurality of said adding means causes the result of said addition including a carry to be stored in the same storage means of a plurality of said storage means.

Claim 13

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.

Claim 14

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.

Claim 15

A calculating apparatus according to claim 11 wherein a plurality of said processing elements constitute a systolic array.

Claim 16

A calculating apparatus according to claim 11 wherein the adding means of said plurality of said processing elements perform the additions simultaneously and add carries generated due to said additions at the next additions.

Claim 17

A communication method comprising the steps of: obtaining bit data representing a cryptogram C=M 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.

Claim 18

A communication method comprising the steps of: obtaining bit data representing a cryptogram C=M 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.

Claim 19

A communication method comprising the steps of: receiving bit data representing a cryptogram C; obtaining bit data representing information M=C 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.

Claim 20

A communication method comprising the steps of: receiving bit data representing a cryptogram C; obtaining bit data representing information M=C 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.