Encrypton system for digital cellular communications

• US 5,148,485 A
• Filed: 05/31/1991
• Issued: 09/15/1992
• Est. Priority Date: 07/20/1990
• Status: Expired due to Term

• Current Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Ericsson GE Mobile Communications Holding, Inc. A Corp. Of New Jersey (Telefonaktiebolaget LM Ericsson)
• Inventors: Dent, Paul
• Primary Examiner(s): SWANN, TOD R
• Application Number:
  US07/708,876
• Time in Patent Office: 473 Days
• Field of Search: 380/23, 380/28, 380/43, 380/44, 380/46, 380/47, 380/48, 380/49, 380/50, 379/59, 379/60, 379/61, 379/62, 379/63, 375/107, 375/110, 375/112, 370/103, 370/105, 370/107, 455/33
• US Class Current: 380/46
• CPC Class Codes: H04L 2209/122 Hardware reduction or efficient architectures
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 63/0457 wherein the sending and receiving network entities apply dynamic encryption, e.g. stream encryption cryptographic mechanisms or cryptographic arrangements for stream encryption H04L9/065
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner
• CPC Class Codes: H04W 12/033 of the user plane, e.g. user's traffic

Abstract

A system for generating a pseudo-random bit sequence which may be used in enciphering digital data prior to transmission or storage of the data. The bit sequence is generated by expanding a plurality of secret key bits in a manner suitable for implementation with a conventional microprocessor arithmetic logic unit (ALU). The system of the present invention may be used, for example, to secure voice or data communications between a base station and a mobile station in a digital cellular communications system.

Claims

1. A method of generating a pseudo-random bit sequence for use in enciphering digital data in which said bit sequence is a function of a plurality of selected key bits, said method comprising:

generating a plurality of multi-bit values each of which is a function of at least some of said selected key bits;

storing each of said plurality of multi-bit values in a discrete location in a memory;

storing each of a plurality of multi-bit values in a look-up table;

generating a sequence of values in a register having a present value at a particular moment by changing the present value contained in said register in response to each cycle of operation;

cyclically calculating a sequence of multi-bit values in accordance with a first preselected algorithm each of which values is a function of at least one of the multi-bit values stored in either said look-up table or in said memory and at least part of the value contained in said register;

cyclically resetting the present value contained in said register with a value obtained as a result of each calculation;

cyclically calculating a multi-bit keyword which is a function of a value obtained as a result of each multi-bit value calculation; and

sequentially combining at least some of said multi-bit keywords into said pseudo-random bit sequence.

2. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 1, wherein said step of generating a plurality of multi-bit values includes generating values which are each a function of all of said selected key bits.

3. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 1, which includes the additional step of periodically initializing the present value contained in said register.

4. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 1, wherein said step of generating a plurality of multi-bit values includes generating values which are each a function of both at least some of said selected key bits and of the value contained in a counter which is periodically incremented in value at a rate which is slow in comparison to the cyclic repetition of said calculations.

5. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 1, wherein said step of generating a sequence of values in a register includes storing a plurality of discrete bytes of data in said register and incrementing only one of said bytes in response to each cycle of operation.

6. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 5, wherein said step of generating a sequence of values in a register includes storing at least three discrete bytes of data in said register and incrementing only one of said bytes in response to each cycle of operation.

7. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 5, wherein said step of calculating a sequence of multi-bit keywords includes making said calculations in accordance with an algorithm in which each calculated value is a function of at least one multi-bit value stored, respectively, at at least one discrete location in said memory and at least one of said discrete bytes of data contained in said register.

8. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 7, wherein said step of calculating a sequence of multi-bit values includes making said calculations in accordance with at least three separate algorithms in which each value calculated with said first algorithm is a function of at least one multi-bit value stored, respectively, at one discrete location in either said memory or in said look-up table and a first one of said discrete bytes of data contained in said register;

each value calculated with said second algorithm is a function of a multi-bit value stored at a discrete location in said look-up table and a second one of said discrete bytes of data contained in said register; and

