Data processing method and related device

[0001] The invention concerns methods of processing data, for example for the implementation of cryptographic algorithms, and devices adapted to execute such methods.

[0002] Data processing methods routinely implemented in electronic entities such as microcircuit cards and microcomputers employ operations that are sometimes complex. In the cryptography field, for example, numerous algorithms use modular arithmetic, especially modular multiplication (which associates with two numbers a and b the remainder of their product modulo a particular number called the modulus n) or the modular exponentiation operation (which associates with two numbers a and e the remainder modulo n of the number a^e).

[0003] The calculation cost of such operations can prove high if the calculations are effected in the conventional manner, for example because of the use of large numbers in cryptographic algorithms to obtain a correct level of security.

[0004] Because of this it has been proposed to optimize the calculations to be effected by defining new operations that lighten the calculations carried out within the algorithms and are in practice effected by dedicated electronic circuits.

[0005] This is the background to the introduction of Montgomery arithmetic, the basic operations of which are as follows:

• • [0006] Montgomery multiplication, represented by the symbol “*”, is defined as follows:
    a*b mod n=a·b·r⁻¹ mod n,

[0007] in which r is the Montgomery radix (an integer prime with n and greater than n) and the symbol “·” represents conventional multiplication (generally called “Euclidean multiplication” in this context);

• • [0008] Montgomery exponentiation, represented by preceding the exponent with the symbol “*” and defined as follows:
    a^*e mod n=a^e·r^1−e mod n.

[0009] The advantage obtained by the use of Montgomery arithmetic is primarily that the algorithms do not then need to effect the conventional reduction modulo n, which involves an operation of division by a large number, which is particularly complex to execute.

[0010] The use of this arithmetic necessitates certain additional calculations, however, which can in some cases reduce its benefit, sometimes to the point where it is preferable to carry out an operation in the standard manner. For example, noting that:
a·b mod n=(a*r²)*b mod n,

[0011] using Montgomery multiplication to effect the modular multiplication entails precalculating the constant (r² mod n), for example as described in patent application EP 0 704 794.

[0012] In other cases, on the other hand, these additional calculations are largely compensated by the benefits linked to the use of Montgomery arithmetic. For example, since:
a^e mod n=(a*r² mod n)^*e*1 mod n,

[0013] the result of Montgomery exponentiation is transformed into the result of modular exponentiation by Montgomery multiplication by 1 of the result of the Montgomery exponentiation.

[0014] Clearly such additional operations generally represent a penalty, whether in terms of the calculation time or of the memory space necessary for storing the necessary constant (r² mod n), for example.

[0015] Because of this, it has recently been proposed to use modified cryptographic protocols that can use only Montgomery operations, for example in the patent application WO 2004/054168. Thus all the data uses the Montgomery representation and no conversion is necessary.

[0016] The patent application EP 0 578 059 also uses a solution of this type, in which modification of the relationship between public and private keys (i.e. modification of the protocol) seeks to circumvent constants that appear in the Montgomery operations and necessitate conversion of the processed data.

[0017] These solutions cannot be generalized, however, since they entail all actors of the system using Montgomery arithmetic and are therefore incompatible with systems used afterwards that employ Euclidean arithmetic.

[0018] In the above context; and in particular to reduce requirements in terms of calculation time and memory space, without compromising compatibility with existing systems, however, the invention proposes a method of storing cryptographic key data in a non-volatile storage unit of an electronic entity, characterized in that it comprises the following steps:

• • [0019] conversion of a data item, derived from at least one key portion and intended to be used with an operand in an operation of a first type into a key data item adapted to be used with said operand in an operation of a second type;
  • [0020] storage of the key data item in the non-volatile storage unit.

[0021] Thus in subsequent operation the key data can be read directly in the non-volatile storage unit in order to use it in the operation concerned of the second type, without necessitating the conversion operation that has already been effected.

[0022] In one embodiment, the conversion step is executed by a device external to the electronic entity and the key data item is transmitted from the external device to the electronic entity before the storage step.

