FIELD OF THE INVENTION

The present invention relates to the field of software implementation of an RSA signature/decryption in a whitebox environment, and of associated cryptographic devices, and more particularly to cryptographic devices allowing to keep cryptographic assets secure even when subject to white-box attacks.

BACKGROUND OF THE INVENTION

A first application of cryptography is to provide mechanisms to protect data, such as messages exchanged on a communication channel, from being accessed by an unauthorized user. A plaintext piece of data may be protected by converting it into a ciphertext that may only be deciphered, i.e., converted back into the original data by someone or some device owning a secret key required for performing the deciphering operation.

Two major categories of cryptography are secret key cryptography and private-key-public-key cryptography (herein, simply referred to as public key cryptography). In public key cryptography, the recipient of a ciphertext message, i.e., the decrypting party, has a private key or secret key required to decipher ciphertext messages encrypted with the public key. In other words, there is an association between a particular private key and a particular public key; they form a key pair. The public key is made available to anyone who wishes to send an encrypted message (a ciphertext message) whereas the corresponding secret key is kept secret by the intended recipient of messages.

Public key cryptography can also be used for authenticating the issuer of a message. Such an issuer can generate a signature based on said message using his private key. The recipient of the message can then use the public key of the alleged issuer for verifying that the signature was generated using the associated private key ie that the issuer of the message is indeed who he claims to be. An example of widely used public key cryptosystem is Rivest-Shamir-Adelson (RSA) cryptosystem. Such a cryptosystem is based on the practical difficulty of factoring the product of two large prime numbers and uses a public key (e, N) and a private key d such that e.d=1 modulo phi(N), with N, d and e integers and phi( ) Euler's totient function. RSA cryptosystem allows publicly sharing the public key (e, N) for producing ciphertexts while enabling that only someone with knowledge of the private key d can decipher such ciphertexts and get knowledge of the private data enciphered in it. The private key can also be used to generate a signature for a message. Such a signature can then be verified by anyone using the associated public key. Of course the private key d must remain secret, otherwise any attacker having knowledge of the secret key could decipher ciphertext ciphered with the public key, and the privacy of enciphered data would not be guaranteed anymore. Such an attacker could also generate forged signatures of a message as if he was the true owner of the private key.

Traditionally, in order to ensure that the secret key remains secret, the decryption or signature algorithm is supposed to be executed in a secure environment only. The device executing such an algorithm is assumed trusted, preventing any attacker trying to decipher a secret message from accessing. This is referred to as black box cryptography.

However, cryptographic processes are more and more deployed in applications executed on open devices. For example many user devices now have access to the Internet, such as PCs, tablets, smartphones, and can be used for playing copyrighted digital content such as audio or video files. Such files may be cryptographically protected, for example using digital rights management (DRM) files, in order to make it available to a user only as long as the user as subscribed to an online multimedia streaming service.

Cryptographic processes are then executed in an environment where not all users or devices can be trusted. Such a context is usually called a white-box attack context. In such a context, cryptosystems sensitive data such as private keys, are vulnerable to attacks since the attacker has full access to the software implementation of the cryptographic processes. Binary code of such processes is completely accessible and editable by the attacker that can analyze the binary code of the cryptography application and, for example, memory pages or registers used for temporary storage during the execution. Such manipulation may, for example, be performed using debuggers and hardware emulation tools.

Software implementations of cryptosystems able to resist white-box attacks have been sought. In such implementations the private key may be provided on the subscriber's cryptography device, e.g., a mobile device such as a mobile telephone, in a manner that it can be used by the device to decrypt or generate a signature without revealing either the key or the algorithm to the subscriber. The key might be hidden in some way inside the code implementing the decryption/signature algorithm and the algorithm may be obfuscated so that it is very difficult to determine where the key is hidden. The key's value might be also protected so that it is very difficult to determine it. This is referred to as white-box cryptography.

