Parmi les utilisations de nombres aléatoires en sécurité informatique, on peut en citer trois principales. La première est la génération de masques « à usage unique » pour un cryptage par masque XOR (le texte crypté résulte de l'application bit à bit d'un opérateur « OU exclusif » entre le masque et le texte en clair). La seconde est la génération automatique de clés ou de mots de passe en vue de crypter les communications à l'aide d'un algorithme de cryptage donné. La troisième est la génération automatique de défis pour les protocoles dits de défi/réponse.

Les protocoles de défi/réponse ont pour objectif d'authentifier un utilisateur. Cette authentification se fait en général par une communication non protégée. Il faut alors éviter qu'une personne indélicate espionnant cette communication puisse en tirer une quelconque indication qui faciliterait des opérations frauduleuses (pénétration d'un système informatique,

accès à des informations pour lesquelles elle n'est pas habilitée,...) Pour produire des nombres aléatoires, on a recours à des systèmes appelés générateurs aléatoires. Un bon générateur aléatoire pourrait tre réalisé en recueillant les résultats successifs d'un grand nombre de tirages à pile ou face (avec une pièce non biaisée), ou de tirages de dés (avec des dés non biaisés), de nombres à la roulette ou dans n'importe quel jeu de hasard non biaisé. Néanmoins la quantité importante de nombres aléatoires nécessaires pour une application opérationnelle rend totalement irréaliste un recours à ces méthodes de génération de nombres aléatoires « à la main ». De plus, dans les applications liées à la sécurité informatique on a en général tout un réseau d'ordinateurs à sécuriser. Il faut alors disposer de nombres aléatoires sur un grand nombre d'ordinateurs différents et parfois éloignés les uns des autres, ce qui rend indispensable un recours à des générateurs aléatoires autres que les tirages à la main décrits ci-dessus.

D'une façon générale, les résultats d'un générateur aléatoire doivent vérifier divers tests statistiques : équirépartition, répartition des différences successives, test de chi-deux, absence de périodicités (du moins sur des durées raisonnables).

En sécurité informatique (génération automatique de clés,...) il est indispensable que les résultats du générateur aléatoire présentent un caractère d'imprévisibilité parfaite. Il doit tre impossible à un pirate d'obtenir une quelconque information susceptible d'aider à deviner les futurs nombres qui sortiront du générateur (ni mme de penser que les nombres de telle liste ont plus de chances d'tre tirés que les autres).

En particulier le pirate ne doit pouvoir trouver aucune corrélation entre les tirages passés et les tirages futurs. La connaissance de l'historique des précédents tirages ne doit fournir au pirate aucune information utile lui

permettant de penser que tel nombre aura, dans un futur proche, plus de chances d'tre tiré que tel autre.

Il existe de bons générateurs aléatoires basés sur des phénomènes physiques (par exemple amplifiant des bruits de fond sur des circuits électroniques...). Ces générateurs seront appelés par la suite générateurs « physiques ». Ils sont, en général, onéreux et encombrants et, dans un réseau informatique, il est hors de question d'équiper chaque poste de travail (ordinateur relié à un réseau, téléphone mobile...) d'un générateur physique.

Il existe de bons générateurs basés sur des algorithmes mathématiques. Ils sont dits « pseudo-aléatoires ».

La liste de leurs résultats successifs semble parfaitement aléatoire, mais pour qui connaît l'algorithme et l'historique des valeurs précédemment tirées, ils sont en principe totalement prévisibles.

On peut construire un générateur mixte couplant les deux types de générateurs ci-dessus. Le générateur physique assure l'imprévisibilité des résultats et le générateur pseudo- aléatoire assure le respect des tests statistiques que doivent vérifier les nombres successifs issus d'un tel système.

Avant de décrire plus en détail l'invention présentée ici, il convient de faire le point sur les générateurs aléatoires classiquement utilisés, avec leurs qualités et leurs défauts.

De nombreux générateurs pseudo-aléatoires ont été réalisés, et, en particulier, le générateur proposé comme standard par Park et Miller (Communications of the ACM 1988) et primitivement proposé par Lewis, Goodman et Miller en 1969 et, entre autres, implémenté par IBM (par exemple dans le langage APL) dans les années 1970. Ce générateur a été utilisé avec succès dans de nombreuses applications et divers algorithmes ont été proposés pour en accélérer le calcul (entre autres par Schrage en 1979, dans ACM transactions of Mathematical Software).

Dans le générateur de Park et Miller, un « germe » g compris entre 1 et 2^31-2 (a^b désigne le nombre a élevé à la puissance b, c'est-à-dire le produit de b nombres égaux à a) sert à calculer le nombre aléatoire. A chaque utilisation du générateur (donc à chaque fois qu'un nombre aléatoire est fourni) le germe g est multiplié par 7^5 = 16 807 et on en prend le reste modulo le nombre de Mersenne 2^31-1 = 2 147 483 647 (qui est un nombre premier).

