Method for generating/regenerating an encryption key for a cryptographic method

[0001] The present invention relates to a method for generating and/or regenerating an encryption key for a cryptographic method. Specifically, the present invention relates to providing and using the encryption key, as well as a public key being generated using a predefined deterministic method, from a large random number (seed).

[0002] The cryptographic technique of encryption to secure communications data and stored data appears to be employed more often. In this context, the data are enciphered (or encrypted) under the control of a cryptographic key. The data can also be deciphered again using the same key. Marketable products and software libraries may be available for this purpose.

[0003] In encryption operations, a so-called hybrid method may be used. In this method, the actual message is encrypted using a randomly selected symmetric key or session key and a preselected symmetric encryption method, e.g., Data Encryption Standard (DES) and/or International Data Encryption Algorithm(IDEA). The session key is then encrypted, in turn, in each case using the public key of the receiver (a plurality of receivers may be involved) and using a predefined asymmetric or public key method, e.g., Rivest, Shamir, Adleman code (RSA) and/or EIGamal (a public key encryption algorithm). The session key encrypted using this process is included with the encrypted message for each receiver. The reference “Cryptography and Network Security: Principles and Practice”, by William Stallings, Prentice Hall, Upper Saddle River, N.J., 1998, appears discuss this procedure and the algorithms employed.

[0004] To decode a received message, the receiver must first decipher the session key using his/her private key, which belongs to his/her public key, and a preselected public key algorithm, to then decrypt the message using this session key.

[0005] Besides encrypting messages, cryptographic methods may also be used to encrypt stored data, e.g., on one's own personal computer. Here as well, one may employ a hybrid method, where the user first encrypts the data using a randomly selected symmetric key or session key and a predefined symmetric encryption method, e.g., DES and/or IDEA. The session key is then encrypted, in turn, using the user's public key and a preselected asymmetric or public key method, e.g., RSA and/or EIGamal.

[0006] Using his/her private key, which belongs to his/her public key, and the predefined public key algorithm, the user first encrypts the session key and then, using this session key, the stored data.

[0007] In the following, the term “encryption key” is used in each case to refer to the user's, i.e., the receiver's, private key.

[0008] The encryption key is either stored on a smart card, access to the smart card being protected by a personal identification number (PIN) known only to the user, or it is stored on another storage medium (for example, a hard disk or diskette), in which case it is preferably protected by a long password.

[0009] It can happen that the encryption key is lost. For example, if the storage medium where it was located is destroyed, or if the user forgets the PIN number or the password which he/she used to secure the encryption key, then it is no longer possible to use it to access the encrypted data.

[0010] To be able to make encrypted data accessible again in the event the encryption key is lost, mechanisms are needed to enable the encryption key to be regenerated in a secure manner. For this purpose, the encryption key is typically generated nowadays at a trust center or trustee or confidential, central location and securely stored. As a rule, the encryption key is produced by initially generating a large random number (seed) using a statistically valid random process. From this random number, the key pair made up of the public key/private key is then generated with the aid of a deterministic method. This seed is subsequently deleted. If necessary, a copy of his/her encryption key is then delivered to the user for use.

[0011] In the process, the user does not have any influence on how his/her encryption key is generated and stored. Moreover, it is expensive to transport the generated encryption key to the user in a secure manner. As a transport medium, nowadays, one uses, for example, the above-mentioned smart card, which is sent to the user. Further, there is a danger of misuse of the stored key by the trust center, or one's own key becoming publicly known due to a malfunction by the trust center and/or in the procedure.

[0012] Exemplary embodiments of the present invention are directed to providing a method of the type mentioned at the outset which may leave it solely up to the user to decide whether an encryption key should be reconstructed.

[0013] Exemplary embodiments of the present invention are further directed to eliminating a need for storing the encryption key for security purposes at the trust center by effecting that when the seed (S) is only generated on the user side, in that quantities (u) known only to the user are consulted; that regeneration information (R), which is suitable for regenerating the seed and from which the seed is able to be derived deterministically by the trust center by linking only to (or concatenating or combining with) information (v) known to it, is generated on the user side and is stored so as to be secured against lost; and that, in the event of loss of encryption key (C), seed (S) is reconstructed by the trust center by linking regeneration information (R) to secret information (v).

[0014] This may be implemented in exemplary embodiments of the present invention in that a mathematical mapping (key agreement mapping) k:

k(x,y)=z is provided, for which it holds that:

• [0015] a) k(k(u,v),w)=k(k(u,w),v) for all u,v,w;
• [0016] b) from the knowledge of u and k(u,v), in practice, one cannot infer v;
• [0017] c) from the knowledge of u, k(u,v) and k(u,w), in practice, one cannot infer k(k(u,w)v);
  that a public parameter g known to the trust center and a secret key v available at the trust center are linked to a public key V=k(g,v) of the trust center;
  that public key V and a random number u selected on the user side are linked on the user side to seed S=k(V,u); that a key pair made up of encryption key C and public user key U is derived from seed S on the user side using the predefined deterministic method; and
  that to render possible the reconstruction of this key pair U and C, regeneration information R=k(g,u) is generated on the user side and is stored so as to be protected against loss.

