Cryptography method and smart cards microcircuit

[0001] The invention relates to a method of cryptography in a smart card comprising a central processing unit, the method implementing precomputation operations. The invention also relates to a microcircuit for smart cards capable of communicating with the exterior through an input-output interface, said microcircuit comprising means for the execution of tasks, including a computation task, and means to manage the execution of the tasks.

[0002] It can be applied to contact type smart cards or contactless smart cards as well as to combination cards, namely cards that can be used for operation with contact as well as contactless operation.

[0003] A smart card C with a chip or chips comprises a microcircuit MC shown in FIG. 1, essentially comprising an input-output interface, a microprocessor UC, an operating program memory M1 for example a ROM (or Read Only Memory), an application(s) program memory M3 for example an EEPROM (Electrically Erasable Programmable Read Only Memory), a working memory M2, for example a RAM (Random Access Memory).

[0004] In the case of contact-type smart cards, the input-output interface is formed by an asynchronous reception or transmission unit UART and a receiver CN generally comprising eight contact zones flush with the card.

[0005] In the case of contactless smart cards, this input/output interface is formed by the asynchronous unit UART and a radiofrequency transmitter-receiver device RF comprising an antenna.

[0006] In the case of combined-operation smart cards, this interface comprises, of course, the device RF and the contact zones CN.

[0007] The field of the invention is that of smart cards using the results of exponentiation computations referenced g^x and often done as modulo n computations. These computations are executed in numerous applications based especially on the signing or authentication of messages.

[0008] The most practical and reliable authentication or signing schemes used at present are the public key algorithms. The best-known and most widely used of these is the RSA algorithm (named after its inventors R. Rivest, A. Shamir and L. Adleman), which is costly in computation time. The schemes based on the discrete algorithm too have been known for a long time and have the advantage of lending themselves to precomputation operations relating especially to the exponentiation computations which are very costly in time.

[0009] The invention can be applied to microcircuit cards implementing public key algorithms using the discrete logarithm in any mathematical structure, especially rings of numbers modulo n (where n belongs to the set Zn, the set of positive integers smaller than n), the elliptic curves on the finite fields GF(q) (GF(q) being the field for which the number of elements is q, with q as a prime number or the power of a prime number). The exponentiation g^x covers all these structures.

[0010] Exemplary methods implementing such computations are presented in the patent application FR No. FR 2 716 058.

[0011] In the case of Zn and of the present embodiments requiring modular exponentiation type (b^x modulo n) computations where the numbers b, x and n commonly have lengths ranging from 768 to 1024 bits, the performances are in the range of 500 to 300 ms. This performance can be achieved only with 8-bit microprocessors using crypto-processors capable of performing high-speed operations of multiplication and modulo n reduction or with 16-bit or 32-bit microprocessors whose intrinsic performance characteristics enable these performance levels to be achieved without resorting to a specific computation cell such as a crypto-processor.

[0012] These performance levels are not sufficient in certain cases. We shall now present an exemplary use of combination cards for public transport services.

[0013] When the card works in contactless mode, it must enable a terminal, during entry into an underground station or into a bus, to authenticate the ticket, verify an entitlement to a certain type of reduction and/or receive payment by electronic wallet (PME). For this type of transaction, as in general for PME type transactions, the public key cryptography algorithms are used for purposes of key management, compliance with standards and, ultimately, security.

[0014] This type of transaction must take place within 150 ms. This is the time needed for a user to pass the card, in a natural movement, before a terminal integrated into a turnstile or located at the entrance to a bus. These 150 ms must then cover not only the cryptographic computations but also the inputs/outputs of the messages and the processing operations other than cryptographic processing operations, whether they are done on the terminal side or on the card side. The processing operations on the terminal side and card side cannot take place in parallel because they are sequenced in a precise order established by a predefined protocol. In practice, given the computation time required on the terminal side, the cryptographic computations on the card side must therefore take place in less than 30 ms.

[0015] There is no microcircuit card component today that enables such performance levels to be achieved. Furthermore, since the card, in contactless mode, is powered by the energy radiated by the terminal and recovered at the antenna, the consumable power is limited and therefore the computation capacities are limited too.

