si rsa tombe

Pierre Vandevennne

08/07/2004 à 00:25

"remy" wrote in news:cch1or$eli$:

bonjour

apres la lecture de

http://www.apprendre-en-ligne.net/crypto/rsa/267_104_108.pdf
je me demande quelles sont les consequences pour la societe civile
si rsa tombe

RSA ne tombera pas totalement. Il restera toujours une asymétrie qui fera
qu'un éventuel crack prendra quand même du temps et on pourra augmenter la
taille des clés.

Faut savoir que si RSA est aussi populaire aujourd'hui c'est parce que les
méthodes d'attaque sont équivalentes à des problèmes étudiés depuis des
millénaires et qu'on ne peut s'attendre à des progrès majeurs subits. C'est
ce qui fait son charme par rapport à des techniques plus ésotériques, mais
dont l'étude réserve peut être plus de surprises.

(et quand ces méthodes plus ésotériques sont recommandées par la NSA, on
hésite entre deux opinions - ils ont cassé RSA et pensent que d'autres
méthodes sont plus sûres/ils ont cassé les autres méthodes et veulent
pousser les autres à les utiliser)

Une autre possibilité est le saut technologique, par exemple les
ordinateurs quantiques. Mais dans ce cas, il y aurait tant de choses qui
changeraient...

quels sont les resaux informatiques qui sont proteges par rsa ??
l'aviation ,les satellites ,... ???

Grosso-modo tout ce qui requiert une authentification et/ou un échange de
clé. Mais dans l'éventualité d'un crack majeur, il suffirait de mettre tout
à jour. Pas simple, pas nécessairement économiquement intéressant, mais pas
la fin du monde non plus.

Laurent Jumet

08/07/2004 à 10:14

Hello !

Pierre Vandevennne wrote:

PV> RSA ne tombera pas totalement. Il restera toujours une asymétrie qui
PV> fera qu'un éventuel crack prendra quand même du temps et on pourra
PV> augmenter la taille des clés.

Cela sur base d'un crack via la factorisation; mais il existe peut-être
un autre crack non encore défini par la mathématique.

PV> Faut savoir que si RSA est aussi populaire aujourd'hui c'est parce que
PV> les méthodes d'attaque sont équivalentes à des problèmes étudiés depuis
PV> des millénaires et qu'on ne peut s'attendre à des progrès majeurs
PV> subits. C'est ce qui fait son charme par rapport à des techniques plus
PV> ésotériques, mais dont l'étude réserve peut être plus de surprises.

Ne crois-tu pas que si un universitaire patriote découvre le crack, il
le réservera aux seuls services de son pays?
Lire en clair les messages de ses ennemis est tout de même agréable.
Mais pour nous, le résultat est le même: tant que le crack n'est pas
public, le secret est garanti sauf si nous sommes listés comme ennemis
potentiels.

Durant les deux Guerres, les codes ont été crackés et personne ne l'a
su.
De même que certains qui nous lisent sont cocus, mais ils l'ignorent.
:-)

--
Laurent Jumet - Point de Chat, Liège, BELGIUM
KeyID: 0xCFAF704C
[Restore address to laurent.jumet for e-mail reply.]

Pierre Vandevenne

08/07/2004 à 13:24

Erwan David wrote in
news::

Pierre Vandevennne écrivait :

RSA ne tombera pas totalement. Il restera toujours une asymétrie qui
fera qu'un éventuel crack prendra quand même du temps et on pourra
augmenter la taille des clés.

Sauf changement de contexte, par exemple si on met au point les
ordinateurs quantiques, alors RSA sera cassé.

Oui, c'était le paragraphe 4 de mon message. Mais à ce moment, lorsque nous
aurons un ordinateur quantique sur notre bureau, le fait qu'il cracke le
RSA sera probablement secondaire.

--
Pierre Vandevenne - DataRescue sa/nv - www.datarescue.com
The IDA Pro Disassembler & Debugger - world leader in hostile code analysis
PhotoRescue - advanced data recovery for digital photographic media
latest review: http://www.pcmag.com/article2/0,1759,1590497,00.asp

Francois Grieu

08/07/2004 à 13:29

Pierre Vandevennne dit:

si RSA est aussi populaire aujourd'hui c'est parce que les
méthodes d'attaque sont équivalentes à des problèmes étudiés
depuis des millénaires et qu'on ne peut s'attendre à des
progrès majeurs subits.

Je réfute le raisonnement, pour deux raisons:
- Il y a eu des progrès radicaux dans la factorisation
sur les dernières 30 années, précisément à cause de
l'intérêt que provoque la popularité de RSA. Les conseils
des premiers articles, genre "des clés de 200 chiffres
(décimaux) donnent une marge de sécurité contre les
futurs développements (en matière de factosiation)"
et les challenges de l'époque (129 chiffres [2])
se sont révélés imprudents, du fait de l'invention
ultérieures de méthodes de factorisation comme MPQS,
ECM, puis finalement GNFS, qui sont à ce que les
millénaires précédents ont produit en matière de
factorisation ce que la bombe H est au pétard.
- Accesoirement, le problème RSA n'est peut-être pas
équivalent à la factorisation, et est peut-être plus
facile; et il n'est pas étudié depuis des millénaires.

