METHOD AND APPARATUS FOR GENERATING A KEY STREAM

• US 20100260335A1
• Filed: 06/23/2010
• Published: 10/14/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
• Granted Patent: US 8,396,212 B2
• Time in Patent Office: Days
• US Class Current: 380/42
• 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, the method being performed by a correspondent in a communication system, the correspondent including a counter, an accumulator, and a table having state information stored therein, the method comprising:

a) said correspondent using the counter, the accumulator, and the state information to generate a pair of non-zero values;

b) said correspondent initializing the counter with a first of the pair of non-zero values and said correspondent initializing the accumulator with a second of the pair of non-zero values;

c) said correspondent obtaining a constant odd value, c, greater than 1;

d) said correspondent 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;

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

f) said correspondent combining the state information swapped in step d) to generate a combined value;

g) said correspondent outputting state information identified by the combined value as a byte of the key stream; and

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

wherein said correspondent repeats steps d) to h) to produce each byte of the key stream.

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

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

4. The method according to claim 2, wherein said combining in steps d, f, and h are additions modulo n.

5. The method according to claim 1 wherein said odd value c is derived from a publicly available session identifier.

6. The method according to claim 1 wherein the correspondent has access to secret key information and wherein step a) comprises:

i. said correspondent initializing said counter;

ii. said correspondent 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. said correspondent combining state information identified by the value of the counter with the first of the pair of non-zero values;

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

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

vi. said correspondent incrementing the counter to generate another value for the counter;

wherein said correspondent repeats steps ii to vi to generate said pair of non-zero values.

7. A correspondent having a key stream generator for generating a key stream, the key stream generator comprising a counter, an accumulator, and a table having state information stored therein, said correspondent being configured to perform steps comprising:

a) said correspondent using the counter, the accumulator, and the state information to generate a pair of non-zero values;

b) said correspondent initializing the counter with a first of the pair of non-zero values and said correspondent initializing the accumulator with a second of the pair of non-zero values;

c) said correspondent obtaining a constant odd value, c, greater than 1;

d) said correspondent 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;

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

f) said correspondent combining the state information swapped in step d) to generate a combined value;

g) said correspondent outputting state information identified by the combined value as a byte of the key stream; and

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

wherein said correspondent is configured to repeat steps d) to h) to produce each byte of the key stream.

8. The correspondent according to claim 7 wherein the correspondent performs computations modulo a number n.

9. The correspondent according to claim 8, wherein said odd value c is prime relative to n.

10. The correspondent according to claim 8, wherein said combining in steps d, f, and h are additions modulo n.

11. The correspondent according to claim 7 wherein said odd value c is derived from a publicly available session identifier.

12. The correspondent according to claim 7 wherein the correspondent has access to secret key information and wherein the correspondent is configured to perform step a) by performing steps comprising:

i. said correspondent initializing said counter;

ii. said correspondent 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. said correspondent combining state information identified by the value of the counter with the first of the pair of non-zero values;

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

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

vi. said correspondent incrementing the counter to generate another value for the counter;

wherein said correspondent is configured to repeat steps ii to vi to generate said pair of non-zero values.

13. A computer readable medium having stored thereon computer readable instructions for performing a method of generating a key stream in a correspondent, the correspondent including a counter, an accumulator, and a table having state information stored therein, the computer readable instructions comprising instructions for:

a) said correspondent using the counter, the accumulator, and the state information to generate a pair of non-zero values;

b) said correspondent initializing the counter with a first of the pair of non-zero values and said correspondent initializing the accumulator with a second of the pair of non-zero values;

c) said correspondent obtaining a constant odd value, c, greater than 1;

d) said correspondent 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;

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

f) said correspondent combining the state information swapped in step d) to generate a combined value;

g) said correspondent outputting state information identified by the combined value as a byte of the key stream; and

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

wherein said instructions further comprise instructions for said correspondent repeating steps d) to h) to produce each byte of the key stream.

14. The computer readable medium according to claim 13 wherein computations in said instructions are performed modulo a number n.

15. The computer readable medium according to claim 14, wherein said odd value c is prime relative to n.

16. The computer readable medium according to claim 14, wherein said combining in steps d, f, and h are additions modulo n.

17. The computer readable medium according to claim 13 wherein said odd value c is derived from a publicly available session identifier.

18. The computer readable medium according to claim 13 wherein the correspondent has access to secret key information and wherein step a) comprises:

i. said correspondent initializing said counter;

ii. said correspondent 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. said correspondent combining state information identified by the value of the counter with the first of the pair of non-zero values;

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

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

vi. said correspondent incrementing the counter to generate another value for the counter;

wherein said instructions further comprise instructions for said correspondent repeating steps ii to vi to generate said pair of non-zero values.

19. A correspondent in a data communication system comprising:

a) a counter;

b) an accumulator;

c) a table having state information stored therein;

d) means for using the counter, the accumulator, and the state information to generate a pair of non-zero values and to initialize the counter with a first of the pair of non-zero values and to initialize the accumulator with a second of the pair of non-zero values;

e) means for 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;

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

g) means for combining the state information identified by the counter and the accumulator to generate a combined value;

h) means for using state information identified by the combined value as a byte of a key stream; and

i) means for combining a constant odd value, c, greater than 1, with the current value for the counter to generate a next value for said counter;

wherein said correspondent is configured to generate the key stream using elements a) to i).