Brevet FR2619976A1 — publié le 19890303

Générateur de séquence de caractères pseudo aléatoire de grande longueur La présente invention concerne de marnière générale la production de séquences de caractères pseudo-aléatoire. Plus particulièrement, l'invention concerne des générateurs de séquence de caractères pseudo-aléatoire de grande longueur destinés à entre implantés, par exemple, dans des équipements de télécommunications chiffrées afin de crypter et de décrypter des messages. De nombreux générateurs de séquence de caractères pseudo-aléatoire sont actuellement connus. Ils ont des qualités variées tant du point de vue de leurs performances que du point de vue de leur complexité. Le meilleur compromis est assuré par les générateurs constitués de registres à décalage a contre-réaction linéaire (',liner feedback shift register" en terminologie anglo-saxonne). Dans un tel générateur, des sorties de certains étages du registre a décalage sont rebouclées 2 des entrées d'autres étages situés en amont, à travers des portes logiques, géneralement des portes OU-exclusif.Le registre est chargé à un état initial, puis un signal d'horloge est appliqué aux étages du registre afin de faire évoluer cet état-initial et de produire successivement les différents caractères de la séquence pseudo-aléatoire. I1 est ainsi possible de produire des séquences pseudo-aléatoires de longueur maximale égale à 2 - 1 caractères, où J représente le nombre d'étages du registre. Ce générateur est de faible complexité. Toutefois, il présente un inconvénient important pour son utilisation dans le domaine des télécommunications chiffrées. En effet, il a été montré que tous les détails de sa structure peuvent être déduits mathématiquement lorsqu'unie suite de 2J caractères successifs de la séquence est connue. La présente invention vise a fournir des générateurs de séquence de caractères pseudo-aléatoire de grande longueur pcu complexe et ayant des performances les rendant aptes a être utilisés dans le domaine des télécommunications chiffrées avec une garantie de secret importante des messages chiffrés. A cette fin, un dispositif de génération d'une séquence de caractères pseudo-aléatoire de grande longueur, est caractérisé en ce qu'il comprend N moyens pour produire respectivement N sous-séquences de caractères pseudo-aleatoires, où N est un entier prédéterminé, la production et la sortie de chacun des caractères d'une sous-séquence dans chacun des moyens pour produire étant commandée par un signal d'horloge respectif, des premiers moyens logiques pour établir N signaux d'horloge destinés respectivement aux N moyens pour produire, en fonction de caractères fournis en sortie par les moyens pour produire et en fonction d'un signal d'horloge prédéterminé recu par le dispositif, et des seconds moyens logiques pour établir successivement chacun des caractères de ladite séquence de caractères pseudo-aléatoire de grande longueur par combinaison logique de caractères fournis successivement et/ou simultanément en sortie par lesdits moyens pour produire. La faible complexité des générateurs selon l'invention les rend utilisables en radio-téléphonie chiffrée, notamment pour entre insérés dans des postes radiotéléphoniques individuels portatifs de faible encombrement. D'autres avantages et caractéristiques de l'invention apparaitront plus clairement à la lecture de la description suivante de plusieurs réalisations préférées du générateur selon l'invention en référence aux dessins annexés correspondants dans lesquels: - La Fig. 1 est un bloc-diagramme schématique d'un générateur de séquence de caractères pseudo-aléatoire selon l'invention; - la Fig. 2 est un bloc-diagramme détaillé d'une première réalisation préféréc du générateur, comprenant trois sous-générateurs de séquence de caractères pseudo-aleatoire; - la Fig. 3 est un bloc-diagramme détaillé d'une seconde réalisation préférée du générateur, comprenant quatre sous-générateurs de séquence de caractères pseudo-aléatoire; et - la Fig. 4 est un bloc-diagramme détaillé d'une troisième réalisation préférée du génératcur, comprenant deux sous-générateurs de séquence de caractères pseudo-aléatoire. En référence à la Fig. 1 > un générateur selon l'invention comprend de manière générale, N sous-générateurs de séquence de caractères pseudo-aléatoire 11 à 1N, où N est un entier prédéterminé notamment en fonction de la longueur de la séquence pseudo-aléatoire desirée, un circuit logique combinatoire 2, et un circuit d'aiguillage d'horloge 3. Les sous-générateurs 11 à 1N sont des dispositifs classiques connus par l'homme du métier, tels que des dispositifs de type LFSR (Linear Feedback Suif t Register) constitués de registres à décalage avec rebouclage de certains étages par des fonctions logiques OU-exclusives et d'un circuit d'initialisation. Le circuit d'initialisation dans un sous-générateur permet d'imposer des états prédéterminés dans les différentes bascules composant le ou les registres à décalage respectifs avant la mise en fonctionnement proprement dite du générateur. Les sous-générateurs 11 à 1N délivrent des sous-séquences de caractères pseudo-aléatoires S1 à SN à des entrées 211 à 21N du circuit logique combinatoire 2, respectivement.Les liaisons transmettant les caractères sortant des sous-générateurs vers les entrées du circuit 2 peuvent être des liaisons à 1 ou plusieurs fils parallèles selon que les caractères sont des bits ou des mots à plusieurs bits en parallèle. Les caractères des sous-séquences sont transférés par les sous-générateurs li à 1N vers les entrées 211 à 21N sous la commande d'un signal impulsionnel d'horloge H applique à des entrées d'horloge 111 à llN des sous-générateurs 11 à 1N à travers le circuit d'aiguillage 3. Le circuit logique combinatoire 2 délivre une séquence de caractères pseudo-aléatoire de grande longueur SS et L signaux logiques de commande d'aiguillage C1 à CL > où L est un entier au maximum égal à N. A un instant quelconque t, le caractère de la séquence SS et l'état de chacun des signaux C1 à CN délivrés par le circuit 2 sont déterminés dans le circuit 2 en fonction des caractères appliqués aux entrées 211 à 21N à ce même instant t, par des combinaisons logiques de ces caractères. Les signaux C1 à CL sont fournis à des entrées de commande du circuit d'aiguillage d'horloge 3 et commandent l'aiguillage du signal d'horloge H vers les entrées il1 à llN des sous-générateurs 1 à 1N. Ainsi à chaque instant, la modification de l'état interne d'un sous-générateur quelconque 1 parmi les N sous-générateurs 1 1 à 1N ou le n blocage à l'état interne de ce sous-générateur précédant ledit instant, et par suite le transfert d'un nouveau caractère ou du caractère sortant précédant ledit instant parce générateur aux entrées correspondantes du circuit 2, sont commandés en fonction des caractères sortants appliqués à cet instant aux entrées 211 à 21N du circuit logique combinatoire 2. De nombreuses réalisations du générateur selon l'invention sont possibles. Le nombre de ces réalisations n'est pas limité du fait que l'homme du métier peut combiner autant de sous-générateurs 1 à 1N qu'il le désire et concevoir différents circuits 2 et 3 afin de commander l'évolution de l'état interne de chacun des sous-générateurs. Des première et seconde réalisations préférées du générateur selon l'invention, décrites ci-dessous, en référence respectivement aux Figs. 2 et 3, ont une structure particulière comprenant un premier sous-générateur évoluant librement, indépendamment des autres, sous la commande directe du signal d'horloge H et de seconds sous-générateurs asservis au premier. Un avantage de cette structure consiste en la suppression de tout risque de blocage du générateur par inactivation simultanée de tous les sous-générateurs. En référence à la Fig. 2, la première réalisation préférée du générateur selon l'invention comprend N = 3 sous-générateurs, à savoir un premier sous-générateur 11 et des seconds sous-générateurs 12 e t 13, un circuit logique combinatoire 2 comprenant une porte OU-exclusif à deux entrées 22 et un inverseur 23, et un circuit d'aiguillage d'horloge 3 comprenant deux portes ET 3 deux entrées 31 et 32. Les N = 3 sous-générateurs 11 a 13 sont de type analogue et délivrent des sous-séquences de bits pseudo-aléatoires S1 à S3 respectivement aux entrées 211 à 213 du circuit 2. La porte 22 du circuit 2 a des première et seconde entrées reliées respectivement aux entrées 212 e t 213 pour recevoir les bits des sous-séquences S2 et S3 délivrées par les sous-générateurs 12 et 13. Une sortie de la porte 22 délivre une séquence de caractères pseudo-aléatoire SS dont chaque caractère est composé d'un unique bit ou, le cas échéant, d'un goupe de bits successifs. Des signaux de commande d'aiguillage C1 e t C2 sont produits à partir des bits de la sous-séquence S1 délivrés par le premier sous-générateur 1 1 à l'entrée 211 du circuit 2. Le signal C2 est constitué par la séquence de bit S1. Le signal C2 est fourni par une sortie de l'inverseur 23 ayant une entrée reliée directement à l'entrée 211 du circuit 2. Les signaux C1 et C2 sont complémentaires, C1 = C2. Les signaux C1 et C2 sont appliqués respectivement à des premières entrées des portes ET 31 et 32 du circuit d'aiguillage d'horloge 3. Des secondes entrées des portes 31 et 32 reçoivent le signal d'horloge H. Des sorties des portes 31 et 32 sont respectivement reliées aux entrées d'horloge 112 et 113 des sous-générateurs 12 et 1 L'entrée d'horloge 11 du premier sous-générateur 11 reçoit directement le signal d'horloge H. Dans cette première réalisation préférée décrite ci-dessus, du fait de la complémentarité des signaux de commande C1 et C2, les sous-générateurs 12 et 13 sont activés alternativement par le sous-générateur 11. En référence à la Fig. 3, la seconde réalisation préférée du générateur selon l'invention comprend N = 4 sous-générateurs, à savoir un premier sous-générateur 1 1 et des seconds sous-générateurs 12, 13 et 14, un circuit logique combinatoire 2a comprenant une porte OU-exclusif à trois entrées 22a trois portes OU à deux entrées 23a > 24a et 25a et trois inverseurs 26a, 27a et 28a, et un circuit d'aiguillage d'horloge 3a comprenant trois portes ET à deux entrées 31a, 32a et 33a. Le premier sous-générateur 11 reçoit directement le signal d'horloge H à l'entrée 111 et délivre en parallèle deux sous-séquences de caractères pseudo-aléatoires S1 et S1'. Une paire de caractères appartenant aux deux sous-séquences est délivrée en parallèle par le sous-générateur 11 en réponse à chaque implusion du signal H. Par exemple, une paire de caractères est composée de deux bits fournis respectivement par des première et seconde sorties du sous-générateur li lorsque celui-ci est constitué d'un dispositif de type LFSR comprenant une pluralité d'étages de 1 bit en cascade, les première et seconde sorties étant celles de deux étages prédéterminés. Les seconds sous-générateurs 12 à 14 délivrent des sous-séquences de bits pseudo aléatoires S2 à S4, respectivement aux entrées 212 à 214 du circuit 2a. La première sortie du sous-générateur 1 est reliée, à travers l'entrée 211 du circuit 2 > directement à des premières entrées des portes 23a et 25a et à travers l'inverseur 26a à une première entrée de la porte 24a. La seconde entrée du sous-générateur 11 est reliées travers une entrée 211 du circuit 2, directement à une seconde entrée de la porte 25a et à travers les inverseurs 27a ct 28a à des secondes entrées des portes 23a et 24a, respectivement. Les portes 23a à 25a fournissent respectivement des signaux de commande C1-à C3. Les signaux C1 à C3 changent d'état en réponse à chaque nouvelle paire de caractères délivrés par les sorties du sous-générateur 11, c'est à dire à chaque impulsion d'horloge du signal H.Les signaux C1 à C3 sont tels qu'au moins deux d'entre eux sont à l'état "1". Les entrées 212, 213 et 214 du circuit 2 sont reliées respectivement à des première, seconde et troisième entrée de la porte OU-exclusif 22a. La porte 22a recoit ainsi à ces entrées les sous-séquences S2, S3 et S4 établies par les sous-générateurs 12, 13 et 14. Une sortie de la porte 22a fournit la séquence SS. Les signaux C1 à C3 dans cette seconde réalisation sont respectivement appliqués à des premières entrées des portes 31a à 33a. Des secondes entrées des portes 31a è 33a reçoivent le signal d'horloge H. Des sorties des portes 31a à 33a sont respectivement reliées aux entrées d'horloge 112 à 114 des sous-générateurs 12 à 14. A chaque impulsion d'horloge du signal H, deux au moins des portes 31a à 33a sont simultanément ouvertes par les signaux C1 à C3 et délivrent le signal H aux entrées des sous-générateurs correspondants 1 En référence à la Fig. 4, une troisième réalisation préférée d'un générateur selon l'invention comprend N=2 sous-générateurs 11 et 12, un circuit logique combinatoire 2a comprenant deux portes OU-exclusif à deux entrées chacune 22b et 23b et un inverseur 24b, et un circuit d'aiguillage d'horloge 3 comprenant deux portes ET à deux entrées 31b et 32b. Les sous-générateurs 11 ct 12 sont de type analogue au sous-générateur 11 montré à la Fig. 3; ils délivrent respectivement des- paires de sous-séquences parallèles de caractères pseudo-aléatoires S1, Sl'r et 52 et S2' dans lesquelles chaque caractère est sous la forme d'un bit. Des première et seconde sorties du sous-générateur li délivrent respectivement les première et seconde sous-séquences de caractères S1 et S1' et sont reliées à travers des entrées 211 et 21' 1 du circuit 2 à des premières entrées des portes OU-exclusif 22b et 23b, respectivement. Des première et seconde sorties du sous-générateur 12 délivrent respectivement les première et seconde sous-séquences de caractères S2 et S2' et sont reliées à travers des entrées 211et 21'2 du circuit 2 à des secondes entrées des portes OU-exclusif 22b et 23b, respectivement. Une sortie de la porte 22b fournit une séquence de caractères pseudo-aléatoire SS. Une sortie de la porte 23b fournit un signal de commande C1. Un signal C2 complémentaire au signal C1 est délivré par une sortie de l'inverseur 24b dont une entrée est reliée à la sortie de la porte 23b pour recevoir le signal C1. Les signaux C1 et C2 sont appliqués à des premières entrées des portes ET 31b et 32b, respectivement. Des secondes entrées des portes 31b et 32b reçoivent le signal d'horloge H. Des sorties des portes 31b et 32b sont reliées aux entrées des sous-générateurs 11 et 12 et y appliquent le signal H sous la commande ses signaux C1 et C2, respectivement. Les signaux C1 et C2 étant complémentaires, aucun blocage n'est possible dans ce générateur et les sous-générateurs 1 1 et 12 sont activés slternativement. REVENDICATIONS 1 - Dispositif de génération d'une séquence de caractères pseudo-aléatoire de grande longueur, caractérisé en ce qu'il comprend N moyens (11 à 1N) pour produire respectivement N sous-séquences de caractères pseudo-aléatoires (S1 à SN), où N est un entier prédéterminé, la production et la sortie de chacun des caractères d'une sous-séquence (Sn) dans chacun (1n) des moyens pour produire étant commandé par un signal d'horloge respectif (11,), des premiers moyens logiques (2,3) pour établir N signaux d'horloge (111 à 11) destinés respectivement aux N moyens pour produire, en fonction de caractères fournis en sortie par les moyens pour produire (11 à 1N) et en fonction d'un signal d'horloge prédéterminé reçu par le dispositif, et des seconds moyens logiques (22; 22a; 22b) pour établir successivement chacun des caractères de ladite séquence de caractères pseudo-aléatoire de grande longueur par combinaison logique de caractères fournis successivement et/ou simultanément en sortie par lesdits moyens pour produire (11 à 1N). 2 - Dispositif conforme à la revendication 1, caractérisé en ce qu' au moins l'un desdits N moyens pour produire (11 a 1N! est commandé directement par le signal d'horloge prédéterminé (H, 111), et en ce que dans les premiers moyens logiques (2,3; 2a > 3a) > les N-l signaux d'horloge au plus (112,113; 112 à 114) commandant les N-1 moyens pour produire restants (12,13; 12 à 14) sont établis seulement en fonction du signal d'horloge prédéterminé (H) et de caractères fournis successivement et/ou simultanément, par ledit moyen pour produire (li) commandé directement par le signal d'horloge prédéterminé. 3 - Dispositif conforme à la revendication 2, caractérisé en ce qu a chaque impulsion du signal d'horloge (H) au moins deux desdits N-l moyens pour produire restants (12,13 et 14) produisent et fournissent en sortie des nouveaux caractères de sous-séquence. 4 - Dispositif conforme à la revendication 1, caractérisé en ce qu'il comprend N=2 moyens pour produire (11 et 12) commandés par des signaux d'horloge complémentaires. 5 - Dispositif conforme a l'une quelconque des revendications 1 à 4, caractérisé en ce que les caractères de la séquence de caractères pseudo-aléatoire de grande longueur sont des caractères à un bit. 6 - Dispositif conforme à la revendication 5, caractérisé en ce que lesdits seconds moyens logiques (2) établissent successivement chacun des caractères de la séquence de caractères pscudo-aléatoire de grande longueur par combinaison logique de type OU-exclusif entre les caractères fournis successivement et/ou simultanément en sortie par lesdits moyens pour produire (11 à 1N).