Cryptage Asymétrique

Échange de Clés Diffie-Hellman

Le principal inconvénient des cryptosystèmes à clé privée (DES ou AES) est que la clé privée doit être échangée. Eh bien, l'algorithme Diffie-Hellman est capable d'échanger des clés privées sur un canal public. Il a été inventé en 1976 par Diffie, Hellman et Merkle. Cette approche n'est donc pas destinée au chiffrement ou au déchiffrement, mais à l'échange sécurisé des clés privées pour les cryptosystèmes asymétriques. Et nous pouvons créer des clés privées séparément basées sur l'arithmétique modulaire.

Nous devons d'abord générer d'énormes nombres premiers n et g. Cependant g doit être la racine primitive de n autrement dit g est la racine primitive n si g mod n, g² mod n ... g^n-1 mod n génère tous les entiers compris dans l'intervalle [1, n-1].

1. L'expéditeur (Alice) génère d'énormes nombres premiers n et g (la racine primitive de n ) et l'envoie au destinataire (Bob) (ce n'est pas un problème si quelqu'un connaît ces numéros). Ces nombres sont typiquement > 1024 bits.
2. L'expéditeur et le destinataire génèrent tous deux un nombre aléatoire < n-1, Alice génère x et Bob génère y (ce sont les clés privées).
3. Alice calcule k₁ = g^x mod n et l'envoie à Bob et Bob calcule k₂ = g^y mod n et l'envoie à Alice.
4. Ils peuvent calculer la clé secrète partagée :
5. Alice calcule k^x₂ mod n = (g^y mod n)^x mod n = g^xy mod n
6. Bob calcule k^y₁ mod n = (g^x mod n)^y mod n = g^yx mod n

Il est très important de choisir n comme nombre premier car si n n'est pas un nombre premier, il est plus facile de craquer le cryptosystème Diffie-Hellman, et l'ensemble du cryptosystème repose fortement sur le fait que la résolution du Problème du logarithme discret a une complexité de temps d'exécution exponentielle, il est donc extrêmement difficile à déchiffrer. Cependant, si nous utilisons des nombres composés pour n, résoudre le problème du logarithme discret (le casser) est plus facile grâce à la Théorème des restes chinois.

Cryptosystème RSA (Rivest-Shamir-Adleman)

C'est un cryptosystème à clé publique (il a donc une clé privée et une clé publique), il a été construit en 1977 par Rivest, Shamir et Adleman. Chaque cryptosystème à clé publique s'appuie fortement sur une fonction de trappe et RSA est sécurisé en raison du problème de factorisation des nombres entiers. Qui consiste à valider le résultat en multipliant deux nombres et c'est facile, mais trouver les facteurs est difficile.

Soit p un nombre premier alors pour tout entier a (a n'est pas divisible par p) le nombre a^p-1-1 est un multiple entier de p.

a^p-1 ≡ 1 (mod p) qui est le petit théorème de Fermat. On peut généraliser ce théorème avec la fonction Φ(n) d'Euler : cette fonction totient compte les entiers positifs jusqu'à un entier donné n qui sont premiers relatifs à n et la formule est : a^Φ(n) ≡ 1 (mod p). Notamment par premier relatif, nous entendons que deux entiers a et b sont dits premiers ou premiers entre eux si le seul entier positif (facteur) qui les divise tous les deux est 1 avec cette formule : pgcd(a, b) = 1

1. Nous générons 2 grands nombres premiers p et q, pour cela nous pouvons utiliser Rabin-Miller un algorithme très optimisé pour le faire.
2. On calcule n = p * q donc multiplions les nombres premiers : Φ(n) = (p - 1) * (q - 1)
3. Calculons le paramètre de clé publique e, nous pouvons calculer e tel que gcd(e, Φ(n)) = 1. Donc, fondamentalement, e et Φ(n) sont des nombres premiers relatifs.
4. Calculons le paramètre d de la clé privée : calculons l'inverse modulaire de e (c'est pour cela qu'il est crucial que e et Φ (n) soient premiers) : d * e mod Φ(n) = 1, après avoir résolu cette équation, nous obtenons le paramètre d.

Ensuite, nous avons : CLÉ PUBLIQUE : (e, n) et CLÉ PRIVÉE : (d, n)

Après ces étapes, pour chiffrer le message, nous devons d'abord transformer le texte brut en blocs (nous pouvons utiliser La Table ASCII pour convertir du texte en nombres) où chaque bloc est plus petit que n et comme d'habitude nous utilisons la clé publique pour le chiffrement et la clé privée pour le déchiffrement. De cette façon ciphertext_block = plaintext_block^e mod n et plaintext_block = ciphertext_block^d mod n

1. Nous avons beaucoup parlé de la théorie, maintenant essayons ceci dans un exemple réel, générons de grands nombres premiers : p = 17 et q = 23.
2. Calculons n = p * q = 17 * 23 = 391 donc Φ(17 - 1) * (23-1) = 352.
3. Nous devons maintenant trouver un nombre e où gcd(e, Φ(n)) = 1 avec L'Algorithme d'Euclide et nous obtenons e = 21.
4. Nous devons enfin trouver l'inverse modulaire de e en utilisant L'Algorithme d'Euclide Étendu et nous obtenons d = 285.

Maintenant que nous avons la clé publique : (21, 391) et la clé privée: (285, 391) nous pouvons chiffrer un message.

Disons que nous avons le caractère a à chiffrer. La représentation ASCII de a est 97.

Cryptage → ciphertext_block = plaintext_block^e mod n = 97²¹ mod 391 = 37

Décryptage → plaintext_block = ciphertext_block^d mod n = 37²⁸⁵ mod 391 = 97

Cryptographie à Courbe Elliptique (ECC)

Il y a plusieurs problèmes avec le cryptosystème RSA, la factorisation est la fonction trappe dans RSA, mais il n'a jamais été prouvé que la factorisation est difficile. General number field sieve (GNFS) est l'algorithme connu le plus rapide pour la factorisation en nombres premiers. C'est pour cela nous avons besoin d'énormes nombres premiers, c'est pourquoi nous utilisons des séquences longues d'au moins 2048 bits comme clés RSA, soit 512 chiffres hexadécimaux. Cependant, l'informatique quantique rendra RSA obsolète à l'avenir.

L'utilisation des courbes elliptiques en cryptographie a été suggérée indépendamment par Neal Koblitz et Victor S.Miller en 1985. C'est l'un des cryptosystèmes à clé publique les plus populaires, et Bitcoin utilise la cryptographie à courbe elliptique.

Si nous avons affaire à une courbe elliptique E définie par y² = x³ + ax + b équation et |E| = n et P(x, y) et R(x, y) sont des points sur la courbe elliptique, le but est de trouver 1 ≤ x ≤ n tel que P + P + P + ... + P = R et xP = 5. C'est une trappe-fonction typique : nous pouvons calculer xP avec O(m) complexité de temps d'exécution linéaire mais (si nous avons R) nous devons utiliser une approche par force brute pour trouver x et il a O(2^m) temps d'exécution exponentiel.

Dans un cryptosystème à clé publique (asymétrique) tous les utilisateurs ont deux clés : la clé publique et la clé privée, ces clés ne sont pas indépendantes l'une de l'autre, la clé privée peut déchiffrer un message qui a été chiffré avec la clé publique et vice-versa versa. Tout le monde peut envoyer un message chiffré à un utilisateur donné à l'aide de sa clé publique et seul l'utilisateur donné peut déchiffrer ce message à l'aide de sa clé privée.