Cryptography – Particular algorithmic function encoding
Reexamination Certificate
2000-10-19
2003-12-16
Decady, Albert (Department: 2131)
Cryptography
Particular algorithmic function encoding
C380S030000, C708S492000
Reexamination Certificate
active
06665405
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to data security, encryption, and, generating and using electronic signatures to verify the identity of a communicating party.
Most public key cryptosystems involve either a factoring problem or a discrete logarithm (DL) problem. The factoring problem is, given a not-prime number, find its complete factorization into prime numbers. The DL problem is, given a group G generated by g and an element h in G, find an integer m such that g
m
=h, that is, evaluate log
g
h. Several proposed schemes for public key cryptosystems rely on the computational difficulty of finding a DL in a multiplicative group of a finite field.
Public key cryptosystems encompass public key encryption schemes and digital signature schemes. Assume each user has a public key and a private key, which is not necessarily true for all schemes, and that party A wishes to send a secure message to party B. In a public key encryption scheme, party A uses party B's public key to encrypt, and then party B uses its own public and private keys to decrypt. In a digital signature scheme, party A uses its own public and private keys to prepare the message, and party B uses party A's public key to receive the message. That is, to prepare the message, in a public key encryption scheme, the sending party uses the receiving party's key information, whereas in a digital signature scheme, the sending party uses its own key information. To receive the message, in a public key encryption scheme, the receiving party uses its own key information, whereas in a digital signature scheme, the receiving party uses the sending party's key information.
In public key cryptosystems, all participants have a public key and a corresponding private key, as disclosed in U.S. Pat. No. 5,481,613 to Ford et al., entitled “Computer Network Cryptographic Key distribution System” which is incorporated herein by reference. A shared public key may refer to the portion of the public key common to multiple users, as disclosed in Scott A. Vanstone et al., “Short RSA Keys and Their Generation”, 8 Journal of Cryptology, pp. 101-114 (1995) and, U.S. Pat. No. 5,231,668 to Kravitz, entitled “Digital Signature Algorithm”, both of which are incorporated herein by reference.
For two participants to be able to communicate using a secret key cryptosystem, the participants must first agree on a secret key to use for their communication. A “shared” key in a secret key cryptosystem refers to the secret key agreed upon by the participants, as disclosed in U.S. Pat. No. 5,481,613 to Ford et al., entitled “Computer Network Cryptographic Key Distribution System”.
Typical digital signature schemes have three steps: system setup, signature generation by a sending party, and signature verification by a receiving party.
System setup is assumed to occur well before signing or encryption of a message. Generally, during system setup of a DL based public key cryptosystem, a prime number is selected and used to obtain a generator for a group, then a random number is selected and used as an exponent for the generator to produce a resulting value in the finite field. Determining the random number when only the generator and resulting value are known is a DL problem.
The outcomes of system setup are a public key and a private key. A public key is assumed to be public knowledge and comprises the prime number, the generator, the resulting value and possibly other parameters. A private key is assumed to be known only to the sending party, and comprises the random number.
During signature generation of a DL based public key cryptosystem, a second random number is chosen and used as an exponent for the generator to produce a second resulting value in the finite field. Determining the second random number when only the generator and second resulting value are known is a DL problem. Then a third value based on the private key, on the message to be signed, and second resulting value is obtained. The outcome of signature generation is a digital signature including the third value and at least one other parameter.
During signature verification of a DL based public key cryptosystem, the public key and third value portion of the signature are exponentially combined to produce a fourth result. If the fourth result is equal to at least one other parameter of the signature, then the signature is considered valid.
The exponentiation portions of system setup, signature generation and signature verification are computationally expensive and time consuming. Techniques are sought which will reduce the computational burden to an authorized user, particularly during signature generation, while maintaining computational difficulty for an unauthorized user.
SUMMARY OF THE INVENTION
In accordance with an aspect of this invention, a method of and an apparatus for determining public and private keys for a public key cryptosystem comprises selecting a first prime number, obtaining a cyclotomic polynomial evaluated at the first prime number, obtaining a second prime number which is a factor of the cyclotomic polynomial evaluated at the first prime number, finding a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number, obtaining a public value based on the generator and a selected integer, forming the public key to include the first and second prime numbers, the generator and the public value, and forming the private key to include the selected integer.
In accordance with a further aspect of this invention, the finite field may be represented with an optimal normal basis.
In accordance with a different aspect of this invention, the second prime number q satisfies (log
2
q)+1≈B, where B is a predetermined number of bits.
In accordance with another aspect of this invention, a control integer t′ is selected, and the cyclotomic polynomial is the t′-th cyclotomic polynomial, and the public key includes the control integer t′.
In accordance with still another aspect of this invention, a method of generating a digital signature for a message additionally selects a second integer, obtains a first signature value based on the second integer and the generator, obtains a second signature value based on the first signature value and the message, and forms the digital signature to include the first and second signature values.
A method of verifying a thus-formed digital signature for a message finds an inverse integer which is the inverse of the second signature value, finds a first intermediate value based on the inverse integer and the message, finds a second intermediate value based on the inverse integer and the first signature value, finds a third intermediate value based on the generator, the public value, and the first and second intermediate values, and determines that the signature is valid when the third intermediate value is equal to the first signature value.
A method of determining a shared key for a public key cryptosystem selects a first prime number, obtains a cyclotomic polynomial evaluated at the first prime number, obtains a second prime number which is a factor of the cyclotomic polynomial evaluated at the first prime number, finds a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number, selects an integer, receives an intermediate value which is based on the generator, and forms the shared key as a function of the intermediate value and the integer.
A method for secure communication of a message selects a first prime number, obtains a cyclotomic polynomial evaluated at the first prime number, obtains a second prime number which is a factor of the cyclotomic polynomial evaluated at the first prime number, finds a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number, selects an integer, receives an intermediate value which is based on the generator, forms the shared key as a function of t
Citibank N.A.
De'cady Albert
Seal James
LandOfFree
Cyclotomic polynomial construction of discrete logarithm... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cyclotomic polynomial construction of discrete logarithm..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cyclotomic polynomial construction of discrete logarithm... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3121073