Шифр Вижинера, пример,Криптоанализ, Реализация

Квадрат Виженера, или таблица Виженера, также известная как tabula recta, может быть использована для шифрования и расшифровывания.

Криптоанализ Шифра Виженера

Шифр Виженера «размывает» характеристики частот появления символов в тексте.

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

1. Поиск длины ключа. Можно анализировать распределение частот в зашифрованном тексте с различным прореживанием. То есть брать текст, включающий каждую 2-ю букву зашифрованного текста, потом каждую 3-ю и т. д. Как только распределение частот букв будет сильно отличаться от равномерного (например, по энтропии), то можно говорить о найденной длине ключа.
2. Криптоанализ. Совокупность l шифров Цезаря (где l — найденная длина ключа), которые по отдельности легко взламываются.

Тесты Фридмана и Касиски могут помочь определить длину ключа.

Тест Касиски и определение с его помощью длины ключа и Индекса совпадений

Чарльз Беббидж был первым, кто разработал алгоритм атаки на шифр Виженера в 1854 году. Стимулом к разработке алгоритма послужил обмен письмами с Джоном Х. Б. Твейтсом. Он заявил, что создал новый шифр, и отправил его в «Journal of the Society of the Arts»; когда Беббидж показал, что шифр Твейтса является лишь частным случаем шифра Виженера, Твейтс предложил ему его взломать. Беббидж расшифровал текст, который оказался поэмой «The Vision of Sin» Альфреда Теннисона, зашифрованной ключевым словом Emily — именем жены поэта. Но он не опубликовал свое открытие. Поэтому данный алгоритм назван в честь Фридриха Вильгельма Касиски, офицера прусской армии, который независимо от Беббиджа разработал такой же алгоритм в 1863 году. И только в XX веке, когда ученые исследовали заметки Беббиджа, появилась информация о первом изобретателе этого алгоритма.^[12]

Вначале определим понятие индекса совпадения данного текста. Пусть рассматривается текст , соответствующий алфавиту, состоящему из букв. Пусть — длина этого текста. Обозначим через число вхождений буквы с номером в текст . Тогда индекс совпадения текста определяется как
.
Эмпирически проверено, что индекс совпадения длинных осмысленных английских текстов, таких как «Моби Дик» Меллвила, приблизительно равен 0,065. При этом, конечно, в тексте оставляют только 26 букв английского алфавита. В то же время абсолютно случайный достаточно длинный текст на 26 буквах, в котором все буквы встречаются приблизительно одинаковое число раз, равен 0,038. Замечено, что чем «осмысленнее» текст, тем выше его индекс совпадения. Это обстоятельство как раз и помогает вычислять длину ключа в шифре Виженера.

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






до тех пор, пока не получится .

Это может свидетельствовать о том, что длина ключа равна , хотя и может оказаться ложным следом.

Действительно, если длина ключа равна , то текст будет получен из сдвигом, следовательно, сохранит , а текст , в свою очередь, является случайной выборкой осмысленного текста, следовательно, должен сохранить его статистические характеристики, в частности индекс совпадения. Об этом говорит сайт https://intellect.icu . Если индекс совпадения некоторого языка неизвестен, то использование теста Касиски также возможно. Нужно не сравнивать полученные значения индексов совпадения со стандартным значением, а смотреть, когда этот индекс резко возрастет. Это может сигнализировать о найденной длине ключа. Конечно, речь идет о расшифровке осмысленных и одновременно достаточно длинных текстов. Впрочем, понятие осмысленности для формальных языков — понятие непростое.

Другим применением теста Касиски является проверка сохранения частот встречающихся букв при шифровании. Пусть — зашифрованный текст, причем алгоритм шифрования неизвестен. Если известно, что использовался обычный английский алфавит и значение близко к 0,065, то это дает основание полагать, что использовался шифр, сохраняющий частоты. Возможно, что это шифр простой замены. В ситуации, когда значение далеко от 0,065, можно предположить, что использовался шифр, не сохраняющий частоты, или же текст был бессмысленным, или же использовался другой алфавит и т.п. Одним словом, что-то оказалось не так и необходим более глубокий анализ.

Однако вернемся к шифру Виженера. Пусть определили правильно длину ключа, равную . Теперь нужно найти сам ключ.

