Forum de mathématiques - Bibm@th.net

jujul3p

Membre

Inscription : 09-01-2013

Messages : 4

Cryptologie RSA, déchiffrage par table

Bonjour à tous,

Suite à quelques recherches sur le net, je me suis renseigné sur la criptologie RSA.

Je pense en avoir relativement bien saisi les tenants et aboutissants mais je me pose une question :

Les clefs publiques permettent de créer quasi instantanément le message chiffré ; pourquoi, plutôt que de chercher à retrouver la clef privée, ne pas créer une table de correspondance entre messages clairs et messages chiffrés ?

En rentrant toutes les valeurs possibles entre 0 et la clef publique dans l'algoritme de cryptage et en en enregistrant les valeurs cryptées en sortie, on obtiendrait donc très rapidement un tableau de correspondance entre les valeurs claires et cryptées.

Décripter un message en partant des valeurs cryptées en utilisant le tableau de correspondance serait alors possible et relativement facile non ?

Qu'en pensez-vous ?

Merci d'éclairer ma lanterne !

Jujul3p

Dernière modification par jujul3p (09-01-2013 16:36:47)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Cryptologie RSA, déchiffrage par table

Salut à tous,

Je ne devrais pas m'aventurer sur ton terrain, parce que là, je franchis les limites de mon domaine, qui est (pardon de toujours me répéter) la cryptologie de papa, et le RSA, c'est du "pas papa", comme dirait ce cher Gaston Lagaffe.

Mais j'ai remarqué que tu étais inscrit d'aujourd'hui. Un membre tout frais comme un oeuf à la coque, il faut lui souhaiter la bienvenue, et je serais heureux d'être le premier à le faire, si personne ne vient me couper l'herbe sous le pied.

Bon ! Le RSA, c'est le tout début du "pas papa", ce qui fait que j'en connais au moins le principe (rien de plus, d'ailleurs).

Tu dis : "En rentrant toutes les valeurs possibles entre 0 et la clef publique...". Si mes souvenirs sont bons, la clé publique, c'est le produit de deux facteurs premiers et la sécurité du procédé réside dans la quasi-impossibilité de factoriser les très grands nombres, spécialement s'ils n'ont que deux diviseurs premiers, ces deux facteurs constituant la clé privée.

Or, je crois que, dans l'état actuel de performances en matière de factorisation, cette quasi-impossibilité commence pour des nombres comportant, au strict minimum, plus de cent chiffres. Alors, appliquer toutes les valeurs possibles entre zéro et une clé publique, ça ne me semble pas être une solution possible.

Si j'ai dit des sottises, n'hésitez pas (tous) à me le faire savoir : je ne suis pas susceptible et il ne me reste plus tellement de temps pour enrichir mes connaissances.

Dernière modification par nerosson (09-01-2013 15:05:48)

jujul3p

Membre

Inscription : 09-01-2013

Messages : 4

Re : Cryptologie RSA, déchiffrage par table

Bonjour et merci de ta réponse.

En fait, je ne cherche pas à casser le RSA en trouvant la clef privée (en factorisant la clef publique) mais je me demande s'il est possible de réaliser une table de correspondance entre valeurs non chiffrées et valeurs chiffrées.

Je m'explique :

Tout utilisateur connait les clefs publiques et peut donc crypter des valeurs.

Un exemple au pif une fois le criptage (par clefs publiques) réalisé :
1=>1
2=>4
3=>5
4=>17
5=>12
...

Chercher à retrouver les valeurs en clair en partant des valeurs cryptées et en n'utilisant que les clefs publiques est (sauf factorisation) impossible. On est tous d'accord.

Cependant en réalisant un tableau comme indiqué ci-dessus, rien n'empèche à un utilisateur (malveillant) de décrypter les valeurs cryptées en valeurs en clair.

(Si je lis 17 5 1 12, en utilisant le tableau créé ci dessus, je peux "décrypter" en 4 3 1 5).

Mon explication me parait claire mais je n'utilise peut-être pas le bon vocabulaire. Veuillez m'en excuser !

En tout cas, merci encore de vos lumières !

Dernière modification par jujul3p (09-01-2013 16:35:54)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Cryptologie RSA, déchiffrage par table

Salut à tous,

@jujul3p

Pour moi, le terrain est de plus en plus mouvant, parce que je connais la théorie du RSA, mais pas sa mise en oeuvre pratique.

Cependant, il ne me parait pas possible que les équivalences clair-crypto que tu auras obtenues à l'aide d'un message que tu auras chiffré toi-même soient utilisables pour décrypter un autre crypto, parce qu'on se trouverait alors en présence d'une sorte de substitution à représentation unique.

jujul3p

Membre

Inscription : 09-01-2013

Messages : 4

Re : Cryptologie RSA, déchiffrage par table

Bah oui, c'est bien ce qui me gène un  peu (beaucoup)...

Effectuer une substitution me parait un peu logique puisque si je crypte deux fois le même message avec les mêmes clefs publiques j'aurai deux fois le même message crypté en résultat...

Selon ma compréhension du système et tout ce que j'ai trouvé sur le système RSA, rien n'explique ce qui empèche cette substitution.

Il doit pourtant y avoir quelque chose qui cloche dans ma logique mais là, je ne vois pas quoi !!!

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Cryptologie RSA, déchiffrage par table

Bonjour Jujul3p,

   Ce que tu proposes n'est pas réalisable, car la clé publique est toujours un très grand entier (de l'autre de 1000 chiffres par exemple). Il est donc impossible
