KEY GENERATION AND PACE WITH PROTECTION AGAINST SIDE CHANNEL ATTACKS

Abstract

A method for key generation is arranged in a client processor device, by means of which a second public client key P.sub.c′ of the client is generated. The public key P.sub.c′ is formed by a calculation, or sequence of calculations, which does not contain any operation whose result depends exclusively on the nonce s and at least one public value, or the public key P.sub.c′ being formed by a calculation, or sequence of calculations, where into each operation in which the nonce s enters, at least one non-public value enters the first private client key k.sub.c or the second private client key k.sub.c′, for example as a result of the calculation P.sub.c′=(k.sub.c′.Math.s).Math.G+(k.sub.c′.Math.k.sub.c).Math.P.sub.t.

Claims

1.-12. (canceled)

13. A method for key generation, arranged in a client processor device, by means of which a second public client key P.sub.c′ of the client is derived, wherein the method for key generation comprises the steps carried out in the client processor device: (1.1) generating a nonce s; (2.1) generating a first asymmetric key pair [k.sub.c, P.sub.c] of the client, comprising a first public client key P.sub.c and a first private client key k.sub.c, the first public client key P.sub.c being formed as a result of the point multiplication P.sub.c=k.sub.c.Math.G of the first private client key k.sub.c with the generator point G of the elliptic curve; (2.2) receiving, from a terminal, a first public terminal key P.sub.t which is included in a first asymmetric key pair of the terminal, which key pair comprises the first public terminal key P.sub.t and a first private terminal key k.sub.t; (3.1) generating a second asymmetric key pair [k.sub.c′, P.sub.c] of the client, comprising a second public client key P.sub.c′ and a second private client key k.sub.c′; Wherein the public key P.sub.c′ is formed by a calculation, or sequence of calculations, which does not contain any operation whose result depends exclusively on the nonce s and at least one public value.

14. The method for key generation, arranged in a client processor device, by means of which a second public client key P.sub.c′ of the client is derived, wherein the method for key generation comprises the steps carried out in the client processor device: (1.1) generating a nonce s; (2.1) generating a first asymmetric key pair [k.sub.c, P.sub.c] of the client, comprising a first public client key P.sub.c and a first private client key k.sub.c, the first public client key P.sub.c being formed as a result of the point multiplication P.sub.c=k.sub.c.Math.G of the first private client key k.sub.c with the generator point G of the elliptic curve; (2.2) receiving, from a terminal, a first public terminal key P.sub.t which is included in a first asymmetric key pair of the terminal, which key pair comprises the first public terminal key P.sub.t and a first private terminal key k.sub.t; (3.1) generating a second asymmetric key pair [k.sub.c′, P.sub.c′] of the client, comprising a second public client key P.sub.c′ and a second private client key k.sub.c′; wherein the public key P.sub.c′ is formed by a calculation, or sequence of calculations, where into each operation in which the nonce s enters, at least one non-public value enters, in particular the first private client key k.sub.c or the second private client key k.sub.c′.

15. The method according to claim 13, wherein: as a public value, or public values, at least one of the following is provided: the generator point G, the first public terminal key P.sub.t, the first private terminal key k.sub.t, the intermediate value H.sub.c of the PACE protocol; or/and as a non-public value, at least one of the following is provided: the first private client key k.sub.c, the second private client key k.sub.c′.

16. The method according to claim 13, wherein step (E3.2*) is carried out as one of the following calculations (i), (ii), (iii) or (iv) which comprise therein one or more operations, in particular point additions + or / and point multiplications .Math. or/and modular multiplications .Math. or/and modular divisions /:
P.sub.c′=P1+P2,  (i) with: P1=(k.sub.c′.Math.s).Math.G or P1=s.Math.(k.sub.c′.Math.G), and with: P2 is equal to the result of an operation or sequence of operations with the second private client key k.sub.c′, the first private client key k.sub.c and the first public terminal key P.sub.t; in particular: P2=(k.sub.c′.Math.k.sub.c).Math.P.sub.t; or P2=k.sub.c′.Math.H.sub.c; or
P.sub.c′=(k.sub.c′.Math.s).Math.(G+(k.sub.c/s).Math.P.sub.t); or  (ii)
P.sub.c′=s.Math.((k.sub.c′.Math.G)+(k.sub.c′/s).Math.H.sub.c); or  (iii)
P.sub.c′=s.Math.((k.sub.c′.Math.G)+(k.sub.c′.Math.k.sub.c/s).Math.P.sub.t);  (iv) wherein H.sub.c is equal to the result of the point operation H.sub.c=k.sub.c.Math.P.sub.t.

