L'algorithme RSA grâce aux nombres premiers

Rivest, Shamir et Adelman L'algorithme RSA et propriétés mathématiques mises en jeu Animation codage et décodage RSA Aide : le calcul d'une (relativement) grande puissance Pour les plus avertis : démonstration mathématique

Rivest, Adi Shamir et Adelman

En 1977, Martin Gardner divulgateur scientifique bien connu, mit ses lecteurs au défi de déchiffrer un nombre de 129 chiffres en indiquant que la solution exigeait de décomposer un nombre en deux facteurs premiers. Il promettait une belle récompense en dollars...
Les créateurs de ce chiffrement étaient Ron Rivest, Adi Shamir et Len Adelman.
La bonne réponse ne fut reçue que 17 ans plus tard avec la collaboration de plus de 600 personnes.

Il s'agit là de la première utilisation d'un modèle à clé publique et à clé secrète connu sous le nom d'algorithme RSA, sigle correspondant aux initiales des noms des inventeurs de ce chiffrement. C'est un algorithme de très grande sécurité aujourd'hui massivement utilisé.
Le processus de déchiffrement sans connaître la clé secrète est énormément laborieux mais... pas impossible.

L'algorithme

Il repose sur certaines propriétés des nombres premiers.
On choisit d'abord un nombre qui est le produit de deux nombres premiers. Ce produit de deux nombres premiers constitue en quelque sorte une fonction non réversible car une fois le produit obtenu, il est extrêmement difficile de retrouver les valeurs des deux facteurs premiers. Bien entendu si le produit est petit c'est très facile, par exemple 21 est le produit des deux nombres premiers 3 et 7.
Cependant dès que les nombres sont très très grands, cette opération devient incroyablement longue même avec de nombreux ordinateurs très puissants.

Le principe, cryptographie asymétrique

Deux personnages Alice et Bob sont habituellement choisis pour expliciter le principe.
- Alice va construire une clé publique et une clé secrète qu'elle gardera bien précieusement sans la divulguer à quiconque.
- Bob chiffre son message m avec la clé publique communiquée par Alice. Il envoie le résultat à Alice.
- Alice et elle seule pourra déchiffrer le message m avec sa clé privée.

Procédure
Cette partie est plus technique mais n'est toutefois pas indispensable pour utiliser les animations suivantes.

. Alice choisit deux nombres premiers p et q et effectue n = pq.
       Les valeurs p et q sont dénommées nombres RSA.
. Alice détermine la fonction d 'Euler de n notée φ(n) = (p-1)(q-1).
       φ(n) dite aussi indicatrice d 'Euler est la quantité de nombres inférieurs à n et premiers avec n.
       Les propriétés de φ(n) sont très nombreuses.
. Alice cherche un nombre entier e tel que le pgcd (e,φ(n )) = 1. C'est -à-dire tel que φ(n) et l'entier e n'aient aucun diviseur commun.
       Le couple (n, e) constitue la clé publique.
. Alice cherche maintenant le nombre entier unique d tel que
       de = 1 (modulo φ(n)), c'est à dire tel que le reste du produit de dans la division par φ(n) soit égal à 1.
. Cette valeur d est primordiale : c'est la clé secrète du système.
       On sait que cette valeur existe grâce aux propriétés des nombres premiers choisis.

Finalement
. Bob utilise la clé publique et calcule
       m^e (modulo n).
       C 'est-à-dire qu' il élève m à la puissance e et calcule le reste de cette puissance dans la division par n.
       Notons r son résultat. Bob  envoie r à Alice.
       ATTENTION, ce calcul peut être long et délicat, aussi on peut s'aider de l'animation suivante qui fera le travail ;).
. Alice reçoit la valeur r, utilise sa clé secrète et calcule :
       r^d (modulo n).
       C 'est-à-dire qu' elle élève r à la puissance d et calcule le reste de cette puissance dans la division par n.
       Elle obtient ainsi le nombre m envoyé par Bob.

Exemple avec de petits nombres
Alice choisit deux nombres premiers :
p = 11 et q = 19 alors n = pq donne n = 209.
φ(n ) = 10*18 = 180.
Alice choisit par exemple 7 qui est premier avec φ(n) = 180.
La clé publique est (7, 209).
Alice envoie la clé publique (7, 209) à Bob.

Alice calcule maintenant d tel que le reste de 7d, dans la division par φ(n) = 180, soit 1.
Elle trouve 103 (on vérifie que 7 * 103 = 721 a bien pour reste 1 dans la division par 180).
La clé secrète est 103.
Notons que pour trouver cette clé secrète, Alice a eu besoin de φ(n)=(11-1)(19-1) et donc des deux facteurs premiers 11 et 19 qui ne sont connus que d'elle.

Bob choisit le nombre 63.
Il a reçu la clé publique (7, 209) et doit calculer m^e (modulo n) soit 63⁷ (modulo 209).
Il trouve 123 et envoie cette valeur à Alice.

Alice reçoit 123. Elle utilise sa clé secrète d=103 pour calculer 123^d (modulo n) soit 123¹⁰³ (modulo 209).
Elle trouve 63.

Elle a bien retrouvé le nombre choisi par Bob.
Ce calcul a nécessité l'utilisation des deux facteurs p et q choisis par Alice et inconnus de Bob.
Ces facteurs sont indispensables pour trouver la clé secrète.
Et c'est justement la détermination de ces deux facteurs qui pose une réelle difficulté lorsque ces nombres sont très grands.

