专利摘要:
The present invention relates to a method of electronically signing a document with a secret key (x) predetermined, the method being characterized in that it comprises the implementation of steps of: (a) Drawing a couple a first internal state (si1) and a bleached implementation (WBi) of a modular arithmetic operation among a T_P0010_L0006set of pairs ({(si1, WBi)} i? | [0, n-1]) each predetermined for a nonce (ki), said first internal state (si1) being a function of the nonce (ki) and said modular arithmetic operation being a function of the first internal state (si1), the nonce (ki) and the secret key (x); (b) Determining a second internal state (si2) by applying to a condensate of the document obtained by a given hash function, from said executed bleached implementation (WBi); (c) generating an electronic signature of the document from the first internal state (si1) of the pulled pair and the second internal state (si2) determined, and removing the torque drawn from said set of pairs ({si1, WBi)} i ? [0, n-1]).
公开号:FR3063857A1
申请号:FR1751894
申请日:2017-03-08
公开日:2018-09-14
发明作者:Herve Chabanne;Emmanuel Prouff
申请人:Safran Identity and Security SAS;
IPC主号:
专利说明:

(54) PREDETERMINED ELECTRONIC SIGNATURE METHOD.
The present invention relates to a method for electronically signing a document with a predetermined secret key (x), the method being characterized in that it comprises the implementation of steps of:
(a) Drawing of a couple of a first internal state (sj) and of a bleached implementation (WB,) of a modular arithmetic operation among a
T_P0010_L0006 set of pairs ({(s'i, WBi)} ^ n _ η) each predetermined for a nonce (k,), said first internal state (sj) being a function of nonce (k,) and said modular arithmetic operation being a function of the first internal state (s'i), the nonce (k,) and the secret key (x);
(b) Determination of a second internal state (s ′ 2 ) by application to a condensate of the document obtained by a given hash function, of said bleached implementation (WBi) drawn;
(c) generation of an electronic signature of the document from the first internal state (s'i) of the couple drawn and the second internal state (s ' 2 ) determined, and deletion of the couple drawn from said set of couples ({s' i, WBj)} j ^ 0 n _i]).
A DOCUMENT WITH A SECRET KEY

i
METHOD FOR ELECTRONIC SIGNING OF A DOCUMENT WITH A PREDETERMINED SECRET KEY
GENERAL TECHNICAL AREA
The present invention relates to the field of cryptography, and in particular to a “white box” type signature process.
STATE OF THE ART
A function is considered to be a "black box" when it cannot access its internal functioning, i.e. it can know its inputs and outputs but not its secret parameters or its intermediate states.
Cryptographic algorithms (for example for encryption or signature) are thus classically assumed to be black boxes when we assess their reliability (resistance to attacks).
The black box hypothesis places a strong constraint on the storage and manipulation of these parameters. However, tools have recently been published to allow the automation of attacks on hardware implementation, so-called auxiliary channel or fault attacks.
Today, for many use cases including mobile payment, it is necessary to deploy cryptographic algorithms by making as few assumptions as possible about the security of the target hardware. The secure storage and handling of secret parameters must then be ensured at the application level.
White box cryptography aims to respond to this challenge by proposing implementations of cryptographic algorithms which are supposed to make the extraction of secrets impossible, even in the event of an attack allowing the attacker full access to the software implementation of the 'algorithm. More precisely, a function is considered to be a “white box” when its mechanisms are visible and allow its operation to be understood. In other words, we directly assume that the attacker has access to everything he wants (the binary is completely visible and modifiable by the attacker and he has full control of the platform. execution). Therefore, the implementation itself is the only line of defense. We then speak of "laundered implementation" of an elementary calculation of the algorithm when we manage to represent this calculation in a secure form avoiding having the keys used in plain text, for example by representing the calculation by a stored table in memory.
For example, in application US2016 / 328543, a method was proposed to hide the inputs and outputs of a modular exponentiation function, which makes it possible to improve the security of cryptographic algorithms such as RSA (“Rivest, Shamir, Adleman ”).
However, it has been shown that this method is not sufficient to ensure satisfactory protection of the DSA ("Digital Signature Algorithm").
The calculation of a DSA signature presupposes that a public key (p, q, g, y) and a private key x have been associated with the user. The process for generating these keys consists of the following different steps:
• Choose a prime number p of length L such that 512 <L <1024, and L is divisible by 64 • Choose a prime number q of 160 bits, such that p - 1 = qc, with c an integer • Choose h , with 1 <h <p - 1 so as to construct g such that g = h c mod p> 1 • Randomly generate an x, with 0 <x <q • Calculate y = g x mod p
The DSA signature of a message m begins with a hash calculation H (m) (using a standard hash function like SHA256) and then continues with the calculation of two values s x and s 2 such that :
s i = Çd k mod p) mod q • s 2 = (H (m) + mod q where k is a datum called nonce (ie an arbitrary number, that is to say a hazard, for single use, "number used once"), which must be drawn randomly for each new signature.
The signature is (si, s 2 ) ·
As explained, one can obtain whitewashed implementations of each of the functions for calculating the internal states s x and s 2 by hiding the modular exponentiation.
However, the same application of the bleached implementation of s 2 to two different data z and z '(for example the condensates of two different messages) while forcing the reuse of the same nonce k (which is normally impossible except in a white box attack where we would have access to the material) allows by calculation of s 2 (z) -s 2 (z ') to go back to x. This is called a "restart attack".
It would therefore be desirable to have a new "white box" signature solution using the standard mechanism such as DSA which is completely resistant to all known attacks.
PRESENTATION OF THE INVENTION
According to a first aspect, the present invention relates to a method of electronic signature of a document with a predetermined secret key, the method being characterized in that it comprises the implementation by data processing means of a piece of equipment 'stages of:
(a) Drawing of a couple from a first internal state and from a laundered implementation of a modular arithmetic operation from among a set of predetermined couples each for a nonce, said set of couples being stored on storage means equipment data, said first internal state being a function of the nonce and said modular arithmetic operation being a function of the first internal state, of the nonce and the secret key;
(b) Determination of a second internal state by application to a condensate of the document obtained by a given hash function, of said drawn bleached implementation;
(c) generation of an electronic signature of the document from the first internal state of the couple drawn and from the second determined internal state, and deletion of the couple drawn from said set of couples.
According to other advantageous and non-limiting characteristics:
• said modular arithmetic operation is zi—> (z + s | x) / cf 1 mod q, where s] is the first internal state, the nonce, x the secret key and q a constant;
s i = (jj ki m ° dp) m ° dq, where g and p are constants;
• the signature is the pair (s [, S2) of the first and second internal states;
• the method comprises a prior step (aO) of generating said set of pairs by data processing means of a server, and its transmission to the equipment;
• step (aO) includes the generation of a plurality of nuncios, then the generation of the couple for each nuncio;
• step (aO) includes the prior generation of the constants p, q, g in accordance with the DSA algorithm;
• step (aO) also includes the prior generation of the secret key and an associated public key as a function of the constants p, q, g;
• said laundered implementations use a Modular Representation System, RNS, to perform said modular arithmetic operation;
• the method comprises a subsequent step (d) of association by the data processing means of the equipment of the electronic signature generated with the document so as to form the signed document
According to a second and a third aspect, the invention provides a computer program product comprising code instructions for the execution of a method according to the first aspect of electronic signature of a document with a predetermined secret key; and storage means readable by computer equipment on which a computer program product comprises code instructions for the execution of a method according to the first aspect of electronic signature of a document with a predetermined secret key.
PRESENTATION OF THE FIGURES
Other characteristics and advantages of the present invention will appear on reading the following description of a preferred embodiment. This description will be given with reference to the appended drawings in which:
FIG. 1 is a diagram of an architecture for implementing the method according to the invention.
DETAILED DESCRIPTION
Architecture
With reference to FIG. 1, there is proposed a method of “white box” signing of a document implemented within equipment 10a such as a mobile terminal (smartphone, touch pad, etc.), ie equipment not particularly having secure hardware and which can be the object of attacks on hardware implementation, and for which the white box approach takes all its interest.
The equipment 10a comprises data processing means 11a (a processor) and data storage means 12a (a memory, for example flash).
The equipment 10a is for example connected to a server 10b for example via the internet network 20. It may be required to receive from this server 10b (for example that of a supplier of security solutions) cryptographic objects (which will describe later) containing secrets which will be stored in the memory 12a and used for the implementation of the present method
The equipment 10a can itself be connected to other third party servers 10c to which it can transmit the signed document once it has generated the electronic signature.
Signing process
The present method is indeed a “generation of electronic document signature” process, and not a “document signature”. This means that it only allows to obtain the electronic signature of the document and not yet the "signed document", i.e. the association of the original document and the signature, generally in any container.
By “electronic signature” of a document is meant the conventional definition of this term, namely a cryptographic primitive making it possible to identify the signatory and guaranteeing that the document has not been altered since the moment when the signature was produced and is indeed the original document (in the rest of this description, we will designate as "original" the document from which the condensate actually came). This cryptographic object generally consists of an encrypted document condensate thanks to an asymmetric encryption function: the signatory uses a private key, and everyone can verify the signature using a public key (by comparing the condensate contained in the signature and recalculated condensate).
It will be understood that the present method is a new implementation of known algorithms using modular arithmetic operations (ie operations comprising modulo calculations, in particular modular exponentiations), in particular DSA which is a current standard and from which we will take the example in the rest of the description. Specifically, it does not offer a new signing strategy, but only a new way of manipulating the data within the algorithm that is resistant to all "white box" hardware attacks.
The document is associated with a condensate obtained by a given hash function.
As explained, a hash function takes as input a message of arbitrary size (the original document) and produces a condensate of fixed size associated with this message. Here, said given hash function is advantageously a so-called cryptographic function, that is to say with additional properties: the condensate is statistically well distributed in the set of arrival values, it is impossible in reasonable time to find two messages which have the same condensate (resistance to collisions) and one cannot from the condensate find a message which made it possible to obtain this value (resistance to the calculation of pre-image).
We will take the example of the functions of the SHA family (“Secure Hash Algorithm”), standardized by the NIST (“National Institute of Standards and Technology”), in particular the SHA-1 or SHA-2 subfamilies (notably SHA -256).
Principle
The present invention proposes, for the same pair of public / private keys, to have several values of a first internal state precalculated if each for a nonce k if then a bleached implementation WB t of a modular arithmetic operation used by l signature algorithm for each of the nonces k if said modular arithmetic operation is in fact a function of the first internal state si, of the nonce k t and of the secret key x. It is recalled that by whitewashed implementation, or “white box implementation”, of an operation, we mean a representation of the operation which does not allow to go back to the internal states or to the parameters when the operation is executed (by application of the implementation laundered with input data).
Thus, a set of pairs of the first internal state si and of the bleached implementation WB t of the modular arithmetic operation are predefined and stored on them stored on the data storage means 12a of the equipment 10a.
In other words, with a fixed public / private key, each couple (si, WBi) is entirely determined by the nonce k t : drawing a nonce is equivalent to drawing a couple. The nonce ki is therefore not an input data of the WB t blank implementation but rather an "encapsulated" parameter to which an attacker cannot go back.
Preferably, said set of pairs is generated by the data processing means 11b of the server 1b and transmitted for storage to the equipment 10a in a prior step (aO).
This generation can include the generation of the plurality of nonces {kj} ie | [o, ni], P U1S * a generation of the couple (s (, lVBj) for each nonce kj so as to define the set [(if, VZS;)} πια i 'nl]
The expected properties of application laundering mean that observation of the execution of the laundered implementation WB t should not make it possible to find the values of the secret key x and of the nonce kj buried in the calculation. So just authorize the use of each WB t only once to prevent going back to kj and thus avoid restart attacks. The proposed signature process therefore makes it possible to resist an attacker who would observe the intermediate states (for example using a malicious application running on the mobile).
The bleached WB t implementations ( and therefore the pairs of a first state and a bleached implementation) are thus deleted after use to avoid any possible attack.
Preferred embodiment
In the example where the signature algorithm conforms to DSA, then sj can be equal to (g ki modp) mod q, where g, p and q are constants (in particular prime numbers for p and q).
Similarly, said modular arithmetic operation represented by the bleached implementation WB t can be z (z + s ^ kf 1 mod q. We can easily verify that this calculation corresponds to that of s l 2 associated with the sj generated previously, for a z-value of the message.
The values p, q, g are preferably predetermined in accordance with the DSA algorithm, in particular by the data processing means 11b of the server 10b during the prior step (aO).
Recall that in DSA, (p, q, g, y) forms a public key generated with a private key x as follows:
• Choose a prime number p of length L such that 512 <L <1024, and L is divisible by 64 • Choose a prime number q of 160 bits, such that p - l = qc, with c an integer • Choose h , with l <h <p-l so that g = h c mod p> 1 • Generate a random x, with 0 <x <q • Calculate y = g x mod p
Those skilled in the art will however understand that the present method is not limited to DSA and provides satisfaction for any signature algorithm comprising a modular arithmetic operation based on a first internal state, a nonce and a key secret.
Implementation
The present method is implemented by the data processing means 11a of the equipment 10a and begins with a step (a) of drawing a pair of a first internal state sj and a bleached implementation WB t d 'a modular arithmetic operation among said set of couples {(spV / Si)}. e | [one predetermined stored on data storage means 12a of the equipment 10a.
This drawing can be random or sequential, it comes down to drawing a nonce k t since each pair is entirely determined by the nonce k t from which it was generated.
In a step (b), a second internal state s l 2 is determined by application to a condensate H (m) of the document m (obtained by a given hash function, such as SHA256), of said bleached implementation WB t drawn. In other words, we take z = H (m).
From there, in a third step (c) can be generated the electronic signature of the document from the first internal state sj of the pulled couple and the second internal state s l 2 determined in step (b). In the preferred example of DSA, the signature is simply (s [, S2).
ίο
Step (c) also includes, as explained, the removal of the torque drawn from said set of couples (before or after the generation of the signature) so as to prevent restart attacks.
Additionally, the method may include a subsequent step (d) of association by the data processing means 11a of the equipment 10a from the electronic signature to the document so as to form the signed document. The equipment 10a can then legally avail itself of this electronic signature from other entities (servers 10c).
Laundered implementation
The realization of milled implementations of modular arithmetic operations is known to the skilled person.
However, the application of the laundered implementation to execute the represented operation can be long, in particular if the said modular arithmetic operation includes modular exponentiations.
As such, preferably said laundered WB t implementations use a Residue Number System (RNS) to perform said modular arithmetic operation.
More precisely, the RNS implementation principle makes it possible to decompose modulo calculations of a given value into modulus calculations of small prime numbers whose product is greater than said given value (thanks to the Chinese theorem).
A person skilled in the art can proceed, for example, in accordance with request US2016 / 239267.
Computer program product
According to a second and a third aspect, the invention relates to a computer program product comprising code instructions for the execution (in particular on the data processing means 11a of the equipment 10a) of a method according to the first aspect of the invention of electronic signature of a document with a secret key x predetermined, as well as storage means readable by computer equipment (a memory 12a of the equipment 10a) on which this product is found program computer.
权利要求:
Claims (12)
[1" id="c-fr-0001]
1. Method for electronic signature of a document with a predetermined secret key (%), the method being characterized in that it comprises the implementation by data processing means (11a) of equipment (10a) steps from:
(a) Drawing of a couple of a first internal state (s [) and a bleached implementation (WB ^) of a modular arithmetic operation among a set of couples ^^ i)} ieŒo n _ 1 j) each predetermined for a nonce (/ cj, said set of pairs being stored on data storage means (12a) of the equipment (10a), said first internal state (s [) being a function of the nonce (/ cj and said modular arithmetic operation being a function of the first internal state (s)), of the nonce (/ cj and of the secret key (%);
(b) Determination of a second internal state (s l 2) by application to a condensate of the document obtained by a given hash function, of said bleached implementation (WBi) drawn;
(c) generation of an electronic signature of the document from the first internal state (s [) of the drawn couple and the second internal state (s ^) determined, and deletion of the couple drawn from said set of couples
[2" id="c-fr-0002]
2. Method according to claim 1, in which said modular arithmetic operation is zi—> (z + s (x) / cf 1 mod q, where s] is the first internal state, Zq the nonce, x the secret key and q a constant.
[3" id="c-fr-0003]
3. The method of claim 2, wherein s ! = (dd ki m ° dp) m ° dq, where g and p are constants.
[4" id="c-fr-0004]
4. Method according to one of claims 1 to 3, wherein the signature is the pair (s], S2) of the first and second internal states.
[5" id="c-fr-0005]
5. Method according to one of claims 1 to 4, comprising a prior step (aO) of generating said set of couples ({( S Î> n ) by data processing means (11b) of a server (1b ), and its transmission to the equipment (10a).
[6" id="c-fr-0006]
6. Method according to claim 5, in which step (aO) comprises the generation of a plurality of nuncios ({kjheno.n-ij), then the generation of the couple (sj, Vl + Bj) for each nuncio ( K J).
[7" id="c-fr-0007]
7. A method according to claims 3 and 6 in combination, wherein step (aO) comprises the prior generation of the constants p, q, g according to the DSA algorithm.
[8" id="c-fr-0008]
8. The method of claim 7, wherein step (aO) also comprises the prior generation of the secret key (%) and an associated public key according to the constants p, q, g.
[9" id="c-fr-0009]
9. Method according to one of claims 1 to 8, wherein said laundered implementations (Vl + Bj) use a Modular Representation System, RNS, to perform said modular arithmetic operation.
[10" id="c-fr-0010]
10. Method according to one of claims 1 to 9, comprising a subsequent step (d) of association by the data processing means (11a) of the equipment (10a) of the electronic signature generated in the document so as to form the signed document
[11" id="c-fr-0011]
11. computer program product comprising code instructions for the execution of a method according to one of claims 1 to 10 for electronic signature of a document with a predetermined secret key (%), when said program is executed by a computer.
[12" id="c-fr-0012]
12. Storage means readable by computer equipment on which a computer program product comprises code instructions for the execution of a method according to one of claims 1 to 10 for electronic signature of a document with a predetermined secret key (%).
3063
类似技术:
公开号 | 公开日 | 专利标题
EP3373509B1|2020-12-23|Method for electronically signing a document with a predetermined secret key
EP2256987B1|2014-12-03|Protection of a generation of prime numbers for the RSA algorithm
CH634161A5|1983-01-14|APPARATUS FOR DECIPHERING A NUMBERED MESSAGE AND ITS USE IN A TRANSMISSION INSTALLATION.
EP2296086B1|2011-11-02|Protection of prime number generation against side-channel attacks
EP1151576B1|2007-03-07|Public and private key cryptographic method
EP2707989B1|2015-06-10|Device and method for generating keys with enhanced security for fully homomorphic encryption algorithm
FR3010210A1|2015-03-06|PROTECTION OF CALCULATION AGAINST HIDDEN CHANNEL ATTACKS
FR3059802A1|2018-06-08|METHOD FOR GENERATING AN ELECTRONIC SIGNATURE OF A DOCUMENT ASSOCIATED WITH A CONDENSATE
FR2632469A1|1989-12-08|SECURE DATA COMMUNICATION DEVICE
EP1804161A1|2007-07-04|Detection of a disturbance in a cryptographic calculation
EP3407537A1|2018-11-28|Method for electronically signing a document with a predetermined secret key
EP2315388B1|2015-04-01|Secured method for cryptographic calculation and corresponding electronic component.
EP2983083A1|2016-02-10|Elliptic curve encryption method comprising an error detection
WO2013024230A2|2013-02-21|Device and method for compressing public keys for a fully homomorphic encryption algorithm
TW201629829A|2016-08-16|Exponent splitting for cryptographic operations
EP3346632A1|2018-07-11|Method for encrypting or decrypting an n-tuple of data with an n-tuple of predetermined secret keys
FR3015079A1|2015-06-19|INTEGRITY VERIFICATION OF PAIR OF CRYPTOGRAPHIC KEYS
CN113297608B|2021-11-02|Identity anonymous searchable encryption method, device and equipment based on commercial password
EP3340096B1|2019-08-07|Method for configuring a cryptographic program intended for being run by a terminal
EP3716044A1|2020-09-30|Protection of an iterative calculation
FR3018372A1|2015-09-11|MESSAGE GENERATION FOR CRYPTOGRAPHIC KEY GENERATION TEST
FR3018127A1|2015-09-04|METHOD FOR SECURING ACCESS TO A CANVAS SITE
CN113114627A|2021-07-13|Secure data interaction method and system based on key exchange
TARIK2019|Privacy Preserving Classification of Biomedical Data
FR3038473A1|2017-01-06|METHOD FOR CRYPTOGRAPHIC DATA PROCESSING AND ASSOCIATED COMPUTER PROGRAM
同族专利:
公开号 | 公开日
EP3373509A1|2018-09-12|
EP3373509B1|2020-12-23|
FR3063857B1|2020-02-14|
US20180262343A1|2018-09-13|
US10938576B2|2021-03-02|
引用文献:
公开号 | 申请日 | 公开日 | 申请人 | 专利标题
WO2009136361A1|2008-05-07|2009-11-12|Koninklijke Philips Electronics N.V.|Exponent obfuscation|
EP3059894A1|2015-02-18|2016-08-24|Nxp B.V.|Modular multiplication using look-up tables|US11102012B2|2017-05-24|2021-08-24|Idemia Identity & Security France|Process for digital signing of a document with a predetermined secret key|US6064740A|1997-11-12|2000-05-16|Curiger; Andreas|Method and apparatus for masking modulo exponentiation calculations in an integrated circuit|
CA2327911A1|2000-12-08|2002-06-08|Cloakware Corporation|Obscuring functions in computer software|
US7194618B1|2001-03-05|2007-03-20|Suominen Edwin A|Encryption and authentication systems and methods|
CA2369304A1|2002-01-30|2003-07-30|Cloakware Corporation|A protocol to hide cryptographic private keys|
US8094816B2|2008-10-21|2012-01-10|Apple Inc.|System and method for stream/block cipher with internal random states|
DE102009001718B4|2009-03-20|2010-12-30|Compugroup Holding Ag|Method for providing cryptographic key pairs|
WO2011120125A1|2010-03-31|2011-10-06|Irdeto Canada Corporation|System and method for protecting cryptographic assets from a white-box attack|
US20120308003A1|2011-05-31|2012-12-06|Verisign, Inc.|Authentic barcodes using digital signatures|
US9264234B2|2011-06-03|2016-02-16|Apple Inc.|Secure authentication of identification for computing devices|
WO2013139380A1|2012-03-20|2013-09-26|Irdeto Bv|Updating key information|
US9531540B2|2014-12-23|2016-12-27|Nxp B.V.|Secure token-based signature schemes using look-up tables|
CN108064381B|2015-03-30|2021-06-18|爱迪德技术有限公司|Method for data protection|
US10372886B2|2015-05-05|2019-08-06|Nxp B.V.|Protecting the input/output of modular encoded white-box RSA/ECC|
US9692592B2|2015-06-05|2017-06-27|Apple Inc.|Using state reordering to protect against white box attacks|
US9390154B1|2015-08-28|2016-07-12|Swirlds, Inc.|Methods and apparatus for a distributed database within a network|
WO2017173099A1|2016-03-30|2017-10-05|Ping Identity Corporation|Methods and apparatus for assessing authentication risk and implementing single sign on using a distributed consensus database|
KR101883156B1|2016-08-10|2018-07-30|삼성에스디에스 주식회사|System and method for authentication, user terminal, authentication server and service server for executing the same|US10790991B2|2018-08-30|2020-09-29|Nxp B.V.|Deterministic digital signature method without using a hash function|
WO2021025631A1|2019-08-05|2021-02-11|Securify Bilisim Teknolojileri Ve Guvenligi Egt. Dan. San. Ve Tic. Ltd. Sti.|A method for generating digital signatures|
法律状态:
2018-02-19| PLFP| Fee payment|Year of fee payment: 2 |
2018-09-14| PLSC| Search report ready|Effective date: 20180914 |
2019-02-20| PLFP| Fee payment|Year of fee payment: 3 |
2020-02-20| PLFP| Fee payment|Year of fee payment: 4 |
2021-02-19| PLFP| Fee payment|Year of fee payment: 5 |
优先权:
申请号 | 申请日 | 专利标题
FR1751894|2017-03-08|
FR1751894A|FR3063857B1|2017-03-08|2017-03-08|METHOD FOR ELECTRONIC SIGNING OF A DOCUMENT WITH A PREDETERMINED SECRET KEY|FR1751894A| FR3063857B1|2017-03-08|2017-03-08|METHOD FOR ELECTRONIC SIGNING OF A DOCUMENT WITH A PREDETERMINED SECRET KEY|
EP18160420.8A| EP3373509B1|2017-03-08|2018-03-07|Method for electronically signing a document with a predetermined secret key|
US15/915,019| US10938576B2|2017-03-08|2018-03-07|Method for electronic signing of a document with a predetermined secret key|
[返回顶部]