Method and apparatus for secure creation of public/private key pairs

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to the field of cryptography, especially to the generation of public-private key pairs in a network environment.

【0002】

[Conventional technology]

As the use of networked systems that communicate information increases, and the potential access to such networked systems increases, the need to secure communications on networked systems increases. .. Currently, many systems are available that encrypt, decrypt, and authenticate the originator of a message. The cryptographic techniques commonly used by such systems are based on public-private key pairing techniques such as the RSA (Rivest, Shamir, Aldeman) public key cryptosystem.

【0003】

Public-Private Key Cryptography uses mathematical techniques to generate unique public keys from private keys, but these mathematical techniques are very esoteric and practically impossible to apply in reverse. .. That is, knowing the public key does not help determine the private key of the public-private key pair. Public-private key pairs are used in corresponding cryptosystems in such a way that documents and messages encrypted with one key can only be decrypted with the other key (the purpose of this statement is). The assumption is that an encrypted message cannot be decrypted without a proper key, even if there is a finite mathematical possibility that someone could decrypt the message without using an authenticated key. ). Public-Private key system contrasted with the Data Encryption Standard (DES) symmetric system developed by the National Institute of Standards and Technology in the United States, that is, a system that encrypts and decrypts using the same key. Therefore, it is called an asymmetric cryptosystem. Other asymmetric key systems that are common in this area are the EIGamal system, and other symmetric key systems include the IDEA system and the blowfish system.

【0004】

When using the system, users of the cryptosystem are assigned a pair of public and private keys. As the name implies, public keys are intended to be freely distributed by users, while private keys are intended to be kept secret by users. When someone wants to send a secure message to this user, they use this user's public key to encrypt the message and then send the encrypted message to this user. This user decrypts an encrypted message using his private key. Encrypted messages cannot be decrypted without the private key, so assuming the user secures the private key, open the encrypted message without fear of being read by anyone other than this user. You can communicate. If someone else wants to send the same message to multiple users, they can generate multiple encrypted messages using each user's public key.

【0005】

Another use for public-private key pairs is authentication. Authentication means inspecting the sender of a message. The message is authenticated by encrypting the message using the sender's private key. Upon receiving this encrypted message, the recipient decrypts the message using the sender's public key. The sender's public key can only decrypt messages encrypted using the sender's private key, so assuming the sender keeps the private key secure, if the message can be successfully decrypted , Authenticate the sender of the message.

【0006】

Another authentication method is to use the user's private key to encrypt the unique characteristics of the message. This unique feature changes whenever any changes are made to the message. The user sends a message and encrypted features to others. If the decrypted feature matches the unique feature of the message, then the message has been authenticated as being sent by that sender, assuming the sender maintains the confidentiality of the private key. It becomes.

【0007】

[Problems to be Solved by the Invention]

The use of public-private key pair cryptosystems provides a high level of security, which relies heavily on the level of security that protects each user's private key. Of particular importance is the process of generating, distributing, storing, and retrieving private keys. In order to distinguish the private key from the public key, that is, to guarantee that it is indistinguishable, the number of public keys and private keys has been very large in the past. For example, RSA uses as many as 200 digits. UK patent application "Data Communication Using Public Key Cryptography" (CJ The UK serial number GB2,318,486A by Holloway, publication date 1998/4/22, filing date 96/10/16) is incorporated herein by reference. The specification of this British patent application discloses a method in which a user's private key is stored on a server in an encrypted form, and then retrieved and decrypted by the user, but the risk of revealing the private key is reduced. To do this, it states that the private key should preferably be generated on the user's computer (the client's processor in the client-server network). In general, the generation of a truly secure public-private key pair requires a lot of computer resources and a source of true random numbers. To avoid being costly and becoming unmanageable by allowing each user in a networked environment to generate a public-private key pair, use a public-private key pair. , For example, using a dedicated processor physically isolated from the network or other systems, typically generated by the network administrator. Using this method, the public-private key pair is sent to each new user on a document or floppy (registered trademark) disk containing the public-private key pair. It is distributed via secure distribution means such as manual delivery. Manual distribution Stem allows each user to generate a direct public-private key pair It's less expensive than providing resources, but it's awkward. Shi However, in the past, in particular, the communication path was monitored by an unauthorized person or was fraudulent. Need to be distributed manually in a networked environment that is monitored by There was sex.

【0008】

An object of the present invention is to provide a method and an apparatus for generating a public-private key pair on a client processor without requiring a lot of computational resources. Another object of the present invention is to provide methods and devices for generating public-private key pairs on client processors that share a source of true random numbers. Yet another object of the present invention is to provide a method and apparatus for generating a public-private key pair on a client processor in a client-server network that utilizes the resources of the server processor without compromising the security of the public-private key pair. It is to be.

