Variable-key cryptography system

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

I claim:

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.sub.i of said input user key having an index number equal to i;

selecting a byte KEY.sub.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.sub.i-1 +KEY.sub.i +KEY.sub.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.sub.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.sub.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.

Description

BACKGROUND OF THE INVENTION

The present-invention relates to cryptography and, more specifically, to a system for encrypting and decrypting digital data using one or more equally weighted variable-length keywords.

Cryptography may be used to provide secure communication or storage of digital data such as voice, facsimile (FAX), electronic mail, credit card information, and television. Practitioners in the art have developed encryption algorithms, such as the Data Encryption Standard (DES). These algorithms require a user to enter a keyword to either encrypt or decrypt the data. Data encrypted using a given keyword can only be decrypted by using the same keyword. DES requires that the keyword be exactly six alphanumeric characters in length. The essence of the DES algorithm is a complex decision tree that alters the states of data bits in response not only to the key but also to the results of logical operations that it performs on groups of data bits. Encryption or decryption is very slow because these calculations take a large amount of time and must be performed sequentially.

Analog cryptographic systems are used to provide secure video transmissions over microwave links and cable television lines. These systems must operate at high speeds to accommodate video bandwidths.

It would be desirable to provide a cryptographic system that does not restrict the user's choice of key length and that operates fast enough to be used in real-time video and voice environments. These problems and deficiencies are clearly felt in the art and are solved by the present invention in the manner described below.

SUMMARY OF THE INVENTION

The present invention comprises a method and apparatus for encrypting and decrypting digital data. The method comprises the steps of manipulating a user key and a base key, forming the exclusive-OR of the manipulated keys to produce a final key, and forming the exclusive-OR of the final key and the data to be encrypted or decrypted.

The user and base keys are binary sequences having any suitable number of bits. The maximum length of the keys is limited only by the physical capabilities of the software and/or hardware of the system in which the present invention is embodied. The base key may be stored in a manner that allows it to be retrieved, but need not be stored in a manner that allows it to be altered. Although the base key remains accessible, the user key is not retained in its original form after it is input. The user key may be input to the hardware employing 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 an ASCII-encoded character string. ASCII-encoded strings consisting of a few characters or consisting of hundreds of pages of text may be suitable as user or base keys if the system hardware and/or software are adapted for manipulating such keys. Data may be encrypted or decrypted using multiple user keys to provide additional security, as described below.

The hardware employing the present invention may communicate data to be encrypted or decrypted with any suitable device, such as a computer system, a telephone network, or a wireless communication network. Because manipulation of the keys to form the final key may be performed at any time before data communication occurs, the only step that must be performed in real-time, i.e, during data communication, is the exclusive-OR between the final key and the data. This minimization of real-time operations maximizes encryption and decryption speed.

Manipulating the user key comprises the steps of permuting the user key, circularly shifting the permuted user key, and filling a memory 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 permutation step shuffles segments of the key in a pseudorandom manner in response to the value and position of segments of the user key. The circular shifting step rotates or shifts the binary sequence by a number of bit positions that is determined in response to the value and position of segments of the permuted user key. In an illustrative embodiment that is adapted for manipulating user keys consisting of ASCII character strings, each segment may consist of one byte. The value of each such segment is thus the ASCII value of the character. The filling step may extend the length of the permuted and shifted user key to equal that of the base key if the base key is longer than the user key by copying the permuted and shifted user key into a location one or more times and appending the copies to each other.

Manipulating the base key comprises 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.

The manipulated user and base keys are combined using an exclusive-OR operation. To provide additional security, this semifinal key may be further combined using an exclusive-OR operation with a number that is determined in response to the value and position of segments of the user key. The result of the latter exclusive-OR operation is the final key. Alternatively, to provide additional security, the semifinal key may be used as a pseudorandom basis for selecting certain bits of the data to be encrypted or decrypted. The selected or "invariant" bits remain unchanged after encryption or decryption.

The present invention performs an exclusive-OR operation between the final key and the data to be encrypted or decrypted. If the data stream is longer than the final key, the final key may be recirculated.

