Licence CC BY-NC-SA

Mise en pratique

Dans ce chapitre, on va passer à la pratique en essayant de coder un système RSA. Pour commencer, je vous donnerai quelques outils mathématiques supplémentaires bien utiles pour ne pas créer un monstre qui va consommer toute l’énergie de votre PC jusqu’au dernier électron. Ensuite, on passera à la réflexion proprement informatique pour bien organiser le projet. Enfin, je vous proposerai des exemples de solution partielle.

Conseils mathématiques

L’opération la plus consommatrice de mémoire et donc de temps de calcul est l'exponentiation modulaire, celle qui consiste à chercher la valeur de aa puissance bb modulo cc. La solution « naïve » pour calculer un tel nombre consiste à faire une série de multiplications pour obtenir la puissance, puis à passer le résultat à la division euclidienne pour trouver le modulo. Et c’est là que cela pêche. Prenons un cas simple : 426≡233 [437]4^{26} \equiv 233 \ [437]. Il ne met en jeu que des nombres de trois chiffres au maximum et pourtant, le résultat de l’opération puissance, avant qu’on lui applique le modulo, est un nombre à seize chiffres. Imaginez ce que ce serait avec des exposants et des bases à cent ou deux cents chiffres !

Il existe cependant un moyen d’aboutir au résultat en n’utilisant que des nombres de l’ordre de grandeur du modulo ou plus petits. Tout commence avec le raisonnement suivant. Si y≡x [N]y \equiv x \ [N] et si x=x0⋅x1⋅x2⋅x3x = x_0 \cdot x_1 \cdot x_2 \cdot x_3, alors :

y ≡x0⋅x1⋅x2⋅x3 [N]≡(x0 [N])⋅(x1 [N])⋅(x2 [N])⋅(x3 [N]) [N]\begin{aligned} y \ &\equiv x_0 \cdot x_1 \cdot x_2 \cdot x_3 \ [N] \\ &\equiv (x_0 \ [N]) \cdot (x_1 \ [N]) \cdot (x_2 \ [N]) \cdot (x_3 \ [N]) \ [N] \end{aligned}

Prenons un cas un peu plus particulier. Comme n’importe quel nombre, l’exposant EE peut être décomposé en une somme de puissances de 2, ça revient à l’écrire en notation binaire. Par exemple, 26=24+23+2126 = 2^4 + 2^3 + 2^1. De manière plus générale, on peut écrire que E=∑i=0n−1ai⋅2iE = \displaystyle\sum_{i = 0}^{n - 1} a_i \cdot 2^i, avec aia_i qui ne peut valoir que 0 ou 1 et nn la première puissance de 2 supérieure à EE. De sorte que la fonction de chiffrement peut se décomposer comme suit (on se rappellera que ab1+b2=ab1×ab2a^{b_1 + b_2} = a^{b_1} \times a^{b_2}).

y≡xE [N]≡x∑i=0n−1ai⋅2i [N] ≡[∏i=0n−1(x2i)ai] [N]≡[∏i=0n−1(x2i [N])ai] [N]\begin{aligned} y & \equiv x^E \ [N] \equiv x^{\sum_{i = 0}^{n - 1} a_i \cdot 2^i} \ [N] \\ \ & \equiv \begin{bmatrix}\prod_{i = 0}^{n - 1} (x^{2^i})^{a_i}\end{bmatrix} \ [N] \equiv \begin{bmatrix}\prod_{i = 0}^{n - 1} (x^{2^i} \ [N])^{a_i}\end{bmatrix} \ [N] \end{aligned}

En outre, x2≡x⋅x [N]≡(x [N])⋅(x [N])[N]x^2 \equiv x \cdot x \ [N] \equiv (x \ [N]) \cdot (x \ [N]) [N], ce qui signifie de manière plus générale que xn≡(x [N])⋅(xn−1 [N]) [N]x^n \equiv (x \ [N]) \cdot (x^{n-1} \ [N]) \ [N].

