Le chiffrement RSA

Introduction

Le chiffrement RSA a été inventé en 1978 par Rivest, Shamir et Adleman. C'est un des cryptosystèmes asymétrique les plus connus et les plus utilisés aujourd'hui. Ce chiffrement est sûr si l'on utilise des clés de taille suffisamment grande (entre 1024 et 4096 bits).

Le chiffrement RSA est homomorphe pour la multiplication. La version RSA de 1978 est déterministe, cela signifie que pour une clé privée donnée, le chiffré est toujours le même. Il s'agit d'une faille de RSA qui permet de retrouver le texte d'origine. De nouvelles versions de RSA probabilistes ont donc été développées depuis 1994 pour résoudre ce problème, en ajoutant du bruit au chiffré ou en découpant le message en blocs, par exemple.

Cependant, la version probabiliste de RSA n'est plus homomorphe pour la multiplication, dans notre démonstration nous utiliserons donc la version d'origine de RSA.

Le chiffrement RSA repose sur le problème de la factorisation de grands nombres.

Algorithme

1. Générer 2 grands nombres premiers, p et q, de même taille et tel que leur produit N=pq fasse le nombre de bits requis.
2. Calculer \( N = p*q \) et \( \phi=(p-1)(q-1) \)
3. Choisir un entier e, tel que \( 1 < e < \phi \) et tel que \( gcd(e,phi)=1 \). Ici e = 65537.
4. Calculer l'exposant secret d, tel que \( 1 < d < \phi \) et tel que \( e*d = 1 (\mod \phi) \) (d est l'inverse modulaire de e modulo phi).
5. La clef publique est \( (n,e) \).
6. La clef privee \( (d, p, q) \). d, p, q et \( \phi \) doivent rester secrets.

Chiffrement

$$c = m^e \mod N$$

Déchiffrement

$$m = c^d \mod N $$

Homomorphe pour la multiplication

Soient m1, m2, deux messages à chiffrer, $$c_1 \equiv m_1^e [n], c_2 \equiv m_2^e [n] $$ Montrons que RSA est homormophe pour la multiplication : $$c_1 * c_2 \equiv m_1^e [n] * m_2^e [n] \\ \Leftrightarrow c_1 * c_2 \equiv m_1^e * m_2^e [n] \\ \Leftrightarrow c_1 * c_2 \equiv (m_1 * m_2)^e [n] \\ \\ \Leftrightarrow D(c_1*c_2) \equiv ((m_1*m_2)^e [n])^d [n] \\ \Leftrightarrow D(c_1*c_2) \equiv ((m_1*m_2)^e)^d [n] \\ \Leftrightarrow D(c_1*c_2) \equiv m_1 * m_2$$

Sécurité du chiffrement

Factorisation et problème RSA:

Le cryptosystème RSA (du nom de ses créateurs : Rivest, Shamir et Adleman) est un cryptosystème asymétrique très utilisé. Il a aussi la particularité d'être, dans sa première version, homomorphe pour la multiplication.

Problème de la factorisation :

D’après le théorême fondamental de l’arithmétique, tout nombre entier naturel n supérieur ou égal à 2 peut se factoriser en produit de nombres premiers. Cette factorisation est unique, à l’ordre des facteurs près. Par exemple, la factorisation de 188 309 est : $$188 309 = 11*17*19*53$$ S’il est aisé, une fois la factorisation obtenue, de retrouver n - il suffit de calculer le produit - il est en revanche complexe d’effectuer l’opération inverse : obtenir la factorisation à partir de n.

Toutefois, le développement de l’informatique quantique est en forte croissance et il existe un algorithme quantique, formulé en 1994 par Peter Shor, qui permet de résoudre le problème de la factorisation. Le problème de la factorisation fait donc partie des problèmes de cryptographie qui ne survivront probablement pas à l’instauration de l’ère quantique.

Problème RSA :

L’algorithme de RSA repose sur deux problèmes mathématiques.

Le premier intervient lors de la création des clés et repose sur le problème de factorisation, la clé publique provenant d’un produit de deux nombres premiers élevés, il est très complexe d’obtenir la clé privée (les deux nombres premiers en question).

Le deuxième intervient lors du chiffrement et du déchiffrement :

En connaissant N (tel que N=pq, avec p et q premiers, distincts, et non connus), e>1 tel que e=1 mod (p-1)(q-1), et c = m^e mod N, trouver la valeur de m. Cette opération est très complexe si on ne connait pas d tel que ed = 1 mod (p-1)(q-1). Sinon, elle est immédiate : m = c^d mod n.

Ce problème comporte un certain nombre de variantes telles que le problème de résiduosité quadratique, où e est fixé à 2.

Démonstration

* Calculer

Résultats attendus :

Paramètres du cryptosystème RSA

Génération de deux grands nombres premiers différents.

Calcul de \(N = p*q\) et \( \phi = (p-1) * (q-1) \)

On pose e = 65537 et on cherche d tq \( e*d = 1 \mod \phi \). d doit être positif.

Environnement chiffré

Chiffrement avec la clé publique {N,e}, puis envoi des données sur le cloud.

Opérations sur les chiffrés sur un cloud

Déchiffrement

Récupération des données et déchiffrement avec la clé privée {d,p,q}

Pour aller plus loin

Présentation de l'algorithme GnuPG v1.2.3 et explications concernant la méthode de calcul des clefs et en particulier le choix de \( e \): How to compute RSA keys ?