Method and arrangement for the computer-aided exchange of cryptographic keys between a first computer unit and a second computer unit

[0001] The invention relates to the computer-aided interchange of cryptographic keys between a first computer unit and a second computer unit.

[0002] Information technology systems are subject to various threats. Thus, by way of example, transmitted information can be tapped and modified by an unauthorized third party. A further threat during communication between two communication parties is that of a false identity of one communication party being feigned.

[0003] These and other threats are countered by various security mechanisms which are intended to protect the information technology system from the threats. One security mechanism used for safeguarding purposes is encryption of the transmitted data. To be able to encrypt the data in a communication link between two communication parties, steps which prepare the encryption first need to be taken before the actual data is transmitted. By way of example, the steps may involve the two communication parties agreeing to an encryption algorithm and, if appropriate, the common secret keys being declared.

[0004] The encryption security mechanism takes on particular significance in the case of mobile radio systems, since the transmitted data in these systems can be tapped by any third party without any particular additional effort.

[0005] This leads to the requirement for known security mechanisms to be selected and these security mechanisms to be suitably combined, and also for communication protocols to be specified, such that they ensure the security of information technology systems.

[0006] Various asymmetric methods for the computer-aided interchange of cryptographic keys are known.

[0007] Asymmetric methods which are suitable for mobile radio systems are described in [1], [2], [3] and [4].

[0008] The method described in [1] relates expressly to local area networks and makes relatively high demands in terms of computing power on a computer unit of a communication party during the key interchange. Moreover, more transmission capacity is required in the method than in the method according to the invention, since the length of the messages is greater than in the case of the invention.

[0009] The method described in [2] has not implemented a few fundamental security aims. Explicit authentication of the network by the user is not achieved. Moreover, a key transmitted to the network by the user is not confirmed to the user by the network. There is also no assurance for the network that the key is fresh (up to date). A further disadvantage of this method is the restriction to the Rabin method in the implicit authentication of the key by the user. This restricts the method in terms of more flexible applicability. In addition, no security mechanism which ensures the incontestability of transmitted data is provided. This is a considerable disadvantage, in particular also for the preparation of incontestable charge accounts for a mobile radio system. The restriction of the method to the signature function used being the National Institute of Standards in Technology Signature Standard (NIST DSS) also restricts the method in its general applicability.

[0010] The method described in [3] has not implemented a fundamental security aim: explicit authentication of the user by the network is not achieved.

[0011] The method described in [4] is based on the assumption of the existence of common secret keys both between the user and the visited network and between the user and the home network before a protocol pass starts. This assumption is too restrictive for many instances of use.

[0012] In addition, [5] discloses a method for secure data interchange between a multiplicity of subscribers involving a certification authority: The protocol used for this method has a random number, an identity statement and also a public key and a session key. However, fundamental security aims are not implemented in this method.

[0013] In addition, [6] discloses a method for PC—PC communication involving a trust center.

[0014] [7] discloses a method in which a session key is produced using both a public key and a secret key and also using a random number. This session key is combined with a public key.

[0015] In addition, [8] describes a method in which a user unit identifies itself to a network unit. An authentication process then takes place between the user unit and the network unit using a hash function.

[0016] [9] discloses further secure communication protocols which nevertheless do not implement important fundamental security aims.

[0017] [10] discloses the practice of forming a first value in a first computer unit from a first random number using a generating element of a finite group, and transmitting it to a second computer unit. In the second computer unit, a session key is formed by hash value formation for the first value, which is exponentiated using a secret network key. The session key is likewise formed in the first computer unit, but there by hash value formation for a public network key which is exponentiated using the first random number. In addition, a hash value for the session key is formed there and the hash value is digitally signed. The resultant signature term is transmitted to the second computer unit and is verified there.

[0018] The method described in [11] achieves the important security aims, but with a relatively high level of input in terms of computing power and transmission capacity.

[0019] Asymmetric methods are essentially based on two complexity theory problems, the problem of efficiently factorizing composed numbers and the discrete logarithm problem (DLP). The DLP is that, although exponentiation operations can be carried out efficiently in suitable computing structures, no efficient algorithms are known for the reversal of this operation, logarithmation.

[0020] By way of example, the finite groups referred to above are to be understood as being such computing structures. These groups are, for example, the multiplicative group of a finite body (e.g. multiplication modulo p, where p is a large prime number), or else so-called “elliptical curves”. Elliptical curves are primarily of interest because they permit much shorter security parameters for the same level of security. This relates to the length of the public keys, to the length of the certificates, to the length of the messages to be interchanged during session key declaration and to the length of digital signatures, which are each described below. The reason for this is that the logarithmation methods known for elliptical curves are much less efficient than those for finite bodies.

[0021] In this context, a large prime number means that the size of the prime number needs to be selected such that logarithmation is so complex that it cannot be performed in a reasonable time. In this context, reasonable means a period of time corresponding to the security policy over a number of years to decades, and longer.

[0022] In this context, a hash function is to be understood as being a function in the case of which it is not possible to calculate a matching input value for a given function value. In addition, an input character sequence of arbitrary length is allocated an output character sequence of fixed length. Furthermore, additional properties may be demanded for the hash function. One such additional property is freedom from conflict, i.e. it must not be possible to find two different input character sequences which produce the same output character sequence.

