11. Криптография

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

Более формально, пусть Алиса хочет послать Бобу секретное сообщение - битовую строку $x$. Она шифрует её с помощью некоторой функции $E(\cdot)$ (от англ. encoder) и посылает Бобу зашифрованное сообщение $E(x)$. Боб использует функцию $D(\cdot)$ (от англ. decoder), чтобы восстановить исходное сообщение: $D(E(x))=x$.

Алиса и Боб хотят, чтобы Ева, даже подслушав $E(x)$, не получила никакой информации $\circ x$.

Обычно считается, что функции $E(\cdot), D(\cdot)$ вычисляются при помощи некоторых известных всем (в том числе Еве) алгоритмов, но результат вычислений зависит от некоторых параметров - ключей, известных только Алисе и Бобу. Это правило известно как принцип Керкгоффса (1883). Такая схема обмена сообщениями оказывается более гибкой: если бы вся сложность расшифровки сообщения состояла в том, что Еве неизвестны алгоритмы, которыми пользуются Алиса и Боб, то, если бы Ева откуда-то узнала эти алгоритмы, Алисе и Бобу пришлось бы с нуля договариваться о новой схеме. Если же алгоритмы известны всем, и Ева откуда-то узнаёт ключи, то достаточно поменять ключи, не меняя всю схему целиком.

Схемы с закрытым ключом

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

Одноразовый блокнот

В этом протоколе шифрования Алиса и Боб заранее встречаются и выбирают битовую строку $r$ той же длины, что и будущее сообщение $x$. Тогда шифрование сообщения состоит в побитовом сложении (xor) сообщения с ключом: $E_{r}(x)=x \oplus r$. Расшифровка устроена ровно так же: $D_{r}(x)=x \oplus r$, тогда $D_{r}\left(E_{r}(x)\right)=D_{r}(x \oplus r)=x \oplus r \oplus r=x$.

Если выбирать каждый бит $r$ случайно равновероятно, то все биты $E_{r}(x)=x \oplus r$ также будут равны 0 или 1 равновероятно, так что зашифрованное сообщение не даст Еве никакой информации (оно могло получиться из каждого сообщения $x$ с одной и той же вероятностью).

Недостаток схемы состоит в том, что таким $r$ можно воспользоваться лишь один раз: если передать два сообщения $x$ и $z$, пользуясь одним $r$, то Ева узнает $x \oplus z=(x \oplus r) \oplus(z \oplus r)$. Отсюда уже можно извлечь полезную информацию: например, если в одном из сообщений есть длинная последовательность нулей, то в $x \oplus z$ на том же месте будет просто кусок другого сообщения. Известна история проекта “Venona”, в рамках которого американцы во время холодной войны расшифровали многие сообщения советских разведчиков, пользуясь в том числе тем, что те иногда переиспользовали одноразовые блокноты.

Если Алиса и Боб хотят передать много сообщений, им нужно заранее запастись очень большим общим набором случайных бит, что непрактично.

Блочные шифры

Существует целое семейство блочных шифров, устроенных по следующей схеме: Алиса и Боб заранее выбирают секретный ключ - случайную строку $r$, но уже фиксированной длины (например, 128 бит). Сообщение делится на блоки одинаковой длины (например, тоже по 128 бит), после чего каждый из блоков шифруется одной и той же сложно устроенной обратимой функцией $E_{r}(\cdot)$.

Примерно так устроены, например, следующие схемы шифрования:

AES (advanced encryption standard) - симметричный алгоритм шифрования, принятый в 2001 году в качестве стандарта шифрования правительством США;
симметричные шифры “Кузнечик” и “Магма” входят в ГОСТ 34.12-2018, принятый в качестве стандарта шифрования на территории России и СНГ.

Предполагается, что несмотря на то, что один и тот же ключ используется для шифрования многих блоков, воспользоваться этим для расшифровки сообщений, как в случае с одноразовым блокнотом, не удастся, потому что функция $E_{r}(\cdot)$ устроена достаточно сложно. Одним из важных свойств такой функции является лавинный эффект при изменении одного бита $x$ должны меняться в среднем порядка половины бит $E_{r}(x)$. Если это не так, то по зашифрованным данным можно пытаться восстановить исходные сообщения с помощью статистического анализа.

Схемы с открытым ключом

У симметричных схем есть следующий недостаток: для того, чтобы договориться о секретном ключе, Алисе и Бобу всё равно нужно как-то поговорить без свидетелей до того, как схема начнёт ими использоваться. Непонятно, что же им делать, если они никогда раньше не общались, и Ева может читать их переписку с самого начала.

В 1970-е годы было открыто сразу несколько схем, позволяющих Алисе и Бобу начать общаться, не договариваясь ни о каких секретных ключах заранее. Эти схемы стали называть асимметричными, или схемами с открытым ключом.

В общих чертах схемы с открытым ключом устроены примерно так: для того, чтобы Алиса могла передавать Бобу сообщения, Боб выбирает два ключа - закрытый, который он не показывает никому (даже Алисе); и открытый, который он показывает Алисе или даже публикует в открытом доступе. При этом функция шифрования сообщения $E(\cdot)$ использует открытый ключ, а функция расшифровки $D(\cdot)$ - закрытый.

Пусть Алиса хочет отправить Бобу сообщение $x$. Алиса, пользуясь открытым ключом, отправляет Бобу зашифрованное сообщение $E(x)$. Боб, пользуясь известным только ему закрытым ключом, расшифровывает сообщение: $D(E(x))=x$.

Важно, чтобы только Боб мог вычислять значения функции $D(\cdot)$ за разумное время (то есть, не обладая закрытым ключом, функцию $E(\cdot)$ должно быть очень сложно обратить). Для достижения такого эффекта обычно используют задачи, которые не умеют решать быстро (например, задачу факторизации числа).

Заметим, что, поскольку открытый ключ доступен вообще всем, не только Алиса, а вообще кто угодно может посылать сообщения Бобу, не опасаясь, что их сможет прочитать кто-то, кроме Боба.

Для того, чтобы Боб мог посылать сообщения Алисе, ей тоже нужно выбрать открытый и закрытый ключи, и опубликовать открытый ключ.

RSA

Одной из первых асимметричных схем была RSA (Rivest, Shamir, Adleman, 1977). Она основана на том, что генерировать большие простые числа умеют быстро, а вот быстро раскладывать числа на простые множители не умеют.

Протокол RSA

Боб выбирает открытый и закрытый ключи:
Боб выбирает два случайных больших простых числа $p \neq q$, вычисляет $n=p q$, $\varphi(n)=(p-1)(q-1)$.
Боб выбирает $e$, взаимно простое с $\varphi(n)$. Обычно берётся небольшое $e$, чтобы шифрование занимало меньше времени. Боб публикует пару ( $n, e$ ) - открытый ключ.
Боб вычисляет $d$, обратное к $e$ по модулю $\varphi(n): d e \equiv 1(\bmod \varphi(n))$. Пара $(n, d)$ - закрытый ключ Боба.
Алиса хочет передать Бобу сообщение $x$. Считаем, что $0 \leqslant x
Боб получает $y$, и, пользуясь закрытым ключом, вычисляет $D(y)=y^{d} \bmod n=$ $x^{d e} \bmod n$.

Лемма

Пусть $n=p q$, где $p \neq q$ - простые; $d$, $e$ - такие, что $d e \equiv 1(\bmod \varphi(n))$. Тогда $x^{d e} \equiv x(\bmod n)$ для любого $0 \leqslant x < n$.

Доказательство

Если $x$ делится на $p$, то $x^{d e} \equiv 0 \equiv x(\bmod p)$. Иначе $x^{d e} \equiv x(\bmod p)$ по малой теореме Ферма, так как $d e-1$ делится на $\varphi(n)$, то есть и на $p-1$. Аналогично, $x^{d e} \equiv x(\bmod q)$, тогда $x^{d e}-x$ делится на $p q=n$.

✍️ Заметим, что доля $x$, не взаимно простых с $n$, не превосходит $\frac{1}{p}+\frac{1}{q}$, что для больших $p, q$ пренебрежимо мало (если мы наткнулись на такой $x$, то мы случайно факторизовали $n$ ). Для $x$, взаимно простых с $n$, утверждение леммы сразу же следует из теоремы Эйлера: $x^{d e}=x^{k \varphi(n)+1} \equiv x(\bmod n)$.

Предполагается, что Ева, даже если перехватит сообщение, не сможет по доступным ей $n, e, x^{e} \bmod n$ восстановить $x$ за разумное время. Можно было бы факторизовать $n$, после чего найти $d$ так же, как это сделал Боб, но факторизовать числа быстро не умеют. Также неизвестно, можно ли решить задачу восстановления $x$ по $n, e, x^{e} \bmod n$ быстрее каким-то другим способом.

При этом все шаги, выполняемые Алисой и Бобом, можно делать быстро (пусть $n$ состоит из $b$ бит):

Быстро генерировать случайные числа заданной длины мы уже умеем;
$d$, обратное к $e$ по модулю $\varphi(n)$, можно вычислить с помощью расширенного алгоритма Евклида за $O\left(b^{2}\right)$;
шифрование и расшифровка сообщения осуществляется возведением в степень по модулю за $O(b \cdot M(b))$.

Есть ещё множество тонкостей, к которым прибегают, чтобы защититься от известных методов атак на этот алгоритм шифрования (например, $d$ должно быть не слишком мало, а $p$ и $q$ должны быть большими, но не слишком близкими друг к другу; $\varphi(n)=(p-1)(q-1)$ не должно состоять только из маленьких делителей;…). Мы о них подробно говорить не будем. Отметим лишь, что в настоящее время рекомендуется использовать $n$, состоящее хотя бы из 2048 бит.

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

Цифровая подпись

Пусть Бобу пришло сообщение якобы от Алисы, и он хочет убедиться, что его послала именно Алиса, а не кто-то другой. С помощью схемы с открытым ключом Алиса может “подписать” своё сообщение так, как это не может сделать никто другой (то есть такую подпись можно использовать как доказательство того, что автор сообщения - Алиса). Делается это следующим образом:

Протокол цифровой подписи

У Алисы есть открытый и закрытый ключи, она хочет послать Бобу сообщение $x$. Алиса вычисляет цифровую подпись $\sigma=D(x)$, пользуясь закрытым ключом, и посылает Бобу пару ( $x, \sigma$ ), состоящую из сообщения и подписи.
Боб, пользуясь открытым ключом, проверяет равенство $E(\sigma)=x$. Если равенство выполняется, сообщение действительно пришло от Алисы; если нет, то сообщение было повреждено при пересылке, либо было отправлено кем-то другим.

✍️ От схемы требуется, чтобы выполнялось равенство $E(D(x))=x$ для любых $x$. Мы же ранее требовали немного другое условие: $D(E(x))=x$ для любого $x$. Но в случае, когда $D(\cdot), E(\cdot)$ - биекции (а это, как правило, так) первое следует из второго.

Цифровая подпись подтверждает не только то, что автор сообщения именно тот, за кого он себя выдаёт, но ещё и то, что сообщение не было изменено в процессе пересылки.

Можно одновременно подписывать сообщение $x$ и пересылать его в зашифрованном виде: Алиса, пользуясь своим закрытым ключом, вычисляет подпись, после чего шифрует сообщение и подпись с помощью открытого ключа Боба и отправляет зашифрованные сообщение и подпись Бобу. Боб расшифровывает сообщение и подпись с помощью своего закрытого ключа, после чего проверяет подпись с помощью открытого ключа Алисы.

Криптографические хеш-функции

На практике обычно подпись вычисляют не от самого сообщения $x$, а от $h(x)$, где $h(\cdot)$ специальная хеш-функция. Тогда получатель может вычислить ту же хеш-функцию от полученного сообщения, и проверить корректность подписи. Смысл в том, что такая подпись намного короче подписи, вычисленной от самого сообщения.

Что требуется от используемой хеш-функции $h(\cdot)$ ? Одно из требований звучит так: нужно, чтобы по значению $h(x)$ было сложно подобрать такое $y$, что $h(x)=h(y)$ (иначе сообщение можно будет подделать).

Цифровой сертификат

Есть ещё одна проблема: Ева может попытаться выдать себя за Алису, например, подменив лежащий в открытом доступе ключ Алисы на свой.

Эту проблему решают следующим образом: создаётся сертификат, в котором содержится информация об открытом ключе Алисы и о самой Алисе, после чего этот сертификат подписывается некоторой стороной, которой все доверяют, и открытый ключ которой всем известен. Поскольку сертификат подписан тем, кому Боб доверяет, он может быть уверен, что открытый ключ в сертификате действительно принадлежит Алисе.

На практике в качестве этой стороны выступают специальные центры сертификации (англ. certification authority).

Протокол Диффи-Хеллмана

Поговорим о схемах с открытым ключом, пользующихся отсутствием известных эффективных решений другой задачи - задачи дискретного логарифмирования. Схема Диффи-Хеллмана (Diffie, Hellman, 1976) была опубликована на год раньше RSA; она позволяет Алисе и Бобу создать общий секретный ключ, общаясь по открытым каналам (которые может подслушивать Ева).

Протокол Диффи-Хеллмана

Алиса и Боб договариваются использовать простой модуль $p$, а также $g$ с достаточном большим $\operatorname{ord}_{p}(g)$ - порядком по модулю $p$ (минимальным $k>0$ таким, что $\left.g^{k} \equiv 1(\bmod p)\right)$.
Алиса выбирает случайное число $a$, а Боб выбирает случайное число $b$.
Алиса отправляет Бобу $x=g^{a} \bmod p$, а Боб отправляет Алисе $y=g^{b} \bmod p$.
Алиса вычисляет $y^{a} \bmod p=g^{a b} \bmod p$, Боб вычисляет $x^{b} \bmod p=g^{a b} \bmod p$. $g^{a b} \bmod p-$ их общий секретный ключ.

✍️ Часто утверждают, что в качестве $g$ нужно брать первообразный корень по модулю p. На самом деле это не обязательное условие, достаточно, чтобы $\operatorname{ord}_{p}(g)$ имел большой простой делитель.

Предполагается, что по $p, g, g^{a} \bmod p, g^{b} \bmod p$ не получится найти $g^{a b} \bmod p$ за разумное время. Можно было бы решить задачу дискретного логарифмирования, то есть восстановить $a$ по $g$ и $g^{a} \bmod p$, аналогично восстановить $b$, после чего вычислить $g^{a b} \bmod p$ уже будет несложно. $a$ и $b$ выбираются достаточно большими, чтобы это нельзя было сделать простым перебором. Неизвестно, можно ли решать задачу дискретного логарифмирования быстро, и можно ли быстро найти $g^{a b} \bmod p$ каким-то другим способом.

$p$ и $g$ обычно выбираются сильно заранее, и считаются известными всем (в том числе Еве). Популярный вариант - использовать такое простое $p$, что $q=\frac{p-1}{2}$ тоже простое (такие $q$ называются числами Софи Жермен). Тогда в качестве $g$ можно взять случайное число из отрезка $[2, p-2]$ - порядок любого взаимно простого с $p$ числа (кроме $p-1$ ) будет не меньше $q$.

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

Схема Эль-Гамаля

Ещё одна асимметричная схема для передачи шифрованных сообщений - схема ЭльГамаля (Elgamal, 1985), основанная на схеме Диффи-Хеллмана.

Протокол Эль-Гамаля

Боб выбирает открытый и закрытый ключи:
Алиса и Боб заранее договариваются о таких же $p$ и $g$, как в протоколе ДиффиХеллмана.
Боб выбирает случайное число $a$ - закрытый ключ Боба.
Боб передаёт Алисе (или публикует) открытый ключ - $h=g^{a} \bmod p$.
Алиса хочет передать Бобу сообщение $x$. Считаем, что $x$ - элемент циклической группы, порождённой $g$ (детали того, как сопоставлять произвольному сообщению элемент группы, порождённой $g$, мы опустим). Алиса выбирает случайное число $b$, и передаёт Бобу пару $(y, z)=\left(g^{b} \bmod p, x h^{b} \bmod p\right)$.
Боб получает пару $(y, z)$ и, пользуясь закрытым ключом, вычисляет $y^{-a} z \bmod p=$ $g^{-a b} g^{a b} x \bmod p=x$.

Как и в протоколе Диффи-Хеллмана, $a$ и $b$ выбирают достаточно большими, чтобы их нельзя было восстановить по $g^{a} \bmod p, g^{b} \bmod p$ простым перебором. Как и схема Диффи-Хеллмана, схема Эль-Гамаля безопасна в предположении того, что не существует эффективных решений задачи дискретного логарифмирования.

Если Алиса будет использовать одно и то же $b$ много раз, и Еве как-то удастся узнать содержание одного из старых сообщений, то она сможет перехватывать все новые сообщения (так как если Ева узнала $x$, то она может вычислить $z x^{-1} \bmod p=h^{b} \bmod p$ с с помощью чего она сможет расшифровывать все последующие сообщения, зашифрованные с помощью того же $b$ ). Поэтому важно каждый раз использовать новое $b$, в связи с чем $b$ часто называют эфемерным ключом.