17. The method for key generation according to claim 13, wherein step (1.1) generating a nonce is carried out as: (E1.1*) generating and making available, or making available, at least one masking value m; generating a masked nonce s.sub.m; and wherein in step (E3.2*) the masked nonce s.sub.m and the masking value m, [s.sub.m, m], are used as nonce s.

18. The method according to claim 17, wherein (E3.2*) wherein step (E3.2*) is carried out as one of the following calculations: P.sub.c′=P1+P2, with: P1=(k.sub.c′.Math.s.sub.m+k.sub.c′.Math.(Σ.sub.j=1.sup.km.sub.j)).Math.G or P1=(k.sub.c′.Math.s.sub.m).Math.G+Σ.sub.j=1.sup.k((k.sub.c′.Math.m.sub.j).Math.G) and with: P2 equal to the result of a point operation, or sequence of point operations, on the second private client key k.sub.c′, the first private client key k.sub.c and the first public terminal key P.sub.t.

19. The method according to claim 13, further comprising: (C) (1.1) in the client, encrypting the nonce s with a password PIN stored in the client so that an encrypted nonce s′=Enc(s; PIN) is generated, or in the case of a masked nonce s.sub.m (E1.1*) encrypting the masked nonce s.sub.m and the mask m with the password PIN so that an encrypted nonce s′=Enc′(s.sub.m, m; PIN) is generated; (C) (1.2) transmitting the encrypted nonce s′ from the client to the terminal.

20. A client processor device arranged to execute a method for key generation according to claim 13.

21. A method for key agreement and authentication between a client and a terminal, comprising the steps of: (C) in the client, carrying out a method for key generation according to claim 19 so that a second public client key P.sub.c′ of the client is derived; (C) (2.2) transmitting the first public client key P.sub.c to the terminal; (T) (1.2) in the terminal, accepting a password PIN_user which has been entered by a user at the terminal; (T) (1.4) in the terminal, receiving the encrypted nonce s′ sent by the client and decrypting the encrypted nonce s′ with the password PIN_user entered by the user so that a terminal nonce s.sub.t=Dec(s,′ PIN-user) is derived; (T) in the terminal, carrying out a terminal method for key generation comprising the steps of: (T) (2.1) in the terminal, generating the first asymmetric key pair [k.sub.t, P.sub.t] of the terminal, comprising the first public terminal key P.sub.t and the first private terminal key k.sub.t, the first public terminal key P.sub.t being formed as a result of the point multiplication P.sub.t=k.sub.t.Math.G of the first private terminal key k.sub.t with the generator point G on the elliptic curve; (T) (2.2) in the terminal, receiving, from the client, the first public client key P.sub.c; (T) in the terminal, generating a second asymmetric key pair [k.sub.t′, P.sub.t′] of the terminal, comprising a second public terminal key P.sub.t′ and a second private terminal key k.sub.t′, the second public terminal key P.sub.t′ being derived using the first public client key P.sub.c received from the client, the first private terminal key k.sub.t, the terminal nonce s.sub.t′, the generator point G on the elliptic curve, and the second private terminal key k.sub.t′; (AUTH) using the second public client key P.sub.c′ and the second public terminal key P.sub.t′ in a key agreement and authentication protocol between the client and the terminal.