If multiple user keys are used, each user key is permuted and combined with all other permuted user keys using an exclusive-OR operation. It should be noted that the order in which the user keys are input and combined is irrelevant due to the associative property of the exclusive-OR operation. If multiple user keys are used, the above-described step of circularly shifting the user key operates on the combined user key.

The present invention does not restrict the user's choice of key length. Furthermore, after performing the initial key manipulation, encryption and decryption speed is limited only by the speed at which the exclusive-OR operation can be performed. This operation can be performed by relatively simple hardware or software. The present invention also does not propagate any data errors that may occur. If one or more bits of the data to be encrypted or decrypted are in error, the exclusive-OR operation does not increase the number of such bits. Furthermore, unique systems can be created by providing unique base keys. Information encrypted from a system having a certain base key cannot be decrypted by a system having a different base key even if the user keys input to the two systems are identical.

The foregoing, together with other features and advantages of the present invention, will become more apparent when referring to the following specification, claims, and accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

For a more complete understanding of the present invention, reference is now made to the following detailed description of the embodiments illustrated in the accompanying drawings, wherein:

FIG. 1 is a block diagram of a circuit for encrypting and decrypting digital data;

FIG. 2 is a flow diagram of an algorithm for encrypting and decrypting digital data; and

FIG. 3 is a flow diagram of an alternative algorithm for encrypting and decrypting digital data.

DESCRIPTION OF A PREFERRED EMBODIMENT

As illustrated in FIG. 1, an exclusive-OR circuit 10 combines data to be encrypted or decrypted with a final key using an exclusive-OR operation. Circuit 10 receives the data from an interface circuit 12 that is connected to an external device 13, such as a computer. Circuit 10 receives the final key from a mask memory 14 that is addressed by an address counter 16. A processor 18, which has program memory 20, calculates the final key in the manner described below under control of a program stored in memory 20. Interface 12, circuit 10, address counter 16 and processor 18 are interconnected via control logic 22.

When it is desired to encrypt or decrypt data, processor 18 receives a user key via interface 12. For example, a user may enter the user key on a keyboard (not shown) connected to external device 13. Processor 18 combines the actual user key with a base key, which may be pre-stored in processor memory 20, in the manner described below under control of the program stored in memory 20. Processor 18 stores the final key in mask memory 14. When exclusive-OR circuit 10 receives data to be encrypted or decrypted via interface 12, address counter 16 is incremented to retrieve successive portions of the final key from mask memory 10. For example, if interface 10 is connected to a computer that reads and writes one byte at a time, address counter 16 may increment each time the computer performs a write operation to interface 12 in order to retrieve the next byte of the final key from memory 14. The computer can immediately perform a read operation to interface 12 to retrieve the encrypted or decrypted byte. Each byte of the final key is thus exclusive-OR'd with one byte of the incoming data. If the incoming data contains more bytes than the final key, this exclusive-OR process is repeated beginning at the first byte of the final key in a circular manner.

Processor 18 may perform the algorithm illustrated in FIG. 2 when a user desires to encrypt or decrypt data. At step 24 processor 18 initializes variables representing an input user key and an actual user key by setting them to zero. At step 26 processor 18 reads an input user key from the computer keyboard or other device connected via interface 12, as described above. The input user key is a digital word that may have any length greater than or equal to a predetermined minimum and less than a predetermined maximum. The maximum user key length is equal to the length of the base key, as discussed below. A user can more easily remember a key that is represented by a string of alphanumeric characters than, for example, a string of binary digits or hexadecimal digits. Therefore, in an illustrative embodiment, the key is represented by a string of ASCII-encoded characters. Each character is one byte, and processor 18 performs all mathematical operations on the basis of a wordlength of one byte. However, in other embodiments the user key can be received in any format that can ultimately be represented as a binary number, and mathematical operations may be performed on the basis of other suitable wordlengths.

For example, the minimum user key length may be five bytes, i.e., five characters. A user may thus enter the character string "IBAInc". These six characters can also be represented in ASCII by the string of hexadecimal numbers:

"49 42 41 49 6E 63".