[0023] The invention is based on the problem of specifying a simplified method for the computer-aided interchange of cryptographic keys which does not presuppose the existence of common secret keys.

[0024] In the method, a first value is formed from a first random number using a generating element of a finite group in the first computer unit. A first message is transmitted from the first computer unit to the second computer unit, the first message containing at least the first value. A session key is formed in the second computer unit using a first hash function, a first input variable for the first hash function containing at least one first term which is formed by exponentiation of the first value using a secret network key. The session key is formed in the first computer unit using the first hash function, a second input variable for the first hash function containing at least one second term which is formed by exponentiation of a public network key using the first random number. A fourth input variable is formed in the first computer unit using a second hash function or the first hash function, a third input variable for the first hash function or for the second hash function containing, for the purpose of forming the fourth input variable, one or more variables which can be used to infer the session key unambiguously. A signature term is formed in the first computer unit from at least the fourth input variable using a first signature function. A third message is transmitted from the first computer unit to the second computer unit, the third message containing at least the signature term from the first computer unit. The signature term is verified in the second computer unit.

[0025] In the case of the arrangement, the first computer unit and the second computer unit are set up such that the following method steps can be carried out:

• • [0026] a first value is formed from a first random number using a generating element of a finite group in the first computer unit,
  • [0027] a first message is transmitted from the first computer unit to the second computer unit, the first message containing at least the first value,
  • [0028] a session key is formed in the second computer unit using a first hash function, a first input variable for the first hash function containing at least one first term which is formed by exponentiation of the first value using a secret network key,
  • [0029] the session key is formed in the first computer unit using the first hash function, a second input variable for the first hash function containing at least one second term which is formed by exponentiation of a public network key using the first random number,
  • [0030] a fourth input variable is formed in the first computer unit using a second hash function or the first hash function, a third input variable for the first hash function or for the second hash function containing, for the purpose of forming the fourth input variable, one or more variables which can be used to infer the session key unambiguously,
  • [0031] a signature term is formed in the first computer unit from at least the fourth input variable using a first signature function,
  • [0032] a third message is transmitted from the first computer unit to the second computer unit, the third message containing at least the signature term from the first computer unit, and
  • [0033] the signature term is verified in the second computer unit.

[0034] The advantages which are achieved by the invention are primarily a considerable reduction in the length of the transmitted messages and the implementation of further security aims.

[0035] In addition, the invention can be adapted very easily to different requirements, since there is no restriction to particular algorithms for signature formation and encryption.

[0036] In one development, provision is made for a long-service secret network key and a long-service public network key to be used.

[0037] A long-service key is to be understood below as being a key which is used for a plurality of protocol passes.

[0038] The invention and its developments implement the following security aims:

• • [0039] mutual explicit authentication by the user and the network, i.e. mutual verification of the claimed identity,
  • [0040] key declaration between the user and the network with mutual implicit authentication, i.e. the method achieves the effect that, after completion of the procedure, a common secret session key is available, of which each party knows that only the authentic counterpart can likewise be in possession of the secret session key,
  • [0041] assurance for the user that the session key is fresh (up to date),
  • [0042] mutual confirmation of the session key by the user and the network, i.e. confirmation that the counterpart is actually in possession of the declared secret session key.

[0043] The following advantageous developments of the method also relate to these security aims.

[0044] In one development, a dependable public user key for the first computer unit, e.g. in the form of a user certificate, is additionally made available in the first computer unit and a dependable public network key for the second computer unit, e.g. in the form of a network certificate, is made available in the second computer unit. The public network key need not be available in the first computer unit in this development.

[0045] In a further refinement, it is not necessary for the public user key to be available in the second computer unit.

[0046] In accordance with a further refinement, no dependable public network key for the second computer unit is necessary in the first computer unit. A dependable public certification key for the certification computer unit is available in the first computer unit. This means that the first computer unit needs to “acquire” the dependable public network key in the form of a network certificate from a certification computer unit. The second computer unit likewise needs the dependable public user key in the form of a user certificate from the certification computer unit.

[0047] The developments of the invention in accordance with patent claims 13, 15 and 20 implement the security aim of user anonymity, i.e. confidentiality of the identity of the user with regard to third parties.

[0048] The development of the method according to the invention in accordance with patent claim 15 permits the use of temporary user identities.

[0049] The development of the method in accordance with patent claim 16 primarily ensures additional authentication of the second computer unit with regard to the first computer unit.

[0050] The development in accordance with patent claim 18 implements the security aim of assurance for the network that the session key is fresh (up to date).

[0051] The development in accordance with patent claim 21 additionally implements the security aim of incontestability of data which has been sent from the user to the network.

[0052] The drawings show preferred exemplary embodiments of the invention which are described in more detail below.

[0056] FIGS. 1A and 1B show a sketch of the execution of the method. The method relates to the interchange of cryptographic keys between a first computer unit U and a second computer unit N, where the first computer unit U is to be understood as being a computer unit of a user of a mobile radio network and a second computer unit N is to be understood as being a computer unit of the network operator of a mobile radio system.

[0057] It is a prerequisite for the method that a dependable public network key g^s for the second computer unit N is available in the first computer unit U and that a dependable public user key KU for the first computer unit U is available in the second computer unit N, where g is a generating element of a finite group.

