[MàJ] Une intelligence artificielle a cassé le chiffrement RSA sur 2048 bits

[MàJ] Une intelligence artificielle a cassé le chiffrement RSA sur 2048 bits

Et là, c'est le drame...

Avatar de l'auteur
Sébastien Gavois

Publié dans

Internet

01/04/2016 6 minutes
83

[MàJ] Une intelligence artificielle a cassé le chiffrement RSA sur 2048 bits

Inattendu, c'est le mot : le système de chiffrement RSA peut être décrypté en quelques dizaines de minutes selon une équipe de scientifiques. Une intelligence artificielle a en effet réussi ce tour de force, mais uniquement sur des clés de 2048 bits au maximum pour le moment.

Alors que scientifiques et mathématiciens pensaient que cela prendrait encore de nombreuses décennies avant qu'une machine ne parvienne à casser dans un délai raisonnable le chiffrement RSA sur 2048 bits, c'est finalement déjà arrivé. Il s'agit d'une annonce importante puisque le RSA est largement utilisé pour chiffrer des données et des communications, notamment sur internet. À qui doit-on cette découverte ? Une intelligence artificielle.

Factoriser un nombre, si simple en apparence et finalement si compliqué

Comme nous l'avions expliqué dans cet article, le principe de base du chiffrement RSA repose sur un jeu de clés. Pour faire simple, p et q sont des nombres premiers et permettent à un utilisateur de générer des clés privées (basées sur p et q) et publiques (basées sur leur produit pxq).

Sans entrer dans les détails, sachez que ce système de chiffrement est robuste et qu'il repose sur un principe : en partant du produit pxq, retrouver les nombres premiers p et q (et donc la clé privée) prend un temps extrêmement long lorsque les nombres sont grands (on parle ici de plusieurs centaines de chiffres). L'exercice qui parait simple en apparence, ne l'est pas tant que cela car il n'existe pas de formule « magique » pour trouver la solution.

La manière la plus aisée, mais pas la plus efficace, est de tester toutes les combinaisons de nombres premiers : peut-on le diviser par 2, 3, par 5, par 7, par 11, 13, 17, 19, etc. Il faut tester toutes les possibilités pour trouver la bonne. Il existe des méthodes permettant d'aller plus vite, comme le crible algébrique, mais rien qui permette de réduire drastiquement le temps nécessaire.

Une compétition est ouverte depuis plusieurs années et l'actuel record de factorisation concerne RSA-768 (il est composé de pas moins de 232 chiffres). Il a été résolu en décembre 2009. RSA-1024 mesure 309 chiffres de long et une récompense de 100 000 euros attend celui qui le factorisera. Avec RSA-2048 on passe à respectivement 617 chiffres et 200 000 dollars.

Quoi qu'il en soit, afin de s'assurer d'un minimum de sécurité, l'ANSSI recommande d'utiliser des clés de 2048 bits minimum, voire 4096 bits. Normalement cela devrait vous laisser plusieurs années de répits.

Une intelligence artificielle à double entrée résout ce casse-tête

Avec l'attrait des récompenses et des retombées médiatiques qui en découlent, de nombreuses équipes s'attèlent à factoriser des nombres de plus en plus grands depuis plusieurs années. Pour y arriver, des mathématiciens se sont associés à des informaticiens afin d'éduquer, via l'apprentissage profond (deep learning), un réseau de neurones. Son objectif ? La fameuse factorisation.

Pour cela, la machine calcule d'un côté le produit de deux grands nombres premiers, tandis qu'elle essaye de le factoriser de l'autre. Bien évidemment, les deux instances ne communiquent pas entre elles, sinon cela n'a aucun intérêt. La machine tourne ainsi en boucle fermée, s'améliorant un peu plus chaque jour. Une manière de faire qui est exactement la même que celle utilisée par DeepMind pour AlphaGo, l'intelligence artificielle qui a battu le champion Lee Sedol.

Et sans trop que l'on s'y attende, cette intelligence artificielle s'est mise à factoriser des nombres extrêmement grands de plus en plus rapidement. De plusieurs semaines, la machine est passée à plusieurs jours, puis heures et enfin dizaines de minutes, et ce, avec des nombres toujours plus grands. Cela s'est fait progressivement, au fil de l'apprentissage. La situation semble désormais stabilisée.

