FR2859290A1 - Generateur de nombres pseudoaleatoires - Google Patents

Abstract

Un générateur de nombres pseudoaléatoires comporte un premier registre (101) à décalage élémentaire ayant une particularité de rétroaction non linéaire, et un deuxième registre (102) à décalage et des moyens (120) de combinaison pour combiner des signaux à une sortie du premier registre (101) à décalage élémentaire et du deuxième registre (102) à décalage élémentaire pour obtenir un signal combiné représentant un nombre pseudoaléatoire. La combinaison de registres à décalage élémentaire non linéaire individuels permet une mise en oeuvre sûre et souple de générateur de nombres aléatoires, dont la séquence de sortie comporte une complexité linéaire élevée et une longueur de période grande.

Description

GÉNÉRATEUR DE NOMBRES PSEUDOALÉATOIRES

La présente invention se rapporte à des générateurs de nombres pseudoaléatoires et en particulier à des générateurs de nombres pseudoaléatoires qui sont fondés sur des registres à décalage à rétroaction.

Un générateur de nombres aléatoires bien connu de ce genre est illustré à la Figure 12. Le générateur de nombres pseudoaléatoires de la Figure 12, qui est également appelé un registre à décalage à rétroaction linéaire, comporte une pluralité d'éléments 51, 52, 53, 54 à mémoire qui à la io Figure 12 sont numérotés de 0 à n. Les cellules de mémoire peuvent être initialisées à une valeur initiale par l'intermédiaire de moyens 55 d'initialisation. Les cellules 51 à 54 de mémoire forment ensemble des moyens à action directe, tandis que le registre à décalage linéaire formé par les cellules 51 à 54 de mémoire est alimenté en retour par des moyens à rétroaction couplés entre une sortie 56 du circuit et la cellule n de mémoire. En particulier, les moyens de rétroaction comportent un ou plusieurs moyens 57, 58 de combinaison qui sont alimentés par des branches 59a, 59b, 59c de rétroaction respectives comme il est illustré à titre d'exemple à la Figure 12. La valeur initiale des derniers moyens 58 de combinaison est envoyée dans la cellule n de mémoire qui, à la Figure 12, est désignée par la référence numérique 54.

Le registre à décalage à rétroaction linéaire représenté à la Figure 12 est entraîné par une horloge de sorte que l'occupant des cellules de mémoire est décalé d'une étape, en se référant à la Figure 12, vers la gauche à chaque cycle d'horloge, de sorte que dans chaque cycle d'horloge l'état stocké dans les moyens 51 de mémoire est émis en sortie sous la forme d'un nombre, tandis que simultanément la valeur est envoyée dans la première unité n de mémoire de la séquence d'unités de mémoire à la sortie des derniers moyens 58 de combinaison. Le registre à décalage à rétroaction linéaire illustré à la Figure 12 fournit ainsi une séquence de nombres en réponse à une séquence de cycles d'horloge. La séquence de nombres obtenue à la sortie 56 est fonction de l'état initial réalisé par les moyens 55 d'initialisation avant le fonctionnement du registre à décalage. La valeur initiale entrée par les moyens 55 d'initialisation est également appelée une semence, et c'est pourquoi des agencements de ce genre illustrés à la Figure 12 sont également appelés des générateurs de semence.

La séquence de nombres obtenue à la sortie 56 est appelée une séquence pseudoaléatoire de nombres puisque les nombres semblent se suivre les uns les autres d'une manière qui semble aléatoire, mais dans l'ensemble sont périodiques bien que la durée de la période soit grande. En outre, la séquence de nombres peut être répétée de manière non ambiguë et ainsi avoir un caractère pseudoaléatoire lorsque la valeur d'initialisation fournie aux éléments de mémoire par les moyens 55 d'initialisation est connue. Des registres à décalage de ce genre sont par exemple utilisés comme générateur de suite de clé pour fournir une suite de clés de io codage/décodage fonction d'une valeur d'initialisation spéciale (semence).

Des registres à décalage de ce genre illustrés à la Figure 12 ont l'inconvénient d'avoir une petite complexité linéaire. Ainsi, 2 n bits de la séquence de sortie sont suffisants dans un LFSR à n bit (LFSR pour linear feedback shift register ou registre à décalage à rétroaction linéaire) pour calculer la séquence complète. L'avantage des LFSR bien connus de ce genre illustrés à la Figure 12, cependant, est qu'ils n'ont pas besoin de coûts de matériel très élevés.

En outre, il y a des LFSR qui sont synchronisés de manière irrégulière. II supporte des coûts matériels quelque peu accrus avec une période sensiblement plus petite. La complexité linéaire cependant peut être accrue de manière considérable. Un inconvénient de dispositifs synchronisés de manière irrégulière de ce genre cependant est le fait que la séquence de sortie peut en principe être établie au moyen de mesure du courant dans un SPA (SPA pour simple power analysis ou analyse de puissance simple) dû à la synchronisation irrégulière. En utilisant les dispositifs à registre à décalage comme parties de générateurs de clé qui produisent des données à maintenir secrètes de manière inhérente, c'est-àdire des données de clé, il est d'importance cruciale pour celles-ci d'être sûre vis-à-vis de tout type d'attaque cryptographique.

D'autre part, il existe l'exigence dans des dispositifs de ce genre, en particulier lorsqu'ils doivent être reçus sur des cartes à puce, que les coûts matériels soient bas. Dit différemment, l'aire de puce que les dispositifs de ce genre occupent doit être aussi petite que possible. La raison en est que dans la fabrication de semi-conducteurs, l'aire de puce d'un dispositif complet à la fin détermine le prix et ainsi la marge ou profit du fabricant de puces. En outre, une spécification, notamment dans les cartes à puce, est généralement telle qu'un client règle l'aire maximale d'une puce de processeur, en millimètres carrés, sur laquelle différentes fonctionnalités doivent être reçues. Il est ainsi pour tâche du fabricant de circuit de répartir cette aire qui a de la valeur pour les composants individuels. En ce qui concerne les algorithmes cryptographiques qui deviennent de plus en plus complexes au cours du temps, des efforts des fabricants de puces sont dirigés au fait que la puce ait la quantité de mémoire la plus grande possible pour être capable de calculer même des algorithmes exigeant beaucoup de mémoire de travail en un temps acceptable. L'aire de puce pour des générateurs de clé et d'autres io composants de ce genre doit ainsi être maintenue aussi petite que possible afin d'être capable de recevoir une quantité de mémoire plus grande sur l'aire de puce donnée.

L'exigence générale pour des générateurs de clé ou des dispositifs de clé pour produire une séquence pseudoaléatoire de nombres est ainsi d'être sûrs d'une part et de nécessiter aussi peu de place que possible d'autre part, c'est-à-dire de supporter les coûts de matériel les plus bas possibles.

En principe, des registres à décalage linéaires ont différentes applications dans des théories de codage, de cryptographie et d'autres domaines en électrotechnologie. Les séquences de sortie de registres à décalage linéaire ont des particularités structurelles utiles qui peuvent être divisées en des particularités algébriques et des particularités de répartition.

On sait que la séquence de sortie d'un registre à décalage linéaire à n étapes, comme cela a été décrit, est périodique. La longueur de la période peut être assez grande et est souvent exponentielle par rapport à n, c'est-à- dire le nombre d'éléments de mémoire. En particulier, la longueur de la période est 2n-1 lorsque le registre à décalage est fondé sur un polynôme à rétroaction primitive.

La complexité linéaire d'une séquence de ce genre cependant est égale au plus à n. La complexité linéaire d'une séquence périodique, par définition, est égale au nombre de cellules du registre à décalage le plus petit possible que la séquence considérée peut produire.

En raison de ce fait, il peut être montré que, comme il a été décrit, 2 n expressions successives de la séquence sont suffisantes pour prédire toutes les expressions restantes de la séquence. En outre, il y a un algorithme efficace, que l'on appelle l'algorithme de Berlekamp Massey, pour calculer les paramètres exigés pour obtenir la séquence complète. Pour cette raison, des séquences de registres à décalage linéaire, malgré leurs périodes potentiellement grandes et leurs particularités de répartition statistiquement bonnes, ne sont pas directement adaptables comme séquences de clé dans ce que l'on appelle des chiffreurs de suite. En outre, il y a d'autres applications dans lesquelles la complexité linéaire comparativement petite d'une séquence produite par un registre à décalage linéaire est vue comme un inconvénient.

Classiquement, des registres à décalage linéaire sont décrits par leur polynôme caractéristique. Le degré du polynôme caractéristique est égal io au nombre d'éléments à retard, qui sont généralement mis en oeuvre sous la forme de bascules flip-flop, du registre à décalage considéré. Les exposants des termes de f(x), à l'exception du terme d'attaque, correspondent aux éléments à retard du registre à décalage contribuant à la rétroaction. Le registre à décalage linéaire illustré à la Figure 12 aurait ainsi un polynôme caractéristique du genre suivant: f(x) = xn+1 + xn + ... + x + 1 Si des registres à décalage linéaire de ce genre, comme illustré à titre d'exemple à la Figure 12, sont chargés avec un état d'initialisation par les moyens 55 d'initialisation, dans lequel cet état est également appelé le vecteur d'état initial, ils vont émettre en sortie classiquement une séquence périodique qui, en fonction de la mise en oeuvre, a une certaine prépériode et une période suivante. Des registres à décalage linéaire seront toujours périodiques. Les applications technologiques ont toujours recherché une séquence de sortie qui a à la fois une grande longueur de période et une complexité linéaire élevée.