Mon raisonnement est plutôt: RSA existe depuis 27 ans.
Il y a eu initialement des progtès dans son attaque,
mais plus rien de majeur ces dernières 12 années,
où le problème a été ultra étudié. Le risque d'un progrès
brutal est acceptable au regard des autres menaces
encourues dans de nombreuses applications. Et il est peu
couteux de prendre des grandes clés si l'enjeu est majeur.

Quand à la popularité de RSA, AMHA elle est initialement due
pour beaucoup à sa relative simplicité, et à la bonne
communication [2] qu'a facilité cette qualité. Ensuite,
l'inertie (selon moi, la force la plus puissante de
l'univers) a fait le reste.

François Grieu

[1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems"
Communications of the ACM archive Volume 21, Issue 2
(February 1978, first submitted April 4, 1977).
<http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

[2] M. Gardner: "A new kind of cipher that would take millions
of years to break", Scientific American, August 1977, p120/124.

Pierre Vandevennne <pierre@datarescue_ns.com> dit:

si RSA est aussi populaire aujourd'hui c'est parce que les
méthodes d'attaque sont équivalentes à des problèmes étudiés
depuis des millénaires et qu'on ne peut s'attendre à des
progrès majeurs subits.

Je réfute le raisonnement, pour deux raisons:
- Il y a eu des progrès radicaux dans la factorisation
sur les dernières 30 années, précisément à cause de
l'intérêt que provoque la popularité de RSA. Les conseils
des premiers articles, genre "des clés de 200 chiffres
(décimaux) donnent une marge de sécurité contre les
futurs développements (en matière de factosiation)"
et les challenges de l'époque (129 chiffres [2])
se sont révélés imprudents, du fait de l'invention
ultérieures de méthodes de factorisation comme MPQS,
ECM, puis finalement GNFS, qui sont à ce que les
millénaires précédents ont produit en matière de
factorisation ce que la bombe H est au pétard.
- Accesoirement, le problème RSA n'est peut-être pas
équivalent à la factorisation, et est peut-être plus
facile; et il n'est pas étudié depuis des millénaires.

Mon raisonnement est plutôt: RSA existe depuis 27 ans.
Il y a eu initialement des progtès dans son attaque,
mais plus rien de majeur ces dernières 12 années,
où le problème a été ultra étudié. Le risque d'un progrès
brutal est acceptable au regard des autres menaces
encourues dans de nombreuses applications. Et il est peu
couteux de prendre des grandes clés si l'enjeu est majeur.

Quand à la popularité de RSA, AMHA elle est initialement due
pour beaucoup à sa relative simplicité, et à la bonne
communication [2] qu'a facilité cette qualité. Ensuite,
l'inertie (selon moi, la force la plus puissante de
l'univers) a fait le reste.

François Grieu

[1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems"
Communications of the ACM archive Volume 21, Issue 2
(February 1978, first submitted April 4, 1977).
<http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

[2] M. Gardner: "A new kind of cipher that would take millions
of years to break", Scientific American, August 1977, p120/124.

Vous avez filtré cet utilisateur ! Consultez son message

Pierre Vandevennne dit:

si RSA est aussi populaire aujourd'hui c'est parce que les
méthodes d'attaque sont équivalentes à des problèmes étudiés
depuis des millénaires et qu'on ne peut s'attendre à des
progrès majeurs subits.

Je réfute le raisonnement, pour deux raisons:
- Il y a eu des progrès radicaux dans la factorisation
sur les dernières 30 années, précisément à cause de
l'intérêt que provoque la popularité de RSA. Les conseils
des premiers articles, genre "des clés de 200 chiffres
(décimaux) donnent une marge de sécurité contre les
futurs développements (en matière de factosiation)"
et les challenges de l'époque (129 chiffres [2])
se sont révélés imprudents, du fait de l'invention
ultérieures de méthodes de factorisation comme MPQS,
ECM, puis finalement GNFS, qui sont à ce que les
millénaires précédents ont produit en matière de
factorisation ce que la bombe H est au pétard.
- Accesoirement, le problème RSA n'est peut-être pas
équivalent à la factorisation, et est peut-être plus
facile; et il n'est pas étudié depuis des millénaires.

Mon raisonnement est plutôt: RSA existe depuis 27 ans.
Il y a eu initialement des progtès dans son attaque,
mais plus rien de majeur ces dernières 12 années,
où le problème a été ultra étudié. Le risque d'un progrès
brutal est acceptable au regard des autres menaces
encourues dans de nombreuses applications. Et il est peu
couteux de prendre des grandes clés si l'enjeu est majeur.

Quand à la popularité de RSA, AMHA elle est initialement due
pour beaucoup à sa relative simplicité, et à la bonne
communication [2] qu'a facilité cette qualité. Ensuite,
l'inertie (selon moi, la force la plus puissante de
l'univers) a fait le reste.

François Grieu

[1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems"
Communications of the ACM archive Volume 21, Issue 2
(February 1978, first submitted April 4, 1977).
<http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

[2] M. Gardner: "A new kind of cipher that would take millions
of years to break", Scientific American, August 1977, p120/124.

Pierre Vandevenne

08/07/2004 à 13:51

Francois Grieu wrote in news:fgrieu-
:

Pierre Vandevennne dit:

si RSA est aussi populaire aujourd'hui c'est parce que les
méthodes d'attaque sont équivalentes à des problèmes étudiés
depuis des millénaires et qu'on ne peut s'attendre à des
progrès majeurs subits.

Je réfute le raisonnement, pour deux raisons:
- Il y a eu des progrès radicaux dans la factorisation
sur les dernières 30 années, précisément à cause de
l'intérêt que provoque la popularité de RSA.

cause: RSA est populaire parce qu'on pense, au moment où il apparait, qu'il
n'y aura pas trop de progrès.

conséquence: comme tu le dis, on étudie le sujet à mort.

conséquence secondaire: on fait des progrès.

Ces progrès sont-ils spectaculaires? Je ne le pense pas. Faudrait par
exemple comparer avec la loi de Moore (retroactivement bien sûr).

Les conseils
des premiers articles, genre "des clés de 200 chiffres
(décimaux) donnent une marge de sécurité contre les
futurs développements (en matière de factosiation)"
et les challenges de l'époque (129 chiffres [2])
se sont révélés imprudents, du fait de l'invention
ultérieures de méthodes de factorisation comme MPQS,
ECM, puis finalement GNFS, qui sont à ce que les
millénaires précédents ont produit en matière de
factorisation ce que la bombe H est au pétard.

Quand PGP est sorti, j'ai opté pour une clé de 1024 bits. Je me suis fait
traiter de "con" par des gens extrêmement renommés qui m'ont patiemment
expliqué que 384 bits étaient largement suffisants. Je partage donc ton
point de vue mais cela se gère facilement en augmentant la taille des clés.

Peut-on comparer, grosso-modo, la valeur des apports théoriques à
l'augmentation de puissance de calcul sur les 27 dernières années?

- Accesoirement, le problème RSA n'est peut-être pas
équivalent à la factorisation, et est peut-être plus
facile; et il n'est pas étudié depuis des millénaires.

S'il est équivalent à la factorisation, il est étudié depuis des
millénaires.

S'il n'est "peut-être" pas équivalent à la factorisation, il n'est peut-
être pas" étudié depuis des millénaires.

Mon raisonnement est plutôt: RSA existe depuis 27 ans.
Il y a eu initialement des progtès dans son attaque,
mais plus rien de majeur ces dernières 12 années,
où le problème a été ultra étudié. Le risque d'un progrès
brutal est acceptable au regard des autres menaces
encourues dans de nombreuses applications.

Là, on est d'accord.

Et il est peu
couteux de prendre des grandes clés si l'enjeu est majeur.

Idem.

Quand à la popularité de RSA, AMHA elle est initialement due
pour beaucoup à sa relative simplicité, et à la bonne

Il y avait-il d'autres choix à l'époque. D'accord pour la simplicité: je
peux le comprendre et comprendre les attaques typiques, ce qui n'est pas le
cas des courbes elliptiques (je lit Koblitz et puis j'oublie, je lis
Koblitz et puis j'oublie... je suis sur une bande de Moebius ici)

communication [2] qu'a facilité cette qualité.

Oui et non. D'abord, comme Thomas Pornin le rappelait régulièrement, SA n'a
pas toujours bonne presse parmi les spécialistes.

Ensuite, RSA a été patenté, ce qui a créé d'énormes complications à sa
mise-en-oeuvre...

(tu peux me retourner l'argument, en me disant que l'attrait de l'interdit
a joué un rôle dans son développement).

l'inertie (selon moi, la force la plus puissante de
l'univers) a fait le reste.

Oui certainement.

Mais aujourd'hui, 27 ans plus tard, qui as une alternative à proposer? Les
courbes elliptiques? Il n'y a que les hyper-spécialistes qui s'y
retrouvent.

--
Pierre Vandevenne - DataRescue sa/nv - www.datarescue.com
The IDA Pro Disassembler & Debugger - world leader in hostile code analysis
PhotoRescue - advanced data recovery for digital photographic media
latest review: http://www.pcmag.com/article2/0,1759,1590497,00.asp

Francois Grieu <fgrieu@francenet.fr> wrote in news:fgrieu-
AACE1A.13292908072004@individual.net:

Pierre Vandevennne <pierre@datarescue_ns.com> dit:

si RSA est aussi populaire aujourd'hui c'est parce que les
méthodes d'attaque sont équivalentes à des problèmes étudiés
depuis des millénaires et qu'on ne peut s'attendre à des
progrès majeurs subits.

Je réfute le raisonnement, pour deux raisons:
- Il y a eu des progrès radicaux dans la factorisation
sur les dernières 30 années, précisément à cause de
l'intérêt que provoque la popularité de RSA.

cause: RSA est populaire parce qu'on pense, au moment où il apparait, qu'il
n'y aura pas trop de progrès.

conséquence: comme tu le dis, on étudie le sujet à mort.

conséquence secondaire: on fait des progrès.

Ces progrès sont-ils spectaculaires? Je ne le pense pas. Faudrait par
exemple comparer avec la loi de Moore (retroactivement bien sûr).

Les conseils
des premiers articles, genre "des clés de 200 chiffres
(décimaux) donnent une marge de sécurité contre les
futurs développements (en matière de factosiation)"
et les challenges de l'époque (129 chiffres [2])
se sont révélés imprudents, du fait de l'invention
ultérieures de méthodes de factorisation comme MPQS,
ECM, puis finalement GNFS, qui sont à ce que les
millénaires précédents ont produit en matière de
factorisation ce que la bombe H est au pétard.

Quand PGP est sorti, j'ai opté pour une clé de 1024 bits. Je me suis fait
traiter de "con" par des gens extrêmement renommés qui m'ont patiemment
expliqué que 384 bits étaient largement suffisants. Je partage donc ton
point de vue mais cela se gère facilement en augmentant la taille des clés.

Peut-on comparer, grosso-modo, la valeur des apports théoriques à
l'augmentation de puissance de calcul sur les 27 dernières années?

- Accesoirement, le problème RSA n'est peut-être pas
équivalent à la factorisation, et est peut-être plus
facile; et il n'est pas étudié depuis des millénaires.

S'il est équivalent à la factorisation, il est étudié depuis des
millénaires.

S'il n'est "peut-être" pas équivalent à la factorisation, il n'est peut-
être pas" étudié depuis des millénaires.

Mon raisonnement est plutôt: RSA existe depuis 27 ans.
Il y a eu initialement des progtès dans son attaque,
mais plus rien de majeur ces dernières 12 années,
où le problème a été ultra étudié. Le risque d'un progrès
brutal est acceptable au regard des autres menaces
encourues dans de nombreuses applications.

Là, on est d'accord.

Et il est peu
couteux de prendre des grandes clés si l'enjeu est majeur.

Idem.

Quand à la popularité de RSA, AMHA elle est initialement due
pour beaucoup à sa relative simplicité, et à la bonne

Il y avait-il d'autres choix à l'époque. D'accord pour la simplicité: je
peux le comprendre et comprendre les attaques typiques, ce qui n'est pas le
cas des courbes elliptiques (je lit Koblitz et puis j'oublie, je lis
Koblitz et puis j'oublie... je suis sur une bande de Moebius ici)

communication [2] qu'a facilité cette qualité.

Oui et non. D'abord, comme Thomas Pornin le rappelait régulièrement, SA n'a
pas toujours bonne presse parmi les spécialistes.

Ensuite, RSA a été patenté, ce qui a créé d'énormes complications à sa
mise-en-oeuvre...

(tu peux me retourner l'argument, en me disant que l'attrait de l'interdit
a joué un rôle dans son développement).

l'inertie (selon moi, la force la plus puissante de
l'univers) a fait le reste.

Oui certainement.

Mais aujourd'hui, 27 ans plus tard, qui as une alternative à proposer? Les
courbes elliptiques? Il n'y a que les hyper-spécialistes qui s'y
retrouvent.

--
Pierre Vandevenne - DataRescue sa/nv - www.datarescue.com
The IDA Pro Disassembler & Debugger - world leader in hostile code analysis
PhotoRescue - advanced data recovery for digital photographic media
latest review: http://www.pcmag.com/article2/0,1759,1590497,00.asp

Vous avez filtré cet utilisateur ! Consultez son message

Francois Grieu wrote in news:fgrieu-
:

Pierre Vandevennne dit:

si RSA est aussi populaire aujourd'hui c'est parce que les
méthodes d'attaque sont équivalentes à des problèmes étudiés
depuis des millénaires et qu'on ne peut s'attendre à des
progrès majeurs subits.

Je réfute le raisonnement, pour deux raisons:
- Il y a eu des progrès radicaux dans la factorisation
sur les dernières 30 années, précisément à cause de
l'intérêt que provoque la popularité de RSA.

cause: RSA est populaire parce qu'on pense, au moment où il apparait, qu'il
n'y aura pas trop de progrès.

conséquence: comme tu le dis, on étudie le sujet à mort.

conséquence secondaire: on fait des progrès.

Ces progrès sont-ils spectaculaires? Je ne le pense pas. Faudrait par
exemple comparer avec la loi de Moore (retroactivement bien sûr).

Les conseils
des premiers articles, genre "des clés de 200 chiffres
(décimaux) donnent une marge de sécurité contre les
futurs développements (en matière de factosiation)"
et les challenges de l'époque (129 chiffres [2])
se sont révélés imprudents, du fait de l'invention
ultérieures de méthodes de factorisation comme MPQS,
ECM, puis finalement GNFS, qui sont à ce que les
millénaires précédents ont produit en matière de
factorisation ce que la bombe H est au pétard.

Quand PGP est sorti, j'ai opté pour une clé de 1024 bits. Je me suis fait
traiter de "con" par des gens extrêmement renommés qui m'ont patiemment
expliqué que 384 bits étaient largement suffisants. Je partage donc ton
point de vue mais cela se gère facilement en augmentant la taille des clés.

Peut-on comparer, grosso-modo, la valeur des apports théoriques à
l'augmentation de puissance de calcul sur les 27 dernières années?

- Accesoirement, le problème RSA n'est peut-être pas
équivalent à la factorisation, et est peut-être plus
facile; et il n'est pas étudié depuis des millénaires.

S'il est équivalent à la factorisation, il est étudié depuis des
millénaires.

S'il n'est "peut-être" pas équivalent à la factorisation, il n'est peut-
être pas" étudié depuis des millénaires.

Mon raisonnement est plutôt: RSA existe depuis 27 ans.
Il y a eu initialement des progtès dans son attaque,
mais plus rien de majeur ces dernières 12 années,
où le problème a été ultra étudié. Le risque d'un progrès
brutal est acceptable au regard des autres menaces
encourues dans de nombreuses applications.

Là, on est d'accord.

Et il est peu
couteux de prendre des grandes clés si l'enjeu est majeur.

Idem.

Quand à la popularité de RSA, AMHA elle est initialement due
pour beaucoup à sa relative simplicité, et à la bonne

Il y avait-il d'autres choix à l'époque. D'accord pour la simplicité: je
peux le comprendre et comprendre les attaques typiques, ce qui n'est pas le
cas des courbes elliptiques (je lit Koblitz et puis j'oublie, je lis
Koblitz et puis j'oublie... je suis sur une bande de Moebius ici)

communication [2] qu'a facilité cette qualité.

Oui et non. D'abord, comme Thomas Pornin le rappelait régulièrement, SA n'a
pas toujours bonne presse parmi les spécialistes.

Ensuite, RSA a été patenté, ce qui a créé d'énormes complications à sa
mise-en-oeuvre...

(tu peux me retourner l'argument, en me disant que l'attrait de l'interdit
a joué un rôle dans son développement).

l'inertie (selon moi, la force la plus puissante de
l'univers) a fait le reste.

Oui certainement.

Mais aujourd'hui, 27 ans plus tard, qui as une alternative à proposer? Les
courbes elliptiques? Il n'y a que les hyper-spécialistes qui s'y
retrouvent.

--
Pierre Vandevenne - DataRescue sa/nv - www.datarescue.com
The IDA Pro Disassembler & Debugger - world leader in hostile code analysis
PhotoRescue - advanced data recovery for digital photographic media
latest review: http://www.pcmag.com/article2/0,1759,1590497,00.asp

remy

08/07/2004 à 14:16

Mais aujourd'hui, 27 ans plus tard, qui as une alternative à proposer? Les
courbes elliptiques? Il n'y a que les hyper-spécialistes qui s'y
retrouvent.

et encore pas toutes les courbes il y en a meme qui ont ete
brevetees surement les meilleures

en voila une question interessante
comment echanger des cles sans rsa

--
Pierre Vandevenne - DataRescue sa/nv - www.datarescue.com
The IDA Pro Disassembler & Debugger - world leader in hostile code
analysis

PhotoRescue - advanced data recovery for digital photographic media
latest review: http://www.pcmag.com/article2/0,1759,1590497,00.asp

Francois Grieu

08/07/2004 à 17:21

Pierre Vandevenne wrote:

Peut-on comparer, grosso-modo, la valeur des apports théoriques à
l'augmentation de puissance de calcul sur les 27 dernières années?

Essayons. En 1974, l'algorithme le plus rapide connu des
inventeurs de RSA [1] utilisait selon eux une puissance de calcul
proportionnelle à ln(n)^((ln(n)/ln(ln(n)))^(1/2))
et à l'époque on en était à peu près à des nombres de 128 bits.

Avec ces références, et en prenant comme loi de Moore que la
puissance de calcul double tout les 18 mois, passer de 128 à
512 bits [1999] aurait du prendre 55 ans, cela en a pris 25.
Si je prends comme référence 576 bits [2003] c'est 62 ans
contre 29.

Sur une échelle logarithmique, le progrès lié à l'algorithmique
depuis 1975 serait donc comparable (un peu supérieur) à celui
lié à la loi de Moore.
Il me semble que la tendance est au ralentissement sur les
deux fronts: l'algorithmique a peu progressé depuis 10 ans,
de même que le temps d'accès à la DRAM (qui en pratique
est le facteur qui limite le plus la vitesse des algorithmes
utilisés).

Ce résultat est à prendre avec des pincettes, pour plein de
raisons:
- Un variante de la loi de Moore énonce que la puissance de
calcul double tout les 12 mois, et non 18 mois.
- Je ne sais pas vraiment quelle taille de nombre RSA était
factorisable en 1974, ni avec quelle puissance de calcul.
Les références précises ne sont pas légion. J'ai en fait
extrapolé deux références:
- La factorisation de 2^(2^7)+1 en 1970 par Morrison et
Brillhart; c'était je crois par fractions continues,
applicable aux clés RSA de même taille (128 bits) avec un
temps de calcul nettement plus élevé. Je n'ai pas retrouvé
d'indicaton sur le temps de calcul ni sur la machine.
- Une référence relativement bien établie [2] que en 1982,
il fallait environ une journée de super-ordinateur pour
une clé RSA de 166 bits (50 chiffres)

François Grieu

[1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems"
Communications of the ACM archive Volume 21, Issue 2
(February 1978, first submitted April 4, 1977).
<http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

[2] Davis, J. A., Holdridge, D. B. and Simmons, G. J
"Status report on factoring (at the Sandia National Labs)"
Eurocrypt 1984.
<http://google.com/search?q=Status+report+factoring+Sandia+National+Labs>

Pierre Vandevenne <pierre@datarescue.com> wrote:

Peut-on comparer, grosso-modo, la valeur des apports théoriques à
l'augmentation de puissance de calcul sur les 27 dernières années?

Essayons. En 1974, l'algorithme le plus rapide connu des
inventeurs de RSA [1] utilisait selon eux une puissance de calcul
proportionnelle à ln(n)^((ln(n)/ln(ln(n)))^(1/2))
et à l'époque on en était à peu près à des nombres de 128 bits.

Avec ces références, et en prenant comme loi de Moore que la
puissance de calcul double tout les 18 mois, passer de 128 à
512 bits [1999] aurait du prendre 55 ans, cela en a pris 25.
Si je prends comme référence 576 bits [2003] c'est 62 ans
contre 29.

Sur une échelle logarithmique, le progrès lié à l'algorithmique
depuis 1975 serait donc comparable (un peu supérieur) à celui
lié à la loi de Moore.
Il me semble que la tendance est au ralentissement sur les
deux fronts: l'algorithmique a peu progressé depuis 10 ans,
de même que le temps d'accès à la DRAM (qui en pratique
est le facteur qui limite le plus la vitesse des algorithmes
utilisés).

Ce résultat est à prendre avec des pincettes, pour plein de
raisons:
- Un variante de la loi de Moore énonce que la puissance de
calcul double tout les 12 mois, et non 18 mois.
- Je ne sais pas vraiment quelle taille de nombre RSA était
factorisable en 1974, ni avec quelle puissance de calcul.
Les références précises ne sont pas légion. J'ai en fait
extrapolé deux références:
- La factorisation de 2^(2^7)+1 en 1970 par Morrison et
Brillhart; c'était je crois par fractions continues,
applicable aux clés RSA de même taille (128 bits) avec un
temps de calcul nettement plus élevé. Je n'ai pas retrouvé
d'indicaton sur le temps de calcul ni sur la machine.
- Une référence relativement bien établie [2] que en 1982,
il fallait environ une journée de super-ordinateur pour
une clé RSA de 166 bits (50 chiffres)

François Grieu

[1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems"
Communications of the ACM archive Volume 21, Issue 2
(February 1978, first submitted April 4, 1977).
<http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

[2] Davis, J. A., Holdridge, D. B. and Simmons, G. J
"Status report on factoring (at the Sandia National Labs)"
Eurocrypt 1984.
<http://google.com/search?q=Status+report+factoring+Sandia+National+Labs>

Vous avez filtré cet utilisateur ! Consultez son message

Pierre Vandevenne wrote:

Peut-on comparer, grosso-modo, la valeur des apports théoriques à
l'augmentation de puissance de calcul sur les 27 dernières années?

Essayons. En 1974, l'algorithme le plus rapide connu des
inventeurs de RSA [1] utilisait selon eux une puissance de calcul
proportionnelle à ln(n)^((ln(n)/ln(ln(n)))^(1/2))
et à l'époque on en était à peu près à des nombres de 128 bits.

Avec ces références, et en prenant comme loi de Moore que la
puissance de calcul double tout les 18 mois, passer de 128 à
512 bits [1999] aurait du prendre 55 ans, cela en a pris 25.
Si je prends comme référence 576 bits [2003] c'est 62 ans
contre 29.

Sur une échelle logarithmique, le progrès lié à l'algorithmique
depuis 1975 serait donc comparable (un peu supérieur) à celui
lié à la loi de Moore.
Il me semble que la tendance est au ralentissement sur les
deux fronts: l'algorithmique a peu progressé depuis 10 ans,
de même que le temps d'accès à la DRAM (qui en pratique
est le facteur qui limite le plus la vitesse des algorithmes
utilisés).

Ce résultat est à prendre avec des pincettes, pour plein de
raisons:
- Un variante de la loi de Moore énonce que la puissance de
calcul double tout les 12 mois, et non 18 mois.
- Je ne sais pas vraiment quelle taille de nombre RSA était
factorisable en 1974, ni avec quelle puissance de calcul.
Les références précises ne sont pas légion. J'ai en fait
extrapolé deux références:
- La factorisation de 2^(2^7)+1 en 1970 par Morrison et
Brillhart; c'était je crois par fractions continues,
applicable aux clés RSA de même taille (128 bits) avec un
temps de calcul nettement plus élevé. Je n'ai pas retrouvé
d'indicaton sur le temps de calcul ni sur la machine.
- Une référence relativement bien établie [2] que en 1982,
il fallait environ une journée de super-ordinateur pour
une clé RSA de 166 bits (50 chiffres)

François Grieu

[1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems"
Communications of the ACM archive Volume 21, Issue 2
(February 1978, first submitted April 4, 1977).
<http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

[2] Davis, J. A., Holdridge, D. B. and Simmons, G. J
"Status report on factoring (at the Sandia National Labs)"
Eurocrypt 1984.
<http://google.com/search?q=Status+report+factoring+Sandia+National+Labs>

Francois Grieu

08/07/2004 à 17:50

Pierre Vandevenne wrote:

Peut-on comparer, grosso-modo, la valeur des apports théoriques à
l'augmentation de puissance de calcul sur les 27 dernières années?

Essayons. En 1977, l'algorithme le plus rapide connu des
inventeurs de RSA [1] utilisait selon eux une puissance de calcul
proportionnelle à ln(n)^((ln(n)/ln(ln(n)))^(1/2))
et à l'époque on en était à peu près à des nombres de 144 bits.

Avec ces références, et en prenant comme loi de Moore que la
puissance de calcul double tout les 18 mois, passer de 144 à
512 bits [1999] aurait du prendre 52 ans, cela en a pris 22.
Si je prends comme référence 576 bits [2003] c'est 59 ans
contre 26.

Sur une échelle logarithmique, le progrès lié à l'algorithmique
sur 27 ans serait donc comparable (un peu supérieur) à celui
lié à la loi de Moore.
Il me semble que la tendance est au ralentissement sur les
deux fronts: l'algorithmique a peu progressé depuis 10 ans,
de même que le temps d'accès à la DRAM (qui en pratique
est le facteur qui limite le plus la vitesse des algorithmes
utilisés).

Ce résultat est à prendre avec des pincettes, pour plein de
raisons:
- Un variante de la loi de Moore énonce que la puissance de
calcul double tout les 12 mois, et non 18 mois.
- Je ne sais pas vraiment quelle taille de nombre RSA était
factorisable en 1977, ni avec quelle puissance de calcul.
Les références précises ne sont pas légion. J'ai en fait
extrapolé deux références:
- La factorisation de 2^(2^7)+1 en 1970 par Morrison et
Brillhart; c'était je crois par fractions continues,
applicable aux clés RSA de même taille (128 bits) avec un
temps de calcul nettement plus élevé. Je n'ai pas retrouvé
d'indicaton sur le temps de calcul ni sur la machine.
- Une référence relativement bien établie [2] que en 1982,
il fallait environ une journée de super-ordinateur pour
une clé RSA de 166 bits (50 chiffres)

François Grieu
[reposté en corrigeant une bête erreur de 3 ans]

[1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems"
Communications of the ACM archive Volume 21, Issue 2
(February 1978, first submitted April 4, 1977).
<http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

[2] Davis, J. A., Holdridge, D. B. and Simmons, G. J
"Status report on factoring (at the Sandia National Labs)"
Eurocrypt 1984.
<http://google.com/search?q=Status+report+factoring+Sandia+National+Labs>

Pierre Vandevenne <pierre@datarescue.com> wrote:

Peut-on comparer, grosso-modo, la valeur des apports théoriques à
l'augmentation de puissance de calcul sur les 27 dernières années?

Essayons. En 1977, l'algorithme le plus rapide connu des
inventeurs de RSA [1] utilisait selon eux une puissance de calcul
proportionnelle à ln(n)^((ln(n)/ln(ln(n)))^(1/2))
et à l'époque on en était à peu près à des nombres de 144 bits.

Avec ces références, et en prenant comme loi de Moore que la
puissance de calcul double tout les 18 mois, passer de 144 à
512 bits [1999] aurait du prendre 52 ans, cela en a pris 22.
Si je prends comme référence 576 bits [2003] c'est 59 ans
contre 26.

Sur une échelle logarithmique, le progrès lié à l'algorithmique
sur 27 ans serait donc comparable (un peu supérieur) à celui
lié à la loi de Moore.
Il me semble que la tendance est au ralentissement sur les
deux fronts: l'algorithmique a peu progressé depuis 10 ans,
de même que le temps d'accès à la DRAM (qui en pratique
est le facteur qui limite le plus la vitesse des algorithmes
utilisés).

Ce résultat est à prendre avec des pincettes, pour plein de
raisons:
- Un variante de la loi de Moore énonce que la puissance de
calcul double tout les 12 mois, et non 18 mois.
- Je ne sais pas vraiment quelle taille de nombre RSA était
factorisable en 1977, ni avec quelle puissance de calcul.
Les références précises ne sont pas légion. J'ai en fait
extrapolé deux références:
- La factorisation de 2^(2^7)+1 en 1970 par Morrison et
Brillhart; c'était je crois par fractions continues,
applicable aux clés RSA de même taille (128 bits) avec un
temps de calcul nettement plus élevé. Je n'ai pas retrouvé
d'indicaton sur le temps de calcul ni sur la machine.
- Une référence relativement bien établie [2] que en 1982,
il fallait environ une journée de super-ordinateur pour
une clé RSA de 166 bits (50 chiffres)

François Grieu
[reposté en corrigeant une bête erreur de 3 ans]

[1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems"
Communications of the ACM archive Volume 21, Issue 2
(February 1978, first submitted April 4, 1977).
<http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

[2] Davis, J. A., Holdridge, D. B. and Simmons, G. J
"Status report on factoring (at the Sandia National Labs)"
Eurocrypt 1984.
<http://google.com/search?q=Status+report+factoring+Sandia+National+Labs>

Vous avez filtré cet utilisateur ! Consultez son message

Pierre Vandevenne wrote:

Peut-on comparer, grosso-modo, la valeur des apports théoriques à
l'augmentation de puissance de calcul sur les 27 dernières années?

Essayons. En 1977, l'algorithme le plus rapide connu des
inventeurs de RSA [1] utilisait selon eux une puissance de calcul
proportionnelle à ln(n)^((ln(n)/ln(ln(n)))^(1/2))
et à l'époque on en était à peu près à des nombres de 144 bits.

Avec ces références, et en prenant comme loi de Moore que la
puissance de calcul double tout les 18 mois, passer de 144 à
512 bits [1999] aurait du prendre 52 ans, cela en a pris 22.
Si je prends comme référence 576 bits [2003] c'est 59 ans
contre 26.

Sur une échelle logarithmique, le progrès lié à l'algorithmique
sur 27 ans serait donc comparable (un peu supérieur) à celui
lié à la loi de Moore.
Il me semble que la tendance est au ralentissement sur les
deux fronts: l'algorithmique a peu progressé depuis 10 ans,
de même que le temps d'accès à la DRAM (qui en pratique
est le facteur qui limite le plus la vitesse des algorithmes
utilisés).

Ce résultat est à prendre avec des pincettes, pour plein de
raisons:
- Un variante de la loi de Moore énonce que la puissance de
calcul double tout les 12 mois, et non 18 mois.
- Je ne sais pas vraiment quelle taille de nombre RSA était
factorisable en 1977, ni avec quelle puissance de calcul.
Les références précises ne sont pas légion. J'ai en fait
extrapolé deux références:
- La factorisation de 2^(2^7)+1 en 1970 par Morrison et
Brillhart; c'était je crois par fractions continues,
applicable aux clés RSA de même taille (128 bits) avec un
temps de calcul nettement plus élevé. Je n'ai pas retrouvé
d'indicaton sur le temps de calcul ni sur la machine.
- Une référence relativement bien établie [2] que en 1982,
il fallait environ une journée de super-ordinateur pour
une clé RSA de 166 bits (50 chiffres)

François Grieu
[reposté en corrigeant une bête erreur de 3 ans]

[1] R.L. Rivest, A. Shamir, and L. Adleman: "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems"
Communications of the ACM archive Volume 21, Issue 2
(February 1978, first submitted April 4, 1977).
<http://theory.lcs.mit.edu/~rivest/rsapaper.pdf>

[2] Davis, J. A., Holdridge, D. B. and Simmons, G. J
"Status report on factoring (at the Sandia National Labs)"
Eurocrypt 1984.
<http://google.com/search?q=Status+report+factoring+Sandia+National+Labs>

Roland

08/07/2004 à 23:21

Bonjour

J'imagine que ceci a déjà été discuté 10000 fois, mais je n'en trouve
pas de trace:
Avez vous une estimation du besoin CPU (en MIPS par exemple) pour
factoriser un nombre de n bits ?
Au moins une idée de la progression : double-t-elle quand on ajoute
quelques bits, quand on double la longueur n, etc.

A+
Roland

remy wrote:

bonjour

apres la lecture de

http://www.apprendre-en-ligne.net/crypto/rsa/267_104_108.pdf
je me demande quelles sont les consequences pour la societe civile
si rsa tombe
la premiere chose qui me vient a l'esprit c'est la carte bancaire
mais bon ce n'est pas tres grave un vol restera un vol

quels sont les resaux informatiques qui sont proteges par rsa ??
l'aviation ,les satellites ,... ???
a+ remy

remy

09/07/2004 à 09:11

"Roland" a écrit dans le message de news:
40edbaf2$0$18116$

Bonjour

J'imagine que ceci a déjà été discuté 10000 fois, mais je n'en trouve
pas de trace:
Avez vous une estimation du besoin CPU (en MIPS par exemple) pour
factoriser un nombre de n bits ?
Au moins une idée de la progression : double-t-elle quand on ajoute
quelques bits, quand on double la longueur n, etc.

a en binaire
a+1 bit=2*a

donc tu double l'espace de factorisation

a+ remy

A+
Roland

remy wrote:
bonjour

apres la lecture de

http://www.apprendre-en-ligne.net/crypto/rsa/267_104_108.pdf
je me demande quelles sont les consequences pour la societe civile
si rsa tombe
la premiere chose qui me vient a l'esprit c'est la carte bancaire
mais bon ce n'est pas tres grave un vol restera un vol

quels sont les resaux informatiques qui sont proteges par rsa ??
l'aviation ,les satellites ,... ???
a+ remy

si rsa tombe

10 réponses

Veuillez sélectionner un problème