WO2003013053A1

WO2003013053A1 - Method for determining the size of a random variable for an electronic signature schema

Info

Publication number: WO2003013053A1
Application number: PCT/FR2002/002453
Authority: WO
Inventors: Jean-Sébastien CORON
Original assignee: Gemplus
Priority date: 2001-08-02
Filing date: 2002-07-11
Publication date: 2003-02-13
Also published as: FR2828353B1; FR2828353A1

Abstract

The invention concerns a method for determining the size of a random variable used to generate an electronic signature in public key cryptosystems, said size being both minimal and enabling to guarantee a level of security equivalent to base cryptographic systems.

Description

METHOD FOR DETERMINING THE SIZE OF A FTA FOR AN ELECTRONIC SIGNATURE SCHEME

The present invention relates to a method for determining the size of a hazard used to generate an electronic signature in public key cryptography systems.

The concept of public key cryptography was invented by Whitfield DIFFIE and Martin HELLMAN in 1976. The principle of public key cryptography consists in using a pair of keys, a public encryption key and a private decryption key. It must be computationally infeasible to find the private decryption key from the public encryption key.

An electronic signature of a message is a number depending both on the private key known only to the person signing the message, as well as on the content of the message to be signed. An electronic signature must be verifiable: it must be possible for a third party to verify the validity of the signature, without knowledge of the private key of the person signing the message being required; signature verification is performed using the corresponding public key.

There are many electronic signature schemes. The best known are: - RSA signature scheme: this is the most widely used electronic signature scheme. Its security is based on the difficulty of factoring large numbers;

- Rabin signature scheme: its security is also based on the difficulty of factoring large numbers; - El-Gamal type signature scheme: its security is based on the difficulty of the problem of the discrete logarithm; the problem of the discrete logarithm consists in determining, if it exists, an integer x such that y = g ^x with y and g two elements of a set E having a group structure;

- Schnorr signature scheme: this is a variant of the El-Gamal type signature scheme.

Technically, two types of electronic signature scheme are distinguished:

Electronic signature schemes requiring the original message for signature verification: the message and the signature are therefore transmitted separately;

- Electronic signature schemes with message reconstruction: the original message is obtained from the signature itself; since the original message is not necessary to verify the signature, the total size of the signature is shorter.

The first realization of a public key scheme was developed in 1977 by Rivest, Shamir and Adleman, who invented the RSA encryption system. The security of RSA rests on the difficulty of factorizing a large number which is the product of two prime numbers. The RSA system is the most widely used public key encryption system. It can be used as an encryption method or as a encryption method. signature. The RSA system is used in smart cards, for certain applications of these. Possible applications of RSA on a smart card are access to databases, banking applications, remote payment applications such as pay TV, gas distribution or payment of tolls. highway.

The principle of an electronic signature scheme based on the RSA system can generally be defined in three parts:

- The first part is the generation of the RSA key. Each user creates an RSA public key and a corresponding private key, according to the following 5-step process:

1) Generate two distinct prime numbers p and q of the same size k / 2 bits, k being an integer parameter;

2) Calculate the number n such that: n = p * q and φ = (p-

1) * (q-1);

3) Randomly select an integer e,

4) Calculate the unique integer d, l <d <φ, such that e * d = l mod φ;

5) The public key is (n, e); the private key is d.

The integers e and d are respectively called encryption exponents and decryption exponents. The integer n is called the module. The second part is the generation of the signature.

The method consists in taking as input the message M to be signed, in applying to it an encoding using a function μ to obtain the character string μ (M). The signature S is then given by:

S = μ (M) d mod N;

Thus, only the person having the private key corresponding to the exponent d can generate the signature;

The third part is the verification of the signature: the method consists in taking as input the message M to sign and the signature S to verify, in applying an encoding to the message M using a function μ to obtain the character string μ (M ), to calculate

Y = S e mod N

and to verify that the result obtained is equal to μ (M). In this case, the signature S of the message M is valid, and otherwise it is false.