Dans tous les cas, cela ne fonctionne que sur des nombres de 2048 bits au maximum expliquent les chercheurs qui cherchent encore à expliquer le phénomène. Ils n'ont pas encore détaillé la manière de fonctionner de l'IA et les algorithmes qu'elle a mis au point, mais sont en train d'étudier cela de près et devraient publier leurs conclusions d'ici quelques mois.

Pour rappel, ce n'est pas la première fois que le chiffrement des données est mis à mal. En août 2014, une équipe de l'INRIA expliquait qu'elle avait développé un algorithme qui « secoue la cryptographie » car il permet de casser des systèmes de chiffrement basés sur le logarithme discret. Un problème présenté comme « aussi dur que la factorisation (RSA) » par le laboratoire de recherche.

Que faire ? 

Quoi qu'il en soit, l'équipe à l'origine de cette découverte a décidé de l'annoncer dès maintenant afin de permettre à la communauté de rapidement mettre à jour ses systèmes de chiffrement. Ils ont par contre fait part de leur intention de ne pas dévoiler le reste des détails tout de suite, car cela aurait des conséquences bien trop fâcheuses.

On se retrouve un peu dans la même situation qu'avec des failles majeures qui se multiplient ces derniers temps : on prévient dans un premier temps, puis on donne les détails une fois qu'une majorité des personnes touchées a pu se mettre à jour. Si un chiffrement RSA sur 2048 bits n'est donc plus vraiment sécurisé, en passant à 4096 bits l'intelligence artificielle se casse les dents... « pour le moment » glisse un des chercheurs, un brin provocateur.

On peut donc changer ses clés pour les passer en 4096 bits, mais avec le risque de devoir recommencer plus tard, le jeu n'en vaut donc pas forcément la chandelle. Que faire alors ? Pour le moment par grand-chose malheureusement, si ce n'est attendre de plus amples informations de la part des spécialistes et de nouvelles recommandations de l'ANSSI par exemple.

Il semblerait que l'équipe de chercheurs soit pour le moment la seule à avoir découvert cette technique. Néanmoins, des groupes moins bien intentionnés pourraient également être arrivés au même résultat, et ne pas prévenir la communauté pour en profiter au maximum. Des yeux commencent d'ores et déjà à se pointer vers les agences de renseignement...

83

Écrit par Sébastien Gavois

Tiens, en parlant de ça :

Sommaire de l'article

Introduction

Factoriser un nombre, si simple en apparence et finalement si compliqué

Une intelligence artificielle à double entrée résout ce casse-tête

Que faire ? 

Le brief de ce matin n'est pas encore là

Partez acheter vos croissants
Et faites chauffer votre bouilloire,
Le brief arrive dans un instant,
Tout frais du matin, gardez espoir.

Commentaires (83)


M’en fous, je chiffre en 4096.<img data-src=" />



Il est ou le lien ? Hein ? Petits coquins va.








Ricard a écrit :



M’en fous, je chiffre en 4096.<img data-src=" /> &nbsp;



&nbsp;

Plus y’a de bit plus c’est bon&nbsp;<img data-src=" />



+1, un lien vers l’etang eu été attendu


Trop gros, ça passeras pas, surtout un premier Avril<img data-src=" />


J’ai toujours détester le 1e avril de PCI.

On dirait un concoure de qui a le poison d’avril le plus pourris.


Dommage, ça aurait été la news du mois. <img data-src=" />


Demandons à une IA de fabriquer des poissons d’Avril.


Trop gros, ça sent le poisson d’avril. Enfin, j’espère en tout cas <img data-src=" />


&gt;&lt;)))°&gt; <img data-src=" />


Le chiffrement boit la tasse <img data-src=" />

<img data-src=" />


John connor va revenir nous sauver


Expliquez nous comment faire, nous serons … tout ouïe








Obidoub a écrit :



&nbsp;

Plus y’a de bit plus c’est bon&nbsp;<img data-src=" />





ça s’appelle un gang bang ? &nbsp;<img data-src=" />



Meuh oui, trop gros, l’article est bien ficelé mais aucune source n’est citée, notament on n’a pas le nom de l’équipe de chercheur ou du labo de recherche. C’est trop inhabituel <img data-src=" />








