Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-09-09
2002-01-08
Peeso, Thomas R. (Department: 2132)
Cryptography
Particular algorithmic function encoding
C713S168000, C713S181000
Reexamination Certificate
active
06337910
ABSTRACT:
RELATED APPLICATIONS
This application is related to co-pending U.S. Pat. application Ser. No. 09/150,120, filed on Sep. 9, 1998, entitled “A HYBRID ONE TIME PAD ENCRYPTION AND DECRYPTION APPARATUS WITH METHODS FOR ENCRYPTING AND DECRYPTING DATA” (VLSI.256PA). The disclosure of the above referenced application is incorporated by reference into this application.
FIELD OF THE INVENTION
This invention relates generally to apparatus and methods for encryption and decryption of digital messages or file representations, more specifically, to an apparatus and method using a hybrid scheme for encrypting and decrypting a high security encrypted message or file representation using a one time random number pad where the pad is generated at both the encrypting and decryption stations.
BACKGROUND OF THE INVENTION
Encryption and decryption devices are desired within the communications industry. As reliance on electronic banking, Internet e-mail and other purely electronic communications increase, there is an increasing need for secure communications which cannot be broken, even with high computation power and heavy investments in technology.
This need is presently being filled by such algorithms as DES (Data Encryption Standard) and RSA (Rivest-Shamir-Adleman) encryption techniques. For the purpose of discussion, these will be referred to as “short key” techniques. While these techniques are robust and allow for variable keys, they are still potentially subject to defeat by application of repetitive analysis to decode the cipher which is cycled many times in a typical message.
A technique which is hypothetically undefeatable is the one time pad technique. Unfortunately it is also impractical in its application. The one time pad technique uses a pad which is a perfectly random set of numbers the same size as the message transmitted. This pad is combined with the message data (typically by an exclusive-OR operation) to produce the encrypted data. Since the pad is truly random, there is no relationship of the output data from this operation to the input data that was provided. The impracticality of the one time pad technique stems from several factors: 1) The encrypted data and pad are twice as large as the original message; and 2) The security requirement for the pad is as great as the security requirement of the message; 3) The recipient needs the pad to decode the message; and 4) The pad can only be used once or repetitive analysis could reveal the pad.
The above referenced co-pending patent application determined that in order to use a one time pad in a practical application, a means to transmit the pad in a fashion as secure as the message itself is needed and that a method is also needed so that the recipient does not have to have foreknowledge of the pad in order to decode the message. It is also possible to not transmit the pad, but generate the pad simultaneously at two locations.
SUMMARY OF THE INVENTION
The present invention addresses the above-mentioned and other needs by creating a method and apparatus for generating a one time pad simultaneously at two locations. The Diffie-Hellman algorithm is used, as suggested by the above referenced co-pending patent application, but here the algorithm is not used to exchange a key, but to generate the same one time pad at the transmitting and receiving stations by exchanging pad recipes. These pad recipes are numbers which can be used to compute a pad that is common between multiple stations. Once the recipes from other locations are known, a pad is computed using a locally generated random number and the received recipes.
The Diffie-Hellman key exchange algorithm is well known to those familiar with the art as a method for passing encryption keys between two locations. A number which is common to both locations g, is raised to a different random power x and y, at each location and divided by a prime number field p. The remainder of that division comprises the recipe that is shared with other locations. The result of this computation g
x
mod p or g
y
mod p is then passed to the other locations. At each location, the received value is then raised to the same random power x and y that was used in the making of the key that was passed to the other location. This results in a number at each location that is equal to g
xy
mod p. This common number can then be used to encode data and no interception of the transmission g
x
and g
y
allows for the computation of g
xy
mod p. This provides for a secure means for sharing a common key between multiple locations. In this invention, it is not a key that is passed between locations but a number which is used to compute the one time pad.
The present invention is directed to encrypting and decrypting messages. According to one example embodiment of the present invention, messages are encrypted and decrypted using a one-time pad that is not transmitted. In another example embodiment of the present invention, a one-time pad is generated simultaneously at two or more locations in a manner that includes computing the one time pad as a function of a recipe and a local secret random number field.
In accordance with one embodiment of the present invention, an apparatus for generating a one time pad in multiple locations is disclosed. The apparatus computes a recipe according to the method below, transmits the recipe and receives a recipe from at least one other location. It then computes the one time pad according to the method described below.
In accordance with another embodiment of the present invention, a method for generating a one time pad at multiple locations simultaneously is disclosed. A random number is generated at each location and used to raise a primitive number of a prime field which is known at all locations to the power of the generated random number. Then the generated number is divided by the prime field which is also known at all locations. The remainder of this division is passed to the other locations as a recipe for a one time pad.
The one time pad is generated for communication with a location by taking the recipe received from that location and raising it to the power of the locally generated random number that was used to make the recipe that this location transmitted to other locations. The result of this exponentiation is then divided by the known prime field and the remainder is used as a one time pad or is used to further compute a one time pad.
The foregoing and other objects, features, and advantages of the invention will be apparent from the following, more particular, description of the preferred embodiment of the invention, as illustrated in the accompanying drawings.
REFERENCES:
patent: 4218582 (1980-08-01), Hellman et al.
patent: 4969189 (1990-11-01), Ohta et al.
patent: 5848159 (1998-12-01), Collins et al.
U.S. Pat. Application No. 09/150,120, filed Sep. 9, 1998, for Cornelius et al.
Cornelius Steve
Goff Lonnie C.
Jack Todd
Koninklijke Philips Electronics N.V. (KPENV)
Peeso Thomas R.
LandOfFree
Method and apparatus for generating one time pads... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating one time pads..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating one time pads... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826511