A very powerful cryptography mechanism, known as fully homomorphic encryption (FHE), was introduced by Craig Gentry in 2009 in [Gentry] Fully Homomorphic Encryption Using Ideal Lattices, in Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC '09), pp. 169-178. ACM, 2009. [Gentry] is incorporated herein by reference in its entirety. Broadly, in FHE, calculations may be performed on encrypted values, with results decrypted, to produce results that are the same as if the calculation had been performed on corresponding plaintext values. FHE provides for the application of an arithmetic circuit to a set of ciphertexts and the result is an encrypted value that would be the same as if it had been evaluated on the underlying plaintext. To be considered fully homomorphic, the encryption scheme allows for computations using arbitrary functions and is capable of evaluation of any circuit.

Homomorphic encryption has been considered for use in white-box cryptography. See e.g., (2009) Brecht Wyseur (COSIC) Ph.D. thesis, (2009), http://www.cosic.esat.kuleuven.be/publications/thesis-152.pdf (accessed on Aug. 29, 2016).

However, current performances of FHE schemes applied to RSA cryptosystem are low. Computation time required for performing RSA cryptographic operations using FHE schemes are too high to enable a practical secure implementation of RSA in a white-box environment on existing user devices.

Therefore, there is a need for a software implementation, and an associated cryptographic device, of RSA cryptosystem secured by a FHE scheme in a white-box environment and achieving a computation time enabling practical application.

SUMMARY OF THE INVENTION

For this purpose and according to a first aspect, this invention therefore relates to a method of generating a secure RSA key by a server comprising the steps of:generating a private RSA key d and a RSA modulus integer N, where N and d are integers;splitting the private key d in J key shares djof length n, with n=log2N, j in [1, J], J being an integer, and such that d=d1+d2+ . . . +dJmod phi(N), where each key share djis equal to (dj(0). . . dj(i). . . dj(n/b−1)) with each key share component dj(i)in {0 . . . 2{circumflex over ( )}b−1} and i in [0, n/b−1], b being an integer inferior to n and phi the Euler's totient function;encrypting with a fully homomorphic encryption (FHE) algorithm each key share component dj(i)of the private RSA key d by using a Fully Homomorphic Encryption secret key psassociated with a set Sscomprising the index couple (i,j), to generate an encrypted key share component edj(i)of said secure RSA key,said set Ssbeing a set of integer couples, among a predetermined integer number u of disjoint sets {S1, S2. . . , Ss, Ss+1, . . . Su} generated such that: U{Ss}={(i,j) such that i in [0, n/b−1], j in [1, J]} and each said set among {S1, . . . Su} being associated with a Fully Homomorphic Encryption (FHE) secret key.

Such a method enables to generate a RSA private key under a form that can be securely stored on a client device and then securely used for RSA signature generation or for RSA-encrypted message decryption. The RSA private key is indeed split in multiple key share components and such components are FHE-encrypted using multiple secret keys, making it difficult for an attacker to recover the whole RSA private key on the client device, even in a whitebox environment.

In a first embodiment, said FHE secret keys of said sets may be all identical.

It makes it unnecessary for a client device using the encrypted key share components to use sets defined by the server. The client device can then define its own sets while remaining able to perform FHE decryption of FHE encrypted values.

In a second embodiment, {S1, . . . Su} comprises at least a first set and a second set such that the FHE secret key associated with the first set is different from the FHE secret key associated with the second set.

Doing so, even if an attacker retrieves the FHE secret key associated with a given set, he won't be able to decrypt all key share components and retrieve the whole RSA private key d.

The fully homomorphic encryption algorithm may be a DGHV (Dijik, Gentry, Halevi, Vaikuntanathan) Scheme such that a ciphertext c for a data m in ZN, FHE encrypted with a FHE secret key p, is equal to q·p+N·r+m where q is a random integer, r is a random integer and N is the RSA modulus such that |p|>CS(2 log N+log r) with CSthe maximum number of elements of any set SSin {S1, . . . , SU}, and such that the ciphertext c is deciphered by computing m=(c mod p) mod N.

Such a FHE scheme enables a practical and efficient implementation of FHE operations described in this document.

According to a second aspect, this invention therefore relates also to a method of secure generation of a RSA signature of a message m by a client device with the secure RSA key generated according to the first aspect, comprising the steps of:receiving from the server the generated encrypted key share components edj(i)with j in [1, J] and i in [0, n/b−1];computing an intermediate value YSfor each set SSin {S1, . . . , Su} from said encrypted key share components edj(i)whose index couple (i,j) is comprised in SSand from said message m, such that said computed intermediate value is a part of the RSA signature of said message m, under FHE-encrypted form;generating the RSA signature of said message m by combining said computed intermediate values for all sets.

