Multifactor split asymmetric crypto-key with persistent key security

• US 7,734,045 B2
• Filed: 05/05/2006
• Issued: 06/08/2010
• Est. Priority Date: 05/05/2006
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: TriCipher, Inc. (Broadcom, Inc.)
• Inventors: Sandhu, Ravinderpal Singh, Desa, Colin Joseph, Ganesan, Ravi, Schoppert, Brett Jason, Bellare, Mihir
• Primary Examiner(s): Tran; Ellen
• Assistant Examiner(s): Ambaye; Samuel
• Application Number:
  US11/381,829
• Publication Number:
  US 20070258585A1
• Time in Patent Office: 1,495 Days
• Field of Search: 380/44, 380/45, 380/28, 380/30, 380/286, 380/277, 380/282, 713/155, 713/171, 713/156, 726 3- 7
• US Class Current: 380/44
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

A processor generates an asymmetric crypto-key, such as an RSA crypto-key, which is associated with the user and includes a private key and a public key. It computes a first key portion based on a stored random number generation function, which has one or more constants such as a salt and/or iteration count, and a first value of a constant, and a second key portion based on the computed first key portion and one of the private key and the public key. It additionally computes another first key portion based on the stored random number generation function and a second value of that constant, and another second key portion based on the computed other first key portion and the one key. The computed first and second key portions and the computed other first and second key portions form first and second splits of the one key of the asymmetric crypto-key.

Claims

1. A system for generating an asymmetric crypto-key associated with a user, comprising:

a storage device configured to store a random number generation function having a constant; and

a processor configured with logic to (i) generate an asymmetric crypto-key associated with the user, the asymmetric crypto-key including a private key and a public key, (ii) compute a first key portion based on the stored random number generation function and a first value of the constant, and compute the second key portion based on the computed first key portion and one of the private key and the public key, wherein the computed first key portion and the computed second key portion form a first split of the one key of the user asymmetric crypto-key, and (iii) compute another first key portion based on the stored random number generation function and a second value of the constant, different than the first constant value, and compute another second key portion based on the computed other first key portion and the one key, wherein the computed other first key portion and the computed other second key portion form a second split of the one key of the user asymmetric crypto-key.

2. The system according to claim 1, wherein:

the stored random number generation function is the Public Key Cryptography Standard-5 (PKCS-5) algorithm; and

the constant is one of a salt and an iteration count.

3. The system according to claim 1, wherein:

the constant is a first constant;

the stored random number generation function also includes a second constant;

the processor further configured to (i) compute the first key portion based also on a first value of the second constant, and (ii) compute the other first key portion based also on a second value of the second constant, wherein the second value of the second constant is different than the first value of the second constant.

4. The system according to claim 3, wherein:

the stored random number generation function is the PKCS-5 algorithm;

the first constant is a salt; and

the second constant is an iteration count.

5. The system according to claim 1, wherein:

the second key portion is computed in accordance with the formula;

D_U1*D_U2=D_u mod Φ

(N_U), where D_U represents the one key of the generated user asymmetric crypto-key, D_U1 represents the computed first key portion, and D_U2 represents the second key portion to be computed; and

the other second key portion is computed in accordance with the formula;

D_U1′

*D_U2′

=D_U mod Φ

(N_u), where D_U represents the one key of the generated user asymmetric crypto-key, D_U1′

represents the computed other first key portion, and D_U2′

represents the other second key portion to be computed.

6. The system according to claim 1, wherein:

the stored random number generation function also has multiple factors, including a first factor and a second factor; and

the processor is further configured to compute the first key portion based also on a value of the first factor and a value of the second factor, and the other first key portion based also on the value of the first factor and the value of the second factor.

7. The system according to claim 6, wherein:

the first factor corresponds to a password of the user; and

the second factor corresponds to one of another private key and another public key of another asymmetric crypto-key which includes the other private key and the other public key.

8. The system according to claim 7, wherein:

the storage device is further configured to also store a value of the one other key of the other asymmetric crypto-key;

the processor is further configured to receive a user input representing the user password;

the first key portion is computed based on the received user password and the stored value of the one other key of the other asymmetric crypto-key; and

the other first key portion is computed based on the received user password and the stored value of the one other key of the other asymmetric crypto-key.

9. The system according to claim 7, further comprising:

a removable storage device configured to be temporarily interconnected with the processor, and to store a value of the one other key of the other asymmetric crypto-key;

wherein the processor is further configured to receive a user input representing the user password;

wherein the first key portion is computed based on the received user password and the stored value of the one other key of the other asymmetric crypto-key, and the other first key portion is computed based on the received user password and the stored value of the one other key of the other asymmetric crypto-key.

10. The system according to claim 6, wherein:

the storage device is further configured to store a value of one of the first factor and the second factor; and

both the first key portion and the other first key portion are computed based on the stored value of the one factor.

11. A method for generating an asymmetric crypto-key associated with a user, comprising:

generating an asymmetric crypto-key associated with the user, the asymmetric crypto-key including a private key and a public key;

computing a first key portion based on a random number generation function having a constant, and a first value of the constant;

computing the second key portion based on the computed first key portion and one of the private key and the public key;

computing another first key portion based on the random number generation function and a second value of the constant, different than the first constant value; and

computing another second key portion based on the computed other first key portion and the one key;

wherein the computed first key portion and the computed second key portion form a first split of the one key of the asymmetric crypto-key, and the computed other first key portion and the computed other second key portion form a second split of the one key of the asymmetric crypto-key.

12. The method according to claim 11, wherein:

the random number generation function is the PKCS-5 algorithm; and

the constant is one of a salt and an iteration count.

13. The method according to claim 11, wherein:

the constant is a first constant;

the random number generation function also includes a second constant;

the first key portion is computed based also on a first value of the second constant;

the other first key portion is computed based also on a second value of the second constant; and

the second value of the second constant is different than the first value of the second constant.

14. The method according to claim 13, wherein:

the random number generation function is the PKCS-5 algorithm;

the first constant is a salt; and

the second constant is an iteration count.

15. The method according to claim 11, wherein:

the second key portion is computed in accordance with the formula;

D_U1*D_U2=D_U mod Φ

(N_U), where D_U represents the one key of the generated asymmetric crypto-key, D_U1 represents the computed first key portion, and D_U2 represents the second key portion to be computed; and

the other second key portion is computed in accordance with the formula;

D_U1′

*D_U2′

=D_U mod Φ

(N_U), where D_U represents the one key of the generated asymmetric crypto-key, D_U1′

represents the computed other first key portion, and D_U2′

represents the other second key portion to be computed.

16. The method according to claim 11, wherein:

the random number generation function also has multiple factors, including a first factor and a second factor;

the first key portion is computed based also on a value of the first factor and a value of the second factor; and

the other first key portion is computed based also on the value of the first factor and the value of the second factor.

17. The method according to claim 16, wherein:

the first factor corresponds to a password of the user; and

the second factor corresponds to one of another private key and another public key of another asymmetric crypto-key which includes the other private key and the other public key.

18. The method according to claim 17, further comprising:

receiving the user password;

wherein the first key portion is computed based on the received user password and a value of the one other key of the other asymmetric crypto-key, and the other first key portion is computed based on the received user password and the value of the one other key of the other asymmetric crypto-key.

19. The method according to claim 17, further comprising:

storing a value of the one other key of the other asymmetric crypto-key; and

receiving a user input representing the user password;

wherein the first key portion is computed based on the received user input and the stored value of the one other key of the other asymmetric crypto-key, and the other first key portion is computed based on the received user input and the stored value of the one other key of the other asymmetric crypto-key.

20. The method according to claim 16, further comprising:

persistently storing a value of one of the first factor and the second factor;

wherein both the first key portion and the other first key portion are computed based on the stored value of the one factor.