- « Tétromino tennis »). Il a créé et résolu d’innombrables énigmes et jeux de mots mathématiques. Il y a environ 20 ans, j'ai appris qu'il était sur le point de découvrir ma règle préférée des 30 pour les automates cellulaires en 1959, alors que je venais de naître.

Comment j'ai rencontré Saul Golomb

J'ai fait la connaissance de presque tous les scientifiques et mathématiciens que je connais grâce à mes relations professionnelles. Mais pas Sola Golomba. C'était en 1981, et moi, un physicien de 21 ans (devenu un peu célèbre dans les médias pour avoir été le plus jeune lauréat du prix MacArthur lors de la cérémonie inaugurale de remise des prix), je faisais des recherches à . On frappa à la porte de mon bureau, et bientôt une jeune femme franchit le seuil. C'était déjà inhabituel, car à l'époque où l'on étudiait la physique théorique des hautes énergies, il y avait désespérément peu de femmes. Même si j'avais vécu en Californie depuis plusieurs années, je n'avais jamais quitté le campus et j'étais mal préparé à l'explosion d'énergie du sud de la Californie qui a fait irruption dans mon bureau. La femme s'est présentée sous le nom d'Astrid et a dit qu'elle avait fréquenté Oxford et qu'elle connaissait quelqu'un avec qui j'étais à la maternelle. Elle a expliqué qu'elle avait été chargée de recueillir des informations sur des personnes intéressantes dans la région de Pasadena. Je pense qu'elle me considérait comme un cas difficile, mais elle a néanmoins insisté pour parler. Et un jour, alors que j'essayais de raconter quelque chose sur ce que je fais, elle m'a dit : " Vous devez rencontrer mon père. C'est un vieil homme maintenant, mais son esprit est toujours aussi vif qu'un rasoir. " Et il se trouve qu'Astrid Golomb, la fille aînée de Sol Golomb, me l'a présenté.

La famille Golomb vivait dans une maison située dans les montagnes près de Pasadena. Ils ont eu deux filles : Astrid - un peu plus âgée que moi, une fille ambitieuse d'Hollywood, et Béatrice - de mon âge et de mon esprit scientifique. Les sœurs Golomb organisaient souvent des fêtes, généralement chez elles. Les thèmes étaient différents : fête dans le jardin et croquet avec flamants roses et hérissons (" Le gagnant sera celui dont le costume correspondra le mieux au thème affiché."), ou une fête à la Stonehenge avec des instructions écrites en runes. Lors de ces soirées, jeunes et moins jeunes se croisaient, dont diverses sommités locales. Et chez elles, un peu à l'écart, il y avait toujours un petit homme avec une grande barbe, ressemblant un peu à un elfe et portant toujours un manteau sombre - Solomon Golomb lui-même.

Petit à petit, j'en ai appris un peu plus sur lui. Dans quoi il a été impliqué" théorie de l'information". Qu'il travaillait à l'Université de Californie du Sud. Qu'il entretenait diverses relations vagues mais apparemment de haut niveau avec le gouvernement et d'autres. J'avais entendu parler des registres de roulement, mais je n'en savais pratiquement rien.

Voici ce qui se passe après un certain temps :

Comme vous pouvez le voir, le registre à décalage décale toujours les bits vers la gauche et d'autres bits sont ajoutés vers la droite selon une règle simple. La séquence de bits semble aléatoire, même si, comme le montre la figure, elle finit par se répéter. Sol Golomb a trouvé une manière mathématique élégante d'analyser de telles séquences et leur répétition.

Si le registre à décalage a une taille n, alors il en a 2 nétats possibles (correspondant à toutes les séquences possibles de 0 et 1 de longueur n). Les règles d'un registre à décalage étant déterministes, toute position donnée doit toujours converger vers une autre position similaire. Cela signifie que le nombre maximum possible d'étapes que le registre à décalage peut parcourir avant que les étapes ne commencent à se répéter est de 2. n(en fait 2 n- 1, puisqu'une position avec uniquement des 0 ne peut évoluer vers autre chose).

Dans l'exemple ci-dessus, le registre à décalage est de taille 7 et se répétera exactement en 2 7 - 1 = 127 pas. Mais quels registres à décalage - avec quels arrangements de prises - produiront des séquences de la longueur maximale ? Solomon Golomb commença à explorer cette question dès l’été 1954. Et sa réponse fut simple et élégante.

Le registre à décalage ci-dessus a des branches aux positions 7, 6 et 1. Saul a représenté cela algébriquement en utilisant un polynôme X 7 + X 6 + 1. Il a ensuite montré que la séquence générée sera de longueur maximale si ce polynôme " irréductible modulo 2"; par conséquent, il ne peut pas être factorisé, ce qui en fait l'analogue des nombres premiers des polynômes ; et la présence de certaines autres propriétés en fait un "polynôme primitif". Aujourd'hui, cela est facile à vérifier en utilisant Mathematica et Wolfram Language :

À l’époque, en 1954, Saul devait tout faire à la main ; il a compilé un assez long tableau de polynômes primitifs correspondant à des registres à décalage produisant des séquences de longueur maximale :

Histoire des registres à décalage

L'idée de maintenir la RAM via " lignes à retard", qui transmettent des impulsions numériques, remonte au début de l'ère informatique. À la fin des années 1940, de telles lignes à retard étaient appliquées numériquement à l'aide d'une série de tubes à vide et étaient appelées " registres à décalage"On ne sait pas encore exactement quand les premiers registres à décalage ont été créés. C'était peut-être à la fin des années 1940. Cependant, cet événement reste encore entouré de mystère car ils ont été utilisés pour la première fois dans la cryptographie militaire.

L'idée de base de la cryptographie est de modifier les messages significatifs afin qu'ils ne puissent pas être reconnus ; cependant, si vous connaissez la clé, vous pouvez recréer le message chiffré. Les chiffrements dits de flux fonctionnent sur le principe de la création de longues séquences d'éléments apparemment aléatoires et sont décodés à l'aide d'un récepteur qui génère indépendamment la même séquence d'éléments.

Les registres à décalage à rétroaction linéaire étaient appréciés en cryptographie en raison de leurs longues périodes de répétition. Cependant, l’analyse mathématique utilisée par Saul pour trouver ces périodes montre clairement que de tels registres à décalage ne conviennent pas à une cryptographie sécurisée. Cependant, au début, elles semblaient plutôt bonnes (surtout en comparaison avec les positions séquentielles du rotor dans Enigma) ; des rumeurs persistantes circulaient selon lesquelles les cryptosystèmes militaires soviétiques avaient été construits sur cette base.

En 2001, alors que je travaillais sur des notes historiques pour mon livre Un nouveau type de science, Saul et moi avons eu une longue conversation au téléphone sur les changements de dossier. Saul m'a dit qu'à ses débuts, il ne connaissait rien au travail cryptographique sur registre à décalage. Il a déclaré que les gens des Bell Labs, des Lincoln Labs et du Jet Propulsion Laboratory avaient commencé à travailler sur les registres à décalage à peu près en même temps que lui ; il parvient cependant à aller un peu plus loin, ce qu'il note dans son rapport de 1955.

Au cours des années suivantes, Saul a progressivement découvert divers prédécesseurs de son travail grâce à la littérature sur les mathématiques pures. Dès 1202, Fibonacci parlait de ce qu'on appelle aujourd'hui les nombres de Fibonacci, qui sont générés par une relation de récurrence (qui peut être considérée comme analogue à un registre à décalage à rétroaction linéaire, fonctionnant sur des entiers arbitraires plutôt que sur des uns et des zéros). Il existe également de petits travaux du début des années 1900 sur la cyclicité de 0 et 1, mais la première étude à grande échelle fut celle d'Oystein Åre de l'Université d'Oslo. Ore avait un étudiant nommé Marshall Hall qui conseillait le prédécesseur de la National Security Agency à la fin des années 1940. - probablement au sujet des registres à décalage. Cependant, tout ce qu'il faisait était classifié, et il s'arrangea donc pour que Saul publie l'histoire des registres à décalage à rétroaction linéaire ; Saul a dédié son livre à Marshall Hall.

A quoi servent les séquences générées par les registres à décalage ?

J'ai remarqué à plusieurs reprises que les systèmes définis par des règles simples aboutissent à de nombreuses applications possibles ; Les registres à décalage suivent également ce modèle. Le matériel et les logiciels modernes regorgent de registres à décalage : un téléphone mobile typique en possède probablement une douzaine ou deux, généralement implémentés dans le matériel et parfois dans le logiciel (quand j'écris ici "registre à décalage", je veux dire, je veux dire registre à décalage à rétroaction linéaire -LFSR).

