À partir de maintenant, deux histoires peuvent s'écrire. Soit son message est intercepté et décrypté, soit Bob le reçoit et Alice est sauvée.

Décrypter un message, en théorie

Destinataire indésirable

Ce destinataire, une fois en possession du message, doit créer la clé privée, par le biais de la factorisation de n, puis il décrypte chaque caractère codé (cc) et il obtient le code ASCII de chaque caractère (cn), puis il les transcrit en caractères clairs (ccl) pour obtenir le message clair.
ccd % n = cn
cn -> ccl -> mc
n connu grâce à la clé publique et d doit être calculé après la factorisation de n.

Véritable destinataire

Prenons l'exemple de Bob. Il reçoit le message crypté, il décrypte chaque caractère codé (cc) et il obtient le code ASCII de chaque caractère (cn), puis il les transcrit en caractères clairs (ccl) pour obtenir le message clair.
ccd % n = cn
cn -> ccl -> mc
d et n sont connus grâce à la clé privée de Bob.

Comme vous pouvez le constater, ces 2 cas sont similaires, ce qui les différencie et d'ailleurs ce qui est à l'origine de la fiabilité de RSA, c'est la factorisation de n. On va donc envisager les 2 cas. Alors, on commence par lequel ? :p

Bon, commençons par le cas où le message serait malheureusement intercepté. Admettons que ce soit un gros gobelin méchant, qui en chassant le pigeon a récupéré celui d'Alice. Comme il n'y comprend rien, il va le porter au gobelin cryptologue. :-° Celui-ci trouvera donc à l'intérieur du message les blocs cryptés. Puisque ce n'est pas lui le destinataire, l'approche pour le décryptage sera différente. Le véritable destinataire, le créateur des clés, aurait utilisé la clé privée, mais lui devra créer la clé privée à partir de la clé publique, pour réussir à décrypter le message !
Clé privée : (d, n).
Comme n est déjà présent dans la clé publique, il reste d à trouver.
Nous avions évoqué plus haut comment l'avoir. Je vous redonne la ligne : p,q < d < n, e*d mod n = 1. Misère ! p et q, on ne les connaît pas ! Exact, mais n est le produit de 2 facteurs premiers qui sont p et q, donc la factorisation de n, nous donne p et q. Cette factorisation est longue, voire très très longue selon la taille de n et vous verrez que c'est le but recherché. On regardera ceci de plus près quelques lignes plus bas.
En factorisant n, on retrouve donc p = 503, q = 563.
Je ne vais pas détailler les calculs suivants car nous les avons déjà rencontrés plus haut.

Image utilisateur

n = 282124, e = 565.

Déterminer d

En analysant un peu les conditions pour trouver d, on remarque que le principe est le même que pour e. On délimite tout d'abord une portion de nombre où se trouve d, d plus grand que p et q et d inférieur à n. Puis on teste les nombres compris dans cette zone avec ce calcul e*d mod

Image utilisateur

n = 1.
565 * 564 % 282124 = 566
565 * 565 % 282124 = 37101
...
565 * 140313 % 282124 = 1
565 * 140314 % 282124 = 566
Cette fois-ci, manuellement il aurait fallu passer un bon bout de temps avant de trouver d. Il vaut mieux appliquer cette méthode à un programme qui nous trouvera d. Mais il y a une autre solution bien plus rapide qui se résume à un seul calcul.

d = 1/e %

Image utilisateur

n
d = 1/565 % 282124
d = 140313

Cette dernière méthode est bien plus pratique.
Avec ces 2 méthodes, on peut aisément trouver d, et donc la clé privée.
Clé privée de Bob (trouvée par les méchants gobelins avec la factorisation de n) : (140313, 282124).

Décrypter le message

Citation : Alice

80488 / 2826 / 241808 / 183218 / 45154 / 84918

Le décryptage sera aussi simple que le cryptage, une simple formule, et nous retrouverons nos blocs de départ, puis on les retranscrit en lettres grâce à la table ASCII.

Formule :
ccd % n = cn

80488140313 % 283189 = 72
2826140313 % 283189 = 101
241808140313 % 283189 = 108
183218140313 % 283189 = 112
45154140313 % 283189 = 32
84918140313 % 283189 = 33

ASCII

Caractère

72

H

101

e

108

l

112

p

32

(espace)

33

!

Et voilà, le message est décrypté, même si ce n'était pas le véritable destinataire !
Pourquoi ?
Tout simplement parce que la sureté du RSA repose sur la factorisation de n et notre n était bien trop petit, il a été factorisé rapidement avec un factorisateur banal.

Je vais prendre un nombre semi-premier, c'est-à-dire le produit de 2 nombres premiers, soit n, du challenge RSA qui n'est plus en vigueur, mais il est encore possible d'accéder à ces nombres. C'est le RSA-576, composé de 174 chiffres :

Citation : Challenge RSA

188 198 812 920 607 963 838 697 239 461 650 439 807 163 563 379 417 382 700 763 356 422 988 859 715 234 665 485 319 060 606 504 743 045 317 388 011 303 396 716 199 692 321 205 734 031 879 550 656 996 221 305 168 759 307 650 257 059

La factorisation en image : début et fin.
Vous pouvez remarquer que fin, c'est vite dit ^^ . En fait la factorisation n'a pas abouti et je ne pouvais pas me permettre de faire tourner mon ordinateur pendant des lustres. L'algorithme de factorisation est peut-être basique mais même avec du bon matériel et un bon algorithme, cela prend quand même énormément de temps, c'est pourquoi RSA est sûr !

Le décryptage du côté de Bob, qui lui est le vrai destinataire, soit le créateur des clés privée et publique, est similaire à celui d'un destinataire indésirable, à la différence que Bob ne doit pas passer par la factorisation de n pour trouver p et q puisqu'il les a déjà.
Voilà, la force de RSA !
Il calcule d, comme vu plus haut et il peut ensuite sans problème décrypter le message d'Alice.
Bob crée donc sa clé privée : (140313, 282124).
Rien de nouveau, il va décrypter de la même manière que notre gobelin cryptologue. Une fois décrypté, Bob pourra sauver Alice. ^^ Houraa ! :-°

Pour un programme de décryptage, il y a donc toujours 2 cas à prendre en compte. Soit il faut factoriser n pour trouver la clé privée ou simplement demander la clé privée à l'utilisateur.

Les auteurs