Canalblog
Editer l'article Suivre ce blog Administration + Créer mon blog
Publicité
Choux romanesco, Vache qui rit et intégrales curvilignes
2 juillet 2007

Devenir H4ck3rz, pour les nuls

Internet, ce n'est pas que des casinos maltais ou des vidéos de chutes en skate, c'est aussi le commerce en ligne : transactions de fonds, numéros de cartes bleues et date d'expiration associée, tout ça circule tranquillement sur le réseau. De manière codée, certes, mais avec des clefs de codages bien connues de tous puisqu'elles sont publiques... Aujourd'hui, apprenons ensemble à décoder les chiffrements renfermant le code de la carte bleue de Mr Dupont qui vient de s'acheter un chouette vélo d'appartement.


Remontons à l'origine de la cryptographie, avec le code de César (comme son nom l'indique, inventé par Jules César). Le principe de ce code est tout simple : on décide d'une clé k, et on fait correspondre à chaque lettre du message la lettre de l'alphabet décalée de k lettres. Si k=3, on a A->D, B->E etc.

Prenons cet exemple : "VBVYJPYJPYJP KJPNNZ G'VIVIVN ZO HJPYN G'XVAZ".
Donné ainsi, déchiffrer le code peut nécessiter plusieurs minutes.
Si je précise qu'il s'agit d'un code de César, il n'y aura plus que 25 clés à tester.

Si j'ajoute que la clé est 8, le code sera cassé en quelques secondes.


Le tour de force des cryptages qui ont lieu sur internet, c'est que tout le monde sait que le codage utilisé est le codage RSA (Du nom de leur auteurs, Ron Rivest, Adi Shamir et Len Adleman), et que la paire de clés de codage est (relativement) publique ! (Pour plus de sécurité, le codage RSA est associé à l'OAEP, mais je ne vais pas en parler dans cet article)

-----

En plus, le codage RSA est plutôt simple à mettre en œuvre pour n'importe qui connaissant l'arithmétique (nombres premiers, nombres premiers entre eux, divisions euclidiennes et congruences) ! Voyons comment cela fonctionne :

Tout d'abord, Arnaud, maître en chef de la cryptographie, choisit deux nombres p et q tous les deux premiers. Il calcule ensuite le produit n=pq. n est alors la première clé de cryptage, qu'il mettra à disposition de tout le monde sur internet. Il choisit ensuite un autre nombre e, premier avec (p-1)(q-1), qu'il mettra à disposition de tout le monde sur internet.

Maintenant, Bernard a une terrible envie de passer un message secret à Arnaud, mais il sait que son ennemi juré, Christophe, guette. Ce message secret, c'est M, un entier positif plus petit que n.
Pour le coder, il suffit simplement de calculer le reste de la division euclidienne de Me par n :

RSA1

Et le tour est joué, le message est codé ! Bernard n'a plus qu'à l'envoyer à Arnaud qui pourra le décoder.
Avant tout ça, Arnaud a aussi calculé l'entier d tel que RSA2.

Pour décoder C, il y a juste à calculer Cd modulo n. Le résultat sera alors M.

Le plus difficile pour Christophe (qui ne connait ni p, ni q, ni d), c'est de trouver ce nombre d. Pour cela, il lui faudra factoriser n en p×q, puis trouver d selon la relation ci-dessus.

-----

Petit exemple :
On prend les clés de cryptage suivantes
n = 1653277069
e = 65537

Et mon message caché, c'est :
C = 305880301

Pour décrypter ce message, il faut donc savoir factoriser. Comme ce n'est pas un nombre trop énorme, on peut encore le faire : 1653277069 = 41113  x  40213.
On a donc T=(p-1)(q-1) = 41112  x  40211 = 1653195744
Il faut à présent calculer d (L'inverse de e modulo T). Cet inverse, c'est d=1104341921.
On décode à présent le message.
Cd modulo n = 1615210520

En le décodant, on a 16.15.21.05.20 -> P.O.U.E.T

Et voilà un beau message décodé !

-----

Allez, passons à un petit exercice ! Saurez-vous décoder ce message codé, sachant que pour le coder, j'ai utilisé :

n =
28419181913810437345824250197567708730088202978694
28913715429476242088608345960904066292721435918199
21106779056877531440875230218032640311325038378896
92339352650802850904343984369558897929963233427

e = 65537

Et voici mon message codé :
C =
11702615899972603057258578189422057798020038730314
78892622538509244478308728446193131481112246707511
12640561090848642523271203957773047992148675956812
22080098315061823288413981706052270284295473961

Le premier ou la première qui réussira à le décoder gagnera un magnifique cadeau d'une valeur inestimable !

 

-----

Bref, pour hacker en toute tranquillité, il suffit simplement de savoir factoriser des grands nombres !

(Ai-je omis de préciser que dans l'état actuel des choses, il est impossible de factoriser un nombre à plus de 200 chiffres ?... Quand on sait que les clés de chiffrements des banques sont de l'ordre de 300 chiffres...)

Il faut tout de même se rassurer : ce système garde encore quelques failles, tout n'est pas perdu pour les hackers !


Sources :
La page Wikipedia sur RSA (avec démonstration)
Générer des grands nombres premiers
Calculs sur de grands entiers

Publicité
Publicité
Commentaires
D
"inviolable durant encore quelques années"... pas si sur. Ta clé fait 652 bits, or l'EPFL et l'INRIA viennent de casser une clé de 768 bits (http://www.inria.fr/actualites/espace-presse/cp/pre210.fr.html ) en utilisant l'équivalent de 1500 coeurs*années. <br /> <br /> Je voulais faire un article là dessus en citant http://www.rsa.com/rsalabs/node.asp?id=2094 et http://fr.wikipedia.org/wiki/Algorithme_de_factorisation_par_crible_sur_les_corps_de_nombres_généralisé , mais finalement j'avais rien de plus à en dire alors un commentaire sur ton blog ça va aussi bien ;-)
Répondre
E
Dr Goulu > En fait, c'est le seul moyen que j'ai trouvé pour passer des messages persos à travers ce blog ;). La clé est effectivement une véritable clé, donc inviolable durant encore quelques années !
Répondre
D
Je m'attendais à ce que ton n soit le carré d'un seul gros nombre premier, me suis donc foulé à écrire une racine carrée de long en Python (qui n'en dispose étonnament pas de base) : perdu.<br /> <br /> Ensuite je me suis dit que tu avais peut-être fait un produit de 2 nombres premiers jumeaux, donc j'ai cherché un peu autour de ma racine : re-perdu.<br /> <br /> Quelques essais de divisions par de petits nombre premiers : re-re-perdu<br /> <br /> Donc tu as apparemment fait une vraie clé solide. C'est pas du jeu. Mais quand j'implanterai http://fr.wikipedia.org/wiki/Algorithme_de_factorisation_par_crible_sur_les_corps_de_nombres_g%C3%A9n%C3%A9ralis%C3%A9 sur mon PC, je veux dire mon implant neural dans 20 ans, je trouverai !
Répondre
J
bonjour j aimerai avoir plus d explication quelqun peut m aider?svp
Répondre
P
Beuuuh ... J'ai décodé le code césar, ça compte ou pas ??
Répondre
Publicité
Votez pour moi
Publicité