Attaques à clair choisi sur RSA

bonjour à tous,

je suis débutant et je me suis dejà un peu renseigné sur le fonctionnement de RSA.
Une chose m'échappe encore, comment se fait il que RSA ne soit pas si vulnérable aux attaques à clair choisi ? sachant que l'on peut crypter comme on veut des données, on pourrai arriver à "retomber" sur des entiers cryptés et donc connaitre leur clair ?
La seule possibilité de l'éviter que je vois serait de choisir les entiers cryptés assez grands (mais toujours <n bien entendu), est ce cela ?
Car si on choisit de crypter les entiers de 1 à 26, ce sera un jeu d'enfant de retrouver le texte d'origine, quelque soit la clé...

Je me trompe ?

Merci d'avance :)

Nilss

Bonjour,

Citation:

---

Envoyé par Nilss

bonjour à tous,

je suis débutant et je me suis dejà un peu renseigné sur le fonctionnement de RSA.
Une chose m'échappe encore, comment se fait il que RSA ne soit pas si vulnérable aux attaques à clair choisi ? sachant que l'on peut crypter comme on veut des données, on pourrai arriver à "retomber" sur des entiers cryptés et donc connaitre leur clair ?
La seule possibilité de l'éviter que je vois serait de choisir les entiers cryptés assez grands (mais toujours <n bien entendu), est ce cela ?
Car si on choisit de crypter les entiers de 1 à 26, ce sera un jeu d'enfant de retrouver le texte d'origine, quelque soit la clé...

Je me trompe ?

Merci d'avance :)

Nilss

---

Non, crypter en RSA avec de petits nombres revient à permettre le crack en quelques millisecondes (ou secondes, heures, etc... si on augmente la taille).

Tout le monde sait que la sécurité de RSA (et d'autres basés sur le même genre de problème) est basée sur le temps prohibitif nécessaire pour décomposer la clé publique en ses 2 facteurs premiers (qui doivent tout les 2 être assez grands).

Si je comprend bien, lorsque l'on dit que RSA doit être utilisé avec de grands nombres, cela signifie que les données chiffrées doivent egalement être grandes ?

Bonjour,

Citation:

---

Envoyé par Nilss

Si je comprend bien, lorsque l'on dit que RSA doit être utilisé avec de grands nombres, cela signifie que les données chiffrées doivent egalement être grandes ?

---

Non, les deux ne sont pas liés.

La necessité d'utiliser de grands nombres pour la clé de crytage est due au fait que la clé est générée par multiplication de 2 nombres premiers, et que la connaissance de ces 2 nombres "racines" permet de décoder le message.
Or, la décomposition d'un nombre en ses facteurs premiers est en même temps triviale, car les algorithmes nécessaires sont bien connus, et actuellement impossible en un temps de calcul raisonnable, si le nombre et ses facteurs premiers sont assez grands.

ps : pour ceux qui connaissent le problème, je précise tout de suite que je connais les algorithmes "rapides" pour cette décomposition, ça évitera qu'on fasse la remarque.

Rebonsoir,

Merci, mais en fait je sais dejà cela, ma question portait plus sur les attaques à clair choisi que sur la factorisation de n. Je cherche simplement à comprendre comment éviter ce type d'attaque (c'est pour cela que je parlais d'utiliser de grands nombres dans les données à crypter pour qu'on ne puisse pas "tomber dessus" en essayant de crypter simplement)

Nilss

Bonjour,

On peut toujours "tomber dessus" une clé de cryptage, mais si elle est bien faite, c'est si peu probable qu'on estime qu'on peut négliger cette éventualité.

Si ceci ne répond pas à ta question, je ne saisis pas bien ce que tu désires.

Je ne suis pas sur d'avoir été clair, alors je vais essayer de détailler un peu plus que je ne l'ai fait :p

Clé publique : (n,e)
Clé privée : (n,d)

On suppose qu'on ne connait que la clé publique, et qu'on a un texte crypté avec cette meme clé qu'on aimerait bien décrypter.
mettons que ce "texte", en fait constitué de chiffres pour simplifier, contienne le chiffre "5423".
C'est à dire que 5423 serait le resultat du cryptage d'un nombre que l'on ignore.

L'attaque dont je parle consisterait à crypter 1 à 1 les entiers entre 0 et n-1.
Si par miracle on tombe sur 5423, on saura le décrypter vu qu'on saura quel est son antécédent.