linker a écrit :



Le chiffrement boit la tasse <img data-src=" />

<img data-src=" />





Et ce n’est pas une contrepèterie &nbsp; …<img data-src=" />



bien écrit en tout cas. un poisson d’avril bien soigné <img data-src=" />


Des détails seront donnés dans quelques heures. Reste branchie.


C’est pas faux ;)


et pxq lol PQ quoi <img data-src=" />


Il paraîtrait même que l’algo de l’IA utiliserait la loi de Poisson <img data-src=" /> <img data-src=" /> <img data-src=" /> <img data-src=" />


sauce ? (pas hollandaise)


un des meilleurs poissons d’avril que j’ai jamais lu


Et le cassage des algos utilisés par Truecrypt, il en est où ? ^^

Mais il est vrai que ça sent le bon poisson d’avril ;)


Trop crédible …


Comment ça ils ont cassé le RSA ?

Ils veulent détruire toutes les petites protections ou quoi ?



et puis il n’est pas de 2048 bits mais de 524.68 et c’est vraiment pas beaucoup.



et ils viennent de le casser …


En tout cas, cette découverte, c’est du caviar pour la NSA.


J’ai commencé à trouver ça bizarre quand ça parlait des chercheurs qui ne savaient pas ce que l’IA utilisait comme méthode de calcul…



Heureusement, sinon, on serait très très mal et ça sentirait le poisson pourri pour longtemps.


C’est vrai que c’est obvious. Un par premier avril c’est amplement suffisant.


Punaise, j’ai foncé dedans comme un bleu -_-


Zut et moi qui lis ça sérieusement… !


Si seulement… on pourrait enfin récupérer les fichiers corrompus par les ransomwares qui trainent en ce moment :/


Ouf, me voilà rassuré. Deux possibilités :





  1. Soit c’est un poisson d’avril, et&nbsp;on peut être sûr que ce n’est pas la gratuité de Xamarin qui est à remettre en cause.



  2. Soit c’est la gratuité de Xamarin qui est le poisson d’avril, mais on s’en fout puisqu’on pourra casser sa protection anti-copie avec ce crack de RSA.



    Dans les deux cas, on est gagnant&nbsp;<img data-src=" />


Bravo pour ceux qui ont tout de suite vu l’anarque du 1er avril.


Non, p et q, c’est vrai de vrai.


J’ai eu tellement peur… o.O


Me suis fait eu


mwarf.



joli papier, mais le manque de sources est fatal. <img data-src=" />


“logarithme discret”

Quoi est-ce ?


j’ai failli y croire quand même :)&nbsp; bien joué


Je me suis fait avoir :(


Hehe, le jour où ma protection en 2^19 bits se fera sauter la capsule, qu’on m’appelle <img data-src=" />








fr1g0 a écrit :



et pxq lol PQ quoi <img data-src=" />





Ça par contre, ça ne prouve rien en terme de poisson. Quand on étudie les algos de chiffrement basés sur des nombres premiers, ils sont systématiques baptisés p et q. Le p étant surement pour “premier”, et le q parce que c’est la lettre suivante dans l’alphabet (comme en géométrie, les sommets d’un triangle sont souvent A, B et C).









Winderly a écrit :



“logarithme discret”

Quoi est-ce ?





https://fr.wikipedia.org/wiki/Logarithme_discret



Un mécanisme one-way qui n’est pas utilisé par RSA mais bien par d’autres techniques notamment Diffie Hellman.



Edit, oui en fait RSA l’utilise aussi pour le chiffrement proprement dit, mais pas pour sécuriser la clé.

&nbsp;









ArchangeBlandin a écrit :



J’ai commencé à trouver ça bizarre quand ça parlait des chercheurs qui ne savaient pas ce que l’IA utilisait comme méthode de calcul…



Heureusement, sinon, on serait très très mal et ça sentirait le poisson pourri pour longtemps.





Non, justement, c’est la “magie” des réseaux de neurones (en particulier lorsqu’il y a plein de couche) : on ne sais pas trop comment ça fonctionne, mais ça fonctionne.



Ce qui moi, m’a fait douté, c’est que justement les réseaux de neurones ne sont pas fait pour donner un résultats exact. Ca donne généralement un résultat plutôt probable (voir même un ensemble de résultats plus ou moins probable). Le type de problème me semble assez inadapté à un réseau de neurone qui est plutôt adapté à des problème acceptant un résultat approximatif.

Il y a aussi le fait qu’il faut du temps pour un réseaux de neurone… un réseau de neurone, le résultat est instantanée pratiquement. C’est l’apprentissage qui est long.



Mais sinon, tout le reste de l’article, de ce que je connais (j’ai pas compris pourquoi certain tilte sur le 2048bit) tout semble correcte, l’explication du RSA, même la façon d’apprentissage supervisé. C’est carrément crédible.



j’y ai cru … mais un petit coin de ma caboche garde toujours en tête qu’une IA a battu un maitre de Go et une autre a passé le test de Turing



alors ça pourrait être possible <img data-src=" />








tazvld a écrit :



Ce qui moi, m’a fait douté, c’est que justement les réseaux de neurones ne sont pas fait pour donner un résultats exact. Ca donne généralement un résultat plutôt probable (voir même un ensemble de résultats plus ou moins probable).





Tout à fait, seulement ça n’empêche pas l’utilisation dans le cas présenté ici : Il suffit de tester “bêtement” les résultats les plus probables donné par le réseau de neurones pour savoir s’il est valide ou non.



La journée va être sacrément drôle sur NXI !



Un système utilisé dans la cryptographie :)

