«Protocoles de cryptosystèmes»: Diffie - Hellman, El-Gamal, MTI / A (0), STS

Comme les créateurs des protocoles à trois passes de la section précédente , les auteurs des algorithmes suivants ne les ont pas considérés uniquement comme des constructions mathématiques fournissant une opération élémentaire (par exemple, le chiffrement à clé publique), mais ont essayé de construire un système de distribution de clés complet autour d'une ou deux formules. Certaines de ces constructions, qui ont été transformées, sont utilisées à ce jour (par exemple, le protocole Diffie-Hellman), certaines ne restent que dans l'histoire de la cryptographie et de la protection des informations.

Plus tard dans les années 1990, les primitives mathématiques asymétriques (chiffrement et signature électronique) et les protocoles seront séparés, ces primitives seront utilisées, ce qui sera démontré dans la section sur les protocoles asymétriques.

Diffie - Hellman Protocol

Le premier algorithme à clé publique a été proposé par Diffie et Hellman en 1976, «New Directions in Cryptography» ( Bailey Whitfield Diffie, Martin Edward Hellman, «New directions in cryptography» , [Diffie, Hellman 1976] ). Ce protocole, qui peut également être appelé schéma Diffie-Hellman , a été le premier à réduire les exigences pour que le canal de communication établisse une connexion sécurisée sans avoir à échanger au préalable les clés.

Le protocole permet à deux parties de créer une clé de session commune à l'aide d'un canal de communication qu'un attaquant peut écouter, mais en supposant que ce dernier ne peut pas modifier le contenu du message.

Soit $$$p$ - un grand nombre premier $$$g$ - un élément primitif du groupe $$$\ mathbb {Z} _p ^ *$ , $$$y = g ^ x \ bmod p$ et $$$p$ , $$$y$ et $$$g$ connu à l'avance. Fonction $$$y = g ^ {x} \ bmod p$ nous considérons unidirectionnel, c'est-à-dire que le calcul d'une fonction avec une valeur connue d'un argument est une tâche facile, et son inversion (trouver un argument) avec une valeur connue d'une fonction est difficile. (Fonction inverse $$$x = \ log_g y \ bmod p$ appelé la fonction logarithme discret. Il n’existe actuellement aucun moyen rapide de calculer une telle fonction $$$p$ .)

Le protocole d'échange comprend les actions suivantes.

1. Alice choisit un hasard $$$2 \ leq a \ leq p - 1$
   $$$Alice \ à \ gauche \ {A = g ^ a \ bmod p \ droite \} \ à Bob$
2. Bob choisit au hasard $$$2 \ leq b \ leq p-1$
   Bob calcule la clé de session $$$K = A ^ b \ bmod p$
   $$$Bob \ à \ gauche \ {B = g ^ b \ bmod p \ droite \} \ à Alice$
3. Alice calcule $$$K = B ^ a \ bmod p$
   

De cette façon, une clé de session secrète partagée est créée $$$K$ . En raison de la sélection aléatoire des valeurs $$$a$ et $$$b$ dans une nouvelle session, une nouvelle clé de session sera reçue.

Le protocole fournit uniquement la génération de nouvelles clés de session (cible G10). En l'absence d'un tiers de confiance, il ne fournit pas d'authentification des parties (objectif G1), faute de passages avec confirmation de la possession de la clé, il n'y a pas d'authentification de clé (objectif G8). Mais, puisque le protocole n'utilise pas de longues clés «maîtres», on peut dire qu'il a la propriété du secret direct parfait (objectif G9).

Le protocole ne peut être utilisé qu'avec des canaux de communication dans lesquels un cryptanalyste actif ne peut pas intervenir. Sinon, le protocole devient vulnérable à une simple «attaque médiane».

1. Alice choisit un hasard $$$2 \ leq a \ leq p - 1$
   $$$Alice \ à \ gauche \ {A = g ^ a \ bmod p \ droite \} \ à Mellory ~ (Bob)$