En principe, des générateurs de nombres pseudoaléatoires, comme cela a été par exemple illustré en se reportant à la Figure 12, sont nécessaires pour différents buts, c'est-à-dire pour des buts de simulation, pour effectuer des échantillonnages aléatoires dans des applications statistiques, pour tester des programmes d'ordinateur, pour chiffrer de manière séquentielle pour produire une séquence de clé, pour des algorithmes probabilistiques, dans les mathématiques numériques, en particulier pour une intégration numérique, pour produire des clés dans la cryptologie ou pour des procédés de Monte Carlo. En particulier, des générateurs de nombres pseudoaléatoires sont utilisés commercialement pour des circuits intégrés sûrs, à l'intérieur de générateurs de nombres aléatoires classiquement intégrés, à l'intérieur de cryptomodules ou pour des applications de télé payante ou même dans des cartes à puce pour des téléphones cellulaires, etc. Fondamentalement, des nombres aléatoires peuvent être produits sur la base d'un processus aléatoire physiquement ou bien par certaines manipulations mathématiques. Seulement dans le cas mentionné en dernier on parle de nombres pseudoaléatoires, tandis que dans le premier cas on io parle de vrais nombres aléatoires. Dans un générateur de nombres pseudoaléatoires, des nombres sont produits à partir de certaines valeurs initiales, ce que l'on appelle la semence qui est effectuée par les moyens 55 d'initialisation de la Figure 12, classiquement à une très grande vitesse, les nombres devant passer un certain nombre de tests que les nombres aléatoires vrais vont également passer. La semence cependant est produite par un processus aléatoire physiquement vrai. Comme cela a été illustré en se référant à la Figure 12, des registres à décalage à rétroaction linéaire (LFSR) sont utilisés pour fournir des générateurs de nombres pseudoaléatoires. Des registres à décalage avec une rétroaction linéaire ont pour avantage que ce sont des théories mathématiques qui indiquent que certaines particularités des nombres pseudoaléatoires produits peuvent être prédites de manière théorique. Les particularités les plus importantes sont la longueur de période et la complexité linéaire de la séquence de sortie. Ainsi, il existe des théories pour des registres à décalage linéaire qui rendent possible soit de prédire de manière exacte la séquence de sortie, soit au moins de faire des déclarations sur la longueur minimum de la période et la dimension maximum de la complexité linéaire. Dit de manière différente, les seuils inférieurs pour la longueur de période et la complexité linéaire peuvent être indiqués et prouvés par des processus mathématiques.

L'inconvénient lié à l'utilisation de registres à décalage avec une rétroaction linéaire comme blocs de formation de base dans des générateurs de nombres pseudoaléatoires est que les séquences de sortie ont une complexité linéaire qui est relativement petite comparée à la longueur de période. La raison de cela est que les séquences de sortie d'un registre à décalage individuel avec une rétroaction linéaire ont déjà une telle disproportion de longueur de période par rapport à la complexité linéaire.

Lorsqu'un registre à décalage avec une rétroaction linéaire comporte par exemple N cellules de mémoire, telles que par exemple des bascules flipflop, la longueur de période de la séquence de sortie peut au plus prendre la valeur de 2N-1. Si le polynôme de rétroaction est bien sélectionné, cela sera effectivement le cas. La complexité linéaire de la séquence de sortie cependant est au plus égale à N. Afin d'augmenter la longueur de période et simultanément la complexité linéaire, il serait nécessaire d'utiliser un registre à décalage avec une rétroaction linéaire pour continuer à augmenter le nombre de cellules de io mémoire ce qui, d'une part, entraîne des problèmes en ce qui concerne l'espace et d'autre part entraîne des problèmes électriques puisque toutes les cellules de mémoire dans un registre à décalage doivent être adressées par un bloc, des problèmes de synchronisation devenant de plus en plus prononcés lorsque le nombre de cellules de mémoire augmente.

En outre, un nombre toujours plus grand de cellules de mémoire à l'intérieur d'un registre à décalage simple a pour résultat que le générateur de nombres pseudoaléatoires peut être localisé encore plus facilement par un attaquant et devenir ainsi la cible d'une attaque cryptographique encore plus facilement. Ceci présente un inconvénient spécial lorsque le générateur de nombres pseudoaléatoires contient des informations secrètes ou fonctionne sur la base d'informations secrètes, ce qui sera classiquement le cas lorsque le générateur de nombres pseudoaléatoires est utilisé dans un domaine cryptographique.

L'objectif de la présente invention est de mettre à disposition un 25 concept amélioré pour produire des nombres pseudoaléatoires.

Cet objectif est atteint par un générateur de nombres pseudoaléatoires, caractérisé en ce qu'il comporte un premier registre à décalage élémentaire ayant une particularité de rétroaction non linéaire et une première sortie de registre à décalage élémentaire; un deuxième registre à décalage élémentaire ayant une deuxième sortie de registre à décalage élémentaire; et des moyens de combinaison destinés à combiner la première sortie de registre à décalage élémentaire et la deuxième sortie de registre à décalage élémentaire pour obtenir un signal combiné comportant un nombre pseudoaléatoire à une sortie, par un procédé pour produire une séquence de nombres pseudoaléatoires, caractérisé en ce qu'il comporte les étapes suivantes: faire fonctionner un premier registre à décalage élémentaire ayant une particularité de rétroaction non linéaire et une première sortie de registre à décalage élémentaire; faire fonctionner un deuxième registre à décalage élémentaire ayant une deuxième sortie de registre à décalage élémentaire; et combiner des signaux à la première sortie de registre à décalage élémentaire et à la deuxième sortie de registre à décalage élémentaire pour obtenir un signal combiné représentant un nombre pseudoaléatoire de la séquence de nombres pseudoaléatoires; ou par un programme d'ordinateur ayant un code de programme pour io effectuer le procédé conforme à l'invention, lorsque le programme d'ordinateur tourne sur un ordinateur.

La présente invention est fondée sur la découverte que des complexités linéaires élevées, des longueurs de période élevées et une utilisation souple de ressources matérielles déjà présentes peuvent être obtenues en formant le générateur de nombres pseudoaléatoires d'une pluralité de registres à décalage élémentaire ayant des particularités de rétroaction non linéaire, et que des signaux sur les sorties des registres à décalage élémentaire sont combinés les uns avec les autres pour obtenir un signal combiné qui par exemple est un chiffre binaire d'un nombre pseudoaléatoire.

Il convient de faire remarquer ici, dans un cas binaire, qu'un chiffre binaire à la sortie bien évidemment est déjà un nombre aléatoire. Généralement, un nombre pseudoaléatoire avec par exemple 8, 16, ... bits est cependant nécessaire. Dans ce cas, 8, 16, ... bits successifs à la sortie du générateur de nombres pseudoaléatoires pourraient par exemple être sélectionnés. Les bits peuvent être successifs ou non, bien que le retrait de bits successifs à la sortie soit préféré.

En fonction de la règle de combinaison utilisée qui est mise en oeuvre par des moyens de combinaison, une augmentation souple de la complexité linéaire peut être obtenue. Lorsqu'une règle de combinaison non linéaire est utilisée comme moyen de combinaison, telle que par exemple une multiplication, c'est-à-dire une porte ET dans le cas binaire, la complexité linéaire d'une séquence de nombres pseudoaléatoires produite par le générateur de nombres pseudoaléatoires suivant l'invention, dans des conditions préalables adaptées, est égale au produit des complexités linéaires des séquences de nombres pseudoaléatoires produits par le registre à décalage élémentaire individuel ayant des particularités de rétroaction non linéaire. Lorsque cependant une combinaison linéaire est utilisée, telle que par exemple dans l'addition (modulo 2), c'est-à-dire une opération XOU (OU exclusif), dans le cas binaire, la complexité linéaire de la séquence de sortie du générateur de nombres pseudoaléatoires est égale à la somme des complexités linéaires des séquences de nombres pseudoaléatoires produits par les registres à décalage élémentaire ayant une particularité de rétroaction non linéaire. L'utilisation de registres à décalage élémentaire ayant des particularités de rétroaction non linéaire à la place de particularités de io rétroaction linéaire rend possible que les relations illustrées ci- dessus en ce qui concerne la complexité linéaire s'appliquent. En outre, la longueur de période de la séquence de générateurs de nombres pseudoaléatoires sera toujours égale au produit des longueurs de période de registre à décalage élémentaire eux-mêmes.

Le concept de générateur de nombres pseudoaléatoires suivant l'invention est d'un avantage particulier par le fait que n'importe quel nombre de registres à décalage élémentaire ayant des particularités de rétroaction non linéaire peut être utilisé et que leurs sorties peuvent être combinées par des moyens de combinaison, les moyens de combinaison pouvant être formés pour être très simples, à savoir par exemple en effectuant uniquement une opération ET et/ou une opération XOU (OU exclusif), c'est-à-dire une addition modulo 2.

En utilisant n'importe quels nombres de registres à décalage élémentaire dans le générateur de nombres pseudoaléatoires suivant l'invention, il y a une grande flexibilité pour la production d'une complexité linéaire spéciale ou une longueur de période spéciale pour chaque application spéciale. Un registre à décalage élémentaire individuel ayant une rétroaction non linéaire n'a ainsi pas besoin d'être modifié lorsqu'un générateur de nombres pseudoaléatoires pour une application différente est nécessaire. À la place, le concept suivant l'invention rend possible que chaque application différente fournisse un nombre différent de registre à décalage élémentaire ayant une rétroaction non linéaire et de les coupler par des moyens de combinaison. Le développeur cependant a un grand degré de liberté pour produire, pour chaque application, un produit dimensionné de manière précise qui, d'une part, n'est pas surdimensionné (et est ainsi efficace en terme de coût) et qui d'autre part n'est pas sous-dimensionné et comporte ainsi la longueur de période et la complexité linéaire exigée pour une application spéciale.

En outre, le concept suivant l'invention est avantageux en ce qui concerne la sécurité et la souplesse lorsque l'on conçoit le circuit puisque divers registres à décalage élémentaire peuvent être agencés en tant qu'unités spéciales à des positions à l'intérieur d'un circuit intégré souhaitées par le développeur de circuit. Si cependant le nombre de cellules de mémoire devait croître lorsque l'on utilise un registre à décalage unique pour augmenter la complexité linéaire, un agencement à registre à décalage de ce lo genre ayant un grand nombre de cellules de mémoire pourrait être reconnu de manière encore plus claire, comparé à différents registres à décalage élémentaire considérablement plus petits, qui en principe peuvent être agencés à souhait sur un circuit intégré et ainsi ne peuvent être que difficilement localisés par un attaquant ou ne pas être localisés du tout. Dans le générateur de nombres pseudoaléatoires suivant l'invention, les registres à décalage élémentaire doivent uniquement être connectés à des moyens de combinaison qui comportent généralement une ou plusieurs grilles par l'intermédiaire d'une ligne de sortie de registre à décalage élémentaire unique, les moyens de combinaison pouvant être cachés sur un circuit intégré facilement et sans grands efforts.

