Cryptosystem for cellular telephony

• US 5,159,634 A
• Filed: 09/13/1991
• Issued: 10/27/1992
• Est. Priority Date: 09/13/1991
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Reeds, James A. III
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US07/759,309
• Time in Patent Office: 410 Days
• Field of Search: 380/28, 380/37, 380/42, 380/45
• US Class Current: 380/42
• CPC Class Codes: H04K 1/02 by adding a second signal to make the desired signal unintelligible
• CPC Class Codes: H04L 2209/80 Wireless
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A relatively secure, self-inverting, symmetric key cryptosystem designed for efficient implementation on an 8-bit microcomputer. The cryptosystem is especially well suited use in cellular telephony. The method of encryption is comprised of three stages: 1) an autokeyed encryption, 2) the use of a one-time pad encryption where the key is derived from a portion of the message as encrypted by the first stage, and 3) a second autokeyed decryption that is the inverse of the first.

Claims

1. In a communications system, a method of transforming a set of message signals representing a message, the method which includes the steps of

encrypting said set of message signals with an encryption process and a set of key signals to form a set of first intermediate signals,

altering said set of first intermediate signals in accordance with an involutory transformation to form a set of second intermediate signals, and decrypting said set of second intermediate signals with a decryption process which is the inverse of said encryption process to form a set of output signals,

Characterized in that:

said step of altering comprises the step of modifying a first subset of said set of first intermediate signals with an unkeyed transformation based on a second subset of said set of first intermediate signals.

2. The method of claim 1 wherein said step of encrypting comprises the step of forming said set of first intermediat signals in accordance with a first autokey process and said step of decrypting comprises the step of forming said set of output signals in accordance with a second autokey process.

3. The method of claim 1 further comprising the step of deriving said set of key signals from a set of source signals.

4. The method of claim 3 wherein said step of deriving comprises the step of hashing a set of pattern signals with said set of source signals to form said set of key signals.

5. The method of claim 4 wherein said set of key signals and the said set of pattern signals each have N elements, where N is a positive integer.

6. The method of claim 5 wherein said step of deriving comprises the step of making said set of pattern signals available for said step of hashing.

7. The method of claim 1 wherein said set of key signals has N elements and said set of message signals has D elements, where N and D are positive integers.

8. The method of claim 7 wherein said step of emcrypting said set of message signals comprises the steps of:

setting a signal z to a selected magnitude; and

for different integral magnitudes of a signal i, spanning the range 0≦

i<

D,

setting a signal q based on the respective magnitudes of said signals i and z;

setting a signal k based on the respective magnitudes of said signal q and on a signal T, where T is the q^th element of said set of key signals;

creating an i^th element of said set of first intermediate signals based on the respective magnitude of said i^th element of said set of message signals and said signal k; and

updating the magnitude of said signal z based on the respective magnitudes of said i^th element of said set of first intermediate signals and said signal z.

9. The method of claim 7 wherein said step of encrypting said set of message signals comprises the steps of:

setting an n-tet signal z to a selected value; and

for successive integer values of index i, spanning the rang 0 ≦

i<

D,

setting an n-tet signal q to z⊕

m, where ⊕

is the bit-wise boolean Exclusive-OR operator and m is i modulo 2ⁿ ;

setting an n-tet signal k to T, where T is said q^th n-tet element of said set of key signals;

creating an i^th n-tet element of said set of first intermediate signals by adding, modulo 2ⁿ, said i^th n-tet element of said set of message signals and said n-tet signal k; and

updating the value of said n-tet signal z by adding, modulo 2ⁿ, said i^th n-tet element of said set of first intermediate signals and said n-tet signal z.

10. The method of claim 9 wherein each of said n-tets is an eight-tet and 2ⁿ eauals 256.

11. The method of claim 7 wherein said step of altering said set of first intermediate signals creates, in the range ##EQU1## an i^th element of said set of second intermediate signals equal to b(i), ⊕

q, where b(i) is the i^th element of said set of first intermediate signals, where q is based on b(x), where x is based on the values of D and i, where b(x) is the x^th element of said set of first intermediate signals, and where ⊕

is the bit-wise boolean Exclusive-OR operator.

12. The method of claim 7 wherein said step of decrypting said set of second intermediate signals comprises the steps of:

setting a signal z to a selected magnitude; and

