Method and system for depositing private key used in RSA cryptosystem

• US 6,072,876 A
• Filed: 07/25/1997
• Issued: 06/06/2000
• Est. Priority Date: 07/26/1996
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Sugiyama, Hiroyuki, Okamoto, Tatsuaki, Okukawa, Moribumi, Obata, Masanori
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/900,978
• Time in Patent Office: 1,047 Days
• Field of Search: 380/21, 380/30, 380/278, 380/282, 380/285, 380/286
• US Class Current: 380/286
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/0825 using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

A scheme for depositing a private key used in the RSA cryptosystem which is capable of maintaining the private key more safely, without requiring a user to always carry around a storage medium. In this scheme, a private key of a user is divided into a first partial private key and a second partial private key at a user'"'"'s entity, where the first partial private key is set to be maintained at the user'"'"'s entity, while the second partial private key is deposited from the user'"'"'s entity to the other entity. Then, the second partial private key is delivered from the other entity to the user'"'"'s entity in response to a request from the user'"'"'s entity, and the first partial private key maintained at the user'"'"'s entity and the second partial private key delivered from the other entity are composed so as to obtain the private key to be used in a processing according to the RSA cryptosystem at the user'"'"'s entity. This scheme can be generalized to a case of dividing the private key into a plurality of partial private keys.

Claims

1. A method for depositing a private key used in an RSA cryptosystem, comprising the steps of:

dividing a private key of a user into a first partial private key and a second partial private key at a user'"'"'s entity, where the first partial private key is set to be maintained at the user'"'"'s entity;

depositing the second partial private key from the user'"'"'s entity to another entity;

delivering the second partial private key from said another entity to the user'"'"'s entity in response to a request from the user'"'"'s entity; and

composing the first partial private key maintained at the user'"'"'s entity and the second partial private key delivered from said another entity so as to obtain the private key to be used in a processing according to the RSA cryptosystem at the user'"'"'s entity.

2. The method of claim 1, wherein at the depositing step, the user'"'"'s entity encrypts the second partial private key by using an encryption key so as to obtain an encrypted second partial private key that can be decrypted by using a key decryption key known only to the user'"'"'s entity, and deposits the encrypted second partial private key;

at the delivering step, said another entity delivers the encrypted second partial private key; and

at the composing step, the user'"'"'s entity obtains the second partial private key by decrypting the encrypted second partial private key by using the key encryption key.

3. The method of claim 2, wherein the encryption key and the key decryption key are a symmetric key generated at the user'"'"'s entity.

4. The method of claim 3, wherein the symmetric key is given in a form of a hash value obtained from the first partial private key by using a one-way random hash function at the user'"'"'s entity.

5. The method of claim 2, wherein the encryption key is the second partial private key itself, and the key decryption key is formed by the first partial private key and a public key of the user.

6. The method of claim 5, wherein said another entity maintains the second partial private key along with the public key, and delivers the second partial private key and the public key at the delivering step;

and

at the composing step, the user'"'"'s entity forms the key decryption key from the first partial private key maintained at the user'"'"'s entity and the public key delivered from said another entity.

7. The method of claim 1, wherein at the depositing step, the user'"'"'s entity encrypts the second partial private key by using the second partial private key itself, further encrypts an encrypted second partial private key by using a symmetric key known only to the user'"'"'s entity so as to obtain a deposit key, and deposits the deposit key;

at the delivering step, said another entity delivers the deposit key; and

at the composing step, the user'"'"'s entity obtains the encrypted second partial private key by decrypting the deposit key by using the symmetric key, and obtains the second partial private key by decrypting the encrypted second partial private key by using the first partial private key and a public key of the user.

8. The method of claim 7, wherein the symmetric key is given in a form of a hash value obtained from the first partial private key by using a one-way random hash function at the user'"'"'s entity.

9. The method of claim 7, wherein said another entity maintains the second partial private key along with the public key, and delivers the second partial private key and the public key at the delivering step;

and

at the composing step, the user'"'"'s entity decrypts the encrypted second partial private key by using the first partial private key maintained at the user'"'"'s entity and the public key delivered from said another entity.

10. The method of claim 1, wherein the first partial private key is maintained at the user'"'"'s entity as a password memorized by the user.

11. The method of claim 10, wherein the user'"'"'s entity requests a delivery of the second partial private key to said another entity when the password is entered into the user'"'"'s entity by the user.

12. The method of claim 1, wherein the user'"'"'s entity requests a delivery of the second partial private key to said another entity when the user carries out the processing according to the RSA cryptosystem at the user'"'"'s entity.

13. The method of claim 1, wherein at the depositing step, the user'"'"'s entity also deposits prime numbers p and q that are used in generating the private key;

at the delivering step, said another entity also delivers the prime numbers p and q along with the second partial private key; and

the method further comprising the step of generating a new first partial private key and a new second partial private key which are different from the first partial private key and the second partial private key, without changing a public key of the user, by using the private key obtained at the composing step and the prime numbers p and q delivered at the delivering step.

14. A method for depositing a private key used in an RSA cryptosystem, comprising the steps of:

dividing a private key of a user into a plurality of partial private keys at a user'"'"'s entity, where one of said plurality of partial private keys is set to be maintained at the user'"'"'s entity;

depositing remaining ones of said plurality of partial private keys from the user'"'"'s entity to mutually different ones of other entities respectively;

delivering the remaining ones of said plurality of partial private keys from the other entities to the user'"'"'s entity in response to a request from the user'"'"'s entity; and

composing said one of said plurality of partial private keys maintained at the user'"'"'s entity and the remaining ones of said plurality of partial private keys delivered from the other entities so as to obtain the private key to be used in a processing according to the RSA cryptosystem at the user'"'"'s entity.