Le générateur pseudo-aléatoire de Park et Miller est suffisant pour de nombreuses applications, mais il présente quelques inconvénients parfaitement rédhibitoires pour une utilisation en sécurité informatique.

Le premier inconvénient du générateur pseudo-aléatoire de Park et Miller est qu'il a une périodicité d'environ 2 milliards (exactement 2^31 moins 2). A la fin de chaque cycle, les mmes valeurs aléatoires reviennent dans le mme ordre. Si ces valeurs sont utilisées pour sécuriser un système informatique, celui-ci est à la merci d'une attaque, dite « attaque en force », consistant à tester toutes les valeurs possibles (ce qui est à la portée de tout micro-ordinateur). La sécurité du système est alors équivalente à celle que fourniraient des clés à 31 bits.

Le second inconvénient est que le générateur est parfaitement prévisible. La connaissance de la valeur du germe à un moment donné permet de prévoir parfaitement et avec précision les valeurs futures du générateur. On pourrait imaginer un algorithme sophistiqué permettant de construire des nombres aléatoires à partir du germe sans qu'il soit possible de retrouver la valeur du germe (fonctions « à sens unique », empreintes, fonctions de hachage,...). La connaissance d'un tirage aléatoire particulier ne permettrait alors pas de retrouver le germe, et ne fournirait donc aucune information au pirate. Mais là encore, une attaque en force permettrait à un pirate de retrouver, par essais et erreurs (au maximum de l'ordre de deux milliards d'essais, réalisables rapidement sur

un micro-ordinateur), la ou les valeurs du germe compatibles avec ces tirages, donc de prévoir les tirages ultérieurs.

Remarquons qu'un générateur pseudo-aléatoire réalisé par un algorithme déterministe sur un ordinateur physique est forcément périodique. En effet un tel système est un automate à nombre fini d'états, l' « état » étant défini par l'ensemble des valeurs des mémoires et des registres utilisés par le programme informatique réalisant le générateur.

L'appel au générateur fournira un résultat qui dépend de l'état actuel du système, et mettra le système dans un nouvel état qui dépend uniquement de l'état actuel. Comme il n'y a qu'un nombre fini d'états possibles, le système se retrouvera forcément à un moment futur dans un état dans lequel il s'était déjà trouvé par le passé. Et à partir de ce moment la suite des états successifs (donc des valeurs fournies par le générateur) se reproduit comme par le passé. Et il est clair que la période est au maximum égale au nombre total d'états possibles du système.

Dans le cas du générateur de Park et Miller décrit précédemment, l'état du générateur est défini par la valeur actuelle du germe g.

Si on utilise un générateur pseudo-aléatoire pour construire des clés de cryptage, il est clair que le nombre total de clés possibles ne peut pas tre supérieur au nombre total d'états du système. Si le nombre d'états est de l'ordre de 2^31, la sécurité de l'application informatique est celle d'un chiffrage avec une clé à 31 bits mme si les algorithmes utilisés manipulent des nombres et des clés de 512 ou 1024 bits ou plus.

Par ailleurs certaines corrélations statistiques ont été mises en évidence et ont des effets néfastes lors de l'utilisation du générateur dans des applications de simulation.

Ces corrélations peuvent tre éliminées si on utilise une technique dite de « shuffling ». Cette méthode a pour avantage

annexe d'augmenter la périodicité du générateur et de le rendre donc plus difficilement prévisible.

La méthode de shuffling que nous décrivons ici a été introduite par Bays et Durham (ACM Trans. Math. Software 1976).

Elle est décrite en détail dans le tome 2 du Knuth (Seminumerical Algorithms, Vol 2 de The Art of Computer Programming, 1981). Elle consiste à tirer d'avance un certain nombre de valeurs aléatoires, à les stocker dans un tableau, ci- après appelé le shuffle, tableau dans lequel on va tirer au hasard le prochain nombre aléatoire à utiliser. En résumé, les nombres aléatoires que l'on obtiendra seront les mmes, mais leur ordre d'apparition sera légèrement modifié. Cela revient à écrire chacun des résultats du générateur sur une carte à jouer et à « battre les cartes » (d'où le nom de shuffling) avant utilisation.

Il semble que ce nouveau générateur pseudo-aléatoire soit « parfait » en ce sens qu'il passe avec succès les divers tests statistiques qu'on peut raisonnablement proposer.

Les techniques précédemment décrites ont, jusqu'à présent, donné des résultats jugés en général satisfaisants pour la plupart des applications.

Plutôt que de recourir à un générateur pseudo- aléatoire basé sur un algorithme mathématique, on peut recourir à un générateur aléatoire basé sur un phénomène physique.

