Patent US5003597A successfully refreshed from Google Patents.
US5003597A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for data encryption
Assignee: Xerox Corp
•
Filing: 1989-12-21
•
Granted: 1991-03-26
•
Expires: 2009-12-21
Abstract
Abstract A method and apparatus for encrypting and decrypting data which operates efficiently on computers of differing architectures is disclosed. Unlike previous encryption/decryption method and apparatus, the present invention executes efficiently in the computer's software. The method uses part of the data input to access a table of pseudo-random numbers. The pseudo-random numbers are exclusively ORed (XORed) with the remaining part of the data input. The output from the XOR operation is then used to access the table where the other portion of the data is in turn XORed with the pseudo random numbers. This iterative process continues until the data is fully randomized. Several variations of this method are presented.
Inventors
- 👤 Ralph C. Merkle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 15:14
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/06; H04L9/0618; H04L9/0625; H04L2209/00; H04L2209/08
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
132 words
A method for encrypting binary data, the binary data comprising 64-bit data blocks, the method comprising the steps of: splitting the 64-bit data block into a left 32-bit block and a right 32-bit block; using the left 32-bit block to access and retrieve a 32-bit number from a table containing 32-bit numbers, the table having been computed prior to the splitting step; exclusive-ORing the right 32-bit block with the 32-bit number obtained from the table; rotating the left 32-bit block according to a predefined rotation schedule; relabelling the rotated left 32-bit data block as the right 32-bit data block and relabelling the product of the exclusive-OR operation as the left 32-bit data block; and repeating the using, exclusive-ORing, rotating and relabelling steps until the binary data appears to be a random number.
Claim 2
Independent Claim
132 words
A method for encrypting binary data, the binary data comprising 64-bit data blocks, the method comprising the steps of: splitting the 64-bit data block into a left 32-bit block and a right 32-bit block; using the left 32-bit block to access and retrieve a 32-bit number from a table containing 32-bit numbers, the table having been computed prior to the splitting step; exclusive-ORing the right 32-bit block with the 32-bit number obtained from the table; rotating the left 32-bit block according to a predefined rotation schedule; relabelling the rotated left 32-bit data block as the right 32-bit data block and relabelling the product of the exclusive-OR operation as the left 32-bit data block; and repeating the using, exclusive-ORing, rotating and relabelling steps until the binary data appears to be a random number.
Claim 3
Dependent Claim
15 words
The method of claim 1 wherein the repeating step is performed at least 15 times.
Claim 4
Dependent Claim
28 words
The method of claim 2 wherein the rotating and repeating steps insure that the table is only accessed once by every 8-bit unit in the 64-bit data block.
Claim 5
Dependent Claim
29 words
The method of claim 2 wherein a second, different table is used for supplying the number to the exclusive-OR step after the repeating step has been performed seven times.
Claim 6
Dependent Claim
45 words
The method of claim 1 wherein after the 64-bit data block is split, the left and right 32-bit blocks are exclusive-ORed with a first and second 32-bit auxiliary key binary number, the products of these exclusive-OR operations being relabelled the right and left 32-bit blocks.
Claim 7
Dependent Claim
52 words
The method of claim 5 wherein after the final repeat step has been performed, the final right and left 32-bit data blocks are exclusive-ORed respectively with a third and fourth auxiliary key binary number, the results of these two exclusive-OR operations being concatenated together to produce a final 64-bit encrypted output number.
Claim 8
Dependent Claim
20 words
The method of claim 1 wherein the rotation of the left 32-bit data block is accomplished by using SHIFT instructions.
Claim 9
Dependent Claim
20 words
The method of claim 1 wherein the rotation of the left 32-bit data block is accomplished by using ROTATE instructions.
Claim 10
Dependent Claim
39 words
The method of claim 1 wherein the table is computed by the steps of generating a stream of pseudo-random bytes; and using the stream of pseudo-random bytes to generate four pseudo-random permutations that map 8 bits to 8 bits.
Claim 11
Dependent Claim
19 words
The method of claim 9 wherein the permutations are generated by using a known algorithm for producing pseudo-random permutations.
Claim 12
Dependent Claim
18 words
The method of claim 9 wherein a predefined table is used to generate the stream of pseudo-random bytes.
Claim 13
Independent Claim
123 words
A method for encrypting binary data, the binary data comprising 64-bit data blocks, the method comprising the steps of: splitting the 64-bit data block into a left 32-bit block and a right 32-bit block; using the left 32-bit block to access and retrieve a 32-bit number from a table containing 256 32-bit numbers; exclusive-ORing the right 32-bit block with the 32-bit number obtained from the table; rotating the left 32-bit block according to a predefined rotation schedule; relabelling the rotated left 32-bit data block as the right 32-bit data block and relabelling the product of the exclusive-OR operation as the left 32-bit data block; and repeating the using, exclusive-ORing, rotating said relabelling steps until the binary data appears to be a random number.
Claim 14
Independent Claim
123 words
A method for encrypting binary data, the binary data comprising 64-bit data blocks, the method comprising the steps of: splitting the 64-bit data block into a left 32-bit block and a right 32-bit block; using the left 32-bit block to access and retrieve a 32-bit number from a table containing 256 32-bit numbers; exclusive-ORing the right 32-bit block with the 32-bit number obtained from the table; rotating the left 32-bit block according to a predefined rotation schedule; relabelling the rotated left 32-bit data block as the right 32-bit data block and relabelling the product of the exclusive-OR operation as the left 32-bit data block; and repeating the using, exclusive-ORing, rotating said relabelling steps until the binary data appears to be a random number.
Claim 15
Dependent Claim
22 words
The method of claim 12 wherein the table comprises four columns and 256 rows, each entry in the rows being 8-bits wide.
Claim 16
Dependent Claim
17 words
The method of claim 13 wherein all four of the 8-bit columns are permutations of one another.
Claim 17
Dependent Claim
24 words
The method of claim 14 wherein the selection of a different number in the table changes all four 8-bit numbers generated by the table.
Claim 18
Dependent Claim
45 words
The method of claim 12 wherein after the 64-bit data block is split, the left and right 32-bit blocks are exclusive-ORed with a first and second 32-bit auxiliary key binary number, the products of these exclusive-OR operations being relabelled the right and left 32-bit blocks.
Claim 19
Dependent Claim
52 words
The method of claim 16 wherein after the final repeat step has been performed, the final right and left 32-bit data blocks are exclusive-ORed respectively with a third and fourth auxiliary key binary number, the results of these two exclusive-OR operations being concatenated together to produce a final 64-bit encrypted output number.
Claim 20
Independent Claim
171 words
A method for encrypting data, the data comprising 64-bit data blocks, the method comprising the steps of: calculating, prior to the start of data encryption, a standard table of pseudo-random permutations; selecting a user-defined key; first exclusive-ORing of the 64-bit data block with the key; splitting the product of the first exclusive-ORing into a left and right 32-bit half; using the left 32-bit half as an index to access the standard table and retrieve a 32-bit pseudo-random number; second exclusive-ORing the right 32-bit half with the 32-bit pseudo-random number; relabelling the product of the second exclusive-ORing of the right half and the 32-bit pseudo-random number as the left 32-bit half; rotating the left 32-bit half according to a predefined schedule; relabelling the left 32-bit half as the right 32-bit half after the rotation; first repeating the steps of using, second exclusive-ORing, relabelling, rotating and relabelling a predefined number of times; and repeating the first exclusive-ORing step prior to the first repeating step every eighth time the first repeating step is performed.
Claim 21
Independent Claim
171 words
A method for encrypting data, the data comprising 64-bit data blocks, the method comprising the steps of: calculating, prior to the start of data encryption, a standard table of pseudo-random permutations; selecting a user-defined key; first exclusive-ORing of the 64-bit data block with the key; splitting the product of the first exclusive-ORing into a left and right 32-bit half; using the left 32-bit half as an index to access the standard table and retrieve a 32-bit pseudo-random number; second exclusive-ORing the right 32-bit half with the 32-bit pseudo-random number; relabelling the product of the second exclusive-ORing of the right half and the 32-bit pseudo-random number as the left 32-bit half; rotating the left 32-bit half according to a predefined schedule; relabelling the left 32-bit half as the right 32-bit half after the rotation; first repeating the steps of using, second exclusive-ORing, relabelling, rotating and relabelling a predefined number of times; and repeating the first exclusive-ORing step prior to the first repeating step every eighth time the first repeating step is performed.
Claim 22
Independent Claim
130 words
A method for encrypting binary data, the binary data comprising 64-bit data blocks, the method comprising the steps of: splitting the 64-bit data block into a left 32-bit block and a right 32-bit block; using the left 32-bit block to access and retrieve a 32-bit number from a table containing 32-bit numbers, the table being computed using a user-supplied key; exclusive-ORing the right 32-bit block with the 32-bit number obtained from the table; rotating the left 32-bit block according to a predefined rotation schedule; relabelling the rotated left 32-bit data block as the right 32-bit data block and relabelling the product of the exclusive-OR operation as the left 32-bit data block; and repeating the using; exclusive-ORing, rotating and relabelling steps until the binary data appears to be a random number.
Claim 23
Independent Claim
130 words
A method for encrypting binary data, the binary data comprising 64-bit data blocks, the method comprising the steps of: splitting the 64-bit data block into a left 32-bit block and a right 32-bit block; using the left 32-bit block to access and retrieve a 32-bit number from a table containing 32-bit numbers, the table being computed using a user-supplied key; exclusive-ORing the right 32-bit block with the 32-bit number obtained from the table; rotating the left 32-bit block according to a predefined rotation schedule; relabelling the rotated left 32-bit data block as the right 32-bit data block and relabelling the product of the exclusive-OR operation as the left 32-bit data block; and repeating the using; exclusive-ORing, rotating and relabelling steps until the binary data appears to be a random number.
Claim 24
Dependent Claim
46 words
The method of claim 19 wherein after the 64-bit data block is split, the left and right 32-bit blocks are exclusive-ORed with a first and second 32-bit auxiliary key binary number, the products of these exclusive-O R operations being relabelled the right and left 32-bit blocks.
Claim 25
Dependent Claim
51 words
The method of claim 20 wherein after the final step has been performed, the final right and left 32-bit data blocks are exclusive-ORed respectively with a third and fourth auxiliary key binary number, the results of these two exclusive-OR operations being concatenated together to produce a final 64-bit encrypted output number.
Claim 26
Independent Claim
133 words
A method for encrypting binary data, the binary data comprising N-bit data blocks, the method comprising the steps of: splitting the N-bit data block into a left N/2-bit block and a right N/2-bit block; using the left N/2-bit block to access and retrieve a N/2-bit number from a table containing N/2-bit numbers, the table having been computed prior to the splitting step; exclusive OR-ing the right N/2-bit block with the N/2-bit number obtained from the table; rotating the left N/2-bit block according to a predefined rotation schedule; relabelling the rotated left N/2-bit data block as the right N/2-bit data block and relabelling the product of the exclusive-OR operation as the left N/2-bit data block; and repeating the using, exclusive-ORing, rotating and relabelling steps until the binary data appears to be a random number.
Claim 27
Independent Claim
133 words
A method for encrypting binary data, the binary data comprising N-bit data blocks, the method comprising the steps of: splitting the N-bit data block into a left N/2-bit block and a right N/2-bit block; using the left N/2-bit block to access and retrieve a N/2-bit number from a table containing N/2-bit numbers, the table having been computed prior to the splitting step; exclusive OR-ing the right N/2-bit block with the N/2-bit number obtained from the table; rotating the left N/2-bit block according to a predefined rotation schedule; relabelling the rotated left N/2-bit data block as the right N/2-bit data block and relabelling the product of the exclusive-OR operation as the left N/2-bit data block; and repeating the using, exclusive-ORing, rotating and relabelling steps until the binary data appears to be a random number.
Claim 28
Dependent Claim
46 words
The method of claim 22 wherein after the N/2-bit data block is split, the left and right N/2-bit blocks are exclusive-ORed with a first and second N/2-bit auxiliary key binary number, the products of these exclusive-O R operations being relabelled the right and left N/2-bit blocks.
Claim 29
Dependent Claim
51 words
The method of claim 23 wherein after the final repeat step has been performed, the final right and left N/2-bit data blocks are exclusive-ORed respectively with a third and fourth auxiliary key binary number, the results of these exclusive-OR operations being concatenated together to produce a final N-bit encrypted output number.
Claim 30
Independent Claim
133 words
A method for encrypting binary data, the binary data comprising 64-bit data blocks, the method comprising the steps of: splitting the 64-bit data block into a left 32-bit block and a right 32-bit block; using the left 32-bit block to access and retrieve a 32-bit number from a table containing 32-bit numbers, the table having been computed prior to the splitting step; reversibly mixing the right 32-bit block with the 32-bit number obtained from the table; rotating the left 32-bit block according to a predefined rotation schedule; relabelling the rotated left 32-bit data block as the right 32-bit data block and relabelling the product of the mixing operation as the left 32-bit data block; and repeating the using, mixing, rotating and relabelling steps until the binary data appears to be a random number.
Claim 31
Independent Claim
133 words
A method for encrypting binary data, the binary data comprising 64-bit data blocks, the method comprising the steps of: splitting the 64-bit data block into a left 32-bit block and a right 32-bit block; using the left 32-bit block to access and retrieve a 32-bit number from a table containing 32-bit numbers, the table having been computed prior to the splitting step; reversibly mixing the right 32-bit block with the 32-bit number obtained from the table; rotating the left 32-bit block according to a predefined rotation schedule; relabelling the rotated left 32-bit data block as the right 32-bit data block and relabelling the product of the mixing operation as the left 32-bit data block; and repeating the using, mixing, rotating and relabelling steps until the binary data appears to be a random number.
Claim 32
Dependent Claim
23 words
The method of claim 25 wherein the reversibly mixing step comprises an integer addition of the right 32-bit block and the 32-bit number.
Claim 33
Dependent Claim
23 words
The method of claim 25 wherein the reversibly mixing step comprises an integer subtraction of the right 32-bit block and the 32-bit number.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-03-25 | 1994-09-24 | 1995-03-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-03-25 | 1998-09-24 | 1999-03-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-03-25 | 2002-09-24 | 2003-03-26 | $7700.00 | Window Closed / Lapsed |