RSA cassé

Le 09 jan, a 10:52, Philippe Lheureux papotait :

http://www.techno-science.net/?onglet=news&newss87

RSA n'est pas cassé. L'article explique qu'une clef de 768 bits a
été cassés après 2 ans et demi de travaux par l'association de
capacités de calcul de plusieurs labos. Ce qui n'est pas une
surprise pour qui connait la Loi de Moore.

La mauvaise foi intellectuelle des mercantiles atteint des
sommets.

--
No fortunes found

On 9 jan, 15:34, Loic Restoux <lrest...@free.fr> wrote:

Le 09 jan, a 10:52, Philippe Lheureux papotait :

>http://www.techno-science.net/?onglet=news&news=7387

RSA n'est pas cass . L'article explique qu'une clef de 768 bits a
t cass s apr s 2 ans et demi de travaux  par  l'association  de
capacit s de calcul de plusieurs labos.

Donc tous les utilisateurs de RSA savent que les tiers qui auraient
(éventuellement) enregistré leurs communications pourront, dans deux
ans et demi prendre connaissance en clair des messages qui sont
secrets aujourd'hui.

C'est rassurant.

On 2010-01-10, Max wrote:

[ RSA est cassable au bout d'un temps très long ]
Donc tous les utilisateurs de RSA savent que les tiers qui auraient
(éventuellement) enregistré leurs communications pourront, dans deux
ans et demi prendre connaissance en clair des messages qui sont
secrets aujourd'hui.

C'est rassurant.

Tu veux quoi ? Le chiffrement parfait ?

Il n'existe pas et personne de censé n'a jamais prétendu le
contraire.

--
Vivien MOREAU / vpm

Max wrote in message
<f3b5d2ce-abc0-4e38-b0da-93e0163a9c65@m3g2000yqf.googlegroups.com>:

Donc tous les utilisateurs de RSA savent que les tiers qui auraient
(éventuellement) enregistré leurs communications pourront, dans deux
ans et demi prendre connaissance en clair des messages qui sont
secrets aujourd'hui.

Pas tous les utilisateurs de RSA. Les utilisateurs de RSA utilisant des
clefs de 768 bits, ayant des secrets de longue durée et qui cherchent à
se protéger contre des attaquants ayant à leur disposition une dizaine de
clusters de 256 cores chacun. Ça ne fait pas énormément de monde.

On 10 jan, 15:00, Vivien MOREAU <vpm+n...@serengetty.fr> wrote:

On 2010-01-10, Max wrote:
> [ RSA est cassable au bout d'un temps très long ]
> Donc tous les utilisateurs de RSA savent que les tiers qui auraient
> (éventuellement) enregistré leurs communications pourront, dans deu x
> ans et demi prendre connaissance en clair des messages qui sont
> secrets aujourd'hui.

> C'est rassurant.

        Tu veux quoi ? Le chiffrement parfait ?

        Il n'existe pas et personne de censé n'a jamais préte ndu le
        contraire.

Parfait, non, mais je ne mettrais pas mes données confidentielles dans
un chiffrement dont la loi de Moore ferait qu'en quelques années,
toutes les archives des communications deviendraient accessibles.

Je n'ai pas suivi l'actualité, mais on doit etre a plus de 50% de
toutes les communications mondiales enregistrées par des services de
renseignement type NSA et qui seront un livre ouvert le jour ou ils
voudront en savoir plus sur quelqu'un.

Donc, plutot que d'utiliser un chiffrement de type RSA ou autre, il
vaut mieux ne pas utiliser de moyen ecoutable pour transmettre qque
chose de confidentiel.

Max wrote:

On 10 jan, 15:00, Vivien MOREAU <vpm+n...@serengetty.fr> wrote:

On 2010-01-10, Max wrote:

[ RSA est cassable au bout d'un temps très long ]
Donc tous les utilisateurs de RSA savent que les tiers qui auraient
(éventuellement) enregistré leurs communications pourront, dans deux
ans et demi prendre connaissance en clair des messages qui sont
secrets aujourd'hui.
C'est rassurant.

Tu veux quoi ? Le chiffrement parfait ?

Il n'existe pas et personne de censé n'a jamais prétendu le
contraire.

Parfait, non, mais je ne mettrais pas mes données confidentielles dans
un chiffrement dont la loi de Moore ferait qu'en quelques années,
toutes les archives des communications deviendraient accessibles.

Si ta clé est trop faible, c'est ce qui arrivera avec toutes les
méthodes de chiffrement existantes actuellement.

Bonjour,

J'aurais aimé quelques renseignements à ce sujet

Avant toute chose, je vous avoue que je n'y connais pas grand-chose en
crypto, n'étant pas un matheux (enfin, moi j'ai rien contre les mat hs,
c'est les maths qui m'aiment pas :() mais le sujet m'intéresse.

Est-ce que cette nouvelle signifie que n'importe quelle message chiffrà ©
avec une clé RSA de 768 bits peut être déchiffré san s avoir le mot de
passe à condition d'avoir suffisament d'ordinateurs et deux ans dev ant soi
?
Parce que j'ai l'impression que quand on parler de "casser" un algorithm e,
ça ne signifie pas forcément être capable de le déch iffrer sans clé.
Les articles que j'ai lu à ce sujet parlent de "factorisation", qu' est-ce
que ça implique ?

Merci de votre indulgence.
--
Envoyé avec l’innovant client de messagerie Opera Mail :
http://www.opera.com/mail/

passage wrote:

Avant toute chose,

Avant toute chose, il faut comprendre ce qu'est le RSA. En très gros, je
ne vais pas détailler, il y a tout ce qu'il faut sur internet.

Le RSA, c'est un chiffrement asymétrique. C'est à dire que tu n'utilises
pas la même clé pour chiffrer et pour déchiffrer.

Si tu chiffres ton message avec ta première clé, puis avec ta seconde
clé, tu obtiens ton message original. Dans l'autre sens, ça marche
aussi, si tu chiffres ton message avec ta seconde clé, puis avec ta
première clé, tu obtiendras aussi ton message original.

Tu peux donc avoir une clé publique que tu donnes à tout le monde et une
clé secrète que tu es le seul à connaître.

Tu peux donc l'utiliser de deux façons, si tu chiffres ton message avec
ta clé privé, n'importe qui peut le déchiffrer. Celui qui le déchiffre
est sûr que tu en es l'auteur. Quelqu'un qui veut te faire parvenir un
document secret peut utiliser ta clé publique, tout le monde pourra voir
ton document chiffré, mais tu seras le seul à pouvoir savoir ce qu'il
contient.

Pour que cette méthode puisse être fiable, il faut donc qu'à partir de
la clé publique, d'un message en clair et d'un message chiffré, il soit
impossible de trouver la clé privée. S'il faut cent milles milliards
d'années à l'ensemble des ordinateurs de la planète pour trouver ta clé
secrète, tu peux considérer que la méthode est sûre.

En gros, au niveau de l'algorithme, tu commences par choisir deux
nombres premiers, puis tu fais des calculs dessus pour obtenir ta clé
privée et ta clé publique.

La faiblesse réside dans le fait que le produit des deux nombres
premiers est public. Il ne faut donc pas que quelqu'un puisse factoriser
la produit des nombres premiers, sinon, il peut faire les calculs pour
trouver la clé privée. Par exemple, si ton produit est 35, tu dois
réussir à trouver 5 et 7 de tête. si ton produit est 899, ça devient un
peu plus dur de trouver 29 et 31, mais avec une calculatrice , ça se
fait bien. Si ton produit fait 758 bits (donc 232 chiffres pour
l'exemple donné par le boulet initial), alors, il faut de très gros
moyens pour y arriver, mais c'est maintenant du domaine du possible.

Est-ce que cette nouvelle signifie que n'importe quelle message chiffré
avec une clé RSA de 768 bits peut être déchiffré sans avoir le mot de
passe à condition d'avoir suffisament d'ordinateurs et deux ans devant soi
?

Si tu as compris ce que j'ai écrit au dessus, tu dois pouvoir répondre à
ta question. Sinon, c'est que je n'ai pas été clair.

Parce que j'ai l'impression que quand on parler de "casser" un algorithme,
ça ne signifie pas forcément être capable de le déchiffrer sans clé.

Cela peut être de trouver la clé, mais en trouvant une faiblesse dans
l'algorithme.

Par exemple, si tu as un code secret de 20 chiffres, tu as 10^20 (un 1
suivi de 20 zéros) combinaisons possibles. Si l'algorithme est parfait,
il faut essayer toutes les combinaisons possibles afin de trouver le
code secret. Si le code secret est 11111111111111111111 alors, tu vas
trouver le code secret très rapidement, mais ce sera la clé qui sera
cassée, pas l'algorithme.

Si, au contraire, ton algorithme présente une faiblesse, par exemple,
s'il te dit si tu te trompes à chaque fois que tu vas rentrer un
chiffre. Dans ce cas, tu n'a besoins que de 10 essais pour trouver le
premier chiffre, puis de 10 autres essais pour trouver le second, etc.
Ce qui fait que tu n'as plus qu'à essayer 10*20 = 200 chiffres (au lieu
des 10^20 nombres de 20 chiffres) pour trouver le code secret.

Dans ce cas, l'algorithme est cassé. Tu as trouvé la clé, mais sans
avoir besoin d'essayer toutes les combinaisons possibles.

Le Mon, 11 Jan 2010 23:40:11 +0100, Stéphane CARPENTIER
<stef.carpentier@gratuit.fr.invalid> a écrit :

Ok, c'est très clair, je pense avoir compris.
Chiffrement asymétrique, je comprends à peu près le princ ipe, j'ai utilisé
PGP à une époque, même si j'avoue que je ne savais mê me pas que RSA était
asymétrique. D'ailleurs, si mes souvenirs sont bons, PGP utilisait deux
algos différents pour la clé publique et la privée, non ?

Par contre

Tu peux donc l'utiliser de deux façons, si tu chiffres ton messag e avec
ta clé privé,

Je croyais que la clé privée ne pouvait servir qu'à dé chiffrer.
Pour moi clé privée = clé; clé publique=cadenas.

Pour que cette méthode puisse être fiable, il faut donc qu'à   partir de
la clé publique, d'un message en clair et d'un message chiffré , il soit
impossible de trouver la clé privée.

Ok, donc là si j'ai bien pigé, ils ont réussi à trou vé la clé privée à
partir de la publique, donc tous les messages qui ont été chif frés avec
cette clé peuvent être déchiffrés.
Un truc que je voudrais vérifier.
A l'époque où j'utilisais PGP, il était bien précisà © en effet de ne jamais
donner sa clé privé à qui que ce soit, et je comprends bi en pourquoi. Même
en même temps, pour déchiffrer un message, j'étais bien o bligé de rentrer
mon mot de passe, ça pouvait se déchiffrer automatiquement jus te parce que
j'avais la clé privée sur mon ordi.
Alors comment est-ce possible de déchiffrer un message juste avec c lé
privé + publique mais sans mot de passe ?

Cela peut être de trouver la clé, mais en trouvant une faibl esse dans
l'algorithme.

Par exemple, si tu as un code secret de 20 chiffres, tu as 10^20 (un 1
suivi de 20 zéros) combinaisons possibles. Si l'algorithme est pa rfait,
il faut essayer toutes les combinaisons possibles afin de trouver le
code secret. Si le code secret est 11111111111111111111 alors, tu vas
trouver le code secret très rapidement, mais ce sera la clé qui sera
cassée, pas l'algorithme.

Si, au contraire, ton algorithme présente une faiblesse, par exem ple,
s'il te dit si tu te trompes à chaque fois que tu vas rentrer un
chiffre. Dans ce cas, tu n'a besoins que de 10 essais pour trouver le
premier chiffre, puis de 10 autres essais pour trouver le second, etc.
Ce qui fait que tu n'as plus qu'à essayer 10*20 = 200 chiffres (au lieu
des 10^20 nombres de 20 chiffres) pour trouver le code secret.

Dans ce cas, l'algorithme est cassé. Tu as trouvé la clé , mais sans
avoir besoin d'essayer toutes les combinaisons possibles.

Ok, c'est exactement ce que je pensais "casser" peut signifier "réd uire le
temps de recherche", donc passer de 1 milliard d'années de recherch e à 1
million d'années et l'algo est "cassé".

Merci pour tout.
--
Envoyé avec l’innovant client de messagerie Opera Mail :
http://www.opera.com/mail/

Bonsoir,

passage wrote:

Je croyais que la clé privée ne pouvait servir qu'à déchiffrer.
Pour moi clé privée = clé; clé publiqueÊdenas.

Non non, c'est assez élégant en fait: il y a une espèce de "symétrie"
dans l'asymétrie, en quelque sorte: chaque clef peut chiffrer et déchiffrer.

On peut alors se demander: mais quel est l'intérêt de chiffrer un
message avec une clef privée, s'il peut être déchiffré illico par la
clef publique correspondante, qui par définition, est connue de tous (ou
tout au moins du plus grand nombre possible) ? Eh bien tout simplement,
si quelqu'un arrive à déchiffrer un message avec *votre* clef publique,
c'est qu'il a été chiffré avec *votre* clef privée, que vous êtes le
seul à connaître ! Vous venez donc d'authentifier la provenance du
message (de le signer, en quelque sorte).

Ok, donc là si j'ai bien pigé, ils ont réussi à trouvé la clé privée à
partir de la publique, donc tous les messages qui ont été chiffrés avec
cette clé peuvent être déchiffrés.

Disons qu'ils ont trouvé la clef privée correspondant à la clef publique
qu'ils avaient (et pas "à partir de" ;-) ) puisqu'il s'agit d'une
attaque sur la clef elle-même, par recherche exhaustive, et non une
attaque sur une faiblesse du protocole (si j'ai bien tout suivi du moins).

A l'époque où j'utilisais PGP, il était bien précisé en effet de ne
jamais donner sa clé privé à qui que ce soit, et je comprends bien
pourquoi. Même en même temps, pour déchiffrer un message, j'étais bien
obligé de rentrer mon mot de passe, ça pouvait se déchiffrer
automatiquement juste parce que j'avais la clé privée sur mon ordi.
Alors comment est-ce possible de déchiffrer un message juste avec clé
privé + publique mais sans mot de passe ?

Le mot de passe que vous entrez est justement là pour déchiffrer à la
volée (au moment de s'en servir) votre clef privée, qui est nettement
moins simple à retenir qu'un mot de passe et reste donc, dans beaucoup
de cas, présente sur un support magnétique ou une clef USB ou autre,
mais sous forme chiffrée également (souvent avec... un algorithme
symétrique genre 3DES ou autre)...

D'où un autre niveau d'attaque possible dans la pratique: vous avez
intérêt à utiliser, pour chiffrer et donc protéger cette clef privée, un
mot de passe "béton". On parle d'ailleurs plutôt de "passphrase" dans un
tel cas, et non de "password". ;-)

Pour répondre à votre question: si vous arrivez à trouver la clef privée
par un autre moyen, vous n'avez pas besoin du mot de passe...

Cordialement,

Bruno