Cryptography – Particular algorithmic function encoding – Nbs/des algorithm
Reexamination Certificate
1998-11-23
2003-04-15
Darrow, Justin T. (Department: 2132)
Cryptography
Particular algorithmic function encoding
Nbs/des algorithm
C380S028000, C380S037000, C380S042000, C380S043000, C380S044000
Reexamination Certificate
active
06549622
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to data security, and more particularly to a system and method for using a fast hardware implementation of RC4 to encrypt and decrypt files.
BACKGROUND OF THE INVENTION
In its infancy, computer networks provided a research-oriented environment where users and hosts were interested in a free and open exchange of information, and where users and hosts mutually trusted one another. However, computer networks have grown drastically. For example, the Internet currently interconnects at least 100,000 computer networks and millions of users. Because of the size and openness of many computer networks, computer networks have become a target of theft, data alteration, and other mischief.
Virtually everyone that sends information over many computer networks is vulnerable. Before sending a file over a computer network, companies balance the benefits and ease of transferring a file over the network against the risks of potential unauthorized file access. Companies generally use the security technique of encryption and decryption in an attempt to prevent unauthorized file access.
Many different types of encryption and decryption have been developed to prevent unauthorized file access. Bruce Schneier, author of
Applied Cryptography
, published by John Wiley & Sons, December 1995, describes RC4 as a variable-key-size stream cipher developed by RSA Data Security, Inc., of San Mateo, Calif., that is one example of a type of encryption/decryption method. RC4 is an encryption method that works in Output-Feedback (OFB) mode. The keystream RC4 is independent of the plaintext and the algorithm has an 8*8 S-box: S
0
, S
1
, . . . , S
255
.
The RC4 method for encrypting data is shown below in Table 1.
TABLE 1
RC4 Key Computation Algorithm
(1) i = (i + 1) mod 256
(2) j = (j + S
i
) mod 256
(3) swap S
i
and S
j
(4) t = (S
i
+ S
j
) mod 256
(5) k = S
t
As shown, two indices, i and j are generated to identify locations in a memory. Index j is based on a value, S
i
, stored in the memory. The values S
i
and S
j
, stored in the memory, are swapped, making the memory dynamic and ever-changing. A third index is then generated to identify a location based on the swapped values. The value stored at that location is used as the key. Because the memory is ever-changing, a hacker would need an exact replica of the memory and values stored therein at that exact moment in time to break the encryption/decryption code.
More particularly, in line 1 of the RC4 key computation algorithm, the variable “i” is incremented by 1. A modulo 256 is taken of the incremented value of variable “i”. In line 2, “j” acquires the sum of “j” plus S
i
. A modulo 256 is taken of the sum. In line 3, a swap of the memory addresses of S
i
and S
j
are taken. In line 4, “t” acquires the sum of the memory addresses of S
i
plus S
j
, modulo 256. In line 5, key “k” acquires the value of S
1
.
The entries of the RC4 encryption method are a permutation of the numbers “0” through “255”. The permutation is a function of the variable-length key. The RC4 encryption method has two counters, “i” and “j” that are each initialized to zero. Variable “k” is XORed with the unencrypted message to produce the encrypted message or XORed with the encrypted message to produce the decrypted message. The S-box is filled linearly from S
0
, S
1
, . . . , S
255
. Once one 256 byte array is filled, another 256 byte array is filled with the key. This process of repeating the key as necessary continues until the entire array: k
0
, k
1
, . . . , k
255
is filled.
A conventional implementation of the RC4 encryption/decryption method would include the steps shown in Table 2.
TABLE 2
RC4 Key Computation Software Implementation
(1) increment i
(2) load S
i
, add to j
(3) load S
j
(4) store value of S
i
into S
j
(5) store value of S
j
into S
i
, add S
i
and S
j
to generate “t”
(6) load S
t
, XOR S
t
with message
The conventional implementation of the RC4 encryption/decryption method is generally performed in software. The steps shown in Table 2 repeat until all data is either encrypted or decrypted. As shown, in line 1 of the RC4 key computation software implementation, variable “i” is incremented by 1. Although not shown, a modulo 256 is taken of the incremented value of variable “i”. In line 2, load the variable S
i
and add “j” to the variable S
i
. Although not shown, a module 256 is taken of the sum. In line 3, load S
j
. In line 4, perform one half of the swap of memory addresses by first storing S
i
into S
j
. In line 5, complete the swap of memory addresses by storing S
j
into S
i
, and add S
i
and S
j
to generate t. Although not shown a modulo of the sum is taken. In line 6, load S
t
, and XOR S
t
with the message. Although a conventional software implementation of the RC4 encryption/decryption process eventually encrypts or decrypts a given message or file, this process is processor heavy, costly and requires excessive resource time.
Therefore, there is a need to provide a system and method to encrypt/decrypt files efficiently using a fast hardware implementation of the RC4 ciphertext algorithm.
SUMMARY OF THE INVENTION
The present invention provides a system and method for encrypting and decrypting files using a fast hardware implementation of the RC4 algorithm to enable secure access to information resources in a computer network. The network system includes a sender computer coupled via a computer network to a receiver computer.
Multiport memory included within both the sender computer and the receiver computer as part of the RC4 logic enable a fast hardware implementation of the respective encryption circuit and decryption circuit. The hardware implementation of the RC4 encryption/decryption algorithm is made faster by reducing the number of cycles needed to perform the encryption/decryption. One of ordinary skill in the art will understand that a reduction in the number of cycles greatly increases efficiency and reduces cost.
From a system point of view, a preferred embodiment of the invention encrypts a message using the RC4 encryption algorithm. The system comprises: a message receiver for receiving a message; a key computation module for computing an encryption key according to the RC4 encryption algorithm, where the key computation module includes at least one multiport memory that allows at least a synchronous read and write; and an XOR module for performing an XOR function of the message and the key to yield an encrypted message.
From a method point of view, a preferred embodiment of the invention encrypts a message using an encryption circuit that includes at least one multiport memory. The method comprises the steps of: (a) incrementing a value “i”; (b) loading a value S
i
; (c) adding substantially simultaneously with step (b) a value S
j
of step b to a value “j”; (d) loading a value S
j
; (e) adding substantially simultaneously with step (d) the value S
j
of step (d) to S
i
to generate “t” and storing S
i
into S
j
; (f) reading k by loading S
t
; (g) storing substantially simultaneously with step (f) S
j
into S
i
and incrementing the value “i”; and (h) performing an XOR function of the message and k (value S
t
) to encrypt the message.
REFERENCES:
patent: 5717760 (1998-02-01), Satterfield
patent: 5799090 (1998-08-01), Angert
patent: 5825882 (1998-10-01), Kowalaski et al.
patent: 6125182 (2000-09-01), Satterfield
Bruce Schneier, “Applied Cryptography”, Oct. 18, 1995, Wiley & Sons, 2nd addition, p. 397-398.*
Schneier, Bruce,Applied Cryptography, Second Edition, 1996, pp. 397, 398, New York, New York U.S.A.
Compaq Computer Corporation
Darrow Justin T.
Fenwick & West LLP
LandOfFree
System and method for a fast hardware implementation of RC4 does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for a fast hardware implementation of RC4, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for a fast hardware implementation of RC4 will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3108939