Гистограмма, построенная по стандартным частотам букв в языке, имеет свои отличительные особенности. Они объясняются крайне неравномерным использованием букв в английском языке. Эта неравномерность как раз и позволяет эффективно применять частотный анализ.

Прежде всего, обращают на себя внимание «пики», соответствующие буквам A, E, H, I, N, O, R, S, T, и «пеньки», соответствующие J, Q, X, Z. При этом некоторые «пики» стоят рядом, даже есть целая тройка: R, S, T. Все вместе дает весьма специфический рельеф.

Если используется сдвиг на 4, то картина изменяется циклически:

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

Роторные машины[править | править код]

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

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

Частотный анализ

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

Упоминания в литературе

В 1881 году Жюль Верн написал роман Жангада. В данном романе автор использовал для зашифровки документа шифр Виженера. В качестве зашифрованного текста, автор использует следующий документ:

По ходу истории герои находят фрагмент расшифрованного слова к этому документу: ОРТЕГА Герои догадались, что это имя может обозначать подпись в конце документа. Таким образом выходит:

Следовательно, ключ — 432513. Зная ключ, можно легко перевести данный документ:

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

Существует, конечно, много других легкозапоминающихся квадратов, которые могут применяться в качестве основы для многоалфавитной системы так же, как и квадрат Виженера. Одним из наиболее известных является квадрат Бофора. Его строками являются строки квадрата Виженера, записанные в обратном порядке. Он назван в честь адмирала сэра Френсиса Бофора — создателя шкалы для определения скорости ветра. Если в квадрате Виженера первая строка и столбец указывают на строки и столбцы соответственно, то в квадрате Бофора этим целям служат первая строка и последний столбец.^[14]

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

Несмотря на очевидную стойкость шифра Виженера, он широко не использовался в Европе. Большее распространение получил шифр Гронсфельда, созданный графом Гронсфельдом, идентичный шифру Виженера, за исключением того, что он использовал только 10 различных алфавитов (соответствующих цифрам от 0 до 9). Преимущество шифра Гронсфельда состоит в том, что в качестве ключа используется не слово, а цифровая последовательность, которая повторяется до тех пор, пока не станет равной длине шифруемого сообщения. Шифр Гронсфельда широко использовался по всей Германии и Европе, несмотря на его недостатки.

Реализация Шифра Вижинера

JavaScript

//Можно скопировать и вставить весь этот код - в консоль браузера.
var a = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";		//Строка алфавита
var m = "ATTACKATDAWN";						//Сообщение
var k = "LEMON";							//Ключ

function Vizhener( m, k, mode ){//(encrypt/decrypt) for "Gronsfeld" + "Vizhener" + "Beaufort" + "Shifted Atbash"
	//m - сообщение или шифротекст (может быть и ключ, если шифр Бофора),
	//k - ключ (или сообщение/шифротекст, если шифр Бофора),
	//mode - режим:
	//	Шифрование: 	"encrypt" (по умолчанию),
	//	Дешифрование: 	"decrypt" (mode === 'decrypt'),
	//	Шифрование-дешифрование по таблице сдвинутого атбаша: (mode==='shifted_atbash')
	//	Извлечение цифр из ключа шифра Гронсфельда: "gronsfeld" или "gronsfeld_encrypt", "gronsfeld decrypt".

	var maxlength = Math.max(m.length, k.length);
	var r = '';	//Пустой результат
	for(i=0; i<maxlength; i++){ 			//encrypt/decrypt
		//Vizhener - encrypt/decrypt one forumula (encrypt - by default; decrypt - when (mode === 'decrypt') )
		var mi = a.indexOf( m[ ( (i>=m.length) ?i%m.length :i ) ] );	//подгон сообщения/шифротекста - к ключу (если меньше)
		var ki_s = k[ ( (i>=k.length) ?i%k.length :i ) ];
		//подгон ключа к сообщению/шифротексту (если короткий)
		var ki = (typeof mode !== 'undefined' && mode.indexOf('gronsfeld') !== -1) ? parseInt( ki_s ): a.indexOf( ki_s );
		//вычитание при дешифровании, либо сложение.
		ki = ( (typeof mode !== 'undefined' && mode.indexOf('decrypt') !== -1) ?(-ki) :ki );
		c = a[ ( ( ( a.length + ( mi + ki ) ) % a.length ) ) ];				//символ по таблице Виженера.
		c = (mode === 'shifted_atbash') ? a[a.length-1-a.indexOf(c)] : c;	//Атбаш символа или символ.
		r += c;																//Добавить символ к результату.
	}
	return r; //вернуть строку результата
}

