Auto-Recoverable and Auto-certifiable cryptosystems with RSA or factoring based keys

• US 6,389,136 B1
• Filed: 09/17/1997
• Issued: 05/14/2002
• Est. Priority Date: 05/28/1997
• Status: Expired due to Term

• Current Assignee: CryptoPeak Security, LLC (Brian Yates)
• Original Assignee: Adam Lucas Young, Marcel Mordechay Yung
• Inventors: Young, Adam Lucas, Yung, Marcel Mordechay
• Primary Examiner(s): Elmore, Reba I.
• Application Number:
  US08/932,639
• Time in Patent Office: 1,700 Days
• Field of Search: 380/21.25, 380/44, 380/30, 380/28, 713/156, 713/180
• US Class Current: 380/28
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

A method is provided for an escrow cryptosystem that is essentially overhead-free, does not require a cryptographic tamper-proof hardware implementation (i.e., can be done in software), is publicly verifiable, and cannot be used subliminally to enable a shadow public key system. The keys generated are based on composite numbers (like RSA keys). A shadow public key system is an unescrowed public key system that is publicly displayed in a covert fashion. The keys generated by the method are auto-recoverable and auto-certifiable (abbrev. ARC). The ARC Cryptosystem is based on a key generation mechanism that outputs a public/private key pair, and a certificate of proof that the key is recoverable by the escrow authorities. Each generated public/private key pair can be verified efficiently to be escrowed properly by anyone. The verification procedure does not use the private key. Hence, the general public has an efficient way of making sure that any given individual'"'"'s private key is escrowed properly, and the trusted authorities will be able to access the private key if needed. Since the verification can be performed by anyone, there is no need for a special trusted entity, known in the art as a “trusted third party”. Furthermore, the system is designed so that its internals can be made publicly scrutinizable (e.g., it can be distributed in source code form). This differs from many schemes which require that the escrowing device be tamper-proof hardware. The system is efficient and can be implemented as a “drop-in” replacement to an RSA or Rabin cryptosystem. The system is applicable for law-enforcement, file systems, e-mail systems, certified e-mail systems, and any scenario in which public key cryptography can be employed and where private keys or information encrypted under public keys need to be recoverable. Another aspect of the system is the possibility to organize it in a hierarchical tree structure, where each element in the tree is an escrow authority (or authorities) capable to recover keys and/or information encrypted under these keys within the subtree rooted at the authority (or authorities) and only within this subtree.

Claims

1. A method for generating public keys where the users public key is a key-based on a composite number, and a proof that the keys are known to the user and are recoverable, comprising the steps of:

the user'"'"'s system generating a random string of bits based on system parameters;

the user running a key generation algorithm to get a secret and public key pair using the random string and public parameters;

the user constructing a proof being a string of bits whose public availability does not compromise the secret key, but at the same time provides confidence to an individual verifying entity that said secret key is known to its user and is recoverable.

3. A method and apparatus for registering users into a Public Key Infrastructure (PKI) such that a user and his public key, which is based on a composite, is registered only upon verifying that the key is known and recoverable, comprising the steps of:

the user generating the keys as in claim 1, and in addition;

the user proving its identity to a registration authority;

the user sending to the registration authority the public key and a proof of the fact that the private key is known and recoverable;

if the registration authority is convinced of the validity of said fact and of the user'"'"'s identity, then a certification authority issues a certificate for user'"'"'s said public key.

4. A method and apparatus as in claim 3 wherein the registration authority, after verifying the validity of said public key, publishes said public key in a public key database, together with the user ID.

5. A method and apparatus as in claim 3 wherein the registration authority certifies the public key of said user by signing user'"'"'s said public key using said registration authority'"'"'s secret key, and where said registration authority retains the proof of the fact that the private key is known and recoverable as a “

certificate of recoverability”

.

2. A method for generating public keys where the users public key is a key based on a composite number, and a proof that the keys are known to their user and are recoverable, comprising the steps of:

the user'"'"'s system generating a random string of bits based on system parameters;

the user running a key generation algorithm based on system parameters to get a secret and public key pair using the random string and public parameters;

the user engaging in a protocol with an entity whereby said entity repeatedly sends a challenge string and said user sends a response based on the challenge and the public and private key pair such that the public availability of said challenges and responses does not compromise the secret key, but at the same time provides confidence that said secret key is known and recoverable.

6. A method and apparatus for a key recovery agent to recover the user'"'"'s private key, where said public key is based on a composite number, that uses at least one of the certified public key of said user available in the public key directory, information contained in said user'"'"'s certificate of recoverability retained by certification authority, and public parameters, comprising of the following steps:

the key recovery agent reading the user'"'"'s certified public key from the public key directory;

running an information recovery algorithm based on the following inputs;

said user'"'"'s certified public key, the public system parameters, and the private key of said recovery agent;

running said information recovery algorithm resulting in the secret information of said user.

7. A method and apparatus for a plurality of key recovery agents to recover the user'"'"'s private key or information encrypted under said user'"'"'s corresponding public key, where said public key is a composite, that uses at least one of the certified public key of said user available in the public key directory, information contained in said users certificate of recoverability, and public parameters, comprising of the following steps:

