On considère p et q deux grands nombres premiers, et n leur produit (cas
de RSA).
Qu'adviendrait-il si une personne trouvait une méthode rapide pour
passer de n à p et à q ? Et si cette personne publiait cette méthode ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Cedric Blancher
Dans sa prose, Horace nous ecrivait :
Qu'adviendrait-il si une personne trouvait une méthode rapide pour passer de n à p et à q ?
RSA serait cassé.
Et si cette personne publiait cette méthode ?
Ce serait une bonne chose, car ça nous permettrait d'arrêter d'utiliser un système en le pensant sûr.
-- Je vais essayer de couper à 80. Mais lorsqu'on quote des messages déjà quoté plusieurs fois (>>>) Outlook coupe toujours à 80. N'y aurait-il pas la possibilité d'avoir une coupe paramétrable ? -+- C in Guide du Neuneu d'Usenet - L'art de couper les neuneux en 4 -+-
Dans sa prose, Horace nous ecrivait :
Qu'adviendrait-il si une personne trouvait une méthode rapide pour
passer de n à p et à q ?
RSA serait cassé.
Et si cette personne publiait cette méthode ?
Ce serait une bonne chose, car ça nous permettrait d'arrêter d'utiliser
un système en le pensant sûr.
--
Je vais essayer de couper à 80. Mais lorsqu'on quote des messages déjà
quoté plusieurs fois (>>>) Outlook coupe toujours à 80.
N'y aurait-il pas la possibilité d'avoir une coupe paramétrable ?
-+- C in Guide du Neuneu d'Usenet - L'art de couper les neuneux en 4 -+-
Qu'adviendrait-il si une personne trouvait une méthode rapide pour passer de n à p et à q ?
RSA serait cassé.
Et si cette personne publiait cette méthode ?
Ce serait une bonne chose, car ça nous permettrait d'arrêter d'utiliser un système en le pensant sûr.
-- Je vais essayer de couper à 80. Mais lorsqu'on quote des messages déjà quoté plusieurs fois (>>>) Outlook coupe toujours à 80. N'y aurait-il pas la possibilité d'avoir une coupe paramétrable ? -+- C in Guide du Neuneu d'Usenet - L'art de couper les neuneux en 4 -+-
Bertrand Masius
Bonjour,
Bonsoir.
On considère p et q deux grands nombres premiers, et n leur produit (cas de RSA). Qu'adviendrait-il si une personne trouvait une méthode rapide pour passer de n à p et à q ? Et si cette personne publiait cette méthode ?
On le mettrait en taule. -- "Ce que l'on conçoit bien s'énonce clairement, Et les mots pour le dire arrivent aisément."
(Nicolas Boileau, l'Art poétique)
Bonjour,
Bonsoir.
On considère p et q deux grands nombres premiers, et n leur produit (cas
de RSA).
Qu'adviendrait-il si une personne trouvait une méthode rapide pour
passer de n à p et à q ? Et si cette personne publiait cette méthode ?
On le mettrait en taule.
--
"Ce que l'on conçoit bien s'énonce clairement,
Et les mots pour le dire arrivent aisément."
On considère p et q deux grands nombres premiers, et n leur produit (cas de RSA). Qu'adviendrait-il si une personne trouvait une méthode rapide pour passer de n à p et à q ? Et si cette personne publiait cette méthode ?
On le mettrait en taule. -- "Ce que l'on conçoit bien s'énonce clairement, Et les mots pour le dire arrivent aisément."
On considère p et q deux grands nombres premiers, et n leur produit (cas de RSA). Qu'adviendrait-il si une personne trouvait une méthode rapide pour passer de n à p et à q ? Et si cette personne publiait cette méthode ?
On le mettrait en taule.
Puis, quelques années (ou siècles) plus tard, on lui éleverait une statue ;-)
-- Paul Gaborit - <http://www.enstimac.fr/~gaborit/> Remove '.OOO' from e-mail address - Supprimez '.OOO' de l'adresse e-mail
On considère p et q deux grands nombres premiers, et n leur produit (cas
de RSA).
Qu'adviendrait-il si une personne trouvait une méthode rapide pour
passer de n à p et à q ? Et si cette personne publiait cette méthode ?
On le mettrait en taule.
Puis, quelques années (ou siècles) plus tard, on lui éleverait une statue ;-)
--
Paul Gaborit - <http://www.enstimac.fr/~gaborit/>
Remove '.OOO' from e-mail address - Supprimez '.OOO' de l'adresse e-mail
On considère p et q deux grands nombres premiers, et n leur produit (cas de RSA). Qu'adviendrait-il si une personne trouvait une méthode rapide pour passer de n à p et à q ? Et si cette personne publiait cette méthode ?
On le mettrait en taule.
Puis, quelques années (ou siècles) plus tard, on lui éleverait une statue ;-)
-- Paul Gaborit - <http://www.enstimac.fr/~gaborit/> Remove '.OOO' from e-mail address - Supprimez '.OOO' de l'adresse e-mail
Niamor
Ce serait la fin de bien des algo et donc des programmes à clés publiques Néanmoins ça fait un paquet de mathématicien qu'il faudrait mettre au rebut :-)
donc la probabilité que cela se passe est aussi grande que celle que tous les atomes de ta prochaine bière ait une agitation moléculaire de même vecteur, vers le haut et que tu prennes instantanément ladite bière à la figure :-)
donc on peut dormir tranquille...
Niamor
"Horace" a écrit dans le message de news:bksmbn$jhc$
Bonsoir.
On considère p et q deux grands nombres premiers, et n leur produit (cas
de RSA). Qu'adviendrait-il si une personne trouvait une méthode rapide pour passer de n à p et à q ? Et si cette personne publiait cette méthode ?
~~ Xtof
Ce serait la fin de bien des algo et donc des programmes à clés publiques
Néanmoins ça fait un paquet de mathématicien qu'il faudrait mettre au rebut
:-)
donc la probabilité que cela se passe est aussi grande que celle que tous
les atomes de ta prochaine bière
ait une agitation moléculaire de même vecteur, vers le haut et que tu
prennes instantanément ladite bière à la figure :-)
donc on peut dormir tranquille...
Niamor
"Horace" <ERROR@ERROR.fr> a écrit dans le message de
news:bksmbn$jhc$1@news-reader4.wanadoo.fr...
Bonsoir.
On considère p et q deux grands nombres premiers, et n leur produit
(cas
de RSA).
Qu'adviendrait-il si une personne trouvait une méthode rapide pour
passer de n à p et à q ? Et si cette personne publiait cette méthode ?
Ce serait la fin de bien des algo et donc des programmes à clés publiques Néanmoins ça fait un paquet de mathématicien qu'il faudrait mettre au rebut :-)
donc la probabilité que cela se passe est aussi grande que celle que tous les atomes de ta prochaine bière ait une agitation moléculaire de même vecteur, vers le haut et que tu prennes instantanément ladite bière à la figure :-)
donc on peut dormir tranquille...
Niamor
"Horace" a écrit dans le message de news:bksmbn$jhc$
Bonsoir.
On considère p et q deux grands nombres premiers, et n leur produit (cas
de RSA). Qu'adviendrait-il si une personne trouvait une méthode rapide pour passer de n à p et à q ? Et si cette personne publiait cette méthode ?
~~ Xtof
pornin
According to Niamor :
Ce serait la fin de bien des algo et donc des programmes à clés publiques
N'exagérons rien : tous les algos à clé publique ne sont pas fondé sur le problème de la factorisation. D'autres, très utilisés aussi, travaillent sur le logarithme discret (DSS, Diffie-Hellman, El-Gamal...). On peut imaginer qu'une résolution rapide de la factorisation pourrait donner de quoi faire une résolution rapide du logarithme discret (en théorie des nombres, ces deux problèmes ont des liens relativement étroits), mais il reste les variantes sur courbe elliptique (qui, eux, n'ont pas grand'chose à voir, mais marchent bien). Et il y a d'autre types d'algorithmes à clé publique (du genre de NTRU).
Dans tous les cas, si tout ça saute, on peut en revenir aux système de signature de Merkle, à base de fonctions de hachage et d'arbres d'authentification ; ils ne sont pas très efficaces, mais on peut en faire quelque chose quand même.
En résumé, un algorithme de factorisation rapide serait pénible pour le business, mais ce serait surmonté en quelques mois/années.
--Thomas Pornin
According to Niamor <romain.roubaty@hevs.ch>:
Ce serait la fin de bien des algo et donc des programmes à clés publiques
N'exagérons rien : tous les algos à clé publique ne sont pas fondé
sur le problème de la factorisation. D'autres, très utilisés
aussi, travaillent sur le logarithme discret (DSS, Diffie-Hellman,
El-Gamal...). On peut imaginer qu'une résolution rapide de la
factorisation pourrait donner de quoi faire une résolution rapide du
logarithme discret (en théorie des nombres, ces deux problèmes ont des
liens relativement étroits), mais il reste les variantes sur courbe
elliptique (qui, eux, n'ont pas grand'chose à voir, mais marchent bien).
Et il y a d'autre types d'algorithmes à clé publique (du genre de NTRU).
Dans tous les cas, si tout ça saute, on peut en revenir aux système
de signature de Merkle, à base de fonctions de hachage et d'arbres
d'authentification ; ils ne sont pas très efficaces, mais on peut en
faire quelque chose quand même.
En résumé, un algorithme de factorisation rapide serait pénible pour
le business, mais ce serait surmonté en quelques mois/années.
Ce serait la fin de bien des algo et donc des programmes à clés publiques
N'exagérons rien : tous les algos à clé publique ne sont pas fondé sur le problème de la factorisation. D'autres, très utilisés aussi, travaillent sur le logarithme discret (DSS, Diffie-Hellman, El-Gamal...). On peut imaginer qu'une résolution rapide de la factorisation pourrait donner de quoi faire une résolution rapide du logarithme discret (en théorie des nombres, ces deux problèmes ont des liens relativement étroits), mais il reste les variantes sur courbe elliptique (qui, eux, n'ont pas grand'chose à voir, mais marchent bien). Et il y a d'autre types d'algorithmes à clé publique (du genre de NTRU).
Dans tous les cas, si tout ça saute, on peut en revenir aux système de signature de Merkle, à base de fonctions de hachage et d'arbres d'authentification ; ils ne sont pas très efficaces, mais on peut en faire quelque chose quand même.
En résumé, un algorithme de factorisation rapide serait pénible pour le business, mais ce serait surmonté en quelques mois/années.
--Thomas Pornin
Cedric Blancher
Dans sa prose, Paul GABORIT nous ecrivait :
On le mettrait en taule. Puis, quelques années (ou siècles) plus tard, on lui éleverait une
statue ;-)
Après l'avoir canonisé et fait de la date de son exécution un jour férié.
-- Je pense que ça en vaut la peine. La hiérarchie fr.* est très mal construite. Non, vraiment, c'est très mal fait, et vous devriez tous envisager le grand chantier de l'an 2000, et refaire tout ça. -+- BC in GNU : Je suis un bug de l'an 2000 à moi tout seul -+-
Dans sa prose, Paul GABORIT nous ecrivait :
On le mettrait en taule.
Puis, quelques années (ou siècles) plus tard, on lui éleverait une
statue ;-)
Après l'avoir canonisé et fait de la date de son exécution un jour
férié.
--
Je pense que ça en vaut la peine. La hiérarchie fr.* est très mal
construite. Non, vraiment, c'est très mal fait, et vous devriez
tous envisager le grand chantier de l'an 2000, et refaire tout ça.
-+- BC in GNU : Je suis un bug de l'an 2000 à moi tout seul -+-
On le mettrait en taule. Puis, quelques années (ou siècles) plus tard, on lui éleverait une
statue ;-)
Après l'avoir canonisé et fait de la date de son exécution un jour férié.
-- Je pense que ça en vaut la peine. La hiérarchie fr.* est très mal construite. Non, vraiment, c'est très mal fait, et vous devriez tous envisager le grand chantier de l'an 2000, et refaire tout ça. -+- BC in GNU : Je suis un bug de l'an 2000 à moi tout seul -+-
Jean-Marc Desperrier
Thomas Pornin wrote:
[...] On peut imaginer qu'une résolution rapide de la factorisation pourrait donner de quoi faire une résolution rapide du logarithme discret (en théorie des nombres, ces deux problèmes ont des liens relativement étroits),
Ca n'a pas été prouvé ? Ou alors prouvé mais dans l'autre sens à partir du logarithme vers la factorisation ?
En résumé, un algorithme de factorisation rapide serait pénible pour le business, mais ce serait surmonté en quelques mois/années.
Honnêtement, je crois qu'on grossirait simplement les clés jusqu'à ce qu'elles redeviennent solides. Une factorisation rapide permet *aussi* de tirer des clés plus vite et le temps de signature/vérification n'est pas bloquant. Génant, mais pas bloquant.
Evidemment si le cassage devenait linéaire suivant la taille, la clé de 50 Ko serait un peu encombrante, suffisament pour pousser à passer à la courbe elliptique très vite.
Thomas Pornin wrote:
[...] On peut imaginer qu'une résolution rapide de la
factorisation pourrait donner de quoi faire une résolution rapide du
logarithme discret (en théorie des nombres, ces deux problèmes ont des
liens relativement étroits),
Ca n'a pas été prouvé ? Ou alors prouvé mais dans l'autre sens à partir
du logarithme vers la factorisation ?
En résumé, un algorithme de factorisation rapide serait pénible pour
le business, mais ce serait surmonté en quelques mois/années.
Honnêtement, je crois qu'on grossirait simplement les clés jusqu'à ce
qu'elles redeviennent solides. Une factorisation rapide permet *aussi*
de tirer des clés plus vite et le temps de signature/vérification n'est
pas bloquant. Génant, mais pas bloquant.
Evidemment si le cassage devenait linéaire suivant la taille, la clé de
50 Ko serait un peu encombrante, suffisament pour pousser à passer à la
courbe elliptique très vite.
[...] On peut imaginer qu'une résolution rapide de la factorisation pourrait donner de quoi faire une résolution rapide du logarithme discret (en théorie des nombres, ces deux problèmes ont des liens relativement étroits),
Ca n'a pas été prouvé ? Ou alors prouvé mais dans l'autre sens à partir du logarithme vers la factorisation ?
En résumé, un algorithme de factorisation rapide serait pénible pour le business, mais ce serait surmonté en quelques mois/années.
Honnêtement, je crois qu'on grossirait simplement les clés jusqu'à ce qu'elles redeviennent solides. Une factorisation rapide permet *aussi* de tirer des clés plus vite et le temps de signature/vérification n'est pas bloquant. Génant, mais pas bloquant.
Evidemment si le cassage devenait linéaire suivant la taille, la clé de 50 Ko serait un peu encombrante, suffisament pour pousser à passer à la courbe elliptique très vite.
Eric Razny
"Jean-Marc Desperrier" a écrit dans le message de news:bkv4st$nv7$
En résumé, un algorithme de factorisation rapide serait pénible pour le business, mais ce serait surmonté en quelques mois/années. Honnêtement, je crois qu'on grossirait simplement les clés jusqu'à ce
qu'elles redeviennent solides.
Sauf si c'est le problème de factorisation lui même qui est devenu "simple". Dans ce cas c'est le système qu'il faut jetter, et en prendre un tout propre :)
Une factorisation rapide permet *aussi* de tirer des clés plus vite et le temps de signature/vérification n'est pas bloquant. Génant, mais pas bloquant.
Pour "tirer" les clefs et les vérifier on ne procède pas à une factorisation. Il existait des tests probabilistes (avec possibilité de choisir p non nul, aussi petit que voulu) afin de determiner si un nombre est composé. On a montré depuis qu'il existe une possibilité de vérification certaine (pas de proba) qu'un nombre est premier en temps polynomial [1]
Evidemment si le cassage devenait linéaire suivant la taille, la clé de 50 Ko serait un peu encombrante, suffisament pour pousser à passer à la courbe elliptique très vite.
Si c'est linéaire il vaut mieux, amha, ne pas passer à autre chose vite, mais de suite! Ca veut dire que le système *est cassé* et que récupérer le clair n'est qu'une question de moyen.
Sinon pour répondre à la question d'origne, si quelqu'un trouve comment factoriser rapidement il a intérêt à rendre sa méthode publique ou à tout jetter au feu et ne rien dire. Sinon, vu les implications, ça risque d'être sous la torture avant élimination :)
Eric.
[1] Google doit donner ça sur "Prime is in P".
"Jean-Marc Desperrier" <jmdesp@alussinan.org> a écrit dans le message de
news:bkv4st$nv7$1@reader1.imaginet.fr...
En résumé, un algorithme de factorisation rapide serait pénible pour
le business, mais ce serait surmonté en quelques mois/années.
Honnêtement, je crois qu'on grossirait simplement les clés jusqu'à ce
qu'elles redeviennent solides.
Sauf si c'est le problème de factorisation lui même qui est devenu "simple".
Dans ce cas c'est le système qu'il faut jetter, et en prendre un tout propre
:)
Une factorisation rapide permet *aussi*
de tirer des clés plus vite et le temps de signature/vérification n'est
pas bloquant. Génant, mais pas bloquant.
Pour "tirer" les clefs et les vérifier on ne procède pas à une
factorisation. Il existait des tests probabilistes (avec possibilité de
choisir p non nul, aussi petit que voulu) afin de determiner si un nombre
est composé. On a montré depuis qu'il existe une possibilité de vérification
certaine (pas de proba) qu'un nombre est premier en temps polynomial [1]
Evidemment si le cassage devenait linéaire suivant la taille, la clé de
50 Ko serait un peu encombrante, suffisament pour pousser à passer à la
courbe elliptique très vite.
Si c'est linéaire il vaut mieux, amha, ne pas passer à autre chose vite,
mais de suite! Ca veut dire que le système *est cassé* et que récupérer le
clair n'est qu'une question de moyen.
Sinon pour répondre à la question d'origne, si quelqu'un trouve comment
factoriser rapidement il a intérêt à rendre sa méthode publique ou à tout
jetter au feu et ne rien dire. Sinon, vu les implications, ça risque d'être
sous la torture avant élimination :)
"Jean-Marc Desperrier" a écrit dans le message de news:bkv4st$nv7$
En résumé, un algorithme de factorisation rapide serait pénible pour le business, mais ce serait surmonté en quelques mois/années. Honnêtement, je crois qu'on grossirait simplement les clés jusqu'à ce
qu'elles redeviennent solides.
Sauf si c'est le problème de factorisation lui même qui est devenu "simple". Dans ce cas c'est le système qu'il faut jetter, et en prendre un tout propre :)
Une factorisation rapide permet *aussi* de tirer des clés plus vite et le temps de signature/vérification n'est pas bloquant. Génant, mais pas bloquant.
Pour "tirer" les clefs et les vérifier on ne procède pas à une factorisation. Il existait des tests probabilistes (avec possibilité de choisir p non nul, aussi petit que voulu) afin de determiner si un nombre est composé. On a montré depuis qu'il existe une possibilité de vérification certaine (pas de proba) qu'un nombre est premier en temps polynomial [1]
Evidemment si le cassage devenait linéaire suivant la taille, la clé de 50 Ko serait un peu encombrante, suffisament pour pousser à passer à la courbe elliptique très vite.
Si c'est linéaire il vaut mieux, amha, ne pas passer à autre chose vite, mais de suite! Ca veut dire que le système *est cassé* et que récupérer le clair n'est qu'une question de moyen.
Sinon pour répondre à la question d'origne, si quelqu'un trouve comment factoriser rapidement il a intérêt à rendre sa méthode publique ou à tout jetter au feu et ne rien dire. Sinon, vu les implications, ça risque d'être sous la torture avant élimination :)
Eric.
[1] Google doit donner ça sur "Prime is in P".
pornin
According to Jean-Marc Desperrier :
Ca n'a pas été prouvé ? Ou alors prouvé mais dans l'autre sens à partir du logarithme vers la factorisation ?
À ma connaissance, rien n'est vraiment prouvé en la matière. Disons qu'à chaque fois que j'ai rencontré un chercheur qui parlait de ça et que j'ai demandé si un des deux sens (ou les deux) était prouvé, sa réponse était très compliquée.
Ce que je sais en revanche, c'est que le meilleur (asymptotiquement) algorithme de factorisation connu, et le meilleur algorithme de logarithme discret, sont tous les deux des variations sur le thème du crible algébrique.
Honnêtement, je crois qu'on grossirait simplement les clés jusqu'à ce qu'elles redeviennent solides.
C'est une question de rapport. On veut que le rapport entre l'effort pour casser la clé et l'effort pour s'en servir soit le plus grand possible. Comme l'usage normal peut être sur carte à puce, et que le méchant a un parc de 5000 gros PC, il faut que le rapport soit au moins d'une centaine de millions pour qu'on soit peinard.
L'utilisation de RSA est en O(n^3) ("n" est la taille du module RSA, 1024 si on fait du RSA 1024 bits). Si on trouve un algorithme efficace de factorisation en O(n^4), le rapport est en O(n), et il ne devient correct que pour des clés qui font 10 méga-octets, et donc des clés trop longues pour être décemment utilisées sur une carte à puce. Si l'algorithme de factorisation est en O(n^3), c'est pire : il n'y a plus de taille de clé qui permette de retrouver le rapport de sécurité. Dans ce cas, RSA serait considéré comme définitivement cassé, sans espoir de retour.
--Thomas Pornin
According to Jean-Marc Desperrier <jmdesp@alussinan.org>:
Ca n'a pas été prouvé ? Ou alors prouvé mais dans l'autre sens à partir
du logarithme vers la factorisation ?
À ma connaissance, rien n'est vraiment prouvé en la matière. Disons
qu'à chaque fois que j'ai rencontré un chercheur qui parlait de ça
et que j'ai demandé si un des deux sens (ou les deux) était prouvé,
sa réponse était très compliquée.
Ce que je sais en revanche, c'est que le meilleur (asymptotiquement)
algorithme de factorisation connu, et le meilleur algorithme de
logarithme discret, sont tous les deux des variations sur le thème
du crible algébrique.
Honnêtement, je crois qu'on grossirait simplement les clés jusqu'à ce
qu'elles redeviennent solides.
C'est une question de rapport. On veut que le rapport entre l'effort
pour casser la clé et l'effort pour s'en servir soit le plus grand
possible. Comme l'usage normal peut être sur carte à puce, et que le
méchant a un parc de 5000 gros PC, il faut que le rapport soit au moins
d'une centaine de millions pour qu'on soit peinard.
L'utilisation de RSA est en O(n^3) ("n" est la taille du module RSA,
1024 si on fait du RSA 1024 bits). Si on trouve un algorithme efficace
de factorisation en O(n^4), le rapport est en O(n), et il ne devient
correct que pour des clés qui font 10 méga-octets, et donc des clés
trop longues pour être décemment utilisées sur une carte à puce. Si
l'algorithme de factorisation est en O(n^3), c'est pire : il n'y a plus
de taille de clé qui permette de retrouver le rapport de sécurité. Dans
ce cas, RSA serait considéré comme définitivement cassé, sans espoir de
retour.
Ca n'a pas été prouvé ? Ou alors prouvé mais dans l'autre sens à partir du logarithme vers la factorisation ?
À ma connaissance, rien n'est vraiment prouvé en la matière. Disons qu'à chaque fois que j'ai rencontré un chercheur qui parlait de ça et que j'ai demandé si un des deux sens (ou les deux) était prouvé, sa réponse était très compliquée.
Ce que je sais en revanche, c'est que le meilleur (asymptotiquement) algorithme de factorisation connu, et le meilleur algorithme de logarithme discret, sont tous les deux des variations sur le thème du crible algébrique.
Honnêtement, je crois qu'on grossirait simplement les clés jusqu'à ce qu'elles redeviennent solides.
C'est une question de rapport. On veut que le rapport entre l'effort pour casser la clé et l'effort pour s'en servir soit le plus grand possible. Comme l'usage normal peut être sur carte à puce, et que le méchant a un parc de 5000 gros PC, il faut que le rapport soit au moins d'une centaine de millions pour qu'on soit peinard.
L'utilisation de RSA est en O(n^3) ("n" est la taille du module RSA, 1024 si on fait du RSA 1024 bits). Si on trouve un algorithme efficace de factorisation en O(n^4), le rapport est en O(n), et il ne devient correct que pour des clés qui font 10 méga-octets, et donc des clés trop longues pour être décemment utilisées sur une carte à puce. Si l'algorithme de factorisation est en O(n^3), c'est pire : il n'y a plus de taille de clé qui permette de retrouver le rapport de sécurité. Dans ce cas, RSA serait considéré comme définitivement cassé, sans espoir de retour.