[0023] For example, the storage step is executed during a step of personalization of the electronic entity.

[0024] In one embodiment that is particularly practical during subsequent operation, the conversion step includes Montgomery multiplication of the data item derived from the key portion by the square of the Montgomery radical.

[0025] In the same line of thinking, the invention also proposes a method of processing data used in an electronic entity including a non-volatile storage unit and necessitating the determination of the result of an operation of a first type involving an operand

[0026] characterized in that it comprises the steps of:

• • [0027] reading of a key data item in the non-volatile storage unit;
  • [0028] execution of an operation of a second type using the key data item and said operand.

[0029] Thus the operation of the second type can be executed instead of the operation of the first type, without necessitating conversion of the data used in those operations.

[0030] In other words, the invention proposes a system using a method of processing data to determine the result of an operation of a first type involving an operand in an electronic entity including a non-volatile storage unit, characterized in that it comprises the steps of:

• • [0031] conversion of a data item, derived from at least one key portion and intended to be used with the operand in the operation of the first type into a key data item adapted to be used with said operand in an operation of a second type;
  • [0032] storage of the key data item in the non-volatile storage unit;
  • [0033] reading of the key data item in the non-volatile storage unit;
  • [0034] execution of the operation of the second type using the key data item and said operand.

[0035] In certain embodiments, the result of said operation of the second type is equal to the result of the operation of the first type. The required result is therefore obtained directly.

[0036] In one particular embodiment, the operation of the second type is a Montgomery multiplication and the operation of the first type is a Euclidean multiplication involving the operand and a key, said key data item being equal to the Montgomery product of the key and the square of the Montgomery radical.

[0037] There is thus obtained a solution that is particularly easy to use to determine the result of a Euclidean multiplication by means of a Montgomery multiplication, without necessitating an additional operation of converting the operands of the multiplication.

[0038] Other embodiments of the method include a step of deconversion of the result of the operation of the second type in order to obtain the result of the operation of the first type. The invention can be therefore applied to a wider range of operations.

[0039] In certain applications, the method includes the following steps:

• • [0040] drawing of a pseudo-random number;
  • [0041] deconversion of the pseudo-random number to obtain said operand.

[0042] This is a simple way to obtain a pseudo-random number in converted and non-converted form that can be used for subsequent calculations.

[0043] For example, the method includes a step of Montgomery multiplication of the pseudo-random number and the operand, which is a simple way to obtain the Euclidean square of a pseudo-random number.

[0044] At least one of the deconversion steps mentioned above can in practice be effected by a Montgomery multiplication by unity. Such an operation does not necessitate a knowledge of the Montgomery radix or its square.

[0045] Such a method can be used in a signature generation method or a signature verification method.

[0046] In a first situation that may be envisaged, the operation of the first type is a Euclidean multiplication and the operation of the second type is a Montgomery multiplication.

[0047] In a second situation that may be envisaged, the operation of the first type is a Euclidean modular exponentiation an the operation of the second type is a Montgomery exponentiation.

[0048] In the case of using the invention in the context of an algorithm employing elliptical curves, the key data may comprise the parameters of an elliptical curve and/or the coordinates of a base point of an elliptical curve. This data therefore does not have to be converted before it is used in an operation of the second type, for example a Montgomery operation.

[0049] As will emerge hereinafter, the invention is well suited to the situation where the electronic entity is a microcircuit card, although other electronic entities may be envisaged, of course.

[0050] The invention further proposes a device for storage of a cryptographic key data item in a non-volatile storage unit of an electronic entity, characterized in that it comprises:

• • [0051] means for conversion of a data item, derived from at least one key portion and intended to be used with an operand in an operation of a first type into a key data item adapted to be used with said operand in an operation of a second type;
  • [0052] means for storage of the key data item in the non-volatile storage unit.

[0053] In one possible embodiment, the conversion means are in a device external to the electronic entity and the means for storing the key data item comprise means for transmission of the key data item from the external device to the electronic entity for storage.

