L'algèbre de base derrière les codes secrets et la communication spatiale

L'exploration de l'espace demande une précision extrême. Lorsque vous faites atterrir un rover sur Mars à 70 millions de kilomètres de la station-service la plus proche, vous devez optimiser votre efficacité et vous préparer à l'inattendu. Cela s'applique à tout, de la conception des engins spatiaux à la transmission des données : ces messages qui reviennent sur Terre sous la forme d'un flux constant de 0 et de 1 contiennent forcément des erreurs, vous devez donc être en mesure de les identifier et de les corriger sans perdre de temps et d'énergie précieux.

C'est là que les mathématiques entrent en jeu. Les mathématiciens ont inventé des moyens ingénieux de transmettre et de stocker des informations. Une méthode étonnamment efficace utilise Codes Reed-Solomon, qui sont construits sur la même algèbre de base que les élèves apprennent à l'école. Participons à un cours de mathématiques pour voir comment les codes Reed-Solomon aident à transmettre et à sécuriser les informations tout en corrigeant les erreurs coûteuses qui surgissent.

Deux étudiants, Art et Zeke, échangent des messages secrets dans le cours de mathématiques de Mme Al-Jabr. Art déplie la dernière note de Zeke pour révéler les nombres 57 et 99. Il sait qu'il doit fournir le x-coordonnées 3 et 6 pour créer les points (3, 57) et (6, 99). L'art branche chaque point dans l'équation linéaire y = Ax + B et produit le système d'équations suivant :

57 = 3A + B

99 = 6A + B

Pour décoder le message, l'Art doit résoudre pour A ainsi que B. Il commence par soustraire la première équation de la seconde :

Cela élimine B. Diviser les deux côtés de cette nouvelle équation par 3 indique à l'Art que A = 14, puis en le remplaçant dans la première équation, 57 = 3 × 14 + B, donne B = 15.

L'art sait maintenant que la droite passant par (3, 57) et (6, 99) est décrite par l'équation y = 14x + 15. Mais il sait aussi que dans un code Reed-Solomon, le message secret se cache dans les coefficients. Il décode le message de Zeke en utilisant leur chiffre alphabétique simple et convenu : 14 est "N" et 15 est "O", ce qui indique à Art que, non, Zeke ne peut pas jouer aux jeux vidéo après l'école aujourd'hui.

Le secret de ce code Reed-Solomon simple commence par deux faits fondamentaux de la géométrie. Premièrement, à travers deux points quelconques, il y a une ligne unique. Deuxièmement, pour les coefficients A ainsi que B, chaque ligne (non verticale) peut être écrite sous la forme y = Ax + B. Ensemble, ces deux faits garantissent que si vous connaissez deux points sur une droite, vous pouvez trouver A ainsi que B, et si vous savez A ainsi que B, vous connaissez tous les points sur la ligne. En bref, posséder l'un ou l'autre ensemble d'informations équivaut à connaître la ligne.

Les codes Reed-Solomon exploitent ces ensembles d'informations équivalents. Le message secret est codé sous forme de coefficients A ainsi que B, et les points de la ligne sont divisés en morceaux, dont certains sont transmis publiquement, et dont certains sont gardés privés. Pour décoder le message, il vous suffit de rassembler les morceaux et de les reconstituer. Et tout ce que cela nécessite est une simple algèbre.

Les pièces de Zeke étaient les numéros 57 et 99, qu'il envoya à Art. Ces numéros constituent la partie publique du message. Art les a assemblés avec ses propres pièces, 3 et 6, pour reconstituer les points (3, 57) et (6, 99). Ici, le 3 et le 6 constituent la partie privée du message, sur laquelle Art et Zeke se sont mis d'accord au préalable.

Les deux points se trouvent sur une ligne, et pour décoder le message, il vous suffit de trouver l'équation de cette ligne. Brancher chaque point sur y = Ax + B vous donne un système de deux équations autour de la droite qui doivent toutes deux être vraies. Maintenant, la stratégie est simple : résolvez le système, déterminez la ligne et décodez le message.

En cours d'algèbre, vous avez probablement appris de nombreuses méthodes de résolution de systèmes d'équations, telles que la représentation graphique, la devinette et la vérification, et la substitution. L'art a utilisé l'élimination, une méthode où vous manipulez les équations algébriquement afin d'éliminer les variables une à la fois. Chaque fois que vous éliminez une variable, le système devient un peu plus facile à résoudre.