En résumé, le générateur de nombres pseudoaléatoires suivant l'invention est avantageux en ce qu'il peut être formé de manière efficace et adaptable en terme d'échelle pour les exigences correspondantes d'une part et en ce que d'autre part il entraîne la possibilité d'être disposé sur un circuit intégré d'une manière répartie telle qu'il ne peut pas être localisé facilement pour des applications où la sécurité est un point critique.

Dans des modes de réalisation préférés de la présente invention, les registres à décalage élémentaire utilisés sont des registres à décalage binaire ayant une fonction de rétroaction non linéaire, qui produit des séquences périodiques maximales chaque fois que toutes les cellules des registres à décalage ne contiennent pas le bit 0. Un registre à décalage périodique maximal de ce genre ayant N cellules de mémoire produit des séquences de sortie de longueur de période 2N-1.

En outre, il est préférable que les nombres de cellules de mémoire 35 des registres à décalage élémentaire ayant des particularités de rétroaction non linéaire utilisés dans un générateur de nombres pseudoaléatoires, par i0 paires, n'aient pas un diviseur commun. Cela signifie que les registres à décalage élémentaire qui comportent chacun un certain nombre de cellules de mémoire, comportent des nombres de cellules de mémoire, dont le plus grand diviseur commun est égal à 1.

En outre, il est préférable que les registres à décalage élémentaire utilisés comportent les particularités supplémentaires pour produire des séquences de complexité linéaire maximale chaque fois que toutes les cellules du registre à décalage contiennent un O. Un registre à décalage de ce genre ayant N cellules de mémoire produit des séquences de sortie ayant une io complexité linéaire de 2N-2. Si cette particularité s'applique à tous les registres à décalage utilisés, la complexité linéaire de la séquence de sortie du générateur de nombres pseudoaléatoires a une valeur maximale correspondante pour la complexité linéaire.

En outre, il est préférable, pour certains modes de réalisation de la présente invention en ce qui concerne une capacité de détection théorique sûre et une prédictabilité, que la séquence de sortie soit utilisée uniquement une fois pour chaque registre à décalage, c'est-à-dire seulement un "fil" sort de chaque registre à décalage.

En outre, il est préférable que les séquences de sortie de certains registres à décalage soient multipliées les unes par les autres, segment par segment (multiplication modulo 2). Les séquences de produits produites de cette manière sont envoyées à un sommateur total.

En outre, il est préférable que la séquence de sortie de au moins un registre à décalage soit envoyée directement au sommateur total.

Enfin, il est préférable que la séquence de sortie du sommateur total qui fait partie des moyens de combinaison représente la séquence de sortie du générateur de nombres pseudoaléatoires complet. Dans ce contexte, une opération XOU de plusieurs séquences d'entrée, c'est-à-dire terme par terme, ce qui est dans le cas binaire bit par bit, est ce que l'on entend par une addition totale.

Il est particulièrement préférable d'utiliser des combinaisons simples de registres à décalage à rétroaction non linéaire existants puisque des théorèmes théoriques concernant la longueur de période et la complexité linéaire des séquences de sortie peuvent être exactement démontrés de manière mathématique par l'intermédiaire de ces combinaisons simples. Ceci permet l'utilisation commandée du registre à décalage suivant l'invention Il ayant une particularité de rétroaction non linéaire dans des générateurs de nombres pseudoaléatoires.

En outre, il est préférable que les registres à décalage élémentaire individuels, comme cela a été décrit, soient des registres à décalage à particularité de rétroaction non linéaire périodique de manière maximale (MPNLFSR). Un registre à décalage à particularité de rétroaction non linéaire périodique de manière maximale est un NLFSR ayant la particularité d'être capable de produire des séquences de longueur de période maximale. II est supposé que le registre à décalage a N cellules de mémoire. La longueur de io période maximale sera alors de 2N-1. Lorsque les cellules de mémoire d'un MP-NLFSR sont occupées par n'importe quel état initial (la seule exception étant qu'il n'y a pas toutes les cellules qui contiennent le bit 0), ce MP-NLFSR produira toujours une séquence de longueur de période maximale.

En fonction de la mise en oeuvre, des MP-NLFSR peuvent être produits d'une manière expérimentale par recherche par ordinateur. Conformément à l'invention, il s'est avéré que des MP-NLFSR construits de cette manière ont presque toujours une complexité linéaire très élevée. Cela signifie que la séquence de sortie produite par le MP-NLFSR a ainsi non seulement une longueur de période maximale de 2N-1, mais généralement également une complexité linéaire élevée de manière similaire. En particulier, la valeur maximale possible pour la complexité linéaire est 2N-2, cette valeur étant recherchée pour la présente invention. Cette observation résulte d'expériences d'ordinateur d'une part et est conforme également à la règle démontrée de manière mathématique par Meidl et Niederreiter qui est illustrée dans IEEE Transactions sur Informations Theory 48, n 11, pages 2817 à 2825, novembre 2002.

Comme cela a été décrit, il est préférable que les nombres de cellules de mémoire des MP-NLFSR utilisés, par paires, n'aient pas de diviseurs communs les uns parmi les autres. Des valeurs exactes pour la longueur de période et la complexité linéaire de la séquence de sortie peuvent alors être prouvées de manière mathématique pour certaines combinaisons des MPNLFSR, par une formule contenant les quantités R, S, T, ..., dans laquelleR est le nombre de cellules de mémoire du premier registre à décalage à rétroaction non linéaire périodique de manière maximale, S est le nombre de cellules de mémoire du deuxième registre à décalage à rétroaction non linéaire périodique de manière maximale, T est le nombre du troisième registre à décalage élémentaire, etc. En outre, des registres à décalage à rétroaction non linéaire périodique de manière maximale peuvent être utilisés, dont les séquences de sortie n'ont pas la complexité linéaire maximale mais des valeurs (quelque peu) plus petites, telles que par exemple LI, L2, L3. Lorsque des registres à décalage élémentaire de ce genre sont combinés conformément à l'invention, de préférence en utilisant une règle de combinaison simple qui par exemple comporte uniquement une opération ET ou XOU, c'est-à-dire une opération logique simple, une formule pour la longueur de période et pour la complexité linéaire peut également être prouvée de manière exacte mathématiquement pour la séquence de sortie du dispositif de générateur de nombres pseudoaléatoires formée de cette manière. Une formule de ce genre pour la complexité linéaire de la séquence de sortie, cependant, à part les quantités R, S, T, ..., contient également les quantités LI, L2, L3, ...

Des modes de réalisation préférés de la présente invention sont décrits par la suite en se référant aux dessins annexés dans lesquels: la Figure 1 représente un générateur de nombres pseudoaléatoires conforme à un premier mode de réalisation de la présente invention; la Figure 2 représente un générateur de nombres pseudoaléatoires conforme à un deuxième mode de réalisation de la présente invention; la Figure 3 représente un générateur de nombres pseudoaléatoires conforme à un troisième mode de réalisation de la présente invention; la Figure 4 représente un générateur de nombres pseudoaléatoires conforme à un quatrième mode de réalisation de la présente invention; la Figure 5 représente un générateur de nombres pseudoaléatoires conforme à un cinquième mode de réalisation de la présente invention; la Figure 6 représente une mise en oeuvre préférée d'un registre à décalage élémentaire ayant une rétroaction non linéaire; la Figure 7 représente une mise en oeuvre en variante pour un registre à décalage élémentaire ayant une rétroaction non linéaire; la Figure 8 représente une mise en oeuvre en variante pour un registre à décalage élémentaire ayant une rétroaction non linéaire; la Figure 9 représente une mise en oeuvre en variante pour un registre à décalage élémentaire ayant une particularité de rétroaction non linéaire; la Figure 10 représente une mise en oeuvre à titre d'exemple pour un registre à décalage élémentaire ayant une rétroaction non linéaire; la Figure 11 est une illustration générale d'un registre à décalage élémentaire avec des cellules de mémoire dans les moyens à action directe et la fonction F de rétroaction; et la Figure 12 représente un registre à décalage linéaire bien connu pour produire une séquence de nombres aléatoires.

La Figure 1 représente un générateur de nombres pseudoaléatoires suivant un premier mode de réalisation de la présente invention. Le générateur de nombres pseudoaléatoires comporte un premier registre 101 à décalage élémentaire ayant une particularité de rétroaction non linéaire et une première sortie 101a de registre à décalage élémentaire et un deuxième registre 102 à décalage élémentaire qui également de préférence a une particularité de rétroaction non linéaire. Le deuxième registre à décalage élémentaire, comme le premier registre 101 à décalage élémentaire, comporte également une deuxième sortie 102a à registre à décalage élémentaire. Les deux sorties 101a, 102a à registre à décalage élémentaire sont combinées au moyen de moyens de combinaison qui à la Figure 1 sont désignés de manière générale par la référence numérique 120. Les moyens 120 de combinaison, sur le côté de sortie, fournissent un signal combiné sur une ligne 122 de sortie qui, au cours du temps, comporte une séquence de nombres pseudoaléatoires, et de préférence une séquence de bits.

Le générateur de nombres pseudoaléatoires suivant l'invention peut principalement être constitué de deux registres 101, 102 à décalage élémentaire, dans lequel au moins un, mais de préférence les deux, comportent une particularité de rétroaction non linéaire, comme cela a été représenté en se référant à la Figure 1. Dans un mode de réalisation préféré, le nombre de registres à décalage élémentaire qui ont de préférence tous une particularité de rétroaction non linéaire, est supérieur à 2, de sorte que le mode de réalisation représenté à la Figure 1 qui en résulte comporte un troisième registre 103 à décalage élémentaire qui, comme les deux registres 101 et 102 à décalage élémentaire, a également de préférence une particularité de rétroaction non linéaire et qui comporte en outre une troisième sortie 103a de registre à décalage élémentaire. Dans ce cas, c'est-à-dire lorsque trois registres à décalage élémentaire ou plus sont utilisés, les moyens 120 de combinaison sont formés de préférence en deux parties si l'on peut dire, en ce sens qu'ils comportent à la fois un dispositif 120a de multiplication et un sommateur 120b. II est préférable dans le cas binaire que le multiplicateur effectue une multiplication modulo 2, c'est- à-dire une opération ET sur deux bits. En outre, il est préférable que le sommateur 120b effectue une addition modulo 2, dans le cas binaire, c'est- à-dire une opération XOU (OU exclusif) sur deux bits. Il convient de noter cependant qu'en principe il est préférable, pour des raisons de prédictabilité théorique, que les moyens de combinaison incluent uniquement des fonctions logiques de base simple telles que par exemple ET, NONET, OU, NONOU, OU exclusif, NONOU exclusif, etc. Les fonctions logiques peuvent, comme cela ressort de manière évidente de l'exemple représenté à la Figure 1, apparaître dans le dispositif de combinaison soit ensemble, soit séparément en fonction d'une conception donnée souhaitée.