[0054] Such a device forms part of a card personalization device, for example.

[0055] The invention further proposes a device for processing of data in an electronic entity including a non-volatile storage unit and necessitating the determination of the result of an operation of a first type involving an operand

[0056] characterized in that it comprises:

• • [0057] means for reading a key data item in the non-volatile storage unit;
  • [0058] means for executing an operation of a second type using the key data item and said operand.

[0059] Considered in the form of a system, the invention proposes a data processing device for determining the result of an operation of a first type involving an operand in an electronic entity including a non-volatile storage unit, characterized in that it comprises:

• • [0060] means for conversion of a data item, derived from at least one key portion and intended to be used with the operand in the operation of the first type into a key data item adapted to be used with said operand in an operation of a second type;
  • [0061] means for storage of the key data item in the non-volatile storage unit;
  • [0062] means for reading of a key data item in the non-volatile storage unit;
  • [0063] means for executing the operation of the second type using the key data item and said operand.

[0064] The devices proposed by the invention can have features corresponding to the optional features of the method referred to hereinabove and thus benefit from the resulting advantages.

[0072] One example of an electronic entity is a microcircuit card 10 the main electronic elements whereof are represented in FIG. 1 and which includes a microprocessor 2 connected on the one hand to a random-access memory (RAM) 4 and on the other hand to a non-volatile rewritable semiconductor memory 6, for example an EEPROM (Electrically Erasable Programmable Read Only Memory). Alternatively, the non-volatile rewritable semiconductor memory 6 could be a flash memory.

[0073] The memories 4, 6 are each connected to the microprocessor 2 by a bus in FIG. 1; alternatively, there could be a common bus.

[0074] The microcircuit card 10 also includes an interface 8 for communicating with a user terminal, here taking the form of contacts one of which provides a bidirectional link with the microprocessor 2, for example. The interface 8 therefore enables bidirectional communication to be set up between the microprocessor 2 and the user terminal into which the microcircuit card 10 is inserted.

[0075] Accordingly on insertion of the microcircuit 10 into a user terminal, the microprocessor 2 executes an operating system of the microcircuit card 10 in accordance with a set of instructions stored in a read-only memory (ROM), for example—not shown—or in the rewritable memory 6, which defines a computer program. This method generally includes the exchange of data with this terminal via the interface 8 and the processing of data within the microcircuit card 10, more precisely within the microprocessor 2, possibly using data stored in the rewritable memory 6 and data stored temporarily in the random-access memory 4.

[0076] Examples of methods that implement the invention are given hereinafter.

[0077] FIG. 2 represents the general physical appearance of the microcircuit card 10 whose general shape is a very thin rectangular parallelepiped.

[0078] The communication interface 8 provided with the contacts already mentioned is clearly apparent on the face of the microcircuit card 10 visible in FIG. 2, in the form of a rectangle on the upper face of the microcircuit card 10.

[0079] Methods used in a first embodiment of the invention are represented in FIGS. 3 and 4.

[0080] The method represented in FIG. 3 is a method of storing a data item c in the non-volatile memory 6 that is used, for example, during the step of personalization of the microcircuit card, i.e. during the step in which all of the basic data that the non-volatile memory 6 must contain is stored in the microcircuit card.

[0081] This step is executed by a card personalization system, for example, operating in accordance with the same principles as a microcomputer, and using a special procedure to communicate to the microcircuit card 10 data to be stored in the non-volatile memory 6, generally via the interface 8.

[0082] During a step E30, the personalization system receives a secret key a, for example from a secure hardware module (SHM) such as an IBM 4758 PCMCIA. In the example described here, the secret key a is referred to as Euclidean because it is intended to be used in a cryptographic protocol defined by Euclidean operations.

[0083] There follows in the step E32 an operation of pre-conversion of the Euclidean secret key a into a key c usable directly in the Montgomery representation and obtained by means of the operation:
c=a*r² mod n,

