Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1997-08-29
2001-06-05
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
C380S277000, C380S286000
Reexamination Certificate
active
06243466
ABSTRACT:
BACKGROUND
1. Field of Invention
The field of this invention is cryptography. This invention relates to cryptosystems, and in particular to the escrowing and recovering of cryptographic keys and data encrypted under cryptographic keys. The escrow and recovery process assures that authorized entities like law-enforcement bodies, government bodies, users, and organizations, can when allowed or required, read encrypted data. The invention relates to cryptosystems implemented in software, but is also applicable to cryptosystems implemented in hardware. In particular, the invention relates to fast generation of cryptographic keys, and public certification thereof.
2. Description of Prior Art
Public Key Cryptosystems (PKC's) allow secure communications between two parties who have never met before. The notion of a PKC was put forth in (W. Diffie, M. Hellman, “New directions in cryptography”, IEEE Transactions on Information Theory, 22, pages 644-654, 1976). This communication can take place over an insecure channel. In a PKC, each user possesses a public key E and a private key D. E is made publicly available by a key distribution center, also called certification authority (CA), after the registration authority verifies the authenticity of the user (its identification, etc.). The registration authority is part of the certification authority. D is kept private by the user. E is used to encrypt messages, and only D can be used to decrypt messages. It is computationally impossible to derive D from E. To use a PKC, party A obtains party B's public key E from the key distribution center. Party A encrypts a message with E and sends the result to party B. B recovers the message by decrypting with D. The key distribution center is trusted by both parties to give correct public keys upon request. A PKC based on the difficulty of computing discrete logarithms was published in (T. ElGamal, “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”, CRYPTO '84, pages 10-18, Springer-Verlag, 1985).
Prior methods for conducting key escrow are U.S. Pat. Nos. 5,276,737, and 5,315,658 which are due to Micali (1994). In these patents Micali discloses a Fair Public Key Cryptosystem (FPKC) which is based on the work of P. Feldman (28th annual FOCS). The FPKC solution is not as efficient in terms of use as Auto-Escrowable and Auto-Certifiable Cryptosystems. Furthermore, It has been shown that the Fair RSA PKC does not meet certain needs of law enforcement (J. Kilian, F. Leighton, “Fair Cryptosystems Revisited”, CRYPTO '95, pages 208-221, Springer-Verlag, 1995), since a shadow public key cryptosystem can be embedded within it. A shadow public key system is a system that can be embedded in a key escrow system that permits conspiring users to conduct untappable communications. Kilian and Leighton disclose a Fail-safe Key Escrow system. This system has the drawback that it requires users to engage in a costly multi-round protocol in order to generate public/private key pairs. Other key escrow systems with similar inefficiencies are by De Santis et al., Walker and Winston (TIS), and the IBM SecureWay document. A “Fraud-Detectable Alternative to Key-Escrow Proposals” based on ElGamal has been described in (E. Verheul, H. van Tilborg, “Binding ElGamal: A Fraud-Detectable Alternative to Key-Escrow Proposals”, Eurocrypt '97, pages 119-133, Springer-Verlag, 1997). This system, called Binding ElGamal, provides for session level key recoverability, and makes no provision for preventing users from encrypting messages using the provided unescrowed public key infrastructure prior to using the Binding ElGamal system. Hence, it permits conspiring criminals to conduct untappable communications. Binding ElGamal also imposes a large amount of communication overhead per communications session. An overview of key escrow schemes appears in (D. Denning, D. Branstad, “A Taxonomy for Key Escrow Encryption Systems,” Communications of the ACM, v. 39, n. 3, 1996). In (N. Jefferies, C. Mitchell, M. Walker, “A Proposed Architecture for Trusted Third Party Services”, Cryptography: Policy and Algorithms, LNCS 1029, Springer, 1996) and (R. Anderson, “The GCHQ Protocol and Its Problems”, Eurocrypt '97, pages 134-148, Springer-Verlag, 1997) a trusted third party approach to escrow is described where the trusted third parties of the participating users are involved in every session key establishment stage, and hence provides for another cumbersome solution as well.
In the pending U.S. Pat. Nos. 08/864,839 and 08/878,189 (by Young and Yung), an auto-recoverable and auto-certifiable public key cryptosystem was disclosed that has the following properties. Users of the system can generate a public/private key pair and a certificate of recoverability. This certificate of recoverability can be used to both recover the private key by the escrow authorities, and verify that the private key is recoverable. The present invention draws many of its ideas from the Auto-Escrowable and Auto-Certifiable key escrow solution. The primary drawback of the auto-recoverable and auto-certifiable cryptosystem that was proposed is that it is not possible to easily generate very large cryptographic keys for use in the system. The patent of Young and Yung cites a 1024 bit prime, which is secure by todays standards. This number is a prime r such that 2r+1 is prime and such that 4r+3 is prime. The requirement that all three numbers r, 2r+1, and 4r+3 be prime is a constraint. A weaker constraint that eases the key generation would be a constraint between two numbers only. The present invention discloses an auto-recoverable and auto-certifiable cryptosystem which uses an entirely different algebraic structure for the escrow authority keys. Namely, the system uses a prime number p such that p=2tn+1. Here, t is a small strong prime and n is the product of two primes. With this algebraic structure for the prime p, keys of size 4096 bits or greater can be easily generated.
Another drawback of the Auto-Recoverable and Auto-Certifiable cryptosystem is that it does not provide a way to make public the certificates of recoverability without risking the introduction of a shadow public key system. The present invention discloses a way to blind the certificates, thereby allowing them to be published safely.
Both Binding ElGamal and the Auto-Escrowable and Auto-Certifiable Cryptosystems solutions employ the use of non-interactive zero-knowledge proofs. More specificly, they employ the Fiat Shamir heuristic which is disclosed in (A. Fiat, A. Shamir, “How to Prove Yourself: Practical Solutions to Identification and Signature Problems”, CRYPTO '86, pages 186-194, Springer-Verlag, 1987).
SUMMARY OF THE INVENTION
The present invention provides a method to verify that a user generated private key is contained within an encryption under the public key of the escrow authorities without excessive overhead. Furthermore, this verification can be performed by anyone in possession of the escrow authorities public key. The present invention consists of a setting up process and three functions which process signals in different ways. The functions are key generation, key verification, and key recovery. In the setup process of the prefered embodiment, the participants agree upon a set of initial public parameters and the authorities generate an escrowing public key and corresponding private keys. The initial parameters and the escrowing public key are the public parameters of the system. The escrowing authorities, Certification Authority (CA), and users of the system all have access to the public parameters. In the key generation process, the method generates a user's public/private key pair, and a certificate of recoverability which is a string of information which includes an encryption of the user's private key under the escrowing public key. The signal information containing the user's public key, and the certificate of recoverability can be transmited to any entity. In the verification pro
Young Adam Lucas
Yung Marcel Mordechay
Hayes Gail
Leaning Jeffrey Scott
Schweitzer Cornman Gross & Bondell LLP
LandOfFree
Auto-escrowable and auto-certifiable cryptosystems with fast... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Auto-escrowable and auto-certifiable cryptosystems with fast..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Auto-escrowable and auto-certifiable cryptosystems with fast... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2539147