MASKING THE OUTPUT OF RANDOM NUMBER GENERATORS IN KEY GENERATION PROTOCOLS

• US 20110307698A1
• Filed: 06/11/2010
• Published: 12/15/2011
• Est. Priority Date: 06/11/2010
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vanstone, Scott Alexander
• Granted Patent: US 8,429,408 B2
• Time in Patent Office: Days
• US Class Current: 713/171
• 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/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds

Abstract

To mitigate the effects of a weak random number generator (RNG) in a public key cryptosystem, a public key obtained from the RNG is encrypted using a deterministic cryptographic scheme before being made publicly available. A trusted party receiving the encrypted public key can recover the public key and combine it with other information so it is not subject to direct scrutiny. In one embodiment, the trusted party incorporates the public key in a certificate, such as an implicit certificate, for use by the correspondents in other communications.

Claims

1. A method of establishing a private key for use in a public key cryptographic system established between computing devices, each computing device having a cryptographic unit to perform cryptographic operations, said method comprising:

establishing at one of said devices a private value from an output of a random number generator,

computing a corresponding public key from said private value,

encrypting said corresponding public key using a deterministic encryption scheme to establish an encrypted public key and forwarding said encrypted public key to a computing device acting as a trusted party,

receiving from said trusted party encrypted private key reconstruction data,

applying a decryption key to recover said private key reconstruction data; and

computing said private key from said private key reconstruction data, said private key being a discrete log private key corresponding to a discrete log public key made available to the other of said computing devices, whereby said private key may be used in a transfer of information with a recipient of said corresponding discrete log public key.

2. The method according to claim 1, wherein said private key reconstruction data is decrypted with a key corresponding to a combination of said private value and publically available data.

3. The method according to claim 2, wherein said publically available data is a public key of said trusted party.

4. The method according to claim 1, wherein said deterministic encryption scheme is an RSA encryption scheme, and is performed using an RSA public key of said trusted party.

5. The method according to claim 1, wherein said one device receives an implicit certificate from said trusted party, said implicit certificate containing public key reconstruction data and an identity of said one device.

6. The method according to claim 5, wherein said private key reconstruction data is a combination of said implicit certificate, an ephemeral private key of said trusted party and a long term private key of said trusted party.

7. The method according to claim 5, wherein said private key reconstruction data has the form ex_CA+k_CA (mod n), wherein

e is a hash of said implicit certificate,

x_CA is an ephemeral private key of said trusted party,

k_CA is a long term private key of said trusted party,

and n is the order of a group over which said cryptographic system is implemented.

8. A computing device for use in a cryptographic system to exchange information with other devices using public key cryptographic protocols, said device comprising:

a cryptographic unit having a random number generator;

a memory to store parameters of said cryptographic system; and

an arithmetic logic unit to perform cryptographic operations, wherein said cryptographic unit is operable to;

generate a public key from an output of said random number generator;

encrypt said public key with a deterministic encryption scheme;

forward said encrypted public key to a trusted party;

receive encrypted private key reconstruction data from said trusted party; and

obtain therefrom a private key for use in communications with other devices.

9. The computing device according to claim 8, wherein said memory includes an RSA public key of said trusted party, and wherein said cryptographic unit is further operable to utilise said RSA public key to encrypt said public key.

10. The computing device according to claim 8, wherein said cryptographic unit is further operable to retrieve said output of said random number generator and combine it with publically available data to obtain a decryption key for said encrypted private key reconstruction data.

11. The computing device according to claim 10, wherein said memory includes a discrete log public key of said trusted party and said cryptographic unit utilizes said discrete log public key as said publically available data.

12. A method of one computing device, acting as a trusted party, generating a certificate, for use by another correspondent in a public key cryptographic system, said method comprising:

receiving from said another correspondent an encrypted public key;

decrypting said public key using a deterministic encryption scheme to obtain said public key;

utilising said public key to generate private key reconstruction data for use by said another correspondent;

encrypting said private key reconstruction data; and

forwarding said encrypted private key reconstruction data to said another correspondent.

13. The method according to claim 12, wherein said encrypting said private key reconstruction data comprises combining said public key and a private key of said one computing device to obtain a new key, and encrypting said private key reconstruction data using said new key.

14. The method according to claim 13, wherein said private key reconstruction data has the form ex_CA+k_CA (mod n), wherein:

e is a hash of an implicit certificate,

x_CA is an ephemeral private key of said trusted party,

k_CA is a long term private key of said trusted party, and

n is the order of a group over which said cryptographic system is implemented.

15. The method according to claim 13, further comprising generating an implicit certificate containing public key reconstruction data and an identity of said another correspondent.

16. The method according to claim 15, further comprising sending said implicit certificate to said another correspondent.

17. A computing device for use in a cryptographic system to exchange information with other devices using public key cryptographic protocols, said device comprising:

a cryptographic unit having a random number generator;

a memory to store parameters of said cryptographic system; and

an arithmetic logic unit to perform cryptographic operations, wherein said cryptographic unit is operable to;

receive from another device an encrypted public key;

decrypt said public key using a deterministic encryption scheme to obtain said public key;

utilise said public key to generate private key reconstruction data for use by said correspondent;

encrypt said private key reconstruction data; and

forward said encrypted private key reconstruction data to said other device.

18. The computing device according to claim 17, wherein said memory includes an RSA private key of said devicey, and wherein said cryptographic unit is further operable to utilise said RSA private key to decrypt said public key received from said other device.

19. A non transitory computer readable storage medium comprising computer executable instructions for establishing a private key for use in a public key cryptographic system established between computing devices, each computing device having a cryptographic unit to perform cryptographic operations, said non transitory computer readable storage medium comprising instructions for:

establishing at one of said devices a private value from an output of a random number generator,

computing a corresponding public key from said private value,

encrypting said corresponding public key using a deterministic encryption scheme to establish an encrypted public key and forwarding said encrypted public key to a computing device acting as a trusted party,

receiving from said trusted party encrypted private key reconstruction data,

applying a decryption key to recover said private key reconstruction data; and

computing said private key from said private key reconstruction data, said private key being a discrete log private key corresponding to a discrete log public key made available to the other of said computing devices, whereby said private key may be used in a transfer of information with a recipient of said corresponding discrete log public key.

20. A non transitory computer readable storage medium comprising computer executable instructions for establishing a private key for use in a public key cryptographic system established between computing devices, each computing device having a cryptographic unit to perform cryptographic operations, said non transitory computer readable storage medium comprising instructions for:

receiving from said another correspondent an encrypted public key;

decrypting said public key using a deterministic encryption scheme to obtain said public key;

utilising said public key to generate private key reconstruction data for use by said another correspondent;

encrypting said private key reconstruction data; and

forwarding said encrypted private key reconstruction data to said another correspondent.