[0084] in which r is the Montgomery radix for the chosen Montgomery representation.

[0085] As described in detail hereinafter, when the key c determined in this way is multiplied in the Montgomery sense by any operand, the result of the Montgomery multiplication is equal to the Euclidean product of the Euclidean secret key a and the operand itself.

[0086] The step E32 is executed by the card personalization system, for example. Such devices generally have large calculation and memory means so that the pre-conversion of the Euclidean secret key a is effected without difficulty.

[0087] The pre-converted key c can then be transmitted to the microcircuit card 10 for storage in the non-volatile memory 6 in a step E34.

[0088] Alternatively, and in particular if the microcircuit card 10 includes Montgomery arithmetic calculation electronic circuits, the pre-conversion step E32 can be carried out within the microcircuit card 10.

[0089] In a first form of this variant, the personalization system transmits the Euclidean secret key a and the Montgomery radix r via the interface 8 to the microprocessor 2, which stores these values in the random-access memory 4 and then effects the pre-conversion in order to obtain the pre-converted key c (step E32) and store it in the non-volatile memory 6 (step E34).

[0090] In a second form of this variant, the Montgomery radix r is stored in the non-volatile memory 6 during a step of personalization of the card as described above; during a later step in which a secret key is to be stored in the card, the Euclidean secret key a is transmitted to the card via the interface 8 and stored in the random-access memory 4, the Montgomery radix r is read in the non-volatile memory 6 and stored in the random-access memory 4, and the card then proceeds to calculate the pre-converted key c using the Montgomery multiplication operation referred to above (step E32) and stores the pre-converted key c in the area of the non-volatile memory 6 that until this point contained the Montgomery radix r (i.e. it overwrites the latter value).

[0091] This latter solution is of course usable only if it can be determined in advance (for example in the light of the intended uses of the card) that future operations will no longer use the Montgomery radix r.

[0092] An example of use of a microcircuit card prepared in accordance with the storage method that has just been described is described next with reference to FIG. 4.

[0093] In this example, a third party seeks to verify that his interlocutor is holding the secret key of value a in Euclidean representation (i.e. in practice that he is already in possession of the microcircuit card storing the Euclidean secret key a), although without communicating that secret key.

[0094] In accordance with a procedure that is relatively simple and is described here by way of one example of the use of the invention, the third party sends a data item b unknown to the cardholder (for example generated pseudo-randomly) and waits to receive in return the modular (Euclidean) product of the data item b sent and the secret key a, which product only a person holding the secret key is a priori able to determine.

[0095] The microcircuit card 10 then receives in a step E40 the data item b sent by the third part and stores it in the random-access memory 4.

[0096] In the next step E42, the microprocessor 2 commands reading of the pre-converted key c in the non-volatile memory 6. (Remember that this key c was stored in the non-volatile memory 6 in the step E34 described with reference to FIG. 3).

[0097] There follows in the step E44 the Montgomery multiplication of the pre-converted key c read in the non-volatile memory 6 and the data item b received from the third party, in order to obtain a result d. This calculation is carried out by a Montgomery arithmetic calculation electronic circuit (not shown), for example.

[0098] Because c=a*r² mod n (by definition: see the step E32 described with reference to FIG. 3), the result of the Montgomery multiplication of the pre-converted key c and the received data item b is equal to the result of the modular Euclidean product of the Euclidean secret key a and the received data item b, in accordance with the formulae:
c*b mod n=(a*r² mod n)*b mod n=a·b mod n.

[0099] The result of the modular multiplication by the Euclidean secret key a is obtained in this way, using Montgomery arithmetic, but without necessitating storage of its radix r, which avoids any change of protocol with the third party.

[0100] The data item d can therefore be sent directly to the third party in a step E46.

[0101] Note also in this connection that the Euclidean representation a and the pre-converted representation (or Montgomery representation) c are two forms of representation for the same secret key, since the holder of the microcircuit card can prove his knowledge of the secret key known in its Euclidean form to the third party a whereas only the key in its pre-converted form c is stored in the non-volatile memory 6.

