В криптографии электронно-цифровые подписи выполняют функции, схожие с функциями обычных “физических” подписей. Какими свойствами должна обладать “хорошая” подпись?

  1. Неподдельность: гарантия, что именно подписавший, а не кто-то иной подписал документ
  2. Невозможность использовать повторно: подпись с одного документа не может быть перенесена на другой документ
  3. Целостность: нельзя изменить подписанный документ, оставив подпись
  4. Невозможность отказа: подписавший не может отказаться от своей подписи

Схема ЭЦП с публичным ключом

Схема ЭЦП состоит из трёх частей:

  1. Алгоритм генерации закрытого и открытого ключей
  2. Алгоритм генерации подписи $Signature$
  3. Алгоритм проверки подписи $Verify$

Алгоритм генерации подписи принимает на вход закрытый ключ и сообщение, которое необходимо подписать. На выходе он выдаёт значение подписи $$Signature(privKey, M) = sig$$

Алгоритм проверки подписи принимает на вход открытый ключ, сообщение и значение подписи. На выходе он выдаёт ответ “да”, если подпись верная (т.е. действительно была корректно сгенерирована для этого сообщения парным закрытым ключом) и “нет” в противном случае $$Verify(pubKey, M, sig) = yes|no$$

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

Проверим свойства:

  1. Неподдельность – для генерации подписи необходим закрытый ключ, которым владеет только подписывающий. В случае подделки или отказа от подписи это будет обнаружено при проверке подписи
  2. Невозможность использовать повторно и целостность – при генерации подписи используется сообщение, в случае изменения сообщения проверка подписи не будет пройдена

RSA

RSA является самым популярными криптографическим алгоритмом с открытым ключом на данный момент. Вы используете RSA постоянно. Например, когда открываете сайт и видите зелёный замочек в строке браузера: если вы кликните на замочек и зайдёте в настройки сертификата, то увидите что-то вроде “SHA-256 с шифрованием RSA”.

Определение:

Целое число $a$ делится на число $b$, если существует такое целое $k$, что $a = kb$

Наибольший общий делитель(НОД) целых чисел $a$ и $b$ – наибольших из делителей и числа $a$ и числа $b$. Обозначается $(a, b)$

Взаимно простые числа – числа, НОД которых равен 1

Функция Эйлера натурального числа $n$ – количество натуральных чисел меньших $n$ и взаимно простых с $n$

Генерация ключей

  1. Сгенерировать два различных простых числа $p$ и $q$
  2. Вычислить $n = pq$
  3. Вычислить функцию эйлера от $n$: $\phi(n) = (p - 1)(q - 1)$
  4. Случайно выбрать $1 \lt e \lt \phi$, такое что $(e, \phi) = 1$
  5. Вычислить $1 \lt d \lt \phi$ такое что $ed \equiv 1 \pmod{\phi}$
    Пара $(e, n)$ является открытым ключом, $d$ – закрытым ключом

Замечания:

  • Схема RSA основана на сложной задаче RSA: на основании $n$ и $e$ вычислить $d$. Это сложная проблема, которая тесно связана с проблемой разложения чисел на множители
  • $p$ и $q$ должны быть большими. На практике используются числа более 2048 бит (порядка 10 тысяч десятичных цифр)
  • $\phi(n)$ легко посчитать, зная $p$ и $q$. Без знания $p$ и $q$ это вычислительно сложная задача
  • По соображениям эффективности число $e$ часто выбирается как небольшое простое число с малым количеством единиц в двоичной записи. Популярное значение $2^{16} + 1 = 65537$
  • Значение $d$ всегда существует и единственное. Найти его можно с помощью расширенного алгоритма Евклида

Подпись и проверка

Подпись сообщения $m$:
$sig = m^d \bmod n$

Проверка подписи:

  1. Вычислить $v = sig^e \bmod n$
  2. Если $v$ равно $m \bmod n$, то подпись принимается. В противном случае подпись отвергается

image

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

Докажем корректность схемы:

$sig^e \bmod n = {(m^d)}^e \bmod n = m^{ed} \bmod n$

Так как $ed \equiv 1 \pmod{\phi}$ то существует такое $k$, что
$ed = 1 + k\phi = 1 + k(p-1)(q-1)$

Рассмотрим два случая:

  1. Если $(m, p) = p$, тогда
    $m^{ed} \bmod p = m \bmod p = 0$
  2. Если $(m, p) = 1$, тогда по теореме Ферма
    $m^{p-1}\equiv 1 \pmod{p} $
    Возведём обе части в степень $k(q - 1)$ и затем умножим на $m$:
    $m^{1 + k(p-1)(q-1)}\equiv m \pmod{p}$
    $m^{ed} \equiv m \pmod{p}$

Аналогично можно доказать, что $m^{ed} \equiv m \pmod{q}$
А так как $n = pq$, то
$m^{ed} \equiv m \pmod{n}$

∎

Пример:

  1. $p=5, q=11$
  2. $n = 5 * 11 = 55$
  3. $\phi = (5 - 1)(11 - 1) = 40$
  4. $e = 3$
  5. $d = 27$, $(3 * 27 = 81 \equiv 1 \pmod{40}$)
  6. $m = 4$
  7. Подпись: $sig = 4^{27} \bmod 55 = 49$
  8. Проверка: $49^{3} \bmod 55 = 4$ – проверка пройдена успешно

∎

Хеш-функции

В примере RSA подписываемое сообщение представлялось в виде числа. Но как именно нужно конвертировать сообщение в число? Из общих соображений понятно, что произвольная функция конвертации не подходит. Например, если для двух различных текстов число $m$ будет одинаковое, то подпись также будет одинаковая, несмотря на то, что тексты различны.

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

Определение:

Криптографическая хеш-функция - это детерминированная функция $h(x)$, которая принимает на вход строки произвольной длины и выдаёт на выход строки фиксированной длины и обладающая следующими свойствами

  1. Значение функции $y = h(x)$ вычисляется просто
  2. По данному $y$ вычислить такой $x$, что $h(x) = y$ сложно
  3. Вычислить два произвольных $x_1 \ne x_2$ такие что $h(x_1) = h(x_2)$ вычислительно сложно

Пример:

Примером может служить хеш-функция SHA-256, которая является текущим стандартом США и выдаёт значения длиной 256 бит (всего $2^{256}$ различных значений). Пространство значений хеш-функции огромно: для сравнения, в видимой части вселенной порядка $2^{260}$ атомов
Есть много сайтов, на которых вы можете поиграться и погенерировать хеши SHA-256 для различных строк
SHA-256(seregablog) = 128295e65c805186909826edf8c6ffac1d15681616f6d99ff3be07c2d7093efd

∎

📢тг-канал