Что такое «асимметричная криптография»

Привет! Это команда Eppie. Подробнее о нашем проекте бессерверной электронной почты можно почитать в этой статье. А здесь поговорим подробнее о криптографии.

Асимметричная криптография сейчас у всех на слуху благодаря бурному развитию Web3. Но мало кто понимает, как она на самом деле работает. Попробуем это исправить. Если вы давно хотели составить себе хотя бы поверхностное представление о современной криптографии, но Википедия не помогла — это статья для вас.

Будет немного формул, но текст рассчитан на читателей, владеющих математикой на уровне общеобразовательной школы, не сложнее.

Чтобы объяснить, что такое асимметричная криптография, начнем с симметричной.

Договоримся, что все виды данных в компьютере — текст, цвет, звук и все содержимое вашего профиля в Google — представлены числами. Шифрование в компьютере — это преобразование одного числа в другое с помощью математической операции. Например:

9 + 4 = 13

Можно сказать, что мы зашифровали число 9, прибавив к нему число 4 (оно в криптографии называется ключом) . Теперь можно произвести над шифром (13) обратную операцию, и мы получим исходный текст (9):

13 – 4 = 9

Самая примитивная схема шифрования — «шифр Цезаря» — устроена похожим образом: каждая буква в тексте смещаются на k позиций в алфавите. Так, если ключ k = 4, то «а» преобразуется в «д», «б» — в «е», и далее по кругу. Последние буквы в алфавите сдвигаются в начало, поэтому «я» с ключом 4 превратится в «г». Один участник переписки прибавляет k к каждой букве в сообщении, чтобы его зашифровать. Второй — расшифровывает его, отнимая от каждой буквы то же число. Таким образом слово «яблоко», зашифрованное методом Цезаря с ключом 4 превратится в «гептот».

Чтобы понимать друг друга, обе стороны должны владеть одним и тем же ключом. Поэтому такой способ шифрования называется симметричным. Момент передачи ключа — его самое слабое звено. В конце концов шифрование придумано для обмена секретной информацией по незащищенному каналу. Представьте: вы Цезарь, и вам нужно послать гонца с секретным сообщением к вашему генералу у стен Карфагена. Если вы уверены в преданности гонца, и в том, что по дороге его не перехватят враги — может быть, вам и не нужно шифрование. Если же у вас нет безопасного способа доставить сообщение, значит сообщение нужно зашифровать. Но встает вопрос: как передать ключ? Этот вопрос не потерял своей актуальности с появлением телеграфа, телефона и интернета. С античности и до изобретения асимметричной криптографии в 70-х годах XX века хорошего решения у нас не было. Передача ключей шифрования была дорогим и сложным в организации мероприятием.

В асимметричных криптографических алгоритмах для шифрования и расшифровки используют разные ключи. У каждого участника свой секретный ключ, известный только ему. Их не нужно (и нельзя) передавать. Это исключает возможность перехвата.

Вернемся к нашему уравнению.

9 + 4 = 13

Если мы знаем результат (13), одну из переменных (4) и операцию (+) , мы можем вычислить вторую, неизвестную, переменную с помощью обратной операции.

x + 4 = 13

x = 13 – 4

x = 9

Чтобы асимметричная криптография работала, нам нужно «защитить» x. То есть использовать такую математическую операцию, для которой не существует эффективного алгоритма вычисления неизвестной переменной, даже когда остальные значения известны. Для этого мы можем использовать, например, модульную арифметику.

Будем складывать по модулю N. Если сумма превышает N, результат будет равен разнице суммы и модуля. Допустим, модуль равен 12.

(9 + 4) mod 12 = 13 – 12 = 1

Наглядный пример такой операции — движение стрелки по циферблату. Когда стрелка доходит до последнего элемента (11 часов) , счет продолжается с нуля.

Теперь, чтобы найти (расшифровать) неизвестное слагаемое, нужно знать сумму по модулю, одно из слагаемых и значение модуля. Зная эти три параметра, мы все еще можем вычислить неизвестное слагаемое.

(9 + x) mod 12 = 1

(9 + x) — 12n = 1

где n показывает, сколько раз стрелка пересекла нулевую отметку. Если сумма двух чисел меньше 12, то стрелка не успела сделать полный круг, и n = 0. В нашем случае сумма равна 13, и n = 1. Поскольку оба слагаемых в конечной группе меньше модуля, n может принять всего два значения.

В первом случае x = -8, и это не может быть правильным ответом по условию (-8 нет на циферблате) , во втором x = 4, и это правильный ответ. Проверить два значения n несложно.

Теперь попробуем умножение. В конечной группе с умножением N должно быть простым числом. Поэтому пусть N = 11, а в качестве множителей возьмем 6 и 9.

(6 ⋅ 9) mod 11 = 54 mod 11 = 10

(11 помещается в 54 целиком 4 раза, а остаток — 10)

Пусть 9 — неизвестная величина. Чтобы ее вычислить, нужно решить уравнение:

(6 x) mod 11 = 10

Выше мы упомянули, что 10 — остаток от деления произведения на модуль. Это можно выразить вот так:

6x — 11n = 10

x = (10 + 11n) /6

В группе с умножением n может принимать значения от 0 до N-2. Будем подставлять все варианты n по очереди, пока x не окажется положительным целым числом, принадлежащим группе. В данном случае x = 9 при n = 4.

Обратите внимание, что в случае с умножением нужно перебрать уже 10 вариантов n. Полный перебор – самый неэффективный способ решения математической задачи: чем больше модуль, тем больше нужно времени на ее решение. Для умножения существуют другие, более «быстрые» алгоритмы решения, поэтому умножение не используется в криптографии. Используется частный случай умножения — возведение в степень. Для уравнения

a^x mod N = b

^ — оператор возведения в степень. Например, 2^2 значит «два в квадрате»

где a, b и N известны, пока не существует эффективного алгоритма вычисления x. Если модуль представляет собой число большого порядка, например 2^1024, подбор такого ключа на самом мощном современном компьютере займет миллиарды лет, и считается на практике невозможным.

Возведение в степень в конечной группе — это такое математическое преобразование, которое нельзя «провернуть обратно», чтобы получить исходные значения.

Еще одна важная особенность конечных групп, которая нам понадобится — ассоциативность, или, как учат в школе, «результат не зависит от расстановки скобок»:

((a b) c) mod N = (a (b c)) mod N

Давайте посмотрим, как это работает на реальном примере — в протоколе генерации совместного ключа Диффи-Хеллмана.

Итак, Алиса и Боб (традиционные имена в описании криптографических алгоритмов) хотят создать совместный (симметричный) ключ шифрования с таким условием, чтобы Ева (злоумышленник) могла полностью подслушать их разговор, но не могла воспроизвести ключ.

Боб звонит Алисе, и они договариваются о конечной группе с модулем N. На практике это всегда число большого порядка, но пусть в нашем примере

N = 17

Ева может узнать это число.

Алиса выбирает в группе случайное секретное число a, не сообщая его Бобу. А Боб выбирает случайное b. Эти числа называются «приватными ключами» Алисы и Боба, которые нельзя разглашать.

Предположим, что

a = 14

b = 11

Далее, Алиса и Боб выбирают «генератор» g — число из группы, обладающее определенными свойствами, которые мы здесь опустим. Генератор не нужно держать в секрете. Пусть в примере g = 3. Каждый участник возводит g в степень, равную своему приватному ключу.

Алиса вычисляет g^a = 3^14 = 4782969

Боб вычисляет g^b = 3^11= 177147

Если бы на этом этапе Алиса и Боб сообщили друг другу свои результаты, Ева могла бы вычислить секретные ключи с помощью логарифмирования:

log3(4782969) = 14

log3(177147) = 11

Но Алиса и Боб проводят вычисления по модулю N = 17. В таком случае

A = 3^14 mod 17 = 2

B = 3^11 mod 17 = 7

A и B — «публичные», или «открытые» ключи. Алиса и Боб сообщают их друг другу. Не существует эффективного алгоритма, который позволит Еве вычислить приватный ключ, зная все остальные параметры. В нашем примере N дает всего 16 вариантов для перебора, но, если N — число порядка 2^1024, перебор всех вариантов на практике невозможен.

Остался последний шаг: Алиса и Боб вычисляют совместный секретный ключ K, который они в дальнейшем и будут использовать для шифрования сообщений. Алиса возводит B (публичный ключ Боба) в степень, равную своему приватному ключу a по модулю N:

K = B^a mod N = 7^14 mod 17 = 8

Боб делает то же самое с публичным ключом Алисы и своим приватным:

K = A^b mod N = 2^11 mod 17 = 8

Совместный ключ K всегда совпадает, благодаря ассоциативности операции возведения в степень.

(g^a )^b = (g^b )^a = g^ab

При замене обычной операции на операцию в конечной группе это свойство сохраняется:

g^ab mod N = g^ba mod N

Теперь у Алисы и Боба есть совместный секретный ключ K. Это ключ для симметричного шифрования, но он был создан «асимметричным способом». При его генерации каждый использовал свой приватный ключ и публичный ключ собеседника. И Ева, владея всей публичной информацией, не может воспроизвести совместный секретный ключ шифрования.

Асимметричная криптография защищает вас прямо сейчас. Посмотрите на адресную строку браузера: префикс https (в отличие от устаревшего http) значит, что данные, передаваемые между вашим компьютером и сервером VC.ru, зашифрованы, а ключ шифрования был получен по протоколу Диффи-Хеллмана, о котором мы только что рассказали.

Технология цифровой подписи, которой вы пользуетесь при подаче налоговой декларации в электронном виде, тоже основана на приемах асимметричной криптографии.

Эти приемы можно использовать и в качестве альтернативы парольной аутентификации. Это распространено в криптовалютах и других Web3 сервисах. Например, механизм шифрования в децентрализованной почте или мессенджере упрощенно мог бы выглядеть так: публичный ключ пользователя — и есть его почтовый адрес в децентрализованной сети. Каждое письмо шифруются с помощью пары ключей — приватного ключа отправителя и публичного ключа (адреса) получателя. Получатель в свою очередь расшифровывает письмо с помощью публичного ключа отправителя и своего приватного.

В такой схеме, в отличие от парольной аутентификации, вам не нужно доказывать системе, что почтовый адрес принадлежит вам. В системе нет элемента, который принимает решение об аутентификации пользователя. Право доступа к почтовому ящику дает вам не сервер (которого не существует) а приватный ключ, который хранится только у вас. Он дает вам, единственному в мире, возможность расшифровать отправленные вам письма. Ваши ключи — ваши письма.

Если вас заинтересовал этот материал, подписывайтесь на наш блог и задавайте вопросы в комментариях. И, конечно, записывайтесь на бета-тест Eppie.