//Тесты:

//1. Шифр Гронсфельда. (Урезанная версия шифра Виженера).
//Параметры: m - сообщение/шифротекст, k - ключ (только цифр), mode - "encrypt/decrypt"
console.log(
		'\n\n1. Шифр Гронсфельда (Урезанная версия шифра Виженера c цифровым ключом):'
	,	'\n'+	'm = ', 'GRONSFELD', ' - сообщение'
	,	'\n'+	'k = ', '2015', '- ключ'
	,	'\n'+	'Шифр Гронсфельда - шифрование: '
	,	Vizhener( 'GRONSFELD', '2015', 'gronsfeld' )	 									//выдаст IRPSUFFQF - шифр Гронсфельда
	,	'\n'+	'Шифр Гронсфельда - дешифрование: '
	,	Vizhener( Vizhener('GRONSFELD', '2015', 'gronsfeld'), '2015', 'gronsfeld decrypt' )	//выдаст GRONSFELD - из шифра Гронсфельда
	,	'\n'+	'Сравнение с сообщением: ', "( decrypted === m )"
	,	( Vizhener( Vizhener( 'GRONSFELD', '2015', 'gronsfeld'), '2015', 'gronsfeld_decrypt' ) === 'GRONSFELD' ) //m? true
);

//2. Также, вместо цифр, в шифре Гронсфельда - возможно и указание букв.
//Тогда, шифром Гронсфельда будет обычный шифр Виженера, но с ограничением символов на ключ.
//Например, при всех возможных цифрах в ключе "0123456789", ключ может быть только из букв "ABCDEFGHIJ"
//Получить его - можно так:
	var Gronsfeld_key = '2015';
	var Vizhener_key = Gronsfeld_key.split('').map(function(x){return a[parseInt(x)]}).join('');	//CABF
//И наоборот:
	var Gronsfeld_key2 = Vizhener_key.split('').map(function(x){return a.indexOf(x)}).join('');		//2015
//Вот они, в консоли:
	console.log(
		'\n2. Конвертация ключа Гронсфельда - в ключ Виженера:'
	,	'\nGronsfeld_key', Gronsfeld_key
	,	'\n'+'в Vizhener_key', Vizhener_key
	,	'\n'+'и назад:', Gronsfeld_key2
	);
//3. Тогда шифрование-дешифрование шифра Гронсфельда - есть работа с шифром Виженера:
console.log(
		"\n3. Шифр Гронсфельда - с ключом Виженера, по таблице Виженера:"
	,	'\n'+	'm = ', 'GRONSFELD', ' - сообщение'
	,	'\n'+	'k = ', Vizhener_key, '- ключ'
	,	'\n'+	'Шифр Гронсфельда - шифрование: '
	,	Vizhener( 'GRONSFELD', Vizhener_key )											//выдаст IRPSUFFQF - шифр Бофора
	,	'\n'+	'Шифр Гронсфельда - дешифрование:'
	,	Vizhener( Vizhener( 'GRONSFELD', Vizhener_key ), Vizhener_key, 'decrypt' ) 		//выдаст GRONSFELD - из шифра Бофора.
	,	'\n'+	'Сравнение с сообщением: ', "( decrypted === m )"
	,	( Vizhener( Vizhener( 'GRONSFELD', Vizhener_key ), Vizhener_key, 'decrypt' ) === 'GRONSFELD' ) //'GRONSFELD'? true
);

//4. Шифр Виженера (полная версия):
//Параметры: m - сообщение/шифротекст, k - ключ, mode - "encrypt"/"decrypt"
console.log(
		'\n4. Шифр Виженера (полная версия):'
	,	'\n'+	'm = ', m, ' - сообщение'
	,	'\n'+	'k = ', k, '- ключ'
	,	'\n'+	'Шифр Виженера - шифрование: ',	Vizhener( m, k )			//выдаст LXFOPVEFRNHR - шифр Виженера
	,	'\n'+	'Шифр Виженера - дешифрование: '
	,	Vizhener( Vizhener(m, k), k, 'decrypt' )							//выдаст ATTACKATDAWN - из шифра Виженера
	,	'\n'+	'Сравнение с сообщением: ', "( decrypted === m )"
	,	( Vizhener( Vizhener( m, k, 'encrypt'), k, 'decrypt' ) === m )		//m? true
);

