Симметричное и асимметричное шифрование

Симметричные схемы

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

Одной из первых реально эффективных схем шифрования был шифр Виженера.

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

Они заранее встречаются и договриваются о неком «секрете»: для примера, пусть это будет слово «гриб».

Теперь Вася хочет передать Пете сообщение «укошкисемерокотят».

Для этого он циклически продолжает секрет: «грибгрибгриб…». После чего складывает своё сообщение с результатом такого продолжения, получая «».

Под сложением в данном случае понимается нечто наподобие:

def add_chars(x, y):
  return chr(ord('а') + (ord(x) + ord(y) - 2*ord('а')) % 32)
  ## 32 -- размер используемого алфавита (без буквы ё)

def add_messages(m1, m2):
  chars = [add_chars(m1[i], m2[i]) for i in range(len(m1))]

  return ''.join(chars)

В результате получается «цъцщншщжпхшпнюъах», что мало напоминает исходное сообщение (поскольку одни и те же символы в результате шифрования преобразуются в различные, полностью сбивается распределение частот символов).

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

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

Шифр Фейстеля

Одна из реально используемых сейчас схем в упрощённом виде выглядит так:

  • выбирается последовательность функций \(f_1, f_2, \ldots f_m\): каждая с \(N\) двоичными входами и таким же количеством двоичных выходов
  • кодируемое сообщение каким-либо образом дополняется до длины \(2N\)
  • пусть \(L_0\) и \(R_0\) — левая и правая половины входного сообщения соответственно
  • вычисляется последовательность \(L_{n}=R_{n-1}\), \(R_{n}=L_{n-1}\oplus f_n(R_{n-1})\) (здесь \(\oplus\) — поразрядный XOR)

Декодировка осуществляется ровно так же, только функции используются в обратном порядке.

Эта схема называется шифром (или сетью) Фейстеля. Секретом является сама последовательность функций (на практике функции являются общеизвестными, но зависящими от неких параметров, набор которых является секретным).

Также отметим, что двоичные входы можно заменить на произвольные, а поразрядный XOR — на любую обратимую (не обязательно даже поразрядную) функцию.

Разбиение на блоки

Если сообщение достаточно длинное (длиннее тех частей ключа, которые определяют вышеупомянутые функции \(f_i\)), то его приходится разбивать на блоки.

Для того, чтобы одинаковые блоки после шифрования становились разными, каждый неким образом модифицируют. Самое частое (и простое): такой блок можно обратимым образом совокупить с элементом некоторой детерминированной последовательности (например, поразрядно проXORить блок с его номером).

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

Общие свойства

К достоинствам симметричных схем относят:

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

Основным же недостатком является необходимость сторонам коммуникации сформировать общий для них секрет: зачастую у этих сторон нет возможности «встретиться наедине».

Обычно общий секрет формируется одним из двух способов:

Формирование общего ключа

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

Вася и Петя (открыто) договариваются об использовании некоторой функции F с двумя входами и следующими свойствами:

  • композициональная коммутативность: \(F(F(x,a),b)=F(F(x,b),a)\)
  • однонаправленность: задача определения по \(F(x,a)\) и \(x\) хотя бы одного подходящего \(a\) имеет высокую вычислительную сложность

Далее Вася и Петя (также открыто) выбирают \(x\). Вася загадывает некоторое \(a\), Петя загадывает некоторое \(b\).

Далее Вася сообщает Пете \(F(x,a)\), а Петя сообщает Васе \(F(x,b)\).

Теперь и Вася, и Петя могут вычислить \(F(F(x,a),b)=F(F(x,b),a)\), что и будет являться для них их общим секретом.

Асимметричные схемы

Шифрование

Асимметричные схемы шифрования работают следующим образом:

  • есть секрет, называемый приватным ключом; он известен ровно одному участнику коммуникации
  • есть публичный ключ, известный всем участникам

Шифрование осуществляется при помощи публичного ключа (то есть любой может отправить сообщение обладателю приватного ключа), а дешифровка — приватным.

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

Классическим асимметричным алгоритмом является RSA.

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

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

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

Если нечто удалось расшифровать публичным ключом во что-то осмысленное, то с высокой вероятностью это нечто — сообщение, написанное тем самым вышеупомянутым лицом.

Отметим, что на практике из-за медлительности асимметричных схем используется чуть другая схема:

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

Чтобы проверить аутентичность сообщения, достаточно публичным ключом расшифровать приложение, а потом применить вышеупомянутую функцию к сообщению и сравнить.