Ici pour Wikipedia et là pour l’actu sur l’analyse des chercheurs

&nbsp;<img data-src=" />


C’est clair que sans source… hum hum ^^


Ça aurait été une bonne nouvelle contre locky .. Mais bon IA de 30 000 CPU ?


Si c’est vrai ça voudrait dire que la machine a trouvé un algorithme de résolution de complexité polynomiale (ou inférieure) à un problème que les mathématiciens croient nP ou nPcomplet.

Intellectuellement ça serait jouissif.

La tournure “pédagogique” de la news me met aussi la puce à l’oreille j’attends demain pour voir…








Elwyns a écrit :



Ça aurait été une bonne nouvelle contre locky .. Mais bon IA de 30 000 CPU ?







En additionnement coeurs logiques et physiques c’est possible, bien que cette données n’est pas indicative de la puissance de la chose.



Bon, je retourne faire des clapotis









manzell a écrit :



Et le cassage des algos utilisés par Truecrypt, il en est où ? ^^

Mais il est vrai que ça sent le bon poisson d’avril ;)







DTC aux dernières nouvelles



Me suis encore fait avoir !


La vache, j’ai sursauté une demi seconde avant de penser au calendrier, vous m’avez eu là !


Et les “algorithmes quantique” ils sont pas adaptés pour ce genre de problème?








tazvld a écrit :



(…)



Ce qui moi, m’a fait douté, c’est que justement les réseaux de neurones ne sont pas fait pour donner un résultats exact. Ca donne généralement un résultat plutôt probable (voir même un ensemble de résultats plus ou moins probable). Le type de problème me semble assez inadapté à un réseau de neurone qui est plutôt adapté à des problème acceptant un résultat approximatif.

(…)







C’est même poisson d’avril dans les commentaires !

Du lourd, du très lourd (probablement) <img data-src=" />




Vin Diesel a écrit :

ça s’appelle un gang bang ? &nbsp;<img data-src=" />



méchant garçon<img data-src=" />



(non je n’ai pas pensé à exactement la même chose)


J’y ai presque cru (bien que ça me semblait gros quand même) jusqu’à ce que je lise que le réseau de neurones a gagné en vitesse de résolution du calcul, ce qui n’a aucun sens.


Tu peux essayé de faire apprendre à faire des calcules à un réseau de neurone, (en fonction de la complexité de l’opération que tu lui as appris) au mieux il te donnera une réponse possible ou un ensemble de réponse possible avec un valeur de vraisemblance et dont l’une d’entre elle est, modulo d’une part d’erreur, le bon résultat.

Un réseau de neurone n’est pas fait pour sortir la réponse absolue, il ne sort qu’une réponse assez bonne la majorité du temps.