Plusieurs techniques ont été utilisées, la plupart basées sur l'amplification d'un bruit de fond dont on extrait des valeurs considérées comme aléatoires. On peut les réaliser sous forme d'une carte hardware enfichable dans un PC et permettant au programmeur d'application de disposer d'une source de nombres réellement aléatoires. On peut aussi, dans un système informatique, analyser des paramètres qui présentent un caractère aléatoire, comme le trafic sur un réseau, l'occupation d'un processeur ou encore le contenu des mémoires ou des disques. Après application de fonctions de type fonction de hachage on arrive à des résultats qui sont d'excellents

candidats pour fournir des nombres aléatoires. Une autre source de phénomènes aléatoires peut consister à capter des émissions de télévision (il existe des dispositifs permettant de le faire sur un micro-ordinateur) et à utiliser les sons et les images digitalisés, après application éventuelle de fonctions de hachage, pour alimenter un générateur aléatoire.

Pour pallier au caractère parfaitement prévisible des nombres générés par un générateur pseudo aléatoire, il est connu de combiner un générateur physique avec un générateur pseudo- aléatoire. Le générateur pseudo-aléatoire assure le caractère aléatoire du résultat (équirépartition des résultats, passage avec succès de tous les tests statistiques souhaités,...). Il est à intervalles fréquents perturbé par un générateur physique assurant le caractère réellement imprévisible et non reproductif des résultats.

Dans les applications liées à la sécurité d'un réseau informatique ou de télécommunications on a besoin de nombres aléatoires d'excellente qualité (imprévisibilité, respect de tests statistiques...) sur un grand nombre d'ordinateurs. Mais il est en général irréaliste d'envisager d'équiper chacun de ces ordinateurs d'un générateur aléatoire physique, ce pour deux principales raisons. D'une part les générateurs physiques sont assez onéreux. Leur coût peut largement dépasser celui d'un micro-ordinateur ce qui rend prohibitive la solution envisagée.

D'autre part, ils sont encombrants et difficiles à installer sur des postes miniaturisés (ordinateurs de poche, téléphones mobiles,...). De toute façon, ils sont bien plus encombrants et bien plus chers que les générateurs pseudo-aléatoires qui sont de petits logiciels ne nécessitent que peu de lignes de code (ou peu de surface de silicium en cas d'implémentation directe sur un processeur spécialisé).

Pour réaliser un bon générateur, destiné à tre installé sur tout ou partie des éléments d'un réseau, il faut respecter plusieurs objectifs. Le premier est d'assurer une périodicité aussi grande que souhaité si le générateur tourne en

mode isolé. Le second est de permettre un couplage facile avec un générateur physique. Le troisième, et le plus important, est d'empcher que la connaissance de l'historique des tirages passés puisse permettre à un pirate d'en déduire des informations utiles sur l'état du générateur (au sens défini plus haut) donc sur les tirages futurs.

L'invention concerne un premier procédé pour la génération de nombres aléatoires caractérisé en ce qu'il comprend les étapes suivantes : - l'étape d'extraire d'une mémoire (ADR) des informations permettant de spécifier, parmi plusieurs générateurs pseudo-aléatoires (PM 1, PM 2,..., PM i,... PM n), lequel d'entre eux sera utilisé lors de la prochaine itération du processus, - l'étape de faire fonctionner le générateur pseudo- aléatoire spécifié à l'étape précédente pour en extraire un nombre ci-après dénommé le nombre RPM, - l'étape d'extraire d'une mémoire (ADR) et du nombre RPM des informations permettant de spécifier une adresse (A) d'un tableau (Sh), - l'étape de lire dans le dit tableau (Sh) le contenu de la dite adresse (A) spécifiée à 1'étape précédente pour fournir les dits nombres aléatoires (RF), - l'étape de stocker à la dite adresse (A) précédemment spécifiée du dit tableau (Sh) une partie des bits du nombre RPM, - l'étape d'utiliser une partie des bits du nombre RPM pour modifier la dite mémoire (ADR).

L'invention concerne aussi un second procédé pour la génération de nombres aléatoires. Le dit second procédé comprend l'étape d'extraire d'un tableau (Sh) une suite de bits pour fournir les dits nombres aléatoires. Le dit tableau (Sh) a été préalablement rempli en mettant en oeuvre les étapes suivantes : l'étape d'extraire d'une mémoire (ADR) des informations permettant de spécifier, parmi plusieurs

générateurs pseudo-aléatoires (PM 1, PM 2,..., PM i,... PM n), lequel d'entre eux sera utilisé lors de la prochaine itération du procédé, étape de faire fonctionner le générateur pseudo- aléatoire spécifié à l'étape précédente pour en extraire un nombre ci-après dénommé le nombre RPM, - l'étape d'extraire d'une mémoire (ADR) et du nombre RPM des informations permettant de spécifier une adresse (A) d'un tableau (Sh), - l'étape de stocker à la dite adresse (A) du dit tableau (Sh) une partie des bits du nombre RPM, - l'étape d'utiliser une partie des bits du nombre RPM pour modifier la dite mémoire (ADR), - l'étape de réitérer l'ensemble des étapes ci-dessus un nombre de fois suffisant pour modifier, lors de la première utilisation toutes les entrées du dit tableau (Sh), et lors des utilisations suivantes, les seules entrées utilisées pour fournir les dits nombres aléatoires.

