Le chiffrement est une pratique cryptographique permettant de rendre inintelligible la lecture d’une information auprès d’un tiers qui n’aurait pas la clef (ou secret) afin de lire le contenu du message. Comme vous le savez peut-être déjà, il existe deux types de chiffrement : symétrique & asymétrique. A l’inverse du chiffrement symétrique, le chiffrement asymétrique nécessite deux clefs pour son bon fonctionnement ; RSA est basé sur ce système. Dans cet article nous aborderons l’algorithme de chiffrement RSA en décrivant au mieux son fonctionnement ainsi que certaines attaques qui sont susceptibles d’être exploitées. Nous prendrons par convention, deux acteurs, respectivement Alice et Bob pour la suite de cet article afin d’illustrer des acteurs.
1. Fonctionnement de l’algorithme
Le cryptosystème RSA est un algorithme de chiffrement asymétrique créé en 1977 par Ronald Rivest, Adi Shamir et Lenoard Adleman. Etant asymétrique, RSA est basé sur un système de chiffrement à double clefs :
- Clef publique afin de chiffrer un message
- Clef privée afin de déchiffrer un message
Ainsi, afin qu’Alice puisse envoyer un message chiffré à Bob il lui est nécessaire de récupérer la clef publique de Bob. Une fois le message envoyé, Bob n’a plus qu’à se munir de sa clef privée afin de déchiffrer le message envoyé par Alice.
Si Bob souhaite répondre à Alice il devra faire la même opération avec la clef publique d’Alice.
Le schéma suivant illustre les différentes étapes dans un échange secret :
- Alice et Bob génèrent une paire de clefs chacun.
- Alice envoie sa clef publique à Bob.
- Bob envoie sa clef publique à Alice.
- Alice chiffre le message à envoyer avec la clef publique de Bob.
- Bob déchiffre le message à l’aide de sa clef privée.
- Bob chiffre la réponse à l’aide de la clef publique d’Alice et lui envoie.
- Alice déchiffre la réponse envoyée par Bob à l’aide de sa clef privée.
1.1. Création des clefs
Afin de permettre un échange secret entre Alice et Bob il est nécessaire que les deux parties créent une paire de clefs chacun. Pour cela nous devons choisir un module n tel que :
avec p et q premiers et un exposant public e tel que :
avec
Par la suite nous avons besoin de d, exposant privé égal à l’inverse modulaire de e modulo phi(n) tel que :
Nous avons donc la clef publique composée du couple (n, e) ainsi que de la clef privée composée du couple (n, d)
1.2. Processus de chiffrement
Pour la suite de cet article nous prendrons des fonctions développées au préalable afin de gagner du temps :
import binascii
import math
def message_to_int(message):
return int(message.encode('utf-8').hex(), base=16)
def int_to_message(integer):
return binascii.unhexlify(hex(integer)[2:]).decode('utf-8')
def gcd(a, b):
return (a if (b == 0) else gcd(b, a % b))
def total_bits(number):
return int((math.log(number) / math.log(2)) + 1)
def display_values(p, q, n, phi, d):
print('p = %d' % p)
print('q = %d' % q)
print('n = %d (%d bits)' % (n, total_bits(n)))
print('φ(n) = %d' % phi)
print('d = %d\n' % d)
RSA travaille avec des nombres, or ici le but de cette utilisation est de chiffrer une chaîne de caractères ou tout autre type de données. Pour se faire, il est nécessaire de convertir nos données sous forme d’entiers (représentés sous une forme décimale, binaire ou encore héxadécimale). Pour la suite de cet article nous prendrons Python dans sa version 3 afin d’effectuer l’ensemble des opérations nécessaires.
Afin d’illustrer le processus de chiffrement nous prendrons la chaîne « Bonjour comment vas-tu ? » comme message original. Nous devons dans un premier temps convertir la chaîne en entiers puis calculer le texte chiffré c où :
Code :
p = 12891720510343188045004713316180039759528428989301731445761930033945274677788771104497679192758438066264952920046711510442107255288014942404269605732627609
q = 8216488903601457311930280110452039876584206473011974266050997219767782816367397228742327489673321528209592843893174635854427070340917786597049175473842569
e = 65537
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
display_values(p, q, n, phi, d)
m = message_to_int('Bonjour comment vas-tu ?')
c = pow(m, e, n)
print('m = %d' % m)
print('c = %d\n' % c)
Sortie :
p = 12891720510343188045004713316180039759528428989301731445761930033945274677788771104497679192758438066264952920046711510442107255288014942404269605732627609
q = 8216488903601457311930280110452039876584206473011974266050997219767782816367397228742327489673321528209592843893174635854427070340917786597049175473842569
n = 105924678521566120857730964294084397748450952475267005663502881925464365971635302498981400709005395893216159439276446023749196573209070889259630113802987871563574495803579634898205049068369134174449020816132646728626719024291996439897989880084843763563893045911044616045173661789462222220405084637968368887521 (1024 bits)
φ(n) = 105924678521566120857730964294084397748450952475267005663502881925464365971635302498981400709005395893216159439276446023749196573209070889259630113802987850455365081858934277963211622436289498061813558502426934915699465311234502283729656640078161331804298571365280676159027365255136593287676083319187162417344
d = 64897593980140141459030340255128718476487344473189131000909886292524386024063846395800848111275976338561552252395854817760982193326881355821016036125110565929692755723969483849685464328308165092634692075437519533547166190731937229329949541008261164776202763874301768311235268582472490810993145452421107657409
m = 1628988290410733638254639806746562587341167837868727803967
c = 67995313735878491968347612138523855789793839900128894430761512480475105199361678876491731040296546831120782122737636077234845318084214607092615465418279441461853418323595299370728611288588101329605191875664235327705876108565285212069714241096046996601944199789970096412319748693560867225415111567959412226219
Notre message chiffré vaut donc :
67995313735878491968347612138523855789793839900128894430761512480475105199361678876491731040296546831120782122737636077234845318084214607092615465418279441461853418323595299370728611288588101329605191875664235327705876108565285212069714241096046996601944199789970096412319748693560867225415111567959412226219
1.3. Processus de déchiffrement
Afin de procéder au déchiffrement du message nous avons besoin de e et de d calculés plus haut. On calcule en suite le message en clair :
Code :
t = pow(c, d, n)
print('t = %d' % t)
print('message = %s' % int_to_message(t))
Sortie :
t = 1628988290410733638254639806746562587341167837868727803967
message = Bonjour comment vas-tu ?
On retrouve donc ici le message original qui correspondait à la chaîne de caractères « Bonjour comment vas-tu ? ».
2. Pratique RSA
2.1. Exercice
Chiffrez et déchiffrez la lettre A à l’aide des entiers p et q tels que p = 7 et q = 19. Assurez-vous que que le message déchiffré t à partir de c correspond bien au message original m.
2.2. Solution
Code :
p = 7
q = 19
e = 5
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
display_values(p, q, n, phi, d)
m = message_to_int('A')
c = pow(m, e, n)
print('m = %d' % m)
print('c = %d\n' % c)
t = pow(c, d, n)
print('t = %d' % t)
print('message = %s' % int_to_message(t))
Sortie :
p = 7
q = 19
n = 133 (8 bits)
φ(n) = 108
d = 65
m = 65
c = 88
t = 65
message = A
3. Quelques attaques
3.1. Factorisation
La factorisation de nombres premiers est encore un casse-tête pour les mathématiciens modernes. En effet, à partir d’une certaine taille d’entier, la factorisation devient simplement impossible dûe à la contrainte de temps et de puissance de calcul. Dans un cadre non-professionel il peut être difficile de se procurer du très bon matériel afin de casser la clef privée, néanmoins il existe un site internet factordb.com qui répertorie un ensemble de solutions de factorisation de nombres premiers. Prenons l’exemple du process de chiffrement :
n = 870001004569
Après une recherche sur factordb on trouve rapidement que 870001004569 est le produit des deux nombres premiers 900241 et 966409. Pour notre exemple ici, la clef est de 40 bits, et les ordinateurs modernes peuvent encore effectuer des attaques par force brute afin de trouver les facteurs de ce module N si la clef est inférieure ou égale à 256 bits.
De nos jours les standards sont d’au minimum 2048 bits (les logiciels tels qu’openssl ou encore la librairie RSA ne permettent pas la création de clefs inférieures à 2048 bits pour éviter les problèmes de factorisation).
3.2. Faible exposant public
A l’instar du module N, l’exposant public e doit également avoir une taille assez grande afin que le texte chiffré soit passé au moins une fois dans le modulo tel que m^e > n. Prenons l’exemple d’un exposant public e = 5 ainsi que le message « pass ». On sait que :
n = 105924678521566120857730964294084397748450952475267005663502881925464365971635302498981400709005395893216159439276446023749196573209070889259630113802987871563574495803579634898205049068369134174449020816132646728626719024291996439897989880084843763563893045911044616045173661789462222220405084637968368887521
c = 23826350340387474793342460320063959706656337699
On peut facilement vérifier que c < n :
>>> 23826350340387474793342460320063959706656337699 <
105924678521566120857730964294084397748450952475267005663502881925464365971635302498981400709005395893216159439276446023749196573209070889259630113802987871563574495803579634898205049068369134174449020816132646728626719024291996439897989880084843763563893045911044616045173661789462222220405084637968368887521
True
Ainsi, on peut calculer la racine cinquième de c et ainsi retrouver le message original.
Code :
e = 5
c = 23826350340387474793342460320063959706656337699
m = int(pow(c, (1/e)))
print('m = %d' % m)
print('message = %s' % int_to_message(m))
Sortie :
m = 1885434739
message = pass
Bibliographie
https://bitsdeep.com/
https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
https://en.wikipedia.org/wiki/Carmichael_function
https://fr.wikipedia.org/wiki/Indicatrice_d%27Euler
https://medium.com/coinmonks/integer-factorization-defining-the-limits-of-rsa-cracking-71fc0675bc0e
http://laure.gonnord.org/pro/teaching/MIF30/projets2009/nguyen_liu_rapport.pdf