[0058] In the first computer unit U, a first random number t is generated (step 101). The generating element g of a finite group is used to form a first value g^t from the first random number t in the first computer unit U (step 102).

[0059] Once the first value g^t has been calculated, a first message M1, containing at least the first value g^t, is coded. The first message M1 is transmitted from the first computer unit U to the second computer unit N (step 103).

[0060] In the second computer unit N, the first message M1 is decoded. The first message M1 may also be transmitted over an insecure channel, that is to say also via an air interface, in unencrypted form, since the logarithmation of the first value g^t cannot be performed in a reasonable time.

[0061] In the second computer unit N, a second random number r is generated (step 104). This additional method step implements an additional security aim: the assurance for the second computer unit N that a session key K described below is fresh (up to date).

[0062] In the second computer unit N, a first hash function h1 is used to form a session key K (step 105). At least one first term is used as a first input variable for the first hash function h1. The first term is formed by raising the first value g^t to a higher power using a secret network key s.

[0063] If the second random number r is used, the first input variable for the first hash function h1 additionally contains at least the second random number r.

[0064] A response A is now formed in the second computer unit N (step 106). Various variants are provided for forming the response A. Thus, for example, it is possible for an encryption function Enc to be used to encrypt a constant const, and possibly further variables, with the session key K. The constant const is known both to the first computer unit U and to the second computer unit N. The encryption function Enc is also known both to the second computer unit N and to the first computer unit U as the encryption function which is to be used in the method.

[0065] A further option for forming the response A (step 106) is for the session key K, and possibly prescribable further variables, e.g. an identity statement idN for the second computer unit N and/or the second random number, to be used as input variable for a second hash function h2, and for the “hashed” value for the session key K, and possibly for the further variables, to be used as response A.

[0066] Stringing together the second random number r, the response A and also an optional first data field dat1 forms a second message M2. The optional first data field dat1 is only contained in the second message M2 if this is provided in the method.

[0067] The second message M2 is coded in the second computer unit N and is transmitted to the first computer unit U (step 107).

[0068] In the first computer unit U, the second message M2 is decoded, which means that the first computer unit U has the second random number r, the response A and possibly the optional first data field dat1 available. The length of the optional first data field dat1 may be of any desired size, i.e. it is also possible for the optional first data field dat1 not to be present.

[0069] In the first computer unit U, the session key K is now likewise formed (step 108), using the first hash function h1, which is known both to the second computer unit N and to the first computer unit U. A second input variable for the first hash function h1 for forming the session key K in the first computer unit U contains at least one second term. The second term is formed from exponentiation of a public network key g^s using the first random number t. If the use of the second random number r is provided in the method for calculating the session key K, the second input variable for the first hash function h1 for forming the session key K in the first computer unit U additionally contains the second random number r.

[0070] The use of the first random number t and of the second random number r for generating the session key K ensures that the session key K is up to date, since the first random number t and the second random number r are respectively used only for one session key K in each case. This prevents reinjection of an older key as the session key K.

[0071] Once the session key K has been formed in the first computer unit U, the received response A is used to check whether the session key K formed in the first computer unit U matches the session key K which was formed in the second computer unit N (step 109). Subject to the variants described above for forming the response A, various options are provided for checking the session key K using the response A.

[0072] One option is that, if the response A has been formed in the second computer unit N by encrypting the constant const, and possibly further variables, with the session key K using the encryption function Enc, the response A is decrypted, and hence the first computer unit U receives a decrypted constant const′, and possibly prescribable further variables, which is/are compared with the known constant const, and possibly the further variables.

[0073] The session key K may also be checked, using the response A, by encrypting the constant const, known to the first computer unit U, and possibly prescribable further variables, with the session key K, formed in the first computer unit U, using the encryption function Enc and checking the result with the response A for a match. This procedure is also used when the response A is formed in the second computer unit N, by applying the second hash function h2 to the session key K, and possibly to the further variables. In this case, the session key K formed in the first computer unit U, and possibly prescribable further variables, is/are used as input variable for the second hash function h2 in the first computer unit U. The “hashed” value for the session key K formed in the first computer unit U, and possibly for further variables, is then checked with the response A for a match. This achieves the aim of key confirmation for the session key K.

[0074] As a result of the secret network key s being used for calculating the session key K in the second computer unit N, and the public network key g^s being used for calculating the session key K in the first computer unit U, the second computer unit N is authenticated by the first computer unit U. This is achieved provided that it is known for the first computer unit U that the public network key g^s actually belongs to the second computer unit N.

[0075] Subsequent to confirmation of the session key K by means of a check on the response A, a signature term is calculated (step 110). To this end, a third hash function h3 is used to form a fourth input variable. The third hash function h3 can, but need not, be the same hash function as the first hash function h1 and/or the second hash function h2. As a third input variable for the third hash function h3, a term is used which contains one or more variables from which it is possible to infer the session key unambiguously. In addition, the third input variable may contain the optional first data field dat1 or else an optional second data field dat2, if the use thereof is provided in the method.

[0076] Such variables are the first value g^t, the public network key g^s and the second random number r.

[0077] It is subsequently not possible to contest the fact that the data contained in the first optional data field dat1 and in the second optional data field dat2 has been sent from the first computer unit U.