Dans la plupart des cas, les registres à décalage qui produisent des séquences de longueur maximale (autrement appelés " Séquences M"). Les raisons pour lesquelles ils sont utilisés sont généralement liés à certaines de leurs propriétés découvertes par Saul. Ils contiennent toujours le même nombre de 0 et de 1 (bien qu'en fait il y ait toujours exactement un 1 supplémentaire). Saul a ensuite montré qu'ils il est également courant d'avoir le même nombre de séquences 00, 01, 10 et 11 - et pour les gros blocs aussi. Cette propriété " équilibre"Cela en soi est déjà très utile - par exemple, si vous testez toutes les combinaisons possibles de bits en entrée.

Cependant, Saül découvrit une autre propriété encore plus importante. Remplacez chaque 0 de la séquence par un 1, puis multipliez chaque élément de la version décalée de la séquence par l'élément correspondant dans l'original. Saul a montré que lorsqu'ils sont ajoutés, ces éléments seront toujours égaux à zéro (sauf dans les cas où il n'y a aucun décalage). Autrement dit, la séquence n’a aucune corrélation avec les versions décalées d’elle-même.

Ces propriétés seront vraies pour toute séquence aléatoire suffisamment longue de 0 et de 1. Étonnamment, pour les séquences de longueur maximale, ces propriétés sont toujours vraies. Les séquences ont des caractéristiques chaotiques, mais en réalité elles ne le sont pas du tout : ils ont une structure bien définie et organisée.

C’est cette structure inhérente aux registres à décalage à rétroaction linéaire qui les rend impropres à une cryptographie sérieuse. Mais ils sont parfaits pour la « permutation d’éléments » de base et la cryptographie à faible coût, et sont largement utilisés à ces fins. Souvent, la tâche consiste simplement à « blanchir » le signal (comme dans le cas du « bruit blanc »). Parfois, vous devez transmettre des données avec de longues séquences de 0. Mais dans ce cas, l'électronique peut devenir confuse si le « silence » est trop long. Vous pouvez éviter ce problème en brouillant les données d'origine en les combinant avec la séquence générée par le registre à décalage. C’est exactement ce qui a été fait avec le Wi-Fi, le Bluetooth, l’USB, la télévision numérique, Internet, etc.

Un effet secondaire du brouillage des registres à décalage est un décodage plus complexe, qui est parfois utilisé pour améliorer la sécurité (la technologie DVD utilise une combinaison de registres à décalage 16 bits et 24 bits pour coder les données ; de nombreux téléphones GSM utilisent une combinaison de trois registres à décalage pour coder les données. coder tous les signaux).

Saül a créé la base mathématique de tout cela et a également présenté un certain nombre de chiffres clés. Dès 1959, il rencontre Irwin Jacobs, qui vient d'obtenir son doctorat au MIT. Il connaissait également Andy Viterbi, qui travaillait au Jet Propulsion Laboratory. Saul les présenta et en 1968 ils fondèrent une société appelée Linkabit, travaillant sur des systèmes de codage (principalement à des fins militaires).

En 1985, Jacobs et Viterbi fondent une autre société appelée Qualcomm. Au début, ils n'ont pas particulièrement bien réussi, mais au début des années 1990, lorsqu'ils ont commencé à fabriquer des composants pour déployer le CDMA dans les téléphones portables, l'entreprise a commencé à se développer rapidement.

Alors où sont ces registres ?

Il est surprenant que la plupart des gens n'aient jamais entendu parler des registres à décalage et interagissent pourtant avec eux chaque fois qu'ils utilisent des systèmes de communication modernes, des technologies informatiques, etc. Il est facile de se tromper ici, étant donné que les mêmes séquences de registres apparaissent derrière différents noms et abréviations. décalage avec retour linéaire (PN, pseudo bruit, séquences M-, FSR, LFSR, MLS, SRS, PRBS, etc.).

En ce qui concerne les téléphones mobiles, leur utilisation des séquences générées par les registres à décalage a varié au fil des années, augmentant et diminuant. Les réseaux sont basés sur TDMA, ils n'utilisent donc pas de séquences générées par des registres à décalage pour coder leurs données, mais ils utilisent encore souvent le CRC (code de redondance cyclique) pour vérifier les blocs de données. Les réseaux sont les plus grands utilisateurs de CDMA, donc les séquences générées par les registres à décalage sont impliquées dans la transmission de chaque bit. les réseaux utilisent généralement une combinaison d'intervalles de temps et de fréquence qui n'incluent pas de séquences de registres à décalage, bien que les CRC soient toujours utilisés : par exemple, pour interagir avec des données intégrales lorsque les fenêtres de fréquence se chevauchent. a une structure plus complexe - avec plusieurs antennes qui s'adaptent dynamiquement pour utiliser le temps et la fréquence optimaux des créneaux horaires. Cependant, la moitié de leurs canaux sont généralement alloués à des « signaux pilotes » qui sont utilisés pour déduire l'environnement radio local ; ils s'appuient également sur des séquences générées par des registres à décalage.

Dans la fabrication de produits électroniques, nous essayons généralement d’atteindre les débits de données les plus élevés possibles tout en utilisant un minimum d’énergie pour permettre aux bits de surmonter le bruit de fond. Et, en règle générale, cette voie conduit à l'automatisation de la détection des erreurs - et donc à l'utilisation du CRC (code de redondance cyclique) et donc des séquences générées par le registre à décalage. Cela s'applique à presque tous les types de bus à l'intérieur de l'ordinateur (PCIe, SATA, etc.) : assurant l'interaction entre les parties du processeur central, ou recevant des données des appareils, ou se connectant à un écran avec HDMI. Dans le cas des disques ou de la mémoire, les CRC et autres codes basés sur des séquences générées par des registres à décalage sont également presque universellement utilisés pour fonctionner à vitesse maximale.

Les registres à décalage sont si omniprésents qu'il est presque impossible d'estimer le nombre de bits qu'ils génèrent. Il existe environ 10 milliards d’ordinateurs, un peu moins de téléphones et un très grand nombre d’appareils dans l’IoT embarqué (« Internet des objets »). Presque toutes les voitures dans le monde (et il y en a plus d’un milliard !) sont équipées d’environ 10 microprocesseurs intégrés.

A quelle fréquence fonctionnent les registres à décalage ? Les systèmes de communication ont une fréquence porteuse de base dans la gamme Hertz, ainsi qu'un « débit de puce », qui indique la vitesse à laquelle l'accès multiple (nous parlons de CDMA) est effectué dans la gamme MHz. D'autre part, dans les bus à l'intérieur des ordinateurs, toutes les données sont transférées à l'aide de registres à décalage - avec la meilleure vitesse de transfert dans la gamme des hertz.

Il y a au moins 10 milliards de lignes de communication fonctionnant pendant au moins 1/10 milliard de secondes (environ 3 ans) qui utilisent au moins 1 milliard de bits des registres à décalage chaque seconde, ce qui signifie qu'à ce jour, l'algorithme de Saul a été utilisé au moins un octillion de fois. .

