RSA cassé ???
Il ont juste a augmenter la taille des 2 nombres premieres et c’est plus cassé non ?
Il joue juste sur le fait qu’on sait pas factoriser des grands nombres premiers mais forcement si la puissance des proc augmente…
Faut augmenter le taille des chiffres…
Euh, on a jamais dit que RSA était cassé … si ?
J’ai peut etre mal compris le message d’urdle … mais c’est pas bien grave
Si ca peux te rassurer, non, RSA est loin d’être cassé. Ca reste un algo simple par le principe. Donc les failles potentielles sont peu nombreuses. Et comme tu le rappelle, les éléments mathématiques sur lesquels il se base (factorisation en deux grands premiers / logarithme discret) sont loin d’être résolus.
Nan, pas de crack réel trouvé, il me semble juste avoir lu qu’on avait des indices de failles potentielles mais qui sont aujourd’hui inexploitables. J’entend par cela que des personnes auraient trouvé quelques cas particuliers où tel ou tel particularité apparait.
J’ai pas d’exemple en tête pour RSA, mais il me semble que pour SHA-256 par exemple, ils ont trouvé un cas particulier (en changeant une partie de l’algo) où un palindrome chiffré donne un palindrome. C’est clair, aujourd’hui on peut rien en faire, mais ce sont des pistes pour les cryptanalystes qui arriveront peut-être un jour à le casser grâce à une astuce (je ne parle pas de force brute)
Ah si, wikipedia m’a donné ce que j’avais lu sur RSA. Mais attention, là on tape dans le très haut niveau. Du timing attack, en gros on peut deviner la clé (ou au moins réduire le nombre de possibilités) si on connait le matos en face très précisement, qu’on lui balance des trucs à déchiffrer et qu’on regarde le temps qu’il met en fonction de la trame.
C’est une méthode très indirecte et une parade a très vite été trouvée (mettre une tempo aléatoire 
)
Evidemment, on est très loin d’avoir cracké quoi que ce soit pour le coup (parceque ça serait oublier la variation du lag qui existe même dans un réseau d’entreprise, alors y’a peut-être des applications, mais limitées)
[quote=« urdle, post:25, topic: 27622 »]Ah si, wikipedia m’a donné ce que j’avais lu sur RSA. Mais attention, là on tape dans le très haut niveau. Du timing attack, en gros on peut deviner la clé (ou au moins réduire le nombre de possibilités) si on connait le matos en face très précisement, qu’on lui balance des trucs à déchiffrer et qu’on regarde le temps qu’il met en fonction de la trame.
C’est une méthode très indirecte et une parade a très vite été trouvée (mettre une tempo aléatoire 
)
Evidemment, on est très loin d’avoir cracké quoi que ce soit pour le coup (parceque ça serait oublier la variation du lag qui existe même dans un réseau d’entreprise, alors y’a peut-être des applications, mais limitées)[/quote]
Ouais, en attaquant le matos, y’a plein de possibilités. Mais la, c’est pas vraiment du cassage de RSA, c’est plus de l’espionage. C’est des choses qui étaient assez facile a faire sur les cartes à puces. Ca deviens de moins en moins évident.
Pour le long terme tu aurais plutôt intérêt à utiliser des courbes elliptiques.
Peter RSA ca revient a resoudre P = NP …
On y est vraiment pas encore …
[quote=« avavrin, post:28, topic: 27622 »]Peter RSA ca revient a resoudre P = NP …
On y est vraiment pas encore …[/quote]
N = a, avec a étant l’élément neutre de la multiplication dans le groupe considéré.
Ca y est, j’ai cassé RSA ?
ahah … non
P = ensemble des problemes qui se resolvent avec des algos polynomiaux
NP = ensemble des problemes qui se resolvent avec des algos non-polynomiaux
[quote=“avavrin, post:30, topic: 27622”]ahah … non
P = ensemble des problemes qui se resolvent avec des algos polynomiaux
NP = ensemble des problemes qui se resolvent avec des algos non-polynomiaux[/quote]
Oula alors attention mon coco, il a simplement été conjecturé que casser RSA était polynomialement équivalent à factoriser n, mais c’est totalement ouvert ! Donc dire que casser RSA revient à prouver que P = NP c’est totalement faux !
(Je pensais que tu faisais allusion à n = pq).
Moloch > j’ai cru que factoriser un nombre c’etait un probleme NP, mais ptet que je me trompe
ton coco
[quote=“avavrin, post:32, topic: 27622”]Moloch > j’ai cru que factoriser un nombre c’etait un probleme NP, mais ptet que je me trompe
ton coco[/quote]
Le débat reste ouvert, d’autre part il n’est pas non plus prouvé que casser RSA se réduise à factoriser n.
Déjà, en espace, c’est pas n (je pense)
Non non c’est bien un problème NP, mais on sait pas s’il est NP-complet ou non, c’est-à-dire que même si on montre un jour que la factorisation est dans P, on n’en déduit pas que P=NP.
Pffff
On ne connait pas exactement quelles classes de complexité contiennent le problème de la décomposition en produit de facteurs premiers. Le problème de décision de forme (« N a t’il moins de facteurs que M ? ») est connu pour être à la fois NP et co-NP. Ceci parceque les réponses OUI et NON peuvent être cochées si les facteurs premiers sont donnés avec leurs preuves de primalité. Il est connu comme étant dans BQP à cause de l’algorithme de Shor. Il est suspecté d’être en dehors de toutes les trois classes de complexité P, NP-complet, et co-NP-complet. S’il peut être démontré qu’il est soit NP-Complet ou co-NP-Complet, cela impliquerait NP = co-NP. Ce serait un résultat très surprenant, par conséquent la factorisation entière est largement suspectée d’être en dehors de ces classes. Beaucoup de monde ont essayé de trouver des algorithmes en temps polynômial pour cela et ont échoué, par conséquent, elle est largement suspectée d’être en dehors de P.[/b]
Bon désolé Wikipédia c’est tout ce que j’ai trouvé en cinq minutes, je sais c’est à chier, mais documente toi un peu et tu verras que tu ne peux pas être aussi affirmatif (le futur peut néanmoins te donner raison et quelqu’un pourrait prouver que factoriser est de classe NP).
Comme l’a prouvée la timing-attack, ce n’est peut-être pas frontalement que RSA serait cassé.
Maintenant il est dit aussi, il me semble, qu’avec un ordinateur quantique spécialisé sur x bits, le cassage de la partie privée à partir de la clé publique serait instantané.
Bon là, les ordis quantique on y est pas encore sur 512 bits…
Je peux me tromper, mais il me semble fortement qu’il est prouve que la factorization est dans NP, puisque si on dispose des facteurs on peut verifier le resultat en temps polynomial. Ceci dit j’ai pas le temps de chercher une bonne reference la tout de suite, desole.
M’enfin bon, ca n’enleve rien au fait qu’on ne sait toujours pas si c’est NP-complet ou non.
Edit: apres verification, la factorization est bien dans NP (et je crois que ces gars-la connaissent leur affaire, enfin j’espere pour eux ).
Ouais, surtout.
Pasque ca peux aussi être cassé si un mec invente le logarithme discret.