Authenticating or signature method with reduced computations

Technical area

The subject of the present invention is a method of authentication or signature with a reduced number of calculations.

The invention relates more precisely to the field of so-called public key cryptography. In such methods, the entity to be authenticated has a secret key and an associated public key. The authenticating entity only needs this public key to perform the authentication.

The invention more precisely relates to the field of so-called zero-knowledge or zero-knowledge authentication methods. In this type of method, the authentication proceeds according to a protocol which, in a proven way, and under assumptions recognized as perfectly reasonable by the scientific community, reveals nothing about the secret key of the entity to be authenticated.

More specifically, the invention relates to methods without knowledge based on the problem of factorization (that is to say on the difficulty of breaking down large integers into a product of prime numbers).

The invention finds application in all systems requiring authentication of entities or messages, or signing messages, and more particularly in systems where the number of calculations performed by the authenticated entity is a critical parameter. This is particularly the case of low-cost or standard microcircuit cards, not equipped with an arithmetic coprocessor (often called cryptoprocessor) to accelerate cryptographic calculations.

A typical application of the invention is the electronic wallet, which requires a very high level of security, while excluding the use of a cryptoprocessor, either for cost reasons or for technical reasons (for example use of a contactless interface), or both.

Another possible application is the next-generation calling card, for which the cost constraints are even more severe than for the electronic purse.

State of the art

Many type identification protocols without knowledge are known. For example:<ul id="ul0001" list-style="dash" compact="compact"><li>the FIAT-SHAMIR protocol described in the article by A. FIAT and A. SHAMIR entitled "How to prove yourself: Practical solutions to identification and signature problems", published in Advances in Cryptology: Proceedings of CRYPTO'86, Lecture Notes in Computer Science ", vol. 263, Springer-Verlag, Berlin, 1987, pp. 186-194,</li><li>the GUILLOU-QUISQUATER protocol described in the article by LC GUILLOU and JJ QUISQUATER, entitled "A practical zero-knowledge protocol fitted to security microprocessors minimizing both transmission and memory", published in "Advances in Cryptology: Proceedings of EUROCRYPT'88, Reading Notes in Computer Science ", Vol. 330, Springer-Verlag, Berlin, 1988, pp. 123-128,</li><li>the GIRAULT protocol described in the French patent application FR-A-2,716,058, based on the so-called discrete logarithm problem.</li></ul>

In general, most of the identification (or message authentication) protocols with no knowledge input take place in three exchanges. It will be assumed, in order to simplify the description, that the authenticating entity B already knows all the public parameters characteristic of the entity to authenticate A, namely its identity, its public key, etc.

During the first exchange, A provides B with a value c called "commitment", image by a pseudo-random function h of a parameter x (itself calculated from a number r randomly selected by A), and that, if necessary, of the message to be authenticated or to sign: c = h (x, [M]) where the notation [M] expresses that M is optional. This is the first step. In some protocols, there may be several commitments.

In a second exchange, B sends to A a parameter e chosen at random (the "question"). This is the second step.

During the third exchange, A provides B with a "response" y, consistent with the question e, the commitment c and the secret key v of A (third step).

Finally, B checks the response received. More precisely, B recalculates x from the elements y, e and v by x = φ (y, e, v); then he checks that: c = h (φ (v, e, y), [M]) (fourth step).

In the case where there is no message to authenticate, the use of the pseudo-random function h is optional. We can then take c = x. The verification then consists in verifying that x = φ (y, e, v).

In some protocols, there are one or two additional exchanges between the entities to authenticate and authenticate.

In the case of a message signature, the first two exchanges are deleted because the parameter e is chosen equal to c; A then calculates successively, and only, c, e (= c) and y.

The number u of possible questions is directly related to the security level of the protocol. The latter is defined as the probability p of detection of an imposter (that is to say of a C entity that attempts fraudulently to pass for A), and is characterized by a parameter k. The numbers p and k are connected by equality: p = 1-2^-k. In other words, the impostor has only one chance out of two^k to succeed his imposture. In the present case, it can be shown that, if the protocol is based on a difficult mathematical problem, and if the commitments are of sufficient length, then it suffices that the length of u is equal to k bits. Typically, k is equal to 32 bits, which gives only one chance in four billion to succeed a sham. In applications where the failure of an identification can have very harmful consequences (prosecution for example), this length can be reduced to a few bits.

In factorization-based protocols, calculating x from r, or calculating y from e, or both, implies modulo n operations where n is a hard number to factorize. This number is of universal type, that is to say generated by a trusted third party, stored and used by all the entities attached to it. The universal character of n implies that it is very large (typically 1024 bits), because the discovery of the factorization of n would compromise the secret keys of all users.

In their basic version, none of the protocols mentioned above can be implemented in an application subject to strong constraints (low cost, low complexity) as described in the previous section, because the required calculations could not be performed by a microcircuit card that does not have a cryptoprocessor.

