Journal Schnorr aurait-il cassé RSA ?

Posté par  (site Web personnel) . Licence CC By‑SA.
Étiquettes :
28
4
mar.
2021

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  . Évalué à 3 (+2/-0).

    ça permettrait pas de miner plus rapidement les coins ces méthodes ?

    • [^] # Re: Coins

      Posté par  (site Web personnel) . Évalué à 7 (+5/-0).

      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 ;-)

      • [^] # Re: Coins

        Posté par  . Évalué à 2 (+1/-1).

        Je suppose que tu voulais dire "si RSA est cassé", non?

      • [^] # Re: Coins

        Posté par  . Évalué à 3 (+2/-0).

        Merci, pour miner je pensais qu'il fallait trouver les nombres premiers dans un intervalle toujours grandissant …

        • [^] # Re: Coins

          Posté par  (site Web personnel) . Évalué à 7 (+5/-0). Dernière modification le 04/03/21 à 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  . Évalué à 1 (+0/-0).

            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  (site Web personnel) . Évalué à 5 (+3/-0).

              Qu'est-ce que tu appelles relativement dur en théorie ? […] Est-ce que tu veux dire que ces tests sont en pratique trop lents ?

              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  . Évalué à 2 (+0/-0).

                Salut,

                Un bit flip, c'est hardware. Rien à voir avec l'algo, probabiliste ou non.

                • [^] # Re: Coins

                  Posté par  (site Web personnel) . Évalué à 3 (+1/-0).

                  En théorie, totalement d'accord. Mais en pratique, ton algo tournera sur du hardware, non ?

                  • [^] # Re: Coins

                    Posté par  . Évalué à 2 (+0/-0).

                    Salut,

                    Mais en pratique, ton algo tournera sur du hardware, non ?

                    Oui, et c'était le sens de ma remarque : probabiliste ou pas, si tu as un bit-flip… ;)

                • [^] # Re: Coins

                  Posté par  . Évalué à 2 (+0/-0).

                  D'autant qu'on a les RAM ECC pour ça.

              • [^] # Re: Coins

                Posté par  . Évalué à 1 (+0/-0). Dernière modification le 05/03/21 à 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  . Évalué à 4 (+4/-0).

          Sans miner, ça peut éventuellement aider a retrouver la clé privé qui donne accès au wallet.

    • [^] # Re: Coins

      Posté par  (site Web personnel) . Évalué à 10 (+11/-0).

      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  (site Web personnel) . Évalué à 6 (+4/-0).

        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  . Évalué à 6 (+4/-0). Dernière modification le 04/03/21 à 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  (site Web personnel) . Évalué à 6 (+4/-0).

          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  (site Web personnel) . Évalué à 10 (+16/-0).

    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 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  (site Web personnel) . Évalué à 10 (+11/-2).

      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 !

      • [^] # Re: Bof

        Posté par  (site Web personnel) . Évalué à 10 (+13/-1).

        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).

        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  . Évalué à -4 (+7/-13).

          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  . Évalué à 9 (+8/-0).

            La différence c'est que Raoult avait raison

            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  (site Web personnel) . Évalué à 2 (+0/-0).

              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  (site Web personnel) . Évalué à 6 (+4/-0).

            Visiblement le second degré ne passe pas sur certains sujets :)

            • [^] # Re: Bof

              Posté par  . Évalué à 6 (+4/-0). Dernière modification le 05/03/21 à 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  . Évalué à 2 (+2/-2). Dernière modification le 04/03/21 à 10:52.

        Salut,

        Schnorr prétend avoir cassé RSA

        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é ;)

  • # Factoriser

    Posté par  . Évalué à 10 (+31/-0).

    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  (site Web personnel) . Évalué à 4 (+2/-0).

      En effet, factoriser un nombre premier, j’y arrive en fait assez bien ;-)

    • [^] # Re: Factoriser

      Posté par  . Évalué à 8 (+7/-1).

      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  . Évalué à 6 (+4/-0).

        Pourrais-tu développer un peu ?

        • [^] # Re: Factoriser

          Posté par  . Évalué à 10 (+8/-0).

          Non, c’est irréductible.

          • [^] # Re: Factoriser

            Posté par  (site Web personnel) . Évalué à 10 (+9/-0).

            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  . Évalué à 2 (+0/-0).

              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  . Évalué à 3 (+1/-0).

          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.

  • # Relativisons

    Posté par  (site Web personnel) . Évalué à 5 (+3/-0).

    Dans son papier, il précise que la factorisation d'un nombre de l'ordre de 1014 prend de l'ordre de 30s.

    Dans les faits, la taille des nombres pour le RSA est beaucoup plus importante :
    - 512 bits : 155 chiffres décimaux
    - 1024 : 309 chiffres décimaux
    - 2048 : 617 chiffres décimaux

    Même si son algo est une avancée, je pense qu'il y a encore pas mal de marge ! Surtout que jusqu'à présent, et à ma connaissance, aucun algorithme n'est polynomial par rapport à la taille du nombre à factoriser…

    • [^] # Re: Relativisons

      Posté par  . Évalué à 3 (+1/-0). Dernière modification le 04/03/21 à 12:04.

      Salut,

      à ma connaissance, aucun algorithme n'est polynomial

      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.

      • [^] # Re: Relativisons

        Posté par  . Évalué à 9 (+9/-1). Dernière modification le 04/03/21 à 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  (site Web personnel) . Évalué à 2 (+0/-0).

        Dépend si P==NP, en gros. Ce que l'on ne sait toujours pas.

        Ben oui, mais si tu tronques une partie essentielle du message :p

        Surtout que jusqu'à présent, et à ma connaissance, aucun algorithme n'est polynomial

        Je ne dis pas qu'on n'en trouvera pas un un jour (comme tu le dis, pour l'instant, le P=NP est un problème ouvert qui, si ma mémoire est bonne, offre une forte récompense pour sa résolution !), je dis qu'aujourd'hui, on en a pas. Subtile nuance ;)

        • [^] # Re: Relativisons

          Posté par  . Évalué à 2 (+0/-0).

          Salut,

          je dis qu'aujourd'hui, on en a pas.

          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

      • [^] # Re: Relativisons

        Posté par  . Évalué à 6 (+3/-0).

        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  . Évalué à 2 (+0/-0). Dernière modification le 04/03/21 à 15:36.

          Salut,

          C'est encore plus étrange que ça.

          Si je me souviens bien de mes cours, le monde se divise en deux * :

          • Y'a P,
          • Y'a NP,
          • Y'a NP-complexe,
          • Y'a NP-difficile.

          [*] Comment ça, ça fait pas deux ?

        • [^] # Re: Relativisons

          Posté par  (site Web personnel) . Évalué à 2 (+0/-0).

          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  . Évalué à 1 (+0/-0).

            Et même en temps polynomial, ça risque de rester difficile si l'exposant est tout dégeulasse ;)

  • # Code ?

    Posté par  . Évalué à 3 (+2/-0). Dernière modification le 04/03/21 à 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é :-)

Envoyer un commentaire

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.