[0102] Note however that the proposed solution entails the Montgomery arithmetic used at the time of pre-conversion (step E32) and that used for the Montgomery multiplication in the step E44 use the same radix r.

[0103] A second example of the use of the invention is described next with reference to FIGS. 5 and 6.

[0104] FIG. 5 shows the main steps of a method for storing a data item derived from a key for its subsequent use in an RSA (Rivest-Shamir-Adelman) type encryption algorithm.

[0105] Remember that the RSA encryption system is based on the use of a public key formed of two integers (n, e) and a private key consisting of three integers (d, p, q), such that:
n=p·q and d·e=1 mod [(p−1)(q−1)]

[0106] where p and q are prime numbers.

[0107] In this encryption system, applying the private key to a message m consists in calculating the modular exponentiation product m^d mod n (where n=p·q), whether to sign the message m or to decrypt it.

[0108] To simplify the calculation of this modular exponentiation if the holder of the private key knows the decomposition n=p·q, the Chinese remainder theorem (CRT) is frequently used, in accordance with the formula:
m^d=[(S₂−S₁)·A_pq mod q]·p+S₁

[0109] where S₁ and S₂ are the results of partial modular exponentiations described in detail hereinafter and A_pq is the modular reciprocal of p modulo q (i.e. where A_pq=p⁻¹ mod q). Thus A_pq is derived from the portion of the private key formed by the numbers p and q.

[0110] During a step preceding the execution of the modular exponentiation calculation, for example during personalization of the microcircuit card used (i.e. during the storage of the information necessary for the basic operation of the card), the method shown in FIG. 5 is executed.

[0111] That method begins in the step E50 with the calculation of the parameter A_pq that has just been defined.

[0112] There follows the step E52 in which the pre-converted modular reciprocal A* is calculated using the formula:
A*=A_pq*r² mod q.

[0113] The calculations effected in the steps E50 and E52 are effected by the card personalization system, for example, which then transmits the result, namely the pre-converted modular reciprocal A*, to the microcircuit card by means of the interface 8.

[0114] The microcircuit card then proceeds to store the pre-converted modular reciprocal A* in its non-volatile memory 6.

[0115] There is described next one possible solution for application of the private key according to the RSA algorithm in the microcircuit prepared by the method just described with reference to FIG. 5.

[0116] The proposed method uses the Chinese remainder theorem and therefore necessitates, in a step E60, calculation of the modular remainders of the message m to which the private key is applied, in accordance with the formulas:
m₁=m mod p and m_e=m mod q.

[0117] Similarly, in a step E61, the exponents used in the Chinese remainder theorem must be determined:
d_p=d mod(p−1) and d_q=d mod(q−1).

[0118] The value of the parameter r², where r is the Montgomery radix, is then read in the non-volatile memory 6 in a step E62. This parameter is then stored in the random access memory (RAM) 4.

[0119] There can then follow in a step E63 the partial modular exponentiations using Montgomery arithmetic in accordance with the formulae:
S₁=(m₁*r² mod p)^*dp*1 mod p
S₂=(m₂*r² mod q)^dq**1 mod q

[0120] The values obtained are naturally stored in the random access memory 4. After this step E63, the random access memory therefore contains the values of p, q, S₁, S₂ and r².

[0121] The proposed method no longer uses the value of the parameter r² once the results of the step E63 are known (see below).

[0122] It is therefore possible in a step E64 to read the pre-converted modular reciprocal A* in the non-volatile memory 6 and to store that value in place of the parameter r² in the random access memory, i.e. to overwrite the value of r².

[0123] It is therefore possible to limit the memory size necessary for execution of the method (which is particularly advantageous in a microcircuit card which typically has 4 kbytes or 8 kbytes of RAM, while storing the parameter r² alone necessitates 1024 bits, i.e. ⅛ kbytes). In this regard, note generally that the random access memory size necessary for executing a calculation is critical because it is necessary to minimize relatively costly access to non-volatile memory such as EEPROM.

