Method and apparatus for encryption key creation

• US 5,850,450 A
• Filed: 07/19/1996
• Issued: 12/15/1998
• Est. Priority Date: 07/20/1995
• Status: Expired due to Fees

• Current Assignee: Dallas Semiconductor Corporation (Analog Devices, Inc.)
• Original Assignee: Dallas Semiconductor Corporation (Analog Devices, Inc.)
• Inventors: Schweitzer, Peter, Armstrong, Bryan M., Loomis, Donald W., Curry, Stephen M., Little, Wendell L., Fox, Christopher W.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/690,272
• Time in Patent Office: 879 Days
• Field of Search: 380/3-5, 380/30, 364/717.01
• US Class Current: 380/30
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 21/73 by creating or determining hardware identification, e.g. serial numbers
• CPC Class Codes: G06F 21/81 by operating on the power supply, e.g. enabling or disabling power-on, sleep or resume operations
• CPC Class Codes: G06F 21/86 Secure or tamper-resistant housings
• CPC Class Codes: G06F 21/87 by means of encapsulation, e.g. for integrated circuits
• CPC Class Codes: G06F 2211/007 Encryption, En-/decode, En-/decipher, En-/decypher, Scramble, (De-)compress
• CPC Class Codes: G06F 2221/2143 Clearing memory, e.g. to prevent the data from being stolen
• CPC Class Codes: G06F 2221/2153 Using hardware token as a secondary aspect
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: G06F 9/30134 Register stacks; shift registers
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/082 Features insuring the integrity of the data on or in the card
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: G11C 5/06 Arrangements for interconnecting storage elements electrically, e.g. by wiring
• CPC Class Codes: G11C 5/143 Detection of memory cassette insertion or removal; Continuity checks of supply or ground lines; Detection of supply variations, interruptions or levels G11C5/148 takes precedence; Switching between alternative supplies G11C5/141 takes precedence
• CPC Class Codes: G11C 7/24 Memory cell safety or protection circuits, e.g. arrangements for preventing inadvertent reading or writing; Status cells; Test cells
• CPC Class Codes: G11C 8/20 Address safety or protection circuits, i.e. arrangements for preventing unauthorized or accidental access
• CPC Class Codes: H01L 2224/16225 : the item being non-metallic, e.g. insulating substrate with or without metallisation
• CPC Class Codes: H01L 23/57 : Protection from inspection, reverse engineering or tampering
• CPC Class Codes: H01L 2924/16152 : Cap comprising a cavity for hosting the device, e.g. U-shaped cap
• CPC Class Codes: H01L 2924/3011 : Impedance
• CPC Class Codes: H04L 25/026 : Arrangements for coupling transmitters, receivers or transceivers to transmission lines; Line drivers duplexing arrangements H04L5/14
• CPC Class Codes: Y10S 257/922 : with means to prevent inspection of or tampering with an integrated circuit, e.g. "smart card", anti-tamper

Abstract

A portable electronic data module for secure transactions, the electronic data module having a random number generator and an optimized co-processor for producing unbreakable key sets for a two-key cryptosystem. A real-time clock is sampled depending upon an external random event series such as power-ups of the data module by a host apparatus, and based upon the contents of the sample thus obtained, the entropy of a previously-loaded accumulator is further enhanced to achieve a pool of true random numbers. By repeatedly requesting random bytes of information from said pool of random numbers, large random numbers are created which are then rendered prime and used for key set creation.

Claims

1. An electronic data module, comprising:

a housing;

a substrate disposed in said housing; and

a monolithic semiconductor chip affixed to said substrate,

wherein said monolithic semiconductor chip includes circuitry for tracking a random event and for providing a random sample of data based upon the occurrence of said random event and a structure for operating a cryptographic algorithm using said random sample of data.

2. The electronic data module as recited in claim 1, wherein said housing further comprises:

a first conductive surface;

a second conductive surface; and

an insulator, said insulator disposed between said first conductive surface and said conductive surface.

3. The electronic data module as recited in claim 1, wherein said structure comprises:

a plurality of memory locations for storing information based at least in part upon said random sample of data;

means for increasing entropy of the contents of a sub-group of said plurality of memory locations; and

means for providing a segment of information upon demand, said segment of information being obtained from the contents of said sub-group of said plurality of memory locations.

4. The electronic data module as recited in claim 1, wherein said circuitry comprises:

a redundancy check generator; and

a real-time clock having at least one counter, said at least one counter for providing at least one sample of information to said cyclic redundancy check generator pursuant to said random event.

5. A method of generating a two-key encryption key set comprising a private component and a public component, the method comprising the steps of:

generating a first random prime number;

generating a second random prime number;

producing a modulus by multiplying said first random number by said second random prime number;

generating a first exponent by solving a first modular arithmetic equation;

generating a second exponent, said second exponent being a modular inverse to said first exponent, by solving a second modular arithmetic equation; and

securely storing at least one of said first exponent, said second exponent, and said modulus in at least one memory location,

wherein each of said first and second random prime numbers is obtained by concatenating a first and second plurality of random bytes, respectively, and further wherein the contents of said random bytes are associated with a random event.

6. The method of generating a two-key encryption key set as recited in claim 5, further comprising the step of:

verifying that said first random number is a prime by solving a third modular arithmetic equation.

7. The method of generating a two-key encryption key set as recited in claim 5, further comprising the step of:

verifying that said second random number is a prime by solving a third modular arithmetic equation.

8. A method of generating a two-key encryption key set using an encryption circuit disposed in a portable electronic data module, the method comprising the steps of:

creating randomized contents in a data storage structure having a select length, said contents based in part upon a random power-up event associated with said portable electronic data module;

enhancing entropy of said data storage structure by manipulating the contents of said data storage structure;

producing a first and second prime number by repeatedly generating a first and second plurality of random bytes of data on demand, respectively, wherein the contents of said random bytes are determined at least in part by the contents of said data storage structure; and

generating a first and second key based on said first and second prime numbers.

9. The method as recited in claim 8, further comprising the step of verifying the primality of each of said first and second prime numbers.

10. The method as recited in claim 9, further comprising the step of privatizing one of said first and second keys.