Les procédés de génération de nombres aléatoires décrits ci-dessus peuvent tre complétés par une étape consistant à utiliser des informations provenant d'une source extérieure pour modifier l'état des dits générateurs pseudo- aléatoires (PM 1, PM 2,..., PM i,... PM n).

Les procédés de génération de nombres aléatoires décrits ci-dessus peuvent tre complétés par une étape consistant à utiliser des informations provenant d'une source extérieure pour modifier, à l'aide d'un OU exclusif bit à bit (opérateur XOR) la dite mémoire (ADR).

Les procédés de génération de nombres aléatoires décrits ci-dessus peuvent tre complétés par une étape consistant à utiliser des informations provenant d'une source extérieure pour modifier, à l'aide d'un OU exclusif bit à bit (opérateur XOR) le dit tableau (Sh).

Les procédés de génération de nombres aléatoires décrits ci-dessus peuvent tre utilisés pour mettre en oeuvre un

procédé de cryptographie. Dans ce cas, le procédé selon l'invention comprend en outre l'étape d'utiliser les dits nombres aléatoires successifs pour crypter ou décrypter un message en appliquant un opérateur XOR bit à bit entre les bits des dits nombres et les bits de certaines parties dudit message.

L'invention concerne aussi un dispositif pour générer des nombres aléatoires. Le dispositif selon l'invention comprend : plusieurs générateurs pseudo-aléatoires (PM 1, PM 2,..., PM i,..., PM n), destinés à tre utilisés à tour de rôle, une zone mémoire (Sh) destinée à stocker des nombres aléatoires issus des dits générateurs pseudo-aléatoires (PM 1, PM 2,..., PM i,..., PM n), et - une mémoire (ADR) destinée à fournir les informations permettant de spécifier lequel des dits générateurs pseudo-aléatoires (PM 1, PM 2,..., PM i,..., PM n) sera utilisé et à quelle adresse de la dite zone mémoire (Sh) sera stocké le résultat fourni par le dit générateur pseudo-aléatoire ainsi spécifié.

L'invention concerne aussi un dispositif pour générer des nombres aléatoires comprenant en outre, une unité de calcul permettant de réaliser des opérations XOR bit à bit entre les bits des nombres aléatoires générés et des bits issus d'informations provenant d'une source extérieure. Un tel dispositif peut tre utilisé à des fins de cryptographie ainsi que cela a été décrit ci-après.

L'invention consiste donc à combiner plusieurs générateurs pseudo-aléatoires classiques qui fonctionneront indépendamment l'un de l'autre. Ces générateurs seront appelés les générateurs « élémentaires ». Lors de chaque tirage aléatoire, on choisit « aléatoirement » celui des générateurs élémentaires à utiliser pour le présent tirage. Pour éviter que le tirage donne une information utile sur l'état du générateur, on ne stockera qu'une partie des bits tirés. Dans l'hypothèse où

les générateurs aléatoires sont des générateurs de Park et Miller (fournissant donc à 31 bits), on stockera par exemple 8 bits. Avant de fournir le résultat final, les aléas ainsi obtenus sont permutés par une méthode classique de shuffling similaire à la méthode de shuffling décrite auparavant.

Pour générer une longue suite de bits aléatoires, on pourra concaténer des valeurs successives produites par le générateur décrit ci-dessus. Par exemple, dans le cas où le shuffle contient des nombres à 8 bits (cas du mode de réalisation décrit ci-avant), si on souhaite générer des chaînes aléatoires de 512 bits ou 1024 bits, il faudra attendre 64 ou 128 itérations successives.

Néanmoins, on peut, sans inconvénient, considérer que l'ensemble du shuffle est une séquence aléatoire. Cela permet de définir le second précédé qui consiste donc à tirer d'un coup des chaînes aléatoires longues. La seule contrainte à respecter d'assurer qu'avant un nouveau tirage, le générateur aura fait un nombre suffisant d'itérations pour assurer que le shuffle a été reconstitué, c'est-à-dire rempli avec de nouvelles valeurs aléatoires. Bien entendu, on pourra augmenter la taille du shuffle pour l'adapter à la taille des suites de bits.

Si on souhaite combiner un générateur pseudo-aléatoire tel que ceux que nous venons de décrire avec un générateur aléatoire physique, ou, plus généralement, avec des informations de provenance diverses et considérées comme aléatoires, il suffira d'adapter les procédés décrits ci-dessus de façon à permettre la modification de l'état du générateur aléatoire.