There are many encoding methods using different μ functions. An example of an encoding process is the process described in the standard "ISO / IEC 9796-2, Information Technology - Security techniques - Digital signature scheme giving message recovery, Part 2: Mechanisms using a hash-funct ion, 1997". Another example of an encoding process is the encoding process described in the standard "RSA Laboboratories, PKCS # 1: RSA cryptography specifications, version 2.0, September 1998". These two encoding methods allow messages of arbitrarily long size to be signed.

The disadvantage of these previously described encoding methods is that they do not necessarily offer a level of security comparable to the RSA system.

On the contrary, there are encoding methods which offer a level of security equivalent to the RSA scheme. The best known of these is the PSS signature scheme, an acronym for "Probabil istic Signature Scheme", described in 1996 by Bellare and Rogaway in the publication "The exact security of digital signatures - How to sign with RSA and Rabin And published at the 1996 Eurocrypt conference. The PSS signature scheme is included in many standards, including

- IEEE P1363, Standard Specifications For Public Key Cryptography: Additional Techniques; - PKCS # 1 v2.1, RSA Cryptography Standard.

The PSS signature scheme makes it possible to sign a message M of arbitrary length. There is also a variant of the PSS scheme called PSS-R in which we find the message when verifying the signature. It is no longer necessary to transmit the message with the signature. The PSS signature process works as follows: to sign a message M, we concatenate a random r of size k ₀ bits, k ₀ being a previously determined parameter. We then apply to M | | r a hash function H which returns as output a string of size ki bits, ki being a parameter, to obtain the result w. A hash function G is defined taking as input a message of size ki bits and returning as output a message of size k-kχ-1 bits. We define the function G which returns the first k ₀ bits of the function G, as well as the function G ₂ which returns the remaining k-kι-k ₀ -l bits. The encoding function μ (M) is then given by:

μ (M) = θ | | | | Gι (w) xor r | | G ₂ (w).

To verify the signature S of a message M, we first calculate

Y = S ^A e mod N

And we then write Y in the form Y = 0 | | w | | r * | | g, where w is a string of size k _x bits, r * is a string of size k _o bits, and g is a string comprising the remaining k-ko-kχ-1 bits. We calculate r = G _x (w) xor r * and we verify that w = H (M | | r) and g = G ₂ (w).

The PSS-R signature scheme, an acronym for Probabilist ic Signature Scheme - Recovery, is similar to the PSS scheme, the difference being that it allows to find the message at the time of the verification of the signature. The size of the message which is found during the verification of the signature is k-1-ko-kχ. We deduce that the smaller the size k ₀ of the hazard, the more we can find a large message when verifying the signature. This therefore reduces the total size of the data exchanged: there is no need to transmit the message because it will be found when verifying the signature. The size of the data exchanged is crucial in many applications with few memories, such as a smart card or pocket computers.

The invention consists of a method for determining the optimal size of the hazard used during the generation of the signature. The size is optimal in the sense that it is the minimum size to guarantee a level of security equivalent to RSA. The use of a smaller size hazard does not provide a level of security equivalent to that of RSA. The method of the invention is particularly intended to apply to the PSS signature scheme, but it can extend to other signature schemes with characteristics similar to PSS, for example to the PFDH signature scheme, English acronym for " Probabilistic Full Domain Hash ”. The PFDH scheme works as follows. To generate a signature of a message M, a random r of size k ₀ bits is concatenated with the message M, k ₀ being a previously determined parameter. We apply then to M | | r a hash function H which returns as output a chain of size k bits denoted μ (M) = H (M | | r).

In a first variant, the method consists in including a counter which limits the total number of signatures which will be generated for a given public key. Initially, the counter is set to zero. With each new signature, the counter is incremented. When the value of the counter has exceeded a maximum value noted qsig, one can no longer generate a signature. The optimal value of the size k ₀ of the hazard is then determined by determining k0 = log (qsig) / log (2), where log denotes the logarithm function. The advantage of this first variant is that the size k ₀ of the hazard is optimal: a size k _o less than this value would generate a level of security lower than the security level of the RSA system, while a size k ₀ greater to this value would decrease the size of the message that can be found during the verification of the signature.

