Aller au contenu

Chiffrer et déchiffrer du RSA en TeX

C’est une drôle d’idée que d’implémenter le chiffrement RSA en TeX, mais, sauf erreur de ma part, je crois que cela n’a pas été fait et le défi que cela représente est intéressant à relever.

Principe du chiffrement RSA

Afin de mener à bien ce défi, voici le principe arithmétique du chiffrement RSA.

La théorie

On considère que les clés, publiques et privées, appelées \((n,e)\) et \((n,d)\) sont déjà créées et nous ne nous étendrons pas sur la méthode pour les générer.

Le processus est le suivant :

  1. le message \(X\) doit être codé de façon réversible sous forme d’un entier appelé \(M\) où si \(M\) dépasse ou égale \(n\), en plusieurs entiers \(M_i\), tous strictement inférieurs à \(n\) ;
  2. le message chiffré correspondant à un entier \(M_i\), noté \(C_i\) est égal à \(C_i \equiv M_i^e \pmod n\) ;
  3. le message chiffré \(Y\) est le texte correspondant à \(M\) ou à l’assemblage des entiers \(C_i\).

Pour déchiffrer le message composé \(Y\) :

  1. le découper en entiers \(C_i\) selon le processus inverse de celui vu au point 4 précédent ;
  2. le message déchiffré \(M_i\) correspondant à \(C_i\) est égal à \(M_i \equiv C_i^d \pmod n\) ;
  3. le message déchiffré \(M\) est égal à l’assemblage des entiers \(M_i\) selon le processus inverse de celui vu au point 2 précédent ;
  4. le message \(X\) sous forme de texte est l’entier \(M\) décodé selon le processus inverse de celui vu au point 1 ;

Un exemple

Voyons cela avec un exemple volontairement simpliste car dans la réalité, les nombres en jeu sont considérablement plus grands que ceux exposés dans cet exemple.

Générons les clés :

  • choisissons deux nombres premiers \(a\) et \(b\), par exemple  \(a=5\) et \(b=11\) ;
  • leur produit \(n=5\times11=55\) est appelé module de chiffrement ;
  • l’indicatrice d’Euler de \(n\), notée \(\phi(n)\) vaut \(\phi(n)=(a-1)\times(b-1)=40\) ;
  • on choisit un exposant de chiffrement \(e\), strictement inférieur à \(\phi(n)\) et premier avec elle, par exemple \(e=3\) ;
  • l’exposant de déchiffrement \(d\) est l’inverse de \(e\) modulo \(\phi(n)\) : ce nombre est 27 car \(3\times27=81\) et on a bien \(81 \equiv 1 \pmod{40}\).

La clé publique est \((55,3)\) et la clé privée est \((55,27)\).

Le passage texte → entier

Tout le mécanisme suppose qu’un texte puisse être traduit de façon biunivoque sous forme d’un entier. Pour que l’exemple soit simple, nous prendrons un alphabet de 5 lettres « a, b, c, d, e » : chaque lettre est repérée par son index en partant de 0 ; ainsi a=0, b=1, …, e=4. Supposons que le mot à coder soit « decad ». Pour transformer « decad » en entier, nous allons affecter à chaque lettre le produit de son index par les puissances croissantes de 5, en partant de 0. Ainsi, « deca » est représenté par le nombre \(3\times5^0+4\times5^1+2\times5^2+0\times5^3+3\times5^4=1948\). Cela revient, si l’on veut, à trouver la valeur décimale du nombre 30243 écrit en base 5 (30243 est l’écriture « à l’envers » de 34203).

Le problème est que l’algorithme RSA n’est capable de fonctionner qu’avec des nombres strictement inférieurs à \(n\) qui vaut 55 ici. Cela va nous obliger à découper le mot « decad » en groupes de lettres de longueur \(i\) tel que l’entier qui représente ces lettres soit strictement inférieur à 55. Cela suppose donc de trouver l’entier qui est strictement inférieur au logarithme de base 5 du nombre 55 ou, autrement dit, combien de fois peut-on multiplier 5 par lui même pour rester strictement inférieur à 55. Ici, ce logarithme est \(i=2\) puisque \(5^2=25<55\) et \(5^3=125>55\). Nous allons donc découper notre texte en groupes de 2 lettres : « de », «ca » et « d ».

Le chiffrement

