Cryptography – Key management – Having particular key generator
Reexamination Certificate
1998-07-02
2002-02-05
Hayes, Gail (Department: 2131)
Cryptography
Key management
Having particular key generator
Reexamination Certificate
active
06345098
ABSTRACT:
BACKGROUND OF THE INVENTION
Cryptography is a security mechanism for protecting information from unintended disclosure by transforming the information into a form that is unreadable to humans, and unreadable to machines that are not specially adapted to reversing the transformation back to the original information content. The cryptographic transformation can be performed on data that is to be transmitted electronically, such as an electronic mail message, and is equally useful for data that is to be securely stored, such as the account records for customers of a bank or credit company.
In addition to preventing unintended disclosure, cryptography also provides a mechanism for preventing unauthorized alteration of data transmitted or stored in electronic form. After the data has been transformed cryptographically, an unauthorized person is unlikely to be able to determine how to alter the data, because the specific data portion of interest cannot be recognized. Even if the unauthorized user knew the position of the data portion within a data file or message, this position may have been changed by the transformation, preventing the unauthorized person from merely substituting data in place. If an alteration to the transformed data is made by the unauthorized user despite the foregoing difficulties, the fact of the alteration will be readily detectable, so that the data will be considered untrustworthy and not relied upon. This detection occurs when the transformation is reversed; the encrypted data will not reverse to its original contents properly if it has been altered. The same principle prevents unauthorized addition of characters to the data, and deletion of characters from the data, once it has been transformed.
The transformation process performed on the original data is referred to as “encryption.” The process of reversing the transformation, to restore the original data, is referred to as “decryption.” The terms “encipher” and “decipher” are also used to describe these processes, respectively. A mechanism that can both encipher and decipher is referred to as a “cipher.” Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption on a plaintext input block, using an encryption key, to produce a ciphertext output block. “Plaintext” refers to the fact that the data is in plain, unencrypted form. “Ciphertext” refers to the fact that the data is in enciphered or encrypted form. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the original plaintext block.
A cipher to be used in a computer system can be implemented in hardware, in software, or in a combination of hardware and software. Hardware chips are available that implement various ciphers. Software algorithms are known in the art as well.
Encryption systems fall into two general categories. Symmetric (or secret key) encryption systems use the same secret key for both encrypting and decrypting messages. An example of a symmetric encryption system is the Data Encryption Standard (DES) system, which is a United States federal standard described in a National Institute of Standards and Technology Federal Information Processing Standard (FIPS Pub 46). In the DES system, a key having 56 independently specified bits is used to convert 64-bit plaintext blocks to 64-bit ciphertext blocks, or vice versa.
Asymmetric (or public key) encryption systems, on the other hand, use two different keys that are not feasibly derivable from one another, one for encryption and another for decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, since only he has the private key. One of the best-known known asymmetric encryption systems is the RSA encryption system, named for its originators Rivest, Shamir, and Adleman, and described in U.S. Pat. No. 4,405,829 to Rivest et al., “Cryptographic Communications System and Method.”
A public key system is frequently used to encrypt and transmit secret keys for use with a secret key system. A public key system is also used to provide for digital signatures, in which the sender encrypts a signature message using his private key. Because the signature message can only be decrypted with the sender's public key, the recipient can use the sender's public key to confirm that the signature message originated with the sender.
A commonplace method, for both signature generation and signature verification, is to reduce the message M (to be signed) by means of a cryptographic hash function, in which case, the hash of the message, H(M), is signed instead of the message M itself. Signing H(M) requires only one encryption operation whereas signing M may require several encryption operations, depending on the length of M.
One of the serious concerns regarding most public key cryptography systems is that, since some public keys can be weaker (although very few, some are easier to “break” than others), an ill intentioned party may deliberately generate such a weaker key to be used to encrypt certain valuable information or to electronically sign a document. This party, if it finds it useful for its purposes, may claim that since the “weak” key was used for a particular transaction, an attacker could decrypt the message or forge a signature. This cheating user can then require the annulment of the transaction or other actions based on such a weakness in the key. For example, if a key used in the Elliptic Curve cryptography system is such that the private key, usually denoted as d, is short, then the encryption can be solved much faster than in the general case. A danger is becoming even more apparent when one is dealing with cryptography systems based on a popular and widely accepted RSA algorithm.
Such a danger exists only when the cheating party (often referred to as “the first party” in the situations described above since the party is responsible for the generation of the key which constitutes the first step in the encryption or in a signing protocol) puts a significant effort into generating such “bad” keys since the probability of obtaining one at random is extremely small. The purpose of this invention is to develop a protocol which will ultimately stop these efforts of a first party attacker and thus assure all parties in the quality of the public keys and in the non-repudiation of the signatures generated.
The approach herein is described with respect to the RSA signature algorithm although it is equally applicable to use in other public key cryptography systems requiring the generation of primes.
A method for computing digital signatures with the RSA algorithm is described in ANSI Standard X9.31-1998 Digital Signatures Using Reversible Public Key Cryptography For The Financial Services Industry (rDSA). ANSI Standard X9.31 defines procedures for:
i. Choosing the public verification exponent, e,
ii. Generating the private prime factors, p and q, and public modulus, n=pq, and
iii. Calculating the private signature exponent, d.
The procedure for signing a message M (signature production) consists of the following steps: M is hashed using a cryptographic hash function H to produce a hash value H(M). H(M) is then encapsulated within a data structure IR, a representative element RR is computed from IR, and RR is raised to the power d modulo n. The signature &Sgr; is either the result or its complement to n, whichever is smaller. That is, &Sgr;=min{RR
d
mod n, n−(RR
d
mod n)}. The signature &Sgr; is exactly one bit less in length than the length of the modulus n. The message and signature (M, &Sgr;) are then sent to the receiver for verification.
The procedure for verifying a signature (signature verification) consists of the following steps: Th
Matyas, Jr. Stephen M.
Roginsky Allen
Doubet Marcia L.
Hayes Gail
Leaning Jeffrey
Ray-Yarletts Jeanine S.
LandOfFree
Method, system and apparatus for improved reliability in... 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, system and apparatus for improved reliability in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system and apparatus for improved reliability in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2964434