Encryption apparatus and methods for raising a large unsigned integer to a large unsigned integer power modulo a large unsigned integer

• US 4,658,094 A
• Filed: 03/28/1985
• Issued: 04/14/1987
• Est. Priority Date: 03/28/1985
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: ITT Corporation (ITT, Inc.)
• Inventors: Clark, James M.
• Primary Examiner(s): Cangialosi, Salvatore
• Assistant Examiner(s): Lewis, Aaron J.
• Application Number:
  US06/716,877
• Time in Patent Office: 747 Days
• Field of Search: 178/22.08, 178/22.11, 178/22.09
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/122 Hardware reduction or efficient architectures
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

There is disclosed an encryption apparatus which apparatus functions to raise a large unsigned integer (B) indicative of message data to a large unsigned integer power E, modulo a large unsigned integer M with each of said integers being as large as N bits wherein the resulting large unsigned integer C is adapted for transmission over an insecure communications channel. The apparatus may likewise operate on a received integer C to recover the decrypted message B. The circuitry includes first logic means which is responsive to the large unsigned integer (B) for successively squaring said integer including means for reducing said squared integers successively by a given modulus M to provide at an output a first value indicative of said squared integer as reduced by said given modulus, selectively operated gating means are coupled to said first logic means and operates to receive bits of a given exponent power E. The gating means applies selected bits of the exponent power to second logic means which are controlled by said gating means to provide the product of said first value as further modified by modulus means for providing at its output the large unsigned integer for transmission over the insecure communications channel. The first and second logic means are constructed such that the required circuit size to perform the computation is significantly reduced in complexity resulting in increased speed together with a substantial reduction in cost.

Claims

1. Encryption apparatus for raising a large unsigned integer (B) indicative of message data to a large unsigned integer power (E), modulo a large unsigned integer M, with each of said integers being as large as N bits, where N is at least twenty one, wherein a resulting large unsigned integer C is adapted for transmission over an insecure communications channel, comprising:

first logic means responsive to said large unsigned integer B for successively squaring said integer, including means for reducing said squared integer succesively by a given modules, to provide at an output a first value indicative of said squared integer as reduced by said given modules, wherein siad first logic means comprises a first register having an input for receiving said large unsigned integer (B) and an output coupled to a first modulo multipier means for successively squaring said integer and reducing said squared integer by said given modulus, with the output of said modulo-multiplier means coupled to the input of said first register to enable said first value to be stored therein, selectively operated gating means having one input adapted to receive a second value indicative of a given exponent power E and having another input coupled to said output of said first logic means,

second logic means having input coupled to said gating means and operative as controlled by said gating means to provide an output value indicative of the product of said first value as further modified by modulus means including in said second logic means to provide at said outputs said resulting large unsigned integer (C) adapted to be transmitted over said insecure communications channel, wherein said second logic means comprises a second register having an input adapted to receive a first binary value, with an output of said second register coupled to the input of a second multiplier modulo means, with another input of said second modulo multiplier, and with the output of siad second modulo-multiplier means coupled to the input of said second register to cause it to store said large unsigned integer.

2. The encryption apparatus according to claim 1, wherein said binary input to said second register is a binary 1.

3. The encryption apparatus according to claim 1, further including a modulus register adapted to store therein a number indicative of said given modulus and having an output coupled to said first and second logic means for applying said given modulus thereto.

4. The encryption apparatus according to claim 1, wherein said first logic means further includes an arithmetic circuit having a first plurality of registers, one for storing therein values indicative of said modulus and one for storing said modulus as multiplied by a given factor and one for storing said large unsigned integer (B), multiplexer means coupled to said plurality of registers for selecting any one output of said plurality of registers, adder means having an input coupled to said multiplexer means and a second input responsive to said first value to provide at an output another successive value indicative of a modified first value.

5. Encryption apparatus for raising a large unsigned integer (B) indicative of message data to a large unsigned integer power (E), modulo a large unsigned integer M, with each of said integers being as large as N bits, where n is at least twenty one, wherein a resulting large unsigned integer C is adapted for transmission over an insecure communications channel, comprising:

master logic means having a plurality of inputs and a plurality of outputs, with said master logic means including arithmetic computation means comprising a plurality of input devices for storing therein said large unsigned integer (B) and a given modulus, means coupled to said input devices to select a given one, multiplying means for multiplying the stored information in said selected devices with said large unsigned integer, register means for storing said multiplied information according to the least and most significant bits for providing storage of successive squares of said large unsigned number as reduced by said given modulus said master logic means further including means for generating command data,