At step 28 processor 18 packs the input user key. A user key having varying bits is preferred because such a user key provides more secure encryption. In the illustrated example, which uses a wordlength of one byte, processor 18 packs the input user key by removing any bytes having a value equal, in hexadecimal notation, equal to "00" or "FF". The remaining bytes are moved in a direction from the less significant bytes toward the more significant bytes (leftward in the drawing) to close up the space previously occupied by the bytes that were removed.

At step 30 processor 18 tests whether the packed input user key has a length greater than the predetermined minimum. For example, the packing step would not alter the input user key "IBAInc", and the length remains six, which is greater than the predetermined minimum of five. Processor 18 therefore proceeds to step 32. However, if processor 18 determines that the packed user key has a length less than the minimum, processor 18 returns to step 26, which requires that the user re-enter the input user key.

At step 32 processor 18 determines the number of unique bytes in the packed input user key. A unique byte is a byte that is different from every other byte. The number of unique bytes in the packed key "IBAInc" is five because the byte representing the character "I" appears twice. At step 34 processor 18 tests whether the number of unique bytes is greater than a predetermined minimum. For example, the minimum may be five, and processor 18 therefore proceeds to step 36. However, if processor 18 determines that the number of unique bytes in the packed input user key is less than the minimum, processor 18 returns to step 26, which requires that the user re-enter the input user key.

At step 36 processor 18 permutes the packed input user key. Permuting the user key shuffles the bytes in a pseudorandom manner in response to the value and positional weight of the bytes. Each byte may be swapped with another byte. The permutation step can be expressed as follows, where the packed input user key is represented by the variable KEY, the ith byte of KEY is represented by KEY.sub.i, and N is the length of KEY in bytes:

L=((KEY.sub.i-1 +KEY.sub.i +KEY.sub.i+1 +i)modulo N)+1.

For i=2, 3, 4, . . . N-1, swap KEY.sub.i with KEY.sub.L.

For example, to permute the input user key "IBAInc" processor 18 performs four swaps: First, when i equals 2, L equals 3, which is 206 modulo 6, plus 1. Processor 18 swaps the second and third bytes of "IBAInc", yielding "IABInc". The number 206 is the sum of KEY.sub.1, which is represented by the decimal number 73, KEY.sub.2, which is represented by the decimal number 66, KEY.sub.3, which is represented by the decimal number 65, and i, which is two. Second, when i equals 3, L equals 4, which is 207 modulo 6, plus 1. Processor 18 swaps the third and fourth bytes of "IABInc", yielding "IAIBnc". The number 207 is the sum of KEY.sub.2, which is represented by the decimal number 65, KEY.sub.3, which is represented by the decimal number 66, KEY.sub.4, which is represented by the decimal number 73, and i, which is three. Third, when i equals 4, L equals 2, which is 253 modulo 6, plus 1. Processor 18 swaps the fourth and second bytes of "IAIBnc", yielding "IBIAnc". The number 253 is the sum of KEY.sub.3, which is represented by the decimal number 73, KEY.sub.4, which is represented by the decimal number 66, KEY.sub.5, which is represented by the decimal number 110, and i, which is four. Fourth, when i equals 5, L equals 4, which is 279 modulo 6, plus 1. Processor 18 swaps the fifth and fourth bytes of "IBIAnc", yielding "IBInAc". The number 279 is the sum of KEY.sub.4, which is represented by the decimal number 65, KEY.sub.5, which is represented by the decimal number 110, KEY.sub.6, which is represented by the decimal number 99, and i, which is five.

At step 38 processor 18 exclusive-ORs the packed and permuted input user key into the actual user key. An actual user key may comprise multiple input user keys that are combined using an exclusive-OR operation. For example, the actual user key was set to zero at step 24, and after exclusive-ORing the actual user key with the packed and permuted input user key "IBInAc", the actual user key becomes "IBInAc".

At step 40 processor 38 tests whether another user key is to be input. Processor 38 may receive a suitable command via interface 12 to indicate this. If processor 18 receives an indication that another user key is to be input, processor 18 proceeds to step 26 to receive the next input user key. If processor 38 receives an indication that no additional user keys are to be input, processor 18 proceeds to step 40. In the present example, "IBAInc" is the sole user key. Therefore, "IBInAc" is the actual user key.