de générer une table de correspondance avec toutes les entrées en clair, même pour les ordinateurs actuels (d'ailleurs, si le nombre de chiffres est assez grand, on doit dépasser le nombre d'atomes dans l'univers).
  En revanche, tu as raison, un des inconvénient du chiffre RSA est que deux textes clairs identiques produiront toujours le même message chiffré.
Il existe d'autres méthodes de chiffrement à clé publique, comme le chiffre Elgama par exemple, pour lequel ce n'est pas le cas.

Fred.

jujul3p

Membre

Inscription : 09-01-2013

Messages : 4

Re : Cryptologie RSA, déchiffrage par table

Bon bon bon...

La méthode de génération de table de correspondance est bloquée par le nombre d'entrées à chiffrer, c'est aussi simple que ça...

Je ne sais pas trop quelles sont les capacités d'un ordinateur en la matière mais ça montre quand même une relative faille du système non ?
En faisant une table aussi grande que possible on pourrait quand même "casser" un (très très) petit pourcentage de messages.

En tout cas, merci à vous deux pour le temps passé à réfléchir à mon problème et à me répondre...

Mine de rien ça faisait une bonne semaine que ça me turlupinait !

Jujul3p

douli

Membre

Inscription : 02-12-2012

Messages : 1

Re : Cryptologie RSA, déchiffrage par table

Salut !

Tu viens d'inventer la recherche exhaustive !

En cryptologie, le postulat de base c'est qu'un code est faible s'il n'est pas cassable en temps polynomial. (et donc on conjecture P != NP).

Pour faire la table de toutes les clés possibles, si n est de l'ordre de 2^k, alors la recherche exhaustive se fera en 2^k. k est le paramètre de sécurité, et c'est un polynôme en k qu'il faudrait obtenir pour casser le code.

RSA n'est pas sécurisé dans de nombreux cas (cryptanalyses à base de réseaux euclidiens, ...), c'est pourquoi la vraie implémentation du RSA diffère un peu de celle dans les bouquins de base... Lis le stinson si tu veux en savoir plus !

Pour finir, ta technique de correspondance clair chiffré ne marcherait pas avec le vrai RSA. En effet, on rajoute de l'aléatoire pour avoir une propriété bien sympa :
connaissant M0, M1 deux messages clairs (choisis par l'attaquant) et C le chiffré de M0 ou M1 (tirage aléatoire), un attaquant n'est pas capable de savoir, en temps polynomial et avec probabilité non négligeable, si C est le chiffré de M0 ou M1...

On appelle cela la propriété d'indistinguabilité contre les attaques à clairs choisis. Tous les systèmes de chiffrement sont implémentés avec cette propriété !

nerosson, quand as-tu arrêté la crypto ? RSA date des années 80, pour moi c'est RSA la crypto à la papa :D

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Cryptologie RSA, déchiffrage par table

Salut à tous,

@douli,

J'ai pris ma retraite en 1983. Le RSA existait déjà en tant que "découverte", mais je doute qu'il ait été déjà exploité à ce moment-là. En outre, on entre avec lui dans l' ère où l'informatique devient indissociable de la cryptologie.

C'est pour cela que je le considère comme la  barrière terminale de mon modeste savoir. Ce qui d'ailleurs explique l' extrème prudence de mes interventions dans cette discussion.

Borne prestigieuse, puisque je considère que le principe du chiffrement à clé publique constitue la plus fantastique découverte de toute l'histoire de la cryptologie depuis l'antiquité.

Dernière modification par nerosson (05-02-2013 14:12:40)