The French patent application FR-A-2,752,122 does indeed describe an optimization of these protocols, but this optimization remains limited to protocols based on the discrete logarithm in a so-called "precalculation" mode which has the disadvantage of involving reloads at regular intervals.

J. BRANDT et al. entitled "Zero-knowledge Authentication Scheme with Secret Key Exchange" published in Advances in Cryptology-Crypto 88 Proceedings, XP 000090662, pages 583-588, describes an authentication scheme without knowledge provision, with secret key exchange between two users, schema in which the entity to be authenticated calculates its own module n = pq and implements an operation of the type m^d (mod n).

The present invention aims to reduce the number of calculations performed by the authenticated entity in the identification protocols (or message authentication or message signing) without knowledge contribution based on factoring, this reduction can reach a factor 2 or 3 in the context of a particular operation of the type v = s^-t (mod n).

It thus makes it possible, and more particularly when paired with the Guillou-Quisquater protocol, the rapid execution of a public-key identification algorithm (or message authentication or message signature algorithm) in a card. standard low-cost microcircuit for applications such as the electronic purse or the next-generation calling card.

Presentation of the invention

Since the module n is a parameter of the individual type (in other words, each user has its own value of n), this choice can be exploited in the following two ways (which may advantageously be combined):<ul id="ul0002" list-style="none" compact="compact"><li>1) first by choosing a size of n less than the usual value (typically less than 1000 and for example between 700 and 800); this is possible because the discovery of the factorization of n compromises only the secret key of the corresponding user and in no way that of the others; this modification alone makes it possible to reduce by approximately 40% the duration of the calculations made modulo n;</li><li>2) if the user has retained the prime factors of n in the memory of his security device, it is possible to implement the so-called Chinese remains technique, to reduce by another 40% the duration of the calculations made modulo n, when the number of prime factors is 2; this reduction can be further amplified by using several prime factors (typically 3 or 4).</li></ul>

In total, it is therefore possible to reduce the modulo n computation times by at least 60%, that is to say by at least a factor of 2.

Specifically, the invention relates to an authentication method implementing a first entity called "to authenticate", having a public key <u>v</u> and a secret key <u>s</u>, these keys being connected by a modulo operation <u>not</u> or <u>not</u> is an integer called module that is specific to the entity to be authenticated, and a second entity called "authenticating", knowing the public key <u>v</u>, these entities comprising means capable of exchanging information of the zero-input type of knowledge and performing cryptographic calculations relating to this information, certain calculations being carried out modulo <u>not</u>, this method being characterized in that the module modulo operation n is of the type v = s^-t (mod n), t being a parameter.

The entities in question may be, for example, microcircuit cards, electronic purses, phonecards, etc.

In an advantageous embodiment, the information exchanges of the null knowledge type and the cryptographic calculations are as follows:<ul id="ul0003" list-style="bullet" compact="compact"><li>the entity to authenticate randomly chooses an integer number (s) <u>r</u> between 1 and n-1 and calculates a parameter (s) <u>x</u> equal (equal) to r^t(mod n), then one (of) number (s) <u>c</u> called engagement (s) which is (are) a function (s) of this (these) parameter (s) and possibly of a message (M), and sends this (these) commitment (s) the authenticating entity;</li><li>the authenticating entity receives the commitment (s) <u>c</u>, randomly chooses a number <u>e</u> called "question" and sends this question to the entity to authenticate;</li><li>the entity to authenticate receives the question <u>e</u>, perform a calculation (s) using this question <u>e</u> and the secret key <u>s</u>, the result of this (these) calculation (s) constituting an answer (s) <u>there</u>, and send this (these) response (s) to the authenticating entity;</li><li>the authenticating entity receives the answer (s) <u>there</u>, performs a calculation using the public key <u>v</u> and the module n, and verified by a modulo operation <u>not</u> that the result of this calculation is well consistent with the commitment (s) received.</li></ul>

The size of the number n, expressed in number of bits, is less than 1000. It can be, for example, between 700 and 800.

The present invention also relates to a method of signing a message by a so-called "signer" entity, this entity having a public key <u>v</u> and a secret key <u>s</u>, these keys being connected by a modulo operation where <u>not</u> is an integer called "module" and <u>t</u> a parameter, a process in which the signatory entity calculates a commitment <u>c</u> particular function of the message to be signed and a number <u>there</u> function of the secret key, issue the numbers <u>there</u> and <u>c</u> which constitute the signature of the message and the message, this method being characterized in that the module <u>not</u> is specific to the signatory.

In an advantageous embodiment, the signatory randomly chooses an integer <u>r</u> between 1 and n-1, calculates a parameter <u>x</u> equal to r^t(mod n), calculates a number <u>c</u> function of the parameter <u>x</u> and the message to sign, calculates a number <u>there</u> using his secret key <u>s</u> and function of numbers <u>r</u> and <u>e</u>, and emit the numbers <u>c</u> and <u>there</u> as a signature.