At step 42 processor 18 packs the actual user key in the same manner as that described above with respect to step 28. At step 44 processor 18 tests whether the packed actual user key has a length greater than a predetermined minimum, which preferably has the same value as the predetermined minimum described above with respect to step 30. For example, the packing step would not alter the actual user key "IBInAc", and the length remains six, which is greater than the predetermined minimum of five. Processor 18 therefore proceeds to step 46. However, if processor 18 determines that the packed user key has a length less than the minimum, processor 18 returns to step 24, which requires that the user re-enter all input user keys.

At step 46 processor 18 determines the number of unique bytes in the packed actual user key in the same manner as that described above with respect to step 32 and, at step 48, tests whether the number of unique bytes is greater than a predetermined minimum, which is preferably the same minimum as that described above with respect to step 34. For example, since no additional input user keys are combined with the initial input user key "IBAInc", the number of unique bytes remains five. Processor 18 therefore proceeds to step 50. However, if processor 18 determines that the number of unique bytes in the packed actual user key is less than the minimum, processor 18 returns to step 24, which requires that the user re-enter all input user keys.

At step 50 processor 18 permutes the packed actual user key in the same manner as that described above with respect to step 36. For example, to permute the actual user key "IBInAc" processor 18 performs four swaps: First, when i equals 2, L equals 5, which is 214 modulo 6, plus 1. Processor 18 swaps the second and fifth bytes of "IBInAc", yielding "IAInBc". The number 214 is the sum of KEY.sub.1, which is represented by the decimal number 73, KEY.sub.2, which is represented by the decimal number 66, KEY.sub.3, which is represented by the decimal number 73, and i, which is two. Second, when i equals 3, L equals 6, which is 251 modulo 6, plus 1. Processor 18 swaps the third and sixth bytes of "IAInBc", yielding "IAcnBI". The number 251 is the sum of KEY.sub.2, which is represented by the decimal number 65, KEY.sub.3, which is represented by the decimal number 73, KEY.sub.4, which is represented by the decimal number 110, and i, which is three. Third, when i equals 4, L equals 4, which is 279 modulo 6, plus 1. Processor 18 swaps the fourth byte of "IAIBnc" with itself, yielding "IAIBnc". The number 279 is the sum of KEY.sub.3, which is represented by the decimal number 99, KEY.sub.4, which is represented by the decimal number 110, KEY.sub.5, which is represented by the decimal number 66, and i, which is four. Fourth, when i equals 5, L equals 3, which is 254 modulo 6, plus 1. Processor 18 swaps the fifth and third bytes of "IAIBnc", yielding "IABncI". The number 254 is the sum of KEY.sub.4, which is represented by the decimal number 110, KEY.sub.5, which is represented by the decimal number 66, KEY.sub.6, which is represented by the decimal number 73, and i, which is five.

At step 52 processor 18 determines a shift factor in response to the value and positional weight of the bytes. The shift factor, S, can be expressed as follows, where the permuted actual user key is represented by the variable KEY, the ith byte of KEY is represented by KEY.sub.i, and N is the length of KEY in bytes:

Let S=0 initially.

For i=1, 2, 3, . . . N, increment S by (255+i)*KEY.sub.i.

For example, if the permuted actual user key is "IABncI", processor 18 sums the value 18688, which is (255+1)*73, the value 16705, which is (255+2)*65, the value 17028, which is (255+3)*66, the value 17028, which is (255+3)*66, the value 28490, which is (255+4)*110, the value 25740, which is (255+5)*99, and the value 19053, which is (255+6)*73. The sum is equal to 125704, which is the shift factor S.