Such a method enables the client device to generate a RSA signature of a message without ever disclosing the RSA private key d. Key share components are only handled under FHE-encrypted form, ensuring their security against any attacker.

According to a third aspect, this invention therefore relates also to a method of secure RSA decryption by a client device of an RSA encrypted message c encrypted with a public RSA key forming a key pair with a secure private RSA key generated according to the first aspect, comprising the steps of:receiving from the server the generated encrypted key share components edj(i)with j in [1, J] and i in [0, n/b−1];computing an intermediate value YSfor each set SSin {S1, . . . , Su} from said encrypted key share components edj(i)whose index couple (i,j) is comprised in SSand from said encrypted message c, such that said computed intermediate value is a part of the RSA decrypted message m, under FHE-encrypted form;decrypting the encrypted message c by combining said computed intermediate values for all sets.

Such a method enables the client device to decrypt a RSA encrypted message without ever disclosing the RSA private key d. Key share components are only handled under FHE-encrypted form, ensuring their security against any attacker.

The computation of an intermediate value YSfor a set SSin (S1, . . . , Su) of the method of secure generation of an RSA signature of a message m, h(m)dmod N, according to the second aspect, may comprise:

for all (i,j) in Ss, computing z(i)=h(m)(2{circumflex over ( )}b){circumflex over ( )}imod N and computing yj(i)=Σw=02b−1(Πv=0,v≠w2b−1(edj(i)−v)/(w−v))z(i){circumflex over ( )}wcalculating the product of yj(i)for all (i,j) in the set Ss.

Such operations enable to combine all encrypted key shares associated with each set into an intermediate value suitable for generating an RSA signature without performing a FHE decryption of the key share components, and therefore without disclosing the RSA private key d.

For each w in [0; 2b−1], the value edj(i){circumflex over ( )}w, resulting from the encryption with said FHE algorithm of the value of each key share component dj(i)to the power w dj(i){circumflex over ( )}wby using the FHE secret key psof said set Sscomprising the index couple (i,j) may be computed and stored by the server, and then transmitted to the client device to compute said intermediate values.

Or for each w in [0; 2b−1],the value Πv=0,v≠w2b−1(edj(i)−v)/(w−v) resulting from the encryption with said FHE algorithm of the value Πv=0,v≠w2d−1(dj(i)−v)/(w−v) by using the FHE secret key psof said set Sscomprising the index couple (i,j), may be computed and stored by the server, and then transmitted to the client device to compute said intermediate values.

Such a precomputation enables to save computation resources on the client device side, and therefore accelerates the generation of an RSA signature by the client device.

The order in which intermediate values YSare computed for every sets SSin {S1, . . . , Su} may be random.

It enables the client device to use a different order at each signature generation or message decryption, which makes it more difficult for an attacker to learn information from attacks on multiple signature generation or decryption occurrences and to retrieve the key share components of the RSA private key.

The generation of the RSA signature may comprise:for each intermediate value YScomputed for each set SSin {S1, . . . , Su}, the decryption of said computed intermediate value YSby using the FHE secret key psof the set Ss,and the multiplication of said decrypted intermediate values all together.

It enables the client device to easily combine intermediate values.

The generation of the RSA signature may comprise a combination of a first intermediate value YSfor a first set SSand a second intermediate value YTfor a second set ST, with SSand STin {S1, . . . , Su}, said combination comprising successively:

a. a prior masking of the first intermediate value YSwith a mask being FHE-encrypted with the FHE secret key psof the first set SS,

b. a FHE-decryption, with the FHE secret key psof the first set SS, of said masked first intermediate value,

c. a simultaneous unmasking and FHE-encryption, with the FHE secret key pTof the second set ST, of the decrypted masked first intermediate value,

d. a multiplication of the result of step c. with the second intermediate value YT.

Such a combination process enables to combine intermediate values while always keeping them under a FHE-encrypted or masked form, despite them being FHE encrypted with different FHE private keys pS. Therefore it increases the security of the method against any attack aiming at retrieving the RSA key share components. It also enable to combine intermediate values.