[0078] The data contained in the first optional data field dat1 and in the second optional data field dat2 may be telephone numbers, the current time or similar parameters suitable for this purpose. This information may be used as a tool for incontestable charge accounting.

[0079] A first signature function Sig_u, is used to form the signature term from at least the fourth input variable. To achieve a higher degree of security, the signature term may be encrypted. In this case, the signature term is encrypted with the session key K using the encryption function Enc and forms the first encrypted term VT1.

[0080] In addition, if the security aim of “anonymity of the user” is to be implemented, a second encrypted term VT2 is calculated by encrypting an identity variable IMUI for the first computer unit U with the session key K using the encryption function Enc. When an optional second data field dat2 is used, a third encrypted term VT3 is calculated in the first computer unit U by encrypting the optional second data field dat2 with the session key K using the encryption function Enc; the optional second data field dat2 may also be transmitted in unencrypted form.

[0081] The three encrypted terms may also be combined to form a fourth encrypted term VT4, in which the interlinkage of signature term, identity variable IMUI and optional second data field dat2 is encrypted with the session key K (step 111).

[0082] In the first computer unit U, a third message M3, containing at least the signature term and the identity variable IMUI for the first computer unit U, is formed and coded.

[0083] If anonymity of the first computer unit U is to be ensured, the third message M3 contains, instead of the identity variable IMUI for the first computer unit U, at least either the second encrypted term VT2 or the fourth encrypted term VT4, which contains the information about the identity of the first computer unit U in encrypted form, which can be decrypted only by the second computer unit N.

[0084] If the use of the optional second data field dat2 is provided, the third message M3 additionally contains at least the third encrypted term VT3 or the fourth encrypted term VT4 or the optional second data field dat2 in plain text.

[0085] If the third message M3 contains the first encrypted term VT1, the second encrypted term VT2 or the third encrypted term VT3 or the fourth encrypted term VT4, these are decrypted in the second computer unit N. This is done for the first encrypted term VT1, which may be present, before verification of the signature term.

[0086] The third message M3 is transmitted from the first computer unit U to the second computer unit N (step 112).

[0087] In addition, authentication of the first computer unit U for the second computer unit N is ensured by the signature term, which contains the random number r, the use of which guarantees that the third message M3 has actually been sent from the first computer unit U at the present time.

[0088] In the second computer unit N, the third message M3 is decoded, decrypted, and a user certificate CertU available to the second computer unit N is then used to verify the signature term (step 113).

[0089] If temporary user identities are provided for the method, then the method described above is extended by a few method steps.

[0090] The second computer unit N must first be informed of which first computer unit U is to be allocated a new temporary identity variable TMUIN by the second computer unit N.

[0091] To this end, an old temporary identity variable TMUIO is transmitted from the first computer unit U to the second computer unit N as an additional component of the first message M1.

[0092] Once the first message M1 has been received, the second computer unit N thus knows for which first computer unit U the new temporary identity variable TMUIN is intended.

[0093] The new temporary identity variable TMUIN for the first computer unit U is then formed in the second computer unit N. This may be performed, for example, by generating a random number or by means of tables in which potential identity variables are stored. The new temporary identity variable TMUIN for the first computer unit U is used to form a fifth encrypted term VT5 in the second computer unit N by encrypting the new temporary identity variable TMUIN for the first computer unit U with the session key K using the encryption function Enc.

[0094] In this case, the second message M2 additionally contains at least the fifth encrypted term VT5. The fifth encrypted term VT5 is then decrypted in the first computer unit U. The new temporary identity variable TMUIN for the first computer unit U is now available in the first computer unit U.

[0095] So that the second computer unit N is also assured of the fact that the first computer unit U has received the new temporary identity variable TMUIN correctly, the third input variable for the first hash function h1 or for the third hash function h3 additionally contains at least the new temporary identity variable TMUIN for the first computer unit U.

[0096] Since the information for the new temporary identity variable TMUIN is contained in the signature term in this case, the third message M3 no longer contains the identity variable IMUI for the first computer unit U.

[0097] It is also possible for the new temporary identity variable TMUIN not to be integrated into the signature term, but rather for the second encrypted term VT2 to be formed by encrypting, instead of the identity variable IMUI for the first computer unit U, the new temporary identity variable TMUIN with the session key K using the encryption function Enc. In this case, the third message M3 additionally contains the second encrypted term VT2.

[0098] The hash functions used in the method, the first hash function h1, the second hash function h2 and the third hash function h3 can be produced by the same hash functions, or else by different hash functions.

[0099] FIGS. 2A and 2B show a sketch of the execution of a second exemplary embodiment of the method.

[0100] A prerequisite for this exemplary embodiment of the method is that a dependable public user key KU for the first computer unit U in the form of a user certificate CertU is made available in the first computer unit U, and that a dependable public network key g^s for the second computer unit N in the form of a network certificate CertN is made available in the second computer unit N. The public network key g^s need not be available in the first computer unit U. Likewise, it is not necessary for the public user key KU to be available in the second computer unit N.

[0101] In the first computer unit U, the first random number t is generated (step 201). The generating element g of a finite group in the first computer unit U is used to form the first value g^t from the first random number t (step 202).