Ainsi, en introduisant le modulo à chaque étape de la multiplication, on réalise plus d’opérations mais avec des nombres beaucoup plus petits. On peut alors définir l’algorithme suivant pour calculer l’exponentiation modulaire xE [N]x^E \ [N].

  1. On décompose EE en puissances de 2 pour obtenir les coefficients aia_i.
  2. On pose y0=x0=1y_0 = x_0 = 1.
  3. xi=(xi−1)2 [N]x_i = (x_{i-1})^2 \ [N].
  4. yi=yi−1⋅(xi)ai [N]y_i = y_{i-1} \cdot (x_i)^{a_i} \ [N]. Cette étape peut être sautée si ai=0a_i = 0, car elle revient à multiplier par 1.
  5. Si i+1<ni+1 < n, retourner à l’étape 3 avec le ii suivant.
  6. Le résultat voulu est le dernier yiy_i.

Voilà tout pour l’exponentiation modulaire. Je vous avais également parlé d’une combine qui permet de simplifier et donc accélérer le déchiffrement ou la signature par clé privé. Le principe général est d’utiliser le théorème des restes chinois pour utiliser des exposants beaucoup plus petits que DD : il faudra faire deux exponentiations modulaires, mais tout mis bout à bout le calcul prendra en fait quatre fois moins de temps environ. Pour l’explication détaillée (en anglais, j’en suis le premier désolé), voyez ce lien.

  1. On commence par calculer les valeurs dP=D [P−1]d_P = D \ [P-1], dQ=D [Q−1]d_Q = D \ [Q-1] et Q−1Q^{-1} l’inverse modulo PP de QQ. Pour calculer cette dernière valeur, on utilisera l’algorithme d’Euclide étendu que nous avons vu au chapitre 2 section 3. Celui-ci nous avait servi à calculer DD à partir de EE et MM : ici, nous allons calculer Q−1Q^{-1} en utilisant QQ à la place de EE et PP à la place de MM.
  2. Ensuite on calcule x1=ydP [P]x_1 = y^{d_P} \ [P] et x2=ydQ [Q]x_2 = y^{d_Q} \ [Q].
  3. Enfin, on peut obtenir le message déchiffré avec la formule suivante : x=x2+Q×(Q−1⋅(x1−x2) [P])x = x_2 + Q \times (Q^{-1} \cdot (x_1 - x_2) \ [P]). Si x1<x2x_1 < x_2, pensez à utiliser (x1−x2+P)(x_1 - x_2 + P) à la place de (x1−x2)(x_1 - x_2).

Conseils informatiques

2,21 gigowatts

Dans un langage comme le C, les types natifs d’entiers permettent de représenter des nombres sur 64 bits. Certaines instructions en assembleur x86 permettent de monter jusqu’à 128 bits. En tout état de cause, on est très loin des clés de 1024 voire 2048 ou 4096 bits qu’un programme implémentant RSA a besoin de pouvoir manipuler. Il faut donc recourir à une bibliothèque d'arithmétique multi-précision.