Comme pour les autres schémas de chiffrement, c'est la combinaison intelligente d'informations publiques et privées qui assure la sécurité des messages. Zeke pourrait crier ses numéros 57 et 99 à travers la classe et cela ne mettrait pas en péril la sécurité de son message à Art (même si cela pourrait lui causer des ennuis avec Mme Al-Jabr). En effet, sans les informations privées correspondantes - le x-coordonnées 3 et 6 — il est impossible d'identifier l'équation de la droite. Tant qu'ils gardent ces valeurs pour eux, ils peuvent en toute sécurité passer leurs messages secrets en public.

La ligne y = 14x + 15 est bien pour transmettre le mot de deux lettres « non », mais que se passe-t-il si les élèves veulent partager un secret plus long ? C'est là que la pleine puissance de l'algèbre, de la géométrie et des systèmes d'équations linéaires entre en jeu.

Supposons que Zeke veuille savoir comment Art pense réussir son test d'anglais de demain. Art convertit sa réponse à trois lettres en nombres 14, 59 et 82 et les transmet à Zeke. Les étudiants ont convenu au préalable que lorsqu'ils utilisent des codes Reed-Solomon de longueur 3, leurs nombres privés sont 2, 5 et 6, Zeke assemble donc les pièces pour reconstruire les points (2, 14), (5, 59) et (6, 82).

Or, il n'y a pas de fonction linéaire qui passe par ces trois points. Mais il existe une fonction quadratique unique qui le fait. Et comme toute fonction quadratique peut s'écrire sous la forme y = Ax² + Bx + C, la même méthode générale peut être appliquée. La seule différence est la taille du système.

Brancher chaque point sur y = Ax² + Bx + C donne une équation, donc les trois points produisent le système de trois équations suivant :

(2, 14): 14 = 4A + 2B + C

(5, 59): 59 = 25A + 5B + C

(6, 82): 82 = 36A + 6B + C

Un système de trois équations à trois inconnues nécessite un peu plus de travail à résoudre qu'un système de deux équations à deux inconnues, mais le but est le même : combiner astucieusement des paires d'équations pour éliminer des variables.

Par exemple, si vous soustrayez la première équation de la seconde, vous obtenez la nouvelle équation 45 = 21A + 3B. De même, si vous soustrayez la deuxième équation de la troisième, vous obtenez 23 = 11A + B. Ces manipulations algébriques produisent un nouveau système :

45 = 21A + 3B

23 = 11A + B

Vous avez maintenant un système "deux par deux": deux équations à deux inconnues. Pour le résoudre, vous pouvez multiplier la seconde équation par −3 et l'ajouter à la première équation :

Remarquez comment l'élimination répétée a transformé le système original de trois équations en une seule équation qui peut être facilement résolue : A = 2. En travaillant à rebours, vous pouvez brancher A = 2 dans l'une des équations du système deux par deux pour trouver B = 1, puis branchez les deux valeurs dans l'une des équations d'origine pour obtenir C = 4. Après avoir utilisé le chiffrement alphabétique simple sur 2, 1 et 4, Zeke sait que Art va faire "MAUVAIS" au test d'anglais de demain. Au moins, il s'entraîne beaucoup à l'algèbre.

Grâce à un fait particulier sur les fonctions polynomiales, vous pouvez transmettre un message de n'importe quelle longueur en utilisant les codes Reed-Solomon. La clé est la suivante : étant donné n points dans le plan avec différents x-coordonnées, il existe un unique polynôme de « degré » n − 1 qui les traverse. Le degré d'un polynôme est la puissance la plus élevée d'une variable dans l'expression, donc une fonction quadratique comme Ax² + Bx + C est de degré 2, puisque la puissance la plus élevée de x est 2. Et une fonction linéaire est de degré 1, puisque dans l'équation y = Ax + B, la plus grande puissance de x est 1.

Dans le premier exemple, nous avons utilisé le fait que deux points déterminent un polynôme linéaire unique, ou de degré 1. Dans la seconde, nous nous sommes appuyés sur le fait que trois points déterminent un unique polynôme de degré 2, ou quadratique. Et si vous voulez envoyer un message de longueur 10, codez simplement le message sous la forme des 10 coefficients d'une fonction polynomiale de degré 9. Une fois que vous avez votre fonction, calculez les 10 y-valeurs en évaluant la fonction aux 10 valeurs privées préalablement convenues x-valeurs. Une fois que vous faites cela, vous pouvez passer en toute sécurité ceux y-coordonnées en public pour que votre récepteur les décode. En pratique, les codes Reed-Solomon sont un peu plus complexes que cela, utilisant des types de coefficients et des schémas de traduction plus sophistiqués, mais l'idée fondamentale est la même.