[0102] Once the first value g^t has been calculated, a first message M1 is coded, said first message containing at least the first value g^t and an identity statement id_CA for a certification computer unit CA which delivers the network certificate CertN which can be verified by the first computer unit U. The first message M1 is transmitted from the first computer unit U to the second computer unit N (step 203).

[0103] In the second computer unit N, the first message M1 is decoded.

[0104] As described in FIG. 2, a second random number r is generated in the second computer unit N (step 204). This additional method step implements an additional security aim: the assurance for the second computer unit N that a session key K described below is fresh (up to date).

[0105] In the second computer unit N, the first hash function h1 is used to form the session key K (step 205). The first input variable used for the first hash function h1 is a first term. The first term is formed by raising the first value g^t to a higher power using the secret network key s.

[0106] When the second random number r is used, the first input variable for the first hash function h1 additionally contains at least the second random number r.

[0107] A response A is now formed in the second computer unit N (step 206). To form the response A, the variants described within the context of the first exemplary embodiment are provided.

[0108] Stringing together the second random number r, the network certificate CertN, the response A and an optional first data field dat1 forms the second message M2. The optional first data field dat1 is only contained in the second message M2 if this is provided in the method.

[0109] The second message M2 is coded in the second computer unit N and is transmitted to the first computer unit U (step 207).

[0110] In the first computer unit U, the second message M2 is decoded, which means that the first computer unit U has the second random number r, the response A and possibly the optional first data field dat1 available. The length of the optional first data field dat1 can be of any desired size, i.e. it is also possible for the optional first data field dat1 not to be present.

[0111] Next, the network certificate CertN contained in the second message M2 is verified in the first computer unit. Hence, the public network key g^s is available in the first computer unit U.

[0112] In the first computer unit U, the session key K is now likewise formed (step 208), using the first hash function h1, which is known both in the second computer unit N and in the first computer unit U. A second input variable for the first hash function h1 for forming the session key K in the first computer unit U contains at least one second term. The second term is formed from exponentiation of the public network key g^s using the first random number t. If the use of the second random number r is provided in the method for calculating the session key K, the second input variable for the first hash function h1 for forming the session key K in the first computer unit U additionally contains the second random number r.

[0113] The use of the first random number t and of the second random number r for generating the session key K ensures that the session key K is up to date, since the first random number t and the second random number r are respectively used only for one session key K in each case. This prevents reinjection of an older key as the session key K.

[0114] Once the session key K has been formed in the first computer unit U, the received response A is used to check whether the session key K formed in the first computer unit U matches the session key K which was formed in the second computer unit N (step 209).

[0115] Subject to the variants described above for forming the response A, various options are provided for checking the session key K using the response A.

[0116] To check the response A, the variants described within the context of the first exemplary embodiment are provided. This achieves the aim of key confirmation for the session key K.

[0117] As a result of the secret network key s being used for calculating the session key K in the second computer unit N, and the public network key g^s being used for calculating the session key K in the first computer unit U, the second computer unit N is authenticated by the first computer unit U. This is achieved provided that it is known for the first computer unit U that the public network key g^s actually belongs to the second computer unit N.

[0118] Subsequent to confirmation of the session key K by means of a check on the response A, the signature term is calculated (step 210). To this end, the third hash function h3 is used to form a fourth input variable. The third hash function h3 can, but need not, be the same hash function as the first hash function h1 and/or the second hash function h2. As a third input variable for the third hash function h3, a term is used which contains one or more variables from which it is possible to infer the session key unambiguously. In addition, the third input variable may contain the optional first data field dat1 or else an optional second data field dat2, if the use thereof is provided in the method.

[0119] Such variables are the first value g^t, the public network key g^s and the second random number r.

[0120] It is subsequently not possible to contest the fact that the data contained in the first optional data field dat1 and in the second optional data field dat2 has been sent from the first computer unit U.

[0121] The data contained in the first optional data field dat1 and in the second optional data field dat2 may be telephone numbers, the current time or similar parameters suitable for this purpose. This information may be used as a tool for incontestable charge accounting.

[0122] A first signature function Sig_U is used to form the signature term from at least the fourth input variable. To achieve a higher degree of security, the signature term may be encrypted. In this case, the signature term is encrypted with the session key K using the encryption function Enc and forms the first encrypted term VT1.

[0123] In addition, if the security aim of “anonymity of the user” is to be implemented, a second encrypted term VT2 is calculated by encrypting a user certificate CertU for the first computer unit U with the session key K using the encryption function Enc. When an optional second data field dat2 is used, a third encrypted term VT3 can be calculated in the first computer unit U by encrypting the optional second data field dat2 with the session key K using the encryption function Enc. The optional second data field dat2 may likewise be transmitted in unencrypted form.

[0124] The three encrypted terms may also be combined to form a fourth encrypted term VT4, in which the chain comprising signature term, identity variable IMUI and optional second data field dat2 is encrypted with K (step 211).

[0125] In the first computer unit U, a third message M3, containing at least the signature term and the user certificate CertU for the first computer unit U, is formed and coded. If user anonymity of the first computer unit U is to be ensured, the third message M3 contains, instead of the user certificate CertU for the first computer unit U, at least either the second encrypted term VT2 or the fourth encrypted term VT4, which contains the user certificate CertU for the first computer unit U in encrypted form, which can be decrypted only by the second computer unit N.

