Method and apparatus for generating a key stream

• US 7,769,169 B2
• Filed: 01/23/2003
• Issued: 08/03/2010
• Est. Priority Date: 01/23/2002
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vadekar, Ashok
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): GEE, JASON KAI YIN
• Application Number:
  US10/348,756
• Publication Number:
  US 20030174836A1
• Time in Patent Office: 2,749 Days
• Field of Search: 380/44
• US Class Current: 380/44
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

A method of generating a key stream for a precomputed state information table. The method comprises initialising a counter and an accumulator with non-zero values; combining state information identified by the counter with the accumulator; swapping state information identified by the counter with state information identified by the accumulator; combining the two pieces of state information; outputting the state information identified by the combination as a byte of the key stream; adding a predetermined number odd number to the counter; and repeating the above steps to produce each byte of the key stream.

Claims

1. A method of generating a key stream from a precomputed state information table including state information, said method being performed by a correspondent in a communication system and comprising:

a) initializing a counter and an accumulator with non-zero values by;

i. initializing said counter;

ii. combining with a value of the accumulator state information identified by a value of the counter and key information identified by the value of the counter to obtain another value of the accumulator;

iii. combining state information identified by the value of the counter with a first of said non-zero values;

iv. combining state information identified by said another value of the accumulator with a second of said non-zero values;

v. swapping the state information identified by the value of the counter with the state information identified by the another value of the accumulator;

vi. incrementing the counter to generate another value for the counter; and

vii. repeating steps ii to vi to produce said non-zero values;

b) obtaining a constant odd value, c greater than 1, derived from a publicly available session identifier;

c) combining with a current value for the accumulator state information identified by a current value for the counter to obtain a next value for the accumulator;

d) swapping said state information identified by the current value for the counter with state information identified by said next value for the accumulator;

e) combining with said state information identified by said next value for the accumulator said state information identified by the current value for the counter to generate a combined value;

f) outputting the state information identified by the combined value as a byte of the key stream;

g) combining said odd value c with the current value for the counter to generate a next value for said counter; and

h) repeating steps c) to g) to produce each byte of the key stream.

2. A method according to claim 1, wherein computations are performed modulo a number n.

3. A method according to claim 2, wherein said odd value c is prime relative to n.

4. A method according to claim 2, wherein said combining in steps c, e, and g are additions modulo n.

5. A method according to claim 2 wherein said number n is 256.

6. A method according to claim 3 wherein said number n is 256.

7. A method according to claim 4 wherein said number n is 256.

8. A method according to claim 1 wherein said odd value c is the smallest odd integer larger than or equal to said session identifier.

9. A computer readable storage medium residing on a computer containing instructions for said computer to generate a key stream from a precomputed state information table, the state information table including state information, said instructions comprising instructions for:

a) initializing a counter and an accumulator with non-zero values by;

i. initializing said counter;

ii. combining with a value of the accumulator state information identified by a value of the counter and key information identified by the value of the counter to obtain another value of the accumulator;

iii. combining state information identified by the value of the counter with a first of said non-zero values;

iv. combining state information identified by said another value of the accumulator with a second of said non-zero values;

v. swapping the state information identified by the value of the counter with the state information identified by the another value of the accumulator;

vi. incrementing the counter to generate another value for the counter; and

vii. repeating steps ii to vi to produce said non-zero values;

b) obtaining a constant odd value, c greater than 1, derived from a publicly available session identifier;

c) combining with a current value for the accumulator state information identified by a current value for the counter to obtain a next value for the accumulator;

d) swapping said state information identified by the current value for the counter with state information identified by said next value for the accumulator;

e) combining with said state information identified by said next value for the accumulator said state information identified by the current value for the counter to generate a combined value;

f) outputting the state information identified by the combined value as a byte of the key stream;

g) combining said odd value c with the current value for the counter to generate a next value for said counter; and

h) repeating steps c) to g) to produce each byte of the key stream.

10. A computer readable storage medium according to claim 9 wherein computations are performed modulo a number n.

11. A computer readable storage medium according to claim 10 wherein said odd number is prime relative to n.

12. A computer readable storage medium according to claim 11 wherein said combining in steps c, e, and g are additions modulo n.

13. A computer readable storage medium according to claim 10 wherein said number n is 256.

14. A computer readable storage medium according to claim 11 wherein said number n is 256.

15. A computer readable storage medium according to claim 12 wherein said number n is 256.

16. A key stream generator for generating a key stream, the key stream generator comprising a counter, an accumulator and a precomputed state information table including state information, said key stream generator being configured for generating said key stream from said precomputed state information table by executing computer executable instructions for:

a) initializing a counter and an accumulator with non-zero values by;

i. initializing said counter;

ii. combining with a value of the accumulator state information identified by a value of the counter and key information identified by the value of the counter to obtain another value of the accumulator;

iii. combining state information identified by the value of the counter with a first of said non-zero values;

iv. combining state information identified by said another value of the accumulator with a second of said non-zero values;

v. swapping the state information identified by the value of the counter with the state information identified by the another value of the accumulator;

vi. incrementing the counter to generate another value for the counter; and

vii. repeating steps ii to vi to produce said non-zero values;

b) obtaining a constant odd value, c greater than 1, derived from a publicly available session identifier;

c) combining with a current value for the accumulator state information identified by a current value for the counter to obtain a next value for the accumulator;

d) swapping said state information identified by the current value for the counter with state information identified by said next value for the accumulator;

e) combining with said state information identified by said next value for the accumulator said state information identified by the current value for the counter to generate a combined value;

f) outputting state information identified by the combined value as a byte of the key stream;

g) combining said odd value c with the current value for the counter to generate a next value for said counter; and

h) repeating steps c) to g) to produce each byte of the key stream.

17. A key stream generator according to claim 16 wherein computations are performed modulo a number n.

18. A key stream generator according to claim 16 wherein said odd number is prime relative to n.

19. A key stream generator according to claim 17 wherein said combining in steps c, e, and g are additions modulo n.

20. A key stream generator according to claim 17 wherein said number n is 256.

21. A key stream generator according to claim 18 wherein said number n is 256.

22. A key stream generator according to claim 19 wherein said number n is 256.

23. A key stream generator according to claim 16 wherein said odd value c is the smallest odd integer larger than or equal to said session identifier.