Trois protocoles de passage

Ce texte sera l'un des chapitres réécrits du manuel sur la protection de l'information du Département de l'ingénierie radio et des systèmes de contrôle, ainsi que, à partir de ce code de formation, le Département de la protection de l'information de l'Institut de physique et de technologie de Moscou. Le tutoriel complet est disponible sur github (voir aussi les versions préliminaires ). Sur Habrir, je prévois de télécharger de nouvelles "grandes" pièces, d'une part, pour collecter des commentaires et observations utiles, et d'autre part, pour donner à la communauté plus de matériel sur des sujets utiles et intéressants.

Sujets précédents:

• Protocoles cryptographiques: définitions, enregistrements, propriétés, classification, attaques
• Protocoles de distribution clés sur des chiffrements symétriques

S'il existe un canal de communication entre Alice et Bob qui n'est pas accessible pour modification par un attaquant (c'est-à-dire, lorsque seul le modèle de cryptanalyste passif est applicable), même sans échange préalable de clés secrètes ou d'autres informations, vous pouvez utiliser les idées utilisées précédemment dans la cryptographie à clé publique. Après avoir décrit le RSA en 1978, Adi Shamir a proposé en 1980 l'utilisation de cryptosystèmes basés sur des opérations commutatives pour transmettre des informations sans d'abord échanger des clés secrètes. Si nous supposons que les informations transmises sont une clé de session secrète générée par l'une des parties, nous obtenons en général le protocole à trois passes suivant.

Préliminaire:

• Alice et Bob sont connectés par un canal de communication non sécurisé, ouvert à l'écoute (mais pas à la modification) par un attaquant.
• Chaque côté a une paire de clés publiques et privées $$$K_A$ , $$$k_A$ , $$$K_B$ , $$$k_B$ en conséquence.
• Les parties ont choisi et utilisé la fonction de chiffrement commutatif:
  

  $$

  $$\ begin {array} {lll} D_ {A} \ left (E_ {A} \ left (X \ right) \ right) = X & \ forall X, \ left \ {K_A, k_a \ right \}; \\ E_ {A} \ left (E_ {B} \ left (X \ right) \ right) = E_B \ left (E_A \ left (X \ right) \ right) & \ forall ~ K_A, K_B, X. \ end {array}$$

Le protocole se compose de trois passes avec transmission de messages (d'où le nom) et une finale, sur laquelle Bob reçoit la clé.

1. Alice sélectionne une nouvelle clé de session $$$K$
   
   $$$Alice \ à \ gauche \ {E_A \ gauche (K \ droite) \ droite \} \ à Bob$
2. $$$Bob \ à \ gauche \ {E_B \ gauche (E_A \ gauche (K \ droite) \ droite) \ droite \} \ à Alice$
3. Alice, en utilisant la commutativité de la fonction de cryptage,
   

   $$

   $$D_A \ gauche (E_B \ gauche (E_A \ gauche (K \ droite) \ droite) \ droite) = D_A \ gauche (E_A \ gauche (E_B \ gauche (K \ droite) \ droite) \ droite) = E_B \ gauche (K \ droite).$$
   $$$Alice \ à \ gauche \ {E_B \ gauche (K \ droite) \ droite \} \ à Bob$
4. Bob déchiffre $$$D_B \ gauche (E_B \ gauche (K \ droite) \ droite) = K$

En conséquence, les parties reçoivent une clé secrète partagée. $$$K$ .

Un inconvénient commun de tous ces protocoles est le manque d'authentification des parties. Bien sûr, dans le cas d'un cryptanalyste passif, cela n'est pas obligatoire, mais dans la vie réelle, vous devez toujours considérer tous les modèles possibles (y compris un cryptanalyste actif) et utiliser des protocoles qui impliquent l'authentification mutuelle des parties. De plus, contrairement au schéma Diffie-Hellman, la nouvelle clé est sélectionnée par l'initiateur de la session, ce qui permet à l'initiateur, non avec de bonnes intentions, de forcer le deuxième participant à utiliser la clé de session obsolète.

En termes de propriétés de sécurité , tous les représentants de cette classe de protocoles déclarent uniquement l'authentification par clé (G7). Contrairement au schéma Diffie - Hellman, les protocoles à trois passes ne nécessitent pas la sélection de nouvelles clés «principales» pour chaque session de protocole, c'est pourquoi ni le secret direct parfait (G9) ni la formation de nouvelles clés (G10) ne peuvent être garantis.

Option triviale

Donnons un exemple de protocole basé sur la fonction XOR (addition bit à bit modulo 2). Bien que cette fonction puisse être utilisée comme base pour la construction de systèmes d'une force cryptographique parfaite, pour un protocole à trois passes, c'est un mauvais choix.

Avant de commencer le protocole, les deux parties ont leurs clés secrètes. $$$K_A$ et $$$K_B$ représentant des séquences binaires aléatoires avec une distribution uniforme des caractères. La fonction de cryptage est définie comme $$$E_i (X) = X \ oplus K_i$ où $$$X$ ce message aussi $$$K_i$ - clé secrète. De toute évidence:

$$

$$\ forall i, j, X: E_i \ left (E_j \ left (X \ right) \ right) = X \ oplus K_j \ oplus K_i = X \ oplus K_i \ oplus K_j = E_j \ left (E_i \ left (X \ droite) \ droite)$$

1. Alice sélectionne une nouvelle clé de session $$$K$
   
   $$$Alice \ to \ left \ {E_A \ left (K \ right) = K \ oplus K_A \ right \} \ to Bob$
2. $$$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) = K \ oplus K_A \ oplus K_B \ right \} \ vers Alice$
3. Alice, en utilisant la commutativité de la fonction de cryptage,
   

   $$

   $$D_A \ gauche (E_B \ gauche (E_A \ gauche (K \ droite) \ droite) \ droite) = K \ oplus K_A \ oplus K_B \ oplus K_A = K \ oplus K_B = E_B \ gauche (K \ droite).$$
   $$$Alice \ to \ left \ {E_B \ left (K \ right) = K \ oplus K_B \ right \} \ to Bob$
