Claus Peter Schnorr, cryptographe bien connu et réputé (notamment pour les signatures Schnorr, système très en avance pour son temps mais qui a été très peu utilisé car breveté, d’où l’intérêt des brevets mais je m’égare…), bref, Claus Peter Schnorr vient de publier un papier au titre aussi imbitable que son abstract :
"Factoring Integers by CVP and SVP Algorithms".
https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf
Bon, pour ce que j’en comprends, cela signifie qu’il a réussi à trouver un algorithme, très complexe, qui permet de réduire le temps nécessaire à la factorisation des grands nombres premiers.
La complexité de la factorisation des nombres premiers étant, je simplifie à l’extrême, la source majeure de sécurité des algorithmes RSA (pour Rivet-Shamir-Adleman), notamment utilisé dans SSL et TLS.
Le cryptographe FredericJacobs a contacté Shnorr par email pour savoir si le papier était bien de lui (une rumeur a circulé que ce serait un papier de 2019 sur lequel un mauvais plaisantin aurait ajouté des fausses infos pour faire croire que RSA était cassé).
La réponse est tombée :
"It is obvious that my paper destroys the RSA cryptosystem."
https://twitter.com/FredericJacobs/status/1367115794363088897
Sur Twitter, les cryptographes se cassent la tête pour tenter de comprendre le papier et de voir si :
1) Le papier est correct
2) Le papier "casse" bien RSA comme le prétend Schnorr
3) Cette méthode pour casser RSA pourrait être mise en pratique
4) Cette mise en pratique pourrait se faire dans un temps "raisonnable"
Si ces 4 points ne sont pas remplis, alors RSA n’est pas vraiment "cassé". Disons qu’il aurait montré certaines limites et devrait progressivement être abandonné. Mais si les 4 points sont remplis, ça va être un fameux branle-bas de combat…
# Coins
Posté par YBoy360 (site web personnel) . Évalué à 3.
ça permettrait pas de miner plus rapidement les coins ces méthodes ?
[^] # Re: Coins
Posté par ploum (site web personnel, Mastodon) . Évalué à 7.
Le minage se base sur SHA256, qui n’est pas lié à RSA à ma connaissance.
Pour casser SHA256, cela signifie pouvoir prédire un hash à partir de l’input sans devoir calculer complètement ce hash (et donc casser l’aspect "chaotique" du hash).
À mes yeux, les deux choses n’ont rien à voir.
Par contre, une chose est certaine : si SHA est "cassé", on a d’autres chats à fouetter que de miner des coins ;-)
Mes livres CC By-SA : https://ploum.net/livres.html
[^] # Re: Coins
Posté par Serge Julien . Évalué à 2.
Je suppose que tu voulais dire "si RSA est cassé", non?
[^] # Re: Coins
Posté par YBoy360 (site web personnel) . Évalué à 3.
Merci, pour miner je pensais qu'il fallait trouver les nombres premiers dans un intervalle toujours grandissant …
[^] # Re: Coins
Posté par Matthieu Moy (site web personnel) . Évalué à 7. Dernière modification le 04 mars 2021 à 11:35.
Trouver des nombres premiers et factoriser des nombres en facteurs premiers, ce sont deux problèmes très différents. Trouver des grands nombres premiers, c'est relativement dur en théorie mais assez facile en pratique grâce aux tests de primalité probabilités (qui permettent d'assurer avec probabilité arbitrairement proche de 1 qu'un nombre est premier), et c'est ce qu'on fait quand on génère des clés RSA par exemple. Factoriser un nombre (trouver x et y étant donné x*y), c'est beaucoup plus dur.
[^] # Re: Coins
Posté par danarmk . Évalué à 1.
Qu'est-ce que tu appelles relativement dur en théorie ? Je dois avouer que je ne sais pas comment on recherche des nombre premiers grand, mais il me semble que le test de primalité n'est pas un obstacle "théorique", dans le sens où il existe des tests de probabilité déterministes en temps polynomial, le plus connu étant le test AKS. Donc, même si on refusait les tests de primalité probabilistes, on pourrait le remplacer par un test déterministe. Est-ce que tu veux dire que ces tests sont en pratique trop lents ? (C'est le cas si j'en crois ce post stackexchange, mais il y est aussi fait mention d'algorithmes rapides sur des nombres de taille raisonnables bien que non polynomiaux.)
[^] # Re: Coins
Posté par Matthieu Moy (site web personnel) . Évalué à 5.
Oui.
Le papier « Primes are in P » est un résultat théorique majeur, mais qui à ma connaissance n'a pas vraiment changé la pratique (disclaimer : je ne suis pas spécialiste).
Dans la pratique, tout algo est probabiliste, parce que la probabilité de bit flip arbitraire dans un ordinateur n'est jamais nulle. Un algo probabiliste avec probabilité d'erreur 10-1000, c'est aussi fiable qu'un algo déterministe en pratique. Et si on veut faire de la crypto derrière, la fiabilité de la crypto est aussi probabiliste (un attaquant a une proba non-nulle de deviner la clé secrète du premier coup, mais la proba est assez faible pour qu'on prenne ce risque sans problème). Le fait qu'un algo soit probabiliste n'est pas un problème en pratique tant qu'on peut rendre la proba d'erreur arbitrairement petite. Le fait qu'un algo comme AKS soit en O(nb-bits6 ) en temps, ça par contre c'est un problème, presque autant qu'un algo exponentiel.
[^] # Re: Coins
Posté par _kaos_ . Évalué à 2.
Salut,
Un bit flip, c'est hardware. Rien à voir avec l'algo, probabiliste ou non.
Matricule 23415
[^] # Re: Coins
Posté par Matthieu Moy (site web personnel) . Évalué à 3.
En théorie, totalement d'accord. Mais en pratique, ton algo tournera sur du hardware, non ?
[^] # Re: Coins
Posté par _kaos_ . Évalué à 2.
Salut,
Oui, et c'était le sens de ma remarque : probabiliste ou pas, si tu as un bit-flip… ;)
Matricule 23415
[^] # Re: Coins
Posté par Anthony Jaguenaud . Évalué à 2.
D'autant qu'on a les RAM ECC pour ça.
[^] # Re: Coins
Posté par danarmk . Évalué à 1. Dernière modification le 05 mars 2021 à 22:28.
D'accord, je comprend mieux ; c'était ton "théorique" qui m'avait mis le doute. Et je suis bien d'accord que refuser d'utiliser des tests probabilistes n'a que peu de sens en pratique ; c'était juste un hypothèse de travail, puisqu'on parlait de chose "théoriques" :) .
Puisque tu es là, quid des tests de primalités non polynomiaux mais plus rapides sur les nombres qu'on rencontre dans la vraie vie, tels que mentionnés dans le post cs.stackexchange que j'ai cité avant ? Est-ce que remplacer les tests de primalité probabilistes par un de ces tests est également inenvisageable ?
[^] # Re: Coins
Posté par Matthieu Moy (site web personnel) . Évalué à 2.
Alors là, désolé, on sort de mon domaine de compétences !
[^] # Re: Coins
Posté par bnurb . Évalué à 4.
Sans miner, ça peut éventuellement aider a retrouver la clé privé qui donne accès au wallet.
[^] # Re: Coins
Posté par corentin38 (site web personnel) . Évalué à 10.
Pas pour Bitcoin, je dirais. La preuve de travail est basée sur SHA256 (ça a peut être changé ?) qui nécessite de faire des xor le plus rapidement possible, pas de factoriser.
En revanche, les adresses bitcoins sont littéralement des clefs publiques RSA, si je me souviens bien … Si c'est bien le cas, n'importe qui pourrait bien dépenser les bitcoins de n'importe qui d'autre.
[^] # Re: Coins
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à 6.
L'avantage, c'est que globalement les gens mal intentionnés regarderont peut-être d'abord de ce côté là avant de s'intéresser à nos malheureuses clefs d'accès ssh.
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Coins
Posté par Moonz . Évalué à 6. Dernière modification le 04 mars 2021 à 14:50.
Non, Bitcoin c’est ECDSA. Ça fait des années que RSA se fait doucement sortir dans le monde de la cryptographie au profit des courbes elliptiques (ECDSA / *25519)
[^] # Re: Coins
Posté par Philippe F (site web personnel) . Évalué à 6.
Je confirme plus ou moins. Je travaille dans la carte à puce et il est vrai que les produits qu'on livre disposent de la dernière crypto top-moumouthe. Exit le RSA et le DES, vive les ECC et AES. Sauf que … les infrastructures ne suivent pas toujours. Les clients institutionnels sont en général très long à envisager de mettre à jour tous leurs systèmes donc dans les faits, il arrive souvent que de le crypto moins récente que ce qu'on voudrait tous soit utilisée…
# Bof
Posté par gouttegd . Évalué à 10.
Disclaimer : Au cas où quelqu’un en douterait, je ne suis absolument pas qualifié pour évaluer la qualité d’un papier de crypto.
Par contre, on peut quand même relever facilement quelques détails qui incitent à une dose saine de scepticisme.
Comme le fait que le mot « RSA » apparaît en tout et pour tout une seule fois dans tout le papier : c’est la dernière phrase de l’abstract, “This destroys the RSA cryptosystem”. Le texte complet qui suit n’évoque plus jamais RSA. La moindre des choses quand on inclut une prétention pareille dans un abstract, c’est de la soutenir un minimum dans le corps de l’article.
Ou le fait que ça fait des années que Schnorr prétend pouvoir factoriser des entiers en temps polynomial (1991, 2009), sans qu’il n’ait jamais démontré pouvoir réellement le faire.
Pour ce que j’ai vu jusqu’à présent les cryptologues qui se sont penchés sur cette nouvelle édition ne sont pas plus impressionnés que par les éditions précédentes (ici ou là par exemple).
Si je devais générer une paire de clefs cryptographiques aujourd’hui, je n’utiliserais peut-être pas RSA (incidemment la bêta de GnuPG 2.3 est sorti la semaine dernière, elle génère des clefs ECC par défaut), mais si vous avez déjà des clefs RSA en cours d’usage, pas la peine de vous précipiter pour les jeter…
[^] # Re: Bof
Posté par ploum (site web personnel, Mastodon) . Évalué à 10.
Y’a une loi médiatique qui dit que "Tout article dont le titre finit par un point d’interrogation peut se résumer à "non" ".
Je pense que cela s’applique à mon journal. ;-)
D’ailleurs, je pense que mon journal est assez clair sur le fait que je n’annonce pas que RSA a été cassé (ce qui mériterait une dépêche urgente) mais plutôt qu’il y’a un twitter-drama car Schnorr prétend avoir cassé RSA (ce qui mérite amplement un journal, c’est même à cela que ça sert).
Bref, préparez le popcorn !
Mes livres CC By-SA : https://ploum.net/livres.html
[^] # Re: Bof
Posté par gouttegd . Évalué à 10.
S’il faut faire un journal chaque fois qu’un gus prétend quelque chose sur Twitter, il va falloir donner un peu d’argent à DLFP pour augmenter la capacité de stockage derrière le site…
(Et non, le fait que le gus en question soit un nom respectable dans le domaine ne change rien. Il y a déjà assez de la virologie où on accorde beaucoup trop d’importance aux délires de « sommités » comme Montagnier ou Raoult, j’ai pas envie qu’on en fasse de même avec la cryptographie.)
[^] # Re: Bof
Posté par tisaac (Mastodon) . Évalué à -4.
La différence c'est que Raoult avait raison et qu'ici il est évident que Schnorr a tort. Faut pas tout confondre!
Surtout, ne pas tout prendre au sérieux !
[^] # Re: Bof
Posté par George_abitbol . Évalué à 9.
Sur le fait que ce n'était qu'une grippette, sur le fait qu'une deuxième vague était de l'ordre de la science fiction ou sur le fait que c'était impossible de trouver un vaccin ?
[^] # Re: Bof
Posté par Anonyme . Évalué à 2.
Ou sur le fait que la propagation du virus est dû aux fumeurs de cette nouvelle technologie qu’est la chicha ?
[^] # Re: Bof
Posté par Colin Pitrat (site web personnel) . Évalué à 6.
Visiblement le second degré ne passe pas sur certains sujets :)
[^] # Re: Bof
Posté par Faya . Évalué à 6. Dernière modification le 05 mars 2021 à 18:20.
Quand le sujet en question a déclenché des commentaires au premier degré sur les nanoparticules du vaccin activées par la 5G, il est effectivement quasi-impossible de savoir si c'est de l'humour ou pas.
Mais en fait ça marche pour tous les sujets Loi_de_Poe
[^] # Re: Bof
Posté par _kaos_ . Évalué à 2. Dernière modification le 04 mars 2021 à 10:52.
Salut,
En fait, le problème n'est pas uniquement de "casser", mais de pouvoir reconstruire en mieux, aussi.
Et ça, ce n'est pas abordé ;)
Matricule 23415
[^] # Re: Bof
Posté par Anonyme . Évalué à 4.
On a déjà « mieux » que RSA avec ECDSA et EdDSA.
[^] # Re: Bof
Posté par _kaos_ . Évalué à 2.
Salut,
J'ai mangé des mots.
Matricule 23415
[^] # Re: Bof
Posté par Matthieu Moy (site web personnel) . Évalué à 3.
Et beaucoup de recherches en cours sur la « crypto post-quantique ».
# Factoriser
Posté par mickabouille . Évalué à 10.
Factoriser les entiers en produits de nombres premiers, pas factoriser les nombres premiers.
Factoriser les nombres premiers, je te fais ça de tête 😄
[^] # Re: Factoriser
Posté par ploum (site web personnel, Mastodon) . Évalué à 4.
En effet, factoriser un nombre premier, j’y arrive en fait assez bien ;-)
Mes livres CC By-SA : https://ploum.net/livres.html
[^] # Re: Factoriser
Posté par Glandos . Évalué à 8.
Tu es le premier à avoir fait la remarque, malgré le grand nombre de lecteurs. Je me demande si c'est un facteur aggravant.
[^] # Re: Factoriser
Posté par El Titi . Évalué à 6.
Pourrais-tu développer un peu ?
[^] # Re: Factoriser
Posté par Thomas Douillard . Évalué à 10.
Non, c’est irréductible.
[^] # Re: Factoriser
Posté par Benoît Sibaud (site web personnel) . Évalué à 10.
Il faut s'attendre à des blagues en nombre, et si vous êtes les premiers, il y en aura-t-il ensuite de moins en moins souvent ? J'en fait l'hypothèse, de rien man.
[^] # Re: Factoriser
Posté par Thomas Douillard . Évalué à 2.
De plus en plus rare, peut-être, mais pour aller au bout, on peut conjecturer qu’on ira pas. Au bout. Des blagues pour toujours !
[^] # Re: Factoriser
Posté par Glandos . Évalué à 3.
C'est un produit dérivé de cette série de journaux. Il faut simplement intégrer le produit de ces développements comme le vecteur d'informations à la racine de la pensée LinuxFR. C'est une pensée complexe, mais très réelle, et pas imaginaire.
# Commentaire supprimé
Posté par Anonyme . Évalué à 5.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: Relativisons
Posté par _kaos_ . Évalué à 3. Dernière modification le 04 mars 2021 à 12:04.
Salut,
Dépend si
P==NP, en gros. Ce que l'on ne sait toujours pas.Et même si on a un jour la réponse, ça ne veut pas non plus dire que tous les algos deviendront magiquement
P.Matricule 23415
[^] # Re: Relativisons
Posté par Tit . Évalué à 9. Dernière modification le 04 mars 2021 à 12:25.
HS dans le HS : pourquoi P==NP et pas simplement P=NP ?
bon je pense connaître la réponse, à cause du fait que dans de nombreux langages de programmation on fasse une comparaison avec == et pas =… mais qu'est-ce que c'est moche, s'il vous plaît, gardons ça pour la programmation. (je regrette pascal, = pour comparer, := pour affecter c'est quand même bien mieux… quelle idée pourri d'utiliser = pour <-, pourquoi a-t-elle été tant suivie ?)
[^] # Re: Relativisons
Posté par _kaos_ . Évalué à 2. Dernière modification le 04 mars 2021 à 12:35.
Salut,
Aucune raison, rien à déclarer :)
Ah si peut-être un, mais c'est ridicule : l'alignement.
ou
;)
Edit : oui, je sais, on peut barrer le
=…Matricule 23415
[^] # Re: Relativisons
Posté par Thomas Douillard . Évalué à 2.
P<>NP
[^] # Re: Relativisons
Posté par Joseph Maârek . Évalué à 2.
En SQL l'opérateur <> est équivalent à l'opérateur !=
[^] # Re: Relativisons
Posté par Anonyme . Évalué à 6.
P ≠ NP
[^] # Commentaire supprimé
Posté par Anonyme . Évalué à 2.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: Relativisons
Posté par _kaos_ . Évalué à 2.
Salut,
Bin donc on est d'accord alors :)
Une preuve c'est bien, une implémentation, c'est peut-être pas la même histoire :p
Matricule 23415
[^] # Re: Relativisons
Posté par rewind (Mastodon) . Évalué à 6.
C'est plus compliqué que ça. D'après Wikipedia, il est suspecté d'être strictement entre P et NP-complet. Et en vrai, on ne sait pas bien où il est.
[^] # Re: Relativisons
Posté par _kaos_ . Évalué à 2. Dernière modification le 04 mars 2021 à 15:36.
Salut,
C'est encore plus étrange que ça.
Si je me souviens bien de mes cours, le monde se divise en deux * :
P,NP,NP-complexe,NP-difficile.[*] Comment ça, ça fait pas deux ?
Matricule 23415
[^] # Re: Relativisons
Posté par Matthieu Moy (site web personnel) . Évalué à 2.
Si P = NP, c'est quand même gagné pour la factorisation en temps polynomial.
Si P != NP, effectivement, ça ne dit pas si la factorisation est polynomiale ou non.
[^] # Re: Relativisons
Posté par baron . Évalué à 1.
Et même en temps polynomial, ça risque de rester difficile si l'exposant est tout dégeulasse ;)
# Code ?
Posté par marzoul . Évalué à 3. Dernière modification le 04 mars 2021 à 23:31.
Vu la criticité du sujet, analyser et valider la dizaine de pages du papier devrait être du gâteau pour des mathématiciens standards ou aguerris. Chose qui ne manque pas sur la planète ! (mais je n'en fais pas partie, hein)
Si c'était vrai, qu'on sache factoriser les grands nombres en temps et mémoire raisonnable, alors ça aurait fait (ou dû faire ?) un foin monstre en peu de temps après sa publication.
Ou alors le papier est un sérieux candidat pour remporter un concours d'offuscation de papier, et aucun des lecteurs candidats à en comprendre la teneur n'a osé dire qu'il ne comprenait rien ;-)
Mais admettons que c'est de la bonne théorie et que personne de pertinent n'est tombé dessus.
Même là, c'est quand même difficile à gober que l'auteur n'aurait pas tenté la pratique et implémenté le tout pour confirmer…
Papier compréhensible ou pas, un exemple d'implémentation fonctionnel est encore la meilleure preuve de validité :-)
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.