In a second variant, the method consists in using the time tgen necessary for the generation of a signature, as well as the maximum lifetime tvie of the system for generating signatures according to a given public key. For example, a bank card using this so-called signature generation system according to a given public key which has to be renewed every two years has a lifetime tvie = 2 years. We then obtain the maximum number qsig of signatures that can be generated by calculating: QSIG = tvie / TGen.

Then we obtain according to the same process described in the first variant the optimal size k _o of the hazard by calculating: k0 = log (qsig) / log (2)

The advantage of this second variant is that a level of security equivalent to the RSA system is obtained, with a maximum retrieved message size, and without using a counter.

In a third variant, a counter q is used for the number of signatures generated, but the limit value of this counter is not known a priori. Initially, the counter q is set to zero, and the value of the parameter k ₀ is set to zero. With each new generation of a signature, the counter q is incremented. A new value of k _{0 is} then determined equal to the size measured in number of bits of q. For example, if q = 7, k0 = 3, and if q = 8, k0 = 4. The advantage of the method of the third variant is that, throughout the process, an optimal value for the size k ₀ of the hazard is kept: a safety level equivalent to the RSA system is maintained while allowing a size to be found. message maximum.

The signature schemes used for the present invention are preferably RSA, Rabin, PSS, PSS-R and PFHD as described previously in the description. The three variants of the process described above, but not exhaustive, can apply more generally to any signature system in which the value of the hazard is found at the time of signature verification. The application of any one of the three variants of the process described above makes it possible to obtain an optimal size of the generated hazard. The three variants are particularly intended for use in an electronic portable object of the smart card type.

Claims

1) Method for determining the size of a hazard used in the generation of an electronic signature, said size being both minimum and making it possible to guarantee an equivalent level of security with the basic cryptographic system used with public key, characterized in that said method requires knowledge of the total number qsig of signatures which are generated for a given public key, the size k ₀ of the hazard being determined by the formulation: k ₀ = log (qsig) / log (2), log designating the logarithm function.

2) Method according to claim 1 characterized in that it uses a counter of the number of signatures generated, said counter being initially set to zero, said counter being incremented with each new generation of signature, the total number of signatures can be generated being limited by a parameter qsig fixed in advance, the size k ₀ of the hazard generated being determined by the formulation: k ₀ = log (qsig) / log (2), log designating the logarithm function.

3) Method according to claim 1 characterized in that a maximum lifetime of a signature generation system for a given public key and a generation time tgen of a signature are known, the maximum number of signatures that can be generated is determined by the formulation: qsig = tvie / tgen, the size k ₀ of the hazard generated is determined by k ₀ = log (qsig) / log ( 2), log designating the logarithm function.

4) Method for determining the size of a hazard used in the generation of an electronic signature, said size being both minimum and making it possible to guarantee an equivalent level of security with the basic cryptographic system used, characterized in that it uses a counter q for the number of signatures, said counter q being initially set at zero, said counter q being incremented at each generation of a signature, the size kb of the hazard being initially set at 0, said size kb of the hazard then being given by the size measured in number of bits of the counter q.

5) Method according to any one of claims 1 to 4, characterized in that said basic cryptographic system is RSA.

6) Method according to any one of claims 1 to 4, characterized in that said basic cryptographic system is Rabin. 7) Method according to any one of claims 1 to 4, characterized in that the signature scheme used is PSS.

8) Method according to any one of claims 1 to 4, characterized in that the signature scheme used is PSS-R.

9) Method according to any one of claims there 4, characterized in that the signature scheme used is PFDH.

10) Method according to any one of claims there 9, characterized in that it is implemented in a portable electronic object.

11) Method according to the preceding claim 9, characterized in that said electronic device is a smart card.

12) Portable electronic device implementing the method according to any one of claims 1 to 11.