Detailed description of particular modes of implementation of the invention

In the following description, the invention is supposed to be applied to the GUILLOU-QUISQUATER protocol, but naturally this is only an example and the invention is not limited to this protocol.

It is recalled that in the GUILLOU-QUISQUATER protocol, the universal parameters are the module n, products of prime numbers and comprising at least 1024 bits, and a number <u>t</u> whole.

The public key <u>v</u> and the secret key <u>s</u> are related by the equation: v = s^-t(mod n).

The security level chosen is <u>u</u> (less than or equal to <u>t</u>, and most often, u = t).

The authentication of A by B, which can be called respectively Alice and Bob according to the terminology in use, is as follows:<ul id="ul0004" list-style="none" compact="compact"><li>1. Alice chooses r in the interval [1, n-1], calculates x = r^t(mod n) then c = h (x, [M]) and sends c to Bob.</li><li>2. Bob chooses e in the interval [0, u-1] and sends e to Alice.</li><li>3. Alice calculates y = rs^e(mod n) and send y to Bob.</li><li>4. Bob calculates x = y^tv^e(mod n) and check that c = h (x, [M])</li></ul>

In the case where there is no message to authenticate, the use of the pseudo-random function h is optional: we can take c = x. The verification then consists in verifying that x = y^tv^e(modulo n).

With the modified protocol according to the invention, the only universal parameter is t.

The public key is (n, v), where n is at least 768 bits. The public key v and the secret key s of Alice are connected by the equation: v = s^-t(mod n).

The secret key may also include the prime factors of n in order to benefit from the second aspect of the invention.

The parameter t can be included in the public key (in this case, there is no more universal parameter).

The security level chosen by Alice and Bob is u (less than or equal to t, often u = t).

Bob's authentication of Alice proceeds as described above, but with faster calculations thanks to a smaller module.

Since all Alice's calculations are done modulo n, the gain factor obtained on a single modular multiplication is reflected in all the calculations made by Alice during the execution of the protocol. It would be the same with the protocols of Fiat-Shamir or Girault for example (in the latter case, there is no gain in step 3 since there is no more modular calculations, but of anyway the execution time of this step is negligible compared to the modular exponentiation of the first step).

The invention can also be implemented by the so-called Chinese remains technique, which consists in performing the calculations modulo each of the prime numbers component n. Since these numbers are necessarily much smaller, these calculations are fast. It remains to calculate the result modulo n using a so-called reconstitution operation. This technique is described in the article by JJ QUISQUATER and C. COVERAGE, titled "Fast decipherment algorithm for RSA public-key cryptosystem", published in "Electronic Letters", vol. 18, October 1982, pp. 905-907.

We therefore consider the case where n is the product of two prime factors p and q.

According to Bezout's theorem, there exist two integers a and b such that ap + bq = 1.

To calculate y = x^e(mod n), we start by "reducing" x modulo each of the prime numbers by calculating x_p= x (mod p) and x_q= x (mod q). We also reduce e modulo (p-1) and (q-1) by calculating e_p= emod (p-1) and e_q= Emod (q-1). (In the Guillou-Quisquater protocol, e is always less than p-1 and q-1 and therefore ep = eq = e).

We calculate then_p= x<maths id="math0001" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>p</mtext></mrow></msub></mrow><mrow><mtext>p</mtext></mrow></mfrac></mrow></math><img file="EP1145483B1_D0001.tif" /></maths> (mod p) and y_q= x<maths id="math0002" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><msub><mrow><mtext>e</mtext></mrow><mrow><mtext>q</mtext></mrow></msub></mrow><mrow><mtext>q</mtext></mrow></mfrac></mrow></math><img file="EP1145483B1_D0002.tif" /></maths> (mod q). When p and q are of similar sizes, each of these calculations is about 8 times faster than the calculation y = x^e(mod n) when the size of e is that of n (first case); 4 times faster when it is less than or equal to that of p (second case as for example in the algorithm). The combination of the two calculations is therefore either 4 times faster or twice as fast.

It remains to reconstruct y from there_p and there_q, which is achieved by the operation:<maths id="math0003" num=""><math display="block"><mrow><msub><mrow><mtext>y = y</mtext></mrow><mrow><mtext>p</mtext></mrow></msub><msub><mrow><mtext>+ P (y</mtext></mrow><mrow><mtext>q</mtext></mrow></msub><msub><mrow><mtext>-y</mtext></mrow><mrow><mtext>p</mtext></mrow></msub><mtext>) (mod n)</mtext></mrow></math><img file="EP1145483B1_D0003.tif" /></maths>

In total, the method of Chinese remains allows to accelerate the calculation of a factor between 3 and 4 in the first case, between 1.5 and 2 in the second case. When the number of prime factors (assumed to be similar sizes) is greater than 2 and equal to k, the acceleration factor is close to k² in the first case, close to k in the second case.