Seriez vous un bon craqueur de code?

Pause Café
#1

[pour ceux qui aiment réfléchir et chercher]

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:

N=102497041265282840135009095514206682314088930453829440600070244487824073 K=47052005212438945143730197090143538749422252919584550169060354884042809

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.

#2

T pas sortable toi :laughing: j’y connais rien en Math mais j’ai toujours besoin de savoir ca va me prendre la tete pendant des mois grrrrr :imp: :imp:

#3

bah, je cherche pas, j’ai même pas compris l’ennoncé :unamused:

#4

J’ai beau être fan de Galois, je n’ai jamais fait de crypto.
Je regarderais ça ce midi, mais je n’ai pas non plus fini de comprendre l’énoncé…

#5

Et dire qu’on me prenait pour un extra-terrestre avec mon antenne wifi en boite de Pringles! :laughing:

la je suis tout simplement bleuffé

#6

[quote=“le_petit_chat_noir”]Et dire qu’on me prenait pour un extra-terrestre avec mon antenne wifi en boite de Pringles! :laughing:
(…)[/quote]qu’est ce que tu veux dire ? tu as fait un ampli avec une boite de pringles ? Ca m’interresse.

#7

http://www.myotis.ch/exoops/modules/mydownloads/cache/files/pringles.pdf

c’est en fait une antenne directionnelle qui de permet de gagner 10dBi :laughing:

sans déconner c’est pas énorme ca avec une boite de chips? (pssst, la mienne est une crème ognions)

#8

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.

#9

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 :slightly_smiling: . Sinon, je vais me la fabriquer, c’est plus utile que de craquer le RSA :slightly_smiling:

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)

#10

bon avant de poluer le sujet, j’en crée un autre :

http://forum.debian-fr.org/viewtopic.php?t=5571

ps: le fond d’une boite pringles est en aluminium, et oui la distance qui sépare le radiateur du fond de la boite est très important.

#11

non!
ça fait peur, les maths et dieu :smiley:

#12

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é :cry:

#13

Si c’est la même chose, en fait tu as

(x^K)^L = x^(KL) = (x^L)^K = x

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.

#14

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.

#15

[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 :slightly_smiling: ) 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,…

#16

J’ai mis le pgm Caml sur http://boisson.homeip.net/RSA64.ml

#17

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 :laughing: (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.

#18

Alors ça a mariné??

#19

Malheureusement c’est pas de mon niveau trop complexe pour moi ça :wink: ca m’énerve d’ailleurs…

#20

fran.b dans quelle section enseignes-tu cela ?