22. The method according to claim 21, wherein when generating the second asymmetric key pair [k.sub.t′, P.sub.t′] of the terminal, the second public terminal key P.sub.t′ is derived by the following substeps: (T) (2.3) in the terminal, generating a derived point H.sub.t on the elliptic curve by point multiplication H.sub.t=k.sub.t.Math.P.sub.c of the first public client key P.sub.c received from the client with the first private terminal key k.sub.t; (T) (2.4) in the terminal, deriving a derived generator point G.sub.t′ on the elliptic curve by point multiplication of the terminal nonce s.sub.t with the generator point G and point addition of the thereby generated point with the derived point H.sub.t, according to
G.sub.t′=s.sub.t.Math.G+H.sub.t; (T) (3.1) in the terminal, generating the second private terminal key k.sub.t′; (T) (E3.2*) in the terminal, deriving the second public terminal key P.sub.t′ by point multiplication P.sub.t′=k.sub.t′.Math.G.sub.t′ of the derived generator point G.sub.t′ with the second private terminal key k.sub.t′.

23. The method according to claim 21, wherein as a protocol the PACE protocol is used.

24. The method according to claim 13, wherein as the private client key of a respective key pair a random number is provided, which is generated in the client or is generated outside the client and is transmitted securely into the client and is stored there securely—volatile or permanent; or/and wherein as the private terminal key of a respective key pair a random number is provided, which is generated in the terminal or is generated outside the terminal and is stored securely in the terminal.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0034] Hereinafter, the invention will be explained more closely on the basis of embodiment examples and with reference to the drawings, in which are shown:

[0035] FIG. 1 Excerpts from an exemplary conventional PACE protocol comprising an elliptic curve Diffie-Hellman method for key generation;

[0036] FIG. 2 Excerpts from an exemplary PACE protocol modified according to the invention, comprising a method for key generation, according to one embodiment of the invention which is based on elements of the method in FIG. 1.

DETAILED DESCRIPTION OF EMBODIMENT EXAMPLES

[0037] FIG. 1 shows excerpts from an exemplary conventional PACE protocol comprising an elliptic curve Diffie-Hellman method for key generation that has already been described above.

[0038] FIG. 2 shows excerpts from an exemplary PACE protocol modified according to the invention, comprising a method for key generation, according to an embodiment of the invention which is based on elements of the method in FIG. 1.

[0039] In an already realized, yet unpublished implementation, the PACE protocol was implemented according to the steps described in Table 1 and a multi-add function was provided as described in 2.4. All other required functions correspond to those that are also required for other ECC implementations. The underlying group is an elliptic curve with generator point G having prime number order. In FIGS. 1 and 2, integer variables are denoted with small letters and points on the elliptic curve are denoted with capital letters.

[0040] The difference between the method according to the invention in FIG. 2 and the conventional method in FIG. 1 consists substantially in the steps (2.3), (2.4) executed in the client, which are omitted in the method according to the invention, and in the step (E3.2*) executed in the client, which is modified compared to the conventional method and in which the omitted steps (2.3), (2.4) are taken up.

[0041] According to the invention, the second public client key is calculated according to a function P.sub.c′=Generate_public_key_with_mapping(G, P.sub.t; s.sub.m, m, k.sub.c, k.sub.c′)=(k.sub.c′.Math.s).Math.G+(k.sub.c′.Math.k.sub.c).Math.P.sub.t.

[0042] According to the embodiment of the invention represented in FIG. 2, the key agreement and authentication method between the client and the terminal is carried out as follows. The order of the steps is effected, insofar as required by the course of the method, in the order stated. If an order is not specified by the method, the order in which the steps are carried out may also differ from the order in which the steps are listed. A masked nonce s.sub.m can be used as a nonce, as shown in FIG. 2 as step E1.1*. Alternatively, an unmasked nonce s can be used as a nonce, according to step 1.1 of FIG. 1, as indicated in FIG. 2 by the reference to step 1.1 of FIG. 1.

[0043] Step 1.1 in the client is effected either without masking the nonce (1.1 as in FIG. 1) or with masking the nonce (E1.1* as in FIG. 2):

(1.1) without masking the nonce:
(C) (1.1) in the client, generating a nonce s;
(C) (1.1) in the client, encrypting the nonce s, with a password (PIN) stored in the client, so that an encrypted nonce s′=Enc(s; PIN) is generated;
(C) (E1.1*) with masking the nonce:
(C) (E1.1*) in the client, generating a mask m by the function m=Generate_mask( );
(C) (E1.1*) in the client, generating a masked nonce s.sub.m by the function s.sub.m=Generate_masked_nonce(m);
(C) (E1.1*) in the client, encrypting the nonce s.sub.m with the mask m and the password PIN stored in the client by the function s′=Enc(s.sub.m, m; PIN) so that the encrypted nonce s′ is generated.