for different integral magnitudes of a signal i, spanning the range 0≦

i<

D,

setting a signal q based on the respective magnitudes of said signals i and z;

setting a signal k based on the respective magnitudes of said signal q and on a signal T, where T is the q^th element of said set of key signals;

updating the magnitude of said signal z based on the respective magnitudes of said i^th element of said set of second intermediate signals and said signal z; and

creating an i^th element of said set of output signals based on the respective magnitudes of said i^th element of said set of second intermediate signals and said signal k.

13. The method of claim 7 wherein said step of decrypting said set of second intermediate signals comprises the steps of:

setting an n-tet signal z to a selected magnitude; and

for successive integer values of index i spanning the range 0≦

i<

D,

setting an n-tet signal q to z⊕

m, where ⊕

is the bit-wise boolean Exclusive-OR operator and m is i modulo 2ⁿ ;

setting an n-tet signal k to T, where T is said q^th n-tet element of said set of key signals;

updating the value of said n-tet signal z by adding, modulo 2ⁿ, said i^th n-tet element of said set of second intermediate signals and said signal z; and

creating an i^th n-tet element of said set of output signals by subtracting, modulo 2ⁿ, n-tet signal k from the i^th element of said set of second intermediate signals.

14. The method of claim 12 wherein each of said n-tets is an eight-tet and 2ⁿ equals 256.

15. The method of claim 1 wherein said set of message signals represents a message in a cellular telephone system.

16. The method of claim 1 wherein said set of message signals represent speech.

17. The method of claim 1 wherein said set of message signals represent non-speech data.

18. The method of claim 1 wherein said set of message signals represents a message in a wirless communications system.

19. A cryptographic system for transforming a set of message signals which set represents a message comprising:

means for encrypting said set of message signals with an encryption process and a set of key signals to form a set of first intermediate signals;

means for altering said set of first intermediate signals in accordance with an involutory transformation to form a set of second intermediate signals; and

means for decrypting said set of second intermediate signals with a decryption process which is the inverse of said encryption process to form a set of output signals,

Characterized in that;

said means for altering comprises means for modifying a first subset of said set of first intermediate signals with an unkeyed transformation in accordance with a second subset of said set of first intermediate signals.

20. The communications systems of claim 19 wherein said means for encrypting comprises means for forming said set of first intermediate signals in accordance with a first autokey process and said means for decrypting comprises means for forming said set of output signals in accordance with a second autokey process.

21. The communications system of claim 19 wherein said set of key signals has N elements and said set of message signals had D elements, where N and D are positive integers.

22. The communications system of claim 21 wherein said means for encrypting said set of message signals comprises:

means for setting a signal z to a selected magnitude; and

means for setting a signal i to different integral magnitudes spanning the range 0≦

i<

D,

means for setting a signal q based on the respective magnitudes of said signals i and z;

means for setting a signal k based on the respective magnitudes of said signal q and on a signal K(q), where K(q) is the q^th element of said set of key signals;

means for creating an i^th element of said set of first intermediate signals based on the respective magnitudes of said i^th element of said set of message signals and said signal k; and

means for updating the magnitude of said signal z based on the respective magnitudes of said i^th element of said set of first intermediate signals and said signal z.

23. The communications system of claim 21 wherein said means for altering said set of first intermediate signals creates, in the range ##EQU2## an i^th element of said set of second intermediate signals equal to b(i) ⊕

q, where b(i) is the i^th element of said set of first intermediate signals, where q is based on b(x), where x is based on the values of D and i, where b(x) is the x^th element of said set of first intermediate signals, and where ⊕

is the bit-wise boolean Exclusive-OR operator.

24. The communications system of claim 21 wherein said means for decrypting said set of second intermediate signals comprises:

means for setting a signal z to a selected magnitude; and

means for setting a signal i to different integral magnitudes spanning the range 0≦

i<

D,

means for setting a signal q based on the respective magnitudes of said signals i and z;

means for setting a signal k based on the respective magnitudes of said signal q and on a signal K(q), where K(q) is the q^th element of said set of key signals;

means for updating the magnitude of said signal z based on the respective magnitudes of said i^th element of said set of second intermediate signals and said signal z; and

means for creating an i^th element of said set of output signals based on the respective magnitudes of said i^th element of said set of second intermediate signals and said signal k.