4. Bob déchiffre $$$D_B \ gauche (E_B \ gauche (K \ droite) \ droite) = K \ oplus K_B \ oplus K_B = K$

À la fin de la session de protocole, Alice et Bob connaissent la clé de session commune $$$K$ .

Le choix proposé de la fonction de cryptage commutatif du secret parfait n'est pas réussi, car il existe des situations dans lesquelles un cryptanalyste peut déterminer la clé $$$K$ . Supposons qu'un cryptanalyste ait intercepté les trois messages:

$$

$$K \ oplus K_A, ~~ K \ oplus K_A \ oplus K_B, ~~ K \ oplus K_B.$$

L'ajout de Modulo 2 aux trois messages donne la clé $$$K$ . Par conséquent, un tel système de cryptage n'est pas utilisé.

Nous présentons maintenant le protocole de transfert fiable de la clé secrète, basé sur la fonction de cryptage exponentielle (commutative). La stabilité de ce protocole est associée à la difficulté de la tâche de calcul du logarithme discret: pour les valeurs connues $$$y, g, p$ trouver $$$x$ de l'équation $$$y = g ^ x \ bmod p$ .

Protocole sans clé de Shamir

Les parties s'entendent provisoirement sur un grand nombre $$$p \ sim 2 ^ {1024}$ . Chacune des parties choisit une clé secrète. $$$a$ et $$$b$ . Ces touches sont plus petites et mutuellement simples. $$$p-1$ . De plus, les parties se sont préparées selon un numéro spécial $$$a '$ et $$$b '$ qui leur permettent de déchiffrer un message chiffré avec leur clé:

$$

$$\ begin {array} {l} a '= a {-1} \ mod (p-1), \\ a \ times a' = 1 \ mod (p-1), \\ \ forall X: (X ^ a) ^ {a '} = X. \\ \ end {array}$$

La dernière expression est vraie par le corollaire du petit théorème de Fermat \ index {théorème! La ferme est petite}. Les opérations de chiffrement et de déchiffrement sont définies comme suit:

$$

$$\ begin {array} {lll} \ forall M <p: & C = E (M) = M ^ {a} & \ mod p, \\ & D (C) = C ^ {a '} & \ mod p, \\ & D_A (E_A (M)) = M ^ {aa '} = M & \ mod p. \\ \ end {array}$$

1. Alice sélectionne une nouvelle clé de session $$$K <p$
   
   $$$Alice \ to \ left \ {E_A \ left (K \ right) = K ^ a \ bmod p \ right \} \ to Bob$
2. $$$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) = K ^ {ab} \ bmod p \ right \} \ to Alice$
3. Alice, en utilisant la commutativité de la fonction de cryptage,
   

   $$

   $$D_A \ gauche (E_B \ gauche (E_A \ gauche (K \ droite) \ droite) \ droite) = K ^ {aba '} = K ^ b = E_B \ gauche (K \ droite) \ mod p.$$
   
   $$$Alice \ to \ left \ {E_B \ left (K \ right) = K ^ b \ right \} \ to Bob$
4. Bob déchiffre $$$D_B \ left (E_B \ left (K \ right) \ right) = K ^ {bb '} \ bmod p = K$

À la fin de la session de protocole, Alice et Bob connaissent la clé de session commune $$$K$ .

Supposons qu'un cryptanalyste ait intercepté trois messages:

$$

$$\ begin {array} {l} y_1 = K ^ a \ bmod p, \\ y_2 = K ^ {ab} \ bmod p, \\ y_3 = K ^ b \ bmod p. \\ \ end {array}$$

Pour trouver la clé $$$K$ , un cryptanalyste doit résoudre un système de ces trois équations, qui a une très grande complexité de calcul, inacceptable d'un point de vue pratique, si les trois $$$a, b, ab$ assez grand. Supposons que $$$a$ (ou $$$b$ ) ne suffit pas. Ensuite, calcul des degrés successifs $$$y_3$ (ou $$$y_1$ ), peut être trouvé $$$a$ (ou $$$b$ ), en comparant le résultat avec $$$y_2$ . Connaître $$$a$ facile à trouver $$$a ^ {- 1} \ bmod (p-1)$ et $$$K = (y_1) ^ {a ^ {- 1}} \ bmod p$ .

Cryptosystème Massey-Omura

En 1982, James Massey et Jim Omura ont déposé un brevet (James Massey, Jim K. Omura), améliorant (selon eux) le protocole sans clé de Shamir. En tant qu'opération de chiffrement au lieu d'exponentiation dans un groupe multiplicatif $$$\ mathbb {Z} _p ^ *$ ils ont suggéré d'utiliser l'exponentiation dans le champ de Galois $$$\ mathbb {GF} {2 ^ n}$ . Clé secrète de chaque partie (pour Alice - $$$a$ ) doit satisfaire aux conditions:

$$

$$\ begin {array} {l} a \ in \ mathbb {GF} {2 ^ n}, \\ gfd \ left (a, x ^ {n-1} + x ^ {n-2} + ... + x + 1 \ droite) = 1. \\ \ end {array}$$

Sinon, le protocole est similaire.

Postface

L'auteur sera reconnaissant des commentaires factuels et autres sur le texte.