2. Mallory choisit un hasard $$$2 \ leq m \ leq p-1$
   Mallory calcule une clé de session pour un canal avec Alice
   

   $$

   $$K_ {AM} = A ^ m \ bmod p = g ^ {am} \ bmod p$$
   
   $$$Mellory ~ (Alice) \ to \ left \ {M = g ^ m \ bmod p \ right \} \ to Bob$
   $$$Mellory ~ (Bob) \ vers \ gauche \ {M = g ^ m \ bmod p \ droite \} \ vers Alice$
3. Alice calcule la clé de session pour le canal avec Mallory (pensant que Mallory est Bob)
   

   $$

   $$K_ {AM} = M ^ a \ bmod p = g ^ {am} \ bmod p$$
4. Bob choisit au hasard $$$2 \ leq b \ leq p-1$
   Bob calcule la clé de session pour le canal avec Mallory (pensant que Mallory est Alice)
   

   $$

   $$K_ {BM} = M ^ b \ bmod p = g ^ {bm} \ bmod p$$
   
   $$$Bob \ à \ gauche \ {B = g ^ b \ bmod p \ droite \} \ à Mellory ~ (Alice)$
5. Mallory calcule une clé de session pour un canal avec Bob
   

   $$

   $$K_ {BM} = B ^ m \ bmod p = g ^ {bm} \ bmod p$$
   
   

En conséquence, Alice et Bob ont reçu de nouvelles clés de session, mais ils n'ont pas établi de canal de communication «sécurisé» entre eux, mais avec un attaquant qui a désormais la possibilité de relayer ou de modifier tous les messages transmis entre Alice et Bob.

Le protocole Diffie-Hellman diffère de la plupart des protocoles de distribution de clés en raison du fait qu'il n'utilise pas d'autres primitives cryptographiques (cryptage, signature numérique ou fonctions de hachage), mais en soi est en un sens une primitive cryptographique pour construire des protocoles plus complexes. Il permet la génération de nombres aléatoires dans un système distribué sans centre de confiance. De plus, aucun côté ne peut forcer l'autre côté à utiliser l'ancienne clé de session, contrairement, par exemple, au protocole Yahalom.

Le protocole peut être modifié de sorte qu'au lieu du groupe multiplicatif de multiplication simple, utilisez le groupe additif d'addition de points de la courbe elliptique. Dans ce cas, les parties choisiront toujours des nombres entiers aléatoires, mais n'augmenteront pas le nombre de générateurs à une puissance, mais multiplieront le point de générateur par le nombre souhaité.

1. Les parties se sont mises d'accord sur un groupe de points de la courbe elliptique $$$\ mathbb {E}$ son sous-groupe cyclique $$$\ mathbb {G}$ puissance $$$n = \ | \ mathbb {G} \ |$ et générateur $$$G$ groupes $$$\ mathbb {G}$ (ou au moins un sous-groupe suffisamment grand du groupe $$$\ mathbb {G}$ )
2. Alice choisit un hasard $$$2 \ leq a \ leq n - 1$
   $$$Alice \ à \ gauche \ {A = a \ fois G \ droite \} \ à Bob$
3. Bob choisit au hasard $$$2 \ leq b \ leq n - 1$
   Bob calcule le point $$$K = b \ fois A$
   $$$Bob \ à \ gauche \ {B = g \ fois G \ droite \} \ à Alice$
4. Alice calcule le point $$$K = a \ fois B$

En tant que nouvelle clé de session, les parties peuvent choisir, par exemple, la première coordonnée du point trouvé $$$K$ .

Protocole El Gamal

Le protocole El-Gamal ( [ElGamal, 1984] , [ElGamal, 1985] ), en raison de la distribution préliminaire de la clé publique de l'une des parties, fournit l'authentification de la clé pour ce côté. Il peut être garanti que seul le propriétaire de la clé privée correspondante peut calculer la clé de session. Cependant, la confirmation de la réception de la clé (réalisation des objectifs G1 et G8) ne fait pas partie du protocole.