Est-ce l’algorithme le plus couramment utilisé ? Je pense que oui. Je soupçonne que seules les opérations arithmétiques peuvent rivaliser. De nos jours, les processeurs sont capables d’effectuer des milliards d’opérations arithmétiques par seconde, et de telles opérations sont nécessaires pour presque tous les bits générés par un ordinateur. Mais comment fait-on l’arithmétique ? À un certain niveau, il s’agit simplement de la mise en œuvre de l’électronique numérique.

Cependant, il existe des « idées algorithmiques » qui restent floues pour tout le monde, à l'exception des concepteurs de microprocesseurs. Lorsque Babbage a fait sa différence avec le moteur (voir l'article sur Habré "Démêler l'histoire d'Ada Lovelace (la première programmeuse de l'histoire)"), les retenues sont devenues un obstacle majeur à l'exécution d'opérations arithmétiques (en fait, un registre à décalage à rétroaction linéaire peut être considéré comme un système qui fait quelque chose comme des calculs arithmétiques mais ne les reporte pas). Il existe des « arbres de propagation de transfert » qui optimisent le transfert. Il existe également de petites astuces (comme « l'algorithme de Booth », les « arbres de Wallace », etc.) qui réduisent le nombre d'opérations sur les bits nécessaires pour créer les « éléments internes » de l'arithmétique. Mais contrairement aux registres à décalage à rétroaction linéaire, il n’existe tout simplement pas d’idée algorithmique unique pouvant être utilisée presque n’importe où ; je pense donc que les séquences les plus longues générées par les registres à décalage à rétroaction linéaire gagnent toujours parmi les séquences les plus utilisées.

Automates cellulaires et registres à décalage avec rétroaction non linéaire

Même si cela ne semble pas évident à première vue, il s’avère qu’il existe un lien étroit entre les registres à décalage et les automates cellulaires que j’étudie depuis de nombreuses années. L'organisation de base d'un registre à décalage avec rétroaction consiste à évaluer un bit à la fois. Dans un automate cellulaire, il y a une ligne de cellules, et à chaque étape, toutes les cellules sont mises à jour en parallèle, selon une règle qui dépend, par exemple, des valeurs de leurs plus proches voisines.

Pour voir comment ils sont liés, vous devez exécuter un registre à décalage avec rétroaction de taille n, et en même temps afficher son état seulement tous les n pas; en d’autres termes, laissez tous les bits être réécrits avant de réapparaître. Si chaque étape d'un registre à décalage à rétroaction linéaire est mappée (ici avec deux tapotements), alors à chaque étape, tout se déplacera vers la gauche - c'est tout. Mais si vous faites une image compressée, affichant seulement chaque nétapes, un motif deviendra visible.

Il s'agit d'un modèle imbriqué ; et cette image est très similaire à celle que l'on peut obtenir si un automate cellulaire prend une cellule et sa voisine et les ajoute modulo 2 (XOR). C'est ce qui arrive à un automate cellulaire s'il dispose ses cellules de manière à ce qu'elles forment un cercle de la même taille que le registre à décalage ci-dessus :

Au début, les automates cellulaires et les modèles de registre à décalage s’avèrent être exactement les mêmes. Si vous regardez ces images, il devient moins surprenant que les mathématiques des registres à décalage aient quelque chose à voir avec les automates cellulaires. Et étant donné la répétabilité des modèles imbriqués, il est clair pourquoi il doit exister une théorie mathématique élégante pour les registres à décalage.

Les registres à décalage typiques utilisés dans la pratique n'ont pas de motifs aussi clairement répétitifs. Voici quelques exemples de registres à décalage qui génèrent des séquences de longueur maximale. Le fait est que les branches sont très éloignées les unes des autres, ce qui rend difficile la recherche de traces visuelles de nidification.

Quelle est l’étendue de la correspondance entre les registres à décalage et les automates cellulaires ? Pour les automates cellulaires, les règles de génération de nouvelles valeurs de cellule peuvent être n'importe quoi. Dans les registres à décalage à rétroaction linéaire, ils doivent toujours être basés sur une addition modulo 2 (ou XOR). C'est ce que signifie la partie « linéaire » d'un « registre à décalage à rétroaction linéaire ». Il est également possible d'utiliser n'importe quelle règle pour combiner les valeurs des registres à décalage à rétroaction non linéaire (NFSR).

En effet, lorsque Saul a développé sa théorie des registres à décalage à rétroaction linéaire, il a commencé par le cas non linéaire. À son arrivée au JPL en 1956, il reçut un laboratoire équipé de racks pour petits modules électroniques. Saul a déclaré que les modules (chacun ayant environ la taille d'un paquet de cigarettes) ont été construits pour un projet des Bell Labs afin d'effectuer une opération logique spécifique (ET, OU, NON, ...). Les modules peuvent être utilisés ensemble pour implémenter n'importe quel registre à décalage à rétroaction non linéaire souhaité, fournissant environ un million de bits par seconde (Saul m'a dit que quelqu'un avait essayé de faire la même chose en utilisant un ordinateur central, et cela prenait 1 seconde lors de l'utilisation de modules matériels, requis 6 semaines de travail sur un ordinateur universel).

Lorsque Saul commença à étudier les registres à décalage à rétroaction linéaire, sa première découverte majeure fut leurs périodes de répétition. Et dans le cas des phénomènes non linéaires, il a consacré la plupart de ses efforts à essayer de comprendre la même chose. Il a collecté toutes sortes de données expérimentales. Il m'a dit qu'il avait même testé des séquences de 2 longueurs 45, ce qui avait pris un an. Il a fait un résumé comme l'image ci-dessous (notez la visualisation des séquences affichées sur la ligne de forme d'onde). Mais il n’a jamais été en mesure de proposer une quelconque théorie générale, comme c’était le cas pour les registres à décalage à rétroaction linéaire.

