





Inventor(s): 
Rivest; Ronald L. , Arlington, MA

Applicant(s): 
RSA
Data Security, Inc., Redwood City, CA

Issued/Filed Dates: 
Nov. 10, 1998 / April 21, 1997

Application Number: 
US1997000845210

IPC Class: 
H04L 009/06;

Class: 
380/044;
380/028;
380/037;
364/717.01;

Field of Search: 
711/216 364/717.01,717.03,717.04,717.05,717.06,717.07
380/46,42,43,44,37,57,28

Abstract: 
A simple encryption and decryption device has been developed. The underlying
algorithm is a fast block cipher that may be implemented efficiently in hardware
or software. The algorithm makes heavy use of datadependent rotations. The
amount of each rotation depends on the data being encrypted and intermediate
encryption results. The variables for the algorithm include word size, rounds,
and the length of a secret key. 
Attorney, Agent, or Firm: 
Testa, Hurwitz & Thibeault, LLP;

Primary/Assistant Examiners: 
Tarcza; Thomas H.; Laufer; Pinchus M.







Related Applications: 
Application Number 
ApplDate 
Patent 
Issued 
Title 
US1995000548318 
19951101 










U.S. References: 
(No patents reference this one)







CLAIMS:

What is claimed is:
1. A method of forming a key table,
the method comprising the steps of:

(a) storing in one of a first table and a second table a sequence of elements
corresponding to a secret key;

(b) initializing the other of the first table and the second table to comprise
a pseudorandom sequence of elements;

(c) updating at least one element of the first table, using information in
the second table, to produce an updated first table;

(d) updating at least one element of the second table, using information
in the updated first table, to produce an updated second table; and

(e) repeating the updating steps (c) and (d) for at least one additional
element of each of the updated first table and the updated second table,
such that a final version of one of the updated first table and the updated
second table corresponds to the key table.
2. The method of claim
1 wherein the storing step (a) includes storing in the first table a
sequence of elements corresponding to a secret key, and the initializing
step (b) includes initializing the second table to comprise a pseudorandom
sequence of elements.
3. The method of claim
2 further including the steps of:

initializing a memory register A and a memory register B;

initializing an accumulator i and an accumulators j, wherein S designates
an element of the second table and L designates an element of the first table;
and

rotating an element S by a predetermined amount and storing the result in
memory register A before performing the updating steps (c) and (d).
4. The method of claim
3 wherein the updating step (c) further includes rotating an element
L by an amount determined at least in part by the contents of memory register
A, and storing the result in memory register B.
5. The method of claim
3 wherein the updating step (d) further includes computing the sum of
an element S and an amount determined at least in part by the contents of
memory register B, rotating the sum by a predetermined amount, and storing
the result in memory register A.
6. The method of claim
3 wherein the repeating step (e) includes incrementing the accumulators
i and j and repeating the updating steps (c) and (d) for different elements
S and L of the updated tables.
7. The method of claim
1 wherein the repeating step (e) further includes repeating the updating
steps (c) and (d) such that the updating steps (c) and (d) are each performed
a constant times the maximum of the number of elements in the first and second
tables.
8. The method of claim
1 wherein the secret key corresponds to an initial value of a pseudorandom
number generator, and the method further includes the step of outputting
a sequence of elements from the final version of at least one of the updated
first table and the updated second table as a pseudorandom number.
9. The method of claim
8 wherein the length of the pseudorandom number is greater than the length
of the initial value.
10. The method of claim
1 wherein the secret key corresponds to an input of a compression function
for a hash routine, and the method further includes the step of outputting
a sequence of elements from the final version of at least one of the updated
first table and the updated second table as an output of the compression
function.
11. An apparatus for forming a key
table, comprising:

a memory for storing in one of a first table and a second table a sequence
of elements corresponding to a secret key, and for storing in the other of
the first table and the second table a pseudorandom sequence of elements;
and

a processor associated with the memory and operative: (i) to update at least
one element of the first table, using information in the second table, to
produce an updated first table; (ii) to update at least one element of the
second table, using information in the updated first table, to produce an
updated second table; and (iii) to repeat the updating operations for at
least one additional element of each of the updated first table and the updated
second table, such that a final version of one of the updated first table
and the updated second table corresponds to the key table.
12. The apparatus of
claim 11 wherein the first table includes the sequence
of elements corresponding to a secret key, and the second table includes
the pseudorandom sequence of elements.
13. A computerreadable medium
containing one or more programs which when executed by a computer and applied
to first and second tables of information, with one of the first table and
the second table storing a sequence of elements corresponding to a secret
key, and the other of the first table and the second table storing a pseudorandom
sequence of elements, implement the following steps:

updating at least one element of the first table, using information in the
second table, to produce an updated first table;

updating at least one element of the second table, using information in the
updated first table, to produce an updated second table;

repeating the updating steps for at least one additional element of each
of the updated first table and the updated second table, such that a final
version of one of the updated first table and the updated second table
corresponds to a key table.

: 
This application is a divisional of U.S. application
Ser. No. 08/548,318, filed Nov. 1, 1995.

Foreign References: 
none
(No patents reference this one)

Other References: 

Applied Cryptography, Protocols, Algorithms, and Source Code in C, Bruce
Schneier, pp. 154185; 219272.

"A High Performance Encryption Algorithm," W.E. Madryga, Computer Secuirty,
pp. 557570.

Ronald L. Rivest, "The RC5 Encryption Algorithm", Dr. Dobb's Journal, Jan.
1995 pp. 146148.