each value calculated with said third algorithm is a function of the third one of said discrete bytes of data contained in said register and an incremental value added thereto.

9. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 8, wherein said first algorithm is

10. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 9, wherein the look-up table or combinatorial logic which yields the value for the R having a number of output bits which is at least as great as the wordlength of A and less than or equal to the wordlength of B.

11. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 10, wherein

every possible state of input bits to the look-up table maps to a unique output value for R.

12. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 5, wherein said step of generating a sequence of values in a register includes storing at least three discrete bytes of data in said register, said step of calculating a sequence of multi-bit values includes calculating at least three discrete values, and said step of cyclically resetting the present value contained in said register includes replacing each of said at least three discrete bytes of data in said register with respective ones of said at least three discrete calculated values following each calculation step.

13. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 12, wherein said step of cyclically calculating a multi-bit keyword includes selecting at least one of said at least three discrete calculated values as a part of said keyword.

14. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 12, wherein said step of cyclically calculating a multi-bit keyword includes selecting at least one of said at least three discrete calculated values and calculating said keyword in accordance with a second algorithm in which said keyword is a function of said at least one selected calculated value.

15. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 14, which includes the additional step of initializing the value in said register at the beginning of each keyblock of sequential keywords combined into said pseudo-random bit sequence and wherein said second algorithm defines said keyword as a function of at least one of the values calculated in accordance with said first algorithm as well as the sequential position of the particular keyword being calculated within the keyblock.

16. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 14, which includes the additional step of initializing the value in said register at the beginning of each keyblock of sequential keywords and wherein said step of cyclically calculating a multi-bit keyword includes selecting only one of said three discrete calculated values and said second algorithm is

17. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 14, which includes the additional step of initializing the value in said register at the beginning of each keyblock of sequential keywords and wherein said step of cyclically calculating a multi-bit keyword includes selecting only one of said three discrete calculated values and said second algorithm is

18. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 14, which includes the additional step of initializing the value in said register at the beginning of each keyblock of sequential keywords and wherein said step of cyclically calculating a multi-bit keyword includes selecting only one of said three discrete calculated values and said second algorithm is

19. A system for generating a pseudo-random bit sequence for use in enciphering digital data in which said bit sequence is a function of a plurality of selected key bits, said system comprising:

means for generating a plurality of multi-bit values each of which are a function of at least some of said selected key bits;

means for storing each of said plurality of multi-bit values in a discrete location in a memory;

means for storing each of a plurality of multi-bit values at a discrete location in a look-up table;

means for generating a sequence of values in a register having a present value at a particular moment by changing the present value contained in said register in response to each cycle of operation;

means for cyclically calculating a sequence of multi-bit values in accordance with a first preselected algorithm each of which values is a function of at least one of the multi-bit values stored in either said look-up table or in said memory and at least part of the value contained in said register;

means for cyclically resetting the present value contained in said register with a value obtained as a result of each calculation;

means for cyclically calculating a multi-bit keyword which is a function of a value obtained as a result of each multi-bit value calculation; and

means for sequentially combining at least some of said multi-bit keywords into said pseudo-random bit sequence.

20. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 19, wherein said means for generating a plurality of multi-bit values includes means for generating values which are each a function of all of said selected key bits.

21. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 19, which also includes means for periodically initializing the present value contained in said register.

22. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 19, wherein said means for generating a plurality of multi-bit values includes means for generating values which are each a function of both at least some of said selected key bits and of the value contained in a counter which is periodically incremented in value at a rate which is slow in comparison to the cyclic repetition of said calculations.

23. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 19, wherein said means for generating a sequence of values in a register includes means for storing a plurality of discrete bytes of data in said register and means for incrementing only one of said bytes in response to each cycle of operation.

24. A system for generating a pseudo-random bit sequence for use in enchiphering digital data as set forth in claim 23, wherein said means for generating a sequence of values in a register includes means for storing at least three discrete bytes of data in said register and means for incrementing only one of said bytes in response to each cycle of operation.

25. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 23, wherein said means for calculating a sequence of multi-bit keywords includes means for calculating said values in accordance with an algorithm in which each calculated value is a function of at least one multi-bit value stored, respectively, at at least one discrete location in said memory and at least one of said discrete bytes of data contained in said register.

26. A system for generating a pseudo-random bit sequence for use in enchiphering digital data as set forth in claim 25, wherein said means for calculating a sequence of multi-bit values includes means for making said calculations in accordance with three separate algorithms in which each value calculated with said first algorithm is a function of at least one multi-bit value stored, respectively, at at least one discrete location in either said memory or in said look-up table and a first one of said discrete bytes of data contained in said register;

each value calculated with said second algorithm is a function of a multi-bit value stored at a discrete location in said look-up table and a second one of said discrete bytes of data contained in said register; and

each value calculated with said third algorithm is a function of the third one of said discrete bytes of data contained in said register and an incremental value added thereto.

27. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 26, wherein said first algorithm is

28. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 27, wherein the look-up table or combinatorial logic which yields the value for the R having a number of output bits which is at least as great as the wordlength of A and less than or equal to the wordlength of B.

29. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 28, wherein every possible state of input bits to the look-up table maps to a unique output value for R.

30. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 23, wherein said means for generating a sequence of values in a register includes means for storing at least three discrete bytes of data in said register, said means for calculating a sequence of multi-bit values includes means for calculating resetting the present value contained in said register includes means for replacing each of said three discrete bytes of data in said register with respective ones of said at least three discrete calculated values following each calculation step.

31. A system for of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 30, wherein said means for cyclically calculating a multi-bit keyword includes means for selecting at least one of said at least three discrete calculated values as a part of said keyword.

32. A system for of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 30, wherein said means for cyclically calculating a multi-bit keyword includes means for selecting at least one of said at least three discrete calculated values and means for calculating said keyword in accordance with a second algorithm in which said keyword is a function of said at least one selected calculated value.

33. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 32, which also includes means for initializing the value in said register at the beginning of each keyblock of sequential keywords combined into said pseudo-random bit sequence and wherein said second algorithm defines said keyword as a function of at least one of the values calculated in accordance with said first algorithm as well as the sequential position of the particular keyword being calculated within the keyblock.

34. A system for generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 32, which also includes means for initializing the value in said register at the beginning of each keyblock of sequential keywords and wherein said means for cyclically calculating a multi-bit keyword includes means for selecting only one of said three discrete calculated values and said second algorithm is

35. A digital communication system in which the streams of digital data being transmitted and received are cryptographically encoded to provide security of telecommunications, said system comprising:

means for adding a pseudo-random keystream of binary bits to the information carrying digital signal of at least one transmitter and at least one receiver in said system to create streams of digital data to be transmitted and received within said system;

means for generating said pseudo-random keystream of binary bits which includes;

means for storing each of a plurality of multi-bit values in a discrete location;

means for generating a sequence of values in a register by changing the present value contained in said register in response to each cycle of operation;

means for cyclically calculating a sequence of multi-bit values in accordance with a first preselected algorithm each of which values is a function of at least one of said stored multi-bit values and the value contained in said register;

means for cyclically resetting the contents of said register with a value obtained as a result of each calculation;

means for cyclically calculating a multi-bit keyword which is a function of a value obtained as a result of each multi-bit value calculation; and

means for sequentially combining at least some of said multi-bit keywords into said pseudo-random keystream of binary bits.

36. A digital communications system as set forth in claim 35, wherein said means for generating said pseudo-random keystream of binary bits includes means for generating said keystream as a function of a plurality of selected secret key bits, comprising:

means for generating a plurality of multi-bit values each of which are a function of at least some of said selected key bits; and

said means for storing each of a plurality of multi-bit values at a discrete location includes means for storing each of said plurality of generated multi-bit values.

37. A digital communications system as set forth in claim 35, which also includes means for periodically initializing the contents of said register.