Pas étonnant qu'il n'ait pas pu le faire. Dès les années 1950, il existait des résultats théoriques (basés pour la plupart sur les idées de Turing sur l'informatique universelle) sur les programmes qui pouvaient en principe réaliser cela. Je ne pense pas que Saul ou quelqu'un d'autre ait jamais pensé que les registres à décalage à rétroaction non linéaire utiliseraient des fonctions très simples (non linéaires).

Ce n’est que plus tard qu’on s’est rendu compte à quel point le comportement de programmes, même très simples, pouvait être complexe. Mon exemple préféré est la règle 30 pour un automate cellulaire, dans laquelle les valeurs des cellules voisines sont combinées à l'aide d'une fonction qui peut être représentée comme R. + q + r + q*r module 2(ou R. XOR ( q OU r)). Étonnamment, Saul envisageait des registres à décalage à rétroaction non linéaire basés sur des fonctions similaires : R. + g + s + q*r + q*s + r*s module 2. Voici ci-dessous des illustrations de ce à quoi ressemblent la fonction de Saul (qui peut être considérée comme la « règle 29070 »), la règle 30 et plusieurs autres règles similaires dans un registre à décalage :

Et ici, non limités par un registre de taille fixe, ils ressemblent à des automates cellulaires :

Bien sûr, Saul n’a jamais réalisé de telles images (et c’était presque impossible à faire dans les années 1950). Au lieu de cela, il s’est concentré sur la période de redoublement comme une sorte de caractéristique globale.

Saul se demandait si les registres à décalage avec rétroaction non linéaire pouvaient être des sources de chaos. D’après ce que l’on sait actuellement sur les automates cellulaires, il est clair que c’est possible. Par exemple, pour créer le chaos pour Mathematica, nous avons utilisé la règle des 30 automates cellulaires pendant 25 ans (bien que nous l'ayons récemment abandonnée au profit d'une règle plus efficace que nous avons trouvée après avoir étudié des milliards de possibilités).

Saul n'a pas beaucoup parlé de chiffrement ; même si je pense qu'il n'a travaillé pour le gouvernement que pendant une courte période. Il m'a dit que même si en 1959 il avait découvert " attaques de corrélation multidimensionnelle sur des séquences non linéaires"en même temps il" soigneusement évité les affirmations selon lesquelles le programme était destiné à la cryptanalyse"Le fait est que la règle 30 pour les automates cellulaires (et peut-être aussi les registres à décalage à rétroaction non linéaire) peuvent être de bons cryptosystèmes - bien qu'en raison du fait qu'ils sont apparemment équivalents aux registres à décalage à rétroaction linéaire (ce qui n'est pas le cas), ils n'ont jamais été utilisés. autant que possible.

En tant que passionné, j'ai essayé au cours des dernières décennies d'étudier tous les prédécesseurs de mes travaux sur les automates cellulaires unidimensionnels. Les automates cellulaires bidimensionnels ont été peu étudiés, mais dans le cas des automates cellulaires unidimensionnels, un seul travail purement théorique a été trouvé. Je pense à tout ce que j'ai vu, les registres à décalage à rétroaction non linéaire de Solomon Golomb étaient les plus proches de ce que j'ai fini par faire un quart de siècle plus tard.

Polyomino

En entendant le nom " Golomb ", beaucoup se souviendront des registres à décalage. Cependant, la plupart se souviendront polyomino. Saul n’a pas inventé les polyominos, bien qu’il en ait trouvé le nom. Il a systématisé ce qui n'apparaissait auparavant que dans des puzzles individuels.

La principale question à laquelle Saul souhaitait répondre était de savoir comment des ensembles de polyominos pouvaient être organisés pour couvrir une certaine zone. Parfois c’est assez évident, et parfois c’est assez difficile. Saul a publié son premier article sur les polyominos en 1954, mais c'est Martin Gardner qui a vraiment rendu les polyominos populaires en 1957 (il a écrit une chronique sur les jeux mathématiques dans le magazine Américain scientifique). Comme Saul l'expliquait dans la préface de son livre de 1964, le résultat fut " un flux constant de correspondants du monde entier et de tous horizons : présidents de conseils d'administration de grandes universités, résidents de monastères inconnus, prisonniers de prisons célèbres...".

Les sociétés de jeux vidéo ont également remarqué les nouvelles énigmes et, quelques mois plus tard, des titres tels que " de nouveaux puzzles sensationnels", suivi de décennies d'autres puzzles et jeux basés sur le polyomino (non, le chauve effrayant ne ressemble pas à Saul) :

Saul a continué à publier des articles sur les polyominos pendant encore 50 ans après la première publication. En 1961, il introduisit les « rep-tiles » qui pouvaient être utilisés pour créer des motifs fractals (« Infin-tile »). Mais presque tout ce que Saül faisait avec les polyominos impliquait de résoudre des problèmes spécifiques.

Je m'intéresse peu aux spécificités des polyominos ; Je m'intéresse aux phénomènes plus généraux qui leur sont associés. Il semble qu'il soit facile de décider s'il est possible de « carreler » tout l'avion à l'aide de quelques formes simples. Mais avec les polyominos (et tous les jeux et puzzles basés sur ceux-ci), force est de constater que les choses ne sont pas si simples. En effet, dans les années 1960, il a été prouvé que ce problème était théoriquement insoluble.

Si nous ne nous intéressons qu'à un domaine limité, nous pouvons en principe simplement énumérer toutes les dispositions imaginables des figures, puis voir si elles sont disposées comme elles devraient l'être. Cependant, si nous nous intéressons à l’infini, cela n’est pas nécessaire. Peut-être que quelqu'un trouvera un moyen de placer avec succès un million de chiffres, mais rien ne garantit que ce résultat puisse être étendu davantage.

Il s’avère que cela pourrait ressembler à une machine de Turing en état de marche – ou à un automate cellulaire. Vous commencez avec une ligne de tuiles. Alors la question de savoir si le pavage infini est possible équivaut à la question de savoir s’il est possible de mettre en place une machine de Turing qui lui permettra de ne pas s’arrêter. Le fait est que si une machine de Turing est universelle (c'est-à-dire qu'elle peut être programmée pour effectuer n'importe quel calcul possible), alors le problème d'arrêt de celle-ci peut être indécidable, ce qui signifie que le problème de pavage sera également indécidable.

Bien entendu, cela dépend de l’ensemble de formulaires d’origine. La question est de savoir dans quelle mesure les formes doivent être complexes pour coder des calculs universels et conduire à un problème de pavage insoluble. Solomon Golomb connaissait la littérature sur ce sujet, mais ne s'y intéressait pas particulièrement.

On sait que des ensembles complexes et soigneusement conçus de polyominos prennent réellement en charge le calcul universel. Mais qu’en est-il d’un simple ensemble ? Est-ce vraiment assez simple pour qu’on tombe dessus par hasard ? Si vous regardez tous les systèmes que j'ai étudiés, l'ensemble le plus simple s'avère vraiment simple. Il est cependant difficile à trouver.

Un problème beaucoup plus simple consiste à trouver des polyominos qui remplissent avec succès les plans, bien que de manière non périodique. Roger Penrose a trouvé un exemple approprié en 1994. Dans mon livre Un nouveau type de science J'ai donné un exemple un peu plus simple avec 3 polyominos :

Le reste de l'histoire

Saul était au début de la trentaine lorsqu'il a obtenu des succès notables dans le domaine des registres à décalage et des polyominos... C'était une personne très active. Il a écrit plusieurs centaines d'articles, dont certains développaient ses travaux antérieurs, d'autres étaient des réponses aux questions qui lui avaient été posées, et certains étaient écrits, semble-t-il, juste pour le plaisir - pour découvrir des choses intéressantes sur les nombres, les séquences. , cryptosystèmes, etc. d.

Les registres à décalage et les polyominos sont des sujets étendus (ils sont même classés dans des catégories distinctes dans la classification AMS). Au cours des dernières décennies, ils ont tous deux connu un nouveau cycle de développement lorsque des expériences informatiques ont commencé à être menées sur leur base ; Sol y a également pris une part active. Cependant, de nombreuses questions restent sans réponse. Et si de grandes matrices de Hadamard peuvent être trouvées pour les registres à décalage avec rétroaction linéaire, alors encore aujourd'hui, on sait peu de choses sur les registres à décalage avec rétroaction non linéaire, sans parler de tous les polyominos non périodiques et autres polyominos exotiques.

Saul a toujours été intéressé par les puzzles, tant mathématiques que de mots. Pendant un certain temps, il a écrit une chronique de puzzles pour Los Angeles Times, et pendant 32 ans a écrit " Les Gambits de Golomb" dans le magazine des anciens élèves de Johns Hopkins. Il a participé aux tests MegaIQ et a remporté un voyage à la Maison Blanche lorsque lui et son patron ont été classés parmi les cinq meilleurs du pays.

Il a investi d'énormes efforts dans son travail à l'université : non seulement il a enseigné aux étudiants de premier cycle, encadré des étudiants des cycles supérieurs et gravi les échelons administratifs (président du conseil universitaire, vice-recteur à la recherche, etc.), mais il a également exprimé ses opinions sur la gestion de l’université dans son ensemble (par exemple, il a écrit un article intitulé « Conseil aux professeurs : supprimer ou partir ? » ; réponse : non, c’est bon pour l’université !). À l'Université de Californie du Sud, il était chasseur de têtes et, pendant son séjour là-bas, il a aidé l'université à sortir de l'obscurité pour se hisser au sommet du classement des programmes éducatifs.

Et puis il y a eu la consultation. Saul était méticuleux et n'a pas révélé ce qu'il faisait pour les organisations gouvernementales. À la fin des années 1960, frustré par le fait que tout le monde, sauf lui, vendait des jeux polyomino, Saul fonda une société qu'il appela Recreational Technology, Inc. Les choses n'allaient pas très bien, mais Saul a rencontré Alvin Berlekamp, ​​​​un professeur de Berkeley qui s'intéressait aux théories et aux énigmes du codage. Ils fondent par la suite la société Cyclotomics (en l'honneur des polynômes cyclotomiques de la forme X n– 1), qui fut finalement revendu à Kodak pour une coquette somme (Berlekamp créa également un système de trading algorithmique, qu'il revendit ensuite à Jim Simons et qui devint le point de départ de Renaissance Technologies, l'un des plus grands hedge funds actuels).

Plus de 10 000 brevets sont liés d’une manière ou d’une autre au travail de Saul, mais Saul lui-même n’a reçu que un brevet sur des cryptosystèmes quasi-groupes - et je pense qu'il a peu fait pour commercialiser son travail.

Pendant de nombreuses années, Saul a travaillé avec le Technion, un institut israélien de technologie. Il parlait de lui-même comme " juif orthodoxe non religieux", mais en même temps il donnait parfois des séminaires sur le Livre de la Genèse pour les débutants, et travaillait également au déchiffrement de parties des manuscrits de la mer Morte (manuscrits de Qumran).

Saul et sa femme ont beaucoup voyagé, mais le « centre du monde » de Saul était sans aucun doute son bureau à Los Angeles, à l'Université de Californie du Sud, et la maison où lui et sa femme ont vécu pendant près de 60 ans. Il était toujours entouré d'amis et d'étudiants. Et il avait une famille. Sa fille Astrid a joué le rôle d'une étudiante dans une pièce sur Richard Feynman (elle a posé pour lui) et dans le roman d'un ami comme l'un des personnages. Béatrice a consacré sa carrière à appliquer un niveau de précision mathématique à divers types de conditions médicales et de diagnostics (maladies liées à la guerre du Golfe, effets des statines, hoquet, etc.). J'ai même apporté une petite contribution à la vie de Béatrice en lui présentant l'homme qui deviendra plus tard son mari : Terry Sejnowski, l'un des fondateurs de la neuroscience computationnelle moderne.

Saul semblait impliqué dans beaucoup de choses, même s'il ne parlait pas trop des détails. De temps en temps, j'avais envie de lui parler de sciences et de mathématiques, mais il était plus intéressé à raconter des histoires (souvent très passionnantes) sur les individus et les organisations." Pouvez-vous croire que [en 1985], après des années d'absence aux conférences, Claude Shannon s'est simplement présenté à l'improviste au bar lors de la conférence annuelle sur la théorie de l'information ?"; "Savez-vous combien ils ont dû payer le directeur de Caltech pour qu'il aille en Arabie Saoudite ?", etc.).

Avec le recul, je me rends compte que j’aurais aimé intéresser Saul à la résolution de certaines des questions mathématiques soulevées dans mon travail. Je ne pense pas avoir jamais réalisé à quel point il aimait résoudre les problèmes proposés par d'autres personnes. Malgré ses contributions significatives à l’infrastructure du monde informatique, Saul lui-même n’a jamais sérieusement utilisé les ordinateurs. Il était très fier de pouvoir facilement faire des calculs dans sa tête. Jusqu'à l'âge de 70 ans, il n'utilisait pas de courrier électronique et n'utilisait jamais d'ordinateur à la maison, même s'il possédait un téléphone portable (il ne recevait presque jamais de courrier électronique régulier. J'ai mentionné une fois qu'il y a environ un an, j'étudiais l'histoire d'Ada Lovelace. ; il a répondu: " L'histoire d'Ada Lovelace en tant que programmeuse de Babbage est si répandue que tout le monde semble l'accepter comme un fait, et pourtant je n'ai jamais vu de sources sur le sujet.").

