En guise de point final à un TP pour mes élèves (dont le thème était les cryptage RSA et surtout comment calculer modulo une clef N=PQ tenant sur n bits avec P et Q de l’ordre de n/2 bits en utilisant uniquement les opérations sur n bits et cela bien sûr sans programmer d’arithmétique étendue, ils doivent utiliser le lemme chinois en calculant modulo P et modulo Q), je leur ai laissé l’exercice suivant: casser le code décrit dans le lien qui suit (comprendre factoriser N et trouver la clef privée L) en sachant que le distributeur simulé est parasité par microndes et que du coup il fait de temps à autre des erreurs de calcul. Si il y en a que ça amuse, je leur donne les clefs publiques:
Il s’agit de trouver L tel que que Si X est un nombre inférieur à N, on le code en faisant Y=X^K modulo N, le décodage se fait en faisant X=Y^L modulo N.
L’URL http://boisson.homeip.net:8080/distributeur.php simule une authentification RSA: Vous rentrez un nombre codé (soit X^K modulo N) et cela vous sort le nombre décodé, sauf que j’introduis des erreurs au hasard dans le calcul. Voilà, si ça vous amuse d’essayer, ça a été une des premières méthodes trouvées pour craquer des codes des machines type distributeurs de billets. Par contre, il faut connaitre un peu le code RSA donc avoir fait des Maths (arithmétique) et de l’Info et avoir de la jugeotte.
[quote=“le_petit_chat_noir”]Et dire qu’on me prenait pour un extra-terrestre avec mon antenne wifi en boite de Pringles!
(…)[/quote]qu’est ce que tu veux dire ? tu as fait un ampli avec une boite de pringles ? Ca m’interresse.
Ah moi j’ai aussi fait des arbres de fourchettes ou des compositions à base de porte manteaux qui me donnaient une télé nickel. Et trés “style” dans un salon.
Mais sinon, je ne vois pas trop comment tu la branche sur le dispositif wifi dans ton pdf.
Dis moi, ta boite de Springles, les fonds sont en alu ou en carton (je pense alu car la position de l’antenne par rapport à ces fonds est importante), par contre le fond de bouteille de coca est en plastique. Je vais donner ça à un collègue de physique, si tout va bien, tu vas être maudit par plusieurs dizaines d’élèves qui vont devoir plancher sur ton truc . Sinon, je vais me la fabriquer, c’est plus utile que de craquer le RSA
Pour mon pbm, c’est sûr qu’il faut avoir de beaux restes d’arithmétique ou avoir programmé RSA. Si je résume l’énoncé en enlevant le superflu:
Le «distributeur» est une machine qui lorsque vous rentrez un entier x inférieur à N vous sort un entier y valant x^L modulo N. y est remarquable car y^K est égal à x modulo N (). La machine ne fait que des calculs sur 240 bits (la clef en fait 236 bits). Avec un micro ondes connecté à une antenne Springles, vous pertubez quelques (très peu, en gros 1 sur 1000) opérations arithmétiques et parfois, le résultat est faux. Le but est de trouver L qui est la clef secrète. (Pour info, il suffit de factoriser N en PQ avec P et Q premier mais ça, on ne sait pas faire normalement).
(*) en fait on utilise surtout l’inverse: si x vaut y^K, alors on a y=x^L, la clef secrète L,N permet de décrypter le message x qui est y codé à l’aide de la clef publique (K,N) (soit x=y^K)
Tu as inversé le rôle de N et K entre les deux versions de l’enoncé, non ?
Parceque dans un cas, tu decris l’encodage avec:y=x^K % Net dans l’autre, tu disy=x^L % NPar ailleurs, je dois être rouillé, mais dans le premier énoncé, tu écris le décodage:x=y^L % N et dans la deuxiême version:y^K=x % NCa ne me parait pas spécialement équivalent comme expression, si ?
Enfin en bref, je pensais m’amuser ce soir avec ton truc, mais je ne comprends plus rien avec ce deuxiême énoncé
Tu as deux applications: On va dire que A est le possesseur de la clef privé (L) et que la clef publique est (K,N).
B veut envoyer un message privé à A, il lui envoit y=x^K et A le décode en faisant y^L=x
B veut être sur que en face de lui se trouve A, B envoit à A la valeur x, A lui renvoit y=x^L et B vérifie que y^L = x
ou encore
la signature d’un message: A envoit le message m plus la signature (md5sum par exemple) x codée en y=x^L, n’importe qui recevant le message peut vérifier qu’il vient bien de A en vérifiant que y^K=x
C’est pour ça que codage et décodage sont des opérations complètement symétriques.
Bon, j’ai beau savoir ce que c’est qu’un cryptage, je comprends encore moins ce que tu dis: dans ce dernier post tu n’utilises maintenant plus N, et il n’est plus question de reste.
A moins que tu ne parles dans Z/NZ, mais dans ce cas, ça serait sympa de préciser.
Bon, je m’y remet, sur la base de ton premier énoncé, parceque j’ai horreur de ne pas comprendre.
[quote=“mattotop”]Bon, j’ai beau savoir ce que c’est qu’un cryptage, je comprends encore moins ce que tu dis: dans ce dernier post tu n’utilises maintenant plus N, et il n’est plus question de reste.
A moins que tu ne parles dans Z/NZ, mais dans ce cas, ça serait sympa de préciser.
[/quote]
Toutes mes excuses, c’est effectivement le cas, à ma décharge c’est une question d’habitude, tu en as vite marre d’écrire a=b[N] et tu finis par écrire a=b (en identifiant la classe aux représentants), en clair tu te place dans Z/NZ effectivement…
[quote]
Bon, je m’y remet, sur la base de ton premier énoncé, parceque j’ai horreur de ne pas comprendre.[/quote]
Si tu veux, je peux mettre le programme (en Caml ) qui permet de faire du calcul de puissance modulo N avec N à 64 bits (N=PQ avec P et Q de moins de 32 bits) sans programmer d’arithmétique étendue (i.e en ne faisant que des opérations sur 64 bits). Sinon la clef de voute pour ça est le lemme chinois,…
OK. Je marine depuis ce matin, et comme je ne me souvenais plus du lemme chinois, je tournais un peu en rond en partant d’une décomposition PQ et en regardant le résultat de y§ alors quoi que je me sois approché de la solution, il ne me restait plus que de démontrer un truc: le lemme chinois (que j’ai retrouvé sur wikipedia sous le nom de théorême des restes chinois).
Partant du principe que c’est démontré, il me reste encore un peu de comprehension à faire, mais essentiellement, reste à trouver combien de valeurs premières de y j’ai besoin pour le calcul.
Enfin j’me comprends.
Mais ça fatigue quand on est rouillé, et je me demande si je ne vais pas essayer de me faire une tite sieste dessus pour laisser infuser la solution.
j’y connais rien en Math mais j’ai toujours besoin de savoir ca va me prendre la tete pendant des mois grrrrr 
. Sinon, je vais me la fabriquer, c’est plus utile que de craquer le RSA 
ca m’énerve d’ailleurs…