Memory configuration which support multiple cryptographical...

Details Memory configuration which support multiple cryptographical... Memory configuration which support multiple cryptographical...

1998-06-29

2001-09-11

Barrón, Jr., Gilberto (Department: 2766)

Electrical computers and digital processing systems: support

Data processing protection using cryptography

C713S152000, C380S044000, C380S030000

Reexamination Certificate

active

06289454

ABSTRACT:

BACKGROUND
The present invention concerns the encrypting and the decrypting of data within a computing system and pertains specifically to memory configurations which support use of multiple cryptographic algorithms.
In order to protect against theft or misuse, secure information within a computing system can be encrypted before being transferred over a network or other medium. When received, the secure information is decrypted before being used. The RSA cryptographic algorithm and the Diffie-Hellman cryptographic algorithm are examples of public key algorithms that utilize both public and private key components to perform key exchanges. Each of these cryptographic algorithms requires private components that are programmed into the system memory.
For example, in the Diffie-Hellman algorithm, all users in the computing system agree on a common large prime number n, and second number g, such that g is primitive mod n. The selected values for n and g are not kept secret. Each user in the system then generates a large random integer x, which is the private key. The associated public key, X, is generated the following formula:
X=g
x
mod
n
Two users can compute a shared secret key, k, by exchanging public keys, X and Y and applying the following formula:
k=Y
x
mod
n
k′=X
y
mod
n
where
k=k′=g
xy
mod
n
Unlike the Diffie-Hellman algorithm, which is a key exchange algorithm, the RSA cryptographic algorithm does not require users to belong to a “system” and have knowledge of predetermined values. Each user determines his own public and private key pairs. To do this two randomly generated large prime numbers p and q are kept secret. The two randomly generated large prime numbers p and q are used to generate a public key n according to the following formula:
n=p*q
The numbers p and q are also, along with a public key component e, used to generate a private key d which also must be kept secret. The formula used to generate private key d is as follows:
d=e
−1
mod((
p−
1)(
q−
1)).
To encrypt a message m to produce an encrypted message c, the sender would use the receivers public key in the following formula:
c=m
e
mod
n
To decrypt the encrypted message c to produce the original message m, the receiver would use his private key in the following formula:
m=c
d
mod
n.
The various key components can be stored in a one time programmable memory (OTP) in a computer system allowing permanent access within the system. This also facilitates the ability of a computer system to provide some protection against undesired copying of the key components from an integrated circuit chip on which the key components are stored.
For example, for the Diffie-Hellman algorithm, the private key, x, is stored in 512 bits of a one-time programmable memory. This number is kept private. The same one-time programmable memory can also be used to store the large prime number n and the second number g. For example, 512 bits of the one-time programmable memory are used to store the number n and 32 bits of the one-time programmable memory are used to store the number g.
In order to support 1024 bit RSA cryptographic algorithm, the length of the value p and of the value q are half the 1024 bit length of n. Thus the values p and q are each 512 bits in length and are each stored using 512 bits in memory. Additionally, the public key component e is also stored using 32 bits of memory. It is advantageous to store p and q rather than storing the secret key d in memory. This is because it is computationally faster to perform the exponentiations utilizing the Chinese Remainder Theorem which use p and q rather than using d.
For additional information on the RSA Algorithm and the Diffie-Hellman algorithm, see Bruce Schneier,
Applied Cryptography,
John Wiley & Sons, Inc., 1996, pp. 466-469, 513-514.
SUMMARY OF THE INVENTION
In accordance with the preferred embodiment of the present invention, multiple cryptographic algorithms are utilized on a single integrated circuit. In a single special memory, a plurality of values are stored. The values are used for a first cryptographic algorithm and are used for a second cryptographic algorithm. At least one value from the plurality of values is used both for the first cryptographic algorithm and for the second cryptographic algorithm. When performing a first operation for the first cryptographic algorithm, first values from the plurality of values are used. The first values include the value used both for the first cryptographic algorithm and for the second cryptographic algorithm. When performing a second operation for the second cryptographic algorithm, second values from the plurality values are used. The second values also include the value used both for the first cryptographic algorithm and for the second cryptographic algorithm.
In one preferred embodiment of the present invention, the first cryptographic algorithm is the RSA cryptographic algorithm and the second cryptographic algorithm is the Diffie-Hellman cryptographic algorithm. The special memory is, for example, a 2048-bit one time programmable memory with half the memory being used to store private values and half the memory being used to store public values. Access to the memory locations used to store private values is restricted in order to preserve secrecy of the private values.
The first and second operations can be, for example, obtaining a public key for either cryptographic algorithm, obtaining a private key for either cryptographic algorithm, performing an encryption using either cryptographic algorithm and/or performing a decryption using either cryptographic algorithm.
The present invention allows implementation of an integrated circuit chip that supports more than one public-key algorithm security system. This approach allows each chip to be programmed without regard to the end application and it offers versatility in the marketplace by having a single chip address multiple public key applications. The OTP memory configurations allow for a single programming algorithm to be used to support multiple public key algorithms applications. Partitioning the OTP into public and private segments as well as prime and non-prime segments allows for each public key algorithm to use different portions of the OTP based upon their own requirements.
The use of the multiple public key OTP memory programming configuration facilitates implementation of multiple public key applications. In development environments this is extremely valuable and in production systems it will provide flexibility and economic advantages. Providing cryptographic primitives (on chip software) which perform generic exponentiation and math intensive computations on either an embedded processor or on dedicated hardware also makes the device more versatile. Again, regardless of the public key algorithm used, the primitives can be used to perform any public key algorithm and the primitives can also be customized via downloadable configuration tables to retrieve the appropriate data from the correct area of the OTP memory.


REFERENCES:
patent: 5987131 (1999-11-01), Clapp
patent: 6088800 (2000-07-01), Jones et al.
patent: 6088802 (2000-07-01), Bialick et al.

Affiliated with

Also associated with

Rating

Memory configuration which support multiple cryptographical... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Memory configuration which support multiple cryptographical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory configuration which support multiple cryptographical... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2437455