Secure cryptographic multi-exponentiation method and coprocessor subsystem

• US 6,141,422 A
• Filed: 06/04/1997
• Issued: 10/31/2000
• Est. Priority Date: 06/04/1997
• Status: Expired due to Term

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Inventors: Ciccone, John Charles, Rimpo, Charles Robert, Yuenyongsgool, Yongyut
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Callahan, Paul E.
• Application Number:
  US08/868,886
• Time in Patent Office: 1,245 Days
• Field of Search: 708/277, 708/490, 708/534, 708/606, 712/16, 364/131, 364/133, 713/189, 706/10, 380/30, 380/44, 380/47, 380/282
• US Class Current: 380/44
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A system for performing high speed exponentiation in a secure environment. The system includes an interface for receiving encrypted data sent from a host system, a plurality of exponentiators capable of operating concurrently, an encyptor decrypting data received from a host system and encrypting data produced from the exponentiators, and logic circuitry for selecting an available and properly functioning exponentiator to perform exponentiation on the received data.

Claims

1. A system for use in connection with a host system for performing high-speed exponentiation, comprising:

an interface for receiving and sending data to a host system;

a plurality of exponentiators provided to perform exponentiation on data received from the host system; and

logic circuitry coupled to receive data to be provided from the host system and adapted to query a status of one of the exponentiators and, in response to an indication of availability, to select said one of the plurality of exponentiators as an available exponentiator, and to use the available exponentiator from said plurality of exponentiators to process the received data.

2. The system according to claim 1, wherein at least two exponentiators process data concurrently.

3. A system according to claim 1, further comprising an encryptor coupled between said plurality of exponentiators and said interface for encrypting data passing between said plurality of exponentiators and said interface.

4. A system according to claim 3, further comprising a non-volatile memory communicating with said encryptor for storing a first encryption key.

5. A system according to claim 4, wherein said first encryption key is a key encryption key.

6. A system according to claim 5, wherein said non-volatile memory stores a plurality of key encryption keys.

7. A system according to claim 5, wherein said non-volatile memory is a battery backed memory.

8. A system according to claim 5, wherein said system receives a randomly-generated second key from said host system and uses said second key to decrypt said data received from said host system using said second key.

9. A system according to claim 8, wherein said second key is a traffic key.

10. A system according to claim 3, wherein said plurality of exponentiators are contained on a single chip.

11. A system according to claim 8, wherein said plurality of exponentiators are contained on a single chip.

12. A system according to claim 2, wherein said logic circuitry disables each of said exponentiators in said plurality of exponentiators that is malfunctioning and selects an exponentiator within said plurality of exponentiators that has not been disabled to receive said data.

13. A system according to claim 3, wherein said logic circuitry disables each of said exponentiators in said plurality of exponentiators that is malfunctioning and selects an exponentiator within said plurality of exponentiators that has not been disabled to receive said data.

14. A system according to claim 2, wherein said logic circuitry monitors the status of the exponentiators, the status including whether each exponentiator is busy or malfunctioning and selects an exponentiator within said plurality of exponentiators that is not busy or malfunctioning to receive said data.

15. A method for performing high speed exponentiation of data transferred from a host system, comprising:

receiving data in encrypted form;

decrypting said encrypted data; and

performing exponentiation of the received data to produce resulting data using a plurality of concurrently-operating exponentiators provided to perform exponentiation on data received from the host system.

16. The method of claim 15, wherein at least two exponentiators process data concurrently.

17. The method of claim 15 further comprising encrypting said resulting data after performing exponentiation.

22. The method of claim 15, further comprising testing whether said plurality of exponentiators function properly and disabling exponentiators in said plurality of exponentiators that are not functioning properly, wherein said received data cannot pass to an exponentiator in said plurality of exponentiators that has been disabled.

18. A method for performing high speed exponentiation of data transferred from a host system, comprising:

receiving data;

performing exponentiation of said received data to produce resulting data using a plurality of exponentiators provided to perform exponentiation on data received from the host system,

wherein the received data is in encrypted form;

decrypting said encrypted data;

encrypting said resulting data after performing exponentiation;

wherein said encrypted data has been encrypted at said host system using a second key;

storing a first key in a non-volatile memory;

receiving said second key in encrypted form, wherein said second key has been encrypted using said first key;

decrypting said second key with said first key;

decrypting said received data with said second key; and

encrypting said resulting data with said second key after performing exponentiation.

19. The method of claim 18, wherein said first key is a key encryption key, and wherein said second key is a traffic key.

20. The method of claim 19, wherein said non-volatile memory is a battery backed memory.

21. A method for performing high speed exponentiation of data transferred from a host system, comprising:

receiving data;

performing exponentiation of said received data to produce resulting data using a plurality of exponentiators provided to perform exponentiation on data received from the host system wherein at least two exponentiators process data concurrently,

wherein the received data is in encrypted form;

decrypting said encrypted data;

encrypting said resulting data after performing exponentiation; and

testing whether said plurality of exponentiators function properly and disabling exponentiators in said plurality of exponentiators that are not functioning properly, wherein said received data cannot pass to an exponentiator in said plurality of exponentiators that has been disabled.