Les filles de Saul ont organisé une fête pour son 80e anniversaire il y a quelques années et ont créé ces invitations intéressantes :

Sol avait quelques problèmes de santé, même si cela ne semblait pas affecter beaucoup son rythme de vie. La santé de sa femme s'était détériorée assez fortement ces dernières semaines. Vendredi, Saul s'est rendu à son bureau comme d'habitude et samedi soir, il est mort dans son sommeil. Sa femme Bo ne lui a survécu que deux semaines et est décédée deux jours seulement avant leur 60e anniversaire de mariage.

Bien que Saul soit parti, son travail perdure en octillions de fragments dans le monde numérique.

Au revoir Sol. Et de la part de nous tous, merci.



Registre à décalage de rétroaction se compose de deux parties : un registre à décalage et fonctions de rétroaction.

Figure 19. Registre à décalage de rétroaction.

En général, un registre à décalage est une séquence de certains éléments en anneau ou en champ. Le plus souvent utilisé peu registres à décalage. La longueur d'un tel registre est exprimée en nombre de bits. Chaque fois qu'un bit est récupéré, tous les bits du registre sont décalés d'une position vers la droite. Le nouveau bit de poids fort est calculé en fonction de tous les autres bits du registre. La sortie est généralement le bit le moins significatif. La période du registre à décalage est la durée de la séquence de sortie avant qu'elle ne commence à se répéter.

Le type de registre à décalage le plus simple est un registre à décalage à rétroaction linéaire (LFSR ou LRS). La rétroaction est une simple opération XOR sur certains bits de registre. La liste de ces bits est déterminée polynôme caractéristique et s'appelle séquence de coups. Parfois, ce schéma est appelé Configuration de Fibonacci.

Figure 20. Configuration RSLOS de Fibonacci.

Lors de l'implémentation de LFSR dans le logiciel, un schéma modifié est utilisé : pour générer un nouveau bit significatif, au lieu d'utiliser les bits de la séquence de prises, une opération XOR est effectuée sur chacun de ses bits avec la sortie du générateur, remplaçant l'ancien bit de la séquence de frappe. Cette modification est parfois appelée Configuration galoisienne.

Figure 21. RSLOS de configuration Galois.

n-bit LFSR peut être dans l'un des 2 n– 1 états internes. Cela signifie que théoriquement un tel registre peut générer une séquence pseudo-aléatoire d'une période de 2 n– 1 bits (le remplissage avec des zéros est totalement inutile). Passage des 2 n– Les états internes 1 ne sont possibles qu'avec certaines séquences de prises. De tels registres sont appelés LFSR avec une période maximale. Pour assurer la période maximale du SFSR, il faut que son polynôme caractéristique soit primitif modulo 2. Le degré du polynôme est la longueur du registre à décalage. Polynôme de degré primitif n- C'est tellement irréductible un polynôme qui est un diviseur mais qui n'est pas un diviseur xd+ 1 pour tout le monde d, qui sont des diviseurs de 2 n– 1. (Lorsqu’on parle de polynômes, le terme nombre premier est remplacé par le terme polynôme irréductible). Le polynôme caractéristique du LFSR représenté sur les figures :

X 32 + X 7 + X 5 + X 3 + X 2 + X + 1

est primitive modulo 2. La période d'un tel registre sera maximale, passant cycliquement par toutes les valeurs 2 32 – 1 avant qu'elles ne soient répétées. Les plus couramment utilisés sont les polynômes amincis, c'est-à-dire qui n'ont que quelques coefficients. les plus populaires sont les trinômes.

Un paramètre important d'un générateur basé sur RSLOS est complexité linéaire. Elle est définie comme la longueur n le HFSR le plus court capable de simuler la sortie du générateur. La complexité linéaire est importante car l'utilisation de simples Algorithme de Berlenkamp-Massey vous pouvez recréer un tel LFSR en cochant seulement 2 n bits gamma. Une fois le RFSL requis déterminé, le chiffrement de flux est réellement craqué.