En plus de garder votre message sécurisé, les codes Reed-Solomon offrent également des moyens simples et efficaces pour détecter et même corriger les erreurs. Ceci est important chaque fois que des données sont transmises ou stockées, car il y a toujours un risque que certaines informations soient perdues ou corrompues.

Une solution à ce problème consisterait simplement à envoyer des copies supplémentaires des données. Par exemple, Zeke peut envoyer le message [14, 14, 14, 15, 15, 15] au lieu de [14, 15]. Tant que Art sait que chaque partie du message est envoyée en triple exemplaire, il peut décoder le message et vérifier les erreurs. En fait, s'il trouve des erreurs, il a de bonnes chances de les corriger. Si Art reçoit [14, 14, 24, 15, 15, 15], le fait que les trois premiers nombres soient différents l'avertit d'une erreur, et puisque deux d'entre eux sont 14, il peut deviner que le 24 devrait probablement être un 14 également. Au lieu de demander que le message soit renvoyé, Art peut poursuivre son décodage. C'est une stratégie efficace mais coûteuse. Quels que soient le temps, l'énergie et les efforts nécessaires pour envoyer n informations, cela demande trois fois plus.

Mais les mathématiques derrière les codes Reed-Solomon offrent une alternative efficace. Au lieu d'envoyer plusieurs copies de chaque élément de données, vous pouvez simplement envoyer un point supplémentaire ! Si ce point supplémentaire correspond à votre polynôme, alors l'information est correcte. Si ce n'est pas le cas, il y a eu une erreur.

Pour voir comment cela fonctionne, supposons que vous souhaitiez vérifier le message "NON" dans le premier exemple. Zeke peut simplement envoyer le supplément y-coordonner 155. En supposant que lui et Art aient convenu d'un troisième x-coordonner au préalable, dire x = 10, Art peut vérifier ce troisième point par rapport à la ligne qu'il a décodée. Quand il branche x = 10 dans y = 14x + 15 et voit que le résultat est 155, il sait qu'il n'y a pas eu d'erreurs de transmission.

Cela ne fonctionne pas seulement pour les lignes. Pour permettre à Zeke de cocher "MAUVAIS" dans le deuxième exemple, Art peut envoyer y = 25. S'ils ont convenu que 3 est le plus privé x-coordonner, Zeke peut brancher x = 3 dans sa fonction quadratique y = 2x² + x + 4 et vérifiez que le point (3, 25) correspond, confirmant à nouveau une transmission sans erreur avec un seul point de plus.

Et ce point supplémentaire peut également corriger les erreurs. Si une erreur est détectée et que le récepteur ne peut pas construire la fonction polynomiale qui contient le message, il peut à la place construire le polynôme « le mieux adapté » en utilisant des techniques de régression. Comme une ligne de meilleur ajustement dans la classe de statistiques, il s'agit de la fonction polynomiale qui est mathématiquement déterminée pour s'adapter le mieux aux points donnés, même si elle ne les traverse pas tous. En fonction de la structure du message et de la quantité d'informations supplémentaires que vous envoyez, ce polynôme le mieux adapté peut vous aider à reconstruire le polynôme correct - et donc le message correct - même à partir d'informations corrompues.

Cette efficacité dans la transmission et la correction des communications explique pourquoi la NASA a utilisé les codes Reed-Solomon lors de ses missions vers la lune et vers Mars. Et cela vous donne quelque chose à méditer pendant que vous résolvez votre prochain système d'équations. Au fur et à mesure que vous devinez, vérifiez ou éliminez votre chemin vers la solution, pensez à la puissance et à l'élégance des codes Reed-Solomon et à tous les secrets que votre système pourrait révéler.

Des exercices

1. En utilisant le même schéma qu'ils ont utilisé en classe, Art affiche les numéros publics 33 et 57 pour que Zeke les décode. Quel est le message ?

2. Comment Art et Zeke peuvent-ils être sûrs que le système d'équations qui résulte de leurs nombres privés x = 3 et x = 6 aura toujours une solution ?

3. En réponse au message d'Art de "MAUVAIS" à propos du test d'anglais, Zeke renvoie [90, 387, 534]. En supposant qu'ils utilisent le même schéma qu'ils ont utilisé en classe, quel est son message ?

4. Lola vous envoie un message de deux lettres plus un numéro de vérification d'erreur en utilisant un code Reed-Solomon et le même chiffre alphabétique simple utilisé par Art et Zeke. Vous vous êtes secrètement mis d'accord sur le x-coordonne les 1, 3 et 10 à l'avance, et Lola transmet les numéros publics [27, 43, 90]. Le message contient-il une erreur ?