Криптография с открытым ключом

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

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

Обычно в криптографии с открытым ключом ключи длиннее, а алгоритмы медленнее, чем в симметричном шифровании. Но криптография с открытым ключом позволяет делать то, что невозможно при симметричном шифровании.

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

Обозначим через $a \mod b$ остаток при делении $a$ на $b$. Здесь $b$ называется модулем. Например, $12 \mod 5 = 2$ и $77 \mod 8 = 5$.

Также мы используем простые числа. Целое число больше 1 является простым, если оно делится только на 1 и на само себя. Например, 7, 101 и 7823 — простые числа, а 6, 15 и 100 — нет.

Для данных целых $a$, $b$ и $c$ легко, по крайней мере в принципе, вычислить $a^b \mod c$. Это модульное возведение в степень относительно легко выполнять даже тогда, когда целые $a$, $b$ и $c$ очень велики. При больших $a$ и $b$ степень $a^b$ становится огромной. К счастью, нам не нужно вычислять это огромное число целиком. Вместо этого можно вычислять остаток для каждого промежуточного значения перед продолжением. Рассмотрим простой пример: $a = 2$, $b = 60$, $c = 1003$. Тогда $a^b = (2^{10})^6$.

Сначала вычисляем $2^{10}=1024$. Затем берем остаток этого промежуточного результата: $1024 \mod 1003 = 21$. Далее возводим 21 в степень 3. Результат — 9261. Снова берем остаток по модулю 1003 и получаем 234. Последний шаг — возвести 234 в степень 2: результат 54756. Снова взяв остаток, получаем итоговый результат: $a^b \mod c = 594$.

С другой стороны, когда даны произвольные целые $a$, $c$ и $d$, очень трудно найти целое $b$, такое что $a^b \mod c = d$. Эта задача называется задачей дискретного логарифмирования. Мы используем обозначение

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

Посмотрим ближе на дискретный логарифм на малых числах. Выберем $c = 101$ и ниже увидим график, изображающий $2^x \mod 101$.

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

Протокол согласования ключей — это метод, с помощью которого две стороны, скажем Alice и Bob, договариваются об общем секретном ключе через небезопасный канал, но так, чтобы никто другой, подслушивающий канал, не смог узнать общий секрет. Пример такого метода — протокол согласования ключей Diffie-Hellman.

Обмен ключами Diffie-Hellman начинается с того, что Alice и Bob договариваются о модуле $p$ и числе $g$. Затем Alice выбирает случайное число $a$ и отправляет Bob число $g^a \mod p = u$. Аналогично Bob выбирает случайное число $b$ и отправляет Alice число $g^b \mod p = v$. Теперь Alice может вычислить $v^a \mod p$, а Bob — $u^b \mod p$. Оба значения равны $g^{ab} \mod p$, и это значение можно использовать как новый общий секретный ключ.

В нашем HTTPS-примере (TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384_256 bit keys,TLS 1.2) используется определенный вариант обмена ключами Diffie-Hellman.

RSA

Теперь посмотрим, как выглядят криптосистемы с открытым ключом. Наиболее распространенная система называется RSA. Она основана на следующем математическом факте:

Если $p$ и $q$ — простые числа, а $e$ и $d$ таковы, что

то для всех значений $x$ выполняется $x^{e \cdot d} \mod n = x$, где $n = p \cdot q$.

Чтобы создать ключи RSA, Alice сначала должна найти два больших простых числа $p$ и $q$. Оба простых числа должны быть длиной не менее 1000 бит. Затем ей нужно выбрать целое $e$, такое что можно найти другое целое $d$, для которого выполняется

Открытый ключ Alice теперь является парой $(e, n)$, где $n = p\cdot q$. Закрытый ключ, который Alice нужен для расшифрования сообщений, — это пара $(d,n)$. Alice не должна раскрывать простые числа $p$ и $q$ никому.

Предположим, что Alice передала свой открытый ключ Bob. Теперь Bob может зашифровать любое "сообщение" $x$, которое закодировано как целое число от 0 до $n$, вычислив $x^e \mod n = y$. Bob отправит результат Alice. Alice может расшифровать шифртекст $y$, потому что знает секретную расшифровывающую экспоненту $d$. Она вычисляет $y^d \mod n = x$.

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

RSA также можно использовать для цифровой подписи и проверки. Alice раскрывает ключ проверки $(e,n)$, а сама использует ключ подписи $(d,n)$. Если Alice хочет подписать сообщение $x$, она вычисляет подпись как $x^d \mod n = s$. Когда Bob получает сообщение $x$ и подпись $s$, он может проверить, что $s^e \mod n = x$. Если это верно, то подпись должна быть от Alice, потому что никто другой не знает параметр $d$, который необходим для вычисления подписей Alice.

Обычно подпись вычисляется не для всего сообщения. Вместо этого сначала вычисляется хэш сообщения, а затем подписывается хэш-значение. Это гарантирует, что подписываемое значение не станет слишком большим. На стороне проверки полученное сообщение аналогично сначала подается на вход хэш-функции, и параллельно к подписи применяется ключ проверки $(e,n)$. Если выходы обеих операций равны, подпись принимается. Хэш-значение сообщения называется его отпечатком, и его можно использовать вместо всего сообщения, если для хэш-функции не найдены коллизии.

В нашем HTTPS-примере (TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384_256 bit keys,TLS 1.2) RSA используется для цифровых подписей.

Вы дошли до конца этого раздела! Перейти к следующему разделу:

Не забудьте проверить свои баллы в индикаторе в правом нижнем углу материала!