Основы криптографии и криптологии

  • один из разделов теории кодирования – криптографическое кодирование
  • криптография – “скрытое письмо”
  • задача – защита информации
  • дисциплина: криптология
  • включает криптографию и криптоанализа
  • криптография – разработка методов шифрования
  • криптоанализ – оценка методов шифрования и разработка методов взлома (вскрытия)
Шифрование
обратимое преобразование информации в целях сокрытия от неавторизованных лиц, при этом с предоставлением авторизованным лицам доступа к ней.
Криптосистема
(шифр) система обратимых преобразований, зависящая от некоторого секретного параметра и предназначенная для обеспечения секретности передаваемой информации.
система защиты информации, использующая криптографические средства.
  • криптосистемы обеспечивают:
    • аутентификацию
    • шифрование

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

Основные аспекты криптографии

  • Криптография предшествует цифровым информационным системам
  • Изначально – тайна переписки
  • Исторические алгоритмы основаны на скрытии алгоритма
  • Непригодны в современных реалиях
  • Современные алгоритмы публичны
  • Полагаются на ключ – случайное секретное значение из множества возможных
Пространство ключей
множество возможных ключей для данного алгоритма с данными параметрами
Симметричное шифрование
Использует один ключ для шифрования и дешифрования. Симметричные шифры известны как шифры с секретным ключом
Асимметричное шифрование
Использует разные ключи для шифрования и дешифрования. Ассиметричные шифры известны как шифры с открытым ключом
Шифротекст
Сообщение после шифрования

Основные аспекты криптоанализа

  • Основное предположение: безопасность полностью определяется ключом
  • Атакующему (криптоаналитику) известны все детали алгоритма, доступен некоторый объём шифротекстов или даже возможность генерировать шифротексты

Основные подходы:

  1. Вскрытие на основе шифротекста.

    • Дано: описание алгоритма, шифротексты с одинаковым ключом
    • Задача: восстановить исходные сообщения, ключ, либо построить алгоритм дешифрования

  2. Вскрытие на основе открытого текста

    • Дано: описание алгоритма, шифротексты с одинаковым ключом, соответствующе исходные сообщения
    • Задача: восстановить ключ, либо построить алгоритм дешифрования

  1. Вскрытие на основе выбранного открытого текста.

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

  2. Вскрытие на основе выбранного шифротекста

    • Дано: описание алгоритма, возможность получить исходные сообщения для произвольных шифротекстов
    • Задача: восстановить ключ, либо построить алгоритм дешифрования

Успешность криптоанализа может варьироваться (по классификации Кнудсена):

  1. Полное вскрытие: получен ключ
  2. Глобальная дедукция: получен алгоритм дешифрования без ключа
  3. Локальная дедукция: для одного шифротекста получено исходное сообщение
  4. Информационная дедукция: получена некоторая информация о ключе или сообщении

Модели криптографии

  • Отправитель: “Алиса” (“А”)
  • Получатель: “Боб” (“B”)
  • Криптоаналитик: “Эва” (“E”)

Модель симметричного шифра

  • \(M\) – исходное сообщение
  • \(C\) – шифротекст
  • \(k\) – ключ
  • \(f\) – функция шифрования
  • \(f^{-1}\) – функция дешифрования.

Модель асимметричного шифра

  • \(M\) – исходное сообщение
  • \(C\) – шифротекст
  • \(p\) – публичный ключ
  • \(s\) – секретный ключ
  • \(f\) – функция шифрования
  • \(f^{-1}\) – фнукция дешифрования
  • \(K\) – алгоритм выработки ключей

Стойкость симметричных систем

  • Устойчивость криптосистемы к вскрытию – криптостойкость или просто стойкость.

Теоретико-информационная модель криптосистемы:

  • исходное сообщение \(M\) – ансамбль векторов длины \(l\) над алфавитом \(\mathcal A_M\)
  • шифротекст \(C\) – ансамбль векторов длины \(l\) над алфавитом \(\mathcal A_C\)
  • ключ \(K\) – ансамбль векторов длины \(n\) над алфавитом \(\mathcal A_C\)
  • Фактически, \(C = f(M, K)\). Без знания \(K\) – можно считать случайным.
Совершенно криптостойкий симметричный шифр
\(P(M | C) = P(M),\)
\(\Leftrightarrow H(M | C) = H(M),\)
\(\Leftrightarrow I(M; C) = 0,\)
наблюдение шифротекста не даёт информации о сообщении

Теорема

Необходимое и достаточное условие совершенной криптостойкости \[\forall M, C: P(C|M) = P(C)\]

\(\Delta\):

\[P(M) = P(M | C)\]

\[P(M) = \frac{P(C | M)P(M)}{P(C)}\]

\[P(C)P(M) = \frac{P(C | M)P(M)P(C)}{P(C)}\]

\[P(C)\cancel{P(M)} = \frac{P(C | M)\cancel{P(M)}\cancel{P(C)}}{\cancel{P(C)}}\]