[0126] If the use of the optional second data field dat2 is provided, the third message M3 additionally contains at least the third encrypted term VT3 or the fourth encrypted term VT4. If the third message M3 contains the first encrypted term VT1, the second encrypted term VT2 or the third encrypted term VT3 or the fourth encrypted term VT4, these are decrypted in the second computer unit N. This is done for the first encrypted term VT1, which may be present, before verification of the signature term.

[0127] The third message M3 is transmitted from the first computer unit U to the second computer unit N (step 212).

[0128] In the second computer unit N, the third message M3 is decoded, decrypted, and a user certificate CertU available to the second computer unit N is then used to verify the signature term (step 213).

[0129] In addition, authentication of the first computer unit U for the second computer unit N is ensured by the signature term, which contains the random number r, the use of which guarantees that the third message M3 has actually been sent from the first computer unit U at the present time.

[0130] If temporary user identities are provided for the method, then the method described above is extended by a few method steps.

[0131] In the second computer unit N, a new temporary identity variable TMUIN is formed for the first computer unit U and is subsequently allocated to the first computer unit U. This may be performed by generating a random number or by means of tables in which potential identity variables are stored. The new temporary identity variable TMUIN for the first computer unit U is used to form a fifth encrypted term VT5 in the second computer unit N by encrypting the new temporary identity variable TMUIN for the first computer unit U with the session key K using the encryption function Enc.

[0132] In this case, the second message M2 additionally contains at least the fifth encrypted term VT5. The fifth encrypted term VT5 is then decrypted in the first computer unit U. The new temporary identity variable TMUIN for the first computer unit U is now available in the first computer unit U.

[0133] So that the second computer unit N is also assured of the fact that the first computer unit U has received the new temporary identity variable TMUIN correctly, the third input variable for the first hash function h1 or for the third hash function h3 additionally contains at least the new temporary identity variable TMUIN for the first computer unit U.

[0134] It is also possible for the new temporary identity variable TMUIN not to be integrated into the signature term, but rather for the second encrypted term VT2 to be formed by encrypting the new temporary identity variable TMUIN for the first computer unit U with the session key K using the encryption function Enc. In this case, the third message M3 additionally contains the second encrypted term VT2.

[0135] FIGS. 3A and 3B show a sketch of the execution of a third exemplary embodiment.

[0136] A prerequisite for this exemplary embodiment of the method is that no dependable public network key g^s for the second computer unit N is available in the first computer unit U. A dependable public certification key cs for a certification computer unit CA is available in the first computer unit U. This means that the first computer unit U needs to “acquire” the dependable public network key g^s in the form of a network certificate CertN from the certification computer unit CA. Likewise, the second computer unit N needs the dependable public user key KU in the form of a user certificate CertU from the certification computer unit CA.

[0137] In the first computer unit U, the first random number t is generated (step 301). The generating element g of a finite group in the first computer unit U is used to form the first value g^t from the first random number t (step 302).

[0138] Once the first value g^t has been calculated, a first message M1 is coded, said first message containing at least the first value g^t, an identity variable IMUI for the first computer unit U and an identity statement id_CA for a certification computer unit CA which delivers a network certificate CertN which can be verified by the first computer unit U. This is necessary when a plurality of certification authorities with different secret certification keys are provided. If the security aim of user anonymity is to be implemented, an intermediate key L is formed in the first computer unit U before formation of the first message M1. This is done by raising the public key declaration key g^u for the certification computer unit CA, which key is available in the first computer unit U, to a higher power using the first random number t. Subsequently, the identity variable IMUI for the first computer unit U is in this case encrypted with the intermediate key L using an encryption function Enc, and the result represents a fifth encrypted term VT5. The fifth encrypted term VT5 is integrated into the first message M1 instead of the identity variable IMUI for the first computer unit U. The first message M1 is transmitted from the first computer unit U to the second computer unit N (step 303).

[0139] In the second computer unit N, the first message M1 is decoded and a fourth message M4 is formed (step 304), said fourth message containing a chain comprising the certificate CertN, known to the second computer unit N, for the public network key g^s, the first value g^t and the identity variable IMUI for the first computer unit U. If the security aim of user anonymity is to be implemented, the fifth encrypted term VT5 is coded in the fourth message M4 instead of the identity variable IMUI for the first computer unit U.

[0140] The fourth message M4 is coded in the second computer unit N and is then transmitted to the certification computer unit CA (step 304).

[0141] The fourth message M4 is decoded in the certification computer unit CA.

[0142] Next, if user anonymity is ensured, that is to say the fifth encrypted term VT5 has also been sent in the fourth message M4, the intermediate key L is calculated in the certification computer unit CA by raising the first value g^t to a higher power using a secret key declaration key u for the certification computer unit CA.

[0143] The fifth encrypted term VT5 is decrypted with the intermediate key L using the encryption function Enc, as a result of which the identity variable IMUI for the first computer unit U is known in the certification computer unit CA.

[0144] In the certification computer unit CA, the user certificate CertU is then ascertained. The user certificate CertU is ascertained from a dedicated database for the certification computer unit CA, said database containing all the certificates for the computer units for which the certification computer unit CA produces certificates.