Le type de fonction de rétroaction le plus simple est une fonction linéaire, par exemple la somme modulo 2 du contenu de certains bits. Ce registre est appelé registre à décalage à rétroaction linéaire (LFSR). En général, la fonction de rétroaction linéaire est donnée par la formule. Ici ck= 1 si k Le ème bit est utilisé dans la fonction de retour, et ck= 0 sinon. Le symbole Å désigne l'addition modulo 2 (OU exclusif).

Par exemple, considérons un LFSR avec une fonction de retour (voir figure).

Si l'état initial du registre est 1111, alors dans les cycles d'horloge suivants, il prendra la série d'états suivante : 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110, 1111, ...

La séquence de sortie est formée à partir du bit le moins significatif (le plus à droite) du registre. Cela ressemblera à ceci : 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. On peut voir que la séquence de bits générée est entièrement déterminée par l'état initial du registre et la fonction de retour. Puisque le nombre d'états de registre possibles est fini (il est égal à 2 L), puis tôt ou tard, la séquence de touches commencera à se répéter. La longueur maximale d'une partie non répétitive d'une séquence de touches est appelée son point T. La période dépend de la fonction de rétroaction. La période maximale possible est T maximum = 2 L-1 (le registre accepte tous les états possibles sauf 0000...0). La séquence de sortie du LFSR ayant la période maximale est appelée Séquence M.

Pour connaître les conditions dans lesquelles le LFSR aura une période maximale, les fonctions de feedback attribuent un polynôme caractéristique. Ainsi, le registre donné ci-dessus à titre d'exemple correspond à un polynôme. L'analyse théorique montre que le LFSR aura une période maximale si et seulement si le polynôme P.(X) est primitif. Vous trouverez ci-dessous quelques polynômes primitifs recommandés pour une utilisation pratique. Le tableau montre les puissances de la variable X en notation polynomiale. Par exemple, l'entrée (31, 3) correspond à un polynôme.

№	P.(X)	№	P.(X)	№	P.(X)
	(39, 16, 23, 35)		(38, 5, 6, 27)		(32, 2, 7, 16)
	(30, 6, 4, 1)		(31, 6)		(31, 7)
	(31, 13)		(31, 25, 23, 8)		(33, 13)
	(35, 2)		(47, 5)		(48, 9, 7, 4)
	(47, 11, 24, 32)		(46, 18, 31, 40)		(53, 6, 2, 1)
	(55, 24)		(57, 7)		(58, 19)
	(59, 7, 4, 2)		(41, 27, 31, 32)		(61, 5, 2, 1)
	(42, 30, 31, 34)		(51, 15, 24, 46)		(50, 17, 31, 34)

Les LFSR ont été initialement conçus pour être implémentés dans le matériel sous la forme d'un ensemble de circuits numériques. Les implémentations logicielles de LFSR sont généralement inférieures en vitesse aux implémentations matérielles. Pour augmenter les performances, il est avantageux de stocker l'état du registre sous forme d'entier L-numéro de bit dont les bits individuels correspondent aux bits binaires du registre. Ensuite, des opérations au niveau du bit (décalage, masquage, etc.) sont utilisées pour accéder aux bits individuels.

décryptage - p i = D (k i, c i), comme le montre la Fig. 7.21.

Riz. 7.21.

Les chiffrements par flux sont plus rapides que les chiffrements par blocs. L’implémentation matérielle d’un chiffrement de flux est également plus simple. Lorsque nous devons chiffrer des flux binaires et les transmettre à une vitesse constante, le meilleur choix est d’utiliser un chiffrement de flux. Les chiffrements de flux offrent une meilleure protection contre la corruption des bits pendant la transmission.

Dans un chiffrement de flux moderne, chacun r Le mot de 3 bits dans le flux de texte brut est chiffré à l'aide de r -mot de bits dans le flux de clés pour créer le mot correspondant r mot de 3 bits dans le flux de texte chiffré.

Riz. 7.22.

Un tampon à usage unique est le chiffre parfait. Il est parfait. Il n’existe aucune méthode permettant à un adversaire de reconnaître la clé ou les statistiques du texte chiffré et du texte en clair. Il n'y a aucune relation entre l'original et le texte chiffré. En d’autres termes, le texte chiffré est un véritable flux aléatoire de bits, même si certains échantillons du texte original sont obtenus. Eve ne peut pas déchiffrer le chiffre à moins d'essayer tous les flux de clés aléatoires possibles, qui seraient 2n si la taille du texte en clair était de n bits. Cependant, cela pose un problème. Pour que l'émetteur et le récepteur partagent un clavier unique, ils doivent établir une connexion chaque fois qu'ils souhaitent échanger des informations. Ils doivent d’une manière ou d’une autre se mettre d’accord sur une clé aléatoire. Ce chiffre parfait et idéal est donc très difficile à mettre en œuvre.

Exemple 7.17

Quelle est la forme du texte chiffré lors de l’utilisation du chiffrement à tampon unique dans chacun des cas suivants ?

UN. Le texte source est composé de n zéros.

b. Le texte source se compose de n unités.

V. Le texte source consiste en une alternance de zéros et de uns.

d. Le texte source est une chaîne aléatoire de bits.

Solution

un. Parce que le , alors le flux de texte chiffré correspondra au flux de clé. Si la clé est aléatoire, le texte chiffré est également aléatoire. Certaines parties du texte original ne sont pas stockées dans le texte chiffré.

b. Parce que le , où est le complément du flux de texte chiffré est le complément du flux de clé. Si le flux de clés est aléatoire, alors le texte chiffré est également aléatoire ; des parties du texte original ne sont pas stockées dans le texte chiffré.

c. Dans ce cas, chaque bit du flux de texte chiffré est soit le même que celui du flux de clé, soit son complément. Par conséquent, le résultat est également aléatoire si le flux de clés est aléatoire.

d. Dans ce cas, le texte chiffré est clairement aléatoire car l’exécution d’une opération XOR sur deux bits aléatoires entraîne un flux aléatoire de bits.

Registre à décalage de rétroaction

Une amélioration du pad unique est (FSR - Feedback Shift Register). FSR peut être implémenté sous forme logicielle ou matérielle, mais pour des raisons de simplicité, nous considérerons l'implémentation matérielle. Registre à décalage de rétroaction comprend registre à décalage et fonctions de rétroaction, comme le montre la fig. 7.23.

Riz. 7.23.

Un registre à décalage est une séquence de m cellules de b 0 à b m-1, où chaque cellule est conçue pour stocker un seul bit. Les cellules sont traitées comme un mot de n bits, appelé au début « valeur de départ » ou source. Chaque fois qu'un bit doit être émis (par exemple, à partir d'un signal à un certain moment), chaque bit est décalé d'une cellule vers la droite. Cela signifie que la valeur de chaque cellule est attribuée à la cellule adjacente droite et prend la valeur de la cellule gauche. La cellule la plus à droite b 0 est considérée comme la sortie et donne la valeur de sortie (k i ). La cellule la plus à gauche, b m-1, obtient sa valeur en fonction de la valeur des informations de la fonction de rétroaction. Nous désignons la sortie de la fonction avec des informations de rétroaction b m . La fonction d'information de retour détermine les valeurs que les cellules doivent calculer b m . Le registre à décalage d'informations de rétroaction peut être linéaire ou non linéaire.

Registre à décalage à rétroaction linéaire (LFSR). Supposons que b m est une fonction linéaire b 0, b 1,…..., b m-1, pour laquelle

