METHOD FOR SECURELY PERFORMING A PUBLIC KEY ALGORITHM

Abstract

Provided is a method for securely performing a public key algorithm comprising cryptographic computations using a private key. It includes selecting (S1), by a server device, a set of mutually coprime integers (p1,...,pn) as a base of a Residue Number System (RNS-base B), with n an integer; computing (S2), by said server device, a RNS representation of said private key, said RNS representation of an integer x in [0, P-1], with P the product of every elements of the base, being the list (x1, ...xn) with xi = x mod pi, i being an integer in [1,n]; sending (S3), by said server device, the computed RNS representation to a client device; and performing (S4), by said client device, the cryptographic computations of the public key algorithm in said RNS base using said sent RNS representation.

Claims

1. A method for securely performing a public key algorithm comprising cryptographic computations using a private key, said method being performed by a system (100) comprising a client device (101) and a server device (104) and comprising the steps of: selecting (S1), by said server device, a set of mutually coprime integers (p.sub.1,...,p.sub.n) as a base of a Residue Number System (RNS-base B), with n an integer; computing (S2), by said server device, a RNS representation of said private key, said RNS representation of an integer x in [0, P-1], with P the product of every elements of the base, being the list (x.sub.1, ...x.sub.n) with x.sub.i = x mod p.sub.i, i being an integer in [1 ,n]; sending (S3), by said server device, the computed RNS representation to the client device; and performing (S4), by said client device, the cryptographic computations of the public key algorithm in said RNS base using said sent RNS representation.

2. The method of claim 1, wherein said client device performs additionnal countermeasures against side-channel and fault attacks to be applied to said public key algorithm.

3. The method of claim 2, wherein said public key algorithm is among : RSA encryption and signature schemes, ECDSA (Elliptic Curve Digital Signature Algorithm) signature scheme, EIGamal encryption and signature schemes.

4. The method of claim 3, wherein said cryptographic computations performed by said client device are among: addition, multiplication, modular addition/multiplication, inversion, Montgomery multiplication.

5. The method of claim 3, wherein said cryptographic computations performed by said client device are arithmetic operations to be executed by said public key algorithm.

6. The method of claim 5, wherein performing, by said client device, the arithmetic operations of the public key algorithm comprises a randomization of inputs and/or outputs of said arithmetic operations.

7. The method of claim 6, wherein performing, by said client device, the arithmetic operations of the public key algorithm comprises a detection of Fault attacks.

8. The method of claim 7, wherein said arithmetic operations of the public key algorithm in said RNS base are performed separately along each vector of said base in a random order.

9. The method of claim 8, wherein RNS representations of inputs of said cryptographic computations are computed and wherein the cryptographic computations of the public key algorithm in said RNS base are performed using said RNS representations of their inputs.

10. The method of claim 9, wherein said RNS representations of inputs of said cryptographic computations are computed by the server device and transmitted to the client device.

11. The method of claim 9, wherein said RNS representations of inputs of said cryptographic computations are computed by the client device using secure techniques configured for performing a reduction modulo an integer without revealing said integer.

12. The method of claim 1, wherein the server device and the client device comprise acomputer program product directly loadable into a memory thereof, comprising software code instructions for performing the steps.

13. A system comprising a client device and a server device comprising each one a processor and an interface and a memory for processing software code instructions configured thereon to select (S1), by said server device, a set of mutually coprime integers (p.sub.1,...p.sub.n as a base of a Residue Number System (RNS-base B), with n an integer; compute (S2), by said server device, a RNS representation of said private key, said RNS representation of an integer x in [0, P-1], with P the product of every elements of the base, being the list (x.sub.1, ...x.sub.n) with x.sub.i = x mod p.sub.i, i being an integer in [1,n]; send (S3), by said server device, the computed RNS representation to the client device; and perform (S4), by said client device, the cryptographic computations of the public key algorithm in said RNS base using said sent RNS representation.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0033] The following description and the annexed drawings set forth in detail certain illustrative aspects and are indicative of but a few of the various ways in which the principles of the embodiments may be employed. Other advantages and novel features will become apparent from the following detailed description when considered in conjunction with the drawings and the disclosed embodiments are intended to include all such aspects and their equivalents.

