High speed encryption system and method

• US 5,365,588 A
• Filed: 03/12/1993
• Issued: 11/15/1994
• Est. Priority Date: 03/12/1993
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (Rtx Corporation)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Mayhew, Gregory L., Bianco, Mark E.
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/030,687
• Time in Patent Office: 613 Days
• Field of Search: 380/42, 380/49, 380/50
• US Class Current: 380/42
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/0668 producing a non-linear pseudorandom sequence
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner

Abstract

A general purpose, high-speed encryption system and method, based on a linear feedback shift register (LFSR) that provides inputs to one or more mathematically independent nonlinear output functions, resulting in the generation of multiple keystream outputs per clock cycle. Due to the parallel architecture, the system need only operate at a rate of 1/N, where N is the number of output functions. For example, the system can encrypt an 8-bit byte in one-eighth the time required for a conventional bit-oriented stream cipher. Alternatively, with high-speed serial-to-parallel and parallel-to-serial interface converters, the system can encrypt a serial data stream at a rate N times that of the system itself.

Claims

1. A high speed data encryption system for encrypting input data to produce encrypted data, comprising:

a working register, comprising a linear feedback shift register having a plurality of stages including an output stage and a plurality of intermediate stages;

means for initializing the working register by loading it with a binary sequence;

means for selectively feeding back the output state of said output stage of said working register into selected inputs of said intermediate stages, as determined by a cryptographic key;

N mathematical independent nonlinear output function means, where N≧

2, each for performing a different nonlinear function on the output states of T selected stages of said working register, where T≧

1;

means for clocking said working register, wherein with each clock cycle, said working register is advanced one state, and the outputs of said selected working register stages feed said N output function means; and

means for logically operating on respective input data bits and said outputs of said output function means to produce encrypted data.

2. The system of claim 1 wherein said N sets of T stages of said working register are randomly selected stages.

3. The system of claim 1 wherein said N output function means comprise N means programmed with nonlinear functions with random properties to map said respective working register stage outputs into N corresponding nonlinear outputs of said N output function means.

4. The system of claim 3 wherein said N means programmed with nonlinear functions comprises read only memory means having said nonlinear functions stored therein.

5. The system of claim 3 wherein said nonlinear functions comprise nonlinear de Bruijn sequences.

6. The system of claim 1 wherein said logical operating means comprises means for performing a logical XOR function.

7. The system of claim 6 wherein said means for performing a logical XOR function comprises a modulo-2 digital adder.

8. The system of claim 1 further comprising a key shift register comprising a plurality of cascaded register stages, and means for loading said key register with said cryptographic key.

9. The system of claim 1 wherein said binary sequence comprises a randomly generated binary sequence.

10. The system of claim 1 wherein said binary sequence comprises a pseudorandomly generated binary sequence.

11. A high speed data encryption system for encrypting input data to produce encrypted data, comprising:

a key shift register having a plurality of cascaded register stages;

means for loading said key register with a cryptographic binary data sequence;

a working register, comprising a linear feedback shift register having a plurality of stages including an output stage and a plurality of intermediate stages;

means for initializing the working register by loading it with a binary sequence;

means for selectively feeding back the output state of said output stage of said working register into selected inputs of said intermediate stages, as determined by the contents of said key register;

N mathematically independent nonlinear output function means for performing N different nonlinear functions on data input to said function means, where N≧

2;

means for feeding the output states of N sets of T stages of said working register into respective inputs of said N output function means, where T≧

1;

means for clocking said working register, wherein with each clock cycle, said working register is advanced one state, and said N sets of T working register stage outputs feed said N output function means; and

means for performing a logical XOR function on respective input data bits and said outputs of said output function means to produce encrypted data.

12. The system of claim 11 wherein said N sets of T stages of said working register are randomly selected stages.

13. The system of claim 11 wherein said N output function means comprise N means programmed with nonlinear functions with random properties to map said respective working register stage outputs into N corresponding nonlinear outputs of said N output function means.

14. The system of claim 13 wherein said N means programmed with nonlinear functions comprises read only memory means having said nonlinear functions stored therein.

15. The system of claim 13 wherein said nonlinear functions comprise nonlinear de Bruijn sequences.

16. The system of claim 11 wherein said means for performing a logical XOR function comprises modulo-2 digital adder means.

17. The system of claim 11 wherein said working register has W stages, and said key register has W-1 stages to accommodate said working register.

18. The system of claim 11 wherein said means for selectively feeding back the output state of said output stage comprises:

a plurality of logical AND gate means, each gate means having a first input coupled to a corresponding output of a register stage of said key register and a second input coupled to the output of said output stage of said working register; and

an XOR gate means disposed between each stage of said working register, one input of each said gate means coupled to the output of the preceding stage of said working register, and a second input of each said XOR gate means coupled to the output of a corresponding logical AND gate means,

whereby the output of said output stage is selectively fed back into said intermediate stages of said working register in dependence on the respective states of said registers comprising said key register.

19. The system of claim 11 wherein said input data is arranged in 8-bit bytes, the number N of said output function means and said stages whose output states are fed into respective inputs of said output function means is eight, and said means for performing a logical XOR function comprises an 8-bit modulo-2 adder means.

20. The system of claim 11 wherein said means for initializing said working register comprises a multiplexer means having an output coupled to the input of a first of said stages of said working register, a first input connected to a source of said binary sequence, and a second input connected to the output of said working register output stage, said multiplexer providing a means for connecting said input stage of said working register to said source of said binary sequence during an initializing mode, and for connecting said output stage of said working register to said input stage during an encryption mode.