15. The method of claim 14, wherein at the depositing step, the user'"'"'s entity also deposits prime numbers p and q that are used in generating the private key to one of the other entities;

at the delivering step, said one of the other entities also delivers the prime numbers p and q along with one of the remaining ones of said plurality of partial private keys; and

the method further comprising the step of generating a plurality of new partial private keys which are different from said plurality of partial private keys, without changing a public key of the user, by using the private key obtained at the composing step and the prime numbers p and q delivered at the delivering step.

16. A system for depositing a private key used in an RSA cryptosystem, comprising a user'"'"'s entity and another entity, wherein the user'"'"'s entity includes:

a private key dividing unit for dividing a private key of a user into a first partial private key and a second partial private key, where the first partial private key is set to be maintained at the user'"'"'s entity;

a key depositing unit for depositing the second partial private key to said another entity;

a partial private key acquisition unit for requesting a delivery of the second partial private key to said another entity and receiving the second partial private key delivered from said another entity; and

a private key composition unit for composing the first partial private key maintained at the user'"'"'s entity and the second partial private key delivered from said another entity so as to obtain the private key to be used in a processing according to the RSA cryptosystem.

17. The system of claim 16, wherein the key depositing unit encrypts the second partial private key by using an encryption key so as to obtain an encrypted second partial private key that can be decrypted by using a key decryption key known only to the user'"'"'s entity, and deposits the encrypted second partial private key;

said another entity delivers the encrypted second partial private key in response to a request from the user'"'"'s entity; and

the private key composition unit obtains the second partial private key by decrypting the encrypted second partial private key by using the key encryption key.

18. The system of claim 17, wherein the encryption key and the key decryption key are a symmetric key generated at the user'"'"'s entity.

19. The system of claim 18, wherein the symmetric key is given in a form of a hash value obtained from the first partial private key by using a one-way random hash function at the user'"'"'s entity.

20. The system of claim 17, wherein the encryption key is the second partial private key itself, and the key decryption key is formed by the first partial private key and a public key of the user.

21. The system of claim 20, wherein said another entity maintains the second partial private key along with the public key, and delivers the second partial private key and the public key in response to a request from the user'"'"'s entity;

and

the private key composition unit forms the key decryption key from the first partial private key maintained at the user'"'"'s entity and the public key delivered from said another entity.

22. The system of claim 16, wherein the key depositing unit encrypts the second partial private key by using the second partial private key itself, further encrypts an encrypted second partial private key by using a symmetric key known only to the user'"'"'s entity so as to obtain a deposit key, and deposits the deposit key;

said another entity delivers the deposit key in response to a request from the user'"'"'s entity; and

the private key composition unit obtains the encrypted second partial private key by decrypting the deposit key by using the symmetric key, and obtains the second partial private key by decrypting the encrypted second partial private key by using the first partial private key and a public key of the user.

23. The system of claim 22, wherein the symmetric key is given in a form of a hash value obtained from the first partial private key by using a one-way random hash function at the user'"'"'s entity.

24. The system of claim 23, wherein said another entity maintains the second partial private key along with the public key, and delivers the second partial private key and the public key in response to a request from the user'"'"'s entity;

and

the private key composition unit decrypts the encrypted second partial private key by using the first partial private key maintained at the user'"'"'s entity and the public key delivered from said another entity.

25. The system of claim 16, wherein the first partial private key is maintained at the user'"'"'s entity as a password memorized by the user.

26. The system of claim 25, wherein the partial private key acquisition unit requests a delivery of the second partial private key to said another entity when the password is entered into the user'"'"'s entity by the user.

27. The system of claim 16, wherein the partial private key acquisition unit requests a delivery of the second partial private key to said another entity when the user carries out the processing according to the RSA cryptosystem at the user'"'"'s entity.

28. The system of claim 16, wherein the key depositing unit also deposits prime numbers p and q that are used in generating the private key;

said another entity also delivers the prime numbers p and q along with the second partial private key in response to a request from the user'"'"'s entity; and

the private key composition unit also generates a new first partial private key and a new second partial private key which are different from the first partial private key and the second partial private key, without changing a public key of the user, by using the private key obtained from the first partial private key and the second partial private key and the prime numbers p and q delivered from said another entity.

29. A system for depositing a private key used in an RSA cryptosystem, comprising a user'"'"'s entity and other entities, wherein the user'"'"'s entity includes:

a private key dividing unit for dividing a private key of a user into a plurality of partial private keys, where one of said plurality of partial private keys is set to be maintained at the user'"'"'s entity;

a key depositing unit for depositing remaining ones of said plurality of partial private keys to mutually different ones of the other entities respectively;

a partial private key acquisition unit for requesting a delivery of the remaining ones of said plurality of partial private keys to the other entities and receiving the remaining ones of said plurality of partial private keys delivered from the other entities; and

a private key composition unit for composing said one of said plurality of partial private keys maintained at the user'"'"'s entity and the remaining ones of said plurality of partial private keys delivered from the other entities so as to obtain the private key to be used in a processing according to the RSA cryptosystem.

30. The system of claim 29, wherein the key depositing unit also deposits prime numbers p and q that are used in generating the private key to one of the other entities;

said one of the other entities also delivers the prime numbers p and q along with one of the remaining ones of said plurality of partial private keys in response to a request from the user'"'"'s entity; and

the private key composition unit generates a plurality of new partial private keys which are different from said plurality of partial private keys, without changing a public key of the user, by using the private key obtained from said one and the remaining ones of said plurality of partial private keys and the prime numbers p and q delivered from the other entities.