FR2672402A1

FR2672402A1 - Process and device for generating unique pseudo-random numbers

Info

Publication number: FR2672402A1
Application number: FR9101268A
Authority: FR
Inventors: Geronimi Francoi Ballot-Schmit; Viricel Gilles
Original assignee: Gemplus Card International SA
Current assignee: Gemplus SA
Priority date: 1991-02-05
Filing date: 1991-02-05
Publication date: 1992-08-07
Anticipated expiration: 2011-02-05
Also published as: FR2672402B1

Abstract

The process consists in registering (1, 2) into a specified area of the non-volatile memory of a microcircuit memory card a specified and non-repetitive value item with each generating of a random number and in converting (3, 4) this item into an item having the form of a pseudo-random number by programming the processing unit by means of a standard information encrypting program of the DES type. Application: memory cards.

Description

PROCEDE ET DISPOSITIF POUR LA GENERATION
DE NOMBRES PSEUDO-ALEATOIRES UNIQUES
La présente invention concerne un procédé et un dispositif pour la génération de nombres pseudo-aléatoires uniques.GENERATION METHOD AND DEVICE
UNIQUE PSEUDO-RANDOM NUMBERS
The present invention relates to a method and a device for generating unique pseudo-random numbers.

Elle s'applique notamment à la réalisation de cartes à microcircuits dites à puces utilisables dans tout système où l'accès à des informations ou à des services est sévèrement contrôlé. Il s'agit notamment des systèmes distributeurs de monnaie fiduciaire, du domaine des systèmes de télévision à péage ; des systèmes pour la distribution d'essence ou de fuel domestique ; des systèmes pour l'accès aux banques de données etc... It applies in particular to the production of so-called chip microcircuit cards usable in any system where access to information or to services is severely controlled. These include, for example, cash dispenser systems, pay television systems; systems for the distribution of gasoline or domestic fuel; systems for access to databases etc ...

Dans les cartes à mémoire à microprocesseur qui sont utilisées dans les domaines précédents, l'accès à des informations ou à des services est sévèrement contrôlé. On utilise pour cela des mots de passe. Ces mots de passe sont de plus en plus souvent transmis en les cryptant par un code pseudo-aléatoire fourni par un générateur à structure programmée ou éventuellement câblée. Dans les cartes à mémoire à base de microprocesseurs, il n'existe dans l'état de la technique que des générateurs matériels (basé sur des phénomènes physiques) ou des générateurs logiciels basé sur des propriétés mathématiques et déjà utilisés dans le monde informatique traditionnel. Ces deux principes ne peuvent pas garantir l'unicité des nombres générés ce qui présente un inconvénient majeur de sécurité en matière de cryptographie moderne. In microprocessor memory cards which are used in the preceding fields, access to information or to services is strictly controlled. Passwords are used for this. These passwords are more and more often transmitted by encrypting them by a pseudo-random code supplied by a generator with programmed or possibly wired structure. In memory cards based on microprocessors, there exist in the prior art only hardware generators (based on physical phenomena) or software generators based on mathematical properties and already used in the traditional computer world. These two principles cannot guarantee the uniqueness of the numbers generated, which has a major security drawback in modern cryptography.

Si cette solution présente l'avantage de ne pas renseigner les fraudeurs sur les mots de passe utilisés, elle laisse en effet la possibilité à ces derniers de recopier les mots de passe cryptés transmis qui, de par leur défaut d'unicité, peuvent toujours être réutilisés pour donner l'accès aux informations ou services pour lesquels la carte est dédiée. En effet, il suffit alors de renouveler l'expérience de manière à retrouver une valeur déjà utilisée et ainsi frauder le système. If this solution has the advantage of not informing fraudsters about the passwords used, it in fact leaves them able to recopy the encrypted passwords transmitted which, due to their lack of uniqueness, can always be reused to give access to information or services for which the card is dedicated. Indeed, it is then enough to repeat the experience so as to find a value already used and thus defraud the system.

Par ailleurs, la production de nombre aléatoire unique se heurte aux possibilités technologiques de réécriture dans des mémoires non volatiles. Chaque cellule ne peut en effet être réécrite plus de 10.000 fois. Le but de 11 invention est de pallier les inconvénients précités. Furthermore, the production of a unique random number comes up against the technological possibilities of rewriting in non-volatile memories. Each cell cannot be rewritten more than 10,000 times. The object of the invention is to overcome the aforementioned drawbacks.