Dans les modes de réalisation préférés, il est préféré en raison de la simplicité de la mise en oeuvre et en raison de la possibilité de la prédictabilité théorique que les moyens de combinaison comportent uniquement une ou plusieurs portes ET et une ou plusieurs portes XOU (OU exclusif), comme cela est illustré principalement en se référant à la Figure 1.

Lorsqu'un générateur de nombres pseudoaléatoires est formé de seulement deux registres à décalage élémentaire, c'est-à-dire le deuxième registre 102 à décalage élémentaire n'est pas présent dans le mode de réalisation représenté à la Figure 1, et qu'à la place il y a uniquement le troisième registre 103 à décalage élémentaire, les moyens de combinaison, contrairement à l'autre cas dans lequel le troisième registre 103 à décalage élémentaire est présent, comportent uniquement le sommateur, c'est-à-dire l'opération 120b XOU à la place de l'opération ET, c'est-àdire le multiplicateur 120a.

En outre, il est préférable que les moyens à action directe des registres 101, 102, 103 à décalage comportent R cellules de mémoire, S cellules de mémoire et T cellules de mémoire. Dans un mode de réalisation préféré de la présente invention, le nombre des cellules de mémoire pour les registres à décalage élémentaire individuels devraient par paire ne pas avoir de diviseur commun. Ainsi, la suite s'applique au mode de réalisation illustré à la Figure 1: plus grand commun diviseur (R, S) = 1, plus grand commun diviseur (R, T) = 1 et plus grand commun diviseur (S, T) = 1, dans lequel plus grand diviseur commun ou gcd est le plus grand diviseur commun des entiers A et B. Cela signifie que dans un mode de réalisation préféré, R = 19, S = 20 et T = 21. En variante, il serait également possible de sélectionner R = 23, S=25etT=27 ou R = 29, S = 30 et T = 31. Le triplé R = 24, S = 25 et T = 27 ne serait cependant pas convenable car les nombres 24 et 27 contiennent le diviseur 3 commun qui n'est pas égal au diviseur 1 commun autorisé maximal.

II est en outre préféré que les registres 101, 102, 103 à décalage utilisés soient de périodicité maximale, c'est-à-dire pris individuellement, produisent les longueurs de période 2R-1, 2s-1 et 2T-1 suivantes, respectivement, dans lesquelles R, S et T sont les nombres de cellules de mémoire dans les registres à décalage élémentaire respectifs. En outre, il est préférable que les registres à décalage élémentaire individuels soient capables de produire des séquences de sortie de complexité linéaire maximale. De cette manière, la séquence de sortie des R registres 101 à décalage de cellules doit avoir une complexité linéaire de 2R-2. Ici, la complexité linéaire est uniquement plus petite de 1 par rapport à la longueur de période, ce qui est uniquement possible parce que le registre 101 à décalage élémentaire a une particularité de rétroaction non linéaire.

En variante, il n'est pas nécessairement exigé que les registres à décalages périodiques maximaux utilisés aient des séquences de sortie de complexité linéaire maximale. Ainsi, une complexité linéaire plus petite résulte également d'une séquence de sortie d'un générateur de nombres pseudoaléatoires suivant l'invention complet, qui cependant n'est pas critique pour certaines applications.

Comme on peut le voir à la Figure 1, le générateur de nombres pseudoaléatoires préféré illustré y fournit une séquence de sortie ayant une longueur de période égale au produit des longueurs de période des registres 101, 102, 103 à décalage élémentaire individuels. En outre, une complexité linéaire plus grande résulte puisque le multiplicateur 120 a pour résultat que les complexités linéaires des deux registres 101, 102 à décalage élémentaire sont multipliées. La complexité linéaire du troisième registre 103 à décalage élémentaire est ajoutée au produit des complexités linéaires des deux registres 101, 102 à décalage élémentaire dues au sommateur 120b dans les moyens de combinaison de sorte que le résultat est une complexité linéaire totale de la séquence de sortie du générateur de nombres pseudoaléatoires suivant l'invention représenté à la Figure 1, comme il est illustré au moyen des équations de la Figure 1.

Le mode de réalisation préféré pour un générateur de nombres pseudoaléatoires conforme à la présente invention illustré à la Figure 2 diffère du mode de réalisation illustré à la Figure 1 par le fait qu'un autre registre 104 à décalage non linéaire est fourni. Ainsi, les deux premiers registres 101, 102 à décalage élémentaire, comme illustré à la Figure 1, sont combinés l'un avec l'autre par le multiplicateur 120, tandis que le signal de sortie du multiplicateur 120a, comme il est illustré à la Figure 1, est ajouté au signal de sortie du registre 103 à décalage élémentaire. Contrairement à la Figure 1, le signal de sortie du quatrième registre 104 à décalage élémentaire est également ajouté en utilisant un sommateur 120b ayant maintenant trois entrées.

La longueur de période peut, comme cela est représenté à la Figure 2, être augmentée en utilisant un quatrième registre 104 à décalage élémentaire, non pas de manière additive mais de manière multiplicative. En outre, la complexité linéaire est également augmentée par le quatrième registre à décalage bien qu'il ne contribue que de manière additive, mais pas de manière multiplicative.

Un autre mode de réalisation de la présente invention est représenté à la Figure 3, dans lequel la Figure 3 diffère de la Figure 2 par le fait qu'il y a un autre registre 105 à décalage élémentaire, dont la sortie de registre à décalage élémentaire est également envoyée au multiplicateur 120a comme le sont les sorties correspondantes des premier et deuxième registres à décalage élémentaire. Ici, la longueur de période est de nouveau augmentée de manière multiplicative. II est important que la complexité linéaire également soit augmentée de manière multiplicative, comme cela est illustré en se référant aux équations représentées à la Figure 3.

Une autre variante de la présente invention est illustrée à la Figure 4. Ici, dix registres 101 à 110 à décalage élémentaire sont utilisés qui, comme illustré en se référant à la Figure 4, sont combinés les uns avec les autres par des moyens de combinaison qui maintenant non seulement comportent un multiplicateur 120a et un sommateur 120b, mais qui, dans l'exemple représenté à la Figure 4, comportent en outre des multiplicateurs supplémentaires 120c, 120d. II convient de noter que dans tous les registres à décalage, les sorties connectées aux différents multiplicateurs 120a, 120c, 120d peuvent bien évidemment être également connectées à un multiplicateur unique qui a un total de sept entrées. Du côté de sortie, toutes les sorties des multiplicateurs 120a, 120c, 120d et toutes les sorties des registres 103, 104, 110 à décalage élémentaire qui ne sont pas envoyées au multiplicateur sont envoyées vers le sommateur 120b pour obtenir une séquence de nombres pseudoaléatoires à une sortie 122 de total.

II doit être mentionné à ce moment qu'il est généralement'préféré d'utiliser des moyens de combinaison qui sont formés de sorte qu'au moins deux sorties de registres à décalage élémentaire sont combinées de manière io multiplicative et de sorte que le signal de sortie du dispositif de combinaison multiplicatif, c'est-à-dire du multiplicateur 120a, 120c et 120d respectivement soit envoyé à un sommateur 120b total qui comporte en outre tous les signaux de sortie de registres à décalage élémentaire des autres registres à décalage élémentaire qui ne sont pas connectés à un multiplicateur et qui eux-mêmes ont une sortie qui coïncide avec la sortie 122 totale du générateur de nombres pseudoaléatoires suivant l'invention. Un tel agencement est préféré pour des raisons d'une meilleure prédictabilité et ainsi d'une capacité à être utilisé plus sûre des registres à décalage de l'invention.

La Figure 5 représente un mode de réalisation en variante pour un générateur de nombres pseudoaléatoires suivant l'invention dans lequel un total de 11 registres à décalage élémentaire sont utilisés, qui ont de préférence tous une particularité de rétroaction non linéaire. De cette manière, les lignes de sortie des registres à décalage élémentaire des registres 101, 102, 105, 109, 110, 111 à décalage élémentaire sont reliées par le multiplicateur 120a, tandis que les lignes de sortie de registres à décalage élémentaire des registres 103, 104, 106, 107, 108 à décalage élémentaire ensemble avec la sortie du multiplicateur 120a sont reliées par l'intermédiaire du sommateur 120b total pour obtenir, au cours du temps, une séquence de nombres pseudoaléatoires à une sortie 122.

Dans un mode de réalisation préféré de la présente invention, tous les circuits ont un caractère binaire. Cela signifie que chaque registre à décalage élémentaire produit une séquence de bits sur le côté sortie, c'est-à-dire aux sorties 101a, 102a, 103a de la Figure 1, dans lesquelles chaque bit de la séquence individuelle de bits est associé à un cycle d'horloge qui est fourni par une horloge de commande non représentée aux Figures 1 à 5. Dans ce cas, des bits sur les lignes 101, 102, 105, 109, 110, 111 de sortie de la Figure 5, par exemple, qui appartiennent toutes au même bloc de commande sont additionnés par le sommateur 120a, dont la sortie inclut également ainsi une séquence de nombres pseudoaléatoires dont la complexité linéaire est égale, de manière analogue à la formule qui a été décrite en se référant aux Figures 1 à 3, au produit des complexités linéaires des registres 101, 102, 105, 109, 110, 111 à décalage et dont la longueur de période est égale au produit des longueurs de période des registres 101, 102, 105, 109, 110, 111 à décalage individuels.

Cette séquence est alors, également bit par bit, additionnée aux io séquences de sortie des registres 103, 104, 106, 107, 108 à décalage de la Figure 5 par le sommateur 120b total.