[0145] To check the validity of the network certificate CertN and of the user certificate CertU, an identity statement id_N for the network computer unit N and the public network key g^s also sent in the fourth message, the identity variable IMUI for the first computer unit U and also the ascertained user certificate CertU are compared with a revocation list containing invalid certificates, keys or identity variables.

[0146] The certification computer unit CA then forms three chains of certificates, a first certificate chain CertChain (U, N), a second certificate chain CertChain (N, U) and a third certificate chain CertChain (N, CA).

[0147] The first certificate chain CertChain (U, N) can be verified by the first computer unit U using the public certification key for the certification computer unit CA, which is known to the first computer unit U, and contains as last element a certificate CertN for the public key g^s from the second computer unit N.

[0148] The second certificate chain CertChain (N, U) can be verified by the second computer unit N and contains as last element a certificate CertU for the public key KU from the first computer unit U.

[0149] The third certificate chain CertChain (N, CA) can be verified by the second computer unit N and contains as last element a certificate for the public verification key from the certification computer unit CA.

[0150] The first certificate chain CertChain (U, N) and the second certificate chain CertChain (N, U) can be uniquely identified by the identifiers cidU and cidN.

[0151] Next, a third term is formed from at least one chain comprising the first value g^t and the identifiers cidU and cidN.

[0152] The third term is “hashed” using a fourth hash function h4, and the result of the hash function h4 is signed using a third signature function Sig_CA.

[0153] In addition, a time stamp TS is created in the certification computer unit CA. This time stamp is optionally included in the third term.

[0154] A fifth message M5 formed in the certification computer unit CA contains at least one chain comprising the signed third term and the certificate chains CertChain (U, N) and CertChain (N, U), and also optionally the time stamp TS and the certificate chain CertChain (N, CA). The signed hash value for the third term and also the certificate chain CertChain (N, U) are optionally encrypted using the intermediate key L.

[0155] The fifth message M5 is coded in the certification computer unit CA and is transmitted to the second computer unit N (step 305). Once the fifth message M5 is decoded in the second computer unit N, the signed hash value for the third term is verified, provided that it is not encrypted with L.

[0156] In the second computer unit N, a fourth term is now formed, said fourth term containing at least one chain comprising the certificate chain CertChain (U, N) and the signed hash value (optionally encrypted with the intermediate key L) for the third term.

[0157] In the second computer unit N, the first hash function h1 is used to form a session key K. A first input variable used for the first hash function h1 is a concatenation of a first term with the second random number r. The first term is formed by raising the first value g^t to a higher power using a secret network key s. The second random number r is used when the intention is to implement the additional security aim of assurance for the second computer unit N that the session key K is fresh (up to date). If this security aim is not required, the second random number r is not used in the method for calculating the session key K.

[0158] In the second computer unit N, a response A is formed. For forming the response A, the variants described in the first exemplary embodiment are provided.

[0159] Stringing together the second random number r, the fourth term, the response A and also an optional first data field dat1 and the optional time stamp forms a second message M2. The optional first data field dat1 is only contained in the second message M2 if this is provided in the method.

[0160] The second message M2 is coded in the second computer unit N and is transmitted to the first computer unit U (step 306).

[0161] In the first computer unit U, the second message M2 is decoded, which means that the first computer unit U has the second random number r, the response A and also possibly the optional first data field dat1 and possibly the time stamp TS available. The length of the optional first data field dat1 can be of any desired size, i.e. it is also possible for the optional first data field dat1 not to be present.

[0162] In the first computer unit U, the session key K is now likewise formed (step 307), using the first hash function h1, which is known both to the second computer unit N and to the first computer unit U. A second input variable for the first hash function h1 for forming the session key K in the first computer unit U contains at least one second term. The second term is formed from exponentiation of a public network key g^s using the first random number t. If the second random number r is provided in the method for calculating the session key K, the second input variable for the first hash function h1 for forming the session key K in the first computer unit U additionally contains the second random number r.

[0163] Once the session key K has been formed in the first computer unit U, the received response A is used to check whether the session key K formed in the first computer unit U matches the session key K which was formed in the second computer unit N (step 308).

[0164] Subject to the variants described above for forming the response A, the options described above are provided for checking the session key K using the response A.

[0165] As a result of the secret network key s being used for calculating the session key K in the second computer unit N, and the public network key g^s being used for calculating the session key K in the first computer unit U, the second computer unit N is authenticated by the first computer unit U. This is achieved provided that it is known for the first computer unit U that the public network key g^s actually belongs to the second computer unit N. That is achieved by U as a result of verification of the certificate chain CertChain (U, N) and also of the signed hash value for the third term. If the latter is encrypted with the intermediate key L, it needs to be decrypted using the intermediate key L before verification.

[0166] Subsequent to confirmation of the session key K by means of a check on the response A, a signature term is calculated (step 309). To this end, a third hash function h3 is used to form a fourth input variable. The third hash function h3 can, but need not, be the same hash function as the first hash function h1 and/or the second hash function h2. As a third input variable for the third hash function h3, a term is used which contains one or more variables from which it is possible to infer the session key unambiguously. In addition, the third input variable may contain the optional first data field dat1 or else an optional second data field dat2, if the use thereof is provided in the method.

[0167] Such variables are the first value g^t, the public network key g^s and the second random number r.

