[quote=“fran.b”]Alors ça a mariné??[/quote]Grumph. Non.
Quand je te disais que vieillir me rendait flemmard.
[quote=“dimm”]fran.b dans quelle section enseignes-tu cela ?[/quote]prépas
Solution:
Si on résume, la pagehttp://boisson.homeip.net:8080/distributeur.php renvoie la valeur x^L modulo N, X étant la valeur entrée. Comme N=PQ, on calcul Y1=x^L modulo P, Y2=x^L modulo Q et on a x^L modulo N qui vaut U.QY1+V.P.Y2 modulo N, U et V sont des valeurs précises ne dépendant que de P et Q donc calculeés à l’avance.
[complément: En fait U est l’inverse de Q modulo P et V est l’inverse de P modulo Q, si on prend Z=U.PY2+V.Q.Y1, on aura Z=Q^(-1).Q.Y1+0=Y1 modulo P, et de même Z=Y2 modulo Q]
Si le calcul est perturbé, cela a une chance quasi nulle d’être durant le calcul de U.QY1+V.PY2 mais plutôt dans le calcul de Y1 ou Y2. Mettons que Y1 soit faux, on aura Y’1 au lieu de Y1 et la valeur affichée sera
U.Q.Y’1+V.PY2.
Si on rentre la valeur 1, le résultat attendu est 1 (1^L=1 quoi qu’il arrive). A un moment donné, une erreur se produit et le résultat affiché est
43145589940583270636975258705502338984633560168576816311742244421480517
R-1 vaut donc Q.Q.(Y’1-Y1). Le pgcd de (R-1) et N=PQ est donc Q soit ici
[quote]Maxima 5.10.0 maxima.sourceforge.net
Using Lisp GNU Common Lisp (GCL) GCL 2.6.7 (aka GCL)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
This is a development version of Maxima. The function bug_report()
provides bug reporting information.
(%i1) gcd(43145589940583270636975258705502338984633560168576816311742244421480517-1,102497041265282840135009095514206682314088930453829440600070244487824073);
(%o1) 88897679776876352614281331768768768691
(%i2) 102497041265282840135009095514206682314088930453829440600070244487824073/88897679776876352614281331768768768691
;
(%o2) 1152977687635261428133337667898003
(%i3) 1152977687635261428133337667898003*88897679776876352614281331768768768691;
(%o3) 102497041265282840135009095514206682314088930453829440600070244487824073
(%i4)
[/quote]
On a donc
[quote]N=102497041265282840135009095514206682314088930453829440600070244487824073
= 1152977687635261428133337667898003 * 88897679776876352614281331768768768691[/quote]
N est factorisé, le code est cassé…
Honte à moi d’avoir abandonné. 
Je suis en train de regarder les failles du RC4 (crackage clef WEP) pour en faire un TP… Je ferais peut être un code avec une faille, je referais dans ce cas un pbm, tu pourras te rattraper…
PS: Cela dit c’est vraiment intéressant à comprendre, les failles du RC4 parce que à froid, ça a l’air quand même bien foutu. En clair, le gars qui a inventé le RC4 n’est pas un gros nul, il n’a pas eu de bol je trouve mais bon…
Je suis stupéfait, j’ai compris le problème posé mais d’instinct j’ouvre une console et je tape gp et qcq 10 de minutes après [quote]? factor(N)
%2 =
[1152977687635261428133337667898003 1]
[88897679776876352614281331768768768691 1]
?[/quote]je vais le refaire pour voir le temps exact que cela prend sur ma machine.
edit: 11 minutes avec gp pour décomposer N.
[quote=“limax”]Je suis stupéfait, j’ai compris le problème posé mais d’instinct j’ouvre une console et je tape gp et qcq 10 de minutes après [quote]? factor(N)
%2 =
[1152977687635261428133337667898003 1]
[88897679776876352614281331768768768691 1]
?[/quote]je vais le refaire pour voir le temps exact que cela prend sur ma machine.
edit: 11 minutes avec gp pour décomposer N.[/quote]
Pas trop étonnant, Pari/gp est très puissant. Tu as également l’outil http://www.alpertron.com.ar/ECM.HTM qui permet de faire ce genre de choses [regardes le temps mis en Java et imagines ce que ça donne en C]. N fait ici 235 bits ce qui permet d’envisager la factorisation brutalement avec des outils performants…