Il convient de noter que des retards introduits par le multiplicateur 120a ne sont pas significatifs puisque est sélectionnée de manière aléatoire de toutes les manières la cellule de mémoire à l'intérieur d'un registre à décalage élémentaire incluant une boucle à rétroaction dont est extraite la séquence de sortie d'un registre à décalage élémentaire est sélectionnée de manière arbitraire. Dit de manière différente, il s'agit d'une sélection arbitraire de la cellule de mémoire de la pluralité de cellules de mémoire à l'intérieur d'un registre à décalage élémentaire à laquelle est connectée la ligne de sortie de registre à décalage élémentaire. Ainsi, il est également non significatif de savoir la dimension du retard qu'un multiplicateur 120a introduit. En outre, il n'est pas nécessaire pour tous les registres à décalage individuels d'être synchronisés par la même horloge ou, dit de manière générale, d'être synchronisés à la même vitesse, tant qu'une addition par le sommateur 120b ou une multiplication par le multiplicateur 120a, respectivement, est garantie afin qu'une séquence continue de nombres aléatoires soit obtenue à la sortie 122. II n'est pas important de savoir, en relation avec un point absolu dans le temps, si des séquences décalées les unes par rapport aux autres des registres à décalage élémentaire ou des séquences se développant à l'intérieur des moyens de combinaison, tel que par exemple à la sortie du multiplicateur 120a, sont combinées ou non d'une manière décalée ou non décalée.

Il convient de noter en anticipation avec la Figure 6 que des séquences de nombres pseudoaléatoires peuvent être extraites de chaque registre à décalage élémentaire ayant plusieurs cellules de mémoire à de nombreuses positions. Ainsi, dans le mode de réalisation représenté à la Figure 6, la première séquence de nombres pseudoaléatoires peut par exemple être extraite à la sortie de la cellule 5 de mémoire qui est désignée par SEn. En outre ou de préférence en variante, même la deuxième séquence de nombres pseudoaléatoires peut être extraite à la sortie de la cellule 3 de mémoire qui est désignée par SE1. La même chose s'applique à la Figure 9, où une séquence peut par exemple être émise en sortie du registre à décalage élémentaire à la sortie de la cellule 2 de mémoire ou en variante à la sortie de la cellule 3 de mémoire qui est désignée par 15 . De nombreuses possibilités différentes sont représentées à la Figure 10, où des séquences peuvent être extraites, c'est-à-dire à la sortie des cellules D7, D6, D5, D4, D3, D2, Dl ou DO de mémoire.

Ensuite, en se référant aux Figures 6 à 10, un certain nombre de modes de réalisation différents pour mettre en oeuvre les registres 101 à 111 à décalage élémentaire individuels aux Figures 6 à 9 sera fourni. Il est également remarqué que tous les registres à décalage, tel que par exemple à la Figure 5 les registres 101 à 111 de décalage, ne doivent pas avoir la même mise en oeuvre et ils peuvent avoir des mises en oeuvre différentes tant qu'au moins l'un et de préférence tous les registres à décalage a/ont une particularité de rétroaction non linéaire.

La Figure 6 représente un registre à décalage élémentaire ayant une rétroaction non linéaire pour produire une séquence pseudoaléatoire de nombres avec des moyens 1 à action directe comportant une séquence d'unités 2 à 5 de mémoire et comportant en outre une entrée 6 et une sortie 7 qui correspond à la sortie du dispositif pour émettre en sortie la séquence de nombres pseudoaléatoires. II convient de noter que la séquence de nombres pseudoaléatoires peut être augmentée par des moyens supplémentaires qui ne sont pas représentés à la Figure 6 pour mettre en tampon des séquences de nombres aléatoires, pour les combiner d'une autre manière, etc. Le dispositif représenté à la Figure 6 comporte en outre des moyens 8 à rétroaction ayant une particularité à rétroaction variable et sont couplés entre l'entrée 6 et la sortie 7 des moyens 1 à action directe. La particularité de rétroaction variable des moyens 8 à rétroaction est illustrée à la Figure 6 par le fait que les moyens 8 à rétroaction peuvent prendre une première particularité 9 à rétroaction ou une seconde particularité 10 à rétroaction, une commutation entre la première particularité 9 à rétroaction et la deuxième particularité 10 de rétroaction pouvant par exemple avoir lieu au moyen de moyens 11 à commutation. Le signal de commande pour les moyens 11 de commutation est uniquement fourni à titre d'exemple par les quatrièmes moyens SE2 à mémoire, comme illustré de manière symbolique par un trajet de signal. La première particularité 9 de rétroaction et la deuxième particularité 10 de rétroaction diffèrent dans le mode réalisation représenté à la Figure 6 par le fait que dans le cas de la première particularité de rétroaction l'état des moyens 1 de mémoire (n 3) entre en rétroaction, tandis que dans le cas de la deuxième particularité de rétroaction, l'état des moyens 5 de mémoire (SEn) contribue à la rétroaction.

io En variante ou de manière supplémentaire, les moyens 8 de rétroaction peuvent être formés de sorte que dans la particularité de rétroaction combinant la valeur à la sortie 7 des moyens à action directe à un état intérieur des moyens à action directe, une règle de combinaison différente est utilisée en fonction des particularités de rétroaction sélectionnées. De cette manière, une combinaison ET peut être utilisée par exemple dans la première particularité de rétroaction pour combiner la valeur à la sortie 7 et la valeur de la cellule 3 de registre, tandis la deuxième particularité de rétroaction diffère de la première particularité de rétroaction par le fait qu'il ne s'agit pas d'une combinaison ET mais d'une combinaison OU qui est utilisée pour combiner les deux valeurs mentionnées. II est évident pour le spécialiste de la technique que différents types de différentes règles de combinaison peuvent être utilisés.

En outre, des valeurs des moyens SE1 et SEn de mémoire, respectivement, n'ont pas besoin d'être envoyées directement à des moyens de combinaison dans les moyens de rétroaction, et ces valeurs peuvent par exemple être inversées, combinées l'une avec l'autre ou traitées de manière non linéaire de n'importe quelle manière avant que les valeurs traitées ne soient envoyées à des moyens de combinaison.

En outre, il n'est pas essentiel que les moyens 11 de commutation soient commandés directement par l'état de l'unité SE2 à mémoire. À la place, l'état des moyens SE2 de mémoire peut être inversé, traité de manière logique ou arithmétique, de n'importe quelle autre manière ou même être combiné avec l'état d'un ou plusieurs moyens de mémoire supplémentaires tant qu'un dispositif pour produire une séquence pseudoaléatoire de nombres ayant des moyens de rétroaction est obtenu, dont la particularité de rétroaction n'est pas statique et peut varier de manière dynamique en fonction des moyens à action directe et en particulier d'un ou plusieurs états dans des unités de mémoire des moyens à action directe.

Dans les moyens 1 à action directe de la Figure 6, des moyens 13 de commande supplémentaires agencés entre deux éléments de mémoire, à savoir dans l'exemple représenté à la Figure 6 entre les éléments 4 et 5 de mémoire, sont incorporés. Comme il y a un passage de signal de l'élément 0 de mémoire vers l'élément n de mémoire à la Figure 6, l'élément 4 de mémoire est l'élément de mémoire agencé en face des moyens de commande tant que le passage de signal est concerné, tandis que l'élément 5 de mémoire est le signal agencé après les moyens de commande tant que le passage de signal est concerné. Les moyens 13 de commande ont une entrée 13a de commande qui peut être alimentée en un signal de commande qui en principe peut être n'importe quel signal de commande.

Le signal de commande peut par exemple être une séquence de nombres aléatoires vraie de sorte que la séquence de sortie de l'agencement de registre à décalage est une séquence de nombres aléatoires. Le signal de commande peut également être un signal de commande déterministe de sorte qu'une séquence de nombres pseudoaléatoires est obtenue du côté de la sortie.

L'entrée 13a de commande, cependant, est connectée de préférence aux moyens 8 à rétroaction, comme il est illustré à la Figure 6 par la ligne en pointillés correspondante, de sorte qu'un signal dans les moyens à rétroaction fournit le signal de commande pour les moyens 13 de commande, ce qui signifie que le signal de commande est un signal à caractéristique déterministe également.

Bien que les moyens 8 à rétroaction dans le mode de réalisation représenté à la Figure 6 soient désignés comme étant des moyens à rétroaction variable, les moyens à rétroaction peuvent également être des moyens à rétroaction ayant une particularité de rétroaction constante, comme cela est représenté par un trait pointillé en 14. Dans ce cas, le signal de commande pour l'entrée 13a de commande sera déduit d'un point 14a de ramification, comme cela est illustré schématiquement à la Figure 6 par le trait pointillé à partir du point 14a vers l'entrée 13a de commande des moyens 13 de commande.

En outre, le générateur de séquences de nombres élémentaires représenté à la Figure 6, pour augmenter le rendement, est utilisé pour produire, par exemple, non seulement une séquence à la sortie 7 mais également une deuxième séquence de nombres de préférence pseudoaléatoires à une autre entrée 15, dans lequel les deux séquences ou uniquement une séquence des deux séquences est ou sont envoyée(s) dans des moyens de combinaison. Incorporer les moyens 13 de commande a pour effet que la sortie de séquence à la sortie 7 est réellement différente de la sortie de séquence à la sortie 15, les deux séquences n'étant pas décalées en direction l'une de l'autre mais, comme cela a été décrit, sont réellement différentes puisqu'elles sont extraites avant et après les moyens 13 de io commande respectivement tant que le passage de signal est concerné.

La Figure 7 représente un registre à décalage à 8 bits, un multiplexeur 20 étant commandé par l'intermédiaire d'une entrée 20a de commande en fonction de l'état des moyens n 4 de mémoire. Si l'entrée 20a de commande est à un état 0, c'est-à-dire s'il y a un état 0 dans la cellule n 4 de mémoire, le multiplexeur va être commandé de sorte qu'il connecte l'état des moyens n 7 de mémoire à une première ligne 20b d'entrée de ceux-ci à une ligne 20d de sortie. Cela correspondrait à l'effet d'un registre à décalage linéaire ayant le polynôme à rétroaction suivant: Si l'entrée 20a de commande cependant est dans un état, l'état des moyens n 6 de mémoire sera connecté à la ligne 20d de sortie du multiplexeur 20 à une deuxième entrée 20c. La ligne 20d de sortie est connectée à des moyens 21 de combinaison qui, dans le mode de réalisation représenté à la Figure 7, reçoit également la valeur à la sortie 7 des moyens à action directe, qui au même endroit forme la sortie du dispositif pour produire une séquence pseudoaléatoire de nombres. Les résultats calculés par les moyens 21 decombinaison sont envoyés à leur tour aux premiers moyens n 7 de mémoire à la Figure 7.