[0168] It is subsequently not possible to contest the fact that the data contained in the first optional data field dat1 and in the second optional data field dat2 is sent from the first computer unit U.

[0169] The data contained in the first optional data field dat1 and in the second optional data field dat2 may be telephone numbers, the current time or similar parameters suitable for this purpose. This information may be used as a tool for incontestable charge accounting.

[0170] A first signature function Sig_u is used to form the signature term from at least the fourth input variable. To achieve a higher degree of security, the signature term may be encrypted. In this case, the signature term is encrypted with the session key K using the encryption function Enc and forms the first encrypted term VT1.

[0171] When an optional second data field dat2 is used, a third encrypted term VT3 is calculated in the first computer unit U by encrypting the optional second data field dat2 with the session key K using the encryption function Enc. The optional second data field dat2 may also be transmitted in unencrypted form, that is to say in plain text.

[0172] As an alternative for forming the first and the third encrypted term VT1 and VT3, it is also possible for a fourth encrypted term VT4 to be formed by encrypting at least the chain comprising the signature term and optionally the data field dat2 and the intermediate key L using the session key K (step 310). In the first computer unit U, a third message M3 is formed and coded, said third message comprising at least the first encrypted term VT1 and, if the optional second data field dat2 is used, the third encrypted term VT3 or the optional second data field dat2 in plain text, or else comprising the fourth encrypted term VT4.

[0173] The third message M3 is transmitted from the first computer unit U to the second computer unit N (step 311).

[0174] In the second computer unit N, the third message M3 is decoded and then the first encrypted term VT1 and also possibly the third encrypted term VT3, or else the fourth encrypted term VT4, is decrypted. If parts of the message M5 have been encrypted with L, then the second computer unit N can now use the intermediate key L received in message M3 to decrypt the encrypted parts of the message M5. The second computer unit N can then verify the second certificate chain Cert (N, U) and also the signed hash value for the third term using the public verification key of CA. The user certificate CertU, which is now available to the second computer unit N, is used to verify the signature term.

[0175] In addition, authentication of the first computer unit U for the second computer unit N is ensured by the signature term in the third message M3, which contains the random number r, the use of which also guarantees that the third message M3 has actually been sent from the first computer unit U at the present time.

[0176] If temporary user identities are provided for the method, then the method described above is extended by a few method steps.

[0177] In the second computer unit N, a new temporary identity variable TMUIN is formed for the first computer unit U and is subsequently allocated to the first computer unit U. This may be performed, for example, by generating a random number or by means of tables in which potential identity variables are stored. The new temporary identity variable TMUIN for the first computer unit U is used to form a fifth encrypted term VT5 in the second computer unit N by encrypting the new temporary identity variable TMUIN for the first computer unit U with the session key K using the encryption function Enc.

[0178] In this case, the second message M2 additionally contains at least the fifth encrypted term VT5. The fifth encrypted term VT5 is then decrypted in the first computer unit U. The new temporary identity variable TMUIN for the first computer unit U is now available in the first computer unit U.

[0179] So that the second computer unit N is also assured of the fact that the first computer unit U has received the new temporary identity variable TMUIN correctly, the third input variable for the first hash function h1 or for the second hash function h2 additionally contains at least the new temporary identity variable TMUIN for the first computer unit U.

[0180] A few alternatives to the exemplary embodiments described above are illustrated below:

[0181] The invention is not restricted to a mobile radio system, and hence it is also not restricted to a user of a mobile radio system and to the network, but rather may be used in all areas in which cryptographic key interchange between two communication parties is required. This may be the case, for example, in a communication link between two computers wishing to interchange data in encrypted form. Without any restriction to the general validity, a first communication party was called the first computer unit U and a second communication party was called the second computer unit N above.

[0182] The following publications were cited as part of this document:

• [0183] [1] A. Aziz, W. Diffie, “Privacy and Authentication for Wireless Local Area Networks”, IEEE Personal Communications, 1994, pp. 25 to 31
• [0184] [2] M. Beller, “Proposed Authentication and Key Agreement Protocol for PCS”, Joint Experts Meeting on Privacy and Authentication for Personal Communications, P&A JEM 1993, 1993, pp. 1 to 11
• [0185] [3] C. Carroll, Y. Frankel, Y. Tsiounis, “Efficient key distribution for slow computing devices”, Conference Security & Privacy, Oakland, 1998
• [0186] [4] J. Zhou, K. Lam, “Undeniable billing in mobile communications”, preprint 1998
• [0187] [5] U.S. Pat. No. 5,214,700
• [0188] [6] DE brochures: Telesec. Telekom, Produktentwicklung Telesec beim Fernmeldeamt Siegen [Telesec. Telecom, product development Telesec at the Siegen exchange], pp. 12–13
• [0189] [7] U.S. Pat. No. 5,222,140
• [0190] [8] U.S. Pat. No. 5,153,919
• [0191] [9] M. Beller et al, Privacy and Authentication on a Portable Communication System, IEEE Journal on Selected Areas in Communications, Vol. 11, No. 6, pp. 821–829, 1993
• [0192] [10] DE 195 18 5465 C1
• [0193] [11] W. Diffie, P. C. van Oorschot, M. Wiener, “Authentication and authenticated key exchanges”, Designs, Codes and Cryptography, Vol. 2, pp. 107–125, 1992