Method and apparatus for generating a key stream

• US 8,396,212 B2
• Filed: 06/23/2010
• Issued: 03/12/2013
• Est. Priority Date: 01/23/2002
• Status: Expired due to Term

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vadekar, Ashok
• Primary Examiner(s): Gee, Jason
• Application Number:
  US12/821,882
• Publication Number:
  US 20100260335A1
• Time in Patent Office: 993 Days
• Field of Search: 380/44, 380/42
• 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 initializing 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 i, an accumulator j, and a state information table S having state information stored in n entries therein, the method comprising:

a) said correspondent using the counter i, the accumulator j, and the state information table S to;

i) randomly distribute entries of the state information table S by swapping pairs of entries; and

,

ii) generate a pair of non-zero values a and b by, for each swapping pair, adding an entry to a and adding the other entry to b;

b) said correspondent initializing the counter i with a and said correspondent initializing the accumulator j with b;

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

d) said correspondent combining with a current value for the accumulator j, state information identified by entry i in the state information table S to obtain a next value for the accumulator j;

e) said correspondent swapping in said state information table S said state information identified by entry i in the state information table S with state information identified by entry j in the state information table S using said next value for the accumulator j;

f) said correspondent combining the entry i state information with the entry j state information swapped in step d) to generate a combined value t;

g) said correspondent outputting state information identified by entry t in the state information table S as a byte of the key stream; and

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

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

2. The method according to claim 1 wherein the state information table S comprises n entries and computations are performed modulo 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. A correspondent having a key stream generator for generating a key stream, the key stream generator comprising a counter i an accumulator j, and a state information table S having state information stored in n entries therein, said correspondent being configured to perform steps comprising:

a) said correspondent using the counted, the accumulator j, and the state information table S to

i) randomly distribute entries of the state information table S by swapping pairs of entries; and

,

ii) generate a pair of non-zero values a and b by, for each swapping pair, adding an entry to a and adding the other entry to b;

b) said correspondent initializing the counter i with a and said correspondent initializing the accumulator j with b;

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

d) said correspondent combining with a current value for the accumulator j, state information identified by entry i in the state information table S to obtain a next value for the accumulator j;

e) said correspondent swapping in said state information table S said state information identified by entry i in the state information table S with state information identified by entry j in the state information table S using said next value for the accumulator j;

f) said correspondent combining the entry i state information with the entry j state information swapped in step d) to generate a combined value t;

g) said correspondent outputting state information identified by entry t in the state information table S as a byte of the key stream; and

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

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

7. The correspondent according to claim 6 wherein the state information table S comprises n entries and wherein the correspondent performs computations modulo n.

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

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

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

11. A non-transitory 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 i an accumulator j, and a state information table S having state information stored in n entries therein, the computer readable instructions comprising instructions for:

a) said correspondent using the counter i, the accumulator j, and the state information table S to;

i) randomly distribute entries of the state information table S by swapping pairs of entries; and

,

ii) generate a pair of non-zero values a and b by, for each swapping pair, adding an entry to a and adding the other entry to b;

b) said correspondent initializing the counter I with a and said correspondent initializing the accumulator j with b;

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

d) said correspondent combining with a current value for the accumulator j, state information identified by entry i in the state information table S to obtain a next value for the accumulator;

e) said correspondent swapping in said state information table S said state information identified by entry i in the state information table S with state information identified by entry j in the in the state information table S using said next value for the accumulator j;

f) said correspondent combining the entry i state information with the entry j state information swapped in step d) to generate a combined value t;

g) said correspondent outputting state information identified by entry t in the state information table S as a byte of the key stream; and

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

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

12. The computer readable medium according to claim 11 wherein the state information table S comprises n entries and wherein computations in said instructions are performed modulo n.

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

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

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

16. A correspondent in a data communication system comprising:

a) a counter i;

b) an accumulator j;

c) a state information table S having state information stored in n entries therein;

d) means for using the counter i the accumulator j, and the state information table S to;

i) randomly distribute entries of the state information table S by swapping pairs of entries;

ii) generate a pair of non-zero values a and b by, for each swapping pair, adding an entry to a and adding the other entry to b; and

,

c) initialize the counter i with a and to initialize the accumulator j with b;

e) means for combining with a current value for the accumulator j, state information identified by entry i in the state information table S to obtain a next value for the accumulator j;

f) means for swapping in said state information table S said state information identified by entry i in the state information table S using said next value for the accumulator j;

g) means for combining the entry i state information with the entry j state information to generate a combined value t;

h) means for using state information identified by entry t in the state information table S 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 i to generate a next value for said counter i;

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