Cela permet de définir des procédés pour la génération de nombres aléatoires similaires à ce qui a été décrit auparavant, mais caractérisés en ce qu'ils comprennent une ou plusieurs des étapes ci-après, ces étapes pouvant tre effectuées dans un ordre quelconque -L'étape d'utiliser des informations provenant d'une source extérieure pour modifier l'état des générateurs aléatoires élémentaires définis précédemment.

-L'étape d'utiliser des informations provenant d'une source extérieure pour modifier, les mémoires utilisées pour choisir quel générateur élémentaire sera utilisé et à quelle adresse sera stocké le résultat.

- L'étape d'utiliser des informations provenant d'une source extérieure pour modifier, le tableau dans lequel on vient stocker et lire les nombres aléatoires.

Dans un mode particulier de réalisation d'un tel procédé, on pourra installer sur tout ou partie des ordinateurs d'un réseau informatique des générateurs pseudo-aléatoires du type décrit précédemment, et on installe sur un seul poste, ou sur un petit nombre de postes, un générateur considéré comme vraiment aléatoire (par exemple basé sur un phénomène physique).

Ce générateur viendra, à intervalles très fréquents, perturber les générateurs pseudo-aléatoires installés sur les divers postes du réseau. Cette perturbation se fait par l'envoi de nombres aléatoires qui viennent modifier l'état des générateurs pseudo-aléatoires élémentaires.

Une telle implantation permet de disposer, sur tous les ordinateurs où c'est souhaitable, de nombres aléatoires de mme qualité que si on y avait installé un générateur physique, tout en n'utilisant, pour l'ensemble du réseau, qu'un seul générateur aléatoire physique (ou un petit nombre). On réalise ainsi des économies importantes.

La communication des nombres aléatoires peut se faire de manière cryptée, et à des intervalles non réguliers, l'écart entre deux envois successifs étant lui-mme déterminé à partir de nombres aléatoires.

Les procédés décrits précédemment fonctionnent à l'aide d'un dispositif matériel similaire dans chacun des cas décrits.

Dans un mode particulier de réalisation présenté ici les générateurs élémentaires sont des générateurs de Park et Miller (tels que décrits ci-avant). Leur nombre, n, dépend de l'application. Si celle-ci nécessite des clés ou des

défis/réponses de l'ordre de 1024 bits, on pourra par exemple choisir n = 32. D'une façon générale, pour des raisons de commodité dtimplémentation, il est préférable que n soit une puissance de 2.

Pour mieux faire comprendre l'invention, on va en décrire maintenant, à titre d'exemple purement illustrait et non limitatif, plusieurs modes de réalisation en se référant aux figures qui représentent : - figure 1 : un schéma fonctionnel du procédé et du dispositif pour générer des nombres aléatoires, - figure 2 : un schéma fonctionnel du procédé et du dispositif utilisant les nombres aléatoires ainsi générés pour des applications cryptographiques.

La figure 1 représente le dispositif physique qui est utilisé pour réaliser le générateur de nombres aléatoires objet de la présente invention. Dans cette figure, PM 1, PM 2,....