[0016] In contact mode, these constraints are not as acute. For example, in payment by electronic purse or wallet, the customer does not need to be made to wait at the sales point for more than a few seconds. However, certain operations demand that the transactions should remain short, in the range of one second.

[0017] To know the details of the computations performed by a public key cryptography algorithm, reference may be made to the patent application FR No. 2 716 058 which presents a method for the digital signing and authentication of messages using a discrete logarithm.

[0018] The method as described in the above patent may be summarized as follows.

[0019] The signing method is preceded by a preliminary phase shown in FIG. 2a.

[0020] An authority A, for example a bank or a transport organization, holding a public key P_A and a secret signing key S_A, chooses a number n (a prime number or composite of prime numbers) and g (an integer smaller than n and generally far smaller) as well as a hashing function h and sends P_A, n, g and h to the entity S which must sign a message, this entity being for example a smart card that has to validate an amount to be paid, as well as to the entities V which must verify the signing, these entities being, for example, terminals such as the ones presently used by tradesmen with their customers.

[0021] The entity S chooses a secret key x, computes its public key yg^x mod n, sends it to the authority A which sends back a certificate Cert to it. This certificate is itself set up especially on the basis of its secret signing key S_A.

[0022] The pieces of data n, g, x, y, Cert are permanent data of the entity S.

[0023] With this preliminary phase completed, the method for signing a message M can start. For S, as shown in FIG. 2b, this may entail the signing of an amount to be paid proposed by V; the message M contains especially the amount to be paid m and an identification of the terminal V requesting this payment.

[0024] The following are the steps of this signing method:

[0025] a) S randomly chooses k,

[0026] b) a witness element rg^k mod n is computed

[0027] c) a known hashing function h of A, S and V is used to compute ch(r,M)

[0028] d) finally skcx is computed

[0029] e) S sends V this information: y, Cert, M, c, S

[0030] V verifies Cert with P_A, computes uy^cg^s mod n and verifies that ch(u,M). If the verification is right, the signing of M is authenticated.

[0031] One of the steps of this method consists of the computation, at each transaction, of a witness r requiring an exponentiation (rg^k mod n for example). This operation uses a great deal of time; this is why it is sometimes planned to precompute these witness elements. However, these precomputations are done by an external device and then the pairs (k,r) are written in a storage zone of the card, for example M3, and this has drawbacks.

[0032] Indeed, the knowledge of the data needed to compute these witness elements and knowledge of the witness elements themselves makes it possible to recover the secret cryptography key. Indeed, the knowledge of r and k gives ch(r,M); the knowledge of skcx and k and c and gives x. The secret is therefore shared between the entity supposed to hold it and this external device in which therefore a great deal of trust has to be placed.

[0033] It is also necessary to be assured of the total security of the sending of the pairs (k,r) to the card and of their writing.

[0034] Furthermore, if the card no longer contains pairs (k,r), it must be reloaded with them. This requires a special terminal connected to a network.

[0035] The aim of the invention is to avoid these drawbacks by seeing to it that the pairs (k,r) are computed by the card without any adverse effects on the duration of the transactions.

[0036] This is obtained by basing the invention on the fact that, in a smart card microprocessor (or computer in general), a major proportion of the time is devoted to waiting for external events to take place. During such times or waiting periods, namely when the card is waiting for a new control message from the terminal or else when the card is in a phase of reception or transmission of a lengthy message on its input/output port, the microprocessor can compute the witness elements r if the zone of storage of the pairs (k,r) is not full.

[0037] These waiting times shall be highlighted in the case shown in FIG. 3 for the recharging of a combined card type of electronic purse card (PME) linked through a telecommunications or computer network R to the reloading server of a financial organization F. This device C may be a Minitel terminal or computer or again a two-slot portable telephone, of a kind already in existence, capable of receiving another card such as a card PME in addition to the usual SIM (Subscriber Identity Module) card.

[0038] After the card PME has been introduced into the device P, with the card then working in contact mode, the device P requests the card PME to authenticate itself. The signature of PME is transmitted by P to F, along with the amount to be loaded into the card PME. Starting from the onset of this transmission, the card PME inserted into the device P is in a waiting state.