At step 54 processor 18 circularly shifts the bits of the permuted actual user key in a direction from the less significant bits toward the more significant bits (leftward in the drawing). (The shift is circular because a bit occupying the most significant position is shifted to the least significant position.) The number of places by which the permuted actual user key is shifted is equal to the shift factor modulo the length of the permuted actual user key expressed in units of bits, plus one. For example, a shift factor of 125704 modulo 48, which is the number of bits in "IABncI", plus one, equals 41. The 41st bit thus becomes the first or most significant bit. Before shifting, the permuted actual user key "IABncI" can be expressed in binary as:

    ______________________________________
    "0100 1001   0100   0001 0100 0010 0110 1110 0110 0111
    0100  1001",
    ______________________________________

    ______________________________________
    "0100 1001   0100   1001 0100 0001 0100 0010 0110 1110
    0110  0111".
    ______________________________________

    ______________________________________
    "0100 1001 0110 1101 0111 0000 0110
                              1111   0111 0010 0111
    0100  0110 0001 0110 1110 0111 0100
                              0100   1001 0110 1110
    0110  0110 0110 1111 0111 0010 0110
                              1101   0110 0001 0111
    0100  0110 1001 0110 1111 0110 1110",
    ______________________________________

    ______________________________________
    "0111 0010 0110 1101 0110 0001 0111
                              0100   0110 1001 0110
    1111  0110 1110 0100 1001 0110 1101
                              0111   0000 0110 1111
    0111  0010 0111 0100 0110 0001 0110
                              1110   0111 0100 0100
    1001  0110 1110 0110 0110 0110 1111".
    ______________________________________

    ______________________________________
    "0100 1001 0100 1001 0100 0001 0100
                              0010   0110 1110 0110
    0111  0100 1001 0100 1001 0100 0001
                              0100   0010 0110 1110
    0110  0111 0100 1001 0100 1001 0100
                              0001   0100 0010 0110
    1110  0110 0111 0100 1001 0100 1001".
    ______________________________________

    ______________________________________
        "0100   1001 0100 1001 0100 0001 0100
                                   0010 0110 1110 0110
    .sym.
        "0100   1001 0110 1101 0111 0000 0110
                                   1111 0111 0010 0111
        0000    0000 0010 0100 0011 0001 0010
                                   1101 0001 1100 0001
        0111    0100 1001 0100 1001 0100 0001
                                   0100 0010 0110 1110
    .sym.
        0100    0110 0001 0110 1110 0111 0100
                                   0100 1001 0110 1110
        0011    0010 1000 0010 0111 0011 0101
                                   0000 1011 0000 0000
        0110    0111 0100 1001 0100 1001 0100
                                   0001 0100 0010 0110
    .sym.
        0110    0110 0110 1111 0111 0010 0110
                                   1101 0110 0001 0111
        0000    0001 0010 0110 0011 1011 0010
                                   1100 0010 0011 0001
        1110    0110 0111 0100 1001 0100 1001"
                                   (user key)
    .sym.
        0100    0110 1001 0110 1111 0110 1110"
                                   (base key)
        1010    0000 1110 0010 0110 0010 0111
                                   (resulting key)
    ______________________________________

    ______________________________________
    "0000 0000 0000 0001 1110 1011 0000 1000".
    ______________________________________

    ______________________________________
        "0000   0000 0010 0100 0011 0001 0010
                                   1101 0001 1100 0001
    .sym.
        "0000   0000 0000 0001 1110 1011 0000
                                   1000 0000 0000 0000
        0000    0000 0010 0101 1101 1010 0010
                                   0101 0001 1100 0001
        0011    0010 1000 0010 0111 0011 0101
                                   0000 1011 0000 0000
    .sym.
        0001    1110 1011 0000 1000 0000 0000
                                   0000 0001 1110 1011
        0010    1100 0011 0010 1111 0011 0101
                                   0000 1010 1110 1011
        0000    0001 0010 0110 0011 1011 0010
                                   1100 0010 0011 0001
    .sym.
        0000    1000 0000 0000 0000 0001 1110
                                   1011 0000 1000 0000
        0000    1001 0010 0110 0011 1010 1100
                                   1111 0010 1011 0001
        1010    0000 1110 0010 0110 0010 0111"
                                   (semifinal key)
    .sym.
        0000    0000 0001 1110 1011 0000 1000"
                                   (shift factor)
        1010    0000 1111 1100 1101 0010 1111
                                   (final key)
    ______________________________________

    ______________________________________
    "0101 0011   0110   0101 0110 0011 0111 0010  0110 0101
    0111  0100   0010   0000 0100 1101 0110 0101  0111 0011
    0111  0011   0110   0001 0110 0111 0110 0101".
    ______________________________________

    ______________________________________
    "S     e     c     r     e
        "0101   0011 0110 0101 0110 0011 0111
                                   0010 0110 0101 0111
    .sym.
        "0000   0000 0010 0101 1101 1010 0010
                                   0101 0001 1100 0001
        "0101   0011 0100 0000 1011 1001 0101
                                   0111 0111 1001 0110
    t     --     M     e     s     s
        0100    0010 0000 0100 1101 0110 0101
                                   0111 0011 0111 0011
    .sym.
        0010    1100 0011 0010 1111 0011 0101
                                   0000 1010 1110 1011
        0110    1110 0011 0110 0010 0101 0000
                                   0111 1001 1001 1000
    a     g     e"         (data -
                           alphanumeric)
        0110    0001 0110 0111 0110 0101"
                                   (data -
                                   ASCII encoded)
    .sym.
        1010    0000 1111 1100 1101 0010"
                                   (final key)
        1100    0001 1001 1011 1011 0111"
                                   (encrypted data)
    ______________________________________

    ______________________________________
    i        L               bytes swapped
    ______________________________________
    2        16              2nd and 16th
    3        10              3rd and 10th
    4        4               4th and 4th
    5        17              5th and 17th
    6        19              6th and 19th
    7        11              7th and 11th
    8        12              8th and 12th
    9        8               9th and 8th
    10       4               10th and 4th
    11       8               11th and 8th
    12       20              12th and 20th
    13       7               13th and 7th
    14       1               14th and 1st
    15       15              15th and 15th
    16       16              16th and 16th
    17       10              17th and 10th
    18       12              18th and 12th
    ______________________________________

    ______________________________________
    "108 116 112 97 73 102 97 110 114 110 109 111 116
     111 109 105 114 116 111 73".
    ______________________________________

    ______________________________________
        "6C    74    70 61
                          49  66 61
                                   6E  72  6E  6D  6F  74
                               6F  6D
                               .sym.
                                   "49 49 41 42 6E 67 49 49 41 42 6E 67 49 49
                                   41
                                   "25 3D 21 23 27 01 28 27 33 2C 03 08 3D 26
                                   2C
        69     72    74 6F
                          49"  (base key)
    .sym.
        42     6E    67 49
                          49"  (user key)
        2B     1C    13 26
                          00"  (semifinal key)
    ______________________________________

    ______________________________________
    i      PI (decimal)
                      IND        X.sub.i, Y.sub.i
    ______________________________________
    1      --         1          X.sub.1 = 1, Y.sub.1 = 1
    2      23688      9          X.sub.2 = 2, Y.sub.2 = 1
    3      12771      132        X.sub.3 = 17, Y.sub.3 = 4
    4      12810      11         X.sub.4 = 2, Y.sub.4 = 3
    5      13065      106        X.sub.5 = 14, Y.sub.5 = 2
    6      341        22         X.sub.6 = 3, Y.sub.6 = 6
    7      13680      81         X.sub.7 = 11, Y.sub.7 = 1
    8      14703      144        X.sub.8 = 18, Y.sub.8 = 8
    9      13370      91         X.sub.9 = 12, Y.sub.9 = 3
    10     15268      69         X.sub.10 = 9, Y.sub.10 = 5
    11     963        4          X.sub.11 = 1, Y.sub.11 = 4
    12     2712       153        X.sub.12 = 20, Y.sub.12 = 1
    13     22875      156        X.sub.13 = 20, Y.sub.13 = 4
    14     15656      137        X.sub.14 = 18, Y.sub.14 = 1
    15     17380      101        X.sub.15 = 13, Y.sub.15 = 5
    16     16598      119        X.sub.16 = 15, Y.sub.16 = 7
    17     10136      57         X.sub.17 = 8, Y.sub.17 = 1
    18     6802       83         X.sub.18 = 11, Y.sub.18 = 3
    19     12578      99         X.sub.19 = 13, Y.sub.19 = 3
    20     --         160        X.sub.20 = 20, Y.sub.20 = 8
    ______________________________________

    ______________________________________
            j   IV.sub.j
    ______________________________________
            1   01101111
            2   01011111
            3   11111011
            4   11111111
            5   11111111
            6   11111111
            7   11111111
            8   01111111
            9   11110111
            10  11111111
            11  01011111
            12  11011111
            13  11010111
            14  10111111
            15  11111101
            16  11111111
            17  11101111
            18  01111110
            19  11111111
            20  01101110
    ______________________________________

    ______________________________________
    (semfinal      "0010   0101 0011 1101 0010 0001 0010 0011
    key)
    (invar. key)
             .sym. "0001   1000 1010 0000 0110 0000 0001 1000
                   "0011   1101 1001 1101 0101 0001 0011 1011
    (invar. mask)
             &     "0110   1111 0101 1111 1111 1011 1111 1111
    (final key)    "0010   1101 0001 1101 1101 0001 0011 1011
                   0010    0111 0000 0001 0010 1000 0010 0111
             .sym. 1010    0000 0110 0000 0001 1000 1010 0000
                   1000    0111 0110 0001 0011 0000 1000 0111
             &     1111    1111 1111 1111 1111 1111 0111 1111
                   1000    0111 0110 0001 0011 0000 0000 0111
                   0011    0011 0010 1100 0000 0011 0000 1000
             .sym. 0110    0000 0001 1000 1010 0000 0110 0000
                   0101    0011 0011 0100 1010 0011 0110 1000
             &     1111    0111 1111 1111 0101 1111 1101 1111
                   0101    0011 0011 0100 0000 0011 0100 1000
                   0011    1101 0010 0110 0010 1100 0010 1011
             .sym. 0001    1000 1010 0000 0110 0000 0001 1000
                   0010    0101 1000 0110 0100 1100 0011 0011
             &     1101    0111 1011 1111 1111 1101 1111 1111
                   0000    0100 1000 0110 0100 1100 0011 0011
                   0001    1100 0001 0011 0010 0110 0000 0000"
             .sym. 1010    0000 0110 0000 0001 1000 1010 0000"
                   1011    1100 0111 0011 0011 1110 1010 0000"
             &     1110    1111 0111 1110 1111 1111 0110 1110"
                   1010    1100 0111 0010 0011 1110 0010 0000"
    ______________________________________

    ______________________________________
    (data, alphanumeric)
                      "S     e     c     r
    (data, ASCII)   "0101   0011 0110 0101 0110 0011 0111 0010
    (final key)
              .sym. "0010   1101 0001 1101 1101 0001 0011 1011
    (encrypted      0111    1110 1111 1000 1011 0010 0100 1001
                  e     t     --    M
                0110    0101 0111 0100 0010 0000 0100 1101
            .sym.
                1000    0111 0110 0001 0011 0000 0000 0111
                1110    0010 0001 0101 0001 0000 0100 1010
                  e     s     s     a
                0110    0101 0111 0011 0111 0011 0110 0001
            .sym.
                0101    0011 0011 0100 0000 0011 0100 1000
                0011    0110 0100 0111 0111 0000 0010 1001
                  g     e"
                0110    0111 0110 0101"
            .sym.
                0000    0100 1000 0110"
                0110    0011 1100 0011"
    ______________________________________

• Inventors
  Shaw, William Y.;
• Published
  Apr-8-1997
• Current US Classes:
  380/259
  380/277
  380/28
  380/44
  713/150
• Application #
  415719
• International Classes
  H04L 009/00
• Field of Search
  380/44 380/45 380/46 380/47 380/21 380/49 380/28
• Examiner
  Cain; David C.
• Agent
  Brown, Martin, Haller & McClain
• US Patent References:
  4200770
  4225935
  4369332
  4503287
  4596898
  4663500
  4819267
  4897876
  5115467
  5231662
  5237612
  5241599