Chiffrons avec la clé (55,3) et présentons les résultats avec 2 chiffres, c’est-à-dire autant qu’en a \(n-1=54\) :

  • le 1er groupe de lettre « de » est représenté par l’entier \(M_1=3\times5^0+4\times5^1=23\). On obtient \(C_1=23^3 \pmod{55}=12\)
  • le 2e groupe de lettres « ca » est représenté par l’entier \(M_2=2\times5^0+0\times5^1=2\) qui est chiffré en \(C_2=2^3 \pmod{55}=08\)
  • le 3e groupe de lettres «d» est représenté par l’entier \(M_3=3\times5^0=3\) qui est chiffré en \(C_3=3^3 \pmod{55}=27\)
  • il reste un problème : le 3e groupe de lettre est incomplet et si ce groupe de lettre avait été « da », les nombres \(M_3\) et \(C_3\) auraient été identiques. Il faut donc créer un dernier entier \(M_4\) qui représente \(k\), le nombre de lettres utiles dans le dernier mot. Nous prendrons \(M_4=n-2-k=55-2-1=52\)  qui serait codé en \(C_4=52^3 \pmod{55}=28\).

Notre texte chiffré est donc \(C=12082728\).

Le passage entier → texte

Avant de déchiffrer proprement dit, examinons comment passer d’un entier aux lettres qu’il représente. Prenons l’entier 76. Effectuons des divisons euclidiennes en cascade par 5 :

  • \(76=15\times5+1\) : le reste 1 est l’index de la première lettre qui est donc « b ». Poursuivons avec la division euclidienne du quotient 15 par 5.
  • \(15=3\times5+0\) : le reste 0 est l’index de la 2e lettre qui est donc « a ». Poursuivons avec la division du quotient 3 par 5 ;
  • \(3=0 \times5+3\) : le reste 3 est l’index de la 3e lettre qui est donc « d ». Le quotient 0 indique que la dernière lettre est atteinte

Par conséquent, 76 représente le mot « bad ».

Le déchiffrement

Déchiffrons \(C=12082701\) avec la clé (55,27). Découpons \(C\) en nombres de 2 chiffres, autant qu’en possède 54 :

  • \(C_1=12\) qui est déchiffré en \(M_1=12^{27} \pmod{55}=23\) et 23 représente le mot «de » ;.
  • \(C_2=08\) qui est déchiffré en \(M_2=08^{27} \pmod{55}=2\) et 2 représente le mot « ca » ;
  • \(C_3=27\) qui est déchiffré en \(M_3=27^{27} \pmod{55}=3\) et 3 représente le mot « da »;
  • \(C_4=28\) qui est déchiffré en \(M_4=28^{27} \pmod{55}=52\). Ceci est le dernier nombre, il représente le nombre de lettres utiles dans le dernier mot trouvé qui vaut \(n-2-52=55-2-52=1\) : le dernier mot est donc « d ».

Le mot déchiffré est « decad ».

Ingrédients

Tout d’abord, il faut se munir d’un outil qui permet de calculer sur des entiers arbitrairement grands. Pour cela, l’extension apnum, pour plainTeX sera appelée.

De quelles macros avons-nous besoin pour mener à bien toutes ces étapes ? Il faut dresser la liste… Avant tout chose, comme les macros de apnum ne sont pas purement développables (et c’est très bien ainsi, il n’y a que les débutants ou les aliénés qui recherchent obstinément le purement développable), nos macros ne le seront pas non plus. Chaque macro ayant un nom (par exemple \tagada), son résultat sera stocké sous une macro de nom \tagadaresult.

Voici une liste :

  • la macro \logbase{<base>}{<nombre>} qui renvoie le logarithme entier en base <n> du <nombre> ;
  • la macro \blocktexttonum{<texte>} qui transforme le <texte> (détokénizé et donc vu comme une suite d’octets inoffensifs) en un entier à l’aide de la base 256 ;
  • la macro \numtoblocktext{<entier>}{<longueur>} qui fait l’exact travail contraire de \blocktexttonum ;
  • la macro \modularexpo{x}{e}{n} qui calcule \(x^e \pmod n\)
  • la macro \grabndigits{<entier>}{<i>} qui enlève <i> chiffres à la gauche de l' <entier> et les met dans \grabndigitsresult

Les prérequis

Ce sont les macros qui servent pour toutes les macros qui restent à écrire. Il faut également souligner que la macro \apDIV{<dividende>}{<diviseur>}, et donc \apMOD qui en découle semblent buguées. En effet, si le dividende est inférieur au diviseur, le reste est nul. Il faut donc utiliser des versions corrigées qui tiennent compte de ce bug.

La macro \logbase

Rien de bien méchant, on multiplie autant de fois possible la <base> sans dépasser le <nombre>. On utilise le test \ifCMPNUM qui permet de comparer des entiers longs à l’aide de apnum. Remarquons que pour avoir le nombre de chiffres (en base 10) d’un <nombre>, il faut appeler \logbase{<nombre>}{10} puis évaluer \logbaseresult+1.

La macro \blocktexttonum

Pour que les nombres générés aient un nombre de chiffres donné, quitte à rajouter des 0 inutiles à leur gauche, il nous faut écrire une macro \powten d’argument \(i\) entier et qui renvoie \(10^i\). L’écriture est triviale avec la boucle \fornum :

