Ronald Rivest,

Adi Shamir

et Leonard Adleman

 

Le chiffrement RSA : un calcul complet

De façon concrète, le chiffrement RSA consiste à choisir deux nombres premiers, 5 et 11 par exemple, et considérer l'indicatrice d'Euler de 55, soit 40. On choisit alors un nombre premier avec 40, comme 3. La clef publique est prête, il s'agit du couple (55, 3). Cette clef permet de chiffrer tout nombre x entre 0 et 54 par f (x) = x³ (mod 55). La fonction de chiffrement est bien une application de ℤ / 55ℤ dans lui-même. Par exemple, f (51) = 46, mais n'essayez pas de faire le calcul à la main, utilisez plutôt un ordinateur !

Déchiffrer demande de disposer d'un nombre a tel que 3a – 1 soit divisible par 40. Un tel nombre existe car 3 et 40 sont premiers entre eux. On trouve que 27 convient : 3 × 27 = 81. Le déchiffrement consiste alors à reprendre les opérations de chiffrement en remplaçant 3 par 27. La fonction de déchiffrement est donc g (x) = x²⁷ (mod 55). On trouve bien g (46) = 51, mais cela ne suffit pas pour vérifier que g est l'inverse de f . Pour cela, on utilise la propriété énoncée à la fin de l'article précédent, qui prouve que x⁸¹ = x (mod 55), ce qui implique que f et g sont inverses l'un de l'autre.

Chiffrement RSA et cartes bancaires

Le chiffrement des cartes bancaires repose sur la méthode RSA et le nombre de deux cent trente-deux chiffres suivants : 15 50880 80278 37692 98423 92150 07513 07878 47102 02152 06711 10279 31119 90113 87539 45534 59999 75760 53046 71735 85609 15975 55389 79740 89381 73344 04367 47047 80986 39006 99066 79096 72893 30814 05044 93596 95145 08676 23994 24934 40750 58927 00157 39962 37452 93632 51827, produit de deux nombres premiers tenus secrets par le Groupement interbancaire (GIE). À partir de ces données secrètes, le GIE a produit la clef privée ainsi que la clef secrète, qui sont deux exposants, comme dans le cas où l'on part du nombre 55 = 5 × 11.

Lorsque vous faites une demande de carte, votre banque produit des informations, qu'elle fournit au GIE. À partir de celles-ci, ce dernier forme le numéro à seize chiffres visible sur la carte. Il le chiffre à l'aide de sa clef privée pour former un numéro d'authentification. Ces données sont stockées dans la puce de la carte.

Quand vous insérez votre carte dans le terminal bancaire, chez un commerçant, le traitement commence par une phase d'authentification. Les deux numéros sont lus et le terminal contrôle, par le biais de la clef publique, qu'ils se correspondent. Selon le montant autorisé par votre carte, les contrôles s'arrêtent là où le terminal contacte un serveur général pour voir s'il n'y a pas d'interdit bancaire, d'opposition ou si le compte est suffisamment alimenté. Le terminal vous demande alors de saisir votre code personnel de quatre chiffres (code PIN, pour personal identifer number). Celui-ci est transmis à la puce de votre carte, qui vérifie son exactitude. Si elle reçoit successivement trois codes incorrects, elle se fige et devient inutilisable. Si le code reçu est correct, la puce mémorise le montant et la date de la transaction, elle vérifie que la somme des montants des transactions écoulées dans la semaine n'excède pas un certain plafond et donne son accord au terminal en produisant un numéro de transaction, qui apparaîtra sur la facturette.

Composez vous-même votre chiffre RSA !

La solidité d'un chiffre RSA dépend de la longueur de sa clef, c'est-à-dire des deux nombres premiers qui le définissent, et d'un choix aléatoire de ces nombres. La coutume est de compter la longueur en bits. De nos jours, les plus solides font 2 048 bits ; on se contentera ici d'un chiffre à 64 bits (vingt chiffres décimaux). Choisissons donc aléatoirement deux nombres premiers d'environ dix chiffres chacun. En utilisant Maple, après avoir réinitialisé la fonction rand avec l'instruction randomize, saisissez alea:=rand(1..10^10): nextprime(alea());
 

On l'utilise deux fois pour obtenir p, q, n = p q et son indicatrice d'Euler m = (p – 1)(q – 1). On trouve par exemple p = 7 419 669 083, q = 1 110 693 341, n = 8 240 977 042 911 676 303, m = 8 240 977 034 381 313 880.

Il s'agit alors de trouver a et b tels que a b  \( \equiv\) 1 (mod m). La solution la plus simple est de factoriser m + 1 ou, à défaut,
2m + 1…, grâce à la fonction ifactor de Maple. Ici, on trouve quatre facteurs : 211, 2 218 561, 33 647 et 523 213, ce qui invite à prendre pour a le produit des deux premiers et pour b celui des deux suivants : a = 468 116 371 et b = 17 604 547 811.

Les deux clefs sont donc (a, n) et (b, n). Elles permettent de chiffrer et déchiffrer les nombres x entre 0 et n – 1 ainsi :

f (x) = x^a (mod n) et g (x) = x^b (mod n) .

Ces calculs ne peuvent être réalisés sans précaution ! Il est nécessaire de définir une fonction puissance sans risque de débordement de la capacité de l'ordinateur.

L'idée est de définir la multiplication modulo n, soit Mult := proc(b,c,n) irem(b*c,n); end;

puis la fonction puissance de manière récursive en utilisant l'égalité x^2a = (x^a)² :

Puissance := proc(x,a,n) local y,z;


if a=0 then 1 else y:=Puissance(x,iquo(a,2),n); z:=Mult(y,y,n);

if irem(a,2)=0 then z else Mult(z,x,n) fi fi; end;



On en déduit les fonctions de chiffrement et de déchiffrement :

f:=x−>Puissance(x,468116371,8240977042911676303)

g:=x−>Puissance(x,17604547811,8240977042911676303);

Par exemple :  f(4568231409) = 2810649729268171204 et g(2810649729268171204) = 4568231409.

Vous pouvez ainsi créer les vôtres ! Dans la pratique, ces fonctions sont utilisées soit pour l'authentification, comme dans le cas de carte bancaire, soit pour l'échange de clefs de chiffrements symétriques. Il vous reste alors à créer un chiffrement symétrique pour compléter votre système.