[0039] The transmission to the server of F through the network last about 5 to 10 seconds. The authentication by the server of F of the signature of PME and the signing by F of the amount to be reloaded may last about two seconds. Similarly, the transmission from F to P, through the network R, of the signed reloading message may again take 5 to 10 seconds. The waiting time of the card will have been about 15 seconds.

[0040] After reception by P and then by the card PME of the reloading message, the latter verifies the signature of F. Then, if the authentication is successful, the PME card updates its credit.

[0041] In this example, the card thus has sufficient waiting time to perform precomputations.

[0042] An object of the invention is a method of cryptography in a smart card, the card comprising a central processing unit, said method implementing precomputations, chiefly characterized in that said precomputations are performed by the smart card and in that the precomputations are performed at a session during the input-output waiting periods of the central processing unit.

[0043] This method may, as the case may be, implement an algorithm based on the computation of a discrete logarithm.

[0044] According to one characteristic, the precomputations therefore comprise computations of exponentiation.

[0045] The precomputations are advantageously performed in steps by carrying out intermediate computations, the results of these intermediate computations being stored in the smart card.

[0046] An object of the invention is also a microcircuit for a smart card capable of communicating with the exterior through an input-output interface I, comprising task-execution means ET including a computation task PC and means GE for the management of the execution of the tasks, characterized in that the management means GE comprise means APC for the activation of the computation task PC during the waiting times pertaining to the other task or tasks active on the microcircuit.

[0047] According to one characteristic of the invention, the task execution means ET comprise a microprocessor UC, a program memory M1 comprising the task execution management program and an applications program memory M3 comprising the executable task or tasks in the form of one or more application programs.

[0048] The task execution means ET may furthermore comprise a cryptographic computation circuit CP.

[0049] According to another characteristic of the invention, the task execution means ET are capable of carrying out computations of exponentiation.

[0050] According to one embodiment of the invention, the computation task activation means APC comprise a circuit O for the scheduling of the inputs-outputs of/on the card capable of activating the task execution means ET when said scheduling circuit O awaits an input or an output.

[0051] The microcircuit preferably comprises means M3 to store the results of said computations.

[0052] An object of the invention is also a contactless and/or contact type microcircuit card comprising a microcircuit as described here above.

[0053] Other features and advantages of the invention shall appear more clearly from the following description given by way of a non-restrictive example and from the appended drawings, of which:

[0054] FIG. 1 is a schematic view of a smart-card microcircuit,

[0055] FIG. 2a provides a schematic view of the progress of the preliminary certification phase, necessary before the use of a signing method,

[0056] FIG. 2b gives a schematic view of the signing phase of a signing method,

[0057] FIG. 3 gives a schematic view of the progress of an electronic wallet reloading transaction,

[0058] FIG. 4 is a flow chart showing the working of the activation means APC,

[0059] FIG. 5 is the flow chart of an exemplary precomputation according to the invention.

[0060] The microcircuits of the smart card(s) such as those considered in the invention are constituted by different elements connected together by a bus, the most important of these elements being shown in FIG. 1.

[0061] The central processing unit UC or microprocessor executes the instructions of the programs stored in a ROM type non-volatile memory M1. This central processing unit UC conventionally receives the clock signals H and Reset signals R through an interface I. When the card works in contact mode, the signals H and R come from the contacts whereas, when the card works in contactless mode, these signals are given by the RF signal received through a radiofrequency device RF

[0062] This central processing signal UC is sometimes seconded by a crypto-processor CP specialized in the fast processing of modulo n operations of exponentiation.

