Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 03-11-2013 07:04:28

Emi !
Invité

RSA 2048 bit, bruteforcing et fonction de hachage

Hey tout le monde ! Aujourd'hui j'ai eu cours d'info a polytechnique ,et on a notamment parler de fréquence d'un processeur et des fonctions de hachage. ( MD5 et SHA-1)

J'ai énormément de mal a comprendre pourquoi ces fonctions la sont dites " inviolable" du faites dutemps que prendrai le cassage en brute forcing de la clée . On a aujourd'hui des processeur qui font , si j'ai tout compris 2milliard d'opération/seconde!

Je comprend bien que casser des clée de 2048 bits pour du RSA , c'est long , mais en se penchant plus prés , ( si j'ai tout compris, aprés je peut me planter) pour le RSA , on cherche a factoriser un nombre x qui a environ 600 chiffres par deux entier P et Q qui sont plus ou moins voisins en terme de taille et premier. Pour cela, ils nous faut tester donc tout les entiers premier entre 0 et racine de x. De plus , P et Q sont de taille voisines , donc tout les premier entre 0 et y , ou y un nombre de 250 chiffres sont a exclure. J'ai donc du mal a comprendre pourquoi les ordinateurs actuellent "rame" tellement sur ce genre de brute forcing

Pour les algorithme de hachage, sa reste aussi pour moi trés obscure. J'ai du mal a comprendre le concept des rainbow-table. J'ai compris qu'on se servait de ces table pour dire a l'ordi " hey regarde donc la dedans si le code y serait pas déja " mais j'ai du mal a comprendre pourquoi ces tables serait une "économie de place" par rapport a la méthode qui consiste a stocker toute les possibiliter et leurs MD5.


Merci pour vous future réponse =)

#2 03-11-2013 14:39:31

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : RSA 2048 bit, bruteforcing et fonction de hachage

Bonjour Emi !

Je n'ai jamais entendu l'expression "fonction inviolable" (mais je ne sais pas tout), on parle en général plutôt de "fonction à sens unique". Oui, on a des processeurs qui font quelques milliards d'opérations par secondes, mais peu importe le nombre de milliards en fait, comme nous allons le voir.

Pour commencer, une clé RSA 2048 bits, ça comporte 2048 chiffres binaires (par définition de bit) et donc environ 600 chiffres décimaux, mais oublions la base 10 si tu veux bien. Pour comprendre pourquoi exclure les petits nombres ne permet pas de gagner beaucoup de temps, commençons par un peu de dénombrement.

Il y a [tex]2^n[/tex] nombres de exactement n bits.
Il y a [tex]2^{n+1} - 1[/tex] nombres de au plus n bits.
Petite observation: il y a donc à peu près autant de nombres de exactement [tex]n[/tex] bits (il y en a [tex]2^n[/tex]) que de nombres de au plus [tex]n-1[/tex] bits (il y en a [tex]2^n - 1[/tex]).

D'après le théorème des nombres premiers, qui donne leur répartition asymptotique, il y a environ [tex]\frac{2^n}{n \cdot ln(2)}[/tex] nombres premiers de au plus [tex]n-1[/tex] bits et à peu près autant de nombres premiers de exactement [tex]n[/tex] bits. Donc éliminer les petits nombres premiers est encore négligeable.


Pour RSA:
Prenons un cas très défavorable pour la sécurité de la clé : supposons que l'on sache qu'elle est le produit de deux nombres premiers de exactement 1024 bits. C'est défavorable car on a décidé qu'on connaissait le nombre de chiffres des facteurs.
Des nombres premiers de 1024 bits, il y en a environ [tex]\frac{2^{1024}}{1024 ln(2)} \geq 2^{1014}[/tex]. En supposant que tu puisses énumérer la liste de ces nombres premiers sans calcul (ce qui est une hypothèse très forte), si tu veux tester tous les produits de nombres premiers de 1024 bits, il te faudra faire environ [tex]\frac{2^{1014} \times 2^{1014}}{2} = 2^{2027}[/tex] multiplications. Supposons que tu sois équipée d'un processeur 2048 bit i.e. faisant des opérations arithmétiques sur 2048 bit en un tic d'horloge (pour info, le processeur de ton ordinateur traites les nombres 32 bits ou 64 bits). Il te faut alors un tic d'horloge pour tester chaque possibilité, donc [tex]2^{2027}[/tex] tics pour essayer toutes les combinaisons.

