Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1998-07-23
2001-06-05
Barron, Jr., Gilberto (Department: 2131)
Cryptography
Particular algorithmic function encoding
Public key
C713S176000, C713S170000, C713S180000
Reexamination Certificate
active
06243467
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to cryptography and, more particularly, to the generation and verification of a discrete logarithm based digital signature on an elliptic curve using a reduced base tau expansion in non-adjacent form.
BACKGROUND OF THE INVENTION
The field of cryptography has spawned numerous devices and methods such as scramblers, symmetric-key encryptors, and public-key encryptors.
A scrambler is a device that receives an unencrypted message (i.e., plaintext) and produces an encrypted message (i.e., ciphertext). The encryption function of a scrambler is fixed in hardware and does not change from message to message. One of the problems with a scrambler is that the same plaintext will produce the same ciphertext. An adversary may collect ciphertext messages from a particular scrambler and compare them against each other in order to analyze a particular ciphertext message. To overcome this problem, the users may change the function of the scrambler periodically. Such a solution is time consuming and expensive.
Another solution to the problem associated with a scrambler is symmetric-key encryption. A symmetric-key encryptor has two inputs (i.e., plaintext and a cryptographic key). A cryptographic key is a message, or number, that should appear random to an adversary. A symmetric-key encryptor combines the cryptographic key with the plaintext using a scrambling function in order to generate ciphertext. The same plaintext may produce different ciphertext if the cryptographic key is changed. Since the cryptographic key is a message, or a number, it is much easier to change than the function of the scrambler which is built into hardware. In fact, the cryptographic key may be changed on a message to message basis without much difficulty. This method is called symmetric-key encryption because the intended recipient must possess the cryptographic key used to generate the ciphertext in order to recover the plaintext. The intended recipient must also possess a function that performs the inverse of the scrambling function used to generate the ciphertext. Typically, the inverse of the scrambling function may be the achieved by operating the scrambling function in reverse. If this is the case, the intended recipient must possess the same cryptographic key and the scrambling function used to generate the ciphertext in order to recover the plaintext.
Even though symmetric-key encryptors make the fastest encryptors they suffer from a few problems. The first problem is distributing cryptographic keys to authorized users in a secure fashion. A courier may be required to deliver the first cryptographic key to the users. This is time consuming and expensive. The second problem is knowing whether or not ciphertext came from a particular person. Anyone knowing the cryptographic key may encrypt or decrypt a message produced using a symmetric-key encryptor as long as they know the cryptographic key, the scrambling function, and the descrambling function.
U.S. Pat. No. 4,200,770, entitled “CRYPTOGRAPHIC APPARATUS AND METHOD,” discloses a device for and method of performing a cryptographic key exchange over a public channel. The method is often called a public-key key exchange method or the Diffie-Hellman key exchange method after the first two named inventors of U.S. Pat. No. 4,200,770. The Diffie-Hellman key exchange method uses the exponentiation function to allow two users to conceal and transmit their secret information to the other user. The users then combine what they received with their secret information in order to generate the same cryptographic key. To recover the secret information that was transmitted and construct the cryptographic key, an adversary would have to find the logarithm of what was transmitted. If the values involved are large enough the logarithm, or discrete log, problem is believed to be intractable. U.S. Pat. No. 4,200,770 is hereby incorporated by reference into the specification of the present invention. The Diffie-Hellman key exchange method offers a solution to the symmetric-key key distribution problem, but it does not solve the problem of verifying the identity of the sender of the ciphertext.
Asymmetric-key, or public-key, encryption was proposed as a solution to identifying the sender of the ciphertext. This problem is often referred to as being able to provide, and verify, a digital signature. Two different, but mathematically related, cryptographic keys are used in asymmetric-key, or public-key, encryption. Typically, a first, or secret, key is used to generate ciphertext while a second, or public, key is used to recover the plaintext. Each user possesses their own secret key and mathematically related public key. Each user keeps their secret key secret and makes their public key public. A first user may now generate ciphertext using their secret key and a second user may recover the corresponding plaintext using the corresponding public key. If the first user is the only person who knows the first user's secret key then the second user is assured that the ciphertext came from the first user.
In the example just given, anyone knowing the first user's public key, which is everyone, could recover the corresponding plaintext. If two users wish to communicate securely with some assurance that the message is from a particular person, the first user would encrypt the plaintext using the first user's secret key then the intended recipient's public key to encrypt the ciphertext and something to identify the first user. The recipient would then use their secret key to recover the ciphertext and the identification material. The identification material is then used to identify the public key of the first user. The first user's public key is then used to recover the plaintext. If the first user is the only one who know's the first user's secret key and the intended recipient is the only one who knows the recipient's secret key then the recipient is the only one who can recover the plaintext and is assured that the ciphertext came from the first user.
U.S. Pat. No. 4,405,829, entitled “CRYPTOGRAPHIC COMMUNICATIONS SYSTEM AND METHOD,” discloses one type of public-key encryption device and method known as RSA after the three names inventors Messrs. Rivest, Shamir, and Adleman. Although RSA uses exponentiation, an adversary is required to factor the product of two prime numbers used to generate the secret key from the chosen public key in order to recover plaintext. If the prime numbers are large enough, it is believed that the factoring problem is intractable. U.S. Pat. No. 4,405,829 is hereby incorporated into the specification of the present invention.
Taher ElGamal developed a public-key digital signature scheme based on the extended Euclidean algorithm. In this scheme, a first user generates a secret value x as the first user's secret key. The first user uses exponentiation to conceal the secret key and publishes the result (i.e., y=g{circumflex over ( )}x mod p) as the first user's public key. The first user then generates a random number k and uses exponentiation to conceal the random number (i.e., r=g{circumflex over ( )}k mod p). The result r is one of two values that will be used as a signature for a message m from the first user. Next, the first user generates an equation that includes the message m, the secret key x, the random number k, the first half of the signature r, and a variable that represents the second half of the signature s (i.e., m=xa+ks (mod p−1)). The first user then solves the equation for s and transmits the message, the public key, and the two halves of the signature (i.e., r,s) to the recipient. The recipient, knowing p and g, checks to see if (y{circumflex over ( )}r)(r{circumflex over ( )}s) mod p=g{circumflex over ( )}m mod p. If so, the recipient is assured that the transmission came from the first user.
The math associated with the ElGamal's digital signature scheme is complex and the digital signature is rather long. U.
Reiter Robert W.
Solinas Jerome A.
Barron Jr. Gilberto
Leaning Jeffrey Scott
Morelli Robert D.
The United States of America as represented by the National Secu
LandOfFree
Method of elliptic curve cryptographic digital signature... 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 elliptic curve cryptographic digital signature..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of elliptic curve cryptographic digital signature... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2457285