Un réseau de neurone, c’est ni plus ni moins qu’un mecs qui avec plein d’expérience est capable de faire des estimation pifométrique d’assez bonne qualité. C’est comme ce que l’on est capable de faire pour estimer avec que force et quel angle il faut que je jette mon bout de papier pour qu’il tombe dans la corbeille sans avoir à sortir une calculette.


Rhoo, quand on voit le nombre de machines requises pour le RC5-72, ca parait difficile.



J’y avais participé pendant plus d’un an, avec les machines du bureau qui tartinaient H24.

L’époque ou les PowerPC G4/G5 mettaient une tannée aux autres dans ce domaine, bha oui les entiers quoi ^^



Je pense savoir ce qu’est un réseau de neurones, plus ou moins.

Je pense que tu écris là des bêtises, sans doute dans un soucis de simplification, tant le contexte de mise en œuvre va influer la prédiction du modèle : dans le monde de la classification de symboles, c’est bien fait pour te donner un résultat exact (qui peut cependant être faux, bien sûr).



Au passage, tu connais des modèles qui te sortent “la réponse absolue” ? Il me semble qu’il en existe… aucun…


Pour la classification des symboles (reconnaissance d’écriture ?) non, le résultat n’est pas absolue, et selon la façon dont tu design ta couche de sortie, tu vas par exemple avoir un indice de vraisemblance pour chaque caractère, celui qui à le score le plus élevé est donc très certainement la réponse.

Avec l’expérience, il va en effet quand même réussir à trier les caractères très bien, et même mieux qu’un humain. Mais c’est surtout une histoire de probabilité de vraisemblance.



Mais dans l’absolue, ce n’est pas fait pour faire une calculette. Or, là, pour le chiffrement RSA, ce que l’on recherche ce sont les 2 chiffres premiers et exactement ceux là, c’est donc un résultat qui n’accepte pas l’à peu prêt, le pifomètre, il existe qu’une seule réponse strict (il n’y a pas de probabilité en jeu, il n’y a pas un vecteur de solutions plus ou moins correcte).


Ce que tu décris c’est l’application des réseaux de neurones à des problème impliquant la logique floue mais ce n’est pas la seule application


On est bien d’accord, aucun résultat, et ce par n’importe quel modèle, n’est absolu.

C’est pourtant bien le but - d’obtenir la bonne réponse à coup sûr - notre salut, très probablement inatteignable il est vrai.

Ton “les réseaux de neurones ne sont pas fait pour donner un résultat exact” me semble alors assez à côté de la plaque vu que l’objectif de la multiplication de ces modèles est bien de tendre vers la réponse absolue.



Classification des symboles : reconnaissance d’écriture (dactylo, manuscrite), de symboles sur schéma électrique, sur plan architecturaux, de logo sur les images de scène naturelle, de pictogrammes, de chiffres sur plaque d’immatriculation, de panneaux de signalisation….








malock a écrit :



On est bien d’accord, aucun résultat, et ce par n’importe quel modèle, n’est absolu.

C’est pourtant bien le but - d’obtenir la bonne réponse à coup sûr - notre salut, très probablement inatteignable il est vrai.

Ton “les réseaux de neurones ne sont pas fait pour donner un résultat exact” me semble alors assez à côté de la plaque vu que l’objectif de la multiplication de ces modèles est bien de tendre vers la réponse absolue.



Classification des symboles : reconnaissance d’écriture (dactylo, manuscrite), de symboles sur schéma électrique, sur plan architecturaux, de logo sur les images de scène naturelle, de pictogrammes, de chiffres sur plaque d’immatriculation, de panneaux de signalisation….





Dans le cas présent sur chiffrement RSA, si, le résultat est absolu, il n’existe qu’un seul couple p et q de nombre premier qui donne la clé public. Et d’une certaine façon, heureusement.

Parfois (souvent), on a besoin d’un résultat exact (lorsque celui est calculable) et ce n’est pas avec un réseau de neurone que l’on confiera ce calcule.

La reconnaissance de symboles est à contrario effectivement un type de problème pour lequel les réseaux de neurones sont tout a fait adaptés.







Geronimo54 a écrit :



Ce que tu décris c’est l’application des réseaux de neurones à des problème impliquant la logique floue mais ce n’est pas la seule application