a subset of said plurality of key recovery agents obtain said user'"'"'s public key;

each member of said subset runs a key recovery algorithm based on the following inputs;

said user'"'"'s certified public key, the public system parameters, and the private key of said member of said subset;

running said key recovery algorithm resulting in a partial result of member of said subset;

all said partial results of said members of said subset are combined using a software algorithm or a tamper-proof hardware implementation of it, to generate said private key of said user or said information encrypted under said user'"'"'s public key.

8. An apparatus for generating public keys which can be used in a public key encryption algorithm to encrypt data and a proof that the keys were generated by a specific algorithm comprising one or more of the following steps:

generating a seed s which is used in conjunction with a hash function F s.t. F(s) contributes to half of the entropy in the generation of n;

generating a composite n and a public exponent e;

generating M quadratic residues Q1,Q2, . . . , QM mod n;

computing two ambivalent roots ri,1 and ri,2 for each quadratic residue Qi;

committing to each of the 2M roots by preprocessing it and by raising the result to the Eth power mod N;

generating the challenge bits bi using a hash function H, the Qi and the Ci,j;

setting Zi to be either ri,1 or ri,2 based on challenge bit bi;

outputing the Qi, Ci,j, Zi;

outputing s;

where the user'"'"'s public key is n and the user'"'"'s private key is p, or the inverse of the users public exponent e mod (p−

1) (q−

1) and where the proof P that the public key n is known and recoverable is the string P=((Q1,C1,1,C1,2), . . . , (QM,CM,1,CM,2),Z1, . . . , ZM) and where the proof P may also include s.

10. An apparatus for enabling an individual verifying entity to verify the recoverability of a private key where said private key can be used to decrypt data, generated as in claim 8 comprising the steps of:

the entity obtaining the public key n and the proof P which was supposed to have been computed as in claim 8;

the entity verifying the proof P as constructed in claim 8;

where if any of the verifications fail then the verifying entity assumes that the private key is not recoverable by the escrow authorities and where otherwise, it is assumed that the private key is recoverable by the escrow authorities.

11. An apparatus for an entity to verify the recoverability of a private key as in claim 10, taking the subsequent action of informing the entity whether or not the private key is escrowed properly or not.

13. A method and apparatus as in claim 10 wherein the function that verify recoverability are implemented as a hardware device.

9. An apparatus for generating public keys which can be used in a public key encryption algorithm to encrypt data and proving that the keys were generated by a specific algorithm comprising of one or more of the following steps performed in an arbitrary order:

generating a seed s which is used in conjunction with a hash function F s.t. F(s) contributes to half of the entropy in the generation of n;

generating a composite n and a public exponent e;

generating M quadratic residues Q1, Q2, . . . , QM mod n;

computing two ambivalent roots ri,1 and ri,2 for each quadratic residue Qi;

committing to each of the 2M roots by raising each root after a possible preprocessing to the Eth power mod N;

sending n and the Qi to the verifier;

sending s to the verifier;

the verifier sends the prover M randomly chosen challenge bits bi;

the prover sends to the verifier the M roots corresponding to the M challenge bits;

the verifier verifies that s correctly contributes to half of the entropy of n;

the verifier verifies that the roots are indeed valid roots of the Qi;

the verifier verifies that the roots are indeed the plaintexts in the M commitments that are opened;

the verifier verifies that no pair of commitments corresponding to Qi contain two non-ambivalent roots of Qi;

the verifier verifies other facts about the values, including that the values that the prover sends lie in the correct sets, and that n<

N;

where the user'"'"'s public key is n and e, and the user'"'"'s private key is p, or the inverse of the users public exponent e mod (p−

1)(q−

1).

12. A method for key generation that outputs a public key which is based on a composite number and which can be used to encrypt data, private key which can be used to decrypt data, and a proof that the private key is recoverable by another entity or entities, wherein the proof contains an implicit encryption of the generated private key under said another entity or entities keys.

14. A method for key escrow where each user'"'"'s public key, which is based on a composite, is accompanied by a publicly available self-certifying proof which enables anyone to verify that the corresponding private key is recoverable by another entity or entities.

15. A method and apparatus for generating public keys which can be used to encrypt data, verifying the recoverability of the corresponding private keys, and recovering said private keys in a key escrow system in the form of a hierarchical tree, with the property that a given node in the tree is able to decrypt the communications of all nodes in the subtree for which it is root, and with the property that no node can decrypt the communications of any node outside of the subtree for which it is root.

16. A method and apparatus as in claim 15, wherein the hierarchical tree structure is determined by each user separately.

17. A method and apparatus for generating a composite n which can be used as a public key to encrypt data and a seed s that uses a one-way hash function which is applied to s to represent half of the bits of n in order to avoid a potential abuse of the subliminal channel present in n.

18. A method and apparatus that takes n and s which were generated as in claim 17 and outputs true if and only if n contains no subliminal channel abuse of significant bandwidth, otherwise false is output.

19. A hierarchical tree organization of escrow agents which is employed as a certified mail service where each node in a tree is able to perform the services of each node in its subtree thus increasing the availability of the certified mail service.