Encrypton system for digital cellular communications
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
69 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
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
- space="preserve" listing-type="equation">W(N)=B+'"'"'K[A+N]
where W(N) is the keyword to be calculated;
N is the sequential position of the particular keyword being calculated within the keyblock;
A is the value of the first one of said discrete bytes of data, B is the second one of said discrete bytes of data;
+ means Exclusive OR, K[A+N] signifies that the Exclusive Or combination of the A and N is to be used as an address in the memory from which to fetch the value of K; and
+'"'"' can either be Exclusive Or or addition modulo the wordlength.
-
- 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
- space="preserve" listing-type="equation">W(N)=B+K[R(A+N)]
where W(N) is the keyword to be calculated;
N is the sequential position of the particular keyword being calculated within the keyblock;
A is the value of the first one of said discrete bytes of data;
B is the second one of said discrete bytes of data, R(A+N) signifies that A+N is the address in a fixed look-up table from which to fetch a value R or that the bits of A+N are to be applied as the inputs of a combinatorial logic block which will give the output R;
+ means Exclusive OR; and
K[R(A+N)] signifies that the value R found in the look-up table at the address of the Exclusive Or combination of A and N is to be used as an address in the memory from which to fetch the value of K.
- space="preserve" listing-type="equation">W(N)=R[A+N]+K[B+N]
N is the sequential position of the particular keyword being calculated within the keyblock;
A is the value of the first one of said discrete bytes of data;
B is the second one of said discrete bytes of data;
R[A+N]) signifies that A+N is the address in a fixed look-up table from which to fetch a value R or that the bits of A+N are to be applied as the inputs of a combinatorial logic block which will give the output R;
+ means Exclusive OR; and
K[B+N] signifies that the address of the Exclusive Or combination of B and N is to be used as an address in the memory from which to fetch the value of K.
-
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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
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
- space="preserve" listing-type="equation">W(N)=B+'"'"'K[A+N]
where W(N) is the keyword to be calculated;
N is the sequential position of the particular keyword being calculated within the keyblock;
A is the value of the first one of said discrete bytes of data;
B is the second one of said discrete bytes of data;
+ means Exclusive OR, K[A+N] signifies that the Exclusive Or combination of the A and N is to be used as an address in the memory from which to fetch the value of K; and
+'"'"' can either be Exclusive Or or addition modulo the wordlength.
-
-
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. - View Dependent Claims (36, 37, 38, 39, 40, 41)
-
-
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. - View Dependent Claims (43, 44, 45, 46, 47, 48, 49, 50, 51, 52)
-
-
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. - View Dependent Claims (54, 55, 56, 57, 58, 59, 60, 61)
-
-
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. - View Dependent Claims (63, 64, 65)
-
-
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. - View Dependent Claims (67, 68, 69)
-
Specification