Que ce soit dans la reconnaissance d’image ou dans la conduite d’un véhicule en passage au jeu de Go, l’idée reste la même, le but n’est pas de proposer la meilleur solution, c’est de proposer très rapidement une bonne solution, quelque chose qui est vraisemblablement correct par rapport à ce qu’il a vu/appris précédemment.

D’un point de vu plus architecturale, un réseau de neurone est effectivement quelque chose qui peut être une machine de Turing et il serait possible potentiellement de l’utiliser pour faire du calcule exact, mais dans la pratique, c’est difficile voir totalement débile. Dans la réalité, on utilise les réseaux de neurones comme une machine avec plein de potentiomètre que l’on va moduler de tel sort qu’à sortie l’erreur soit minimale (dans le cadre d’un apprentissage supervisé).



Le FBI, la NSA, la DGSE, le MOSSAD, le KGB, le MI6, la CIA et Bernard Cazeneuve approuvent cet article <img data-src=" />








Obidoub a écrit :



&nbsp;

Plus y’a de bit plus c’est bon&nbsp;<img data-src=" />





Le long moment de solitude de la prof d’algo, en école d’ingé, annonçant “aujourd’hui on va voir les champs de bits”…



Elle a du regretter de ne pas avoir parlé d’élement binaire! Cela aurait emmené d’autres questions tant le terme est désuet, mais elle n’aurait pas rougi!



Chapeau, super bien tourné l’article… Je n’avais pas fait le lien avant de lire les commentaires….


J’aime bien les sujets des videos sur Lidd.fr aussi, tout pour se fendre la gueule entre “tout savoir sur le bilan comptable”, “L’assomoir de Zola en 30 minutes” et “Qu’est ce que l’usufruit ?” <img data-src=" />


Alors ça, ça c’est du 1er avril de taré.

Si cette news était vraie, je m’ouvrirais les veines dans l’heure.



Heureusement elle est fausse, il faudrait actuellement 4 milliards d’années à tous les ordinateurs de la planète pour casser un RSA2048.



Si cette news était vraie, ce serait la panique : Internet la finance toute entière s’écrouleraient, ce serait la guerre mondiale.



Ça voudrait dire qu’on a trouvé la fonction qui génère les nombres premiers, ce qui est l’une des (la ?) plus grande énigme mathématique.


En l’occurrence j’ai plus compris la news comme “un réseau de neurones a trouvé un théorème mathématique permettant de trouver le couple p et q”. On part par contre dans une toute autre complexité des réseaux de neurones, qui auraient alors atteint un niveau d’intelligence bien supérieur à ce qu’on sait leur donner à l’heure actuelle. Cette IA nous donnerait le résultat à la manière d’un être humain, faisant parfois des erreurs de calculs mais étant globalement correcte.

Ça donne même à réfléchir car si la news était vraie, cela veut dire qu’on aurait une IA ayant trouvé un théorème que l’on ne connaît pas et elle n’est pas capable de nous le donner facilement, faisant ça de façon instinctive.


Heureusement que j’ai lu ton post, j’y croyais déjà. Je suis vraiment fatigué moi.


Oh même pas, p et q sont simplement les lettres consacrées lorsqu’on parle d’entiers en arithmétique, qu’ils soient premiers ou non.


La mèche est vendue dès le début de l’explication puisqu’on parle de multiplier des nombre premiers d’un côté et de les factoriser de l’autre, or par définition un nombre premier n’est pas factorisable… mais la méthode existe peut-être en multipliant et en factorisant des grands nombres quelconques avec deux consignes “stop” :



si l’un des nombres est factorisable alors il n’est pas premier -&gt; stop

si le produit des deux nombres ne correspond pas au résultat -&gt; stop



mais ça je pense que c’est la base de la base…








Chungking a écrit :



Oh même pas, p et q sont simplement les lettres consacrées lorsqu’on parle d’entiers en arithmétique, qu’ils soient premiers ou non.







Bof, les entiers, c’est plutôt n par défaut non ?

Après je prétends pas tout savoir des maths, je bosse pas dans les maths, donc c’est juste mes souvenirs de cours.









Chungking a écrit :