slave circuit means having a plurality of inputs coupled to said outputs of said master logic means for receiving selected data from said master logic means according to said stored information, and indicative of multiplied information, said slave circuit means including arithmetic computation means for successively multiplying said multiplied information according to said command data as generated by said master logic means,

microprocessor means coupled to the input terminals of said master logic means and operative to provide a series of instructions to said master logic means indicative of the message data to be processed and the given modulus assigned to said data.

6. The encryption apparatus according to claim 5 wherein said master logic means includes clock generating means for controlling the operation of said arithmetic computation means and for providing on selected outputs timing waveforms for said slave circuit means.

7. The encryption apparatus according to claim 5, wherein said automatic computation means in both said master logic means and said slave circuit means includes first and second selectable registers, with said first register adapted to store the squared value of said large unsigned integer (B) as reduced by said given modulus and with said second register adapted to store an output value indicative of the product of said value stored in said first register as further modified by said given modulus.

8. The encryption apparatus according to claim 5, wherein said master logic means further includes a state register having an output coupled to said slave circuit means to indicate to said slave circuit means the computational state of said master logic means.

9. The encryption apparatus according to claim 5, wherein both said master logic means said slave circuit means include a partial product register adapted to store therein partial products resulting from said multiplications.

10. The encryption apparatus according to claim 9, wherein multiplying means includes first and second adders, said first adder adapted for adding carries and said second adder adapted to add values to said partial product register.

11. The encryption apparatus according to claim 5, wherein said master logic means further includes control circuitry adapted to receive a command signal from said microprocessor, a load register responsive to said command to cause said register to commence a shifting operation for controlling the operation of said arithmetic computation means.

12. The encryption apparatus according to claim 5, wherein said master logic means further includes a cycle-count register operative to store therein a count indicative of the number of multiplications performed by said multiplying means to control the number of products accumulated during a multiplication operation.

13. The encryption apparatus according to claim 5, wherein said master logic means further includes a control register adapted to receive commands from said microcprocessor means via the data bus.

14. The encryption apparatus for raising a large unsigned integer (B) indicative of message data to a large unsigned integer power (E), modulo a large unsigned integer (M) with each of said integers being as large as N bits, where N is at least twenty one, for transmitting a resulting modulo large unsigned integer (C) as encrypted data over an insecure communications channel, comprising

first means having an input for receiving said large unsigned integer (B) indicative of message data and for providing said large unsigned integer at an output,

first multiplier modulo means including means for storing a given modulus M having an input coupled to the output of said first means for providing at an output a signal indicative of the squared value of said message data (B) as reduced by a selected modulus, with said output of said first mulitplier modulo means coupled to the input of said first means to cause said first means to provide a sequence of squares modulo indicative of said modulo large unsigned integer (M)

gating means having one input adapted to receive a valve indicative of said integer power (E) and another input coupled to the output of said first means,

second means for storing a result indicative of the product of selected squares modulo, said second means having an output and an input adapted to receive a given binary value,

second multiplier modulo means including means for storing said given modulus having a first input coupled to said gating means and a second input coupled to the output of said second means for providing at an output a value indicative of the product of the values stored in said first and second means as controlled by said gating means and with said product reduced by the modulus, with the output of said second multiplier modulo means coupled to the input of said second means, whereby said second means has stored therein said resulting modulo large unsigned integer (C) for transmission over said communications channel.

15. The encryption apparatus according to claim 14, wherein said first multiplier modulo means includes a partial product register means for storing partial products of said squared value of said message data as reduced by said selected modulus, with said product register capable of storing said values according to the most and least significant bits.

16. The encryption apparatus according to claim 15, wherein said first and second modulo means each are adapted to time share said partial product register.

17. The encryption apparatus according to claim 14, whrein said encryption apparatus further includes a microprocessor having output data lines coupled to said first and second multiplier modulo means for providing said large unsigned integer and said given binary value and for directing a series of commmands to said first and second means operative to control the respective multiplications.

18. A method for raising a large unsigned integer (B) to a large unsigned integer power (E) (exponent), modulo a large unsigned integer (M), with each of said integers being as large as N bits, where N is at least twenty one, comprising the steps of:

(a) storing said large unsigned integer (B)

(b) squaring said stored value

(c) reducing said squared value by the modulus M to obtain a value S

(d) providing a product of selected squares, Modulo M

(e) multiplying said product of selected squares, modulo M by said value S according to a given value of an exponent bit (E) to obtain a value X

(f) reducing said value X by said modulus M to produce a value R

(g) storing said value R indicative of said large unsigned integer M.