A cet effet, l'invention a pour objet un procédé pour la génération de nombres pseudo-aléatoires uniques dans une carte à mémoire à microcircuits comportant au moins une mémoire non volatile réinscriptible (EEPROM) couplée à un organe de traitement de données, caractérisé en ce qu'il consiste
- à inscrire dans une zone déterminée de la mémoire, une information de valeur déterminée et non répétitive à chaque génération d'un nombre aléatoire et,
- à convertir cette information en une information ayant la forme d'un nombre pseudo-aléatoire en lui faisant subir dans l'organe de traitement de données un programme de cryptage de type DES.To this end, the subject of the invention is a method for generating unique pseudo-random numbers in a microcircuit memory card comprising at least one rewritable non-volatile memory (EEPROM) coupled to a data processing device, characterized in what it is
- to write in a determined area of the memory, information of determined value and non-repetitive with each generation of a random number and,
- converting this information into information in the form of a pseudo-random number by subjecting it in the data processing unit to a DES-type encryption program.

Elle a également pour objet un dispositif pour la mis en oeuvre du procédé. It also relates to a device for implementing the method.

L'invention a en outre pour principal avantage de permettre, en utilisant un compteur qui comporte un registre à décalage, d'obtenir un nombre de tirages très élevé de nombres aléatoires comparativement au nombre de cycles d'effacement/écriture autorisés dans la mémoire non volatile équipant habituellement les cartes à mémoire. Ainsi, malgré un nombre d'effacement/écriture limité à 10.000 par la technologie actuelle des mémoires non volatiles, encore connues sous la désignation
EEPROM, il est possible, grâce à l'invention, de générer dans le pire des cas 320.000 valeurs différentes et dans le meilleur des cas 21 milliards, en utilisant un espace mémoire EEPROM très réduit de 64 bits.The main advantage of the invention is also to allow, by using a counter which includes a shift register, to obtain a very high number of draws of random numbers compared to the number of erase / write cycles authorized in the non-volatile memory. volatile usually fitted to memory cards. Thus, despite an erase / write number limited to 10,000 by the current technology of non-volatile memories, still known under the designation
EEPROM, it is possible, thanks to the invention, to generate in the worst case 320,000 different values and in the best case 21 billion, using a very reduced EEPROM memory space of 64 bits.

D'autres caractéristiques et avantages de l'invention apparaîtront ci-après à l'aide de la description qui suit faite en regard des dessins annexés qui représentent
Figure 1 : un mode d'exécution du procédé selon l'invention mis sous la forme d'un organigramme.Other characteristics and advantages of the invention will appear below with the aid of the description which follows given with reference to the appended drawings which represent
Figure 1: an embodiment of the method according to the invention in the form of a flowchart.

Figure 2 : un format d'un mot d'information utilisable pour la mise en oeuvre du procédé selon l'invention représenté par l'organigramme de la figure 1. FIG. 2: a format of an information word usable for implementing the method according to the invention represented by the flow diagram of FIG. 1.

Dans sa définition la plus générale, une carte à mémoire pour l'application du procédé selon l'invention comporte, de façon connue et non représentée, un dispositif de mémorisation et un organe de traitement formé normalement par un microprocesseur ou tout dispositif équivalent, couplés l'un à l'autre par un bus de données et d'adresses. Ce bus assure également la liaison du microcircuit de la carte ainsi formée, avec des dispositifs d'écriture et de lecture extérieurs à la carte. Le dispositif de mémorisation comporte généralement une mémoire non volatile, de type EPROM ou
EEPROM, dans laquelle sont enregistrés des microprogrammes nécessaires au fonctionnement de l'organe de traitement et normalement une mémoire vive volatile de type RAM.Cette dernière sert pour la mémorisation temporaire des données et des instructions spécifiques de l'application en cours avec la carte à mémoire. Dans la mémoire non volatile sont rangés, par exemple, d'une part le code secret identifiant le titulaire de la carte, avec éventuellement un programme de chiffrement pour l'obtention d'une signature calculée sur la base du code secret et, d'autre part, des instructions du programme d'utilisation lui-même.In its most general definition, a memory card for the application of the method according to the invention comprises, in a known manner and not shown, a storage device and a processing member normally formed by a microprocessor or any equivalent device, coupled to each other by a data and address bus. This bus also ensures the connection of the microcircuit of the card thus formed, with writing and reading devices external to the card. The storage device generally comprises a non-volatile memory, of EPROM type or
EEPROM, in which microprograms necessary for the functioning of the processing unit are recorded and normally a volatile random access memory of RAM type. This latter is used for the temporary storage of data and specific instructions of the current application with the card. memory. In the non-volatile memory are stored, for example, on the one hand the secret code identifying the card holder, possibly with an encryption program for obtaining a signature calculated on the basis of the secret code and, on the other hand, instructions from the user program itself.