24. The method of claim 21, further comprising monitoring the status of the exponentiators in said plurality of exponentiators to determine if any of the exponentiators in said plurality of exponentiators is in a busy status.

23. A method for performing high speed exponentiation of data transferred from a host system, comprising:

receiving data;

performing exponentiation of said received data to produce resulting data using a plurality of exponentiators provided to perform exponentiation on data received from the host system wherein at least two exponentiators process data concurrently,

wherein the received data is in encrypted form;

decrypting said encrypted data;

encrypting said resulting data after performing exponentiation; and

monitoring the status of the exponentiators in said plurality of exponentiators to determine if any of the exponentiators in said plurality of exponentiators is in a busy status.

25. A method for performing high speed exponentiation of data, comprising:

transferring data from a host system to a subsystem;

performing exponentiation of said transferred data at said subsystem to produce resulting data using a plurality of exponentiators provided to perform exponentiation on data received from the host system;

encrypting said transferred data at said host system prior to transferring said transferred data to said subsystem; and

decrypting said transferred data at said subsystem before performing exponentiation.

26. The method of claim 25, wherein at least two exponentiators process data concurrently.

27. The method of claim 26, further comprising:

encrypting said resulting data at said subsystem; and

transmitting said resulting data in encrypted form to said host system.

29. The method of claim 25, further comprising testing said plurality of exponentiators and disabling each of said exponentiators that does not function properly.

30. The method of claim 29, further comprising monitoring the status of said plurality of exponentiators to determine if any of said plurality of exponentiators is in busy status.

31. The method of claim 26, further comprising monitoring the status of said plurality of exponentiators to determine if any of said plurality of exponentiators is in a busy status.

39. The method of claim 25, wherein said subsystem includes a plurality of chips having at least one exponentiator in said plurality of exponentiators, each of said chips having a common base address and a unique offset address.

28. A method for performing high speed exponentiation of data, comprising:

transferring data from a host system to a subsystem;

performing exponentiation of said transferred data at said subsystem to produce resulting data using a plurality of concurrently-operating exponentiators provided to perform exponentiation on data received form the host system; and

testing said plurality of said exponentiators and disabling each of said exponentiators in said plurality of exponentiators that does not function properly.

32. A method for performing high speed exponentiation of data, comprising:

transferring data from a host system to a subsystem;

performing exponentiation of said transferred data at said subsystem to produce resulting data using a plurality of exponentiators provided to perform exponentiation on data received form the host system;

wherein at least two exponentiators process data concurrently;

storing a first key in said subsystem;

encrypting said transferred data at said host system with said first key prior to transferring said transferred data to said subsystem;

decrypting said transferred data at said subsystem using said first key; and

encrypting said resulting data with said first key after performing exponentiation.

33. A method for performing high speed exponentiation of data, comprising:

transferring data from a host system to a subsystem;

performing exponentiation of said transferred data at said subsystem to produce resulting data using a plurality of exponentiators provided to perform exponentiation on data received form the host system;

wherein at least two exponentiators process data concurrently;

storing a first key in said subsystem;

randomly generating a second key at said host system;

encrypting said transferred data at said host system with said second key prior to transferring said transferred data to said subsystem;

encrypting said second key with said first key at said host system;

transferring said encrypted second key and said encrypted data to said subsystem;

decrypting said encrypted second key with said first key at said subsystem; and

decrypting said transferred data received at said subsystem using said second key.

34. The method of claim 33, wherein said first key is a key encryption key, and wherein said second key is a traffic key.

35. The method of claim 34, further comprising:

encrypting resulting data with said traffic key; and

transmitting said resulting data in encrypted form to said host system.

36. The method of claim 35, wherein said key encryption key is stored in a non-volatile memory in said subsystem.

37. The method of claim 36, wherein said non-volatile memory is a battery backed memory.

38. A method for performing high speed exponentiation of data, comprising:

transferring data from a host system to a subsystem;

performing exponentiation of said transferred data at said subsystem to produce resulting data using a plurality of exponentiators provided to perform exponentiation on data received form the host system;

wherein at least two exponentiators process data concurrently; and

wherein said subsystem includes a plurality of chips having at least one exponentiator in said plurality of exponentiators, each of said chips having a common base address and a unique offset address.

40. A system for performing high speed exponentiation of data, comprising:

a host system;

a subsystem communicating with said host system, said subsystem having an interface for receiving data from said host system, a plurality of concurrently-operating exponentiators provided to perform exponentiation on the data received from the host system, and logic circuitry for selecting an available exponentiator from said plurality of exponentiators to receive said data, said logic circuitry connected between said interface and said plurality of exponentiators, the available exponentiator being selected based on a status indicating it is available for use in processing the received data.

41. The system of claim 40, wherein at least two exponentiators process data concurrently.

42. The system of claim 41, wherein said plurality of exponentiators in said subsystem are contained on a plurality of chips, each of said chips having a common base address and a unique offset address.

43. The system of claim 42, said subsystem further including an encryptor coupled between said plurality of exponentiators and said interface for encrypting data passing between said plurality of exponentiators and said interface.

44. The system of claim 43, wherein said plurality of exponentiators are contained on a plurality of chips, each of said chips having a common base address and a unique offset address.