Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
2000-10-25
2004-10-05
Jung, David (Department: 2134)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C213S168000, C213S169000
Reexamination Certificate
active
06802001
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to cryptographic methods and, more particularly, to methods of establishing an encryption key between two or more parties.
Encryption is the process of disguising intelligible information, called plaintext, to hide its substance from eavesdroppers. Encrypting plaintext produces unintelligible data called ciphertext. Decryption is the process of converting ciphertext back to its original plaintext. Using encryption and decryption, two parties can send messages over an insecure channel without revealing the substance of the message to eavesdroppers.
A cryptographic algorithm or cipher is a mathematical function used in the encryption and decryption of data. A cryptographic algorithm works in combination with a key to encrypt and decrypt messages. The key, typically a large random number, controls the encryption of data by the cryptographic algorithm. The same plaintext encrypts to different ciphertext with different keys. In general, it is extremely difficult to recover the plaintext of a message without access to the key, even by an eavesdropper having full knowledge of the cryptographic algorithm.
One type of key-based cryptographic algorithm is a symmetric algorithm, also called secret key algorithms, in which the same key is used both for encryption and decryption. Symmetric algorithms require that the sender and receiver of the message agree on a secret key before they can communicate securely. One benefit of symmetric algorithms is that symmetric algorithms are fast. However, key distribution can be a problem, particularly where the communicating parties are in different physical locations. The parties must agree upon a key in secret, since anyone possessing the key can encrypt or decrypt messages. If the key is compromised, an eavesdropper can decrypt any messages encrypted to that key. The eavesdropper could also pretend to be one of the parties and produce false messages to fool the other party.
The Diffie-Hellman algorithm is a key exchange algorithm that allows two or more parties to agree on a secret key over an insecure channel without divulging the secret key. According to the Diffie-Hellman algorithm, the parties agree on two, non-secret prime numbers P
1
and P
2
which may be chosen at random with P
2
being typically a large prime number. The security of the system is based on the difficulty of factoring numbers as large as P
2
. Each party generates a large random integer, denoted X
1
and X
2
, respectively. The parties then calculate exchanged numbers Y
1
and Y
2
, respectively. The first party computes Y
1
using the equation Y
2
=P
1
X1
mod P
2
. The second party computes Y
2
using the equation Y
2
=P
1
X2
mod P
2
. The first party transmits Y
1
to the second party and second party transmits Y
2
to the first party. The first party computes the key K using the K=Y
2
X1
mod P
2
. The second party computes the key K using the equation K=Y
1
X2
mod P
2
. Since Y
2
X1
mod P
2
and Y
1
X2
mod P
2
both equal P
1
X1X2
mod P
2
, both parties compute the same key K. However, an eavesdropper cannot compute the key K with knowledge of only of P
1
, P
2
, Y
1
, and Y
2
. Therefore, the value K, which was computed independently by the two parties using information exchanged over the insecure channel, may be used by the parties as the secret key K for secure communications.
Typically, the parties using the Diffie-Hellman algorithm take turns exchanging information. Information sent in one direction triggers a response to be sent in the reverse direction until the encryption key is established. However, the second party normally receives the exchanged number Y
1
from the first party prior to the first party receiving the exchanged number Y
2
in return. Thus, the second party is in position to determine the encryption key K by combining the exchanged number received from the first party with the locally generated random number before the first party has received enough information to do likewise. Moreover, the second party can examine the encryption key K and decide that it does not suit a nefarious purpose and thus continue to generate further local random numbers until one is found that results in a desired encryption key K.
BRIEF SUMMARY OF THE INVENTION
The present invention establishes an encryption key between two or more parties in a manner that prohibits any party from forcing the value of the key to a desired value. The encryption key is based on exchanged values derived by each of the parties from random bitstrings. By incrementally sharing the exchanged values, the final value of the encryption key cannot be forced by one party to a certain value.
In one embodiment, the first party generates a first random number and computes a first exchanged number based on the first random number. The first exchanged number is split into at least two parts, with less than the total number of parts being sent to the second party to initiate a secure communication session. The second party generates a second random number, and then computes a second exchanged number based on the second random number. Because the second party does not yet have the remainder of the first exchanged number, the second party cannot choose a value for the second exchanged number that will force the encryption key to a desired value. The second exchanged number is then sent to the first party. The first party may then compute the encryption key. However, because the first party has already sent the second party a part of the first exchanged number, the first party likewise cannot force the value of the encryption key to a desired value. The first party sends the second party the remainder of the first exchanged number so that the second party can also determine the encryption key only after receiving at least a part of the second exchanged number.
More than two parties may take part in the establishment of the encryption key. Additionally, the exchanged numbers of each party may be split into more than two sections to further enhance the security of the key exchange procedure.
REFERENCES:
patent: 6185685 (2001-02-01), Morgan et al.
patent: 6615193 (2003-09-01), Kingdon et al.
patent: 6633980 (2003-10-01), Johnson
Shi et al., Signature based approach to fair document exchange, Communications, IEE Proceedings, vol. 150, Issue 1, Feb. 2003, pp. 21-27.*
Lin et al., Three-party encrypted key exchange without server public-keys, Comjmunication Letters, IEEE, Volumen 5, Issue 12, Dec. 2001, pp. 497-499.*
Moreau, Probabilistic encryption key exchange, Electronics Letters, vol. 31, Issue 25, Dec. 7, 1995, pp. 2166-2168.
Coats & Bennett PLLC
Ericsson Inc.
Jung David
LandOfFree
Method of incrementally establishing an encryption key 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 of incrementally establishing an encryption key, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of incrementally establishing an encryption key will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3308702