Le procédé selon l'invention dont les étapes 1 à 4 sont représentées schématiquement sur l'organigramme de la figure 1 consiste, chaque fois qu'un nombre aléatoire 10 est à produire, à calculer suivant les étapes 1 et 2, à partir d'une donnée 1 d'information déterminée (de longueur N = 64 bits par exemple), une nouvelle donnée 2 de même longueur N, mais dont la valeur ne pourra plus à nouveau être générée lors d'une requête ultérieure de nouvelle donnée 2. Une fois transformée, la donnée 2 est à l'étape 4 associée à une clef secrète 3 comportant un même nombre de bits, par un algorithme de calcul communément connu sous l'abréviation anglo-saxonne DES de "Data Encryption Standard" et dont une description peut être trouvée dans les brochures des normes FIPS des "Federal Information Processing Standards" des
Etats-Unis d 'Amérique. The method according to the invention whose steps 1 to 4 are shown diagrammatically on the flow diagram of FIG. 1 consists, each time a random number 10 is to be produced, to be calculated according to steps 1 and 2, starting from a given data item of information (of length N = 64 bits for example), a new item of data of the same length N, but the value of which can no longer be generated again during a subsequent request for new item of data 2. A once transformed, the data 2 is in step 4 associated with a secret key 3 comprising the same number of bits, by a calculation algorithm commonly known by the English abbreviation DES of "Data Encryption Standard" and a description of which can be found in the FIPS standards brochures of the Federal Information Processing Standards
United States of America.

La supériorité de l'algorithme d'association DES sur les autres algorithmes d'association est qu'il permet d'obtenir pour chaque clef secrète constante 3 de longueur de N bits, les 2N combinaisons possibles du résultat en garantissant toujours le caractère non prévisible du nombre aléatoire 10, c'est-à-dire, d'obtenir toujours des nombres aléatoires différents 10. The superiority of the DES association algorithm over the other association algorithms is that it makes it possible to obtain for each constant secret key 3 of length of N bits, the 2N possible combinations of the result while always guaranteeing the unpredictable nature. of the random number 10, that is, to always get different random numbers 10.

Ceci est obtenu à partir des 2N combinaisons possibles de la donnée en entrée. Mais le fait que la clé ait une longueur de N bits n'a rien à voir avec le fait qu'il y ait 2N combinaisons différentes sur le résultat. Ceci est lié au fait que la donnée en entrée à une longueur de N bits. Par exemple, les caractéristiques de DES indiquent que pour une clef secrète constante, les 264 combinaisons possibles de la donnée balaient les 264 combinaisons possibles du résultat ce qui garantit, en plus du caractère non prévisible du nombre aléatoire (lié aux performances de DES), la propriété de toujours obtenir des nombres aléatoires différents. Dans l'invention, on disposera ainsi d'une clef secrète constante 3.This is obtained from the 2N possible combinations of the input data. But the fact that the key has a length of N bits has nothing to do with the fact that there are 2N different combinations on the result. This is linked to the fact that the input data has a length of N bits. For example, the characteristics of DES indicate that for a constant secret key, the 264 possible combinations of the data sweep the 264 possible combinations of the result, which guarantees, in addition to the unpredictable nature of the random number (linked to the performance of DES), the property of always obtaining different random numbers. In the invention, there will thus be a constant secret key 3.