1. Alice et Bob choisissent des options communes $$$p$ et $$$g$ où $$$p$ Est un grand nombre premier, et $$$g$ - élément de champ primitif $$$\ mathbb {Z} _p ^ *$ .
   Bob crée une paire de clés privées et publiques $$$b$ et $$$K_B$ :
   

   $$

   $$\ begin {array} {l} b: 2 \ leq b \ leq p - 1, \\ K_B = g ^ b \ bmod p. \ end {array}$$
   
   Clé publique $$$K_B$ Il est en libre accès public pour toutes les parties. Un cryptanalyste ne peut pas le remplacer - la substitution sera perceptible.
2. Alice cueille un secret $$$x$ et calcule la clé de session $$$K$
   

   $$

   $$K = K_B ^ {x} = g ^ {bx} \ bmod p.$$
   
   

   $$

   $$Alice \ à \ gauche \ {g ^ x \ bmod p \ droite \} \ à Bob$$
3. Bob calcule la clé de session
   

   $$

   $$K = (g ^ x) ^ {b} = g ^ {bx} \ bmod p.$$

Le protocole ne garantit pas la sélection d'une nouvelle clé de session dans chaque session de protocole (G10), et l'utilisation d'une clé «maître» $$$K_B$ transférer une clé de session permet à un attaquant de calculer toutes les clés de session des sessions précédentes lorsqu'une clé privée est compromise $$$b$ (objectif G9).

Protocole MTI / A (0)

En 1986, C. Matsumoto ( Tsutomu Matsumoto ), I. Takashima ( Youichi Takashima ) et H. Imai ( Hideki Imai ) ont proposé plusieurs algorithmes, appelés plus tard la famille de protocoles MTI ( [Matsumoto, Tsutomu, Imai 1986] ). En raison de la distribution préliminaire des clés publiques des deux parties, ils ont fourni une authentification de clé implicite (cible G7). Autrement dit, une clé de session ne pouvait être garantie que par les propriétaires des clés publiques correspondantes. Nous considérerons l'un des représentants de cette famille - le protocole MTI / A (0).

Auparavant, les parties étaient convenues des paramètres généraux du système. $$$p$ et $$$g$ où $$$p$ Est un grand nombre premier, et $$$g$ - élément de champ primitif $$$\ mathbb {Z} _p ^ *$ .


Chacune des parties (Alice et Bob) a généré une paire de clés privées et publiques:

$$

$$\ begin {array} {ll} Alice: & ~ a, ~~ K_A = g ^ a \ bmod p, \\ Bob: & ~ b, ~~ K_B = g ^ b \ bmod p. \\ \ end {array}$$

1. Alice a généré un nombre aléatoire $$$R_A: ~ 2 \ leq R_A \ leq p-1$
   $$$Alice \ à \ gauche \ {g ^ {R_A} \ bmod p \ droite \} \ à Bob$
2. Bob a généré un nombre aléatoire $$$R_B: ~ 2 \ leq R_B \ leq p-1$
   Bob a trouvé une clé de session $$$K = (g ^ {R_A}) ^ b \ cdot K_A ^ {R_B} \ bmod p$
   $$$Bob \ à \ gauche \ {g ^ {R_B} \ bmod p \ droite \} \ à Alice$
3. Alice a calculé la clé de session $$$K = (g ^ {R_B}) ^ a \ cdot K_B ^ {R_A} \ bmod p$

Si les clés publiques $$$K_A$ et $$$K_B$ correspondre à vos clés privées $$$a$ et $$$b$ , puis les clés de session calculées par les participants correspondent:

$$

$$\ begin {array} {lll} (g ^ {R_A}) ^ b \ cdot K_A ^ {R_B} \ bmod p & = & g ^ {b R_A + a R_B} \ bmod p, \\ (g ^ { R_B}) ^ a \ cdot K_B ^ {R_A} \ bmod p & = & g ^ {a R_B + b R_A} \ bmod p. \ end {array}$$

En raison de la complexité de la tâche de logarithme discret, un attaquant ne pourra pas obtenir $$$a, R_A$ ou $$$b, R_B$ à partir des messages transmis, et la publication préalable des clés publiques garantit que seuls les utilisateurs légitimes reçoivent la clé de session. Sélection aléatoire $$$R_A$ et $$$R_B$ garantit que les deux parties peuvent être sûres de créer une nouvelle clé de session dans chaque session de protocole.