Les propriétés mathématiques mises en jeu

L 'ensemble des nombres inférieurs à n et premiers avec n (n'ayant aucun diviseur commun avec n) est dénommé
       fonction d'Euler ou indicatrice d'Euler.
       On le note φ(n).

Si n = pq avec p et q deux nombres premiers, alors φ(n)=(p-1)(q-1).

Le petit théorème de Fermat :
       si p est un nombre premier,
       si a est un nombre premier avec p (c' est-à-dire que pgcd (a,p) = 1), alors
       a^p-1 = 1 (modulo p).

Le théorème d 'Euler :
       si pgcd (a,n) = 1, alors
       a^φ(n) = 1 (modulo n).

La démonstration (Pour les plus avertis c'est ICI) repose sur ces propriétés mathématiques des nombres premiers.


Maintenant nous allons pouvoir expérimenter avec l'animation suivante.

Animation : codage et décodage RSA

Dans la vie courante les nombres utilisés pour notre sécurité sont immenses : ils ont plus de 200 chiffres.

Même avec des nombres assez petits on se rend compte que les calculs deviennent vite fastidieux.
Il ne faudra donc pas hésiter à utiliser l 'AIDE proposée dans l'animation pour effectuer le calcul de Bob.

Cette AIDE est proposée volontairement dans une animation extérieure, indépendante de celle-ci.
Ceci afin que chacun soit bien assuré qu'il n'y a aucun trucage et que le programme ne connaît pas a priori le nombre m choisi par le dénommé Bob.

Alice retrouvera le nombre choisi par Bob avec sa clé secrète magique.

CLIQUER

 

Aide : le calcul d'une puissance relativement grande selon un modulo

L'animation ci-dessous effectue le calcul d'une puissance qui peut être assez grande et donne le reste dans la division par n :
elle donne donc le résultat de la puissance modulo n.

Trois nombres m, e et n étant entrés, l'animation effectue pour nous le calcul :
       m^e (modulo n).

 

CLIQUER

 

 

 

Démonstration

Nous noterons m le nombre choisi par Bob, e l'exposant et n le modulo. Le résultat repose sur les choix effectués par Alice pour les valeurs de e et d et enfin de n=pq avec p et q nombres premiers. Alice a choisi les entiers e et d tels que ed = 1 (modulo φ(n)). Nous savons donc qu'il existe un nombre entier k tel que ed = k φ(n) +1. La clé publique est le couple (n,e). La clé secrète est d. Rq : l'expression 45 = 3 (modulo 6)    signifie que 45 a pour reste 3 dans la division par 6. On dit que 45 est congru à 3 modulo 6. Bob a envoyé le nombre  r = me (modulo n)  à Alice. Alice a alors calculé rd = (me)d (modulo n). Nous allons montrer qu'elle retrouve bien la valeur m envoyée par Bob. Nous avons : rd = (me)d (modulo n)     = med (modulo n)     = mk φ(n) +1 (modulo n)     = mk φ(n) m (modulo n) Retenons avec rd = med (modulo n) med = mk φ(n) m (modulo n)       (relation 0). Plusieurs cas se présentent 1°) Premier cas : pgcd (m,n) = 1 D'après le théorème d'Euler si pgcd (m,n) = 1 alors mφ(n) = 1 (modulo n) Ainsi rd = mk φ(n) m (modulo n) rd = (mφ(n))k m (modulo n) rd = 1k m (modulo n) rd = m (modulo n)                 CQFD. 2°) Deuxième cas : pgcd (m,n) différent de 1 Comme n = pq    avec p et q premiers, m est divisible par p seulement OU par q seulement OU par les deux à la fois. -Si m est divisible par p seulement (donc premier avec q) alors m peut s'écrire m =  kp avec k entier. Ainsi kp = 0 (modulo p ) SOIT     m = 0 (modulo p ) ET on a aussi med = (kp)ed (modulo p) med = 0 (modulo p)    De ces deux lignes colorées en bleu, on obtient  med = m (modulo p ) On peut donc dire qu'il existe un entier A tel que med - m = Ap         (relation 1). Par ailleurs on a avec la relation 0 : med = mk φ(n) m (modulo n)       = mφ(n)k m (modulo n)       = m(q-1)(p-1) km (modulo n)       = m(q-1)k(p-1)m (modulo n) D'après le petit théorème de Fermat, comme m est premier avec q, nous avons :     m(q-1) = 1 (modulo q) d'où med = m(q-1)k(p-1) m = 1k(p-1 m = m (modulo q) on obtient  med = m (modulo q ) On peut donc dire qu'il existe un entier B tel que med - m = Bq       (relation 2). Grâce aux relations 1 et 2, nous pouvons écrire que p et q divisent med - m, donc n     divise med - m        (car n = pq avec p et q premiers) . Cela signifie que med - m = 0 (modulo n)     c'est-à-dire que : med = m (modulo n) et enfin que rd = m (modulo n)                 CQFD. -Si m est divisible par p et par q (premiers et donc premiers entre eux ). alors m = 0 (modulo pq) et med = 0 (modulo pq) c'est-à-dire Comme n=pq, le résultat med = m (modulo n)   est trivial      ET rd = m (modulo n)                    CQFD.

Bibliographie
-Codage et cryptographie Mathématiciens, espions et pirates informatiques
De la collection
Le monde est MATHEMATIQUE

-Wikipedia

 

---