Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 10-07-2008 19:08:47
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
RSA besoin de réponses
Bonjour tous le monde,
J'ai trois question concernant l'algorythme de cryptage RSA:
-Si un lettre F est crypté selon le systeme RSA en M, n'est il pas alors aisé de casser RSA grace a une simple analyse des frequences?? Si non, comment RSA brouille les fréquences des lettres?
-Si, la formule du cryptosysteme RSA est la suivante: C= Me (modN)
ou e=3 et N=14 ; trouver M parait plus simple que de trouver les deux nombres premiers qui se multipli pour donner N=14 (soit 7*2=14).
Je reviens a mes moutons; C= Me (mod N)
C= M éxposant 3 (modulo 14)
Alice code une lettre a Bernard, cette lettre est D= 4 (place dans l'alphabet)
Elle code: 4*4*4 (mod 14)
=64 (mod 14)
=8
=H (selon la place dans l'alphabet)
Alice envoit donc la lettre H a Bernard.
Mais Eve intercepte le message coder H , elle peut donc en conclure que M*M*M (mod 14)=8
Elle peut alors compter en tournant en rond en modulo 14 (1,2,3,4...jusque a 14) , apres 14, elle revient a 1 et continu comme dans la parenthese precedente. Mais lorsque que Eve compte; elle prends le soin de noter le numero qu'elle prononce dés qu'elle passe devant 8. En suivant ce résonnement, on obtient; 22 puis 36 puis 50 puis 64 etc.. Eve fait ensuite la manipulation suivante: 2*2*2=8 et 8 n'est pas égual 22 ni 36 ni 50 ni 64.
Elle essaye alors avec 3; sa donne 3*3*3=27 et 27 n'est pas égual a 22 ni 36 ni 50 ni 64.
Elle essaye ensuite avec 4, j'obtient 4*4*4=64 et 64 n'est pas égual a 22 ni 36 ni 50 MAIS 64!!
Eve peut donc trouver M! et M=4 donc M=D
-admettons que Alice envoi a Bernard le message " JE T'AIME" crypté selon RSA en "LYFQUQN ", Eve intercepte le message tout en se doutant qu'il ya une liaison entre Alice et Bernard; elle en deduit qu'il ya surement marqué "JE T'AIME". Elle décide alors de crypté le message "JE T'AIME" selon la clef public de Bernard pour voir si le message trouvé correspond au message crypté par Alice. Si c'est le cas, Eve obtient la certitude que Alice a envoyer "JE T'AIME" a Bernard.
Pourquoi, dans aucun livre site internet..personne ne parle de ces failles??
Voila messieur les cryptanalystes ^^ , j'ai essayé d'etre le plus clair possible, j'attend de vos réponses! Merci!
« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »
Hors ligne
#2 11-07-2008 15:45:08
Re : RSA besoin de réponses
Bonjour,
Je suis pas expert en RSA mais je peux apporter quelques explication mettant en doute tes idées pour le casser.
Question 1 : RSA n'est pas prévu pour chiffrer des lettres à la base mais des chiffres. Et même si l'on souhaite chiffrer des lettres, on va pas faire une conversion alphabétique ou ASCII de chaque lettre et les envoyer une par une. En effet on va traduire une série de lettre en ascii (par exemple) on les met bout à bout et on chiffre la chaine globale.
En général, le RSA sert a chiffrer des séquences courtes d'information (par exemple une clef partagée pour un futur algorithme symétrique permetant lui de chiffrer des flots de données). Ainsi tu risques de ne voir passer qu'une seule chaine de chiffre/caratère codée et il te sera difficile de faire une analyse de fréquence dessus.
Question 2 : tu fais ta démonstration sur des tous petits chiffres alors qu'il est bien admis que la sureté du rsa tient dans l'utilisation de très grands chiffres, ou il n'es pas techniquement possible de "bruteforcer" le code ;
Si ta clef est de l'ordre de 10^100 (ou plus) chiffres, tu auras du mal a mettre en place ton algorithme. De plus, ton explication ne portant que sur un exemple je pense qu'on peut facilement trouver.
De plus je doute sincèrement que l'équation M^e=Nx+C dans l'ensemble N² (c'est l'interprétation mathématique de ton raisonnement) ait une unique solution pour le couple (M,X) surtout lorsque les chiffres deviennent très grand.
Question 3 : tu utilises la encore une analyse de contenu qui n'est pas logique dans l'utilisation du RSA ; Meme si je t'aime fait partie du message il sera fondu dans le reste du message et sera donc chiffré relativement a ce qui l'entoure ; cela suppose par ailleurs que tu connaisse déja une partie de la transmission ce qui n'est pas le cas lorsqu'on échange (le plus souvent) des clefs aléatoires pour une future transaction de données symétrique (SSL par exemple).
En résumé, je pense que tes méthodes ne sont pas remises dans le contexte d'utilisation du RSA et que tu cherches des solutions a une échelle ou la factorisation de N est bien plus rapide et efficace pour cracker l'algo.
J'espère que mes explications t'auront aider a comprendre ; elles sont cependant elles aussi à remettre dans leur contexte et sont bien sur largement contextables. Si tu as des questions, n'hézite pas.
A+
Galdinx
PS : ton titre "besoin de réponse" n'est pas très adapté ; je doute que ce soit un réel BESOIN existentiel et on se doute que si tu postes une question c'est en l'attente de réponses
Hors ligne
#3 11-07-2008 15:57:48
- Barbichu
- Membre actif
- Inscription : 15-12-2007
- Messages : 405
Re : RSA besoin de réponses
Salut Golgup,
Je vais tenter de répondre à tes interrogations :
Pour ta toute première question : en pratique, on ne chiffre jamais le message directement car c'est beaucoup trop long, mais on chiffre seulement une clé (générée aléatoiremenent) qui sert à effectuer un chiffrement symétrique du message (AES ou 3DES). Cela répond du coup à la question 3.
De plus on ne fait pas du chiffrement lettre à lettre, mais d'entiers compris entre 0 et N-1. Ce qui fait qu'on ne peut pas faire des tests séparés pour chaque lettre.
Pour la deuxième question, tout est un problème de temps de calcul (et d'ordre de grandeur) Ta solution consiste à essayer le calcul M^e (mod N) pour tous les M possibles, c'est à dire pour tout les clairs possible : c'est une attaque en force brute et ça prend un temps exponentiel.
++
Barbichu
Hors ligne
Pages : 1