Brevet FR2727811A1 — publié le 19960607

GBNERATEUR PSHUDO-ALEATOIRB w APPLICATION A LA RADIODIFFUSION A CONTRôLE D'ACCES. L'invention se situe dans le domaine du chiffrement applicable notamment au système de radiodiffusion à contrôle d'accès. Dans cette technique, on distingue généralement le chiffrement proprement dit et l'embrouillage. Le chiffrement utilise un algorithme réversible opérant sur les données à chiffrer et, à la réception on applique aux données reçues l'algorithme inverse. Cette méthode est très efficace du point de vue sécurité mais nécessite des moyens de traitement importants et/ou des temps de calcul élevés. L'embrouillage consiste à utiliser un générateur de bits ou de mots pseudoaléatoires qui sont combinés par une opération OU EXCLUSIF avec les bits ou les mots à chiffrer. A la réception, on utilise le même générateur pseudoaléatoire dont les bits ou les mots de sortie sont combinés par l'opération OU EXCLUSIF aux données reçues, ce qui permet de restituer les données initiales.Cette méthode présente les avantages d'une réalisation simplifiée et d'un traitement rapide mais possède une sécurité limitée par le caractère cyçlique du fonctionnement du générateur pseudo-aléatoire. On peut cependant compenser cette faiblesse en modifiant de temps en temps les conditions d'initialisation du générateur au moyen d'un mot d'initialisation qui conditionne les états internes ultérieurs successifs du générateur. Comme exemple de générateur pseudo-aléatoire, on peut citer celui qui est décrit dans le brevet américain US A-5218559 (correspondant à la demande de brevet européen EP-A-0495706) qui décrit un générateur basé sur quatre polynômes générateurs irréductibles définis sur les corps de Galois d'ordre 31 et d'ordre 127. Ce type de générateur est bien adapté au chiffrement de données transmises à haut débit mais présente une certaine complexité de réalisation. Aussi, l'invention a pour but de trouver un meilleur compromis entre la complexité et les performances dans le cas ou le générateur est destiné à des applications nécessitant un débit plus faible telles que la radiodiffusion de données en onde longue, conformément à la norme française NF C 90-002 intitulée "système de diffusion de données compatible avec la radiodiffusion sonore à modulation d'amplitude". Dans ce but, l'invention a pour objet un générateur pseudo-aléatoire comprenant - des moyens d'horloge fournissant des signaux d'horloge de base, - des moyens d'initialisation pour fournir des premier et second mots d'initialisation, - des premier et second moyens de calcul initialisés respectivement par lesdits premier et second mots d'initialisation, synchronisés par lesdits moyens d'horloge de façon à se placer dans un nouvel état à chaque signal d'horloge de base, chaque état étant défini par un ensemble de valeurs binaires produit par lesdits premier et second moyens de calcul, - des moyens logiques de sortie pour engendrer un mot de sortie à partir de valeurs binaires extraites desdits premier et second moyens de calcul, ledit générateur étant caractérisé en ce que lesdits moyens d'horloge sont prévus pour fournir des seconds signaux d'horloge à une fréquence 2P fois inférieure & BR Ainsi, le circuit logique de sortie est conçu de façon à exploiter la propriété du signal à embrouiller d'être à faible débit, tout en appliquant une tres forte compression sur les états internes successifs des moyens de calcul. Ceci a pour effet qu'il est très difficile de déduire les états internes du générateur à partir de la suite délivrée en sortie puisque tres peu d'échantillons de ces états sont utilisés pour engendrer le mot de sortie. Selon un aspect particulier de l'invention, le premier opérateur logique effectue l'opération OU EXCLUSIF sur deux bits extraits respectivement desdits premier et second moyens de calcul. Selon un autre aspect, en prenant p égal à 3, le second opérateur logique fournit un premier bit extrait directement des premiers moyens de calcul, un second bit résultant de l'opération OU EXCLUSIF appliqué à deux bits extraits respectivement desdits premier et second moyens de calcul et un troisième bit extrait directement desdits seconds moyens de calcul. Les générateurs pseudo-aléatoires utilisent généralement des automates fondés sur des polynômes générateurs sur un corps de Galois. L'algorithme effectué par l'automate est équivalent à une division d'un polynôme d'entrée par le polynôme générateur et les états internes successifs de l'automate correspondent aux coefficients des restes successifs de la division. Le fonctionnement de l'automate est nécessairement cyclique, c'est-à-dire qu'au bout d'un certain nombre d'états successifs, on retrouve l'état initial et on sait que si le polynôme choisi n'est pas un polynôme primitif, la longueur du cycle dépend de l'état initial de l'automate. Il conviendra donc de veiller à ce que cet état initial ne conduise pas à des états dégénérés. Dans ce but et selon un autre aspect de l'invention, les premier et second moyens de calcul opérant sur des valeurs binaires organisées en mots de L bits, lesdits moyens d'initialisation fournissent lesdits premier et second mots d'initialisation à partir d'un mot d'entrée comprenant 2L - 2 bits et le premier mot d'initialisation est formé de L - 1 bits extraits dudit mot d'entrée et du complément d'un desdits L - 1 bit et le second mot d'initialisation est formé des L - 1 autres bits extraits dudit mot d'entrée et du complément d'un desdits L - 1 autres bits. Cette dernière disposition permet d'utiliser un mot d'entrée généré automatiquement en évitant que tous les bits des mots d'initialisation soient à 0 ou à 1, ce qui conduirait à des états dégénérés. On peut alors former le mot d'entrée à partir des informations transmises, par exemple de données horaires dans le cas du système de radiodiffusion conforme à la norme précitée. L'invention a également pour objet l'application du générateur défini précédemment dans un système de radiodiffusion pour le chiffrement à l'émission et le déchiffrement à la réception de données associées à des données horaires. Les données sont chiffrées à l'émission par des opérateurs OU EXCLUSIF portant sur les bits des données à émettre et sur les bits dudit mot de sortie, les données sont déchiffrées à la réception par des opérations OU EXCLUSIF portant sur les bits reçus et sur les bits dudit mot de sortie et les premier et second mots d'initialisation sont fonction desdites données horaires. D'autres aspects de réalisation et avantages de l'invention apparaitront dans la suite de la description en référence aux figures. - La figure 1 représente un schéma d'ensemble du générateur pseudo-aléatoire conforme à l'invention. - La figure 2 représente une réalisation détaillée du circuit d'initialisation du générateur. - Les figures 3 et 4 représentent des réalisations détaillées de deux automates faisant partie du générateur. La figure 1 représente une réalisation ciblée du générateur pseudo-aléatoire conforme à l'invention. Le générateur comporte un circuit d'initialisation CI recevant un mot d'entrée In et fournissant deux mots d'initialisation QI, RI respectivement à deux registres portant les mêmes références. Les sorties des registres QI et RI sont reliées respectivement aux entrées de deux moyens de calcul CQ et CR pouvant être les automates dont les descriptions détaillées seront données ultérieurement. Les automates CQ et CR sont synchronisés par un signal d'horloge de base CK0 fourni par des moyens d'horloge H. A chaque signal d'horloge de base CK0, sont extraits des automates CQ et CR respectivement les bits al, bl, cl et a2, b2, c2 qui servent d'entrées à un circuit logique de sortie NS.Le circuit NS est composé de deux opérateurs logiques L1, L2, d'un registre à décalage RD1 et de moyens de sélection MS. Les moyens de sélection MS sont formés d'un multiplexeur MUX et d'un second registre à décalage RD2. Le multiplexeur MUX est prévu pour recevoir p bits de commande (p étant égal à 3 dans l'exemple représenté) et N bits d'entrée, avec N = 2P. Sa sortie est reliée à l'entrée série du second registre à décalage RD2. Le registre RD2 est synchronisé par un second signal d'horloge CK1 dont la fréquence est le sous-multiple dans le rapport N de celle f0 du signal d'horloge de base CK0. La sortie parallèle du registre RD2 fournit le mot de sortie DS. Le premier opérateur logique L1 reçoit les bits al et a2 et fournit un bit de sortie sl résultant par exemple de l'opération OU EXCLUSIF appliquée aux bits reçus. Le second opérateur logique L2 reçoit les bits bl, cl, b2, c2 et fournit en sortie p valeurs binaires s2, s3, s4. Dans la réalisation représentée, s2 est égal à bl, s4 est égal b2 et s3 résulte de l'opération OU EXCLUSIF sur cl et c2. Le registre à décalage RD1 a une capacité de N bits et est synchronisé par le signal d'horloge de base CK0. Il reçoit sur son entrée série le bit sl fourni par l'opérateur L1 et sa sortie parallèle est reliée à l'entrée parallèle correspondante du multiplexeur MUX du circuit de sélection MS. Le générateur fonctionne de la façon suivante. Initialement, un mot d'entrée In est appliqué à l'entrée du circuit d'initialisation CI qui fournit les deux mots d'initialisation QI, RI à l'entrée des automates CQ et CR dont les états internes sont préalablement mis à zéro. Les moyens d'horloge H sont alors activés et, pour chaque signal d'horloge de base CKO, les automates changent d'état et les valeurs binaires al, a2 extraites alors respectivement des automates CQ, CR sont appliquées à l'opérateur Li dont la sortie sl est chargée dans le registre à décalage RD1. Au bout de N signaux d'horloge CKO, un signal d'horloge CK1 est reçu sur l'entrée d'horloge du second registre à décalage RD2 qui est alors chargé par l'un des bits contenu dans le registre RD1 et sélectionné par le multiplexeur MUX en fonction des signaux s2, s3, s4.L'opération se répète ainsi pour chaque second signal d'horloge CK1 fourni par les moyens d'horloge H et le registre à décalage RD2 se charge progressivement. L'état du registre RD2 constitue le mot de sortie DS qui peut être utilisé pour l'embrouillage des données à transmettre. La figure 2 montre le circuit d'initialisation CI dans le cas particulier où le mot d'entrée In est un octet et où les automates CQ et CR opèrent sur des mots de 5 bits. Le premier mot d'initialisation QI est obtenu à partir du premier quartet du mot d'entrée In, complété par un cinquième bit obtenu par inversion d'un des bits du premier quartet. De même, le second mot d'initialisation RI est formé du second quartet du mot d'entrée In complété par l'inverse d'un des bits de ce second quartet.Dans le cas général, pour des moyens de calcul fonctionnant sur des mots de L bits, on pourra obtenir de la même façon les mots d'initialisation à partir d'un mot d'entrée In constitué de 2L - 2 bits en formant le premier mot d'initialisation à partir de L 1 bits extraits du mot In et du complement d'un de ces bits, le second mot d'initialisation étant formé des L - 1 autres bits du mot In complétés par le complément d'un de ces autres bits. Il est clair que cette disposition assure que les mots d'initialisation QI, RI ne seront jamais formés que de 0 ou que de 1, ce qui entrainerait une dégénérescence de l'algorithme. La figure 3 montre un automate utilisable comme premier moyen de calcul CQ. Cet automate est fondé sur le polynôme générateur X5 = 2XZ + 1 défini sur le corps de Galois d'ordre 31. L'automate est constitué de cinq registres QO et Q4 de cinq bits, synchronisés par CK0, et d'un additionneur modulo 31 selon la disposition représentée sur la figure. Initialement, le registre Q2 reçoit le mot d'initialisation QI, les autres registres étant mis à zéro. Par la suite, le contenu des registres évolue à l'apparition de chaque signal d'horloge CKO. Plus précisément, les relations entre les nouvelles valeurs respectivement contenues dans les registres QO à Q4 et les anciennes valeurs avant le signal d'horloge sont les suivantes Q1, Q2, Q3 e QI, Q4, (2Q2 + QO) modulo 31. Sachant qu'une multiplication par 2 modulo 31 correspond à un décalage des bits d'un registre vers les poids forts avec rebouclage du poids fort vers le poids le plus faible, on pourra aisément vérifier que l'automate CQ représenté réalise la division du polynôme QIX5 par le polynôme générateur X5 - 2X2 - 1, les différents registres QO à Q4 contenant les coefficients des polynômes qui forment les restes successifs de la division. Comme représenté, les valeurs binaires al, bl, cl sont extraites du registre Q4. La figure 4 représente un autre automate pouvant être utilisé pour réaliser les seconds moyens de calcul CR. Cet automate est basé sur le polynôme générateur X7 = 2X + 2 défini sur le corps de Galois d'ordre 31. I1 est constitué des registres RO à R6 et d'un additionneur modulo 31 conformément à la disposition représentée sur la figure. Le registre R1 reçoit le mot d'initialisation RI et les valeurs binaires a2, b2, c2 sont extraites du registre R6. Selon la réalisation représentée, les relations entre les nouvelles valeurs respectivement contenues dans les registres R0 à R6 et les anciennes valeurs sont les suivantes R1, R2 $ RI, R3, R4, R5, R6, (2R0 + 2R1) modulo 31. Le mode de réalisation qui vient d'être décrit n'est bien entendu pas limitatif. En particulier, les valeurs binaires extraites des automates CQ et CR peuvent être en nombre quelconque ainsi que la valeur de p. De même, la dimension du registre RD2 pourra être choisie en fonction du format des données à émettre. Ce registre pourrait même être remplacé par une simple bascule si le format des données se réduit à un seul bit. Par ailleurs, on pourra en pratique utiliser aussi bien des circuits câblés que des moyens programmés équivalents pour effectuer le même algorithme et donc assurer le même résultat. Le choix entre une solution câblée ou programmée en totalité ou en partie tiendra évidemment compte du contexte d'utilisation (débit exigé), de la technologie disponible, du court et des contraintes industrielles. REVENDICATIONS 1. Générateur pseudo-aléatoire comprenant - des moyens d'horloge (H) fournissant des signaux d'horloge de base (CKO), - des moyens d'initialisation (CI) pour fournir des premier et second mots d'initialisation (QI, RI), - des premier et second moyens de calcul (CQ, CR) initialisés respectivement par lesdits premier et second mots d'initialisation (QI, RI), synchronisés par lesdits moyens d'horloge de façon à se placer dans un nouvel état à chaque signal d'horloge de base (CKO), chaque état étant défini par un ensemble de valeurs binaires produit par lesdits premier et second moyens de calcul (CQ, CR), - des moyens logiques de sortie (LS) pour engendrer un mot de sortie (DS) à partir de valeurs binaires (al, bl, cl, a2, b2, c2) extraites desdits premier et second moyens de calcul (CQ, CR), ledit générateur étant caractérisé en ce que lesdits moyens d'horloge (H) sont prévus pour fournir des seconds signaux d'horloge (CK1) à une fréquence 2P fois inférieure à celle dudit signal de base (CK0), p étant un entier positif, et en ce que lesdits moyens logiques de sortie (LS) comportent - un premier opérateur logique (L1) fournissant pour chaque signal d'horloge de base (CKO) une première valeur binaire de sortie (sl) fonction d'au moins une valeur binaire (al) extraite des premiers moyens de calcul (CQ) et d'au moins une valeur binaire (a2) extraite des seconds moyens de calcul (CR), - un second opérateur logique (L2) fournissant pour chaque signal d'horloge de base (CK0) un nombre p de secondes valeurs binaires de sortie (s2, s3, s4) fonction d'au moins une valeur binaire (bl, cl) extraite des premiers moyens de calcul (CQ) et d'au moins une valeur binaire (b2, c2) extraite des seconds moyens de calcul (CR), - des premiers moyens de mémorisation (RD1) pour mémoriser lesdites premières valeurs binaires de sortie fournies par ledit premier opérateur logique (L1) pour 2P signaux d'horloge de base (CK1) consécutifs et - des moyens de sélection (MS) pour sélectionner pour chaque second signal d'horloge (CK1) une desdites valeurs binaires mémorisées (sl) de façon à former ledit mot de sortie (DS) à partir d'au moins une desdites valeurs binaires sélectionnées. 2. Générateur pseudo-aléatoire selon la revendication 1, caractérisé en ce que ledit premier opérateur logique (L1) effectue l'opération OU EXCLUSIF sur deux bits (al, a2) extraits respectivement desdits premier et seconds moyens de calcul (CQ, CR). 3. Générateur pseudo-aléatoire selon l'une des revendications 1 ou 2, caractérisé en ce que p étant égal à 3, ledit second opérateur logique (L2) fournit un premier bit (s2) extrait directement des premiers moyens de calcul (CQ), un second bit (s3) résultant de l'opération OU EXCLUSIF appliqué à deux bits (cl, c2) extraits respectivement desdits premier et second moyens de calcul (CQ, CR) et un troisième bit (s4) extrait directement desdits seconds moyens de calcul (CR). 4. Générateur pseudo-aléatoire selon l'une des revendications 1 à 3, caractérisé en ce que lesdits moyens de mémorisation (RD1) sont constitués d'un premier registre à décalage synchronisé par lesdits signaux d'horloge de base (CK0) et dont l'entrée série reçoit ladite première valeur binaire de sortie (s0). 5. Générateur pseudo-aléatoire selon la revendication 4, caractérisé en ce que lesdits moyens de sélection comportent un multiplexeur (MUX) dont l'entrée est reliée à la sortie parallèle dudit registre à décalage (RD1), commandé par lesdites secondes valeurs binaires de sortie (s2, s3 s4) et dont la sortie est reliée à l'entrée d'une bascule ou à l'entrée série d'un second registre à décalage (RD2) synchronisés par lesdits seconds signaux d'horloge (CK1). 6. Générateur pseudo-aléatoire selon l'une des revendications 1 à 5, caractérisé en ce que lesdits premier et second moyens de calcul (CQ, CR) opèrent sur des valeurs binaires organisées en mots de L bits, en ce que lesdits moyens d'initialisation (CI) fournissent lesdits premier et second mots d'initialisation (QI, RI) à partir d'un mot d'entrée (In) comprenant 2L - 2 bits et en ce que le premier mot d'initialisation (QI) est formé de L - 1 bits extraits dudit mot d'entrée (In) et du complément d'un desdits L - 1 bit et le second mot d'initialisation (RI) est formé des L - 1 autres bits extraits dudit mot d'entrée (In) et du complément d'un desdits L - 1 autres bits. 7. Générateur pseudo-aléatoire selon la revendication 6, caractérisé en ce que L étant égal à 5, lesdits premier et second moyens de calcul (CQ, CR) sont constitués de deux automates fondés respectivement sur les polynômes générateurs X5 = 2X2 + 1 et X7 = 2X + 2 définis sur le corps de Galois d'ordre 31. 8. Application du générateur pseudo-aléatoire selon l'une des revendications 1 à 7 dans un système de radiodiffusion pour le chiffrement à l'émission et le déchiffrement à la réception de données associées à des données horaires, caractérisée en ce que lesdites données sont chiffrées à l'émission par des opérateurs OU EXCLUSIF portant sur les bits des données à émettre et sur les bits dudit mot de sortie (DS), en ce que lesdites données sont déchiffrées à la réception par des opérations OU EXCLUSIF portant sur les bits reçus et sur les bits dudit mot de sortie et en ce que lesdits premier et second mots d'initialisation (QI, RI) sont fonction desdites données horaires.