\[P(C) = P(C | M)\qed\]

Лемма

Для любой детерминированной криптосистемы, \(H(M|C) \le H(K|C),\) \(H(C|M) \le H(K|M).\)

Т.к. \(C=f(M,K)\) и \(M=f^{-1}(C,K),\) \(H(C|KM) = H(M|KC) = 0.\)

Рассмотрим \(H(KM|C)\) и \(H(KC|M)\)

\(H(M|C) \le H(KM|C)\)

\(H(M|C) \le H(KMC)-H(C)\)

\(H(M|C) \le H(M|KC)+H(KC)-H(C)\)

\(H(M|C) \le H(M|KC)+H(K|C)\)

\(H(M|C) \le \cancel{H(M|KC)}+H(K|C)\)

\(H(M|C) \le H(K|C)\phantom\qed\)

\(H(C|M) \le H(KC|M)\)

\(H(C|M) \le H(KCM)-H(M)\)

\(H(C|M) \le H(C|KM)+H(KM)-H(M)\)

\(H(C|M) \le H(C|KM)+H(K|M)\)

\(H(C|M) \le \cancel{H(C|KM)}+H(K|M)\)

\(H(C|M) \le H(K|M)\phantom\qed\)

\(H(C|M) \le H(K|M)\qed\)

Теорема

Необходимое условие совершенной криптостойкости:

\(H(K) \ge H(M), H(K) \ge H(C).\)

По определению, \(H(M)=H(M|C),\) \(H(C)=H(C|M)\).

\(H(M) = H(M|C) \phantom{\le H(K|C) \le H(K)}\)

\(H(M) = H(M|C) \le H(K|C) \phantom{\le H(K)}\)

\(H(M) = H(M|C) \le H(K|C) \le H(K)\)

\(H(M) \le H(K)\)

\(H(C) = H(C|M) \phantom{\le H(K|M) \le H(K)}\)

\(H(C) = H(C|M) \le H(K|M) \phantom{\le H(K)}\)

\(H(C) = H(C|M) \le H(K|M) \le H(K)\)

\(H(C) \le H(K)\)

\(\phantom{H(C) \le H(K)}\qed\)

Следствие

  • \(H(M) \le H(K)\)

  • \(H(M) \le \log |M|\)

  • \(H(K) \le \log |K|\)

  • в худшем случае \(H(M) = \log |M|\)

  • Тогда:

    \(H(M) \le H(K) \phantom{\le \log |K|}\)

    \(\log |M| \le H(K) \phantom{\le \log |K|}\)

    \(\log |M| \le H(K) \le \log |K|\)

    \(\log |M| \le \log |K|\)

    \(|M| \le |K|\)

Практически интересен случай \(|K| = |M|\), тогда \(H(K) = \log |K|\), тогда ключей столько же сколько сообщений и все ключи равновероятны.

В случае \(|\mathcal A_M| = |\mathcal A_C|\), \(|K| \ge |M|\)\(\Rightarrow |\mathcal A_C|^n \ge |\mathcal A_M|^l\)\(\Rightarrow n\ge l\)

Некоторые простые симметричные шифры

Шифр подстановки

  • Использует замену символов
  • \(i \in \{1, \ldots, l\}\)
  • Открытый текст \(M = \{m_i\}\)
  • Множество биективных функций \(\phi_i : \mathcal A_M \to \mathcal A_C\)
  • Шифротекст \(C = \{\phi_i(x_i)\}\).

Шифр перестановки

  • Использует перестановку символов
  • \(i \in \{1, \ldots, l\}\)
  • Открытый текст \(M = \{x_i\}\)
  • Множество индексов перестановки \(\psi_i \in \{1, \ldots, l\};\)
  • \(\forall i\neq j: \psi_i\neq\psi_j\)
  • Шифротекст \(C = \{x_{\psi_i}\}\).

Шифр Виженера

  • шифр подстановки, \(\mathcal A_M = \mathcal A_C\)
  • \(\phi_i\) – циклические сдвиги алфавита на основе ключевой фразы.
  • Открытый текст \(M = \{m_i\} \in \mathcal A_M^l\)
  • Ключевая фраза \(K = \{k_i\} \in \mathcal A_M^n\).
  • \(j = i \mod n\)
  • Шифротекст \(C = \{c_i\} \in \mathcal A_M^l\), \(c_i = m_i + k_j \mod |\mathcal A_M|.\)
  • Дешифрование: \(m_i = c_i - k_j \mod |\mathcal A_M|.\)

Шифр Вернама

  • Частный случай шифра Виженера при \(n \ge l\).
  • Строго говоря, шифр Вернама – двоичный алфавит
  • Обобщение – шифр Вернама по модулю \(m\) или система одноразовых блокнотов.

Теорема

Шифр Вернама является совершенно криптостойким, если \(K\) и \(M\) независимы и \(K\) равномерно распределён.

Пусть \(n=l\), \(\mathrm E(m, k) = m + k \mod |\mathcal A_M|\), \(\mathrm D(c, k) = c - k \mod |\mathcal A_M|\), \(\mathrm F(m,c) = c - m \mod |\mathcal A_M|\)

