Шифри Вернама, Плейфера, перестановок, машини Хагеліна і Енігма

Пример 2.5

Метод Казиски

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

Процитируем пример из [4].

Рассмотрим следующий открытый текст и криптограмму, полученную из него с помощью ключа.

открытый текст	t	h	e	r	e	i	s	a	n	o	t
ключ	c	o	m	e	t	c	o	m	e	t	c
шифртекст	v	v	q	v	x	k	g	m	r	h	v
открытый текст	h	e	r	f	a	m	o	u	s	p	i
ключ	o	m	e	t	c	o	m	e	t	c	o
шифртекст	v	q	v	y	c	a	a	y	l	r	w

В криптограмме имеется два вхождения подстроки, начинающиеся с 1-й и с 11-й позиций. Это показывает, что длина ключа делит 10. Кроме того, дважды встречается и подстрока, с 8-й и с 23-й позиций. Таким образом, кажется правдоподобным, что длина ключа делит 15. Комбинируя эти результаты, можно сделать вывод, что. В данном случае вывод оказывается верен.

Дополнительные подробности криптоанализа системы Виженера можно найти в [4].

Одноразовые блокноты (шифр Вернама)

Поверите или нет, но идеальный способ шифрования существует. Он называется одноразовым блокнотом и был изобретен в 1917 году Мэйджором Джозефом Моборном (Major Joseph Mauborgne) и Гилбертом Вернамом (Gilbert Vernam) из AT&T. В классическом понимании одноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом, написанных на кусочках бумаги и приклеенных к листу блокнота. Первоначально это была одноразовая лента для телетайпов. Отправитель использовал каждый символ ключа блокнота для шифрования только одного символа открытого текста. Шифрование представляет собой сложение по модулю 26 символа открытого текста и символа ключа из одноразового блокнота.

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

ONETIMEPAD

а ключевая последовательность в блокноте:

TBFRGFARFM

то шифротекст будет выглядеть как:

IPKLPSFHGQ

так как

O + Т mod 26 = I

N + В mod 26 = Р

Е + F mod 26 = К

и т.д.

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

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

POYYAEAAZX

что дешифрируется как:

SALMONEGGS

или на:

BXEGBMTMXM

что дешифрируется как:

GREENFLUID

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

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

Другой важный момент: ключевую последовательность никогда нельзя использовать второй раз. Даже если вы используете блокнот размером в несколько гигабайт, то если криптоаналитик получит несколько текстов с перекрывающимися ключами, он сможет восстановить открытый текст. Он сдвинет каждую пару шифротекстов относительно друг друга и подсчитает число совпадений в каждой позиции. Если шифротексты смещены правильно, соотношение совпадений резко возрастет - точное значение зависит от языка открытого текста. С этой точки зрения криптоанализ не представляет труда. Это похоже на показатель совпадений, но сравниваются два различных "периода". Не используйте ключевую последовательность повторно.

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

Однако существует несколько проблем. Так как ключевые биты должны быть случайными, и не могут использоваться снова, длина ключевой последовательности должна равняться длине сообщения. Одноразовый блокнот удобен для нескольких небольших сообщений, но его нельзя использовать для работы по каналу связи с пропускной способностью 1.544 Мбит/с. Вы можете хранить 650 Мбайт случайных данных на CD-ROM, но и тут есть проблемы. Во-первых, вам нужно только две копии случайных битов, но CD-ROM экономичны только при больших тиражах. И, во-вторых, вам нужно уничтожать использованные биты. Для CD-ROM нет другой возможности удалить информацию кроме как физически разрушить весь диск. Гораздо больше подходит цифровая лента.

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

Одноразовые блокноты используются и сегодня, главным образом для сверхсекретных каналов связи с низкой пропускной способностью. По слухам "горячая линия" между Соединенными Штатами и бывшим Советским Союзом (а действует ли она сейчас?) шифруется с помощью одноразового блокнота. Многие сообщения советских шпионов зашифрованы с использованием одноразовых блокнотов. Эти сообщения нераскрыты сегодня и навсегда останутся нераскрытыми. На этот факт не повлияет время работы суперкомпьютеров над этой проблемой. Даже когда враги из созвездия Андромеды приземлят свои тяжелые корабли с компьютерами немыслимой мощности, и они не смогут прочесть сообщения советских шпионов, зашифрованные с помощью одноразовых (если, конечно, они не смогут вернуться в прошлое и добыть нужные одноразовые блокноты).

Дата добавления: 2013-12-12