The generation of the RSA signature may comprise:a combination of a first intermediate value YSFHE-encrypted with a first FHE secret key pSassociated with a first set SS, with a second intermediate value YTFHE-encrypted with a second FHE secret key pTassociated with a second set ST, wherein SSand STare the union of one or more sets in {S1, . . . , Su}, wherein a random value kShas been FHE-encrypted with the first FHE secret key psto generate a FHE-encrypted mask eksfor the first set SS, and wherein the inverse or opposite invkSof the random value kShas been FHE encrypted with the second FHE secret key pTof the second set STto generate a FHE-encrypted inverse mask einvksfor the first set SS, said combination comprising if the size of the first set SSis below a predetermined value, performing a key switching between said first set SSand said second set STcomprising:masking the first intermediate value YSwith said generated mask: zS=YS*ekSor zS=YS+ekS;FHE-decrypting said masked first intermediate value zSwith the first FHE secret key psto obtain a decrypted masked first intermediate value mS;simultaneously unmasking and FHE-encrypting with the second FHE secret key pTthe decrypted masked first intermediate value mSby multiplying or summing up said decrypted masked first intermediate value mSwith said FHE-encrypted inverse mask einvkSfor the first set SS, to obtain a third intermediate value wS=mS*einvkSor wS=mS+einvkS;multiplying the second intermediate value YTwith the third intermediate value wSfor obtaining a fourth intermediate value YS′for the set SS′union of sets SSand ST: YS′=YT*wS;

if the size of the set SS′union of said first set SSand said second set STis superior to said predetermined value, FHE decrypting said fourth intermediate value YS′with the second FHE secret key pTof the second set ST;

else performing the previous steps using the fourth intermediate value YS′as first intermediate value for the union set SS′as first set with the second FHE secret key pTas first FHE secret key, and using a fifth intermediate value YVas second intermediate value for a third set SVas second set, wherein SVis the union of one or more sets in {S1, . . . , SU} not already included in the union set SS′.

It enables combining altogether multiple intermediate values until getting a combination result that can be FHE-decrypted with little enough risk that an attacker could retrieve key share components, i.e. part of the RSA private key, by attacking said combination result under FHE-decrypted form.

When said FHE secret keys of said sets are all identical, the method of secure generation of a RSA signature of a message m by a client device with the secure RSA key generated according to the first aspect, may comprise the steps of:receiving from the server the generated encrypted key share components edj(i)with j in [1, J] and i in [0, n/b−1];generating a predetermined integer number v of disjoint sets {S′1, . . . , S′2. . . , S′S, S′S+1, . . . S′v} such that: U{S's}={(i,j) such that i in [0, n/b−1], j in [1, J]} and each said set S'samong {S′1, . . . S′v} being associated with the Fully Homomorphic Encryption (FHE) secret key psused by the server to encrypt said key share components.computing an intermediate value YSfor each set S′Sin {S′1, . . . , S′v} from said encrypted key share components edj(i)whose index couple (i,j) is comprised in S'Sand from said message m, such that said computed intermediate value is a part of the RSA signature of said message m, under FHE-encrypted form;generating the RSA signature of said message m by combining said computed intermediate values for all sets.

Such a RSA signature generation method enables the client device to define its own sets to be used for computing intermediate values, rather than using the sets defined by the server. It enables the client device to redefine new sets at each generation of a new RSA signature, therefore increasing the security level of the method.

The generation of said disjoint sets {S′1, . . . , S′v} may be performed depending on said message.

It enables the client device to easily define new sets each time an RSA signature is generated for a new message.

According to a fourth aspect, this invention therefore relates also 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 methods according to the first, second or third aspect when said product is run on the computer.

According to a fifth aspect, this invention therefore relates also to a server comprising a processor configured to perform the steps of the method according to the first aspect, a memory configured to store said key share components of said secure RSA key and an interface to send said key share components of said secure RSA key.

According to a sixth aspect, this invention therefore relates also to a client device comprising a memory and a processor configured to perform the computing and generating steps of the method according to the second aspect, and an interface to receive said key share components of said secure RSA key.

To the accomplishment of the foregoing and related ends, one or more embodiments comprise the features hereinafter fully described and particularly pointed out in the claims.