Pour obtenir ce résultat, chaque donnée 2 d'information variable est structurée de la façon qui est représentée à la figure 2. Son format comporte trois zones, une première zone 5 de capacité égale par exemple à 16 bits représente les états pris par un premier compteur, une deuxième zone 6 de capacité égale par exemple à 32 bits représente les états d'un registre à décalage et, une troisième zone 7 de capacité égale par exemple à 16 bits représente les états d'un deuxième compteur. Les première et deuxième zones 5 et 6 sont alors situées dans une mémoire non volatile de la carte alors que la zone 7 est située en mémoire vive. Selon l'invention, le contenu des trois zones est considéré comme équivalent à celui qui serait donné par un compteur de N bits qui serait incrémenté à chaque demande de calcul. Cette information est donc prévisible mais est toujours différente des valeurs précédentes. Le stockage en mémoire EEPROM des données des zones 5 et 6 permet de conserver les valeurs de leur contenu lorsque la tension d'alimentation de la carte est supprimée. To obtain this result, each variable information data item 2 is structured as shown in FIG. 2. Its format comprises three areas, a first area 5 of capacity equal for example to 16 bits represents the states taken by a first counter, a second area 6 of capacity equal for example to 32 bits represents the states of a shift register and, a third area 7 of capacity equal for example to 16 bits represents the states of a second counter. The first and second zones 5 and 6 are then located in a non-volatile memory of the card while zone 7 is located in random access memory. According to the invention, the content of the three areas is considered to be equivalent to that which would be given by an N-bit counter which would be incremented at each calculation request. This information is therefore predictable but is always different from the previous values. By storing the data in zones 5 and 6 in EEPROM memory, the values of their contents can be kept when the supply voltage of the card is removed.

Cette solution permet d'obtenir un nombre maximum de nombres aléatoires très supérieur aux 10.000 autorisés par la technologie EEPROM.This solution makes it possible to obtain a maximum number of random numbers much higher than the 10,000 authorized by the EEPROM technology.

La zone 6, qui est organisée en registre à décalage, permet d'obtenir un nombre maximum de nombre aléatoires. Pour cela, à chaque nouveau calcul ou session, un bit de valeur 1 est chargé à la dernière position de poids le plus faible du registre qui est encore à 0. Lorsque 32 demandes de calcul, correspondant à la mise à 1 des 32 bits du registre 6 à décalage, sont effectuées, le calcul suivant remet à zéro le registre à décalage représenté par la zone 6. Lorsque les 32 calculs ont été réalisés, le registre à décalage est à la valeur FFFFFFFFH bien que chaque bit n'ait été écrit qu'une seule fois. On obtient ainsi 32 valeurs différentes en ne consommant qu'une seule écriture pour chaque cellule.A chaque effacement de ce registre de 32 bits, le compteur de 16 bits de la zone 5 en EEPROM sera incrémenté ce qui en définitive permet d'obtenir, 32 X 10000 = 320000 valeurs imprévisibles et non répétitives pour la donnée 2 (sans qu'aucun des bits manipulés en
EEPROM ne soit effacé/écrit plus de 10000 fois). Pour obtenir une plus grande quantité de valeurs (hors pire cas), il suffit d'adjoindre à cette variable de 48 bits en EEPROM, un compteur 7 de 16 bits en RAM qui sera incrémenté à chaque calcul dans une même session.Zone 6, which is organized in shift register, makes it possible to obtain a maximum number of random numbers. For this, at each new calculation or session, a bit of value 1 is loaded at the last least significant position of the register which is still at 0. When 32 calculation requests, corresponding to the setting of the 32 bits of the shift register 6 are carried out, the following calculation resets the shift register represented by zone 6 to zero. When the 32 calculations have been carried out, the shift register is at the value FFFFFFFFH although each bit has not been written only once. 32 different values are thus obtained by consuming only one write for each cell. Each time this 32-bit register is erased, the 16-bit counter in zone 5 in EEPROM will be incremented, which ultimately makes it possible to obtain, 32 X 10000 = 320 000 unpredictable and non-repetitive values for data 2 (without any of the bits handled in
EEPROM is not deleted / written more than 10,000 times). To obtain a greater quantity of values (except worst case), it is enough to add to this variable of 48 bits in EEPROM, a counter 7 of 16 bits in RAM which will be incremented with each calculation in the same session.

La zone 7 située en mémoire RAM permet donc d'augmenter le nombre des valeurs précédentes en augmentant, de manière similaire au compteur matérialisé par la zone 5, le contenu du compteur matérialisé par la zone 7 à chaque nouveau calcul dans une même session. The area 7 located in RAM memory therefore makes it possible to increase the number of the preceding values by increasing, in a similar manner to the counter materialized by the area 5, the content of the counter materialized by the area 7 at each new calculation in the same session.