Comme d'autres représentants des protocoles de cryptosystème, MTI n'a pas été développé en tenant compte de la possibilité de compromettre les clés "maîtres" fermées $$$a$ et $$$b$ (objectif G9).

Protocole de station à station

Le protocole STS ( Station-to-Station , [Diffie, Oorschot, Wiener 1992] ) est destiné aux systèmes de communication mobiles. Il utilise les idées du protocole Diffie-Hellman et du cryptosystème RSA. Une caractéristique du protocole est l'utilisation d'un mécanisme de signature électronique pour l'authentification mutuelle des parties.

Auparavant, les parties étaient convenues des paramètres généraux du système. $$$p$ et $$$g$ où $$$p$ Est un grand nombre premier, et $$$g$ - élément de champ primitif $$$\ mathbb {Z} _p ^ *$ .

De chaque côté $$$A$ et $$$B$ possède une paire de clés à long terme: une clé privée pour déchiffrer et créer une signature électronique $$$K _ {\ text {public}}$ et clé publique pour le chiffrement et la vérification de signature $$$K _ {\ text {public}}$ .

$$

$$\ begin {array} {ll} A: K_ {A, \ text {private}}, K_ {A, \ text {public}}: \ forall M: & \ text {Verify} _A (M, S_A (M )) = true, \\ & D_A (E_A (M)) = M, \\ B: K_ {B, \ text {private}}, K_ {B, \ text {public}}: \ forall M: & \ text {Verify} _B (M, S_B (M)) = true, \\ & D_B (E_B (M)) = M. \\ \ end {array}$$

O Where $$$\ text {Verify} _A (\ dots)$ c'est une fonction de vérification de la signature électronique sur une clé publique $$$K_ {A, \ text {public}}$ et $$$D_A$ - fonction de déchiffrement utilisant la clé privée $$$K_ {A, \ text {private}}$ .

Le protocole se compose de quatre passes, dont trois incluent la transmission de messages ( [Cheryomushkin 2009] ).

1. Alice choisit un nombre aléatoire $$$R_A: 2 \ leq R_A \ leq p-1$ .
   $$$Alice \ à \ gauche \ {A, m_A = g ^ {R_A} \ bmod p \ droite \} \ à Bob$
2. Bob choisit un nombre aléatoire $$$R_B: 2 \ leq R_B \ leq p-1$ .
   Bob calcule la clé de session $$$K = m_A ^ {R_B} \ bmod p$ .
   $$$Bob \ à \ gauche \ {B, A, m_B = g ^ {R_B} \ bmod p, E_K (S_B (m_A, m_B)) \ right \} \ à Alice$
3. Alice calcule une clé de session $$$K = m_B ^ {R_A} \ bmod p$ .
   Alice vérifie la signature dans le message $$$E_K (S_B (m_A, m_B))$ .
   $$$Alice \ à \ gauche \ {A, B, E_K (S_A (m_A, m_B)) \ droite \} \ à Bob$
4. Bob vérifie la signature dans le message $$$E_K (S_A (m_A, m_B))$ .

Le protocole assure la garantie de la formation de nouvelles clés (G10), mais pas le secret direct parfait (G9).

Comme l'a montré l'attaque de Lowe 1996 ( [Lowe 1996] ), le protocole ne peut garantir l'authentification des sujets (cible G1), des clés (G7) et la preuve de propriété de la clé de session (G8). Bien que l'attaquant ne puisse pas accéder à la nouvelle clé de session si le protocole est utilisé uniquement pour authentifier les sujets, Alice peut confondre l'attaquant avec Bob.

1. Alice choisit un nombre aléatoire $$$R_A: 2 \ leq R_A \ leq p-1$ .
   $$$Alice \ à \ gauche \ {A, m_A = g ^ {R_A} \ bmod p \ droite \} \ à Mellory ~ (Bob)$
   
2. $$$Mellory \ to \ left \ {M, m_A \ right \} \ to Bob$
   