PM i,..., PM n représentent n générateurs pseudo-aléatoires élémentaires. Un aiguillage, noté S1 (pour « Switch » 1) spécifie quel est le générateur élémentaire à utiliser actuellement (dans le cas particulier de la figure, c'est le générateur i).

Sur la figure, RPM désigne la mémoire dans laquelle est provisoirement stocké le nombre fourni par le générateur élémentaire spécifié par l'aiguillage S1. Le contenu de cette mémoire sera également désigné dénommé RPM. Le tableau qui sert de Shuffle, noté Sh, est composé d'un certain nombre d'entrées.

Un aiguillage, noté S2 (pour « Switch » 2) sur la figure 1, spécifie quelle est l'entrée du Shuffle actuellement en cours d'utilisation. Cette entrée est notée A sur la figure.

Le nombre qui était précédemment stocké à cette entrée A est le résultat final du procédé de génération de nombres aléatoires et est envoyé sur un organe de sortie noté RF. Dans le texte, RF désigne aussi le contenu de cet organe de sortie, c'est-à-dire le résultat final du procédé de génération d'un nombre aléatoire.

Un registre noté ADR sur la Figure 1 contient les informations permettant de positionner les aiguillages S1 et S2.

Un mode particulier de réalisation de l'invention peut tre obtenu en procédant comme suit. On dispose en parallèle n générateurs élémentaires PM 1, PM 2,..., PM i,..., PM n de type Park et Miller, tels que décrits précédemment.

Le résultat fourni par un générateur de Park et Miller est la valeur courante du germe g de ce générateur, c'est-à- dire un nombre entre 0 et 2^31 moins 2. Ce nombre est stocké sur 31 bits. Toutes les configurations de 31 bits sont possibles et équiprobables sauf les deux configurations où les 31 bits sont tous à 0 ou bien tous à 1, ce qui ne peut jamais se produire.

Un aiguillage S1 spécifie quel est le générateur élémentaire à utiliser actuellement. Le nombre fourni par le générateur élémentaire spécifié par S1 est stocké dans une mémoire RPM.

On dispose par ailleurs d'un tableau Sh de 512 entrées, le shuffle, et un aiguillage S2 spécifie l'entrée A du Shuffle qui est l'entrée actuellement en cours d'utilisation.

Une partie des bits de la mémoire RPM sont alors recopiés en vue d'tre stockés dans l'entrée A du shuffle définie par l'aiguillage S2. Dans le mode particulier de réalisation présenté ici, il s'agit de 8 bits situés parmi les bits du milieu. (On évite les bits de poids fort et les bits de poids faible).

Un registre ADR contient les informations permettant de positionner les aiguillages S1 et S2. Dans le mode particulier de réalisation présenté ici, ADR se compose de 32 bits, dont 5 sont utilisés pour positionner l'aiguillage S1 (32 valeurs possibles correspondant aux 32 générateurs élémentaires utilisés) et 9 pour positionner l'aiguillage S2 (512 valeurs possibles correspondant aux 512 entrées dans le Shuffle). Ces 5 bits et ces 9 bits forment deux ensembles disjoints, c'est-à- dire qu'aucun bit du registre ADR n'est utilisé simultanément pour le positionnement des deux aiguillages. Le registre ADR

joue en quelque sorte un rôle de chef d'orchestre pour le positionnement des aiguillages S1 et S2. En vue de conserver un caractère apparemment aléatoire à ces positionnements, le registre ADR est régulièrement modifié de la façon suivante : Les bits de RPM qui n'ont pas été utilisés pour alimenter le Shuffle (soit 23 bits sur les 31 bits initiaux) serviront à modifier ADR. Cette modification de ADR se fait en deux temps. Dans un premier temps, 23 bits de ADR sont modifiés par un « OU exclusif bit à bit » (opérateur XOR) avec les 23 bits issus de RPM (cela consiste à retourner le bit de ADR lorsque le bit correspondant de RPM est à 1 et à ne rien faire lorsque le bit correspondant de RPM est à zéro). Dans un second temps, on fait une permutation circulaire d'un cran sur les bits de ADR.

Le choix des 5 bits et des 9 bits de ADR destinés à positionner les aiguillages S1 et S2, le choix des 23 bits d'ADR qui seront perturbés par des bits provenant de RPM, le choix des 23 bits de RPM envoyés vers ADR et des 8 envoyés dans le shuffle sont des détails d'implémentation qui ne changent rien à la qualité du générateur.

Dans d'autres modes de réalisation, on pourra remplacer les générateurs de Park et Miller par n'importe quel générateur pseudo-aléatoire ou aléatoire. Il faudra simplement s'assurer que la taille de la mémoire RPM est adaptée à la taille des résultats fournis par ces générateurs. On pourra modifier le nombres de bits de RPM destinés à tre envoyés dans le shuffle et ceux destinés à perturber le registre ADR. On pourra aussi modifier le nombre de générateurs de Park et Miller utilisés ainsi que le nombre d'entrées dans le shuffle (dans le mode de réalisation précédent ces nombres sont respectivement 32 et 512). Pour des questions de facilités d'implémentation, il vaut mieux que ces nombres soient des puissances de 2. De ces nombres, on peut déduire le nombres de bits nécessaires pour positionner les aiguillages S1 et S2 (ici respectivement 5 et 9). On pourra aussi modifier le nombre de bits du registre ADR,

en veillant toutefois à ce qu'il reste toujours significativement supérieur à la somme des nombres de bits nécessaires à positionner les aiguillages S1 et S2 (dans le mode de réalisation précédemment décrit, ce nombre de bits était 32, ce qui est significativement supérieur à 5+9).

Maintenant que nous avions décrit un mode particulier de réalisation de dispositif objet de la présente invention, détaillons, à titre d'exemple purement illustratif et non limitatif comment se déroule, sur ce mode particulier de réalisation le procédé de génération d'un nombre aléatoire.

On appellera « cycle » du générateur pseudo-aléatoire l'ensemble des opérations nécessaires à la fourniture d'un nombre aléatoire.

Au début d'un cycle, on extrait du registre ADR les bits nécessaires au positionnement des aiguillages S1 et S2 (5 et 9 dans le mode particulier de réalisation décrit ici) et on positionne les dits aiguillages.

On extrait alors un nombre aléatoire du générateur élémentaire spécifié par l'aiguillage S1. Dans le mode particulier de réalisation décrit ici, ce générateur est de type Park et Miller ; il consiste en pratique en une mémoire de 31 bits et l'opération de fourniture d'un nombre aléatoire consiste simplement à multiplier par 7^5 modulo 2^31-1 le contenu de cette mémoire, et c'est ce nouveau contenu qui représente le résultat recherché. Le contenu de cette mémoire de 31 bits est alors envoyé dans RPM, et est séparé en deux parties, d'une part les bits destinés à alimenter le shuffle sh et d'autre part ceux destinés à perturber ADR.

On extrait du shuffle le nombre stocké à l'entrée spécifiée par l'aiguillage S2. Ce nombre est exporté dans l'organe de sortie RF et sera le nombre aléatoire fourni lors de ce cycle. A la place qu'il occupait dans le shuffle, on recopie les bits de RPM destinés à alimenter le shuffle (8 bits dans le mode particulier de réalisation décrit ici).

On utilise les bits de RPM destinés à perturber ADR pour réaliser cette perturbation. Cette dernière se fait en deux temps, d'abord l'application d'un OU exclusif bit à bit (opérateur XOR) pour perturber une partie des bits de ADR, puis une permutation circulaire. ADR contient maintenant la valeur qui sera utilisée au cycle suivant.

Cette opération termine le cycle, et le générateur pseudo-aléatoire est prt à entamer le cycle suivant.

Dans un autre mode de réalisation, les bits servant à positionner l'aiguillage S2 peuvent de plus tre perturbés (en appliquant un OU exclusif bit à bit c'est-à-dire l'opérateur XOR) par une partie des bits provenant de RPM. Les bits de RPM sont alors séparés en trois familles, en principe disjointes, ceux servant à alimenter le shuffle et ceux servant à perturber ADR comme précédemment, mais aussi une troisième famille qui servira à modifier l'aiguillage S2.

L'algorithme présenté ici est très facile à programmer ou à implémenter sur un circuit spécialisé (ASIC c'est-à-dire puce développée spécifiquement). Dans le second cas, il n'occupe qu'une surface minime dans le silicium. Les implémentations peuvent différer par le nombre de générateurs élémentaires PM utilisés, le nombre de bits extraits d'un PM à chaque itération et la taille du shuffle.

