Brevet FR2641921A1 — publié le 19900720

"Dispositif générateur de séquence pseudo-aléatoire". La présente invention concerne un dispositif généra- teur de séquence pseudo-aléatoire, comprenant au moins deux registres à décalage de base montés en multiplicateurs, les décalages étant commandés par les impulsions d'une horloge, registres dont le contenu initial est prédéterminé par une clé interne, et qui sont rebouclés l'un sur l'autre avec un organe modifieur inséré dans la boucle. Un tel dispositif est connu de EP-A-O 119 972. Le dispositif décrit par ce document comporte plusieurs couples de registres dont les sorties sont combinées dans un circuit logique. Dans chaque couple, les registres sont rebouclés l'un sur l'autre avec un organe modifieur inséré dans la boucle, à savoir un commutateur qui a pour effet que, soit le registre principal est rebouclé sur lui-même, soit il est rebouclé via le deuxième registre. En outre le deuxième registre est 'per- turbé" du fait que l'horloge lui est fournie par à coups en fonction d'un comptage de bits en sortie. - Des problèmes majeurs, en matière de générateurs pseudo-aléatoires, dits GPA, sont les suivants - l'observabilité doitAtre réduite. On entend par là qu'il doit être difficile de découvrir comment le GPA fonc- tionne par observation des signaux de sortie. Dans le cas d'un générateur linéaire, de degré n, il suffit d'obserer 2n-1 éléments consécutifs d'une séquence pour caractériser complè- tement le générateur. Dans le cas de générateurs non linéai- res, il faut observer beaucoup plus d'éléments. - On peut tenter de connaitre la structure du GPA par une simulation informatique en temps réel des polynomes multiplicateurs, de leurs rebouclages, et de leur intercon- nexion, en essayant tour à tour différentes structures. Il 26 41921 faut rendre cette simulation suffisamment longue pour qu'elle devienne irréalisable en pratique. Néanmoins il ne faut pas que le dispositif matériel soit trop compliqué à réaliser. Là encore, un générateur non linéaire est plus difficile à simu- ler. - Les séquences fournies doivent avoir un caractère suffisamment aléatoire, c'est-à-dire obéir aux mêmes lois qu'une séquence réellement aléatoire (o par exemple,-zla pro- portion statistique de bits à 1 et à 0 est de 50%). Par ail- leurs la durée de cycle, c'est-à-dire la durée avant qu'on ne retrouve à nouveau une séquence identique (en supposant qu'on ne réinitialise pas les contenus) doit être suffisamment lon- gue. Dans le cas des générateurs linéaires la durée peut être maximale et constante et les séquences sont statistiquement aléatoires. Au contraire, avec des non linéarités, la durée d'un cycle est variable et il y a possibilité de dégénérescen- ce entraînant l'apparition de cycles trop courts et/ou de sé- quences statistiquement non aléatoires. L'invention a pour but de fournir un GPA qui réali- se le meilleur compromis entre les avantages contradictoires des générateurs linéaires et non linéaires. Il utilise des gé- nérateurs linéaires modifiés par des opérateurs non linéaires controlés de façon telle qu'ils entraînent peu de dégénéres- cence, ni de propriétés statistiquement non aléatoires. A cet effet, dans le dispositif selon l'invention, l'organe modifieur est une porte qui peut interrompre le transfert des bits dans au moins une partie de la boucle et qui est commandée par un signal issu d'au moins un registre à décalage rebouclé sur lui-même et indépendant des deux pre- miers. Cette porte est avantageusement une porte ET com- mandée par un signal issu d'une porte OU aux entrées de la- quelle sont amenés des bits venant chacun d'un susdit registre à décalage indépendant. Ainsi on introduit une légère non li- néarité, sans risquer de dégénérescence sensible. En outre la complexité est accrue sans dégénérescen- ce sensible si les registres indépendants sont modifiés l'un par l'autre, et si en outre cette modification est faite avec insertion d'au moins un élément non linéaire, notamment un compteur à bascule. Une deuxième caractéristique essentielle du dispo- sitif est qu'au moins l'un des deux registres de base est mo- difié linéairement par insertion de bits provenant d'une sour- ce extérieure au registre à modifier. On rend ainsi plus dif- ficile l'observation, tout en conservant les avantages des gé- nérateurs linéaires. Chaque bit modificateur peut avantageusement prove- nir d'une porte ET aux entrées de laquelle sont amenés des bits provenant de deux registres indépendants différents. Avantageusement ces deux registres indépendants sont les mêmes que ceux qui commandent l'organe modifieur de la boucle des registres de base. Alors que dans le dispositif décrit par le document EP-A-O 119 972, la séquence pseudo-aléatoire résulte d'une combinaison logique des bits de plusieurs couples de regis- tres, dans le dispositif selon l'invention, la sortie de la séquence pseudoaléatoire s'effectue sous forme parallèle en prélevant plusieurs bits à la fois à différents étages de l'un des registres à décalage c- base. On obtient ainsi des carac- téristiques très performantes, tout en n'utilisant au total que quatre registres. Les performances sont encore accrues, du fait que les bits de sortie sont modifiés linéairement, à partir de bits issus d'un ou plusieurs registre(s) indépendant(s). Ceci a pour avantage de compliquer fortement une éventuelle analyse par corrélation basée sur l'observation des sorties. En outre, dans le chemin d'au moins un bit issu du ou des registre(s) indépendant(s), est avantageusement inséré un élément non linéaire. Lorsque le dispositif est utilisé pour le chiffrage d'une émission de télévision, une horloge à fréquence plus élevée est appliquée durant certaines périodes o la fournitu- re de codes n'est pas nécessaire, la sortie de la séquence étant alors masquée, et la durée pendant laquelle cette horlo- 26 4 1921 ge à fréquence plus élevée est appliquée estelle-même déter- minée de façon pseudo-aléatoire. Ceci présente l'avantage que le nombre de coups d'horloge est beaucoup plus grand que le nombre de sorties observables, ce qui réduit dans le rapport inverse l'observabilité d'états consécutifs. La description qui va suivre, en regard des dessins annexés décrivant des exemples non limitatifs fera bien com- prendre comment l'invention peut être réalisée. La figure unique est un schéma d'ensemble du dispo- -10 sitif. Le dispositif est utilisé dans un système de télé- vision cryptée, pour engendrer un mot pseudo-aléatoire de huit bits qui définit par exemple un point de coupure dans une li- gne diimage. Huit bits sont donc nécessaires à chaque ligne, c'est-à-dire toutes les 64 microsecondes. Contrairement au système prévu dans la norme D2MAC-paquet, qui comporte une horloge à huit fois la fréquence ligne et fournit en série huit bits par ligne, le présent système fournit huit bits en parallèle et fonctionne, au moins pendant les périodes o la fourniture des codes est nécessaire, avec une horloge qui fournit une seule impulsion par ligne. A la différence du sys- tème décrit dans le document FR-A-O 119 972, o les impulsions d'horloge peuvent être interrompues semi-aléatoirement par des portes, dans le présent système tous les éléments sont activés ensemble et régulièrement par l'horloge: il est donc inutile de la représenter sur la figure. Les générateurs de fréquences pseudo-aléatoires sont basés sur l'emploi de registres à décalage, qui compor- tent une connexion de bouclage ramenant un bit lié à la sé- quence de sortie vers dés modifieurs insérés chaque fois entre deux étages du registre. Des agencements de ce type peuvent constituer des registres dits multiplicateurs, faisant réfé- rence à l'analogie mathématique selon laquelle ces registres réalisent la multiplication d'une séquence de bits fournie en série à l'entrée, par un polynome. Tous les registres du présent dispositif sont char- gés au départ par des mots créés au moyen d'un algorithme par- tant d'une clé interne associée à un chiffre transmis par l'é- metteur. Ceci ne fait pas partie de l'invention. Le dispositif est basé sur un registre multiplica- teur 1 appelé registre de base, dont est tirée la séquence pseudoaléatoire. Le polynome correspondant est d'un degré re- lativement élevé, par-exemple compris entre 40 et 70; le cycle de base est ainsi relativement long. Ce registre est un regis- tre du type à modifieurs linéaires insérés entre les étages du registre (pour mémoire, il existe une variante o les modi- fieurs sont placés dans une connexion de rebouclage). Par "modifieurs linéaires", on entend que le bit modifieur est ap- pliqué à un élément réalisant une addition modulo2 (OU exclu- sif) inséré dans la boucle. Un deuxième registre 3 est prévu. On l'appelera deuxième registre de base parcequ'il est couplé avec le pre- mier. Ce registre est aussi monté en multiplicateur avec des modifieurs linéaires insérés entre certains étages. Il peut avoir une degré beaucoup plus faible, par exemple compris en- tre 5 et 20. Au lieu que chacun de ces deux registres soit re- bouclé sur lui-même de façon habituelle, la connexion de re- bouclage de chacun d'eux est ouverte, et l'autre registre y est inséré. Ainsi la sortie 2 du registre 3 est reliée à l'en- trée 26 du registre 1, et la sortie 4 de ce dernier est reliée à l'entrée 27 du registre 3. En outre, la sortie 2 est amenée à l'entrée 26 via une porte ET 5 à deux entrées,qui peut for- cer 5es zéros dans la partie de boucle qui est à droite sur la figure. La deuxième entrée de la porte ET est commandée par un signal issu de deux registres à décalage-33,34 indépendants des deux premiers. Ces deux registres 33 et 34 sont rebouclés directe- ment, chacun sur lui-même, la sortie 20 du registre 33 étant refermée vers son entrée 7, et de même la sortie 9 du registre 34 vers son entrée 14. 26 4 1921 Les registres 33 et 34 ont par exemple des degrés plus faibles que ceux du polynome de base, et voisins l'un de l'autre, de-l'ordre de 25 à 35. A la sortie 9 du registre 34 est connecté un comp- teur à bascule 10 qui est un élément non linéaire. On appelle ici compteur à bascule un compteur dont la sortie change d'é- tat (effet de bascule) lorsqu'un nombre déterminé de bits à 1 a été compté à son entrée. Tous les compteurs à bascule du dispositif sont initialisés au départ. La sortie de la bascule 10 est combinée avec la sortie 20 du registre 33 dans une por- te "OU exclusif* dont la sortie est appliquée à l'entrée 7 du registre 33. Une disposition symétrique est obtenue grâce au compteur à bascule 11 entre la sortie 20 du registre 33 et l'entrée 14 du registre 34. Ainsi les deux registres 33 et 34 sont modifiés l'un par l'autre, et les compteurs perturbent de temps en temps la séquence. Si le compteur est un compteur par n, on a en moyenne tous les 2n coups d'horloge une inversion des bits futurs de la séquence. Les compteurs 10 et 11 ont des valeurs de comptage inégales, et peu élevées, par exemple comprises entre 4 et 12. En outre, un inverseur 35 est inséré dans l'entrée de l'un des compteurs, ici le compteur 11. Ceci a pour but que l'un des compteurs compte des zéros et l'autre des 'un", afin d'éviter un éventuel autoblocage: s'il y a beaucoup de zéros, le compteur 11 bascule et change la suite de la séquence. La seconde entrée de la porte ET 5, insérée entre les registres de base 3 et 1, est reliée à la sortie d'une porte OU 8. Une entrée de cette porte 8 est reliée à l'entrée 7 du registre 33 et l'autre entrée est reliée à la sortie 9 du registre 34. Bien entendu elles pourraient aussi bien, en va- riante, être reliées à n'importe.quel autre étage de ces re- gistres, sans changer fondamentalement le principe de fenc- tionnement. Aux entrées de la porte OU 8 sont présentées des séquences dans lequelles les 1 et les O sont équiprobables. Du fait de la fonction OU, les bits en sortie de la porte 8 sont à 1 pour les trois quarts (statistiquement). De ce fait, la porte ET 5 est fermée en moyenne pendant seulement un quart du temps: les séquences sont ainsi peu modifiées et on ne risque donc pas d'obtenir de longues séries de zéros. Des bits issus d'un élément 28 qui fournit un chif- fre provenant d'un comptage de trames de télévision sont in- troduits dans le corps du registre 3, et agissent sur des mo- difieurs linéaires (non représentés); la modification résul- tante a pour but d'éviter que la sortie soit périodique même si on réintroduit périodiquement la même clé de départ. Le registre 1 est modifié, lui aussi, mais de façon plus complexe. Le registre comporte cinq modifieurs linéaires (qui ne sont pas représentés pour ne pas compliquer la figure, leur disposition étant bien connue) à chacun desquels est ame- né un bit modificateur issu d'une porte ET 24 à 25. Les points d'insertion laissent entre eux un cer- tain nombre d'étages de registre. Les points d'insertion des bits modificateurs sont disposés de façon à laisser entre eux des blocs de registres dont les degrés sont différents et au- tant que faire se peut, premiers entre eux. Par exemple si le registre par a un degré 67, un bloc de degré 19 peut être pré- vu entre la sortie 4 et le point d'insertion du bit sortant de la porte 21, puis un bloc de degré 13 entre les points d'ap- plication de la porte 2t et de la porte 22, puis un bloc de degré 11 entre les points d'applications des portes 22 et 23, un bloc de degré 7 entre les points d'application des portes 23 et 24, un bloc de degré 17 entre les points d'application des portes 24 et 25, la sortie de la porte 25 étant elle même appliquée directement à l'entrée du registre. La somme des degrés des blocs partiels, 19 + 13 + 7 + 11 + 17 donne bien 67 qui est ici le degré du registre. Les degrés des blocs sont tous différents et premiers entre eux. Il ne faut néanmoins pas exclure à priori d'autres degrés de registre pour lesquels on ne pourrait pas trouver des valeurs qui soient toutes premières entre elles. Chacune des portes ET 21 à 25 comporte deux en- trées. Pour chaque porte, une des entrées est reliée à une sortie intermédiaire du registre 33 et l'autre à une sortie intermédiaire du registre 34. On appelle sortie intermédiaire une connexion branchée entre deux étages à l'intérieur (non représenté} d'un registre. Beaucoup d'entrées ou sorties de registres ne sont pas référencées individuellement, pour ne pas compliquer la figure, des flèches étant suffisantes pour indiquer s'il s'agit de sorties ou d'entrées. *Des portes de type ET sont choisies ici de préfé- rence, pour la rais6n suivante: avec des séquences de 1 et O équiprobables en entrée, chacune des portes ET 21 à 25 fournit des bits à 1 seulement pour un quart des bits (statistique- ment). Comme il y a cinq modifieurs, on a donc 5/4 chances de modifier, c'est-à-dire à peu près une chance par coup d'horlo- ge. De préférence les entrées d'une même porte sont re- liées à des sorties intermédiaires de rang très différent dans le registre 33 et dans le registre 34. Par exemple une porte peut être reliée à la sortie de rang 5 du registre 33 et à la sortie de rang 26 du registre 34. Bien entendu il y a une très grande variété de possibilités équivalentes, c'est pourquoi il est superflu d'indiquer pour chaque porte ET a quels rangs des registres elle est reliée. Les sorties intermédiaires ne sont pas, de préférence, équidistantes. Les deux registres 33, 34 ont donc plusieurs façons d'influencer les deux registres 3, 1. Au contraire, il n'y a aucune liaison en retour des registres 3, 1 vers les registres 33, 34. Ceux-ci sont donc indépendants des registres de base. Dans le registre 1 sont prévues cinq sorties inter- médiaires 15 à 19, qui fournissent une séquence pseudo-aléa- toire de cinq bits en parallèle. Il a été indiqué plus haut que huit bits étaient désirés. Il n'y a ici que cinq sorties. L'analyse par corréla- tion serait plus facile si l'on disposait d'un plus grand nom- bre de connexions, qui sont en quelque sorte un 'regard' sur le registre. C'est pourquoi on ne prélève que cinq bits, et on les expanse à huit par la suite. Cette expansion ne fait pas partie de l'invention. Les points de prélèvement de la séquence pseudo- aléatoire, liés aux connexions 15 à 19, d'une part, et-les points d'introduction des bits modificateurs liés aux sorties des portes 21 à 25 d'autre part, sont disposés en quinconce, c'est-à-dire que si l'on considère les blocs dont.les degrés sont premiers entre eux, qui ont été décrits plus haut, chacun - d'eux fournit une des sorties, prélevée entre deux de ses éta- ges. Une ultime précaution pour diminuer encore l'obser- 1C vabilité consiste à modifier la séquence prélevée sur le re- gistre 1, de façon linéaire, à partir de bits prélevés sur des sorties intermédiaires des deux registres indépendants 33, 34. A cet effet, sur les cinq connexions 15 à 19 sont insérées des modifieurs linéaires, c'est-à-dire des portes 'OU exclu- sif", commandés chacun par une sortie de registre. De tels mo- difieurs sont symbolisés par un signe + entouré d'un cercle. Un groupe 32 de modifieurs est associé au registre 34, et un groupe 30 est associé au registre 33. Les sorties intermédiai- res des registres 33, 34 utilisées ici ne sont pas les mêmes que celles reliées aux portes 21 à 25. Ces deux groupes de sorties peuvent par exemple, eux aussi, être disposés en quin- conce. En outre, dans chaque connexion de sortie de regis- tre est inséré un compteur à bascule 12 ou 13. Tous ceux asso- ciés à un même registre ont de préférence des valeurs de comp- tage différentes et premières entre elles, par exemple 2, 5, 7, 9, 13 ou 3, 5, 7, 11, 13, etc... Chaque sortie de compteur commande quatre portes modifiant donc quatre parmi les cinq connexions 15-19. A chaque fois, la connexion non modifiée est différente: par exemple pour le registre 34, la première sor- tie la plus à gauche sur la figure ne modifie pas la connexion , la seconde sortie ne modifie pas la connexion 16, et ainsi de suite, la cinquième sortie la plus à droite ne modifie pas la connexion 19. Ainsi la modification est linéaire. Durant certaines périodes o la fourniture de codes n'est pas nécessaire, par exemple durant les retours de trame, une horloge à fréquence plus élevée est appliquée. Cette hor- 26419 21 loge (non représentée) peut être par exemple obtenue par mul- tiplication de la fréquence ligne au moyen d'un oscillateur à boucle à verrouillage de phase. Les sorties sont masquées pendant les retours de trame, afin d'empêcher l'observation de la séquence pendant ces périodes. Pour déterminer la durée pendant laquelle est ap- pliquée l'horloge à fréquence plus élevée, on initialise un décompteur avec un nombre pseudo-aléatoire. Ce dernier est ob- tenu en prélevant quelques bits internes au GPA. Ensuite, le décompteur décompte à la fréquence de l'horloge jusqu'à zéro, après quoi l'horloge à fréquence plus élevée est arrêtée et on attend le début de-l'image pour repartir avec l'horloge à fré- quence ligne. !5E Avec la structure décrite ci-dessus et-la façon se- lon laquelle les non linéarités (à savoir les portes ET et les compteurs à bascule) sont disposées, le système est très com- plexe et néanmzins le risque de dégénérescence est faible. REVENDICATIONS: 1. Dispositif générateur de séquence pseudo-aléatoi- re, comprenant au moins deux registres à décalage de base mon- tés en multiplicateurs, les décalages étant commandés par les impulsions d'une horloge, registres dont le contenu initial est prédéterminé par une clé interne! et qui sont rebouclés l'un sur l'autre avec un organe modifieur inséré dans la bou- -cle, caractérisé en ce quel'organe modifieur est une porte qui peut forcer des zéros dans au moins une partie de la bou- cle et qui est commandée par un signal issu d'au moins un re- gistre à décalage rebouclé sur lui-même et indépendant des deux premiers. 2. Dispositif selon la revendication 1, caractérisé en ce que la porte est une porte ET commandée par un signal issu d'une porte OU aux entrées de laquelle sont amenés des bits venant chacun d'un susdit registre à décalage indépendant. 3. Dispositif selon l'une des revendications 1 ou 2, caractérisé en ce qu'il comporte deux registres dits indépen- dants qui sont modifiés l'un par l'autre. 4. Dispositif selon la revendication 3, caractérisé en ce que la modification des deux registres indépendants l'un par l'autre est faite avec insertion d'au moins un élément non linéaire. 5. Dispositif selon la revendication 4, caractérisé en ce que l'élément non linéaire est un compteur à bascule. 6. Dispositif selon la revendication 5, caractérisé en ce qu'il y a deux compteurs à bascule et qu'un inverseur est disposé en série avec un des compteurs. 7. Dispositif selon l'une quelconque des revendica- tions 1 à 6, caractérisé en ce qu'au moins l'un des deux re- gistres de base est modifié linéairement par insertion de bits provenant d'une source extérieure au registre à modifier. 8. Dispositif selon la revendication 7, utilisé pour le chiffrage d'une émission de télévision, caractérisé en ce que l'un des deux registres de base est modifié par un chiffre qui-provient du comptage des trames de l'image de télévision. 9. Dispositif selon la revendication 7, caractérisé en 264 1921 ce que l'un des deux registres de base est modifié par inser- tion de bits modificateurs provenant dudit ou desdits regis- tre(s) indépendant(s. 10. Dispositif selon la revendication 9, caractérisé en ce que chaque bit modificateur est issu d'une porte ET aux en- trées de laquelle sont amenés des bits provenant de deux re- gistres indépendants différents. 11. Dispositif selon la revendication 9, caractérisé en ce que les points d'insertion des bits modificateurs sont dis- posés de façon à laisser entre eux des blocs de registre dont les degrés sont différents et autant que faire se peut, pre- miers entre eux. 12. Dispositif selon l'une quelconque des revendica- tions précédentes, caractérisé en ce que la sortie de la sé- quence pseudoaléatoire s'effectue sous forme parallèle en pré- levant plusieurs bits à la fois à différents étages de l'un des registres à décalage de base. 13. Dispositif selon les revendications 9 et 12 ensem- ble, caractérisé en ce que les points de prélèvement de la sé- quence pseudoaléatoire, d'une part, et les points d'introduc- tion des bits modificateurs d'autre part, sont disposés en quinconce. 14. Dispositif selon la revendication 12, caractérisé en ce que les bits de sortie sont modifiés linéairement, à partir de bits issus d'un susdit registre indépendant. 15. Dispositif selon la revendication 14, caractérisé en ce que les bits de sortie sont modifiés deux fois à partir des bits issus de deux registres indépendants différents. 16. Dispositif selon l'une des revendication 14 ou 15, caractérisé en ce que, dans le chemin d'au moins un bit issu du ou des registre(s) indépendant(s), est inséré élément non linéaire. 17. Dispositif selon la revendication 16, caractérisé en ce que l'élément non linéaire est un compteur à bascule. 18. Dispositif selon l'une quelconque des revendications précédentes, utilisé pour le chiffrage d'une image de télévision, caractérisé en ce qu'une horloge à fréquence plus élevée est appliquée durant certaines périodes o la fourniture de codes n'est pas nécessaire, la sortie étant masquée durant cette période. 19. Dispositif sein la revendication 18, caractérisé en ce que l'horloge à fréquence plus élevée est appliquée pendant une durée déterminée ellemême de façon pseudo-aléatoire.