[0034] FIG. 1 is a schematic illustration of a system according to an embodiment of the present invention;

[0035] FIG. 2 is a schematic illustration of a client device according to an embodiment of the present invention;

[0036] FIG. 3 illustrates schematically a method enabling to perform cryptographic operations using a private key without disclosing said private key to an attacker in a whitebox context according to an embodiment of the present invention.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

[0037] The invention aims at providing a method enabling a client device to perform cryptographic computations of a public key algorithm using a corresponding private key in such a way that it is makes it more difficult for an attacker to retrieve the secret key in a white box context and that it is protected against side channel analysis. Such a public key algorithm may for example be among RSA encryption and signature schemes, ECDSA (Elliptic Curve Digital Signature Algorithm) signature scheme or ElGamal encryption and signature schemes ; and the cryptographic computations performed by the client device may be arithmetic operations to be executed by such a public key algorithm. Such cryptographic computations performed by said client device may for example include addition, multiplication, modular addition/multiplication, inversion, Montgomery multiplication.

[0038] The main idea of the invention is to apply to the secret key prior to the execution of the cryptographic computations a transformation into a Residue Number System. Indeed, after choosing a set of n mutually coprime integers (p.sub.1,...,p.sub.n) as a base of the RNS, any integer may be defined by its residues obtained after modular reductions by each of the vectors of the base : x in [0, P-1], with P the product of every elements of the base, may be expressed as the list (x.sub.1, ...x.sub.n) with x.sub.i = x mod p.sub.i for any integer i in [1,n].

[0039] After such a transformation of the private key has been performed, many operations of cryptographic computations may be performed easily along each vector of the base instead of using the operands of the operations as whole numbers. Even if an attacker would be able to recover the value of the secret key expressed in the RNS base, either directly in a white box context, or by side-channel analysis, such a value would be useless as long as the attacker is no knowledge of the RNS base in which the key is expressed. In order to keep such a base hidden in a white box context, the transformation of the secret key may be performed by a distant server device, considered as secure, before the secret key is transmitted to the client device.

[0040] As illustrated on FIG. 1, the method according to the invention is performed by a system 100 comprising a client device 101 operated by a user 102 and configured for interacting through a network 103 with one or more distant server devices 104.

[0041] FIG. 2, is a schematic illustration of such a client device 101. It may include a processor 201 connected via a bus 202 to at least one memory among a random access memory (RAM) 203, a read-only memory (ROM) 204, a non-volatile memory (NVM) 205 or a cache memory.

[0042] The client device 101 may further include a communication interface 206 which may be used to connect it to various forms of wireless networks, e.g., wide-area networks, WiFi networks, or mobile telephony networks. Alternatively, the client device 101 may connect to networks via wired network connections such as Ethernet.

[0043] The client device 101 may also include input/output means 207 providing interfaces to the user of the client device 101, such as one or more screens, loudspeakers, a mouse, tactile surfaces, a keyboard etc...

[0044] Such a client device may for example be a computer or a smartphone.

[0045] The server device 104 has the same kind of architecture and may include the same elements as the client device (301, ...).

[0046] The following paragraphs describe with more details the steps of a method according to the invention.

[0047] In a first step S1, the server device selects a set of mutually coprime integers (p.sub.1,...,p.sub.n) as a base of the Residue Number System, with n an integer.

[0048] In a second step S2, the server device computes a RNS representation of the private key.

[0049] In a third step S3, the server device sends the computed RNS representation to the client device. After he receives it, the client device may use it to perform calculations using the private key without returning it back to its original form.

[0050] In a fourth step S4, the client device performs the cryptographic computations of the public key algorithm in said RNS base using said sent RNS representation of the private key. The results of such computations are also expressed in the RNS base selected by the server device in the first step.

[0051] By doing so, the performed computations do not manipulate at any time the cleartext value of the private key. Thus, an attacker could not retrieve the private key from his observations of the computations, neither directly by static analysis of the memory, nor by performing side channel analysis.

[0052] In order to use the result of the cryptographic computations, it will most likely be required to reverse the RNS transformation by expressing this result in a base known to the client device.