[0124] The following calculation is then executed in a step E65, using a Montgomery multiplication:
[(S₂−S₁)*A^* mod q]·p+S₁,

[0125] which, given the definition of the pre-converted modular reciprocal specified in the step E52, has the precise value:
m^d=[(S₂−S₁)·A_pq mod q]p+S₁.

[0126] The result of the modular exponentiation is therefore obtained using Montgomery arithmetic but without having to store the parameter r² permanently in random access memory or to read this parameter in non-volatile memory on each execution of a Montgomery operation.

[0127] Moreover, although the microcircuit card stores a parameter used as one of the operands in a Montgomery multiplication (here the pre-converted modular reciprocal A*), the message m, the intermediate results (in particular S₁ and S₂), and the result m^d are linked by the standard relationships of Euclidean representation, and the method that has just been described can therefore be used in a system in which the other users (for example those wishing to verify the signature produced by application of the private key or to encrypt the message sent to the holder of the private key) do not have access to Montgomery arithmetic.

[0128] A third example of the use of the invention is described next in the context of the Feige-Fiat-Shamir (FFS) signature scheme. The general principles of this signature scheme are explained in “Handbook of applied cryptography”, A. Menezes, P. Van Oorschot and S. Vanstone, CRC Press, 1996, section 11.4.1, for example.

[0129] According to this scheme, the private key is made up of k elements s₁, s₂, . . . , s_k linked to the k elements ν₁, ν₂, . . . , ν_k that with the modulus n form the public key by the relationship: ν_j=s_j⁻² mod n, for all j in 1 and k.

[0130] To sign a message m in the context of this signature scheme, a microcircuit card of the type described with reference to FIG. 1 is used, which stores the pre-converted keys S*_j defined on the basis of the keys s_j of the chosen signature scheme in accordance with the relationship:
S_*j=s_j*r² mod n.

[0131] A method similar to that described with reference to FIGS. 3 and 5 can be used to store the pre-converted keys S_*j, for example during personalization of the microcircuit card.

[0132] To sign a message m in accordance with the FFS algorithm using the private key consisting of the elements s_j using this kind of microcircuit card, the following steps are executed:

• • [0133] choice of a number ρ₁, for example by drawing pseudo-random numbers (this number will be considered as the Montgomery representation of a pseudo-random number);
  • [0134] calculation of ρ₀=ρ₁*1 mod n (which amounts as explained hereinafter to deconverting the number ρ₁ so that the number ρ₀ is considered as the Euclidean representation of the number represented by ρ₁ in the Montgomery representation);
  • [0135] calculation of u=ρ₁*ρ₀ mod n (which implies that u=ρ₀² mod n in accordance with the standard FFS scheme);
  • [0136] calculation of the set of k elements e=(e₁, e₂, . . . , e_k)=h(m∥u) where h is a hashing function and where the components e_i of e have the value 0 or 1;
  • [0137] calculation of

[0138] $s={\rho }_0*\left(\prod _{j=1}^k*S_{*j}^{*e_j}\right),$
where the symbol

[0139] $\prod _{j=1}^k*$
represents the product of the k elements by Montgomery multiplications.

[0140] Given the definition of S_*j, the number s is none other than the signature of the message m in the FFS scheme:

[0141] $s={\rho }_0·\prod _{j=1}^k{S}_j^{e_j}.$

[0142] Note that Montgomery arithmetic has therefore been used to effect the modular multiplications required by the FFS scheme without having to store the Montgomery parameter r (or its square r²) in the microcircuit card.

[0143] A fourth embodiment of the invention, described next, relates to the Guillou-Quisquater (GQ) signature scheme. The principles of this kind of signature scheme are described in the work “Handbook of applied cryptography” already referred to, for example, in section 11.4.2.

[0144] The GQ scheme uses a private key a and a public key consisting of the modulus n, an integer e and an identifier J_A of the holder A of the private key a.