21. The system of claim 11 wherein said binary sequence comprises a randomly generated binary sequence.

22. The system of claim 11 wherein said binary sequence comprises a pseudorandomly generated binary sequence.

23. A method for high speed encryption of digital input data, comprising a sequence of the following steps:

providing a cryptographic key binary data sequence;

providing a working register comprising a linear feedback shift register having a plurality of stages including an output stage and a plurality of intermediate stages;

initializing the working register with a binary sequence;

selectively feeding back the output stage of said output stage into selected intermediate stages, as determined by said cryptographic key sequence;

operating on the outputs of N set of T stages of said working register with N respective mathematically independent nonlinear output functions to provide N output keystreams, where N≧

2 and where T≧

1;

logically operating on N bits of input data with N output keystreams to provide encrypted data; and

clocking said working register stages at a selected clock rate, wherein said working register is advanced by one state, and N bits of input data are encrypted during each clock cycle.

24. The method of claim 23 wherein said N sets of T working register stages are selected randomly.

25. The method of claim 23 wherein said output functions have random properties.

26. The method of claim 25 wherein said output functions are determined by nonlinear de Bruijn sequences.

27. The method of claim 23 wherein said logical operating step includes the step of logically XORing input data bits with corresponding bits of said N output key-streams.

28. The method of claim 23 further comprising the steps of providing a key shift register comprising a plurality of cascaded register stages, filling the shift register stages with said key sequence, and using the states of the shift register stages to logically determine whether the state of the working register output stage is fed back into said intermediate stages.

29. The method of claim 23 wherein the number N is eight.

30. The method of claim 23 wherein said binary sequence comprises a randomly generated binary sequence.

31. The method of claim 23 wherein said binary sequence comprises a pseudorandomly generated binary sequence.

32. A high speed data decryption system for decrypting input ciphertext data to produce decrypted data, comprising:

a working register, comprising a linear feedback shift register having a plurality of stages including an output stage and a plurality of intermediate stages;

means for initializing the working register by loading it with a binary sequence;

means for selectively feeding back the output state of said output stage of said working register into selected inputs of said intermediate stages, as determined by a cryptographic key;

wherein said binary sequence and said cryptographic key corresponds to a respective binary sequence and a cryptographic key used to encrypt said ciphertext;

N mathematically independent nonlinear output function means, where N≧

2, each for performing a different nonlinear function on the output states of T selected stages of said working register, where T≧

1;

means for clocking said working register, wherein with each clock cycle, said working register is advanced one state, and the outputs of said selected working register stages feed said N output function means; and

means for logically operating on respective input data bits and said outputs of said output function means to produce decrypted data from said ciphertext.

33. The system of claim 32 wherein said N sets of T stages of said working register are randomly selected stages.

34. The system of claim 32 wherein said N output function means comprise N means programmed with nonlinear functions with random properties to map said respective working register stage outputs into N corresponding nonlinear outputs of said N output function means.

35. The system of claim 34 wherein said N means programmed with nonlinear functions comprises read only memory means having said nonlinear functions stored therein.

36. The system of claim 34 wherein said nonlinear functions comprise nonlinear de Bruijn sequences.

37. The system of claim 32 wherein said logical operating comprises means for performing a logical XOR function.

38. The system of claim 37 wherein said means for performing a logical XOR function comprises a modulo-2 digital adder.

39. The system of claim 32 further comprising a key shift register comprising a plurality of cascaded register stages, and means for loading said key register with said cryptographic key.

40. The system of claim 32 wherein said binary sequence comprises a randomly generated binary sequence.

41. The system of claim 32 wherein said binary sequence comprises a pseudorandomly generated binary sequence.

42. A method for high speed decryption of digital input ciphertext data, comprising a sequence of the following steps:

providing a cryptographic key binary data sequence corresponding to a cryptographic key sequence used to generate said ciphertext data;

providing a working register comprising a linear feedback shift register having a plurality of stages including an output stage and a plurality of intermediate stages;

initializing the working register with a binary sequence, said binary sequence corresponding to a binary sequence used to generate said ciphertext data;

selectively feeding back the output state of said output stage into selected intermediate stages, as determined by said cryptographic key sequence;

operating on the outputs of N set of T stages of said working register with N respective mathematically independent nonlinear output functions to provide N output keystreams, where N≧

2 and where T≧

1;

logically operating on said N bits of input data with N output keystreams to provide decrypted data; and

clocking said working register stages at a selected clock rate, wherein said working register is advanced by one state, and N bits of input data are decrypted during each clock cycle.

43. The method of claim 42 wherein said N sets of T working register stages are selected randomly.

44. The method of claim 42 wherein said output functions have random properties.

45. The method of claim 42 wherein said output functions are determined by nonlinear de Bruijn sequences.

46. The method of claim 42 wherein said logical operating step includes the step of logically XORing input data bits with corresponding bits of said N output key-streams.

47. The method of claim 42 further comprising the steps of providing a key shift register comprising a plurality of cascaded register stages, filling the shift register stages with said key sequence, and using the states of the shift register stages to logically determine whether the state of the working register output state is fed back into said intermediate stages.

48. The method of claim 42 wherein said binary sequence comprises a randomly generated binary sequence.

49. The method of claim 42 wherein said binary sequence comprises a pseudorandomly generated binary sequence.