[0053] In such a case, in a first embodiment, the client device may send back the computations result to the server device and make it apply to the result the inverse operation of the RNS transformation performed in the second step S2. The server device may then send back the value of the result to the client device. By doing so, the result of the cryptographic computations is exposed to an attacker in a whitebox context but the private key is not. Exposing the result of the cryptographic computations to an attacker is not always an issue. For example, when such a result is a signature, it is meant to be publicly shared and not to be kept secret. In other cases, such as in the case of decryption of an encrypted value, the method according to the invention, by preventing a disclosure of the private key, prevents an attacker from being able to decrypt any other value encrypted with the same public key. In addition, the server device may, before transmitting the result of the inverse operation of the RNS transformation to the client device, encrypt it using another encryption key shared with the client device. This other encryption key may for example be a single-use session key, such that even if an attacker gets knowledge of it, he cannot re-use it.

[0054] In a second embodiment, the RNS base selected in the first step is transmitted by the server device to the client device and the client device is able to compute the expression in another base of the result of the cryptographic computations expressed in the RNS base.

[0055] In order to further increase the level of security of the method, the client device may perform additional countermeasures protecting the public key algorithm against side-channel and fault attacks. Such countermeasures are especially needed when the client device stores the RNS base to protect it and to protect operations translating a value from the RNS base to another base, in order to prevent an attacker from gaining knowledge of the selected RNS base and then defeat the protection provided by the RNS transformation of the private key. In such a case, the invention makes it harder for an attacker to retrieve the clear value of the private key since he must both retrieve it in RNS base and gain knowledge of the RNS base itself in order to get an understandable value of the private key.

[0056] Particularly, the arithmetic operations performed in the RNS base may comprises a randomization of the inputs and/or the outputs of these arithmetic operations. Such a randomization is usually performed in order to protect an algorithm against side-channel analysis.

[0057] Such arithmetic operations may also include a detection of Fault attacks, for example by using redundancy techniques.

[0058] The cryptographic operations performed by the client device have at least one operand in addition to the private key. When the client device performs these operations in the RNS base, the operands of the operations shall also be expressed in the same RNS base. As a result, the method according to the invention may comprise an operand transformation step S4-0 performed before the fourth step S4 during which RNS representations of inputs of the cryptographic computations are computed. The cryptographic computations of the public key algorithm in the RNS base may then be performed using these RNS representations of their inputs.

[0059] In a first embodiment, these RNS representations of inputs of the cryptographic computations may be computed by the server device and transmitted to the client device. By doing so, the client device does not need to know the RNS base.

[0060] In a second embodiment, these RNS representations of inputs of said cryptographic computations are computed by the client device. For that, the client device may have knowledge of the RNS base. As discussed above, such a knowledge comes with the risk that an attacker may discover the RNS base. Thus, in such a case additional countermeasures have to be applied in order to keep the RNS base secret. Alternatively, the client device may compute such representations by using secure techniques configured for performing a reduction modulo an integer without revealing said integer. By doing so, the client device is able to compute the RNS representation of any value without knowing the RNS base, which guarantees that an attacker will not discover it, even in a whitebox context.

[0061] When the cryptographic operations are performed by the client device in the selected RNS base, these operations must be performed along each vector of the selected base. Since all these vectors of the base are coprime with each other, no carry has to be propagated from one vector to another.

[0062] As a result, the operations in the RNS may be performed separately along each vector independently from the operations performed along the other vectors of the same base. Consequently, for a given operation to be performed, it may be performed separately along each vector of said base in a random order.

[0063] The same operation may even be applied along several vectors of the selected base at the same time, in parallel.

[0064] According another aspect, the invention relates to a computer program product directly loadable into the memory of at least one computer, comprising software code instructions for performing the steps of the method described here above when said product is run on the computer.

[0065] The described solution enables to protect the private key during the execution of the cryptographic operations, even in a white box context, including against side-channel analysis. Since RNS representation computation is not very expensive and performing cryptographic computations in an RNS base does not induce a strong increase of the cost of the cryptographic computations, the computation time induced by such a method remains low compared to other countermeasures against whitebox attacks.