Maintenant que ceci est fait, la macro \forceformat{<entier>}{<i>} renverra l' <entier> écrit avec <i> chiffres, nombre qui est supposé être strictement supérieur au nombre de chiffres de <entier> (aucune vérification ne sera faite à ce sujet) :

Voici enfin la macro \blocktextetonum ; rien d’extraordinaire si ce n’est une macro récursive qui prend les caractères un par un, et multiplie la base par 256 à chaque tour. Après le processus, afin que le nombre retourné ait bien \(i\) chiffres, la macro \forceformat est appelée.

La macro \numtoblocktext

C’est l’inverse de celle ci-dessus.

Elle nécessite tout d’abord de transformer un entier (inférieur à 255) en le caractère correspondant. Le seul moyen économe en lignes de code en eTeX est de recourir à la primitive \scantokens{^^<hex>}<hex> est le nombre hexadécimal, écrit en lettres minuscules, correspondant à l’entier.

Voici donc tout d’abord une macro qui convertit un entier (inférieur à 256) en hexadécimal écrit en minuscule :

Passons à la macro \dectochar{<entier>} qui renvoie le caractère de code <entier> (inférieur à 256) :

Tout est en place pour écrire la macro \numtoblocktext{<entier>}{<longueur du texte>} :

La macro \modularexpo

Le cœur du chiffrement et du déchiffrement est de calculer un entier \(x=y^e \pmod m\). La macro \modularexpo{<y>}{<e>}{<m>} se chargera de ce calcul. Il n’est pas question de calculer \(y^e\) puis d’en calculer le reste dans la division par \(m\), car les nombres obtenus seraient beaucoup trop grands ce qui ralentirait considérablement le calcul.

La méthode la plus rapide est d’écrire \(e\) en base 2, comme cela est très bien décrit dans cet article.

Il faut donc avant tout écrire une macro qui convertit un entier arbitrairement grand en base 2. Pour que le résultat soit plus facile à manier par la suite, les chiffres binaires seront écrits dans l’ordre inverse dans le résultat.

La macro \modularexpo est désormais facile à écrire :

La macro \grabndigits

Le code complet

Tout est maintenant prêt pour écrire la macro de chiffrement \RSA et celle de déchiffrement \unRSA.

La macro \RSA va faire les choses suivantes :

  1. lire les clés publiques \(n\) et \(e\), convertir \(e\) en base 2, stocker les clés
  2. rendre les catcodes de tous les octets à 12, sauf { et }, lire le <texte> à chiffrer entre accolades puis détokénizer les accolades éventuelles se trouvant dans ce texte, et stocker le résultat dans \RSAcleartext
  3. calculer avec \logbase la longueur des blocs de texte \RSAblocktextlen
  4. calculer avec \logbase la longueur des blocs de chiffres obtenus après chiffrement \RSAblockdigitslen
  5. découper le <texte> en blocs, les chiffrer, les formatter et accumuler les nombres obtenus dans la macro \RSAresult
  6. après le dernier bloc, de longueur \(k\), calculer \(n-2-k\), chiffrer ce nombre et l’ajouter à \RSAresult

La macro \unRSA va faire les choses dans l’ordre inverse :

  1. lire les clés publiques \(n\) et \(d\), convertir \(d\) en base 2, stocker les clés
  2. calculer avec \logbase la longueur des blocs de texte \RSAblocktextlen
  3. calculer avec \logbase la longueur des blocs de chiffres obtenus après chiffrement \RSAblockdigitslen
  4. lire l' <entier> à déchiffrer et le découper en blocs de longueur \RSAblockdigitslen les déchiffrer, les décoder sous forme de textes de longueur  \RSAblocktextlen et accoler le texte obtenu dans \unRSAresult
  5. pour le dernier bloc déchiffré, ne pas le décoder, mais enlever au bloc précédent la longueur trouvée par déchiffrement du dernier bloc.

Un booléen \ifRSAverbose, désactivable si besoin, permet d’afficher toutes les étapes.

Puisque le texte à chiffrer est détokénizé, le texte déchiffré, contenu dans la macro  est détokénizé lui aussi ce qui conduit à un affichage sous forme souvent étrange. Il est possible de le tokénizer pour le manipuler normalement par TeX via la macro \RSAtokenize.

Voici donc un exemple où le texte à chiffrer est « Apprendre à programmer en \TeX{} est facile et utile ! ». Les clés, générées sur un site comme on en trouve partout, sont :

  • la clé publique = (296794529088786870857070303383262468007,309485009821345068724781057)
  • clé privée =(296794529088786870857070303383262468007,292447678587574340440676199541777968113)

Attention : bien que les entiers soient grands, ils ne le sont pas assez (et de très loin) pour garantir la sécurité du chiffrement.

Le booléen \ifRSAverbose est assigné à « true » pour que soient affichés les étapes et les résultats du chiffrement/déchiffrement. La compilation demande quelques secondes.

Laisser un commentaire