Un registre à décalage à rétroaction linéaire fonctionne sur des chiffres binaires, donc la multiplication et l'addition se font dans le champ GF(2), donc la valeur de C i est soit 1, soit 0, mais C 0 doit être 1 pour obtenir des informations de rétroaction à la sortie. L’opération d’addition est une opération OU EXCLUSIF. Autrement dit,

Exemple 7.18

Construisons un registre à décalage à rétroaction linéaire avec 5 cellules, dans lequel .

Solution

Si C i = 0, b i ne joue pas de rôle dans le calcul de b m, alors cela signifie que b i n'est pas associé à la fonction d'information de retour. Si c i = 1, b i est inclus dans le calcul de b m. Dans cet exemple, c 1 et c 3 sont des zéros, ce qui signifie que nous n'avons que trois connexions. La figure 7.24 montre le circuit d'un registre à décalage à rétroaction linéaire.

Riz. 7.24.

Exemple 7.19

Construisons un registre à décalage à rétroaction linéaire avec 4 cellules, dans lequel . Afficher la valeur du registre après 20 opérations (équipes), si la valeur d'origine est (0001) 2 .

Solution

La figure 7.25 montre la conception et l'utilisation d'un registre à décalage linéaire en boucle fermée pour le chiffrement.

Riz. 7.25.

Tableau 7.6. affiche la valeur du flux de clés. Pour chaque transition, la première valeur de b4 est calculée, puis chaque bit est décalé d'une cellule vers la droite.

Tableau 7.6.

valeur actuelle	b4	b3	b2	b1	b 0	ok je
Valeur initiale	1	0	0	0	1
1	0	1	0	0	0	1
2	0	0	1	0	0	0
3	1	0	0	1	0	0
4	1	1	0	0	1	0
5	0	1	1	0	0	1
6	1	0	1	1	0	0
7	0	1	0	1	1	0
8	1	0	1	0	1	1
9	1	1	0	1	0	1
10	1	1	1	0	1	0
11	1	1	1	1	0	1
12	0	1	1	1	1	0
13	0	0	1	1	1	1
14	0	0	0	1	1	1
15	1	0	0	0	1	1
16	0	1	0	0	0	1
17	0	0	1	0	0	0
18	1	0	0	1	0	0
19	1	1	0	0	1	0
20	1	1	1	0	0	1

Notez que le flux de clé est 1000100110101111 1001……. Cela ressemble, à première vue, à une séquence aléatoire, mais si l’on regarde un grand nombre de transactions (shifts), on constate que les séquences sont périodiques. Cette répétition de 15 bits est illustrée ci-dessous.

La clé de flux est générée à l'aide d'un registre à décalage à rétroaction linéaire séquence pseudo-aléatoire, dans lequel des séquences de longueur N sont répétées. Le flux est périodique. Cela dépend du circuit du générateur et des informations initiales et ne peut pas dépasser 2 m – 1. Chaque circuit génère des séquences de m bits allant de celles contenant uniquement des zéros à celles contenant uniquement des un. Cependant, si la séquence initiale est uniquement composée de zéros, le résultat est inutile : le texte original serait un flux composé uniquement de zéros. Une telle séquence initiale est donc exclue.

Dans un registre à décalage à rétroaction linéaire, il y a deux parties (modules) : le registre à décalage lui-même et les circuits (ou sous-programmes) qui calculent la valeur du bit poussé. Un registre est constitué de cellules fonctionnelles (ou de bits d'un mot machine ou de plusieurs mots), dont chacune stocke l'état actuel d'un bit. Le nombre de cellules est appelé longueur du registre. Les bits (cellules) sont généralement numérotés avec des nombres, chacun étant capable de stocker un bit, et le bit calculé est poussé dans la cellule, et le bit généré suivant est supprimé de la cellule. Le calcul du bit à pousser est généralement effectué avant le décalage du registre, et ce n'est qu'après le décalage que la valeur du bit calculé est placée dans la cellule.

La période du registre à décalage est la longueur minimale de la séquence résultante avant qu'elle ne commence à se répéter. Puisqu'un registre de cellules binaires n'a que des états différents non nuls, alors, en principe, la période du registre ne peut pas dépasser ce nombre. Si la période du registre est égale à ce nombre, alors un tel registre est appelé registre de période maximale.

Pour LFSR, la fonction de retour est une fonction booléenne linéaire des états de tout ou partie des bits du registre. Par exemple, la somme modulo deux ou son inversion logique est une fonction booléenne linéaire (opération XOR, notée dans les formules par ) et est le plus souvent utilisée dans de tels registres.

Dans ce cas, les bits qui sont des variables de la fonction de rétroaction sont généralement appelés virages.

Le contrôle des registres dans les implémentations matérielles est effectué en appliquant une impulsion de décalage (autrement appelée horloge ou impulsion de synchronisation) à toutes les cellules, dans le logiciel - en exécutant un cycle logiciel, comprenant le calcul de la fonction de rétroaction et le décalage des bits dans un mot.

À chaque pas de temps, les opérations suivantes sont effectuées :

Registre à décalage à rétroaction linéaire

Ainsi, l'opération logique XOR (OU exclusif) est prise comme fonction de retour, c'est-à-dire :

Propriétés des polynômes primitifs

Propriétés

Les propriétés de la séquence produite par le LFSR sont étroitement liées aux propriétés du polynôme associé. Ses coefficients non nuls sont appelés virages, ainsi que les cellules de registre correspondantes qui fournissent les valeurs des arguments de la fonction de rétroaction.

Complexité linéaire

La complexité linéaire d’une séquence binaire est l’une des caractéristiques les plus importantes du fonctionnement du LFSR. Introduisons la notation suivante :

Définition

Complexité linéaire d'une séquence binaire infinie s'appelle un nombre, qui est défini comme suit :

Complexité linéaire d'une séquence binaire finie est appelé un nombre égal à la longueur du LFSR le plus court qui génère une séquence ayant pour premiers termes .

Propriétés de la complexité linéaire

Soit et soit des séquences binaires. Alors:

Indépendance de la corrélation

Pour atteindre une complexité linéaire élevée, les cryptographes tentent de combiner de manière non linéaire les résultats de plusieurs séquences de sortie. Dans ce cas, le danger est qu'une ou plusieurs séquences de sortie (souvent même les sorties de LFSR individuels) puissent être reliées par un flux de clé commun et ouvertes à l'aide de l'algèbre linéaire. Le piratage basé sur une telle vulnérabilité est appelé autopsie de corrélation. Thomas Siegenthaler a montré qu'il est possible de spécifier précisément l'indépendance de corrélation et qu'il existe un compromis entre l'indépendance de corrélation et la complexité linéaire.

L'idée principale d'un tel hack est de détecter une certaine corrélation entre la sortie du générateur et la sortie de l'un de ses composants. Ensuite, en observant la séquence de sortie, des informations sur cette sortie intermédiaire peuvent être obtenues. En utilisant ces informations et d'autres corrélations, les données peuvent être collectées sur d'autres broches intermédiaires jusqu'à ce que le générateur soit compromis.

Les attaques de corrélation ou leurs variantes telles que les attaques de corrélation rapide impliquant un compromis entre complexité informatique et efficacité ont été utilisées avec succès contre de nombreux générateurs de flux de clés de registre à décalage à rétroaction linéaire.

Exemple

Pour SFLOS avec un polynôme associé, la séquence générée a la forme . Disons qu'avant le début du processus la séquence est écrite dans le registre, alors la période du flux binaire généré sera égale à 7 avec la séquence suivante :

Numéro d'étape	État	Bit généré
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Puisque l'état interne de la septième étape est revenu à son état d'origine, alors, à partir de l'étape suivante, il y aura une répétition. En d'autres termes, la période de la séquence s'est avérée être égale à 7, ce qui s'est produit en raison du caractère primitif du polynôme.

Algorithmes de génération de polynômes primitifs

Tableaux prêts

Calculer la primitivité d'un polynôme est un problème mathématique assez complexe. Par conséquent, il existe des tableaux prêts à l'emploi qui montrent le nombre de séquences de prises qui fournissent la période maximale du générateur. Par exemple, pour un registre à décalage de 32 bits, il existe la séquence . Cela signifie que pour générer un nouveau bit, vous devez ajouter les 31e, 30e, 29e, 27e, 25e et 0e bits à l'aide de la fonction XOR. Le code d'un tel RLOS en langage C est le suivant :

Int LFSR (void) ( statique non signé long S = 1; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1 ) ; retourner S & 1 ; )

