Residue number encryption and decryption system

• US 5,077,793 A
• Filed: 01/18/1991
• Issued: 12/31/1991
• Est. Priority Date: 09/29/1989
• Status: Expired due to Fees

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Falk, R. Aaron, Houk, Theodore L.
• Primary Examiner(s): Buczinski, Stephen C.
• Application Number:
  US07/642,561
• Time in Patent Office: 347 Days
• Field of Search: 380/28, 380/30, 364/200, 364/900, 364/746
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

An encryption and decryption system performs encryption and decryption using the residue number system. A binary input signal is converted into residue number system representation in a binary to residue converter. Pseudo random numbers, generated from pseudo random number generators, are then added to the converted input signal in modular, that is, residue number system, adders. The outputs of the modular adders are converted into binary or mixed radix digit representation and are then transmitted to the location of a decrypter. The transmitted binary or mixed radix digit signal is converted back into residue number system representation in another converter and is then decrypted by subtracting the pseudo random number sequence. This decrypted signal is then converted into binary representation. The binary representation of the decrypted signal resembles the input signal.

Claims

1. A residue number encryption and decryption system, comprising:

a first converter, said first converter receiving an input signal and converting said input signal into a second signal, said second signal being in residue number representation;

an encrypter, said encrypter receiving and encrypting said second signal, and outputting a third signal in an encrypted residue number representation;

a first-number-system-to-second-number-system converter, said first-number-to-second-number-system converter receiving said third signal and converting said third signal into a fourth signal, said fourth signal being in a number system representation other than residue number representation;

a second-number-system-to-first-number-system converter, said second-number-system-to-first-number-system converter receiving said fourth signal and converting said fourth signal into a fifth signal, said fifth signal being in encrypted residue number representation;

a decrypter, said decrypter receiving and decrypting said fifth signal, and outputting a sixth signal; and

a fourth converter, said fourth converter receiving said sixth signal and converting said sixth signal into an output signal, said output signal providing the same information as said input signal.

2. A residue number encryption and decryption system as set forth in claim 1, wherein said encrypter comprises:

first pseudo random number generator means for generating a first set of pseudo random number signals in a residue number system (RNS) representation corresponding to a plurality of pseudo random numbers;

first modular operation means for performing modular arithmetic, said first modular operation means performing modular arithmetic operations, using said second signal and said first set of pseudo random number signals as operands, to produce said third signal; and

wherein said decrypter comprises;

second pseudo random number generator means for generating a second set of pseudo random number signals in a RNS representation corresponding to said plurality of pseudo random numbers; and

second modular operation means for performing modular arithmetic, said second modular operation means performing modular arithmetic operations, using said fifth signal and said second set of pseudo random number signals as operands, to produce said sixth signal.

3. A residue number encryption and decryption system as set forth in claim 2, wherein:

said first modular operation means adds said second signal to said first set of pseudo random number signals; and

said second modular operation means subtracts said second set of pseudo random number signals from said fifth signal.

4. A residue number encryption and decryption system as set forth in claim 2, wherein:

said first modular operation means subtracts said second signal from said first set of pseudo random number signals; and

said second modular operation means subtracts said fifth signal from said second set of pseudo random number signals.

5. A residue number encryption and decryption system as set forth in claim 2, wherein said second, third, fourth, fifth, and sixth signals and said first and second sets of pseudo random number signals are optic signals.

6. A residue number encryption and decryption system as set forth in claim 2, wherein said second, third, fourth, fifth, and sixth signals and said first and second sets of pseudo random number signals are electronic signals.

7. A residue number encryption and decryption system as set forth in claim 2, wherein:

said input and output signals and said fourth signal are in binary representation;

said first and third converters are binary to residue number system converters; and

said second and fourth converters are residue number system to binary converters.

8. A residue number encryption and decryption system as set forth in claim 2, wherein:

moduli used in residue number representations are varied in time; and

a key is passed between said encrypter and said decrypter, said key indicating which moduli are to be used by said residue number encryption and decryption system.

9. A residue number encryption and decryption system as set forth in claim 2, wherein:

said input and output signals are in binary representation;

said first converter is a binary to residue number system converter;

said second converter is a residue number system to mixed radix number system converter;

said fourth signal is in mixed radix number system representation;

said third converter is a mixed radix number system to residue number system converter; and