[0044] In both cases, non-masked and masked nonce, the method continues as follows:

(C) (1.2) transmitting the encrypted nonce s′ from the client to the terminal;
(T) (1.3) in the terminal, accepting a password PIN_user which has been entered by a user at the terminal;
(T) (1.4) in the terminal, receiving the encrypted nonce s′ sent by the client and decrypting the encrypted nonce s′ with the password entered by the user so that a terminal nonce s.sub.t=Dec(s,′ PIN-user) is derived;
(C) (2.1) in the client, generating a first asymmetric key pair [k.sub.c, P.sub.c] of the client, comprising a first public client key P.sub.c and a first private client key k.sub.c, the first public client key P.sub.c being formed as a result of the point multiplication P.sub.c=k.sub.c.Math.G of the first private client key k.sub.c with the generator point G of the elliptic curve; the first private client key k.sub.c being a random number which is generated in the client;
(T) (2.1) in the terminal, generating a first asymmetric key pair [k.sub.t, P.sub.t] of the terminal, comprising a first public terminal key P.sub.t and a first private terminal key k.sub.t, the first public terminal key P.sub.t being formed as a result of the point multiplication P.sub.t=k.sub.t.Math.G of the first private terminal key k.sub.t with the generator point G of the elliptic curve; the first private terminal key k.sub.t being preferably a random number which is preferably generated in the terminal;
(C) (2.2) transmitting the first public client key P.sub.c from the client to the terminal;
(T) (2.2) transmitting the first public terminal key P.sub.t from the terminal to the client;
(C) (2.2) in the client, receiving, from the terminal, the first public terminal key P.sub.t;
(T) (2.2) in the terminal, receiving, from the client, the first public client key P.sub.c;
(T) (E2.3*) in the terminal, generating a derived point H.sub.t on the elliptic curve by point multiplication H.sub.t=k.sub.t.Math.P.sub.c of the first public client key P.sub.c received from the client with the first private terminal key k.sub.t;
(T) (E2.4*) in the terminal, deriving a derived generator point G.sub.t′ on the elliptic curve by point multiplication of the terminal nonce s.sub.t with the generator point G and point addition of the thereby generated point with the derived point H.sub.t, according to G.sub.t′=s.sub.t.Math.G+H.sub.t;
(T) (3.1) in the terminal, generating the second private terminal key k.sub.t′;
(T) (E3.2*) in the terminal, deriving the second public terminal key P.sub.t′ by point multiplication Pt′=k.sub.t′.Math.G.sub.t′ of the derived generator point G.sub.t′ with the second private terminal key k.sub.t′.
(C) (3.1) in the client, generating a second asymmetric key pair [k.sub.c′, P.sub.c′] of the client, comprising a second public client key P.sub.c′ and a second private client key k.sub.c′; the second private client key k.sub.c′ being a random number which is generated in the client;
(C) (E3.2*) in doing so, the second public client key P.sub.c′ is formed as a result of the point operation P.sub.c′=(k.sub.c′.Math.s).Math.G+(k.sub.c′.Math.k.sub.c).Math.P.sub.t; here, two results of two point multiplications (k.sub.c′.Math.s).Math.G and (k.sub.c′.Math.k.sub.c).Math.P.sub.t are generated, once by point multiplication of the product of the second private client key k.sub.c′ and the client nonce s (which may optionally be present in masked form) with the generator point G, and once by point multiplication of the product of the second private client key k.sub.c′ and the first private client key k.sub.c with the first public terminal key P.sub.t; the two results are combined by a point addition so that finally the second public key P.sub.c′ of the client is derived;
(AUTH) Use of the second public client key P.sub.c′ and the second public terminal key P.sub.t′ in an authentication and key agreement protocol between the client and the terminal, for example in the PACE protocol.