[0018] In a further exemplary embodiment of the present invention, once regeneration information R is generated, random number u and seed S should again be destroyed for security reasons. Regeneration information R may be generated under tap-proof conditions, for example, within the user-side computer terminal, so that there is no chance of random number u or of seed S falling into the hands of the public. Without knowledge of secret key v, regeneration information R, by itself, may not be suitable for deciphering messages and data and, therefore, does not need to be kept secret.

[0019] Regeneration information R may be stored at any location, for example, on paper, and then when needed be sent or transmitted over any tappable route, for example, mail, e-mail, www or internet, ftp, etc., to the trust center.

[0020] Examples of suitable key agreement mappings k include those available from the theory of numbers. Provision may be made, for example, for key agreement mapping k to be a discrete exponential function modulo a large prime number p: k(x,y):=x^y modulo p, and for public parameter g to be an element of a mathematical field GF(p) of a high multiplicative power, or for key agreement mapping k to be the multiplication on an elliptic curve. In practice, in a further exemplary embodiment of the present invention, one should select the order of magnitude of the numbers used such that, even by summoning up modern technical means, it may be impossible to calculate value y from values x and k(x,y), which, presupposing today's deciphering technology, is ensured at orders of magnitude of the prime numbers used of between 500 and 1000 bits.

[0021] The reference “Cryptography and Network Security: Principles and Practice”, by William Stallings, Prentice Hall, Upper Saddle River, N.J., 1998, appears to discuss such formulations, including the Diffie-Hellman key exchange principle.

[0022] The present invention makes use of the Diffie-Hellman key exchange principle. Exemplary embodiments of the method of the present invention presupposes a trust center, which, if needed, is able to regenerate encryption key C with the aid of regeneration information R.

[0023] In further exemplary embodiments of the present invention, to reconstruct encryption key C in the event of a loss, seed S=k(R,v) may be calculated by the trust center from regeneration information R. The lost encryption key C is, itself, able to be calculated from the thus reconstructed seed S using the deterministic method.

[0024] Due to the property of mapping k which is used, it holds that k(R,v)=k(k(g,u),v)=k(k(g,v),u)=k(V,u)=S, which actually corresponds, again, to original seed S. Since the deterministic method may be available to be known to the trust center, using regeneration information R, the trust center can be able to readily reproduce encryption key C, even without knowledge of random number u. The regenerated encryption key C should then be relayed to the user over a tap-proof channel or route.

[0025] In a further exemplary embodiment of the present invention, to prevent the method of the present invention from being misused to obtain private encryption keys C belonging to others, provision may also be made, once seed S is calculated and the user's new public key U and the new encryption key C are derived due to the loss of a key, for the trust center to verify whether the newly calculated public key U is identical to the user's original public key U, and for reconstructed encryption key C to only be handed over to the user when this verification is conclusive. A method for securely linking the user's identity to his/her public key U is available by ITU standard X.509.

[0026] A further exemplary embodiment of the present invention is directed to providing for there to be a plurality of trust centers which employ key agreement mapping k and public parameter g. In generating encryption key C, one or more of these trust centers may be selected, with the aid of each of the selected trust centers, another fraction value Sv of the seed being generated on the user side, as described, and partial seed Sv being linked on the user side to seed S. To regenerate encryption key C in the case of loss, the selected trust centers may calculate their respective fraction value Sv of seed S using regeneration information R. To reconstruct encryption key C, the reconstructed fraction values Sv are linked, in combination with one another, to seed S. The procedure can prevent a trust center from misusing the method, since each trust center is able to generate only one partial seed Sv which, by itself, is unusable.

[0027] A further embodiment of the present invention is directed to providing for the various trust centers to use different functions kv and/or different public parameters gv, and for separate regeneration information Rv to be created for each of the selected trust centers. In such a case, the user must implement the method of the present invention for each trust center, and each trust center must generate its particular partial seed Sv using its specific regeneration information Rv.

[0030] FIG. 1 shows a time-related flow chart of the processes required for generating a reconstructable, user-specific encryption key C and public user key U in accordance with the method of the present invention. In the column denoted by N, the user-side data occurring one after another are listed from top to bottom. U designates the data transmission link to a trust center V. Trust center V and user N have public parameter g and large prime number p. Public key V=g^v modulo p is generated by trust center V and transmitted by simple channels or means to user N. In response thereto, the user, using a random number u that he/she selects, generates a seed S and regeneration information R and again erases random number u for security reasons. Regeneration information G is transmitted to trust center V. By applying a predefined deterministic method known to the user and the trust center, a public user key U, as well as a private, likewise user-specific encryption key C is generated from seed S. Encryption key C is used here for decrypting messages or data from the user.

[0031] In the case that the encryption key is lost, the trust center, as shown in FIG. 2, regenerates seed S and encryption key C from regeneration information R, transmitted by the user to the trust center, by linking to secret key v and communicates it by secure channels or other such means to the user.