Si les contenus de la cellule n 4 de mémoire sont égaux à 1, il y aura le polynôme de rétroaction suivant: II devient évident de la description cidessus qu'une commutation entre les deux polynômes à rétroaction mentionnés ci-dessus a lieu en fonction des contenus de la cellule n 4 de mémoire des moyens 1 à action directe.

Il s'est avéré que les complexités linéaires de séquences obtenues conformément à l'invention sont élevées, à savoir comprises entre 234 et 254 lorsque le registre à décalage a 8 bascules flip-flop. II convient de noter que la longueur de période d'une séquence produite par n'importe quel registre à décalage à 8 échelons peut, au maximum, être égale à 255. La valeur io maximale pour la complexité linéaire d'une telle séquence est de 254.

Le registre le plus simple de tous les registres à décalage élémentaire à 8 échelons qui peut produire une séquence est le registre à décalage illustré à la Figure 7, ayant les deux polynômes de rétroaction illustrés à la Figure 7. En ce qui concerne la théorie des registres à décalage linéaire à titre d'exemple comparatif, il convient de noter qu'il y a 16 polynômes primitifs de degré 8. Chaque polynôme de ce genre décrit un registre à décalage linéaire qui peut produire une séquence de longueur de période 255 et de complexité linéaire 8. Au contraire, il y a beaucoup plus de registres à décalage, à savoir 2 020, conformes à la présente invention qui peuvent produire les séquences de longueur de période 255 conformes à la présente invention.

En outre, les séquences qui sont produites par les registres à décalage suivant l'invention ont des complexités linéaires bien plus grandes que les modes de réalisation analogues conformes à l'art antérieur. Comme cela a été décrit, le mode de réalisation représenté à la Figure 7 est préféré parmi toutes les possibilités examinées pour un registre à décalage à 8 bits ayant des moyens de rétroaction puisqu'il entraîne les coûts de matériels les plus bas, et simultanément a une durée de période maximale et en outre comporte une complexité linéaire maximale.

Les moyens 13 de commande sont agencés en outre entre deux éléments de mémoire à la Figure 7, ceux-ci étant des éléments 1 et 2 de mémoire. Les moyens 13 de commande reçoivent un signal de commande qui est extrait des moyens 8 à rétroaction ayant une particularité à rétroaction variable. Bien évidemment, le signal pour les moyens de commande peut également être extrait après la grille 21 XOU tant que le passage de signal est concerné. En outre, les moyens 13 de commande peuvent bien évidemment également être formés entre n'importe quelles deux autres cellules de mémoire, tel que par exemple entre les cellules 5 et 6 de mémoire ou entre les cellules 0 et 7 de mémoire, c'est-à-dire soit dans la direction de passage du signal, après la cellule 0 de mémoire de sorte que le signal à la sortie des moyens de mémoire est directement émis en sortie à la sortie 7, soit directement avant la cellule 7 de mémoire.

II est cependant préféré pour des raisons de traitement de signal pour tous les signaux, tel que par exemple des séquences de sortie, des signaux de commande et des signaux de données pour le multiplexeur, etc. io qu'ils soient extraits à la sortie des registres à décalage de sorte que le registre à décalage, à part sa fonctionnalité pour produire la séquence de nombres, sert également pour fournir des signaux stables pour des portes logiques. Ainsi, des étages de sortie correspondants pour des portes logiques n'ont pas besoin d'être produits lorsque des signaux de commande ou des signaux de sortie sont extraits des sorties des portes logiques elles-mêmes.

Ensuite, on se référera à la Figure 8 pour illustrer une mise en oeuvre spéciale des moyens 20 multiplexeurs de la Figure 7. Le multiplexeur 20 peut aisément être mis en oeuvre par deux portes 40a, 40b ET qui sont toutes les deux connectées à des portes 41a, 41b OU (ou des portes XOU) couplées en série, comme cela est représenté à la Figure 8. En particulier, l'état de la cellule 4 de mémoire est envoyé à la première porte 40a ET, tandis que l'état inversé de la cellule 4 de mémoire est envoyé à la deuxième porte 40b ET. Pour déterminer le polynôme de rétroaction correspondant, les contenus de la cellule 6 de mémoire sont envoyés à la première porte 40a ET en tant que deuxième entrée, tandis que les contenus de la cellule 7 de mémoire sont envoyés à la deuxième porte 40b ET et à une deuxième entrée. En outre, il convient de noter que les deux portes OU 41a, 41b connectées en série pourraient être mises en oeuvre d'une manière alternative. Lorsque cependant des mises en oeuvre sont nécessitées dans lesquelles chaque porte logique a deux entrées et une sortie, l'illustration donnée à titre d'exemple représentée à la Figure 8 sera avantageuse.

Dans un procédé pour produire une séquence pseudoaléatoire de nombres à partir d'un registre à décalage élémentaire utilisant des moyens 1 à action directe ayant une pluralité de moyens de mémoire ayant une entrée et une sortie pour émettre en sortie la séquence de nombres, et des moyens de rétroaction comportant une particularité de rétroaction variable et connectés entre l'entrée et la sortie, une étape d'initialisation des moyens de mémoire dans les moyens à action directe à une valeur initiale déterminée à l'avance doit être effectuée en premier.

En réponse à l'état de moyens de mémoire de la pluralité de moyens de mémoire des moyens à action directe, les moyens de commande sont alors commandés dans une autre étape en fonction du signal de rétroaction. Ensuite, l'état de moyens de mémoire connectés à la sortie des moyens 1 à action directe est émis en sortie pour obtenir un certain nombre de la séquence de nombres aléatoires. Après cela, un bloc de décision est io effectué pour examiner si d'autres nombres aléatoires sont nécessaires. Si cette question a une réponse non, le traitement s'arrête ici. S'il est cependant déterminé que des nombres supplémentaires sont nécessaires, le bloc de décision a pour réponse oui, à la suite de quoi une autre étape suit dans laquelle la pluralité de moyens de mémoire sont réoccupés sur la base d'un état précédent des moyens de mémoire et sur la base d'une sortie des moyens de rétroaction. Les étapes de commande des moyens de commande, d'émission en sortie et de réoccupation sont répétées aussi souvent que souhaité dans une boucle pour finalement obtenir une séquence pseudoaléatoire de nombres.

Il convient de remarquer que ce procédé peut être effectué en utilisant une horloge régulière ou même en utilisant une horloge non régulière bien que la version ayant l'horloge régulière soit préférée en ce que concerne la sécurité améliorée vis-à-vis d'une attaque de puissance ou une attaque temporelle.

Dans le cas du registre à décalage linéaire illustré à la Figure 7, il convient de noter que la réoccupation de la pluralité des moyens de mémoire a lieu en série, sur la base de l'état précédent des moyens de mémoire qui, pris dans leur ensemble, soient décalés d'une étape vers la gauche de sorte qu'un état des moyens de mémoire 0 sort sur le côté de sortie. Cette valeur "sortie" est le nombre qui sera émis en sortie. Les moyens de mémoire n 7 à la Figure 7 à la droite extrême peuvent être réoccupés par le décalage vers la gauche de l'état entier de tous les moyens de mémoire considérés. La pluralité de moyens de mémoire et en particulier les moyens 7 de mémoire sont ainsi réoccupés en fonction d'une sortie des moyens de rétroaction au point de synchronisation réelle dans le temps.

La Figure 9 représente un mode de réalisation en variante dans lequel la variante des moyens de rétroaction auxquels on se réfère par la référence numérique 14 à la Figure 6 est illustrée. En particulier, les moyens 14 de rétroaction à la Figure 9 sont formés de sorte qu'ils n'ont pas une particularité de rétroaction variable mais une particularité de rétroaction constante. Les avantages suivant l'invention sont obtenus en agençant au moins un moyen 13 de commande et de préférence un autre moyen 60 de commande dans les moyens à action directe.