Résumons :
Une année c'est un peu moins de [tex]2^{25}[/tex] secondes. Une machine moderne est cadencée à environ [tex]2^{32}[/tex] tics par seconde (approximation pour 4Ghz), sans compter les multi-coeurs. Tu as besoin de [tex]2^{2027}[/tex] tics pour tester toutes les combinaisons.

Avec [tex]2^{300}[/tex] (des milliards de milliards de ... de milliards de) machines modernes travaillant en parallèle sur la même clé il faudrait donc environ [tex]2^{2027 - 25 - 332} = 2^{1670}[/tex] années pour essayer toutes les combinaisons, ce qui est bien au delà du temps qui reste à l'univers d'après certaines théories.

Dans tout cela, il faut bien sûr garder à l'esprit qu'on parle d'attaque en force brute uniquement. Il y a d'autres approches (en particulier la factorisation en produit de nombres premiers), et il convient d'évaluer la sécurité d'un système en fonction des diverses approches connues.

Pour MD5:
Je te laisse dénombrer le nombre de possibilités à stocker en utilisant les méthodes ci-dessus. L'idée du rainbow table est de faire un compromis entre temps et mémoire en faisant des chaînes et en ne stockant que la première et la dernière entrée. L'occupation de la mémoire est alors réduite à "nombres de possibilités"/"taille moyenne des chaînes". Cela dit, je ne m'y connais pas beaucoup plus en rainbow-tables et MD5.

En espérant t'avoir éclairé,
A+


Barbichu

Hors ligne

#3 01-10-2014 21:46:57

DuduJ
Invité

Re : RSA 2048 bit, bruteforcing et fonction de hachage

Rien que ça ! en tout cas merci Barbichu pour toutes ces infos ça m’aura permis de comprendre l’intérêt d'un tel cryptage !

#4 18-10-2014 11:56:40

RastaRocco
Invité

Re : RSA 2048 bit, bruteforcing et fonction de hachage

Si je peux me permettre de compléter :
un des gros intérêts de ces fonctions à sens unique, c'est que le calcul de l'image se fait en temps linéaire, alors que le calcul de l'antécédent se fait en temps exponentiel. Ainsi, même si les processeurs gagnent en vitesse, on n'a besoin d'augmenter que de quelques bits la taille de la clé pour multiplier par 2^(quelques bits) la difficulté à casser le chiffrement.

Cependant, l'utilisation d'un algo de chiffrement prouvé difficile dans la théorie mathématique n'est pas la garantie d'une sécurité absolue. Il y a deux grands types d'attaque qui sont mises en place, et qui exploitent :
- les failles d'implémentation, notamment les générateurs aléatoires : la théorie suppose des clés choisies de façon aléatoire et parfaitement uniforme, ce qui n'est pas réalisable dans la pratique. Si la génération des clés est prédictible, alors le chiffrement est cassé, de fait.
- les canaux cachés : quand on chiffre ou qu'on déchiffre, les calculs dépendent de la clé. Typiquement, pour le RSA, on utilise l'exponentiation rapide, qui effectue, pour chaque bit de la clé, des calculs différents selon que le bit est 1 ou 0. Si on écoute la consommation électrique du CPU effectuant l'exponentiation rapide, on est capables de savoir si la calcul correspond au 1 ou au 0, car le  calcul n'étant pas le même, la consommation électrique n'est pas la même. Dès lors, casser des clés 2048 bits devient un jeu d'enfant. Ces canaux cachés prennent diverses formes : électricité, temps de calcul, rayonnement electromagnétique, et même le son du CPU (cf acoustic cryptanalysis d'adi shamir). Ce qu'il faut en conclure, c'est que sur du matériel standard, le chiffrement est cassable par canaux cachés. Il existe biensûr des solutions pour s'en prémunir, qui sont pour la plupart intégrées dans les cartes à puce, cette petite puce sécurisée qui connaît la clé, effectue les calculs, et cache, à l'extérieur, sa consommation électrique, les temps de calcul, les rayonnements electromagnétiques, ...

Bref, la sécurité est un vaste sujet, et il ne suffit pas d'avoir des belles théories mathématiques pour être confiant...


Et pour info, on dit chiffrer/déchiffrer/chiffrement/déchiffrement et non (en)crypter/décrypter/cryptage/décryptage.

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
trente trois plus trente quatre
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums