Проблема распределения ключей
Алиса и Боб хотят организовать секретную переписку. Это означает, что Алиса и Боб хотят читать сообщения, которые они отправляют друг другу, но не хотят, чтобы кто-то другой (например, Ева) мог их читать. Для обеспечения секретности они шифруют сообщения. Для этого Алиса и Боб должны иметь один и тот же ключ шифрования, благодаря которому они могут зашифровывать и расшифровывать сообщения. Ева, не имея этого ключа, не может читать их сообщения – для неё они представляют собой просто зашифрованную бессмыслицу.
Но каким образом Алисе и Бобу договориться о ключе? Они не могут просто переслать ключ по открытому каналу – тогда Ева перехватит ключ. В простейшем случае можно встретиться лично и передать ключ, но это:
- Небезопасно: ключ могут подсмотреть, украсть, его можно потерять
- Неудобно: что делать если Алиса и Боб в разных городах? Разных странах? Если это не люди, а например, компьютеры, которые хотят установить шифрованное соединение? Что если абонентов не два, а миллионы?
Итак, проблема состоит в следующем: могут ли Алиса и Боб, общаясь по открытому каналу, который прослушивает противник Ева, сгенерировать общий ключ таким образом, чтобы Ева не смогла его узнать?
Оказывается, это возможно и решается с помощью криптосистем с открытым ключом.
Открытый и закрытый ключ
Основная идея криптосистем с открытым ключом состоит в следующем: у каждого участника есть два ключа: закрытый и открытый. Закрытый ключ является секретным и его никому нельзя разглашать. Открытый ключ не является секретным: его можно разглашать и передавать по открытому каналу. Закрытый ключ генерируется участником самостоятельно (обычно случайно). Открытый ключ генерируется из закрытого с помощью специальных математических преобразований таким образом, что получить из закрытого ключа открытый легко, а получить из открытого ключа закрытый – очень сложно. Слова “легко” и “сложно” трактуются в криптографии в смысле теории сложности вычислений.
Вычислительная сложность
Решать вычислительную задачу можно различными алгоритмами. Чтобы понимать, какой алгоритм более эффективный, а какой – менее, нужно оценивать меру сложности алгоритмов. Важно, что эта мера относится именно к алгоритму и не связана с мощностью компьютера, на котором алгоритм будет выполняться, что позволяет корректно сравнивать алгоритмы между собой (даже неэффективный алгоритм может работать быстрее эффективного, если выполнять его на более мощном компьютере).
Под сложностью понимают функцию количества “элементарных операций” от параметра задачи, выражающего её “размер”. Обычно сложность алгоритма записывают в виде O-нотации
Пример:
Неформальная постановка задачи: Среди всех книг в библиотеке подсчитать количество книг, в которых более 100 страниц
Математическая постановка задачи: В множестве чисел (числа представляют собой количество страниц в каждой книге) найти количество чисел больших 100. Параметром размера задачи можно считать общее количество чисел (общее количество книг в библиотеке) – обозначим его $n$. Операциями - сравнения чисел
Алгоритм:
- Установить значение счётчика равное нулю
- Начать с первого числа
- Если число больше 100, то увеличить счётчик на 1
- Перейти к следующему числу и повторить с шага 3.
- Если числа кончились - выдать значение счётчика
В процессе работы алгоритм проанализирует длины всех книг, которых ровно $n$, поэтому сложность этого алгоритма $O(n)$.
Чем больше $n$ тем больше нужно будет совершить действий, но количество этих действий растёт с линейной скоростью от размера задачи.
∎
В криптографии “легкими”, “эффективными” и т. п. считаются задачи, которые имеют не более чем полиномиальную сложность. То есть количество действий растёт не быстрее, чем некоторый полином от размера задачи. Например, $O(n), O(n^2), O(log(n))$.“Сложными”, “трудными” и т.п. считаются задачи, имеющие сверхполиномиальную скорость роста. То есть количество действий растёт быстрее, чем какой-либо полином. Например $O(2^n), O(n!)$.
Одностронние функции
Существование криптографии с отрытым ключом основано на предположении о существовании односторонних функций
Односторонняя функция – математическая функция, которая легко вычисляется для любого входного значения, но сложно найти аргумент по заданному значению функции. Открытый ключ получается из закрытого с помощью применения одностронней функции. В этом случае получить из открытого ключа закрытый означает обратить функцию, что трудно по определению.
Существование или отсутствие односторонних функций не доказано и является открытой математической проблемой. В криптографии используют функции-кандидаты в одностронние функции: хорошо изученные функции, для которых не известно эффективных алгоритмов решения. Если для какой-то из функций будет найден полиномиальный алгоритм решения, то криптосистемы, основанные на этой функции, перестанут считаться безопасными
Кандидаты в одностронние функции
Разложение на множители
Функция принимает на вход два простых числа – $p$ и $q$ и выдаёт на выходе их произведение $f(p, q) = pq$. Параметром задачи является длина чисел в двоичном представлении $n$. Перемножение двух числе даже простым алгоритмом “в столбик” имеет сложность $O(n^2)$. Для разложения на множители не известно алгоритма с полиномиальной сложностью
Дискретное логарифмирование
Функция принимает на вход простое число $p$ целое число $0 \lt x \lt p$ и целое число $0 \lt a \lt p - 1$. Результатом является $f(x, p) = a^x \bmod p $
Строго
$G$ – конечная циклическая группа, $a$ – порождающий элемент, $x$ – натуральное число. $f(x, a) = a^x$Сложность задач понимается в общем случае. Существуют числа, которые легко разложить на множители (например, чётные) или множества, в которых легко решается задача дискретного логарифмирования. Но в общем случае эффективного алгоритма решения не известно.
Протокол Диффи-Хеллмана
Протокол Диффи-Хеллмана решает проблему генерации общего ключа с передачей данных по открытому каналу. Этот протокол произвёл революцию в криптографии и фактически положил начало широкому распространению криптографии с открытым ключом.
Параметры:
$p$ – простое число
$0 \lt g \lt p$ – порождающий элемент группы $Z(p)$
Проще
Если не понятно, что такое порождающий элемент, то можно считать, что это просто число, выбранное по известному алгоритму.Эти значения не секретные, их можно передавать по открытому каналу. Как правило, их генерирует один из участников и передаёт второму.
Протокол:
- Алиса генерирует случайно секретный ключ $0 \lt a \lt p$
- Алиса вычисляет публичный ключ $A = g^a \bmod p$ и передаёт его Бобу
- Боб генерирует случайно секретный ключ $0 \lt b \lt p$
- Боб вычисляет публичный ключ $B = g^b \bmod p$ и передаёт его Алисе
- Алиса вычисляет $B^a \bmod p = (g^a)^b \bmod p = g^{ab} \bmod p$
- Боб вычисляет $A^b \bmod p = (g^b)^a \bmod p = g^{ab} \bmod p$
В результате Алиса и Боб сгенерировали общее значение $g^{ab}$
При этом по открытому каналу передавались числа $A = g^a \bmod p$ и $B = g^b \bmod p$. Задача вычислить на основании них значение $g^{ab} \bmod p$ является сложной задачей (задача Диффи-Хеллмана), она тесно связана с задачей дискретного логарифмирования.
Пример:
Параметры: $p = 23, g = 5$
- Алиса генерирует секретный ключ: $a = 7$
- Боб генерирует секретный ключ: $b = 6$
- Алиса вычисляет открытый ключ и посылает его Бобу: $A = 5^7 \bmod 23 = 17$
- Боб вычисляет открытый ключ и посылает его Алисе: $B = 5^6 \bmod 23= 8$
- Алиса вычисляет общий ключ: $B^a = 8^7 \bmod 23 = 12$
- Боб вычисляет общий ключ: $A^b = 17^6 \bmod 23= 12$
∎
Заключение
В криптосистемах с открытым ключом у каждого участника есть два ключа: открытый и закрытый. Закрытый держится в секрете, а открытый распространяется свободно. Ключи связаны специальными математическими соотношениями таким образом, что из секретного ключа легко получить открытый, а из открытого нельзя получить секретный.
Протокол Диффи-Хеллмана решает проблему генерации общего ключа с передачей данных по открытому каналу. Это простой и показательный, но далеко не единственный пример криптосистемы с открытым ключом. В дальнейшем идея получила сильное развитие, существует множество криптографических протоколов, решающих самые разнообразные задачи.