Les implémentations logicielles des générateurs LFSR sont assez lentes et fonctionnent plus rapidement si elles sont écrites en assembleur plutôt qu'en langage C. Une solution consiste à utiliser 16 RSLOS en parallèle (ou 32, selon la longueur des mots dans l'architecture d'un ordinateur particulier). Dans un tel schéma, un tableau de mots est utilisé, dont la taille est égale à la longueur du LFSR, et chaque bit d'un mot du tableau fait référence à son propre LFSR. À condition que les mêmes numéros de séquence de prises soient utilisés, cela peut fournir un gain de performances notable. [besoin d'un exemple de code] (Voir : bitslice).

Configuration galoisienne

Configuration galoisienne d'un registre à décalage à rétroaction linéaire

Le circuit de rétroaction peut également être modifié. Dans ce cas, le générateur n’aura pas une plus grande force cryptographique, mais il sera plus facile à implémenter dans le logiciel. Au lieu d'utiliser le bit le plus à gauche de la séquence de prises pour générer le nouveau bit le plus à gauche, il XOR chaque bit de la séquence de prises avec la sortie du générateur et le remplace par le résultat de cette action, puis la sortie du générateur devient la nouvelle le bit le plus à gauche. En C, cela ressemble à ceci :

Int LFSR (void) ( static non signé long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

L'avantage est que tous les XOR sont effectués en une seule opération.

• on peut prouver que la configuration de Fibonacci donnée en premier et la configuration de Galois donnée ici donnent les mêmes séquences (longueur 2 32 −1), mais décalées en phase l'une par rapport à l'autre
• une boucle d'un nombre fixe d'appels à la fonction LFSR dans la configuration Galois s'exécute environ deux fois plus vite que dans la configuration Fibonacci (compilateur MS VS 2010 sur Intel Core i5)
• notez que dans la configuration Galois l'ordre des bits dans le mot définissant le feedback est inversé par rapport à la configuration Fibonacci

Exemples de générateurs

Générateurs stop-and-go

Générateur stop-go alterné

Cet oscillateur utilise la sortie d'un LFSR pour contrôler la fréquence d'horloge d'un autre LFSR. La sortie d'horloge de RSLOS-2 est contrôlée par la sortie de RSLOS-1, de sorte que RSLOS-2 ne peut changer d'état au temps t que si la sortie de RSDOS-1 au temps t-1 était égale à un. Mais ce schéma n’a pas pu résister à la dissection corrélationnelle.

Par conséquent, un générateur amélioré basé sur la même idée a été proposé. C'est ce qu'on appelle un générateur alternatif stop-go. Il utilise trois LFSR de longueurs différentes. RSLOS-2 est cadencé lorsque la sortie de RSLOS-1 est égale à un, et RSLOS-3 est cadencé lorsque la sortie de RSLOS-1 est égale à zéro. La sortie du générateur est la somme modulo 2 de RSLOS-2 et RSLOS-3. Ce générateur a une longue période et une grande complexité linéaire. Ses auteurs ont également montré une méthode d'ouverture corrélative de RSLOS-1, mais cela n'affaiblit pas beaucoup le générateur.

Cascade Gollmann

Cascade Gollmann

La cascade Gollmann est une version renforcée du générateur stop-go. Il consiste en une séquence de LFSR, dont le timing de chacun est contrôlé par le LFSR précédent. Si la sortie de RSLOS-1 au temps t est 1, alors RSLOS-2 est cadencé. Si la sortie de RSLOS-2 au temps t est 1, alors RSLOS-3 est cadencé, et ainsi de suite. La sortie du dernier LFSR est la sortie du générateur. Si la longueur de tous les LFSR est la même et égale à n, alors la complexité linéaire d'un système de k LFSR est égale à .

Cette idée est simple et peut être utilisée pour générer des séquences avec des périodes énormes, une grande complexité linéaire et de bonnes propriétés statistiques. Mais malheureusement, ils sont sensibles à l’ouverture, appelée « lock-in ». Pour une plus grande durabilité, il est recommandé d'utiliser un k d'au moins 15. De plus, il est préférable d'utiliser plus de SFSR courts que moins de SFSR longs.

Générateur de seuil

Générateur de seuil

Ce générateur tente de contourner les problèmes de sécurité inhérents aux générateurs précédents en utilisant un nombre variable de registres à décalage. En théorie, lorsqu'on utilise un plus grand nombre de registres à décalage, la complexité du chiffrement augmente, ce qui a été fait dans ce générateur.

Ce générateur est constitué d'un grand nombre de registres à décalage dont les sorties alimentent la fonction de majoration. Si le nombre de un aux sorties des registres est supérieur à la moitié, alors le générateur en sort un. Si le nombre de zéros aux sorties est supérieur à la moitié, alors le générateur génère zéro. Pour que la comparaison du nombre de zéros et de uns soit possible, le nombre de registres à décalage doit être impair. Les longueurs de tous les registres doivent être relativement premières et les polynômes de rétroaction doivent être primitifs, afin que la période de la séquence générée soit maximale.

Pour le cas de trois registres à décalage, le générateur peut être représenté comme :

Ce générateur est similaire au générateur Geff sauf que le générateur de seuil a une complexité plus linéaire. Sa complexité linéaire est :

où , , sont les longueurs des premier, deuxième et troisième registres à décalage.

Son inconvénient est que chaque bit de sortie fournit des informations sur l'état du registre à décalage. Ou plutôt 0,189 bits. Par conséquent, ce générateur pourrait ne pas être en mesure de résister à une attaque par corrélation.

Autres types

Auto-éclaircissant

Les générateurs auto-décimants sont ceux qui contrôlent leur propre fréquence. Deux types de tels générateurs ont été proposés. Le premier consiste en un registre à décalage à rétroaction linéaire et certains circuits qui synchronisent ce registre en fonction des valeurs de sortie du registre à décalage. Si la sortie du SFSR est égale à un, alors le registre est cadencé d fois. Si la sortie est nulle, alors le registre est cadencé k fois. Le second a presque la même conception, mais légèrement modifié : dans le circuit d'horloge, l'entrée, pour vérifier 0 ou 1, n'est pas le signal de sortie lui-même, mais XOR de certains bits du registre à décalage avec rétroaction linéaire. Malheureusement, ce type de générateur n’est pas sécuritaire.

Oscillateur à plusieurs vitesses avec produit interne

Cet oscillateur utilise deux registres à décalage à rétroaction linéaire avec des fréquences d'horloge différentes : RSLOS-1 et RSLOS-2. La fréquence d'horloge de RSLOS-2 est d fois supérieure à celle de RSLOS-1. Les bits individuels de ces registres sont combinés à l'aide de l'opération ET. Les sorties de l’opération ET sont ensuite XOR. La séquence de sortie est extraite de ce bloc XOR. Encore une fois, ce générateur n'est pas parfait (il n'a pas résisté à la découverte de la cohérence linéaire. Si - la longueur de SFLO-1, - la longueur de SFLO-2, et d est le rapport des fréquences d'horloge, alors l'état interne du générateur peut être obtenu à partir d'une séquence de sortie de longueur ), mais il présente une complexité linéaire élevée et d'excellentes performances statistiques.