On s'assurera en particulier que le nombre de générateurs élémentaires est adapté à l'application envisagée.

Le nombre de générateurs utilisés (par exemple 32 dans le mode de réalisation présenté ici) multiplié par le nombre de bits définissant l'état d'un générateur (31 dans le cas d'un générateur de Park et Miller) doit tre de l'ordre de grandeur de la taille des clés à générer (dans le mode de réalisation présenté ici, il s'agit d'un millier de bits).

La taille du shuffle doit tre plus grande que le nombre de valeurs différentes prises par un élément du shuffle.

Dans le mode de réalisation présenté précédemment, le shuffle

stocke des nombres à 8 bits (256 valeurs possibles) et a 512 entrées.

Au début d'un cycle, le générateur pseudo-aléatoire est dans un certain état, spécifié d'une part par le contenu du shuffle et du registre ADR et d'autre part par l'état des générateurs élémentaires formant le système. Dans le cas où ces générateurs élémentaires sont des générateurs de Park et Miller, leur état est simplement donné par la valeur du germe g (31 bits). Dans le mode particulier de réalisation décrit ici, (32 générateurs élémentaires) il faut donc 32 fois 31 donc près de 1000 bits pour spécifier uniquement l'état de ces générateurs.

Compte tenu d'une part de la présence du shuffle et du registre ADR et d'autre part du fait que seul un petit nombre de bits issus des générateurs élémentaires est utilisé pour le résultat final, on peut montrer qu'un éventuel pirate connaissant tout l'historique des tirages aléatoires ne peut en extraire aucune information pertinente permettant de retrouver l'état des générateurs élémentaires. Son seul mode d'attaque est une méthode par tâtonnements, donc par essais et erreurs, en essayant diverses valeurs pour les états des générateurs élémentaires. Mais, à moins que le système ait démarré d'un état initial connu, il n'y a qu'une probabilité extrmement faible qu'un pirate puisse retrouver l'état des générateurs élémentaires en un temps inférieur à l'âge de l'univers.

La façon exacte dont on décide, d'une part quel générateur élémentaire, et d'autre part quelle entrée de shuffle, seront utilisés à l'itération suivante est un détail d'implémentation. Le principe général étant que cela est géré par une mémoire ou un registre qui est, à chaque itération, perturbé par les bits non retenus parmi les bits aléatoires générés par le générateur aléatoire précédemment utilisé.

Le système proposé est particulièrement adapté à une architecture dans laquelle un générateur aléatoire local est régulièrement perturbé par des aléas provenant d'une source extérieure, générateur aléatoire physique, et/ou information

envoyée par un serveur central. Les bits aléatoires arrivant de l'extérieur seront simplement combinés par un « OU exclusif bit à bit » (opérateur XOR) avec les mémoires contenant l'état des générateurs élémentaires (les germes dans de cas de générateurs de Park et Miller), avec le contenu du shuffle et avec le registre ADR spécifiant quel générateur pseudo-aléatoire et quelle entrée de shuffle on utilise.

Lors de l'initialisation du générateur aléatoire, les générateurs élémentaires sont initialisés, de préférence avec des valeurs aléatoires générées précédemment par le système. Il faudra faire tourner le générateur à vide le temps de remplir le shuffle. On prévoira un nombre d'itérations égal à plusieurs fois la taille du shuffle pour assurer un fonctionnement parfait du générateur pseudo-aléatoire.

En fonction de l'application utilisant le générateur pseudo-aléatoire, on décidera à certains moments de modifier l'état du générateur (donc l'état des générateurs élémentaires qui le composent, ainsi que les contenus du registre ADR et du shuffle) en faisant un « OU exclusif bit à bit » (opérateur XOR) avec des valeurs de diverses provenances, et en particulier des valeurs provenant d'un'serveur central et transmises par voie cryptée.

Dans un autre mode de fonctionnement, on pourra aussi réinitialiser le générateur en imposant son état (donc en imposant une valeur à l'état des générateurs élémentaires qui le composent, ainsi qu'aux contenus du registre ADR et du shuffle).

Chaque fois que le générateur est réinitialisé dans un mme état, la séquence des nombres aléatoires successifs qu'il fournira par la suite sera identique.

Dans certains modes de réalisation, le générateur aléatoire pourra tourner en permanence en tâche de fond. En cas d'implémentation logicielle, c'est un programme résident en mémoire qui s'exécute lorsque l'unité centrale est inoccupée. En cas d'implémentation matérielle, par exemple sur un ASIC, le générateur est une zone spécifique de l'ASIC qui tourne en

permanence. Les résultats successifs sont effacés au fur et à mesure que de nouvelles valeurs sont écrites dans le shuffle.

On va maintenant décrire en se référant à la figure 2 comment le générateur aléatoire objet de cette invention peut tre utilisé pour réaliser un système de cryptographie inviolable. Rappelons tout d'abord que si l'état du générateur aléatoire décrit ici est initialisé ou réinitialisé à partir d'une séquence de bits fournie par l'utilisateur, la suite des résultats successifs qu'il fournit est absolument déterminée.

Cependant cette suite présente un caractère aléatoire et imprévisible : en effet considérons un éventuel pirate qui ne connaît pas l'état actuel du générateur ni la façon dont le générateur avait été initialisé ; ce pirate sera incapable d'avoir une quelconque indication sur les valeurs susceptibles d'tre fournies à l'avenir par le générateur, et ce, mme s'il connaît toutes les valeurs qui ont été fournies depuis l'initialisation ou la réinitialisation.

Compte tenu de ces propriétés, le générateur peut servir de support à un système de cryptographie extrmement puissant. Il nécessite simplement que l'expéditeur et le destinateur possèdent le mme générateur aléatoire et se soient mis d'accord sur une clé de cryptage commune.

La clé de cryptage servira à initialiser ou réinitialiser le générateur, soit directement, en utilisant des parties de la clé comme valeurs à imposer aux générateurs élémentaires et aux contenus du registre ADR et du shuffle, soit en générant ces valeurs à partir de la clé par un processus défini à l'avance.

Lors du cryptage, on réinitialise le générateur aléatoire à l'aide de ladite clé de cryptage. Le message à crypter est considéré comme une suite de bits. On utilise le générateur aléatoire, initialisé comme ci-dessus, pour générer une suite de bits de mme longueur que le message. Cette nouvelle suite de bits sera appelée le masque. Le message crypté s'obtint en combinant bit à bit le message en clair avec le

masque à l'aide de l'opérateur XOR (OU exclusif bit à bit) : cela revient, lorsque le bit du masque est à 1, à retourner l'état du bit correspondant du message en clair pour obtenir le bit message crypté (0 donne 1 et 1 donne 0), et à ce que le bit du message crypté soit égal au bit du message correspondant en clair lorsque le bit correspondant du masque est à 0.

Lors du décryptage, on réinitialisera le générateur de la mme façon que lors du cryptage, avec la mme clé de cryptage, ce qui aura pour effet de le mettre dans le mme état qu'au début de 1"opération de cryptage. On génère alors un masque de mme longueur que celle du message à décrypter. Compte tenu de la réinitialisation du générateur, on sait que ce masque est identique à celui qui avait été utilisée pour le cryptage.

On décrypte le message en appliquant alors l'opérateur XOR bit à bit exactement de la mme façon que lors de l'opération de cryptage.

La figure 2 schématise le système de cryptage/décryptage que nous venons de décrire. Dans cette figure C désigne le message en clair (suite de bits) et D le message crypté (suite de bits de mme longueur), G désigne le générateur aléatoire, K la clé de cryptage, M le masque (suite de bits de mme longueur que les messages) fourni par le générateur après que celui-ci aura été initialisé par la clé K.

Le symbole @ (symbole plus de l'addition, inscrit dans un cercle) symbolise l'opérateur XOR bit à bit.