Cryptography – Particular algorithmic function encoding – Nbs/des algorithm
Reexamination Certificate
1996-10-11
2004-04-20
Buczinski, Stephen C. (Department: 3662)
Cryptography
Particular algorithmic function encoding
Nbs/des algorithm
C380S029000
Reexamination Certificate
active
06724893
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to cryptography and, more particularly, to a method of passing a cryptographic key so that an authorized third party may gain access to the key.
BACKGROUND OF THE INVENTION
Practitioners in the field of cryptography first occupied themselves with trying to find a mathematical function that an adversary could not determine. Theoretically, such functions exist (e.g., scramblers). However, such devices are not secure because such devices are easily reverse-engineered in order to determine the cryptographic function.
The notion that hardware could be kept secret was abandoned. An idea was then introduced to couple a secret random entity (i.e., a cryptographic key) to the hardware in order to keep communications secure even if the hardware was reverse engineered. In this scenario, each user received a copy of the hardware. Each pair, or group, of users who wished to communicate securely would decide on a cryptographic key. For convenience, the process was such that the cryptographic key could be used for both encryption and decryption hence the terms “symmetric-key” and “symmetric-key cryptography.” The cryptographic key decided upon was then securely given to each party to the communication. Typically, this meant that the cryptographic key had to be securely delivered to each user. Such a key distribution system works well with a closed group of users consisting of a small number, but it becomes unwieldy when the number of users is large. Also, if the symmetric-key is compromised, the communications of everyone using the key is compromised. Therefore, a need arose for a solution to the key distribution problem. Public-key cryptography offers such a solution.
U.S. Pat. No. 4,200,770, entitled “CRYPTOGRAPHIC APPARATUS AND METHOD,” is a patent on the first publicly disclosed method of arriving at a secret symmetric-key between two users using a non-secure channel. U.S. Pat. No. 4,200,770, commonly referred to as the Diffie-Hellman key exchange method, is hereby incorporated by reference into the specification of the present invention. In this key exchange method, each user generates a random number that is kept secret. Each user uses their secret as an exponent to a non-secret base that is shared in common with the other user (i.e., exponentiation). Each user modulo reduces their exponentiation by a non-secret number that is shared in common with the other user. Each user transmits their modulo reduced exponentiation to the other user. Each user raises the exponentiation they receive to their secret, and each user modulo reduces this second exponentiation by the same shared modulus. This results in each user computing the same value that is known only by them. In effect, each user conceals their secret (the exponent) in a mathematical function that is believed to be unsolvable for large values (i.e., modulo reduced exponentiation). Each user transmits their buried secret to the other user. Each user raises the other user's buried secret to their secret. After a final modulo reduction, each user is in possession of the same symmetric key that an adversary cannot mathematically determine. To mathematically determine the key, an adversary must be able to determine the discreet logarithm of what at least one user transmitted, hence the name “discreet logarithm problem.” This problem is considered unsolvable, or intractable, for large values.
Here, “key exchange” is defined as each user participating in the creation of a key. Neither participant knows in advance what the final key will be. This differs from a “key pass” which entails a single user creating a key and passing it securely to the other user. The receiving user recovers, or decrypts, the key but does not alter the key in any other way.
Along with the advantages of public-key cryptography there are some disadvantages. That is, public-key cryptography involves many more steps than does symmetric-key cryptography. This means that public-key cryptography is slow compared to symmetric-key cryptography. Also, a user using the Diffie-Hellman key exchange method cannot be sure that the other user is who they claim to be. Therefore, a need arose for a method of digitally signing an electronic communication.
Taher ElGamal, in a paper entitled “A Public Key Cryptosystem and Signature Scheme Based on Discreet Logarithms,” IEEE Transactions on Information Theory, Vol. IT-31, No. 4, July 1985, pp. 469-472, proposed an encryption method and a digital signature method that incorporates the strength of the Diffie Hellman key-exchange method (i.e., the discreet logarithm problem). ElGamal's signature method has received more attention than has his encryption method. ElGamal's signature method is based on Euler's Totient function. In this method, a first user generates a long term secret exponent and “hides” it in a modulo reduced exponentiation using a publicly known base and modulus. The user binds the result to his or her identity by a certifying authority. Next, the first user computes a number using a certain parameter (e.g. a message), his long-term secret, and a second per-message secret. These two secrets are known only by the first user. The first user sends the computed number, the modulo reduced exponentiation of the “per-message secret,” and the message to the second user. The second user uses the numbers, the message, and the certified modulo reduced exponentiation to verify a mathematical relationship. If the relationship is verified then the second user is assured that the message came from the first user. This may not be true if the long-term secret is known by an adversary. ElGamal's method creates a digital signature. The computations involved here are mathematically complex and time consuming. The resulting signature is large and requires a large amount of bandwidth in order to transmit it.
In a paper entitled “Efficient Identification and Signatures for Smart Cards,” Advances in Cryptology—Proceedings of CRYPTO '89, Lecture Notes in Computer Science, No. 435, Springer-Verlag, New York, 1990, pp. 239-251, Claus Schnorr developed a variation of ElGamal's digital signature that is simpler to compute and takes up less bandwidth than ElGamal's digital signature. Schnorr uses a subgroup of the group used by ElGamal. The subgroup Schnorr uses is smaller than the group used by ElGamal. The result is a faster, less compute intensive method that requires fewer bits to be transmitted. Schnorr's method was patented as U.S. Pat. No. 4,995,082 entitled “METHOD FOR IDENTIFYING SUBSCRIBERS AND FOR GENERATING AND VERIFYING ELECTRONIC SIGNATURES IN A DATA EXCHANGE SYSTEM.” U.S. Pat. No. 4,995,082 is hereby incorporated by reference into the specification of the present invention.
The National Institute of Standards and Technology (NIST) published Federal Information Process Standard (FIPS) Publication No. 186 entitled “Digital Signature Standard” (DSS). FIPS PUB 186 is hereby incorporated by reference into the specification of the present invention. The DSS discloses a method of generating a digital signature that is secure, reasonably easy to generate and verify, and bandwidth efficient. U.S. Pat. No. 5,231,668, entitled “Digital Signature Algorithm,” (DSA) embodies DSS. U.S. Pat. No. 5,231,668 is hereby incorporated by reference into the specification of the present invention. DSA is a bandwidth efficient variant of ElGamal. DSA employs the computations of ElGamal in a subgroup of the group used by ElGamal. The subgroup used in DSA is smaller than the group used by ElGamal.
In a paper entitled “Message Recovery for Signature Schemes Based on the Discreet Logarithm Problem,” Pre-proceedings of Eurocrypt '94, pp. 175-190, Ms. Nyberg and Mr. Rueppel developed a variant of DSA that eliminates the need to send the message while allowing the recovery of the message from what is transmitted. Nyberg and Rueppel also propose a key exchange method that is based on DSA and the Diffie-Hellman key exchange method. The steps of their message-recovery method is
Buczinski Stephen C.
Morelli Robert D.
The United States of America as represented by the National Secu
LandOfFree
Method of passing a cryptographic key that allows third... 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 passing a cryptographic key that allows third..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of passing a cryptographic key that allows third... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207654