\[\phantom{1=}P(C=c|K=k,M=D(c, k))\\\phantom{\frac{P(C=c,K=k,M=D(c, k))}{P(K=k,M=D(c,k))}}\]

\[\phantom{1=}P(C=c|K=k,M=D(c, k)) \\=\frac{P(C=c,K=k,M=D(c, k))}{P(K=k,M=D(c,k))}\]

\[1=P(C=c|K=k,M=D(c, k)) \\=\frac{P(C=c,K=k,M=D(c, k))}{P(K=k,M=D(c,k))}\]

\[1 = \frac{P(C=c,K=k,M=D(c, k))}{P(K=k,M=D(c,k))}\]

\[1 = \frac{P(C=c,K=k)P(M=D(c, k)|C=c,K=k)}{P(K=k,M=D(c,k))}\]

\[1 = \frac{P(C=c,K=k)\cancelto{1}{P(M=D(c, k)|C=c,K=k)}}{P(K=k,M=D(c,k))}\]

\[1 = \frac{P(C=c,K=k)}{P(K=k,M=D(c,k))}\]

\[1 = \frac{P(C=c,K=k)}{P(K=k)P(M=D(c,k))}\]

\[1 = \frac{P(C=c|K=k)}{P(M=D(c,k))}\]

\[P(C=c|K=k) = P(M=D(c,k))\]

\[P(C=c)\phantom{ = \sum_k P(C=c|K=k)P(K=k)}\]

\[P(C=c) = \sum_k P(C=c|K=k)P(K=k)\]

\[P(C=c) = \sum_k P(C=c|K=k)\frac{1}{N}\]

\[P(C=c) = \frac{1}{N}\sum_k P(C=c|K=k)\]

\[P(C=c) = \frac{1}{N}\sum_k P(M=D(c,k))\]

\[P(c) = \frac{1}{N}\]

\[P(M=m|C=c) = \frac{P(M=m,C=c)}{P(C=c)}\]

\[P(M=m|C=c) = \frac{P(M=m,K=F(m,c))}{P(C=c)}\]

\[P(M=m|C=c) = \frac{P(M=m)P(K=F(m,c))}{P(C=c)}\]

\[P(M=m|C=c) = \frac{P(M=m)\frac{1}{N}}{\frac{1}{N}}\]

\[P(M=m|C=c) = P(M=m)\]

\[P(M|C) = P(M)\]

\[\phantom{P(M|C) = P(M)}\qed\]

Проблема обмена ключами

  • при использовании симметричных шифров
  • все стороны должны иметь один ключ или набор ключей
  • компрометация ключа – немедленный взлом шифра
  • встаёт вопрос безопасной передачи ключей

  1. Прямая передача ключа. Проблема курицы и яйца – чтобы безопасно передать ключ надо сначала передать ключ.

  2. Предварительное распределение ключей. Ключи вырабатываются некой третьей стороной, которая распространяет ключи среди участников связи. Кроме той же проблемы, встаёт вопрос доверия (в том числе к способу выработки ключей)

  3. Совместная выработка участниками связи общего ключа. Наиболее распространённый подход, в виде алгоритма Диффи-Хеллмана. Возможная атака – MitM.

  • В общем случае решается криптографией с открытым ключом. Протокол Диффи-Хеллмана по сути использует те же подходы.
  • Асимметричные шифры вычислительно более сложные, с более слабыми теоретическими гарантиями.

Схема Блома

  • Доверенная сторона: \(D = \{d_{ij}\},\) \(i,j\in\{1,\ldots,k\},\) \(d_{ij}\in GF(p)\), \(p\) – простое число. \(D\) секретная.
  • Для \(i\)-го участника выбирается случайный уникальный идентификатор \(I_i \in GF^k(p)\). Секретный ключ тогда \(g_i = D I_i\).
  • Пара \(i\)-го и \(j\)-го участников вырабатывает общий ключ \(k_{ij} = g_i^\T I_j = I_i^\T D^\T I_j = I_i^\T D I_j = I_i^T g_j = k_{ji}^\T\)

\(D\) тривиально восстанавливается, если известно \(k\) различных \(g_i\).

Если \(I_i\) линейно зависим от \(I_j\), то \(k_{ij}\) возможно восстановить даже не зная матрицы \(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\) налагаются следующие условия:

  • \(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\), \(|G|=p-1\) и порождающий элемент \(g \in G\).
  • В стандартном алгоритме \(G\) – циклическая мультипликативная группа порядка \(p-1\) над целыми числами.
  • Чтобы было возможности факторизации ЗДЛ, \(p=2q+1\), где \(q\) – простое, тогда у \(p-1\) есть только множители \(2\) и \(q\).
  • \(g\) – порождающий элемент \(G\), либо подгруппы порядка \(q\)
  • Как правило, \(g\) мал, т.к. не влияет на сложность вскрытия.