[0145] To obtain the signature of a message m, the holder A of the private key a stored in pre-converted form a_m in the non-volatile memory of a microcircuit card (where a_m=a*r² mod n) uses the following method in the microcircuit card:

• • [0146] choice of a number k unknown to the public and preferably variable, for example by drawing of a pseudo-random number;
  • [0147] calculation by Montgomery exponentiation followed by deconversion of the number ρ: ρ=k^*e*1 mod n;
  • [0148] calculation of l=h(m∥ρ), where h is a hashing function;
  • [0149] calculation by means of a Montgomery multiplication using the pre-converted key a_m of the signature s from the formula:
    s=k*(a_m^*l)*1 mod n.

[0150] The calculations are therefore effected using Montgomery arithmetic, but without necessitating storage of the Montgomery radix r (or its square), thanks to the use of the pre-converted key a_m and to the organization of the calculations in such a manner as to use only deconversions (i.e. Montgomery multiplications by unity) that do not need to know the Montgomery radix.

[0151] The signature (s, l) obtained is therefore identical to that which would have been obtained by Euclidean calculations from the private key a and can therefore be verified by means of the public key (n, e, J_A) previously referred to and linked to the private key a by the standard relationships of Euclidean arithmetic described in the work mentioned above, for example, at the algorithm 11.47.

[0152] The algorithm for verification of the signature (s, l) can nevertheless also use the invention, for example in accordance with the following method that uses pre-converted keys in an electronic entity in which are stored the square r² of the Montgomery radix and the pre-converted identifier J_Am, which has the value J_Am=J_A*r² mod n:

• • [0153] reading of the square r² of the Montgomery radix in the non-volatile memory 6 and storing it in the random access memory 4;
  • [0154] conversion of the signature s in the Montgomery representation by the calculation of the converted signature s_m=s*r² mod n;
  • [0155] reading of the pre-converted key J_Am in non-volatile memory and storing this pre-converted public key in random access memory, overwriting the value of the square r² of the Montgomery radix previously stored therein;
  • [0156] calculation of u=s_m^*e*J_Am^*l*1 mod n;
  • [0157] calculation of l′=h(m∥u), where h is the hashing function already referred to;
  • [0158] verification of the validity of the signature by verification of the equation l=l′.

[0159] In this latter embodiment, the square r² of the Montgomery radix is stored in the non-volatile memory of the electronic entity. However, storing the public key (identifier) J_A in pre-converted form authorizes overwriting in random access memory of the square r² of the Montgomery radix and thus limitation of the memory size required to effect the operation.

[0160] A fifth embodiment of the invention is described next in the context of the DSA signature scheme as described in the work “Handbook of applied cryptography” already referred to.

[0161] The public key element a and the private key a are stored in their pre-converted forms a_m and a_m, respectively, in the non-volatile memory of the electronic entity that has to generate the signature, for example a microcircuit card. Thus a_m=a*r₁² mod p where a is the public key used in the protocol concerned and a_m=a*r₂² mod q where a is the corresponding private key. (A Montgomery radix r₁ is used for the operations modulo p and a Montgomery radix r₂ is used for the operations modulo q.)

[0162] Signature generation can then be effected by means of the following steps:

• • [0163] selection of a number k₁, for example by drawing of a pseudo-random number;
  • [0164] calculation of k₀=k₁*1 mod q: k₀ will be considered to be a pseudo-random number whose representation converted into the Montgomery representation has the value k₁;
  • [0165] calculation of ρ=(a_m^*k0*1 mod p)mod q;
  • [0166] calculating the reciprocal of k₁ modulo q in the Montgomery sense, k₁^*(−1)mod q, by calculation of (by analogy with the Euclidean case): k₁^*(q−2)mod q;
  • [0167] calculation of s=(k₁^*(−1))*{h(m)+a_m*ρ} mod q, where h is a hashing function.

[0168] Note that k₁^*(−1)mod q=k₀⁻¹·r₂ mod q, i.e. that k₁^*(−1) is also the result of the conversion into the Montgomery representation of the reciprocal of k₀.

