Cryptography – Key management – Having particular key generator
Reexamination Certificate
1998-07-10
2001-10-23
Peeso, Thomas R. (Department: 2132)
Cryptography
Key management
Having particular key generator
C380S046000
Reexamination Certificate
active
06307938
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 date 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 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 M may require several encryption operations, depending on the length of M.
A method for computing digital signatures (e.g., 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
1. Choosing the public verification exponent, e,
2. Generating the private prime factors, p and q, and public modulus, n=pq, and
3. 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: The verifier treats the message and signature as (M′, &Sgr;′) until the signature verification is successful, and it is proven that M=M′ and &Sgr;=&Sgr;′. The signature &Sgr;′ is raised to the power e mod n in order to obtain the intermediate integer RR′. That is, RR′=(&Sgr;′)
e
mod n. The intermediate integer IR′ is then computed from RR′ as a function of the least significant (right most) bits of RR′. A sanity check is then performed on IR′, and if this step succeeds, the value of H(M)′ is then recovered from IR′. Finally, a hash is computed on the message M′, and the computed value of H(M′) is compared for equality with the recovered value of H(M)′. The verification process succeeds if the two values are equal and it fails if the two values are not equal.
The public exponent is a positive integer e, where 2≦e≦2
k−160
, and k is the length of the modulus n in bits. The public exponent may be selected as a fixed value or generated as a random value. When e is odd, the digital signature algorithm is called RSA. When e is even, the digital signature algorithm is called Rabin-Williams. Common fixed values for e are 2, 3, 17, and 2
16
+1=65,537.
The public modulus, n, is the product of two distinct positive primes, p and q (i.e., n=pq).
The private prime factors, p and q, are secretly and randomly selected by each signing entity. The private prime factors must satisfy several conditions, as follows:
1. Constraints on p and q relative to e are:
If e is odd, then e shall be relatively prime to both p−1 and q−1.
If e is even, then p shall be congruent to 3 mod 8, q shall be congruent to 7 mod 8, and e shall be relatively prime to both (p−1)
Matyas, Jr. Stephen M.
Roginsky Allen
International Business Machines - Corporation
Jack Todd
Peeso Thomas R.
Ray-Yarletts Jeanine S.
LandOfFree
Method, system and apparatus for generating self-validating... 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 generating self-validating..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system and apparatus for generating self-validating... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2599983