38. A digital communications system as set forth in claim 36, wherein said means for generating a plurality of multi-bit values includes means for generating values which are each a function of both at least some of said selected key bits and of the value contained in a counter which is periodically incremented in value at a rate which is slow in comparison to the cyclic repetition of said calculations.

39. A digital cellular communications system as set forth in claim 35, wherein said means for generating a sequence of values in a register includes means for storing a plurality of discrete bytes of data in said register and means for incrementing only one of said bytes in response to each cycle of operation.

40. A digital cellular communications system as set forth in claim 39, wherein said means for generating a sequence of values in a register includes means for storing at least three discrete bytes of data in said register and means for incrementing only one of said bytes in response to each cycle of operation.

41. A digital cellular communications system as set forth in claim 39, wherein said means for calculating a sequence of multi-bit values includes means for calculating said values in accordance with an algorithm in which each calculated value is a function of at least two multi-bit values stored, respectively, at at least two discrete locations in said memory and at least one of said discrete bytes of data contained in said register.

42. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence to be used for enciphering a stream of digital information, said bit sequence being a function of plurality of selected key bits, said method comprising:

storing in memory a set of digital values larger in number than the number of selected key bits and each of which values is a logical function of at least some of said key bits;

iteratively calculating a sequence of multi-bit values with a general purpose microprocessor under program control each of which values is a function of at least one of the digital values stored in memory; and

assembling at least part of said calculated sequence of values into said pseudo-random bit sequence.

43. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence as set forth in claim 42 wherein said step of storing in memory also includes the steps of:

generating a plurality of multi-bit values each of which is a function of at least some of said selected key bits;

storing each of said plurality of multi-bit values in a discrete location in a memory.

44. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence as set forth in claim 43, wherein said step of generating a plurality of multi-bit values includes generating values which are each a function of all of said selected key bits.

45. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence as set forth in claim 43, which also includes the step of:

generating a sequence of values in a register by changing the present value contained in said register in response to each cycle of operation.

46. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence as set forth in claim 45, wherein said step of iteratively calculating a sequence of multi-bit values includes the following steps:

cyclically calculating a sequence of multi-bit values in accordance with a first preselected algorithm each of which values is a function of at least one of the stored digital values and at least part of the value contained in said register;

cyclically resetting the contents of said register with a value obtained as a result of each calculation.

47. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence as set forth in claim 45, which includes the additional step of periodically initializing the contents of said register.

48. A method of reducing the amount of logic hardware needed to generate pseudo-random bit sequence as set forth in claim 43, wherein said step of generating a plurality of multi-bit values includes generating values which are each a function of both at least some of said selected key-bits and of the value contained in a counter which is periodically incremented in value at a rate which is slow in comparison to the cyclic repetition of said calculations.

49. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence as set forth in claim 45, wherein said step of generating a sequence of values in a register includes storing a plurality of discrete bytes of data in said register and incrementing only one of said bytes in response to each cycle of operation.

50. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence as set forth in claim 45, wherein said step of generating a sequence of values in a register includes storing at least three discrete bytes of data in said register and incrementing only one of said bytes in response to each cycle of operation.

51. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence as set forth in claim 45, wherein said step of iteratively calculating a sequence of multi-bit values includes making said calculations in accordance with an algorithm in which each calculated value is a function of at least one of said stored digital values and at least one of said discrete bytes of data contained in said register.

52. A method of reducing the amount of logic hardware needed to generate a pseudo-random bit sequence as set forth in claim 50, wherein said step of iteratively calculating a sequence of multi-bit values includes making said calculations in accordance with at least three separate algorithms in which each value calculated with said first algorithm is a function of at least one of said stored digital values and a first one of said discrete bytes of data contained in said register;

each value calculated with said second algorithm is a function of a stored digital value and a second one of said discrete bytes of data contained in said register; and

each value calculated with said third algorithm is a function of the third one of said discrete bytes of data contained in said register and an incremental value added thereto.