Donc en fait, ma question serait "comment éviter ça ?"
(et la solution que je proposais serait de crypter des entiers tellement grands, qu'on ne pourrai pas les atteindre en cryptant un à un les entiers )

Voila :mrgreen:

Nilss

Bonjour,

Il est évident que dans une attaque à clair choisi, si le clair correspond au message recherché alors la sécurité ne tient plus.

Pour éviter cela on peut ajouter un "sel", c'est à dire un nombre aléatoire dont il ne sera pas tenu compte dans le déchiffrement, mais qui permet d'avoir des messages chiffrés différents pour un même message clair.

Mais de toute façon on utilise rarement RSA pour chiffrer les données à protéger directement. On se contente en général de chiffrer une clef de session aléatoire en RSA, puis le message est chiffré avec cette clef de session par un algorithme de chiffrement à clef privé (AES, DES, Blowfish...).

Bonjour,

Ton problème revient à explorer de manière exhaustive toutes les possibilités, ce qui devient très rapidement inutilisable quand la longueur du message augmente, donc dans ton cas, quand la valeur du nombre augmente (et ton exemple implique déjà d'avoir une idée du contenu, ce qui n'est pas gagné d'avance).

Evidemment, c'est applicable quand le message codé est court, et même très court, sinon bonjour le temps de calcul... astronomique.

Dans mon groupe, pour tout message de moins de 2 Ko, on utilise un générateur aléatoire pour ajouter des données à la fin, en ajoutant également la longueur effective du message, etc..., tu vois ce que je veux dire.

Rebonjour,

Tout d'abord merci de vos réponses.

Sovitec, peux-tu me montrer sur un exemple concret comment tu utilises ce "sel" ? (à quoi l'ajoute-t-on précisement ? , de plus, je ne comprend pas comment on peut ne pas en tenir compte dans le déchiffrement, enfin ça c'est parce que j'ai pas compris la méthode :p)

Thewho : voila c'est cela, tu dois comprendre maintenant pourquoi je parlais d'utiliser de grands entiers également dans le message à chiffrer.
Pourquoi serait ce plus facile pour un message "court" ? D'apres ce qu'on a dis, il suffirait de rendre assez grands les entiers qui representent le message, comme ça, on aurai du mal à tomber dessus (sauf coup de chance si on commence la recherche pas trop loin).

Voila :)

PS : J'ai une derniere question, pourquoi crypter au RSA une clé issue d'un autre algo de cryptage ? Cela ne revient pas à crypter directement par ce second algorithme ? (donc s'il a des faiblesses que RSA n'a pas, il pourra etre attaqué quand meme...)

Bonjour,

Citation:

---

Envoyé par Nilss

Thewho : voila c'est cela, tu dois comprendre maintenant pourquoi je parlais d'utiliser de grands entiers également dans le message à chiffrer.
Pourquoi serait ce plus facile pour un message "court" ? D'apres ce qu'on a dis, il suffirait de rendre assez grands les entiers qui representent le message, comme ça, on aurai du mal à tomber dessus (sauf coup de chance si on commence la recherche pas trop loin)

---

J'avoue que je ne comprends pas de quoi tu parles avec tes entiers plus ou moins grands qui "représentent le message".

D'où viennent-ils ? Que représentent-ils ? S'agit-il des nombres correspondant à une clé RSA ?

Et bien, si l'on souhaite crypter un texte, il faut commencer par assigner un entier à chaque lettre, pour pouvoir calculer l'image de cet entier par la fonction de cryptage RSA.

(evidemment apres on code par bloc de plusieurs lettres... c'est peut etre ça d'ailleurs qui rendrait l'attaque à clair choisi difficile : en utilisant des blocs assez grands, et c'est aussi peut etre de ça que tu parlais dans ton précédent message)

Citation:

---

Envoyé par Nilss

Sovitec, peux-tu me montrer sur un exemple concret comment tu utilises ce "sel" ? (à quoi l'ajoute-t-on précisement ? , de plus, je ne comprend pas comment on peut ne pas en tenir compte dans le déchiffrement, enfin ça c'est parce que j'ai pas compris la méthode :p)

---

La méthode exposée par Thewho est un exemple de "sel" (ou "salt" en anglais si tu veux te renseigner sur un moteur de recherche).

Citation:

---

Envoyé par Nilss

Thewho : voila c'est cela, tu dois comprendre maintenant pourquoi je parlais d'utiliser de grands entiers également dans le message à chiffrer.
Pourquoi serait ce plus facile pour un message "court" ? D'apres ce qu'on a dis, il suffirait de rendre assez grands les entiers qui representent le message, comme ça, on aurai du mal à tomber dessus (sauf coup de chance si on commence la recherche pas trop loin).

---

Chiffrer chaque lettre par un "grand entier" ressemble plus à de la "sécurité par obscurité" qu'autre chose, si on connaît la table d'association lettre<->grand entier alors il ne coûte pas beaucoup plus cher de déchiffrer ce message que l'association lettre<->code ASCII.

Citation:

---

Envoyé par Nilss

PS : J'ai une derniere question, pourquoi crypter au RSA une clé issue d'un autre algo de cryptage ?

---

RSA est très lent dès que le message est un peu long. On préfère donc utiliser un algo rapide pour chiffrer les données, puis utiliser RSA pour transmettre la clef utilisée lors de ce chiffrement.

Citation:

---

Envoyé par Nilss

Cela ne revient pas à crypter directement par ce second algorithme ? (donc s'il a des faiblesses que RSA n'a pas, il pourra etre attaqué quand meme...)

---

Oui, cela revient à chiffrer par le second algorithme, et ajoutera donc les faiblesse de cet algorithme à ceux de RSA. RSA ne sert dans ce cas qu'à partager la clef de session.

PS: bien que crypter soit passé dans le langage populaire, les spécialistes préfèrent parler de chiffrer.

Bonjour,

Citation:

---

Envoyé par Nilss

Et bien, si l'on souhaite crypter un texte, il faut commencer par assigner un entier à chaque lettre, pour pouvoir calculer l'image de cet entier par la fonction de cryptage RSA

---

Comme l'a précisé sovitec, ça ne sert à rien. Tu ne fais que te compliquer la tâche et augmenter la taille du message à crypter (et comme l'a également précisé sovitec, RSA est lent).

Pour en revenir à tes soucis de sécurité, "l'attaque en clair" comme tu l'appelles nécessiterait tellement de temps, même pour un message assez court, que je ne pense pas que quelqu'un sain d'esprit s'amusera à essayer, car c'est voué à l'échec.
(Amuse toi à calculer le nombre de combinaisons possibles pour un message de n caractères, avec n allant de 1 à autant que tu veux, même si on limite chaque caractère à être une lettre ou un chiffre + les signes de ponctuation.)

Citation:

---

Envoyé par Nilss

(evidemment apres on code par bloc de plusieurs lettres... c'est peut etre ça d'ailleurs qui rendrait l'attaque à clair choisi difficile : en utilisant des blocs assez grands, et c'est aussi peut etre de ça que tu parlais dans ton précédent message)

---

Bien entendu, ça fait partie du principe du RSA.
Si je comprends bien, tu envisageais de crypter caractère par caractère ?
D'où t'es venue cette idée ? Dans quel but ?

Citation:

---

Envoyé par sovitec

PS: bien que crypter soit passé dans le langage populaire, les spécialistes préfèrent parler de chiffrer.

---

Oui, mais utiliser le mot crypter n'est pas faux.

Bonjour,

Citation:

---

Envoyé par thewho

Bien entendu, ça fait partie du principe du RSA.
Si je comprends bien, tu envisageais de crypter caractère par caractère ?
D'où t'es venue cette idée ? Dans quel but ?

---

Eh bien en fait , étant débutant, c'est l'idée la plus naturelle qui m'est venue à l'esprit.

Etant en train de préparer un exposé, je me suis automatiquement limité au cas ou l'on souhaiterai chiffrer un texte quelconque. (Je fais donc abstraction du fait qu'on l'utilise surtout pour crypter des clés, ce que je trouve en fait bizzare car si l'on sait transmettre une clé privée RSA de maniere confidentielle, on pourrai directement le faire pour une clé d'un autre algorithme... à moins que ce soit un probleme de taille)

Tu disais qu'assigner à chaque lettre un nombre était inutile et ne ferait qu'augmenter la taille du texte à chiffrer, mais alors, comment procéder pour realiser un tel cryptage ? (celui d'un texte, directement).
Il faut bien disposer de chiffres à un moment ou à un autre si l'on veut récuperer un resultat par RSA.

Nilss

Citation:

---

Eh bien en fait , étant débutant, c'est l'idée la plus naturelle qui m'est venue à l'esprit.

---

C'est effectivement assez naturel en première approche, mais présente les vulnérabilités que tu as remarquées. Donc en pratique on tronçonne le message on morceaux de taille fixe (de la taille de la clef il me semble ?) pour eviter ce problème. Et si on n'a pas assez de données pour en remplir un on bourre avec des données aléatoires afin de brouiller les pistes.

Citation:

---

ce que je trouve en fait bizzare car si l'on sait transmettre une clé privée RSA de maniere confidentielle

---

En fait c'est tout l'intéret du RSA : on ne transmet pas la clef privée qui sert au décodage, et ça tombe bien car c'est transmettre une clef secrète qui pose généralement problème. Les deux interlocuteurs échangent leurs clefs publiques de manière... publique (pas besoin de se cacher), ce qui permet à chacun de chiffrer des messages que seul l'autre pourra déchiffrer.

Mais, comme les chiffrages à clef publique sont plus faibles que ceux à clef privée, on est obligée d'avoir des clefs très grandes donc des calculs très lourds. Alors on profite du canal sécurisé via clefs publiques (RSA par ex) pour échanger des clefs privées en toute sécurité et voilà.

Citation:

---

Tu disais qu'assigner à chaque lettre un nombre était inutile et ne ferait qu'augmenter la taille du texte à chiffrer, mais alors, comment procéder pour realiser un tel cryptage ? (celui d'un texte, directement).
Il faut bien disposer de chiffres à un moment ou à un autre si l'on veut récuperer un resultat par RSA.

---

En fait il y a méprise sur le concept. En crypto, quand on parle d'assigner des nombres à des lettre on fait généralement référence à des nombres choisis aléatoirement afin de chiffrer le message (les couples nombre-lettre forment alors la clef). Simple mais peu efficace.
En info c'est une convention qui sert à stocker du texte dans la mémoire d'une machine qui ne traite que des 0 et des 1. Par exemple le code ASCII dit que la lettre 'A' correspond à 65. Mais en mémoire les deux sont représentés pas '1000001'.
Je pense que tu faisais référence à cet aspect là.

Ce n'est pas réellement une difficulté car il suffit d'interpréter les lettres comme des nombres. En fait cela peut s'appliquer à tout type de données. Si tu codes par morceaux de 64 bits (par exemple), il n'y a qu'à découper les données en morceaux de 64 bits sans se soucier de ce qu'ils représentent à l'origine (par exemple huit lettres d'un texte en ASCII, huit pixels d'un bitmap 8 bit ou 2 pixels et deux tiers pour une image en 34bits :mouarf:). On peut interpréter ces séries de bits comme on le souhaite, y compris comme des entiers positifs inférieurs à 2^64, et les chiffrer (au sens crypter hein) un à un.

Bonjour,

Voilà, Sivrît a répondu pour moi

Merci à vous tous.
Je crois que j'ai compris. Pour conclure, je parlais effectivement de représenter les lettres par des nombres comme moyen pratique pour pouvoir crypter par RSA.
Ce que je viens de comprendre (arretez moi si je me trompe encore :)), c'est que finalement, peu importe la représentation numérique que l'on donne aux nombres avant de les crypter (ASCII par exemple comme tu disais Sivrît), du moment que l'on effectue des regroupements assez grands

En effet, au debut je me disais que si on cryptait caractere par caractere, et qu'on utilisais les tables ASCII comme représentation des lettres, le cryptage ne tiendrait pas la route, car il suffirait par exemple de crypter par la clé publique les entiers jusqu'a k (ou k est le dernier code ASCII, que j'ai oublié :p). C'est ce qui a motivé l'ecriture de ce post.
Mais apparement , la solution semble bel est bien etre celle des regroupements, ce qui donnerait des entiers d'une taille de l'ordre de celle de la clé (tres grande donc...) à crypter, et il serait quasiment impossible de tomber dessus par une attaque à clair choisi .

Voila ce que j'ai compris, corrigez moi si je me suis trompé quelque part :)
Merci encore.

Nilss.

Bonjour,

C'est bon.