S'il arrive dans une même session que ce compteur déborde, c'est-à-dire que son contenu dépasse ici 65536 valeurs, on peut modifier le contenu du registre à décalage matérialisé par la zone 6 de la mémoire EEPROM comme si une nouvelle session commençait. Dans ce cas, on met à 1 un autre des bits de ce registre 6.If this counter overflows in the same session, that is to say that its content here exceeds 65536 values, the content of the shift register materialized by zone 6 of the EEPROM memory can be modified as if a new session started. In this case, we put another 1 of this register 6 bits.

Au total, cette disposition permet en concaténant, c'est-à-dire en juxtaposant les 48 bits en EEPROM aux 16 bits situés en mémoire RAM, d'obtenir 320.000 X 65536 soit environ 21 milliards de valeurs imprévisibles et non répétitives par la mise en oeuvre d'un calcul de nombres aléatoires en utilisant l'algorithme DES précédemment cité. In total, this arrangement makes it possible, by concatenating, that is to say by juxtaposing the 48 bits in EEPROM with the 16 bits located in RAM memory, to obtain 320,000 X 65,536 or approximately 21 billion unpredictable and non-repetitive values by setting implementing a calculation of random numbers using the DES algorithm cited above.

Par sécurité, on associe au compteur 5 de 16 bits en EEPROM un compteur-image en EEPROM. Ce compteur-image contient toujours la même valeur que le véritable compteur et est utilisé dans le cas où la valeur du compteur est détruite (arrachage de la carte lorsque le compteur vient d'être effacé pour en modifier la valeur). Il n'est pas nécessaire de prévoir la même chose pour le registre à décalage car celui-ci n'est effacé que pour sa remise à zéro. For security, we associate to the counter 5 of 16 bits in EEPROM an image counter in EEPROM. This image counter always contains the same value as the real counter and is used in the case where the counter value is destroyed (removal of the card when the counter has just been erased to modify its value). It is not necessary to provide the same thing for the shift register because it is only erased for its reset.

La structure du compteur ainsi utilisée (comprenant un registre à décalage) permet d'obtenir un nombre de tirages très élevé comparativement au nombre de cycles d'effacement/écriture (mise à jour) autorisé dans la mémoire non volatile. Ainsi, malgré un nombre d'effacement/ecriture limité à 10000 par la technologie
EEPROM, on arrive à générer dans le pire des cas 320.000 valeurs différentes et dans le meilleur des cas 21 milliards. The structure of the counter thus used (including a shift register) makes it possible to obtain a very high number of prints compared to the number of erase / write (update) cycles authorized in the non-volatile memory. Thus, despite an erasure / write number limited to 10,000 by technology
EEPROM, we manage to generate in the worst case 320,000 different values and in the best case 21 billion.

Claims

1. Method for generating unique pseudo-random numbers in a microcircuit memory card comprising at least one non-volatile rewritable memory (EEPROM) coupled to a data processing device characterized in that it consists,

- to write (1,2) in a determined area of the memory, information of determined value and non-repetitive with each generation of a random number and,

- converting (3,4) this information into information in the form of a pseudo-random number by subjecting it in the data processing unit to a DES-type encryption program.

2. Method according to claim 1, characterized in that the determined value information and not repetitive is written in an EEPROM memory of the card.

3. Method according to claim 2, characterized in that the information of determined and non-repetitive value is structured according to at least two zones, a first zone (6) for systematically writing at least one new bit each time a pseudo-random number is generated by the card, and a second counting area (5) for totaling the number of times the first area has been completely written.

4. Method according to claim 3, characterized in that it consists in structuring the information of determined and non-repetitive value by adding to it a third counting area (7) to total the number of times in a single session, a pseudo-random number has been generated.

5. Method according to claim 4, characterized in that the first and second areas (6, 5) are stored in a non-volatile memory of the card and in that the third area (7) is stored in a volatile memory of the menu.

6. Method according to claim 3, characterized in that a third zone is reserved to serve as an image of the result of the totalized count in the second zone.

7. Device for implementing the method according to any one of claims 1 to 6, characterized in that it is formed by a microcircuit card comprising a processing unit coupled to a non-volatile memory and to a volatile memory .