Dans le mode de réalisation représenté à la Figure 9, les io moyens 13 de commande sont commandés avec un signal de commande qui est directement déduit des moyens 14 de rétroaction. Dans les moyens à action directe représentés à la Figure 9, uniquement deux moyens 2 et 3 de mémoire sont fournis, le premier moyen 13 de commande étant connecté entre les cellules 2 et 3 de mémoire, tandis que le deuxième moyen 60 de commande est connecté entre la cellule 3 de mémoire et la cellule 2 de mémoire (par l'intermédiaire des moyens 14 à rétroaction). En outre, un passage de signal est marqué par une erreur 61 à la Figure 9, qui représente le passage de signal dans les moyens à action directe qui, dans le mode de réalisation représenté à la Figure 9, va de la droite vers la gauche. Un bit atteint en premier les moyens D2 de mémoire. Le bit stocké dans D2 est émis en sortie et forme un bit de la première séquence. Simultanément, le bit émis en sortie par les moyens 2 de mémoire subit une opération XOU dans le mode de réalisation représenté à la Figure 9 avec le bit qui vient juste d'être appliqué au moyen 14 de rétroaction pour obtenir un bit de résultat qui sera alors synchronisé dans l'élément 3 de mémoire dans le cycle suivant à une sortie de l'opération XOU. Ainsi, le bit qui vient juste d'être présent dans l'élément 3 de mémoire sera synchronisé en sortie de l'élément 3 de mémoire et ainsi représente un bit de la deuxième séquence pseudoaléatoire de nombres. Le bit à la sortie de la cellule 3 de mémoire est ensuite soumis à une opération XOU avec un signal de commande pour le deuxième moyen 60 de commande, le signal de commande étant produit à partir du signal sur les moyens 14 de rétroaction et le signal de sortie du premier moyen 13 de commande au moyen de moyens de combinaison. Les moyens 62 de combinaison sont de préférence une porte logique et en particulier dans le mode de réalisation représenté à la Figure 9 une porte ET. La première séquence est émise en sortie par l'intermédiaire d'une sortie 7, tandis que la deuxième séquence est émise en sortie par l'intermédiaire d'une sortie 15. Les deux séquences émises en sortie par l'intermédiaire des sorties 7 et 15 sont réellement différentes et pas seulement décalées en phase mutuellement.

Afin de simplifier la mise en oeuvre de la porte 60 XOU, un autre élément de mémoire est fourni dans un autre mode de réalisation préféré après la porte 60 XOU dans la direction de passage du signal, à la sortie de cet élément de mémoire une séquence qui est uniquement décalée en phase vers la première séquence à la sortie 7, qui est cependant différente en io principe de la deuxième séquence à la sortie 15, étant émise en sortie.

La Figure 10 représente un registre à décalage élémentaire à 8 bits avec des bascules flip-flop DO à D7 qui sont connectées en série, dans lequel en outre les deuxièmes moyens 60 de commande sont disposés entre la quatrième et la troisième bascules flip-flop, tandis que les premiers moyens 13 de commande sont disposés entre la septième et la sixième bascules flip-flop. Le premier moyen 13 de commande est de nouveau alimenté directement en le signal de rétroaction sur les moyens 14 de rétroaction, tandis que le deuxième moyen 60 de commande est alimenté en le signal de sortie de la porte 62 ET qui à son tour est fourni d'une part par les moyens 14 de rétroaction et d'autre part par le signal de sortie de la cinquième cellule D5. De manière analogue au mode de réalisation représenté à la Figure 9, la séquence de sortie de la quatrième cellule D4 représente la deuxième séquence de nombres pseudoaléatoires, tandis que la séquence de sortie de la septième cellule D7 représente la première séquence de nombres aléatoires.

Les modes de réalisation représentés aux Figures 9 et 10 pour un registre à décalage élémentaire diffèrent en ce que deux cellules D5, D6 de registre supplémentaire sont connectées entre les deux moyens de commande et en outre en ce que des cellules DO à D3 de mémoire supplémentaires sont formées à la sortie des moyens 60 de commande XOU de sorte qu'un registre à décalage à 8 bits est formé. Dans un mode de réalisation, une séquence de nombres pseudoaléatoires est extraite à la sortie de chaque cellule DO à D7 de mémoire et envoyée à des moyens de combinaison pour obtenir un générateur de nombres pseudoaléatoires particulièrement efficace. En particulier, les deux séquences émises en sortie par les cellules D4 et D5 sont des versions décalées de la séquence émise en sortie par la cellule D6. En outre, les quatre séquences émises en sortie par les cellules D2, D1, DO et D7 sont des versions décalées de la séquence émise en sortie par la cellule D3. Ainsi, chaque séquence des cellules D7, DO, Dl, D2 et D3 sont sensiblement différentes d'une séquence des cellules D4, D5, D6.

II convient de noter que l'état initial auquel le registre à décalage a été initialisé, c'est-à-dire la semence telle qu'on l'a décrite en référence à la Figure 7, l'élément 55, doit être conçu de sorte qu'il comporte au moins une valeur pour un élément de mémoire qui n'est pas égale à 0 afin que le registre à décalage démarre quelque peu et non pas émette huit séquences nulles aux huit sorties. Ensuite, lorsque cette condition est remplie, toutes les huit séquences ont une périodicité maximum, c'est-à-dire ont une longueur de période de 255. En outre, chacune des huit séquences émises en sortie dans le mode de réalisation représenté à la Figure 10 a une complexité linéaire maximale de 254. En outre, comme cela a déjà été décrit, les deux séquences émises en sortie par les cellules D3 et D6 sont sensiblement différentes.

Comme on peut également le voir à la Figure 10, la cellule D5 de mémoire est ici la cellule de commande. Si la cellule D5 contient un 0, l'effet des moyens 60 de commande entre les cellules D3 et D4 sera supprimé.

Uniquement la porte XOU entre les cellules D6 et D7 sera alors appliquée. Si la cellule D5 cependant comporte un 1, à la fois les moyens 13 et 60 XOU seront utilisés.

La Figure 11 représente un registre à décalage à rétroaction général ayant des cellules de mémoire Do, ...Dn_1 avec des moyens à action directe et des moyens de rétroaction auxquels on se réfère par F(xo, x1, .

, )(n_ 1)...DTD: Un registre à décalage à rétroaction a n échelon général (ou n cellule) sur l'élément de base GF(2) = {0,1} est supposé ici. Le registre à décalage comporte n cellules de mémoire (bascules flip-flop) Do, D1,... Dn_1 et la réalisation (électronique) d'une fonction F(xo, x1, ..., )(n_1) de rétroaction. La fonction de rétroaction associe une valeur non ambiguë provenant de GF(2), c'est-à-dire la valeur de 0 ou 1, à chaque n uple incluant n bits. En terminologie mathématique, F est une fonction avec un domaine de définition de GF(2)n et un domaine cible de GF(2).

Le registre à décalage est commandé par une horloge externe. Les contenus de la cellule Di de mémoire sont décalés vers la cellule Di_1 voisine à gauche avec chaque horloge, 1 j n-1. Les contenus de la cellule DO de mémoire sont émis en sortie. Si les contenus des cellules de mémoire Do, D1, Dn_2, Dn-1, à un instant t sont donnés par St, Stil, ..., St+n-2, St+ n-1, les cellules de mémoire, une horloge plus tard, c'est-à-dire à un instant t + 1, contiendront les bits St+1, St+2, ..., St+n-1, St+n, dans lequel la valeur St+n entrant dans la cellule Dn_1 est fournie par St+n = F(St, St+1, ..., St+n_1).

Le n uple (St, St+i, ..., St+n_1) décrit l'état du registre à décalage à un instant t. Le n uple (So, Si, ..., Sn_1) est appelé l'état initial. FSR(F) est utilisé comme abréviation pour le registre à décalage à rétroaction générale ayant une fonction F de rétroaction (FSR signifie registre à décalage à rétroaction).

La figure 12 représente un registre à décalage à rétroaction générale.

Le registre à décalage émet en sortie un bit à chaque horloge de l'horloge externe. De cette manière, le registre à décalage peut produire une séquence (so, s1, s2, ...) de bits périodiques, ce que l'on appelle une séquence de registre à décalage. so, s1, ..., sn_1 doivent être pris comme valeurs initiales de la séquence de registre à décalage. La fonction F(xo, x1, ..., xn_1) de rétroaction et les valeurs initiales so, s1, ..., sn_1 déterminent complètement la séquence de registre à décalage. Comme il y a uniquement 2" états différents pour le registre à décalage, la longueur de période de la séquence so, s1, s2, ... de registre à décalage est au plus de 2".

Un registre FSR(F) à décalage à rétroaction générale sera dit homogène si sa fonction F de rétroaction est homogène, c'est-à-dire si F(0, 0, ..., 0) = 0. Un registre à décalage homogène mis dans l'état initial so = s1 = .. . = sn_1 = 0 produira la séquence zéro. II s'ensuit que la longueur de période de la séquence de sortie d'un registre à décalage homogène à n échelon peut au plus être de 21 1. Lorsque la longueur de période a la valeur maximum de 2" 1, la séquence de registre à décalage est appelée une séquence M et le registre à décalage est à un maximum. Il s'agit d'une tâche importante que de trouver des registres à décalage maximum.

Deux cas spéciaux du registre à décalage à rétroaction général FSR(F) sont d'intérêt particulier. Dans un cas, la fonction F de rétroaction a la forme: F(xo, x1, ..., Xn-1) = Eai1XiXj o<i<j<n-1 dans laquelle les coefficients au sont soit 0, soit 1. Dans ce cas, ceci est appelé une fonction de rétroaction carrée en tant qu'un exemple pour une fonction rétroaction non linéaire et les carrés de l'expression sont également transférés au registre à décalage.

L'autre cas spécial est lorsque la fonction de rétroaction F est linéaire. Dans ce cas F a la forme suivante: F(xo, x1, ..., xn-i) = aox0 + a1X1 + .

+ an-1xn-1, dans laquelle les coefficients a; qui apparaissent sont de nouveau 0 ou 1, c'est-à-dire des éléments de GF(2). Dans ce cas, ceci est appelé un registre à décalage à rétroaction linéaire et l'abréviation LFSR (registre à décalage à rétroaction linéaire) est utilisée pour cela. Il convient de noter qu'à la fois la rétroaction linéaire et les registres à décalage à rétroaction carrés sont homogènes...DTD: Un registre à décalage à rétroaction linéaire à n échelon est généralement caractérisé par un polynôme f(x) binaire de degré n dans une variable x. Ce polynôme f est appelé le polynôme caractéristique du registre à décalage à rétroaction linéaire. Le registre à décalage est alors indiqué par LFSR(f).

La fonction F(xo, x1, ..., xn_I) de rétroaction d'un registre à décalage à rétroaction linéaire est un polynôme de n variables xo, x1, ..., xn_1 et de degré 1. Au contraire, le polynôme f(x) caractéristique du même registre à décalage linéaire est un polynôme de seulement une variable, à savoir la variable x, mais de degré n. La suite s'applique: f(x) = xn + F(1, x, x2, ..., xn-1).

La non linéarité de la fonction de rétroaction peut ainsi être effectuée par des conceptions relativement arbitraires de la fonction F de rétroaction. Pour cela, il suffit en principe de multiplier uniquement les signaux de sortie de deux cellules D; et D;+1 de mémoire, dans lesquelles un registre à décalage carré serait le résultat de cela. Bien évidemment, plus que deux sorties de cellules de mémoire peuvent être multipliées l'une par l'autre ou être soumises à une fonction non linéaire quelconque. En principe, une rétroaction avec uniquement un signal de sortie d'une mémoire unique ro pourrait cependant également être effectuée par exemple en fournissant uniquement le signal de sortie de la cellule Do de mémoire, en l'envoyant à la fonction F(xo) et en envoyant le signal de sortie de cette fonction, par exemple, sur le côté d'entrée dans la cellule Dn_1 de mémoire. Une telle fonction non linéaire avec uniquement une valeur pourrait par exemple être une inversion, c'est- à-dire une fonction NON logique. La fonction non linéaire pourrait cependant également être n'importe quelle autre fonction telle que par exemple une fonction d'association non linéaire ou une fonction cryptographique.

En fonction des circonstances, le procédé suivant l'invention pour produire des nombres pseudoaléatoires peut être mis en ceuvre soit dans du matériel soit par logiciel. La mise en oeuvre peut avoir lieu sur un support de stockage numérique, tel que par exemple une disquette ou sur un CD avec des signaux de commande qui peuvent être lus électroniquement et qui peuvent coopérer avec un système d'ordinateur programmable de sorte que le procédé correspondant soit exécuté. En général, l'invention comporte également un produit de programme d'ordinateur ayant un code de programme stocké sur un support pouvant être lu par machine pour effectuer le procédé suivant l'invention lorsque le produit de programme d'ordinateur tourne sur un ordinateur. Dit de manière différente, l'invention peut ainsi être mise en oeuvre sous la forme d'un programme d'ordinateur ayant un code de programme pour effectuer le procédé lorsque le programme d'ordinateur tourne sur un ordinateur.

Suivant un perfectionnement de l'invention, les moyens de combinaison sont formés pour utiliser uniquement une sortie (101a, 102a, 103a) de registre à décalage élémentaire associée de chaque registre (101, 102, 103) à décalage élémentaire une fois.

Suivant un perfectionnement de l'invention, un registre à décalage élémentaire est formé de sorte qu'il produit une séquence ayant une périodicité qui est la périodicité maximale ou au moins 75 % de la périodicité maximale.

Claims (19)

REVENDICATIONS

1. Générateur de nombres pseudoaléatoires caractérisé en ce qu'il comporte: un premier registre (101) à décalage élémentaire ayant une 5 particularité de rétroaction non linéaire et une première sortie (101a) de registre à décalage élémentaire; un deuxième registre (102) à décalage élémentaire ayant une deuxième sortie (102a) de registre à décalage élémentaire; et des moyens (120) de combinaison destinés à combiner la première lo sortie (101a) de registre à décalage élémentaire et la deuxième sortie de registre à décalage élémentaire pour obtenir un signal combiné comportant un nombre pseudoaléatoire à une sortie (122).

2. Générateur de nombres pseudoaléatoires suivant la revendication 1, caractérisé en ce que les moyens (120) de combinaison comportent un multiplicateur, un sommateur, un diviseur ou un soustracteur.

3. Générateur de nombres pseudoaléatoires suivant la revendication 1 ou 2, caractérisé en ce qu'il comporte en outre un troisième registre (103) à décalage élémentaire ayant une troisième sortie (103a) de registre à décalage élémentaire, les moyens (120) de combinaison étant formés pour combiner la première sortie (101a) de registre à décalage élémentaire, la deuxième sortie (102a) de registre à décalage élémentaire et en plus la troisième sortie (103a) de registre à décalage élémentaire.

4. Générateur de nombres pseudoaléatoires suivant la revendication 3, caractérisé en ce que les moyens (120) de combinaison sont formés pour multiplier (120a) des signaux à la première sortie (101a) de registre à décalage élémentaire et à la deuxième sortie (102a) de registre à décalage élémentaire pour obtenir un résultat de multiplication, et pour additionner (120b) le résultat de multiplication à un signal à la troisième sortie (103a) de registre à décalage élémentaire pour obtenir le signal combiné.

5. Générateur de nombres pseudoaléatoires suivant l'une quelconque des revendications précédentes, caractérisé en ce que les moyens de combinaison sont formés pour utiliser uniquement une sortie (101a, 102a, 103a) de registre à décalage élémentaire associée de chaque registre (101, 102, 103) à décalage élémentaire une fois.

6. Générateur de nombres pseudoaléatoires suivant l'une des revendications précédentes, caractérisé en ce qu'il comporte en outre des moyens de synchronisation, les moyens de synchronisation étant formés pour synchroniser les registres à décalage élémentaire et les moyens de io combinaison.

7. Générateur de nombres pseudoaléatoires suivant l'une des revendications précédentes, caractérisé en ce qu'un registre (101, 102, 103) à décalage élémentaire comporte: des moyens à action directe; et des moyens de rétroaction couplés aux moyens à action directe, les moyens de rétroaction étant formés pour mettre en oeuvre une fonction non linéaire en utilisant un ou plusieurs états dans les moyens à action directe de sorte qu'un signal de sortie provenant des moyens de rétroaction se trouvent dans un contexte non linéaire vis-à-vis d'un signal d'entrée dans les moyens de rétroaction.

8. Générateur de nombres pseudoaléatoires suivant l'une des revendications précédentes, caractérisé en ce qu'un registre (101, 102, 103) à décalage élémentaire comporte: une pluralité de cellules (Do, DI, D2) de mémoire connectées en série, dans lequel la sortie de registre à décalage élémentaire est couplée à une sortie d'une cellule de mémoire, des moyens de rétroaction ayant une entrée de rétroaction et une sortie de rétroaction, les moyens de rétroaction étant connectés à une sortie d'une cellule de mémoire, et dans lequel les moyens de rétroaction sont formés pour combiner des signaux à des sorties d'au moins deux cellules de mémoire l'une avec l'autre d'une manière non linéaire.

9. Générateur de nombres pseudoaléatoires suivant l'une des revendications précédentes, caractérisé en ce que chaque registre à décalage élémentaire comporte un nombre de cellules de mémoire, et dans lequel le nombre de cellules de mémoire des registres à décalage élémentaire est sélectionné de sorte qu'ils n'ont pas un diviseur commun les uns par rapport aux autres.

10. Générateur de nombres pseudoaléatoires suivant l'une des revendications précédentes, caractérisé en ce qu'un registre à décalage élémentaire est formé de sorte qu'il produit une séquence ayant une périodicité qui est la périodicité maximale ou au moins 75 % de la périodicité maximale.

11. Générateur de nombres pseudoaléatoires suivant la io revendication 10, caractérisé en ce que le registre à décalage élémentaire a un nombre N de cellules de mémoire, et dans lequel la séquence a une longueur de période de 2N 1.

12. Générateur de nombres pseudoaléatoires suivant la revendication 1, caractérisé en ce qu'il comporte un troisième registre (103) à décalage élémentaire et un quatrième registre (104) à décalage élémentaire, et dans lequel les moyens de combinaison sont formés pour combiner des signaux à la première sortie (101a) de registre à décalage élémentaire et à la deuxième sortie (102a) de registre à décalage élémentaire au moyen d'une porte (120a) ET, et pour combiner des signaux à une sortie du troisième registre (103) de décalage élémentaire, à une sortie du quatrième registre (104) à décalage élémentaire et à une sortie de la porte (120a) ET par une porte XOU (120b).

13. Générateur de nombres pseudoaléatoires suivant la revendication 1, caractérisé en ce qu'il comporte en outre un troisième registre (103) à décalage élémentaire, un quatrième registre (104) à décalage élémentaire et un cinquième registre (105) à décalage élémentaire, et dans lequel les moyens (120) de combinaison sont formés pour combiner des signaux aux sorties du premier registre (101) à décalage élémentaire, du deuxième registre (102) à décalage élémentaire et du cinquième registre (105) à décalage élémentaire au moyen d'une porte (120a) ET, et pour combiner des signaux à une sortie du troisième registre (103) à décalage élémentaire, du quatrième registre (104) à décalage élémentaire et de la porte(120a) ET au moyen d'une porte (120b) XOU.

14. Générateur de nombres pseudoaléatoires suivant la 35 revendication 1, caractérisé en ce qu'il comporte en outre un troisième registre (103) à décalage élémentaire, un quatrième registre (104) à décalage élémentaire, un cinquième registre (105) à décalage élémentaire, un sixième registre (106) à décalage élémentaire, un septième registre (107) à décalage élémentaire, un huitième registre (108) à décalage élémentaire, un neuvième registre (109) à décalage élémentaire et un dixième registre (110) à décalage élémentaire, et dans lequel les moyens de combinaison sont formés pour combiner des signaux à des sorties du premier registre (101) à décalage élémentaire, du deuxième registre (102) à décalage élémentaire et du cinquième registre (105) à décalage élémentaire au moyen d'une première porte (120a) lo ET, pour combiner des signaux à des sorties du sixième registre (106) à décalage élémentaire et du septième registre (107) à décalage élémentaire au moyen d'une deuxième porte (120d) ET, et pour combiner des signaux à des sorties du huitième registre (108) à décalage élémentaire et du neuvième registre (109) à décalage élémentaire au moyen d'une troisième porte (120c) ET, et pour combiner des signaux à des sorties du troisième registre (103) à décalage élémentaire, du quatrième registre (104) à décalage élémentaire, du dixième registre (110) à décalage élémentaire et de la première porte(120a) ET, de la deuxième porte (120d) ET et de la troisième porte (120c) ET au moyen d'une porte (120b) XOU.

15. Générateur de nombres pseudoaléatoires suivant la revendication 1, caractérisé en ce qu'il comporte en outre un troisième (103), un quatrième (104), un cinquième (105), un sixième (106), un septième (107), un huitième (108), un neuvième (109), un dixième (110) et un onzième (111) registre à décalage élémentaire, et dans lequel les moyens (120) de combinaison sont formés pour combiner des signaux à des sorties des premier (101), deuxième (102), cinquième (105), neuvième (109), dixième (110) et onzième (111) registres à décalage élémentaire au moyen d'une porte (120a) ET, et pour combiner des signaux à des sorties des troisième (103), quatrième (104), sixième (106), septième (107), huitième (108) registres à décalage élémentaire et de la porte (120a) ET au moyen d'une porte (120b) XOU pour obtenir le signal combiné.

16. Générateur de nombres pseudoaléatoires suivant l'une des revendications précédentes, caractérisé en ce que chaque registre à décalage élémentaire est un registre à décalage élémentaire ayant une particularité de rétroaction non linéaire.

17. Générateur de nombres pseudoaléatoires suivant l'une des revendications précédentes, caractérisé en ce que les moyens de combinaison sont formés de manière à inclure une porte sélectionnée parmi le groupe de portes suivantes: porte ET, porte NONET, porte OU, porte NONOU, porte XOU, porte XNONOU.

18. Procédé pour produire une séquence de nombres io pseudoaléatoires, caractérisé en ce qu'il comporte les étapes suivantes: faire fonctionner un premier registre (101) à décalage élémentaire ayant une particularité de rétroaction non linéaire et une première sortie (101a) de registre à décalage élémentaire; faire fonctionner un deuxième registre (102) à décalage 15 élémentaire ayant une deuxième sortie (102a) de registre à décalage élémentaire; et combiner des signaux à la première sortie (101a) de registre à décalage élémentaire et à la deuxième sortie (102b) de registre à décalage élémentaire pour obtenir un signal combiné représentant un nombre pseudoaléatoire de la séquence de nombres pseudoaléatoires.

19. Programme d'ordinateur ayant un code de programme pour effectuer le procédé conforme à la revendication 18, lorsque le programme d'ordinateur tourne sur un ordinateur.