【0009】

The present invention will be described in more detail with reference to the accompanying drawings, but this is merely an example.

【0010】

[Means for solving problems]

FIG. 1 shows a network system 100 including a server processor 150 and client processors 111 to 114. Each of the client processors 111 to 114 can communicate with the server processor 150 and also with other networks 170. The network 100 may be a local network, a home management network, a private network such as the Internet, or the like. Client-server networks typically have significant advantages in terms of resource utilization. For the sake of clarity, we will use the corporate network as an example of the network from now on. Consider the case where a new user is added to the network in the client processor 111 when a new employee joins the company. Traditionally, as mentioned above, the administrator creates a public-private key pair for this new employee on a secure processor and distributes a floppy disk containing the assigned public-private key pair. .. The reason for doing this is that the communication path between the server processor 150 and the client processor 111 is unsecured, and it also produces a truly secure public-private key pair on the client processor 111. This is because the cost of providing the necessary resources is too high.

【0011】

FIG. 2 shows an example of a client processor 111 that works with the server processor 150 as an example to generate a truly secure public-private key pair on the client processor 111. True security, or true security, means that the parameters used to generate the public-private key pair follow mathematical criteria based on the cryptosystem. For example, some cryptographic system algorithms, such as RSA and EIGamal, need to utilize very large prime numbers with special characteristics. Generating a large prime number is not a simple task, nor is it a task of confirming whether the generated prime number has the desired characteristics. In other cases, the algorithms of some cryptosystems need to utilize large, truly secure random numbers, and these large random numbers need to be truly random. However, most computer-generated random numbers are pseudo-random numbers that know either one or more of the previous random numbers generated by the random number generator, or the seed value used by this random number generator. If possible, it means that it will help determine the next random number generated by this generator.

【0012】

In order to optimize the use of resources in a preferred embodiment, the resources required to generate costly parameters for the intended cryptosystem are the example server processor 150, or server processor. Place it on another processor (not shown) accessible by 150. The example server 150 illustrated in FIG. 2 comprises a factor generator 252 that generates one or more parameters p255, a Verifier 254, and a random number generator 256 that generates a random number K257. The Factor Generator 252 and Inspector 254 are illustrated as examples of generators of the parameters required to generate a truly secure public-private key pair. The random number K257 in this embodiment is merely another cryptographic system parameter, and the random number generator 256 is shown as an example for a special device required to generate individual parameters. The parameters p255 and K257 are transmitted to the client processor 111 via the communication units 259 and 259'. Alternatively, these parameters can be encrypted with 258 on server processor 150 and decrypted on 258'on client processor 111 using encryption and decryption techniques that are common to those skilled in the art.

【0013】

The illustrated client processor 111 includes a private key generator 260 and a public key generator 270 that use parameters p255 and K257 transmitted from the server processor 150 as needed. The private key generator 260 generates a secret key x261 which is a function of the random number K257 and the other number N. Most cryptographic algorithms can generate a private key directly from a random number, or the random number itself can be used as a private key, but in this preferred embodiment, not only from the server 150. In order to isolate the generation of the private key from those who can monitor the generation and transmission of K257, the random number K257 is changed by the other number N. That is, for example, even if the administrator of the system that generates the random number K257 should be a reliable person, the security of the private key x261 is greatly enhanced, and even if the random number K257 is known, x261 is used. Little or no help in making a decision.

【0014】

The public key generator 270 generates the public key y203 from the private key x261 using the parameter p255 provided by the server 150. In general, knowing the parameters other than those used to generate the private key is of little or no help in determining the private key. Therefore, in a preferred embodiment, the parameter p255 received from the server processor 150 is used directly by the public key generator 270. Obviously to those skilled in the art, if knowing the parameter p255 helps determine the private key x261, the parameter p255 should be transmitted encrypted from the server processor 150. Alternatively, it should be modified on the client processor 111 before it can be used with the public key generator 270.

【0015】

In order to keep the private key x261 secure, the hash function 210 and the value of the key U201, which is unique to the new user, are then encrypted. This hash function 210 is converted from the key U201 to a form called S211 suitable for use as a secret key. For example, the user key U201 can be a large number, whereas the encryptor 230 can be a DES cryptosystem that uses a 56-bit key value to encrypt. After being encrypted with the hash value S, the private key x261 is erased from the client processor.

【0016】