[0063] The memory M1 contains task execution management means GE which, in certain cases, are included in the COS (Chip or Card Operating System. The function of the COS is to manage the inputs-outputs, organize and manage the memory, manage access authorizations (confidential codes), organize the response to the Reset signal, carry out the loading if necessary of specific sub-programs during the customization of the card or during the use of the card. The memory M1 also sometimes contains the programs of the applications.

[0064] The programs of the memory M1 use RAM type working memories M2 or registers and EEPROM type permanent memories M3 for the permanent data which must not be erased even if the circuit is no longer powered. The application programs are often stored in these memories M3.

[0065] The microcircuit communicates with the exterior by means of an asynchronous reception or transmission unit UART responsible for receiving or transmitting messages in the form of blocks of several bytes. This asynchronous unit UART itself communicates with the input/output series link ES through an interface I. In the case of contact type cards, the messages pass through the contact zones and, in the case of the contactless cards, the messages pass through the radiofrequency device RF.

[0066] The microcircuit is supplied with energy by the interface I which is itself supplied with the supply voltage referenced Vcc (Vcc5 Volts) and by the electric ground referenced Vss (Vss0 Volt). In contact type mode, the interface I is powered through the contacts while, in contactless mode, it is powered by the radiofrequency signal through the radiofrequency device RF.

[0067] According to the invention, in the operating system COS stored in the memory M1, there are provided means GE for the management of the tasks ET and the different tasks constituting the applications. These tasks include the computation task PC: it will be activated by the management means GE during the waiting time corresponding to the other tasks which will thus be put to good use to perform the precomputations and save them in the memory M3.

[0068] To this end, the management means GE comprise means APC for the activation of the precomputation tasks PC. These activation means APC may consist of a program or may be integrated into a scheduling circuit O.

[0069] A description shall now be given of the working of these activation means APC shown in FIG. 4 while the computation of witness elements task is active, namely when a computation of witness elements is in progress, step I.

[0070] When there is an external event, namely when the waiting times used by the computation of witness elements task to execute its computations are over (step II), and if the supply to the card is not cut off (step III), the means APC pass on to whichever task is entitled to be performed:

[0071] if the external event corresponds to the reception of a new N-byte message by the UART the means APC then pass on to the task that was awaiting this message, for example the task t1 (step IV),

[0072] if the external event corresponds to the end of transmission, by the UART, of a message comprising N bytes, the means APC then pass on to the task in which this message had been sent out, for example the task t2 (step IV).

[0073] Then when the task ti (t1 or t2 in the present example) to which the means APC had returned is completed or when an external event takes place (step 5) prompting a wait, the means APC return to the computation of witness elements task during this waiting period until this computation of witness elements task is completed (the witness elements storage zone is full) or when an external event occurs (step V) and there is then a return to the initial situation.

[0074] It may be considered that the APC means manage the priorities between the tasks, the applications tasks always having priority over the computation of witness elements tasks.

[0075] The computation of witness elements may be lengthy: several hundreds of ms. To the extent that this computation may be interrupted by the other tasks which are priority tasks or by a power cut, this computation is done in steps, the intermediate results being saved in the storage zone, in this case the memory M3. Thus, a computation that is started but not completed will not be lost and could be resumed without any need to redo the entire computation which has already been performed, when the APC means return to this witness element computation task. If the task is interrupted during the step m, the results of the step m-1 having been saved, the computations will resume at the start of the step m when the means APC again return to the task.

[0076] A step is itself formed by elementary loops and a loop counter used to activate the saving if a predetermined number of loops has been counted. To give a clear picture, if k amounts to 300 bits, the computation can be organized in 10 steps of 30 loops each.

[0077] One example for which the flow chart is shown in FIG. 5 illustrates this process in which the witness element r is computed according to the formula

[0078] A preliminary step I precedes the computation itself: this step consists in choosing k and initializing the parameters that will be used thereafter with the values of the saved parameters or with default values. The computation is done in a loop comprising the steps II to VI, consisting of comparisons, computations and saving or storage operations.

[0079] These computations of witness elements by the card during the waiting periods makes it possible, during a transaction, to replace the steps a and b) (choose k and cancel r) of the signing method initially described by read a pair (k,r) in the storage zone, this storage zone having been filled according to the method equivalent to that indicated here above. The other computations remaining to be executed by the card are simple and fast computations. The cryptographic computations on the card side then occur in less than about 10 ms and thus enable the required performance levels to be easily achieved.

[0080] It is furthermore possible to achieve savings in memory space.

[0081] Indeed, if k is generated by a reproducible pseudo-random generator, then k does not have to be saved: only the input parameters of the generator can be saved. This represents a saving of memory space.

[0082] Similarly, it is not necessary to store the pair (k,r) in its totality: it is enough to limit the storage to a small number of bits of g^k mod n. An example is given in the patent No. FR 2 752 122.