Variable-key cryptography system

• US 5,619,576 A
• Filed: 04/03/1995
• Issued: 04/08/1997
• Est. Priority Date: 03/14/1994
• Status: Expired due to Fees

• Current Assignee: William Y. Shaw
• Original Assignee: William Y. Shaw
• Inventors: Shaw, William Y.
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/415,719
• Time in Patent Office: 736 Days
• Field of Search: 380/44, 380/45, 380/46, 380/47, 380/21, 380/49, 380/28
• US Class Current: 380/44
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/065 Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3

Abstract

Binary data is encrypted or decrypted using a final key. The final key is formed by manipulating one or more user keys, a base key and a block of data, and combining the manipulated keys and data using an exclusive-OR operation. The data to be encrypted or decrypted are combined with the final key using a circular exclusive-OR operation. A new final key is formed for each block of data. The user and base keys are binary sequences having any number of bits. The user key may be input to the present invention directly in binary form or in any other suitable form that the present invention can interpret as a binary sequence, such as a string of ASCII-encoded alphanumeric characters. Manipulating the user key includes the steps of shuffling or permuting segments of the user key, such as bytes, circularly shifting the permuted user key by a number of bit positions, and filling a location with one or more copies of the permuted and shifted key such that the result has a length equal to that of the base key. The ordering of the segments of the user key in the permutation step and the number of bit positions by which the user key is shifted in the shifting step are determined in response to the value and position of the segments of the user key itself. Manipulating the base key includes the step of circularly shifting the base key by a number of bit positions that is determined in response to the value and position of segments of the user key.

Claims

1. A method for encrypting and decrypting input digital data, comprising the steps of:

providing a first key comprising a sequence of bits;

selecting a plurality of invariant bit positions in response to said first key; and

providing output digital data having in each of said invariant bit positions a bit equal in value to said bit in a corresponding position in said input digital data and having in all other positions bits determined in response to said first key.

2. The method recited in claim 1, further comprising the step of forming an invariant key in response to said input digital data, said invariant key consisting of bits in said invariant bit positions in said input digital data, wherein said output digital data is provided in response to both said user key and said invariant key.

3. The method recited in claim 2, wherein said step of providing output digital data comprises the step of calculating the exclusive-OR of said first key and said invariant key.

4. The method recited in claim 1, wherein said step of providing output digital data comprises the step of calculating the exclusive-OR of said input digital data and a final key.

5. The method recited in claim 1, wherein said step of providing a first key comprises the step of permuting a user key.

6. The method recited in claim 1, wherein said step of providing a first key comprises the step of shifting a user key.

7. A method for encrypting and decrypting digital data, comprising the steps of:

forming an actual user key in response to at least one input user key comprising a sequence of bits;

forming an actual base key comprising a sequence of bits;

forming a semifinal key in response to said actual user key and said actual base key;

determining invariant bit positions in response to said semifinal key;

forming an invariant key in response to said invariant bit positions and a block of said digital data, said invariant key consisting of bits in said invariant bit positions in said block of said digital data;

forming a final key in response to said semifinal key and said invariant key; and

calculating the exclusive-OR of said final key and said digital data.

8. The method recited in claim 7, wherein said step of forming an actual user key comprises the steps of:

permuting said input user key to form a permuted user key;

circularly shifting said permuted user key to form a shifted user key; and

filling a location having a length equal to the length of said base key with said shifted user key to form said actual user key.

9. The method recited in claim 7, wherein said step of forming an actual base key comprises the steps of:

circularly shifting a predetermined base key comprising a sequence of bits; and

permuting said base key in response to said actual user key.

10. The method recited in claim 7, wherein said step of forming a final key comprises the step of calculating the exclusive-OR of said semifinal key and said invariant key.

11. The method recited in claim 8, wherein said step of permuting said input user key comprises the steps of:

selecting two selected portions of said input user key, each said selected portion comprising a sequence of bits, each said selected portion determined in response to the value and position within said input user key of each of a plurality of predetermined portions of said input user key; and

swapping said selected portions of said input user key.

12. The method recited in claim 11, wherein each said portion consists of a byte.

13. The method recited in claim 12, wherein said predetermined portions consist of a plurality of consecutive bytes of said input user key.

14. The method recited in claim 13, wherein said predetermined portions consist of three consecutive bytes of said input user key.

15. The method recited in claim 14, wherein:

said step of selecting two selected portions of said input user key comprises the steps of;

selecting a byte KEY_i of said input user key having an index number equal to i;

selecting a byte KEY_l of said input user key having an index number equal to L; and

said step of permuting said input user key comprises repeating said steps of selecting a byte for values of i between 2 and N-1 inclusive, wherein each byte of said input user key has an index number, wherein N is the length of said input user key in bytes, and wherein;

L=((KEY_i-1 +KEY_i +KEY_i+1 +i)modulo N)+1.

16. The method recited in claim 8, wherein said step of circularly shifting said permuted user key comprises the step of:

circularly shifting said permuted user key by a number of bit positions, said number determined in response to the value and positional weight of each of a plurality of portions of said permuted user key, each said portion comprising a sequence of bits.

17. The method recited in claim 16, wherein said step of circularly shifting said permuted user key by a number of bit positions comprises the steps of:

forming a shift factor S equal to the sum of the values (255+i)*KEY_i for values of i between 1 and N inclusive, wherein KEY is a byte of said user key, wherein each said byte of said user key has an index number, wherein N is the length of said user key in bytes; and

circularly shifting said permuted user key by L bit positions toward the most significant bit position, wherein;

L=(S modulo(N*8))+1.

18. The method recited in claim 7, wherein:

said step of forming an actual user key comprises the steps of;

permuting said input user key to form a permuted user key;

circularly shifting said permuted user key to form a shifted user key; and

filling a location having a length equal to the length of said base key with said shifted user key to form said actual user key;

said step of forming an actual base key comprises the steps of;

circularly shifting a predetermined base key by a number of bit positions determined in response to the value and positional weight of each of a plurality of portions of said permuted user key, each said portion comprising a sequence of bits; and

permuting said circularly shifted base key in response to said actual user key.

19. The method recited in claim 18, wherein said step of circularly shifting said predetermined base key by a number of bit positions comprises the steps of:

forming a shift factor S equal to the sum of the values (255+i)*KEY_i for values of i between 1 and N inclusive, wherein KEY is a byte of said user key, wherein each said byte of said user key has an index number, wherein N is the length of said user key in bytes; and

circularly shifting said predetermined base key by L bit positions toward the most significant bit position;

wherein M is the length of said base key in bytes, and wherein;

L=(S modulo(M*8))+1.

20. The method recited in claim 7, wherein said step of determining invariant bit positions in response to said semifinal key comprises the step of generating byte position indices and bit position indices.

21. The method recited in claim 20, wherein said step of determining invariant bit positions in response to said semifinal key further comprises the step of forming an invariant bit mask.

22. The method recited in claim 7, wherein said step of forming an invariant key comprises the steps of:

selecting bits of said digital data in said invariant bit positions in a block of said digital data having a length equal to the length of said semifinal key; and

copying and appending together the selected bits.

23. The method recited in claim 22, wherein said step of determining invariant bit positions in response to said semifinal key comprises the step of forming an invariant bit mask, said invariant bit mask.

24. The method recited in claim 23 wherein said step of forming an invariant key further comprises the step of circularly filling said invariant bits.

25. The method recited in claim 24, wherein said step of forming a final key comprises the steps of:

forming the exclusive-OR of said semifinal key and said invariant key; and

forming the logical AND of said invariant bit mask and said exclusive-OR of said semifinal key and said invariant key.