Øprésentation :

Les avantages offerts par le cryptage à clef publique entraîna tout naturellement la réalisation d’algorithmes suivant ce procédé. Si celui à empilement, de Merkle fut le premier du genre, le RSA (du nom de ses inventeurs Ron Rivest, Adi Shamir et Leonard Adleman, et datant de 1978) parut peu après. Son indéniable popularité provient de sa simplicité (du point de vue de sa réalisation comme de sa compréhension). Par ailleurs, même si sa sécurité n’est pas théoriquement démontrée, RSA résiste pour l’instant à toute les tentatives de craquage, ce qui suggère un certain niveau de confiance dans l’algorithme.

En fait, les clefs publiques et privées sont générées à partir de deux grands nombres premiers (plus de 100 chiffres). Retrouver le texte en clair à partir d’une des clefs est équivalent à la factorisation du produit des deux nombres premiers. Par conséquent le niveau de sécurité de RSA dépend directement de la difficulté de factoriser des grands nombres. 

ØGénération des clefs :

La première étape consiste à choisir deux nombres premiers p et q et d’en calculer le produit :

n = p * q

Ensuite, la clef de chiffrement e est choisie aléatoirement, de telle sorte que e et 

(p - 1)*(q - 1) soient premiers entre eux. 

Il reste alors à calculer la clef de déchiffrement d, qui vérifie :

d = e^-1 mod ((p - 1)*(q - 1))

Ainsi :

e*d = 1 mod ((p - 1)*((q - 1))

d et e sont ainsi premiers entre eux.

Les nombres e et n forment la clef publique, le nombre d est la clef privée. p et q ne servent plus : ils peuvent être jetés, mais pas révélés.

Remarquons que pour le programme réalisé en Scheme on a choisi les nombres :

p=1234567891011121314151617181912139

q=2019181716151413121110987654451

n=2492816912877266687794240983917596973374166417784717890774280689

e=135791113151719212325272931

d=1672375233889116393189907035665861569376320879041961999959883771

ØChiffrement et déchiffrement d’un message.

Pour commencer, découpons le message m à crypter en blocs numériques ayant chacun une représentation unique modulo n. Ainsi, si p et q sont tous deux des nombres premiers de 100 chiffres, n aura tout juste moins de 200 chiffres et chaque bloc de message m_i doit avoir juste moins de 200 chiffres. Le message chiffré c sera constitué de manière similaire de blocs c_i d’à peu près la même longueur.

La formule de chiffrement est simplement :

c_i = m_i ^e mod n

Pour déchiffrer un message, prenons chaque bloc c_i et calculons :

m_i = c_i^d mod n

Cette formule permet de retrouver le message de départ. En effet (toutes les opérations sont effectuées modulo n) :

c_i ^d = (m_i ^e) ^d = m_i^ed = m_i ^{k (p - 1) (q - 1) + 1} = m_i * m_i ^{k (p - 1) (q - 1)} = m_i*1 = m_i

Le message aurait évidemment pu être chiffré avec d et déchiffré avec e.

ØUn petit exemple.

Afin de clarifier les idées voici un exemple simple :

Prenons p = 47 et q = 71, alors

n = p*q = 3337

La clef de chiffrement e ne doit pas avoir de facteurs communs avec :

(p - 1)*(q - 1) = 46*70 = 3220

Choisissons e aléatoirement, ... disons 79. Dans ce cas :

d = 79^-1 mod 3220 = 1019

Ce nombre peut être calculé à l’aide de l’algorithme d’Euclide étendu (voir II).

Il nous reste alors à publier e et n, à oublier p et q, et à garder d secret.

Pour chiffrer le message : m = 688232687966683

procédons d’abord à son découpage en blocs de trois chiffres (c’est le maximum dans ce cas). On obtient :

m₁ = 688

m₂ = 232

m₃ = 687

m₄ = 966

m₅ = 668

m₆ = 3

Le premier bloc est chiffré par : 688⁷⁹ mod 3337 = 1570 = c₁

En effectuant la même opération pour tous les blocs, il vient :

c = 1570 2756 2091 2276 2423 158

Le déchiffrement s’effectue de la même manière, mais en utilisant la clef de déchiffrement. Donc :

1570¹⁰¹⁹ mod 3337 = 688 = m₁

Le reste du message s’obtient par la même méthode.

ØAvantages et inconvénients de l’algorithme RSA.

ØAvantages.

· Un des gros avantages du RSA est d’être un algorithme de chiffrement à clef publique. Il échappe ainsi aux inconvénients majeurs des codages à clef secrète, notamment la transmission des clefs (voire la présentation générale du cryptage pour plus de détails).

· De part sa sécurité, RSA est principalement utilisé pour transmettre les clefs des algorithmes à clef secrète comme le DES ou pour les signatures, ce qui atténue le problème de la transmission des clefs pour de tels algorithmes.

· RSA est actuellement considéré comme incassable en un temps ou avec des moyens raisonnables. 

ØInconvénients.

· Un premier problème réside dans le choix des deux nombres premiers p et q. Il est en effet préférable de ne pas choisir ces nombres sans précautions. De fait, les concepteurs du système RSA ont donné un certain nombre de règles qu’il est conseillé de suivre lorsqu’il s’agit de choisir le quadruplet (p, q, d, e), car un mauvais choix de ces paramètres peut rendre le système de codage relativement vulnérable et cassable par un bon algorithme de factorisation spécialisé.

Choix de p et q :

- prendre p et q de tailles sensiblement différentes, mais pas trop.

- choisir des nombres premiers p et q "sûrs", de la forme 2x + 1, avec x premier, et tel que x - 1 possède de grands facteurs premiers.

Choix de d et e :

- choisir d en premier, tel que d et (p -1)*(q - 1) soient premiers entre eux.

- choisir ensuite e et vérifier que e >> log₂ (n).

- ne retenir e que si n et e sont premiers entre eux.

retour aux exemples.