Brevet FR2563392A1 — publié le 19851025

GENERATEUR PSEUDO-ALEATOIRE L'invention est relative à un générateur pseudo-aléatoire. Un dispositif de ce genre transforme un nombre binaire appliqué sur son entrée en un autre nombre binaire. Le nombre de chiffres du nombre, ou mot, de sortie est en général important. Un tel générateur est, par exemple, utilisé pour effectuer un codage; l'importance du nombre des chiffres binaires du mot de sortie rend difficile le décodage non autorisé. La loi de transformation du mot d'entrée en mot de sortie n'est toutefois pas entièrement aléatoire car, s'il en était ainsi, la transformation ne serait pas reproductible et le décodage serait impossible. Mais sans connaissance de la loi de transformation celleci apparaît aléatoire. Un tel générateur est habituellement constitué par un registre à décalage et par une porte "OU exclusif" dont la sortie est connectée à l'entrée série du registre. La première entrée de la porte OU exclusif reçoit le signal d'une case de rang intermédiaire déterminé du registre et la seconde entrée de cette porte est connectée à la sortie de ce même registre. Le nombre, ou mot, d'entrée est introduit, habituellement de façon parallèle - c'est-àdire simultanément dans toutes les cases -, dans le registre. Le fonctionnement de ce dernier est commandé par un signal d'horloge. A chaque impulsion d'horloge le signal de sortie de la porte OU exclusif est introduit dans la première case du registre et le contenu de chaque case est déplacé vers la sortie, c'est-à-dire que le contenu de la case de rang m devient le contenu, avant l'impulsion d'horloge, de la case de rang m - 1. Le nombre ou mot de sortie est obtenu après un nombre déterminé, X, d'impulsions d'horloge, ce nombre X étant fixé, constant, pour un générateur pseudo-aléatoire donné. Ce mot de sortie est constitué soit par le contenu des diverses cases du registre à décalage au bout de ces X impulsions d'horloge ou par le contenu d'une fraction de ces cases, soit par une séquence série de chiffres binaires à la sortie du registre à décalage. Dans ce dernier cas la durée de la séquence, c'est-à-dire le nombre de chiffres binaires du signal de sortie, est fixée par construction du générateur pseudoaléatoire. Le mot de sortie est fonction de trois paramètres: le mot d'entrée, le rang intermédiaire de la case à laquelle est connectée la première entrée de la porte OU exclusif, et le nombre X d'impulsions d'horloge qui sépare le mot d'entrée du mot de sortie. Les deux derniers paramètres étant constants, le risque qu'une personne non autorisée puisse découvrir ces paramètres n'est pas nul. L'invention augmente la difficulté de décodage pour une personne non autorisée. A cet effet, selon l'invention, le mot de sortie apparaît après un temps t suivant l'application du mot d'entrée qui est fonction de ce mot d'entrée. De cette manière la transformation fait intervenir un paramètre supplémentaire qui rend le décodage encore plus difficile. En variante le nombre de chiffres binaires du mot de sortie dépend également de la valeur du mot d'entrée. Pour faire varier la durée t en fonction de la valeur du mot d'entrée on utilise par exemple une mémoire morte qui contient en mémoire des valeurs de durées t qu'elle restitue en fonction des valeurs de mots d'entrée qui lui sont appliqués. La loi de variation peut être également établie par programmation d'un microprocesseur. Dans le cas où le mot de sortie est parallèle et a le même nombre de chiffres binaires que le mot d'entrée, la variation de la durée t en fonction de la valeur du mot d'entrée peut être rendue encore plus complexe de la façon suivante: à l'issue d'une première durée t1, fonction de la valeur du mot d'entrée C, le mot de sortie G1 est considéré comme constituant un nouveau mot d'entrée qui fixe une nouvelle valeur t2. Une telle rupture de séquence est effectuée un nombre A de fois qui dépend, de préférence, de la valeur du mot d'entrée. Le mot de sortie GA est celui qui apparaît après ces A cycles ou ruptures de séquences. D'autres caractéristiques et avantages de l'invention apparaît tront avec la description de certains de ses modes de réalisation, celle-ci étant effectuée en se référant aux dessins ci-annexés sur lesquels: - la figure 1 est une schéma d'un générateur pseudo-aléatoire, - la figure 2 est une représentation du mot de sortie d'un générateur pseudo-aléatoire, et - la figure 3 est un organigramme de commande du générateur pseudo-aléatoire de la figure 1. Un générateur pseudo-aléatoire comporte un registre à décalage 10 formé de bascules bistables 101,102,...10N en série. L'entrée série est constituée par l'entrée de la première bascule 101 et la sortie-série est constituée par la sortie 12 de la dernière bascule 10N Chaque bascule comporte une entrée supplémentaire 111,112 1 1N sur laquelle on applique un chiffre binaire d'un mot d'entrée de type parallèle. Une sortie d'une bascule intermédiaire 10 (n n nectée à la première entrée 131 d'une porte 13 du type "OU exclusif" dont la seconde entrée 132 est reliée à la sortie 12N de la bascule 10N La sortie 133 de la porte 13 est reliée à entrée série de la bascule 101. La table de vérité de la porte OU exclusif est la suivante: 131 132 133 O 0 O 0 l l 1 0 1 1 1 0 Le fonctionnement du générateur pseudo-aléatoire est commandé par des impulsions d'horloge H appliquées sur les entrées correspondantes des bascules 101...10N. Un générateur pseudo-aléatoire classique fonctionne de la façon suivante: on applique sur les entrées parallèles 111... 11N les chiffres binaires d'un nombre C, appelé mot d'entrée. Après la première impulsion d'horloge H la bascule 101 emmagasine le signal de sortie de la porte 13, la bascule 112 emmagasine le chiffre qui se trouvait précédemment dans la bascule 111 et, de même, chacune des autres bascules stocke le contenu antérieur de la bascule précédente. Le mot de sortie apparaît après un nombre déterminé, X, d'impulsions d'horloge. Ce mot de sortie est par exemple du type parallèle, étant recueilli sur les sorties 121, 122,... 12N Il peut être également du type série: dans ce cas c'est le nombre binaire qui apparaît sur la sortie 12N à partir de la X ième impulsion d'horloge; ce nombre série a par exemple m chiffres binaires. Il est donc recueilli pendant m impulsions d'horloge. Le signal de sortie est périodique. La période est: p = (2N - 1). t: , b étant la période du signal d'horloge. Du fait du caractère périodique de la séquence S de sortie on peut représenter cette dernière par un cercle 15 (figure 2). Sur ce cercle le point 16 représente l'instant d'introduction du mot C d'entrée, le point 17 est l'instant où commence à apparaître le mot de sortie, l'intervalle de temps séparant les points 16 et 17 étant: tR = Xa t L'arc 18 représente la durée des m bits du mot de sortie lorsque celui-ci est du type série. Selon un premier aspect de l'invention le nombre X n'est pas indépendant du mot d'entrée, c'est-à-dire que la position du point 17 varie en fonction de la valeur du mot d'entrée G. Selon un second aspect de l'invention le nombre de bits du mot de sortie, c'est-à-dire le nombre m ou la longueur de l'arc 18, dépend de la valeur du mot G d'entrée. Ce second aspect peut être utilisé en combinaison avec le premier ou indépendamment de celui-ci. Pour faire dépendre le nombre X du mot G on utilise, par exemple, une mémoire morte (non représentée) qui contient en mémoire des valeurs X et sur les entrées de laquelle on applique le mot d'entrée G. Le nombre X est utilisé pour charger un registre temporel ou compteur (non représenté) dont le contenu décroît d'une unité à chaque impulsion d'horloge et qui indique la fin de la séquence quand son contenu est revenu à zéro. La loi de transformation du mot d'entrée G en un temps tR peut également etre effectuée par programmation comme décrit cidessous en relation avec la figure 3. Dans cet exemple on effectue plusieurs cycles ou ruptures de séquence pour rendre la loi de transformation de G en t encore plus complexe. La signification de l'expression "rupture de séquence" apparaîtra avec la description ci-après. La figure 3 est un organigramme qui fait partie intégrante de la présente description. Le mot d'initialisation Go est celui qui est introduit sur les entrées l1#...l 1N c'est le mot d'entrée. Au mot Go on associe un nombre A de cycles à effectuer. La transformation peut être réalisée à l'aide d'une mémoire morte ou selon une loi préétablie calculée par un ordinateur ou microordinateur. Ce mot de départ Go sert également à définir un nombre X d'impulsions d'horloge au bout duquel on effectue une rupture de séquence ou au bout duquel apparaît le mot de sortie K. Le temps tR = X (C). T est introduit dans un registre temporel sous la forme d'un nombre T. Pour que ce nombre T ne soit pas trop petit on fixe arbitrairement le bit de rang A de ce nombre T à la valeur I afin que le temps séparant les points 16 et 17 ait au moins la valeur 2 La partie 20 à gauche de l'organigramme de la figure 3 correspond au fonctionnement d'un générateur pseudo-aléatoire classique. A l'issue d'un premier cycle, c'est-à-dire lorsque le contenu du registre temporel devient nul, le temps tR s'étant écoulé, le contenu du registre dans lequel on a mis en mémoire le nombre A est diminué d'une unité et si ce contenu n'a pas alors atteint la valeur nulle le mot G' de sortie est utilisé pour définir une nouvelle durée tR. On a alors effectué une rupture de séquence. Par contre si le contenu du registre des A est nul la séquence est terminée et le contenu des diverses bascules constitue le mot C' de sortie. REVENDICATIONS 1. Générateur pseudo-aléatoire transformant un nombre binaire, ou mot, d'entrée G en un mot de sortie G', une transformation étant effectuée à chaque impulsion d'horloge H, le mot de sortie apparaissant après un nombre déterminé X d'impulsions d'horloge suivant l'application du mot d'entrée, caractérisé en ce qu'il comprend un moyen pour faire varier le nombre X d'impulsions d'horloge séparant le mot d'entrée du mot de sortie en fonction de la valeur du mot d'entrée C. 2. Générateur pseudo-aléatoire transformant un nombre binaire, ou mot, d'entrée G en un mot de sortie G', une transformation étant effectuée à chaque impulsion d'horloge H, le mot de sortie apparaissant après un nombre déterminé X d'impulsions d'horloge suivant l'application du mot d'entrée, caractérisé en ce que le nombre de chiffres binaires du mot de sortie varie en fonction de la valeur du mot d'entrée. 3. Générateur pseudo-aléatoire selon la revendication 1, caractérisé en ce qu'après l'écoulement d'un premier temps tR dont la valeur a été déterminée par la valeur du mot d'entrée G, le mot de sortie du générateur est alors utilisé pour constituer un nouveau mot d'entrée définissant un nouveau temps tR, le mot de sortie apparaissant après un nombre déterminé A de telles ruptures de séquence de sortie. 4. Générateur selon la revendication 3, caractérisé en ce que le nombre A de ruptures de séquence est variable en fonction de la valeur du mot d'entrée Go 5. Générateur pseudo-aléatoire selon l'une quelconque des revendications précédentes, caractérisé en ce que, de façon en soi connue, il comporte un registre à décalage (10) à N cases (101...10N) en série et une porte OU exclusif (13) dont la première entrée (131) est reliée à la sortie d'une case (lOn) de rang intermédiaire, la seconde sortie (132) étant reliée à la sortie (12N) de la dernière case, et la sortie (133) de cette porte étant connectée à l'entrée de la première case (l0î). 6. Générateur pseudo-aléatoire selon la revendication 5, caractérisé en ce que le mot d'entrée et le mot de sortie sont de type parallèle.