3. Bob choisit un nombre aléatoire $$$R_B: 2 \ leq R_B \ leq p-1$ .
   Bob calcule la clé de session $$$K = m_A ^ {R_B} \ bmod p$ .
   $$$Bob \ à \ gauche \ {B, M, m_B, E_K (S_B (m_A, m_B)) \ droite \} \ à Mellory$
   
4. $$$Mellory ~ (Bob) \ vers \ gauche \ {B, A, E_K (S_B (m_A, m_B)) \ droite \} \ vers Alice$
   
5. Alice calcule une clé de session $$$K = m_B ^ {R_A} \ bmod p$ .
   Alice vérifie la signature dans le message $$$E_K (S_B (m_A, m_B))$ .
   $$$Alice \ à \ gauche \ {A, B, E_K (S_A (m_A, m_B)) \ droite \} \ à Mellory ~ (Bob)$
   

Après avoir réussi le protocole, Alice est convaincue qu'elle communique avec Bob.

Comme tous les autres «protocoles de cryptosystème», le protocole de station à station est basé sur une source externe d'informations sur les clés publiques des participants, sans remettre en cause l'exactitude et la fiabilité de cette source. Ce qui, dans le cas général, est incorrect. Si des informations sur les clés des participants doivent être reçues en externe à chaque session du protocole (par exemple, s'il y a beaucoup de participants et qu'il n'est pas possible de se souvenir de toutes les clés), alors le canal d'obtention des clés publiques sera l'objectif principal d'un cryptanalyste actif pour les protocoles considérés. La façon de vous protéger de cela en utilisant des primitives de cryptographie asymétriques est dans la section suivante.

Littérature

• [Diffie, Hellman 1976] Diffie W., Hellman ME Nouvelles directions en cryptographie // Information Theory, IEEE Transactions on. - 1976. - nov. - t. 22, n ° 6. - p. 644-654. - ISSN 0018-9448. - DOI: 10.1109 / TIT.1976.1055638.
• [ElGamal, 1984] El Gamal T. Un cryptosystème à clé publique et un schéma de signature basé sur des logarithmes discrets // Actes du CRYPTO 84 sur les progrès de la cryptologie. - Santa Barbara, Californie, États-Unis: Springer-Verlag New York, Inc., 1985 .-- p. 10-18. - ISBN 0-387-15658-5. - URL: dl.acm.org/citation.cfm?id=19478.19480 .
• [ElGamal, 1985] El Gamal T. Un cryptosystème à clé publique et un schéma de signature basé sur des logarithmes discrets // Transactions IEEE sur la théorie de l'information. - 1985. - juillet. - t. 31, n ° 4. - p. 469-472. - DOI: 10.1109 / TIT.1985.1057074.
• [Matsumoto, Tsutomu, Imai 1986] Matsumoto T., Takashima Y., Imai H. À la recherche de systèmes intelligents de distribution de publicités // Trans. Inst. Electron Commun. Eng. Jpn. Sect. E. T. 69. question 2. - 02.1986. - avec 99-106.
• [Diffie, Oorschot, Wiener 1992] Diffie W., Van Oorschot PC, Wiener MJ Authentication
  et échanges de clés authentifiés // Conceptions, codes et cryptographie. - 1992. - juin. - t. 2, n ° 2. - p. 107-125. - ISSN 1573-7586. - DOI: 10.1007 / BF00124891.
• [Lowe 1996] Lowe G. Quelques nouvelles attaques contre les protocoles de sécurité // CSFW '96 Actes du 9ème atelier IEEE sur les fondations de sécurité informatique. —Washington, DC, États-Unis: IEEE Computer Society, 1996. - p. 162.
• [Cheremushkin 2009] Cheremushkin A. V. Protocoles cryptographiques: propriétés et vulnérabilités de base // Applied Discrete Mathematics. - 2009. - nov. - problème. 2. - p. 115-150. - URL: cyberleninka.ru/article/n/kriptograficheskieprotokoly-osnovnye-svoystva-i-uyazvimosti.pdf .