//5. Шифр Бофора - через шифр Виженера (там другая таблица и шифротекст - сдвинутый атбаш по строкам).
//Параметры: m - ключ, k - сообщение/шифротекст, mode - 'decrypt' (только дешифрование)
//Особенность шифра Бофора - в том, что дешифрование представляет из себя повторное шифрование шифротекста - тем же ключом.
//То есть - одна и та же операция.
console.log(
		"\n5. Шифр Бофора (в талбице - атбаш по строкам):"
	,	'\n'+	'm = ', m, ' - сообщение'
	,	'\n'+	'k = ', k, '- ключ'
	,	'\n'+	'Шифр Бофора - шифрование по таблице Виженера: '
	,	Vizhener( k, m, 'decrypt' )											//выдаст LLTOLBETLNPR - шифр Бофора
	,	'\n'+	'Шифр Бофора - дешифрование по таблице Виженера:'
	,	Vizhener( k, Vizhener( k, m, 'decrypt' ), 'decrypt' ) 				//выдаст ATTACKATDAWN - из шифра Бофора.
	,	'\n'+	'Сравнение с сообщением: ', "( decrypted === m )"
	,	( Vizhener( k, Vizhener( k, m, 'decrypt' ), 'decrypt' ) === m )		//m? true
);

//6. Сдвинутый атбаш - через шифр Виженера (там другая таблица и шифротекст - атбаш, сдвинутый и по строкам по столбцам).
//Параметры: m или k - сообщение/шифротекст и ключ (или наоборот), mode - 'shifted_atbash'(только encrypt + атбаш к результату)
//Мало того, что одна и та же операция (дешифрование - есть шифрование шифротекста), но к тому же она еще и коммутативна.
//То есть, здесь, n-ные буквы (сообщения/шифротекста) и ключа - могут быть поменяны местами, давая тот же результат.
//Именно этим, сдвинутый атбаш - и приближается к шифру Вернама,
//так как при дешифровании шифром Вернама - операции XOR не важно где именно байты ключа, а где - байты шифротекста.
console.log(
		"\n6. Сдвинутый атбаш (в таблице атбаш, сдвинутый и по строкам и по столбцам):"
	,	'\n'+	'm = ', m, ' - сообщение'
	,	'\n'+	'k = ', k, '- ключ'
	,	'\n'+	'Сдвинутый атбаш - шифрование по таблице Виженера: '
	,	Vizhener( m, k, 'shifted_atbash' )										//выдаст OCULKEVUIMSI - шифр сдвинутого атбаша.
	,	'Тест коммутативности замены: '
	,	Vizhener( k, m, 'shifted_atbash' )										//То же самое, не важно где ключ, а где сообщение.
	,	'\n'+	'Сдвинутый атбаш - дешифрование по таблице Виженера: '
	,	Vizhener( Vizhener( k, m, 'shifted_atbash' ), k, 'shifted_atbash' )		//выдаст ATTACKATDAWN - из шифра сдвинутого атбаша.
	,	'Тест коммутативности замены: '
	,	Vizhener( k, Vizhener( k, m, 'shifted_atbash' ), 'shifted_atbash' )		//То же самое, не важно где ключ, а где шифротекст.
	,	'\n'+	'Сравнение с сообщением: '
	,	"( decrypted === m )"
	,	( Vizhener( k, Vizhener( k, m, 'shifted_atbash' ), 'shifted_atbash' ) === m ) //m? true
	,	'\n'+	'Коммутативность замены: '
	,	(
					(Vizhener( m, k, 'shifted_atbash') === Vizhener( k, m, 'shifted_atbash'))
				&&	(
						Vizhener( Vizhener( k, m, 'shifted_atbash' ), k, 'shifted_atbash' )
						===
						Vizhener( k, Vizhener( k, m, 'shifted_atbash' ), 'shifted_atbash' )
					)
		)																		//Коммутативность? true
);