La mèche est vendue dès le début de l’explication puisqu’on parle de multiplier des nombre premiers d’un côté et de les factoriser de l’autre, or par définition un nombre premier n’est pas factorisable…







Nan t’as juste raté un bout du fonctionnement <img data-src=" />



Comme dit l’article, la clé RSA est le résultat de la multiplication de p et de q . Retrouver la valeur de p ou de q permet de déchiffrer les messages, donc il vaut mieux ne pas réussir à les trouver. L’opération qui permet de retrouver p et q, c’est bien la factorisation, vu que clé = p x q.



Et l’histoire des nombres premiers, c’est qu’utiliser des nombres premiers pour p et q rend la factorisation longue et difficile.



oui on utilise n, k, puis souvent l et m pour des entiers naturels (positifs donc). C’est le cas en algèbre où ces entiers sont souvent les indices des termes d’une suite, un nombre de termes à “sommer”, une puissance implicitement positive, etc. Bref n est un élément de N. En arithmétique p et q sont généralement des entiers relatifs donc éléments de Z. Pour l’anecdote z est généralement un élément de C (complexe) mais ça tu le sais sûrement déjà ;-)



Pour ton deuxième commentaire, je crois que j’avais bien compris ce que tu dis :



mais il y a bien deux façons de raisonner qui peuvent être mises en parallèle, soit on multiplie des grands nombres sans savoir s’ils sont premiers (éventuellement avec des outils statistiques) et si le résultat est égal a la clé alors c’est q’on a trouvé le bon couple (p,q) puisque la décomposition en facteurs premiers est unique.



Ou&nbsp;alors on test des nombres p pour savoir s’ils sont premiers et on essaie de diviser la clé avec &nbsp;pour déduire q et surtout confirmer qu’on a le bon p (si la division est entière c’est gagné).



Quoi qu’il en soit la phrase :&nbsp;“la machine calcule d’un côté le&nbsp;produit de deux grands nombres premiers, tandis qu’elle essaye de les factoriser de l’autre” n’a toujours pas de sens pour moi ou alors factoriser ne veut plus dire développer en produit de facteurs ?



&nbsp;

&nbsp;Mais contrairement à ce que tu dis, je crois que le grand avantage des nombres premiers c’est de rendre la solution unique. Pour une clé publique c, il existe un seul couple (p,q) de clés privées tel c=pxq.



Pour faire simple :



91=7x13 et c’est la seule décomposition qu’on puisse faire du nombre 91 parce que 7 et 13 sont premiers



mais 60=6x10=2x30=3x20=5x12



Bon mes souvenirs de licence de maths sont loin aussi et peut-être que je cherche la petite bête ;-)


En générale pas pour les hommes.<img data-src=" /><img data-src=" />








Chungking a écrit :



La mèche est vendue dès le début de l’explication puisqu’on parle de multiplier des nombre premiers d’un côté et de les factoriser de l’autre, or par définition un nombre premier n’est pas factorisable… mais la méthode existe peut-être en multipliant et en factorisant des grands nombres quelconques avec deux consignes “stop” :



si l’un des nombres est factorisable alors il n’est pas premier -&gt; stop

si le produit des deux nombres ne correspond pas au résultat -&gt; stop



mais ça je pense que c’est la base de la base…





Non, tu n’a pas compris, p et q sont effictivement premier et constitue la clé privé (celle pour décoder), ok, mais le produit p*q qui constitue la clé public (celle pour encoder) et factorisable. Du fait que la factorisation en nombre premier est difficile, on estime donc que diffuser le produit de 2 nombres premiers assez grand ne permet pas de retrouver les 2 nombres premiers en un temps acceptable

L’explication de la clé RSA, selon mes souvenirs est donc correcte.

C’est toute la magie de cet article, il est cohérent, presque tout ce qui est dit est plausible : plein de truc vrai permet de mettre en zone de confort et permet de nous faire avaler n’importe quoi. Cela marche d’autant plus que dans les truc vrai, il faut atteindre le niveau du lectorat, il faut titiller son égo en mettant des truc qu’il sait mais que peu de gens ne savent (le chiffrement RSA ici), ça le rend encore moins méfiant.



purée je me suis fait avoir sur les trois plus gros poissons :(