The key U201 used to encrypt the private key x261 can also be a biometric key (biometric key) based on a new user, such as a fingerprint, retinal print, etc. The US patent application "Biometric authentication method for maintaining the integrity of biometric information (agent reference number PHA23,548, application number 09 / 211,155, filed on December 14, 1998, Michael Epstein)" is a simultaneous application. , Discloses methods for the safe exchange of biometric information, which is incorporated herein by reference. The key U201 can also be based on a password or phrase created by the user, which is easier to remember than, for example, the 200-digit RSA private key x261. Since the encryptor 230 uses symmetric encryption, therefore, the same biometric data or stored passwords and phrases can be used to decrypt the private key x261 whenever necessary. In a preferred embodiment, the encrypted private key is stored on the server processor so that the user is encrypted from the other client processors 112-114 whenever the private key is needed. It will be possible to retrieve the private key z202 afterwards.

【0017】

In a preferred embodiment, based on this same user key U201, the above-mentioned number N for changing the random number K257 is generated. As shown in FIG. 2, the pseudo-random number generator 220 generates a random number N using the hash value S211 of the user key U201 as a seed. It is possible to determine this random number N based on knowing the previous value generated by this pseudo-random number generator 220, but in such a determination in this embodiment the user key used as a seed in the process described above. You need to know the hash value of U201. Although not shown in the figure, the public key y202 and the corresponding encrypted key z203 are transmitted and stored on the server processor 150 in a list of keys, as well as for the new user corresponding to this key pair. Authenticate. In this way, if another user on the network wants to communicate securely with this new user, the other user can access the list of keys to get this new user's public key y202. , Communication can be encrypted as appropriate. After receiving the encrypted communication, the user takes out his / her encrypted private key, decrypts it based on his / her user key U201, and the private key x261 required to decrypt the encrypted communication. Can be obtained.

【0018】

FIG. 4 is an exemplary flow chart for generating a public-private key pair according to the present invention using the EIGamal encryption system model as an example. Block 410 generates the cryptosystem parameter p, and block 420 generates the true random number K as an example. As mentioned above, for a truly secure public-private key pair, the parameters containing random numbers used in the secret system have certain criteria and are typically suitable as cryptographic parameters. You will be given a series of tests to check for. These operations are performed on a server processor or on other processors accessible to this server processor. In block 430, these parameters are transmitted to the client processor and can optionally be transmitted in an encrypted state. In block 440, the user key U is obtained, and in block 444, this is hashed to generate the symmetric key S, which is used in block 470 to encrypt the private key x. As mentioned above, block 448 uses the key S as a seed to the pseudo-random number generator to generate the random number N used to change the random number K.

【0019】

In a preferred embodiment, in block 450, the exclusive OR function is used to combine the random numbers K and N and convert them to the private key x. This exclusive OR function has the desired attribute of propagating the properties of a true random number, which is an input variable, to the resulting value, the secret key x. That is, knowing N is of no use in determining the private key x. In block 460, the public key y is generated using the private key x and the parameter p. Using the EIGamal encryption system as an example, the public key y is y = (p₁)^xmod p₂It is calculated by.

【0020】

In block 470, the private key x is encrypted using the symmetric key S, and in block 480 it is erased from the memory of the client processor. Also, in block 480, the random numbers K, N, and the symmetric key S are also erased from the memory of the client processor. The resulting encrypted private key E_s(x), the corresponding public key y, and the user ID for authentication are transmitted to the server processor to facilitate access to the user's public key y by others, and by the user himself / herself. Encrypted private key E_sFacilitate access to (x).

【0021】

The above description merely describes the principles of the present invention. Therefore, it should be understood that those skilled in the art, although not explicitly described herein, will allow them to create various configurations that implement the principles of the invention within the spirit and scope of the invention. For example, the methods described herein provide a high level of security in the generation of public-private key pairs on client processors. In view of the present invention, the level of security may be lower, but other methods will be obvious to those skilled in the art. For example, the step of mixing the random number K with other random numbers can be omitted, but in this case, the secret key x can be determined by knowing K. Similarly, we have explained that the random number N, which is mixed with the random number K, is based on the hash of the user key U, but it can also be generated independently. Similarly, some cryptosystem parameters can be generated on the client processor. For example, if the source of the true random number K is not available in the server processor, but a large prime source with the desired characteristics is available in the server processor, then only the parameter p255 is generated and from the server processor. Communicate it. In this case, the use of the pseudo-random number K'generated in the client processor would provide a safer process to utilize the pseudo-random number K'transmitted from the server processor. Within the claims, these and other changes and optimizations will be obvious to those skilled in the art.

[Simple explanation of drawings]

[Figure 1]

It shows an example of a networked computer system including a server and a plurality of clients.

[Figure 2]

The present invention shows an example of a client processor that generates a public-private key pair.

[Fig. 3]

The present invention shows an example of a flowchart for generating a public-private key pair on a client processor.