53. A method of generating a pseudo-random bit sequence for use in enciphering digital data, said method comprising:

generating a plurality of multi-bit values;

storing said plurality of multi-bit values at discrete locations;

generating a sequence of values in a register having a present value at a particular moment by changing the present value contained in said register in response to each cycle of operation;

cyclically calculating a sequence of multi-bit values in accordance with a first preselected algorithm each of which values is a function of at least one of said stored multi-bit values and the value contained in said register;

cyclically resetting the present value contained in said register with a value obtained as a result of each multi-bit value calculation;

cyclically calculating a multi-bit keyword which is a function of a value obtained as a result of each multi-bit value calculation;

sequentially combining at least part of said multi-bit keywords into said pseudo-random bit sequence.

54. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 53, wherein said bit sequence is a function of a plurality of selected key bits and which also includes the step of:

generating a plurality of multi-bit values each of which are a function of at least some of said selected key bits; and

wherein said step of storing a plurality of multi-bit values at discrete locations includes storing each of said generated multi-bit values at a discrete location in a memory.

55. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 54, wherein said step of generating a plurality of multi-bit values includes generating values which are each a function of all of said selected key bits.

56. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 53, which includes the additional step of periodically initializing the present value contained in said register.

57. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 54, wherein said step of generating a plurality of multi-bit values includes generating values which are each a function of both at least some of said selected key bits and of the value contained in a counter which is periodically incremented in value at a rate which is slow in comparison to the cyclic repetition of said calculations.

58. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 53, wherein said step of generating a sequence of values in a register includes storing a plurality of discrete bytes of data in said register and incrementing only one of said bytes in response to each cycle of operation.

59. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 58, wherein said step of generating a sequence of values in a register includes storing at least three discrete bytes of data in said register and incrementing only one of said bytes in response to each cycle of operation.

60. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 58, wherein said step of calculating a sequence of multi-bit keywords includes making said calculations in accordance with an algorithm in which each calculated value is a function of at least one multi-bit value stored, respectively, at least one discrete location and at least one of said discrete bytes of data contained in said register.

61. A method of generating a pseudo-random bit sequence for use in enciphering digital data as set forth in claim 59, wherein said step of calculating a sequence of multi-bit values includes making said calculations in accordance with at least three separate algorithms in which each value calculated with said first algorithm is a function of at least one multi-bit value stored, respectively, at one discrete location and a first one of said discrete bytes of data contained in said register;

each value calculated with said second algorithm is a function of a multi-bit value stored at a discrete location and a second one of said discrete bytes of data contained in said register; and

each value calculated with said third algorithm is a function of the third one of said discrete bytes of data contained in said register and an incremental value added thereto.

62. A method of generating cryptographic variables for use in a communications system comprising the steps of:

storing a plurality of multi-bit values in a memory;

initializing a register to a starting multi-bit value; and

iteratively calculating a new value for said register in accordance with an algorithm wherein at least some of the bits of the new register value calculated at each iteration are the result of combining at least some of the bits of the previous register value with at least some of the bits of one of the values stored in said memory.

63. A method according to claim 62 wherein said memory comprises a look-up table.

64. A method according to claim 63 wherein said register comprises a plurality of 8-bit registers and said look-up table containe 256 values.

65. A method according to claim 62 wherein at least some of the values stored in said memory are a function of secret data.

66. A system of generating cryptographic variables comprising:

means for storing a plurality of multi-bit values in a memory;

means for initializing a register to a starting multi-bit value; and

means for iteratively calculating a new value for said register in accordance with an algorithm wherein at least some of the bits of the new register value calculated at each iteration are the result of combining at least some of the bits of the previous register value with at least some of the bits of one of the values stored in said memory.

67. A system according to claim 66 wherein said memory comprises a look-up table.

68. A system according to claim 67 wherein said register comprises a plurality of 8-bit registers and said look-up table contains 256 values.

69. A system according to claim 66 wherein at least some of the values stored in said memory are a function of secret data.