dxdt.ru: занимательный интернет-журнал

Часто попадается популярная иллюстрация к протоколу Диффи-Хеллмана, использующая аналогию “смешивания красок”: то есть, стороны, пытающиеся получить общий секрет, смешивают исходную краску, которая известна всем, каждая со своей секретной краской, а потом обмениваются результатами по открытому каналу и смешивают со своим секретом уже результат второй стороны (см. ниже), получая, таким образом, одинаковый “цвет”. Например, в английской “Википедии” сейчас дана именно такая иллюстрация.

(Source: Wikimedia)

Оказывается, такая картинка – не самый плохой способ объяснить что-то содержательное про протокол DH “на пальцах”, пусть некоторые требования и остаются за кадром. Например, эта схема не позволяет показать, почему атакующая сторона не может “перебрать все краски” (естественно, в практическом случае с числами).

Посмотрим на основные моменты, которые подразумевает имеющаяся картинка. Во-первых, результат смешивания красок должно быть трудно обратить – важнейшее свойство для DH, который строится на “однонаправленных” функциях (об этом написано на исходной картинке). То есть, сторона, наблюдающая обмен, не может простым способом разделить краски. Вспомните, что исходная краска, – которая соответствует генератору в “настоящем” DH, – известна всем, в том числе, стороне, пытающейся взломать обмен. По условию – выделить эту краску из смешанных “цветов” оказывается вычислительно невозможно. Во-вторых, операция смешивания красок должна быть “коммутативной” (условно!) – то есть, результат не отличается от порядка подмешивания ингредиентов сторонами. Это не менее важный математический момент “настоящего” протокола, который позволяет обобщить его и перенести с классических вычетов на совсем другие структуры.

Вообще, “коммутативность” тут именно в кавычках, поскольку математическая структура несколько сложнее. Запишем операцию в виде формулы, где “*” соответствует смешиванию красок и действует слева: α * G – означает, что секретная краска α смешана с краской G (чтобы как-то обосновать “левое и правое” действие – считаем, что колер α добавлен в банку к краске G). Тогда: β * (α * G) == α * (β * G) – это то, что происходит в протоколе с красками. То есть, сторона A получает результат смешивания (β * G) и замешивает свою краску α: α * (β * G). Сторона B – наоборот. Казалось бы, должно выполняться (α * β) == (β * α), тогда работает схема. Именно так устроено в классическом DH, но с показателями степенй: (G^β)^α == (G^α)^β. Однако для протокола на красках, вообще говоря, (α * β) == (β * α) хоть и очевидно работает в “локальном” случае, но не применимо в иллюстрируемой схеме – ведь ни у стороны A, ни у стороны B нет готового состава (α * β) – они не могут его приготовить по условию “неразделимости” красок. Вариант (α * β) * G провернуть не получится, по условиям задачи: краски – это не натуральные числа. Поэтому-то “коммутативность” тут – это не настоящая коммутативность (без кавычек). Требуется именно “одинаковость” действия и краски α, и краски β на уже смешанные и подходящие краски. Это можно переписать в других обозначениях: A := α * G (подмешали α в G); B := β * G (подмешали β в G); α * B == β * A – потребовали выполнения базового свойства, необходимого для работы протокола DH на красках: β переводит A в тот же цвет, в который α переводит B.

И это вовсе не беспричинно въедливое разбирательство. Любой химик вам подтвердит, что в химии – далеко не всегда порядок подмешивания ингредиентов не влияет на результат. Формулы веществ это хорошо, но иногда нарушение порядка смешивания может так повлиять, что лабораторию придётся ремонтировать или даже строить новую.

Дело не только в химии: именно обобщение структурной особенности, которая переводит две разных “краски” строго в одну при действии разными элементами (другими “красками”) как раз и позволяет максимально обобщить и сам протокол DH, переписав его в терминах того, что в математике называется “действием группы”. Это, впрочем, отдельная история.

С “красочной” иллюстрацией к DH связан и ещё один занимательный момент. Хорошо, разобрать смешанный “цвет” на составляющие краски трудно – это по условию задачи. Но что мешает атакующему перебрать все доступные краски, подмешивая их к исходной? Результаты смешивания сравниваются с переданными в открытом виде “цветами” (они соответствуют открытым ключам DH) – если цвет совпал, то угадана секретная краска. Естественный вариант защиты: красок слишком много – перебор окажется неприемлемо долгим, а вот сторонам протокола легко выбрать одну секретную краску. Это, опять же, важный математический момент протокола: краски выбрать может быть легко, – вот тысячи, допустим, банок стоят на складских полках, – но реальный DH работает не на красках и там тоже требуется, чтобы был вычислительно простой метод равновероятного случайного выбора нужного числа (секретной “краски”). Да, в классическом варианте с целыми числами – выбрать число случайно и равновероятно не трудно. Вот только тут возникает другая проблема.

Классический вариант DH требует возведения в степень. Показатель степени является секретным ключом. Чтобы атакующая сторона не могла перебрать все показатели за обозримое время, значение должно быть большим. Но как быть стороне протокола, вычисляющей открытый параметр при помощи того же возведения в степень? Последовательно умножать генератор столько же раз, сколько и атакующий – выглядит несколько абсурдно. Хорошо, что знание показателя степени позволяет использовать быстрые методы, построенные на возведении генератора в квадрат и домножении на генератор в “нечётных” случаях: например, чтобы возвести 2 в пятую степень нужно дважды возвести 2 в квадрат и домножить на 2 – (2^2)^2 * 2, это три умножения, а не четыре, как для 2*2*2*2*2. В красках этого нет, но для любого практического воплощения протокола DH данное свойство “удвоения со сложением” необходимо – иначе легитимные стороны протокола оказываются в том же положении, что и атакующая сторона.

Адрес записки: https://dxdt.ru/2025/06/19/15702/