Deux problèmes essentiels limitent les méthodes de cryptographie à clés privées dans les réseaux (utilisées seules) :
- L'échange de clés entre des sites qui n'ont jamais été en relation => Il faut un moyen différent pour
échanger des clés.
- Pour communiquer dans un groupe de n participants il faut n(n-1)/2 clés.
1976 - Diffie et Hellman définissent les principes d'une nouvelle approche en cryptographie sans proposer de solution au problème qu'ils posent.
La cryptographie à clés publique.
1978 - R. Rivest A. Shamir L. Adelman donnent une première solution : La méthode RSA.
Cryptographie à clés publiques
L'idée est de supposer que l'on sait trouver deux fonctions Ek et Dk' qui dépendent de clés k et k'.
Ek est la méthodes d'encryptage.
Dk' est la méthodes de déchiffrage.
Ayant les propriétés suivantes :
1- Définition même de la cryptographie : Le déchiffrage est l'inverse de l'encryptage.
Dk' (Ek (M) ) = M
2- Il est très difficile de déduire Dk' de la connaissance de messages cryptés par Ek ou de Ek complète car cette fonction est diffusée à tous.
=> Des milliers d'années de calcul seraient nécessaires dans l'état des connaissances.
3- Idéalement Ek (M) et Dk' (M) devraient être faciles à calculer.
Les clés publiques: une révolution dans l'approche cryptographique
Un utilisateur a un couple (Ek, Dk')
- L'idée essentielle est que Ek (en fait k) peut être rendue publique par exemple dans un annuaire (le nom vient de là).
- Dk' est privée (en fait k' est privée et nécessairement différente de k).
- Tout le monde peut connaître Ek et envoyer des messages secrets qu'un seul destinataire (celui qui connaît Dk') peut comprendre.
- D'où l'hypothèse fondamentale d'un tel système.
=> On ne doit pas pouvoir trouver Dk' quand on connaît Ek.
Comme un attaquant connaît Ek et des messages cryptés par Ek il ne doit pas pouvoir casser Ek
=> Décrypter des messages cryptés par Ek en essayant des messages connus.
L'Algorithme RSA
Fonction E Encodage (publique)
- La clé publique est un couple d'entiers:
k = (e, n)
- L'encodage se fait au moyen de l'élévation à la puissance e modulo n:
Ek (M) = Me (mod n)
Fonction D Décodage (secrète)
- La clé secrète est un couple d'entiers :
k' = (d, n)
- Le décodage se fait au moyen de l'élévation à la puissance d modulo n:
Dk' (M) = Md (mod n)
Remarque: Les entiers n, e, d doivent être choisis selon des règles précises.
Méthode de choix des clés
1. Détermination de n
Trouver deux entiers premiers p et q très grands :
Calculez n = p q De préférence détruisez p et q.
La sécurité du système repose sur la difficulté de factoriser un grand entier n en deux entiers premiers p et q (taille de n : 320 bits, 512 bits, 1024 bits conditionne également la lenteur des algorithmes).
2. Détermination de d
Calculez z = (p-1) (q-1)
Choisir un entier e premier avec z.
La clé publique est ( e , n )
3. Détermination de d
Choisir un entier d tel que :
(d inverse de e dans l'arithmétique mod z)
La clé privée est ( d , n )
Réversibilité de RSA
Fonction d'Euler
Théorème d'Euler
Si a et n sont premiers entre eux
Pourquoi RSA marche
Remarques
1. Le RSA doit toujours être appliqué à des blocs de chiffres d'amplitude inférieure à n pour faire des calculs modulo n.
=>Décomposition des messages en blocs
2. On voit ici que l'on a aussi:
D ( E (M)) = E ( D (M)) = M
Exemple
1 Soient deux entiers premiers p =47,q =71
n = pq = 3337
2 z= (p-1)(q-1)= 46 . 70 = 3220
Choisissons e = 79 (premier avec n)
3 Calcul de l'inverse de e modulo z
Une solution possible: le théorème d'Euler
Numériquement 7978
(mod 3220) = 1019
Une autre solution plus simple:
L'algorithme d'Euclide
4 Crypter M = 6882326879666683
Décomposition en blocs de taille inférieure à n= 3337 => Des blocs de 3 chiffres
M= 688 232 687 966 668 3
Crypter 688 :
68879 (mod 3337) = 1570
E(M) = 1570 2756 2091 2276 2423 158
Décrypter 1570 :
15701019 (mod 3337) = 688
Tiré de "Cryptographie appliquée" B. Schneier
Intuitions relatives au RSA
Crypter = bousculer les informations pour rendre le sens inaccessible.
RSA = l'utilisation de l'élévation à la puissance puis d'une congruence.
- L'élévation à une puissance permet de changer le registre des entiers choisis
Exemple très simple e = 3 et n = 41:
Pour M = 27, M' = 28 peu différents.
E(M) = 27 3 = 19683
E(M') = 28 3 = 21952
- Les congruences introduisent des discontinuités => il est très difficile de trouver le logarithme d'un nombre dans un ensemble d'entiers modulo n.
Attaque du RSA
Solution de base
- n étant public le cryptanalyste cherche à trouver p et q pour calculer z.
=> Il doit factoriser un grand nombre en deux facteurs premiers.
Ce problème est complexe
Meilleurs algorithmes connus
- En 1989 avec 400 Vax pendant 3 semaines factorisation d'un nombre de 106 chiffres (352 bits)
- Actuellement factorisation possible de nombres de 110 à 120 chiffres (350 à 400 bits)
- Si on a trouvé p et q alors utiliser l'algorithme d'Euclide pour trouver e, d premiers avec (p-1) (q-1) = z
Attaque du RSA
Solution de base
- n étant public le cryptanalyste cherche à trouver p et q pour calculer z.
=> Il doit factoriser un grand nombre en deux facteurs premiers.
Ce problème est complexe
Meilleurs algorithmes connus
- En 1989 avec 400 Vax pendant 3 semaines factorisation d'un nombre de 106 chiffres (352 bits)
- Actuellement factorisation possible de nombres de 110 à 120 chiffres (350 à 400 bits)
- Si on a trouvé p et q alors utiliser l'algorithme d'Euclide pour trouver e, d premiers avec (p-1) (q-1) = z
Sécurité et performances du RSA
Utiliser des longueurs de clés de plus en plus importantes Valeurs envisagées 512 bits, 640 bits
1024 bits (considéré comme assez sûr pour plusieurs années) 2048 bits Utiliser des circuits intégrés de cryptage de plus en plus performants Actuellement une dizaine de circuits disponibles.
Vitesse de cryptage de base pour 512 bits:
De 10 à 30 Kb/s Évolution en cours de l'ordre de 64 Kb/s à venir de l'ordre de 1 Mb/s
Remarque: Compte tenu de la complexité des traitements le DES doit être environ toujours 100 fois plus rapide que le RSA.
Problèmes du RSA
- Trouver de grands nombres premiers (on prend en fait des nombres premiers en probabilité).
- Choisir des clés secrètes et publiques assez longues.
- Réaliser les opérations modulo n rapidement.
RSA carte bancaire
limitation des calculs du fait de la puissance de calcul disponible.
n sur 320 bits (de l'ordre de 95 chiffres) clé publique 3 pour tout le monde
Conclusion RSA
- Problème principal
Complexité algorithmique de la méthode.
Solution assez générale.
Utiliser le RSA brièvement au début d'un échange pour échanger des clés secrètes de session d'un algorithme efficace à clés privées.
- Efficacité en sécurité
La méthode est officiellement sûre si l'on respecte certaines contraintes de longueur de clés et d'usage.
Personne depuis 2500 ans n'a trouvé de solution rapide au problème de la factorisation ...
Les fonctions de hachage à sens unique
Notion de fonction à sens unique("one way function")
C'est une fonction f(M) facile à calculer mais telle qu'il est extrêmement difficile de déduire M de f(M).
Les fonctions à sens unique sont utiles pour garder sous forme inaccessible des mots de passe.
Par contre pour la cryptographie elles sont peu utiles car une fois M chiffré on ne sait pas déchiffrer M.
Notion de fonction à sens unique à brèche secrète C'est une fonction f(M) facile à calculer telle qu'il est extrêmement difficile de déduire M sauf si l'on connaît un secret K.
Notion de fonction de hachage
Une fonction de hachage est une fonction mathématique qui à partir d'un message (d'une donnée) génère une autre chaîne (généralement plus courte).
Terminologie: fonction de contraction, digest, empreinte digitale, ...
Exemples: Calcul de parité verticale
On fait le ou exclusif de tous les octets d'une chaîne de caractères.
Calcul de code polynomial.
Notion de fonction de hachage à sens unique sans clé
C'est une fonction de hachage à sens unique qui peut être calculée par n'importe qui (MD5).
Notion de fonction de hachage à sens unique avec clé
C'est une fonction de hachage à sens unique qui ne peut être calculée que par une seule entité détentrice de la clé.
Nombreux exemples de fonctions de hachage à sens unique avec clé.
<<< Chapitre III : Le DES "Data Encryption Standard"
Description : Mon Blog(fermaton.over-blog.com),No-5, THÉORÈME DES DÉGUISÉS. - DES PROBABILITÉS ??
RépondreSupprimer