Когда мы говорили о теории кодирования, одним из разделов называлось криптографическое кодирование. Собственно, криптография дословно означает “скрытое письмо”. Задача криптографии в общем – обеспечить защиту информации.
В более общем ключе, вопросами защиты информации посредством её преобразования занимается криптология. Криптология в свою очередь включает в себя дисциплины криптографии и криптоанализа. Первая, соответственно, занимается разработкой методов шифрования, вторая – оценкой сильных и слабых сторон методов шифрования и разработкой методов взлома криптосистем.
- Шифрование
- обратимое преобразование информации в целях сокрытия от неавторизованных лиц, при этом с предоставлением авторизованным лицам доступа к ней.
- Криптосистема
- (шифр) система обратимых преобразований, зависящая от некоторого секретного параметра и предназначенная для обеспечения секретности передаваемой информации.
- система защиты информации, использующая криптографические средства.
Помимо обеспечения конфиденциальности информации посредством шифрования, криптосистемы так же обеспечивают аутентификацию различных аспектов информационного взаимодействия.
В рамках модели угроз, используемой в криптологии, рассматриваются исключительно преднамеренные действия противника или недобросовестного участника информационного взаимодействия. Случайное искажение информации вследствие помех и пр. не рассматривается.
Основные аспекты криптографии
Исторически, криптография появилась сильно раньше цифровых информационных систем и использовалась в основном для обеспечения тайны переписки. Однако исторические алгоритмы шифрования полагаются в основном на неизвестность алгоритма третьей стороне, что делает их непригодными в современных реалиях.
Современные шифры не полагаются на тайну алгоритма – все широко используемые алгоритмы опубликованы во множестве открытых источников. Вместо этого, современные криптосистемы используют т.н. ключ – некоторое значение, выбранное (возможно случайно) из множества возможных значений, называемого пространством ключей.
- Симметричное шифрование
- Если для шифрования и дешифрования используется один и тот же ключ, такой шифр называется симметричным. Такие шифры так же называются шифрами с секретным ключом.
- Асимметричное шифрование
- Если для шифрования и дешифрования используются разные ключи, то такой шифр называется асимметричным. Такие шифры так же называются шифрами с открытым ключом.
- Шифротекст
- Сообщение после шифрования называется шифротекстом.
Основные аспекты криптоанализа
Основное предположение современного криптоанализа состоит в следующем: безопасность полностью определяется ключом. По сути, в рамках этого предположения, атакующему (криптоаналитику) известны все детали работы алгоритма, и доступен некоторый объём шифротекстов или даже возможность генерировать шифротексты по желанию.
Собственно, есть несколько типовых подходов к задаче криптоанализа.
Вскрытие на основе шифротекста.
Атакующий имеет описание алгоритма и некоторое (возможно большое) число зашифрованных одним ключом шифротекстов.
Требуется найти либо исходные сообщения для всех или нескольких шифротекстов, восстановить исходный ключ, либо построить алгоритм, позволяющий дешифровать новый шифротекст.
Вскрытие на основе открытого текста
Атакующий имеет описание алгоритма и некоторое (возможно большое) число зашифрованных одним ключом шифротекстов и соответствующих им исходных сообщений.
Требуется найти исходный ключ, либо построить алгоритм, позволяющий дешифровать новый шифротекст.
Вскрытие на основе выбранного открытого текста.
Атакующий имеет описание алгоритма и возможность получить шифротексты для некоторого (возможно большого) числа произвольных сообщений, единовременно, либо итеративно (тогда вскрытие называется адаптивным).
Требуется найти исходный ключ, либо построить алгоритм, позволяющий дешифровать новый шифротекст.
Вскрытие на основе выбранного шифротекста
Атакующий имеет описание алгоритма и возможность получить исходные сообщения для некоторого (возможно большого) числа произвольных шифротекстов.
Требуется найти исходный ключ, либо построить алгоритм, позволяющий дешифровать новый шифротекст.
Успешность криптоанализа может варьироваться (по классификации Кнудсена):
- Полное вскрытие. Получен ключ.
- Глобальная дедукция. Получен альтернативный алгоритм дешифрования без ключа.
- Локальная дедукция. Для одного шифротекста получено исходное сообщение.
- Информационная дедукция. Получена некоторая информация о ключе или сообщении.
Модели криптографии
В моделях криптографии часто используют обозначение “Алиса” (“А”) для отправителя, “Боб” (“B”) для получателя, и “Эва” (“E”) для криптоаналитика.
Модель симметричного шифра. Здесь \(M\) – исходное сообщение, \(C\) – шифротекст, \(k\) – ключ, \(f\) – функция шифрования, \(f^{-1}\) – фнукция дешифрования.
Модель асимметричного шифра. Здесь \(M\) – исходное сообщение, \(C\) – шифротекст, \(p\) – публичный ключ, \(s\) – секретный ключ, \(f\) – функция шифрования, \(f^{-1}\) – фнукция дешифрования, \(K\) – алгоритм выработки пары ключей \((p, s)\).
Стойкость симметричных систем
Свойство устойчивости криптосистемы к вскрытию принято называть криптостойкостью или просто стойкостью.
В теоретико-информационной модели криптосистемы, исходное сообщение \(M\) полагается случайным \(l\)-вектором из ансамбля \(X\) с алфавитом размерности \(\nu\) и некоторым распределением вероятностей \(P(X)\). Шифротекст \(С\) считается \(l\)-вектором с алфавитом размерности \(\mu\). Ключ \(k\) – случайным \(n\)-вектором из ансамбля \(K\) с алфавитом шифротекста и распределением \(P(K)\).
Фактически, \(C = f(X, k)\). Однако, с точки зрения криптоаналитика, не знающего ключа \(k\), шифротекст представляет из себя случайный вектор \(Y\).
Симметричный шифр называется совершенно криптостойким, если апостериорное распределение вероятностей исходного случайного сообщения \(M\) при регистрации случайного шифротекста \(C\) совпадает с априорным: \[\forall M \in X, k \in K: P(M | C) = P(M),\] то есть, для криптоаналитика, вероятность того, что было отправлено сообщение \(M\) не меняется при наблюдении шифротекста \(C\).
Смысл этого условия в том, что перехват шифротекста не даёт дополнительной информации об исходном сообщении.
- Теорема
Необходимое и достаточное условие совершенной криптостойкости в том, что \[\forall M\in X, C=f(M, k): P(C|M) = P(C)\]
\(\Delta\): Тривиально по теореме Байеса.
В терминах информационной энтропии, можно записать
\[H(X | Y) = H(X),\] \[H(Y | X) = H(Y),\] то есть, \[I(X; Y) = I(Y; X) = 0.\]
- Лемма
Для любой детерминированной криптосистемы, \[H(X|Y) \le H(K|Y)\] \[H(Y|X) \le H(K|X)\]
\(\Delta\): Рассмотрим \(H(KX|Y)\) и \(H(KY|X)\): \[\begin{align} H(X|Y) \le H(KX|Y) & = H(KXY) - H(Y) \\& = H(X|KY) + H(KY) - H(Y) \\& = H(X|KY) + H(K|Y) \end{align}\] \[\begin{align} H(Y|X) \le H(KY|X) & = H(KXY) - H(X) \\& = H(Y|KX) + H(KX) - H(X) \\& = H(Y|KY) + H(K|X) \end{align}\] Поскольку \(C=f(M,k)\) детерминированная обратимая функция, \(H(Y|KX) = H(X|KY) = 0,\) тогда \[H(X|Y) \le H(K|Y)\] \[H(Y|X) \le H(K|X)\] \(\not\Delta\)
- Теорема
Необходимым условием совершенной криптостойкости является: \[H(K) \ge H(X),\] \[H(K) \ge H(Y).\]
\(\Delta\): Система совершенно криптостойкая тогда и только тогда, когда \(H(X)=H(X|Y)\) и (эквивалентно) \(H(Y)=H(Y|X)\). Тогда,
\[H(X) = H(X|Y) \le H(K|Y) \le H(K)\] \[H(Y) = H(Y|X) \le H(K|X) \le H(K)\]
\(\not\Delta\)
Требование \(H(K) \ge H(X)\) выливается в следующее. \(H(X) \le \log |X|\), в худшем случае \(H(X) = \log |X|\). \(H(K) \le \log |K|\). Тогда \[\log |K| \ge \log |X|,\] \[|K| \ge |X|.\]
С практической точки зрения интересен граничный случай \(|K| = |X|\), тогда \(H(K) = \log |K|\) и следовательно \(\forall k \in K: P(K) = |K|^{-1}\), т.е. ключей столько же сколько сообщений и все ключи равновероятны.
В распространённом случае \(\mu = \nu\), условие \(|K| \ge |X|\) приобретает вид \(\mu^m \ge \nu^l\), или \(m \ge l\).
Таким образом, совершенно криптостойкий шифр должен использовать полностью случайные равновероятные одноразовые ключи.
Некоторые простые симметричные шифры
Рассмотрим некоторые простые симметричные шифры. Они скорее представляют исторический интерес, однако ввиду простоты часто используются в качестве иллюстрации.
Шифр подстановки
Шифр подстановки – общее название семейства побуквенных шифров, использующих замену символов открытого текста по некоторому детерминированному алгоритму.
В наиболее общем виде, пусть имеется открытый текст \(M = \{x_i\}\) над алфавитом \(X\), и множество взаимно-однозначных (биективных) функций отображения \(\phi_i : X \to Y\), \(i \in \{1, \ldots, n\}\). Тогда шифротекст \(C = \{\phi_i(x_i)\}\).
Шифр перестановки
Шифр перестановки – общее название семейства побуквенных шифров, использующих перестановку символов исходного сообщения.
В наиболее общем виде, пусть имеется открытый текст \(M = \{x_i\}\) над алфавитом \(X\), и множество неповторяющихся индексов перестановки \(\psi_i \in \{1, \ldots, n\}\), \(i \in \{1, \ldots, n\}\). Тогда шифротекст \(C = \{x_{\psi_i}\}\).
Шифр Виженера
Шифр Виженера – шифр подстановки, использующий в качестве алфавита шифротекста алфавит исходного сообщения. В качестве функций подстановки используются циклические сдвиги, основанные на ключевой фразе.
Пусть открытый текст \(M = \{m_i\} \in X^l\), ключевая фраза \(K = \{k_i\} \in X^m\). Пусть \(j = i \mod m\). Тогда шифротекст \(C = \{c_i\} \in X^l\) строится как \[c_i = m_i + k_j \mod |X|.\]
Дешифрование, соответственно, \[m_i = c_i - k_j \mod |X|.\]
Шифр Вернама
Частный случай шифра Виженера при \(m \ge n\).
Строго говоря, канонически шифр Вернама использует двоичный алфавит, обобщение этого шифра на алфавит размерности \(m\) назвается шифром Вернама по модулю \(m\) или системой одноразовых блокнотов.
- Теорема
Шифр Вернама является совершенно криптостойким.
\(\Delta\):
По определению шифра Вернама, \(C = M + k \mod |X|\), причём \(k\) – равномерно распределённая случайная последовательность. Тогда и \(C\) – равномерно распределённая случайная последовательность. Тогда \(H(Y|X)=H(Y)=\log |Y|^{-1}\)
\(\not\Delta\)
Проблема обмена ключами
Как можно заметить по вышеизложенному, при использовании симметричных шифров, все стороны информационного взаимодействия должны иметь один и тот же ключ или набор ключей. А поскольку компрометация ключа приведёт к немедленному взлому шифра, крайне важным оказывается вопрос безопасной (конфиденциальной) передачи ключей.
К решению этой проблемы существуют несколько подходов.
Прямая передача ключа. Этот подход работает только при условии, что прямая передача ключа происходит по заведомо безопасному каналу. Но заведомо безопасный канал проблематично установить без предварительной передачи ключа – исключая вариант передачи “из рук в руки”.
Предварительное распределение ключей. Ключи вырабатываются некой доверенной стороной, которая по безопасным каналам распространяет ключи среди участников связи. Кроме очевидной проблемы поиска безопасного канала связи в отсутствие ключей, такие схемы часто страдают от алгоритмической выработки ключей, что часто позволяет восстановить все ключи по малому подмножеству всех ключей. Один из широко известных методов предварительного распределения ключей – схема Блома (в частности потому что этот метод использовался в системе DRM HDCP v1.x)
Совместная выработка участниками связи общего ключа. Это наиболее распространённый на текущий момент подход, конкретно в виде алгоритма Диффи-Хеллмана. Стороны совместно вырабатывают общий ключ, обмениваясь по открытым каналам только данными, которые вычислительно сложно (но теоретически возможно) использовать для вычисления общего ключа. Одной из технически реализуемых атак в данном случае является атака “человек посередине” (Man in the Middle, MitM), заключающейся в имитации второй стороны для каждого из участников в момент выработки общего ключа. Этот подход используется в частности в протоколах семейства TLS.
В общем случае, проблему распространения ключей решает криптография с открытым ключом (асимметричные шифры). В известном смысле, протокол Диффи-Хеллмана по сути использует те же подходы.
Однако, как правило, криптография с открытым ключом более сложна в вычислительном смысле, и даёт теоретически более слабые гарантии конфиденциальности, чем симметричная криптография.
Схема Блома
Доверенная сторона выбирает случайную симметричную квадратную матрицу \(D\) размера \(k\times k\) (в идеале ранга \(k\)) в поле Галуа \(GF(p)\), где \(p\) – простое число. Матрица \(D\) известна только доверенной стороне.
Для каждого нового участника связи выбирается публичный идентификатор \(I_i\) – случайный уникальный столбец размера \(k\) в поле \(GF^k(p)\). Доверенная сторона затем вычисляет секретный ключ для каждого из участников \(g_i = D I_i\).
Теперь любая пара участников может выработать совместный секретный ключ, найдя скалярное произведение своего секретного ключа и идентификатора второй стороны: \[k_{ij} = g_i^\mathrm TI_j = I_i^\mathrm TD^\mathrm TI_j = I_i^\mathrm TD I_j = I_i^T g_j = k_{ji}^\mathrm T\]
Понятно, что исходная матрица \(D\) тривиально восстанавливается, если атакующему известно \(k\) различных секретных ключей. Ситуация несколько ухудшается, если идентификаторы некоторых участников линейно зависимы – тогда возможно вычислить ключи таких участников, даже не зная матрицы \(D\).
Протокол Диффи-Хеллмана
В начале работы алгоритма определяются числа \(g\) и \(p\) (p – простое), которые не являются секретными. Традиционно обозначим участников связи Алиса (А) и Боб (Б).
Оба участника генерируют большие случайные числа, соответственно \(a\) и \(b\), вычисляют соответственно \[A = g^a \mod p,\] \[B = g^b \mod p,\] и обмениваются вычисленными числами \(A\) и \(B\).
Алиса, получив \(B\), вычисляет \(K = B^a \mod p = g^{ab} \mod p\). Боб, получив \(A\), вычисляет \(K = A^b \mod p = g^{ab} \mod p\). Далее \(K\) может использоваться в качестве общего ключа.
Криптоаналитик, перехвативший \(A\) и \(B\) сталкивается с задачей дискретного логарифма, которая (предположительно) является вычислительно сложной. При выборе достаточно больших чисел \(a, b\), и “хороших” \(g\), \(p\), эта задача неразрешима за разумное время.
Числа \(g\), \(p\) обычно генерируются инициирующей стороной и передаются по открытому каналу. В целях увеличения безопасности, на \(g\) и \(p\) налагаются следующие условия:
- \(p\) – случайное простое число, такое, что \((p-1)/2\) также простое.
- \(g\) – первообразный корень по модулю \(p\), т.е. \(g^{\phi(p)} = 1 \mod p\) и \(\forall i \in [1, \phi(p)): g^i \neq 1 \mod p\), где \(\phi(p)\) – функция Эйлера, для простого \(p\), \(\phi(p) = p-1\).
В более общем случае, вместо чисел \(g\) и \(p\), стороны выбирают конечную циклическую группу \(G\) порядка \(p-1\) и порождающий элемент \(g \in G\). В стандартном алгоритме \(G\) – циклическая мультипликативная группа порядка \(p-1\) над целыми числами. Чтобы задача дискретного логарифма была действительно трудно разрешимой, у порядка группы \(G\) должен быть большой простой множитель (иначе возможна факторизация и решение задачи в группах меньшего размера, что значительно проще), поэтому предпочтительно выбирается \(p=2q+1\), где \(q\) – простое, тогда у \(p-1\) есть только множители \(2\) и \(q\). \(g\) обычно выбирается таким образом, чтобы быть порождающим элементом группы \(G\), либо, реже, её подгруппы порядка \(q\). Как правило, \(g\) выбирается малым, поскольку размер \(g\) в конечном итоге не влияет на сложность вскрытия.