La plus utilisée en C (et en C++ par l’intermédiaire d’une surcouche) est la GNU Multiple Precision Arithmetic Library ou GMP pour les intimes. Ce n’est pas la seule : en C++, la Class Library for Numbers ou CLN est nettement moins utilisée mais présente l’avantage d’être codée nativement en C++, plutôt que « d’enrober » du C. Mais objectivement, la GMP domine le paysage informatique. En effet, de nombreux langages implémentent l’arithmétique multi-précision dans leur bibliothèque standard (C#, Java, OCaml, Perl, PHP, etc.) voire nativement dans le langage (Erlang, Haskell, Python, Ruby, etc.) ; cependant, la plupart de ces langages font en réalité appel à GMP de manière transparente pour l’utilisateur.

Cela étant, nous n’expliquerons pas comment fonctionne cette bibliothèque, pour deux raisons. Tout d’abord, c’est une bibliothèque extrêmement puissante, qui nécessiterait un tutoriel à elle seule, et ce ne serait pas lui faire justice que d’en expliquer quelques bribes sur un coin de table. Ensuite, il n’y a pas grand intérêt à créer une implémentation de RSA en C/C++ : la librairie OpenSSL, très largement utilisée par les logiciels ayant besoin de SSL, et la librairie libgcrypt, utilisée surtout par GnuPG, toutes deux écrites en C, font cela bien mieux que vous ou nous n’en serions capable. Si vraiment vous voulez travailler en C/C++, essayez plutôt de trouver un moyen d’améliorer ces deux bibliothèques, ou un projet voisin (CyaSSL, GnuTLS, PolarSSL…). En revanche, il peut être intéressant de créer des implémentations natives dans d’autres langages, plutôt que de recourir indirectement à ces deux bibliothèques, en particulier pour les langages strictement fonctionnels.

Pensez donc simplement à utiliser des entiers n’ayant pas de limite de taille si le langage ne le fait pas automatiquement à votre place

Y’a écrit quoi, là ?

Le gros inconvénient du chiffrement RSA, c’est qu’une fois chiffré, un simple texte ne ressemble plus à rien, et cela devient excessivement difficile de l’enregistrer dans un fichier ou de le transmettre par mail. De même, les clés publiques et clés privées étant de grands nombres, il n’est pas dit que les interpréter comme du texte donne quoi que ce soit de potable. Ce n’est pas trop gênant pour les conserver, déjà plus pour les transmettre à quelqu’un.

La solution la plus couramment adoptée, et à mon avis la plus simple et la plus économique, consiste à convertir tout ce qui n’est pas du texte brut ou un type de fichier usuel (JPEG, etc.) en base64. Cet encodage consiste à découper les données en tronçons de trois octets soit 24 bits, et à représenter chaque groupe de 6 bits de ce tronçon par un caractère : comme il n’y a plus que 64 possibilités, on peut n’utiliser que des caractères courants. En l’occurrence, les lettres de l’alphabet en minuscule et majuscule, les dix chiffres et les caractères « + », « / » et « = », ou alors, dans une variante destinée à être utilisée dans les URL, « - », « _ » et « = ».

Je vous conseille vivement de l’utiliser aussi.

Mettons de l’ordre

Dans une implémentation complète d’un logiciel utilisant RSA, il y aura nécessairement plusieurs couches. La première correspond aux outils de bas niveau nécessaires pour faire fonctionner les algorithmes : je pense en particulier au générateur de données aléatoires. La deuxième regroupe les fonctions mathématiques qui sont utiles en cryptographie mais qui peuvent avoir d’autres usages : PGCD, exponentiation modulaire, inverse modulaire, etc. La troisième est la couche vraiment cryptographique : on y trouvera les fonctions de hachage, les algorithmes de cryptographie symétrique et l’algorithme RSA proprement dit. La quatrième implémente les outils nécessaires à une utilisation en situation réelle de RSA : génération de clés robustes, lutte contre les attaques par chronométrage, OAEP, stockage de clés, réseau de confiance, etc. La cinquième constitue l’interface utilisateur donnant accès aux quatre couches inférieures. Elle n’est pas indispensable si vous ne voulez pas faire un outil spécifique, par exemple un clavardeur en P2P chiffré, mais simplement une bibliothèque utilisable par d’autres gens.

À partir de là, tout dépend jusqu’à quel point vous voulez réinventer la roue. La plupart des langages ont dans leur bibliothèque standard une implémentation des deux premières couches. Nombre d’entre eux implémentent aussi tout ou partie de la troisième. Et si vous creusez, il y a des chances que quelqu’un ait déjà implémenté la quatrième couche aussi. Dans ce dernier cas, n’abandonnez pas tout de suite : voyez s’il s’agit d’une implémentation native ou seulement d’une interface avec une bibliothèque en C ou équivalent. Vous pourriez avoir tout de même quelque chose à apporter.

En tout état de cause, il peut être judicieux de regrouper les deux premières couches dans une bibliothèque, qui pourra toujours vous servir sur d’autres projets, et les deux suivantes dans une autre bibliothèque, que vous pourrez interfacer à plusieurs logiciels différents.

C’est pourquoi, dans la dernière section de ce tutoriel, je ne donnerai pas une implémentation complète, beaucoup trop longue à programmer et dont le code prendrait beaucoup trop de place, mais des exemples commentés, dans plusieurs langages, de certaines des fonctions à implémenter.

Exemples

Base64 (en PHP)

Un exemple d’implémentation du Base64 en PHP. En soi, ce n’est pas nécessaire puisque le langage possède nativement les fonctions base64_encode() et base64_decode(). Cependant, l’exemple donné ici a deux intérêts. Tout d’abord, il offre également une paire de fonctions pour le base64 « spécial URL ». Ensuite, il met en évidence la principale difficulté que vous serez amenés à rencontrer si vous voulez implémenter du RSA en PHP : quand un script PHP lit un fichier ou reçoit des arguments par l’URL, ces données sont de type texte, alors que toutes les fonctions mathématiques ou bit-à-bit travaillent sur des nombres, et il est excessivement fastidieux de faire la conversion de l’un à l’autre.

En d’autres termes, PHP est un mauvais langage pour la cryptographie.

<?php

$b64tc = str_split("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/", 1);
// Plus rapide à coder que de taper le tableau à la main.
// b64tc est pour base64_table_caracteres

function base64($texte)	{

global $b64tc;

if ($texte == "") return ""; // Pour une chaine vide, pas la peine de suivre toute la fonction.

$morceaux = str_split($texte, 3); // Le texte d'entrée est découpé en tronçons de trois caractères de long.
$resultat = "";

for ($i = 0; $i < count($morceaux); $i++)	{

    $caras = str_split($morceaux[$i], 1); // Les caractères individuels, pour pouvoir obtenir la valeur numérique de la chaîne.
				// Sans cela, PHP ne nous permet pas d'utiliser les opérateurs bit-à-bit.

    if (strlen($morceaux[$i]) == 3)	{ // On a un tronçon complet. C'est le cas le plus courant, 
				// c'est pourquoi on le met en premier, pour économiser des comparaisons inutiles.
        $morceaux[$i] = ord($caras[0])*0x10000 + ord($caras[1])*0x100 + ord($caras[2]); // On le convertit en un nombre.

        $bloc1 = ($morceaux[$i] & 0xFC0000) >> 18;
        $bloc2 = ($morceaux[$i] & 0x03F000) >> 12;
        $bloc3 = ($morceaux[$i] & 0x000FC0) >> 6;  // On met à profit les opérateurs bit-à-bit pour
        $bloc4 = ($morceaux[$i] & 0x00003F);       //     obtenir les 4 morceaux du tronçon.

	$resultat .= $b64tc[$bloc1] . $b64tc[$bloc2] . $b64tc[$bloc3] . $b64tc[$bloc4];
    } // Fin du cas principal

    else if (strlen($morceaux[$i]) == 2)	{

        $morceaux[$i] = ord($caras[0])*0x100 + ord($caras[1]); // On le convertit en un nombre.

        $bloc1 = ($morceaux[$i] & 0xFC00) >> 10;
        $bloc2 = ($morceaux[$i] & 0x03F0) >> 4;
        $bloc3 = ($morceaux[$i] & 0x000F) << 2;

        $resultat .= $b64tc[$bloc1] . $b64tc[$bloc2] . $b64tc[$bloc3] . '=';

    } // Fin du premier cas particulier

    else	{ // Si strlen($morceaux[$i]) == 1, donc.

        $morceaux[$i] = ord($caras[0]);

        $bloc1 = ($morceaux[$i] & 0xFC) >> 2;
        $bloc2 = ($morceaux[$i] & 0x03) << 4;

        $resultat .= $b64tc[$bloc1] . $b64tc[$bloc2] . '==';

    } // Fin du second cas particulier

} // Fin de la boucle

return $resultat;

} // Fin de function base64($texte)



function base64_dechiffrer($texte)	{

global $b64tc;

$morceaux = str_split($texte, 4); // Le texte d'entrée est découpé en tronçons de quatre caractères de long.
$resultat = "";

for ($i = 0; $i < count($morceaux); $i++)	{
    $blocs = str_split($morceaux[$i], 1);

    if ($blocs[3] != '=')	{ // Cas général, on a un tronçon complet.

        $en_numerique = (array_keys($b64tc, $blocs[0])[0] << 18) | (array_keys($b64tc, $blocs[1])[0] << 12) | (array_keys($b64tc, $blocs[2])[0] << 6) | array_keys($b64tc, $blocs[3])[0]; // D'abord on travaille sur des nombres, pour reconstituer la valeur numérique du tronçon de 3 caractères
        $resultat .= chr(($en_numerique & 0xFF0000)>>16) . chr(($en_numerique & 0x00FF00)>>8) . chr($en_numerique & 0x0000FF);
            // Puis on récupère chaque caractère du tronçon à partir de sa valeur numérique.
    } // Fin du cas général

    else if ($blocs[2] != '=')	{ // Le tronçon n'a que deux caractères.

        $en_numerique = (array_keys($b64tc, $blocs[0])[0] << 10) | (array_keys($b64tc, $blocs[1])[0] << 4) | (array_keys($b64tc, $blocs[2])[0] >> 2);
        $resultat .= chr(($en_numerique & 0xFF00)>>8) . chr($en_numerique & 0x00FF);

    } // Fin du premier cas particulier

    else { // Le tronçon n'a qu'un caractère.

        $resultat .= chr((array_keys($b64tc, $blocs[0])[0] << 2) | (array_keys($b64tc, $blocs[1])[0] >> 4));

    } // Fin du second cas particulier

} // Fin de la boucle

return $resultat;

} // Fin de function base64_dechiffrer($texte)



/****** Mode URL ******/
// Les deux fonctions suivantes se contentent de remplacer les deux caractères qui diffèrent d'avec le base64 normal.

function base64_url($texte)	{

return str_replace(array('+', '/'), array('-', '_'), base64($texte));

}

function base64_url_dechiffrer($texte)	{

return base64_dechiffrer(str_replace(array('-', '_'), array('+', '/'), $texte));

}

?>

Fonction RSA et annexes (en Haskell)

On implémente ici la fonction de chiffrement/déchiffrement de RSA ainsi que deux variantes de la fonction de déchiffrement optimisé (cf. supra « Conseils mathématiques »), accompagnées des trois fonctions mathématiques indispensables pour les mener à bien : l’exponentiation modulaire, l’algorithme d’Euclide étendu et l’inverse modulaire.

Le Haskell est particulièrement adapté ici. Utiliser un langage strictement fonctionnel est une très bonne idée quand on ne s’intéresse pas directement à l’interface utilisateur mais seulement aux calculs qui doivent être faits. En outre, les principales fonctions mathématiques ici présentées utilisent massivement la récursivité et Haskell est très fort à ce jeu-là.

Voyez en outre la concision du code : il y a presque plus de commentaires que de code.

-- Exponentiation modulaire
-- x = base, e = exposant, n = modulo
expoMod :: Integer -> Integer -> Integer -> Integer
expoMod x e 0 = error "expoMod : Le modulo 0 n'existe pas."
expoMod x 0 n = 1
expoMod x e n = (base (e `mod` 2) * expoMod ((x*x) `mod` n) (e `div` 2) n) `mod` n
        where base 0 = 1
              base 1 = x

-- Algorithme d'Euclide étendu
-- Pour bien comprendre comment la récursivité est mise en place, il faut bien voir que
--   si    b*u' + r*v' = pgcd, a*u + b*v = pgcd et a=b*q + r
--   alors r = a - b*q
--   donc  pgcd = b*u' + (a - b*q)*v' = a*v' + b*(u' - q*v')
--   donc  u = v' et v = (u' - q*v')
--   ce qui permet d'introduire la récursivité.
--   Pour plus de sécurité, on effectue beaucoup de vérifications sur les paramètres.
euclideExt :: Integer -> Integer -> (Integer, Integer, Integer)
euclideExt a 0 = (1, 0, a)
euclideExt a b
        | a < b = euclideExt b a
        | a == 0 = error "euclideExt : Au moins un des deux arguments doit être différent de 0."
        | a < 0 = euclidExt (-a) b
        | b < 0 = euclidExt a (-b)
        | otherwise = (v', u' - q*v', pgcd)
        where (q, r) = a `quotRem` b
              (u', v', pgcd) = euclideExt b r

-- Inverse modulaire
-- a = base, n = modulo
-- La fonction retourne 0 en cas d'erreur
invMod :: Integer -> Integer -> Integer
invMod a 0 = error "invMod : Le modulo 0 n'existe pas."
invMod a n
        | pgcd == 1 = if inv < 0 then inv + n else inv
        | otherwise = error "invMod : La base et le modulo doivent être premiers entre eux."
        where (_, inv, pgcd) = euclideExt n a

-- L'algorithme de chiffrement, ou le déchiffrement non optimisé, n'est qu'un appel à
--   la fonction d'exponentiation modulaire avec les bons arguments. Il n'y a donc pas
--   lieu de l'implémenter indépendamment

-- Déchiffrement optimisé avec toutes les infos précalculées
-- y = message chiffré, (p, q, dp, dq, qinv) = clé privée complète
rsaDechiffre :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer -> Integer
rsaDechiffre y p q dp dq qinv = xbis + q * ((qinv * diffxs) `mod` p)
        where diffxs | xsemel < xbis = xsemel - xbis + p | otherwise = xsemel - xbis
              xsemel = expoMod y dp p
              xbis = expoMod y dq q

-- Déchiffrement semi-optimisé où la clé privée complète doit être calculée
-- y = message chiffré, (p, q, d) = clé privée de base
rsaDechiffre' :: Integer -> Integer -> Integer -> Integer -> Integer
rsaDechiffre' y p q d = rsaDechiffre y p q (d `mod` (p-1)) (d `mod` (q-1)) (invMod q p)

OAEP (en Python)

La fonction présentée ici met en place l’OAEP : si vous ne vous souvenez plus de ce que c’est, courrez lire la section « Bourrage papier » du chapitre précédent. Elle n’agit que dans un sens, à savoir emballer le message pour qu’il respecte le standard, mais elle sait gérer à la fois des textes de la bonne taille et des textes trop long. Pour l’écrire, on a utilisé Python, pour la simplicité du code, mais aussi pour bénéficier des nombreuses fonctions de hachage que le langage implémente dans sa bibliothèque standard.

Si vous voulez vous entraîner, vous pouvez modifier la fonction de manière à ce qu’elle puisse utiliser d’autres fonctions de hachage produisant des condensats de taille différente à ce qui est présenté là. Puis, vous pourriez implémenter une nouvelle fonction qui, en fonction de la longueur de la clé, appelle oaep_base() avec les fonctions de hachage les plus adaptées.

# -*- coding: utf8 -*-
import os
import hashlib

def xor_str(s1, s2):
  # Effectue un "ou exclusif" entre les deux chaînes
  return "".join(chr(ord(a) ^ ord(b)) for a, b in zip(s1, s2))

def oaep_base(msg):
  if len(msg) <= 64:
    # On complète la chaîne avec des "0" jusqu'à ce 
    # qu'elle ait une longueur de 64
    msg = msg + chr(0) * (64 - len(msg)) 

    # 32 octets de données aléatoires
    R = os.urandom(256) 

    # On chiffre R
    G = hashlib.sha512(R)

    # XOR
    X = xor_str(msg, str(G))

    # On chiffre X
    H = hashlib.sha256(X)

    # XOR
    Y = xor_str(str(H), str(R))

    return X + Y
  else:
    # len(msg) = 64 * q + len(msg)%64 
    # Donc len(msg) = 64 * (q+1) - 64 + len(msg)%64
    # Donc len(msg) + 64 - len(msg)%64 est un multiple de 64.
    msg = msg + chr(0) * (64 - len(msg)%64)

    # Découpage en tronçons de 512 bits i.e. 64 caractères
    data = [msg[64*i:64*(i+1)] for i in range(len(msg)/64)]

    # On applique oaep_base à chaque tronçon
    data = map(oaep_base, data)
    
    return data

Voilà, on a fait le tour de la question. Si vous avez des questions ou des remarques, n’hésitez pas à commenter. Par ailleurs, si vous avez des implémentations à proposer dans d’autres langages informatiques, nous serions ravis d’en entendre parler.