Method and apparatus for generating encryption stream ciphers

• US 6,252,958 B1
• Filed: 10/24/1997
• Issued: 06/26/2001
• Est. Priority Date: 09/22/1997
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Rose, Gregory G.
• Primary Examiner(s): Elmore, Reba I.
• Application Number:
  US08/957,571
• Time in Patent Office: 1,341 Days
• Field of Search: 380/44, 380/28, 380/42, 380/46, 364/724.1, 370/18, 375/1, 371/37, 371/37.1, 371/40.1
• US Class Current: 380/28
• CPC Class Codes: G09C 1/00 Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system cryptographic typewriters G09C3/00
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 9/0668 producing a non-linear pseudorandom sequence
• CPC Class Codes: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Abstract

A method and apparatus for generating encryption stream ciphers. The recurrence relation is designed to operate over finite fields larger than GF(2) and is maximal length. An output equation generates the output based on a plurality of elements in the shift register used to implement the recurrence relation. The recurrence relation and the output equation are selected to have distinct pair distances such that, as the shift register shifts, no particular pair of elements of the shift register are used twice in either the recurrence relation or the output equation.

Claims

1. A method for generating a stream cipher comprising:

selecting a finite field having an order greater than one;

selecting a recurrence relation over said finite field;

selecting an output equation;

computing said stream cipher in accordance with said recurrence relation and said output equation; and

wherein said recurrence relation and said output equation have distinct pair distances.

2. The method of claim 1 wherein said finite field is selected based on a word size of a processor used to compute said stream cipher.

3. The method of claim 1 wherein said finite field is a Galois field comprising 256 elements.

4. The method of claim 1 wherein said recurrence relation is maximal length.

5. The method of claim 1 wherein said recurrence relation has an order of 17.

6. The method of claim 1 wherein said recurrence relation is defined as S_n+17=141S_n+15⊕

S_n+4⊕

175S_n, where operations are defined over GF(2⁸), ⊕

is an exclusive-OR operation on two bytes, and is a polynomial modular multiplication.

7. The method of claim 1 wherein said stream cipher comprises up to 128-bit key material.

8. The method of claim 1 wherein said recurrence relation is implemented with a linear feedback shift register.

9. The method of claim 8 wherein said linear feedback shift register is implemented with a circular buffer.

10. The method of claim 8 wherein said linear feedback shift register is implemented with a sliding window.

11. The method of claim 1 wherein said computing step is further performed in accordance with at least one non-linear process.

12. The method of claim 11 wherein said at least one non-linear process comprises stuttering a shift register used to implement said recurrence relation.

13. The method of claim 12 wherein said stuttering is performed in accordance with said stream cipher.

14. The method of claim 1 wherein said at least one non-linear process comprises computing a non-linear function of a state of said generator.

15. The method of claim 1 wherein said at least one non-linear process comprises bit inversion of selected bits of said stream cipher.

16. The method of claim 15 wherein said bit inversion is performed in accordance with a set of constants having a Hamming distance chosen to invert half of the bits in said stream cipher.

17. The method of claim 1 wherein said computing step comprises modulo addition.

18. The method of claim 1 further comprising the step of:

initializing said generator with a secret key.

19. The method of claim 18 wherein said initializing step comprises the steps of:

adding a least significant byte of said secret key to said recurrence relation;

shifting said secret key by one byte; and

repeating said adding step and said shifting steps until all bytes in said secret key are added to said recurrence relation.

20. The method of claim 18 wherein a length of said secret key is less than an order of said recurrence relation.

21. The method of claim 18 further comprising the step of:

initializing said generator with a per frame key.

22. The method of claim 21 wherein a length of said per frame key is four octets long.

23. The method of claim 21 wherein said initializing said generator with a per frame key step is performed for each data frame.

24. The method of claim 21 wherein said initializing said generator with a per frame key step comprises the steps of:

adding a least significant byte of said per frame key to said recurrence relation;

shifting said per frame key by three bits;

repeating said adding step and said shifting steps until all bytes in said per frame key are added to said recurrence relation.

25. The method of claim 24 wherein said initializing said generator with a per frame key step further comprises the step of:

adding said least significant byte of said per frame key to a most significant byte of said per frame key.

26. An apparatus for generating a stream cipher, comprising a processor for receiving instructions for performing a recurrence relation and an output equation, said processor performing manipulations on elements in accordance with said instructions, wherein said recurrence relation and said output equation have distinct pair distances, and wherein said recurrence relation is defined over a finite field having an order of greater than one.

27. The apparatus of claim 26 wherein said finite field is selected based on a word size of said processor.

28. The apparatus of claim 26 wherein said finite field is a Galois field comprising 256 elements.

29. The apparatus of claim 26 wherein said recurrence relation is maximal length.

30. The apparatus of claim 26 wherein said recurrence relation has an order of 17.

31. The apparatus of claim 26 wherein said processor provides a stream cipher comprising 128-bit key material.

32. The apparatus of claim 26 wherein said recurrence relation is implemented with a linear feedback shift register.