[0169] The signature of the message m in accordance with the DSA protocol using the private key a and the public key a is therefore the pair (ρ, s).

[0170] A sixth embodiment of the invention is described next in the context of the GQ2 signature protocol, described for example in the paper “GQ2 une preuve zero-knowledge de connaissance de la factorisation complément essentiel à RSA” [“GQ2 a zero-knowledge proof of knowledge of the complement factorization essential to RSA”], S. Boutiton, F. Daudé and L. Guillou, proceedings of the SSTIC04 symposium.

[0171] The electronic entity used by the prover, for example a microcircuit card, stores in its non-volatile memory m secret numbers Q₁, Q₂, . . . , Q_m in their pre-converted form for the Montgomery operations (which can therefore be referred to as their Montgomery form) Q₁^*, Q₂^*, . . . Q_m^*, where Q_i^*=Q_i·r mod n=Q_i*r² mod n.

[0172] The electronic entity held by the prover then executes the following steps:

• • [0173] selection of a number ρ₁, for example by drawing of a pseudo-random number;
  • [0174] deconversion of the number ρ₁ considered in Montgomery form to obtain a number ρ₀ which can then also be considered to have been obtained by drawing of a pseudo-random number, in accordance with the formula ρ₀=ρ₁*1 mod n;
  • [0175] calculation of the witness W=(ρ₁^*v mod n)*1 mod n, where the verification exponent v is a given of the protocol, W then having the value ρ₀^v mod n;
  • [0176] in response to each challenge from the verifier consisting in a series of m random numbers d₁, d₂, . . . , d_m, calculation of the response
    D=ρ₀*(Q₁^*)^*d₁*(Q₂^*)^*d₂^* . . . * (^Q_m^*)^*d_m.

[0177] Thanks to the definition of the pre-converted secret numbers Q_i^*, the number D has the value ρ₀. Q₁^d₁. Q₂^d₂ . . . Q_m^d_m: this is the response to be sent to the verifier without necessitating other complementary calculations.

[0178] As before, storage of the pre-converted secret keys and deconversion of the pseudo-random number ρ₁ enable Montgomery operations to be applied to data received from an external device and to be sent to that external device, without the latter necessarily having access to Montgomery arithmetic, or the electronic entity that uses Montgomery arithmetic using the known Montgomery radix r (or its square r²).

[0179] The embodiments that have just been described are merely possible examples of implementation of the invention. The invention could be applied to protocols other than those indicated.

[0180] For example, noting that there is an isomorphism between an elliptical curve
EC: y²=x³+a·x+b mod p

[0181] and the associated Montgomery curve
EC*: y^*2=x^*3+(a^*r²)^*x+(b^*r²)mod p,

[0182] and consequently that if a point P with coordinates (x, y) is on the curve EC, its image as a result of this isomorphism is the point on the curve EC* with coordinates (x^*r², y^*r²), the invention can be used in the context of algorithms operating on elliptical curves that store in the electronic entity the preconverted parameters (a^*r²), (b^*r²) and the preconverted coordinates (x^*r², y^*r²) of the base point, substituting Montgomery multiplications for the Euclidean multiplications.

[0183] Operations on the points of the elliptical curve used in the cryptographic algorithms amount to multiplications, which can therefore be effected using Montgomery arithmetic.

[0184] Moreover, when these operations use the coordinates of the base point and the latter are stored in preconverted form in the electronic entity, Montgomery arithmetic can be used directly without having to store the value of the Montgomery radix r or its square r².

[0185] As in the aforementioned examples, it can nevertheless be necessary to deconvert the result obtained by applying to it a Montgomery multiplication by unity, which does not involve knowing the Montgomery radix.

[0186] The invention is not limited to use in microcircuit cards and is to be contrary applicable to any type of electronic entity, for example computers, personal digital assistants (PDA), telephones and electronic passports (these examples are not limiting on the invention).