said fourth converter is a residue number system to binary converter.

10. A residue number encryption and decryption system as set forth in claim 9, wherein:

said second converter changes inputs and internal moduli over time and has fixed internal connections.

11. A residue number encryption and decryption system as set forth in claim 9, wherein

said second converter varies internal connections over time and uses fixed inputs and fixed moduli.

12. A residue number encryption and decryption system as set forth in claim 11, wherein said second converter comprises:

a plurality of stages, each stage including modular subtracters arranged parallel to each other and modular multipliers arranged parallel to each other.

13. A residue number encryption and decryption system as set forth in claim 12, wherein each stage further comprises:

a plurality of first switches to select residue digits; and

a plurality of second switches to select multiplicative inverses.

14. A residue number encryption and decryption system as set forth in claim 13, wherein:

when a new modulus, chosen to be next in a conversion order in a next stage, is selected, all of said first and second switches in said next stage are set to a new modulus position, except for switches associated with mixed base digits which have been calculated.

15. A method of encrypting and decrypting, comprising the steps of:

converting an input signal into a second signal, said second signal being a residue number system (RNS) representation of said input signal;

generating a first set of pseudo random number signals, said first set of pseudo random number signals being in a RNS representation and corresponding to a sequence of pseudo random numbers;

performing modular arithmetic operations, using said second signal and said first set of pseudo random number signals as operands, to generate a third signal;

transmitting said third signal to a receiver;

receiving said third signal in a receiver;

generating a second set of pseudo random number signals for said receiver, said second set of pseudo random number signals being in a RNS representation and corresponding to said sequence of pseudo random numbers; and

performing modular arithmetic operations at said receiver, using said third signal and said second set of pseudo random number signals as operands, to generate an output signal, said output signal providing the same information as said input signal.

16. A method of encrypting and decrypting as set forth in claim 15, wherein said transmitting step comprises the step of:

converting said third signal from RNS representation into binary representation; and

wherein said receiving step comprises the step of;

converting said third signal from binary representation into RNS representation.

17. A method of encrypting and decrypting as set forth in claim 15, wherein said transmitting step comprises the step of:

converting said third signal from RNS representation into mixed radix number system representation; and

wherein said receiving step comprises the step of;

converting said third signal from mixed radix number system representation into RNS representation.

18. A method of encrypting and decrypting as set forth in claim 17, wherein:

an order of said converting of said third signal from RNS representation into mixed radix number system representation is varied;

an order of said converting of said third signal from mixed radix number system representation into RNS representation is varied.

19. An encrypter comprising:

first pseudo random number generator means for generating a first set of pseudo random number signals in a residue number system (RNS) representation corresponding to a plurality of pseudo random numbers;

first modular operation means for performing modular arithmetic, said first modular operation means performing modular arithmetic operations, using a second signal and said first set of pseudo random number signals as operands, to produce a third signal;

communication link means for transmitting said third signal to another location, the output from said communication link means being a fifth signal;

second pseudo random number generator means for generating a second set of pseudo random number signals in a RNS representation corresponding to said plurality of pseudo random numbers; and

second modular operation means for performing modular arithmetic, said second modular operation means performing modular arithmetic operations, using said fifth signal and said second set of pseudo random number signals as operands, to produce a sixth signal.

20. An encrypter as set forth in claim 19, wherein:

said first modular operation means adds said second signal to said first set of pseudo random number signals; and

said second modular operation means subtracts said second set of pseudo random number signals from said fifth signal.

21. An encrypter as set forth in claim 19, wherein:

said first modular operation means subtracts said second signal from said first set of pseudo random number signals; and

said second modular operation means subtracts said fifth signal from said second set of pseudo random number signals.

22. An encrypter as set forth in claim 19, wherein said second, third, fifth, and sixth signals and said first and second sets of pseudo random number signals are optic signals.

23. An encrypter as set forth in claim 19, wherein said second, third, fifth, and sixth signals and said first and second sets of pseudo random number signals are electronic signals.

24. An encrypter as set forth in claim 19, wherein:

input and output signals to said encrypter are in binary representation; and

said third signal is transmitted in binary representation.

25. An encrypter as set forth in claim 19, wherein:

input and output signals to said encrypter are in binary representation; and

said third signal is transmitted in mixed radix number system representation.