Шифр виженера как найти длину ключа - Исправление недочетов и поиск решений вместе с Examum.ru

Шифр Вижинера и его разгадка

Время на прочтение
3 мин

Количество просмотров 73K

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

Блезом Вижинером в 17 веке был предложен довольно интересный метод шифрования. Ключом шифра служит специальная фраза. Эта фраза, многократно повторяясь, пишется над шифруемым текстом. Каждая буква секретного сообщения получается сдвигом каждой буквы исходного текста на определённое число, задаваемое буквой ключевой фразы (Буква А не даёт сдвига, буква Б — сдвиг на одну позицию, В — на две и т.д.).
Например попробуем зашифровать слово «СЕКРЕТ», пользуясь ключевой фразой «АБВ». Буква С не сдвигается, первая буква Е сдвигается на одну позицию, превращаясь в Ж, буква К сдвигается на две позиции, превращаясь в М. Продолжая шифровать сообщение, мы в итоге получим «СЖМРЖФ».

На протяжении трёх веков этот шифр считался практически не взламываемым. Первые попытки взлома этого шифра были предприняты в 19 веке. Все эти попытки были основаны на определении длины ключевой фразы. Если нам известна её длина, то весь зашифрованый текст мы можем разбить на фрагменты, каждый из которых кодируется одним и тем же сдвигом. В нашем примере буквы С, Р кодируются с нулевым сдвигом, Е, Е кодируются со сдвигом в единицу, К, Т кодируются со сдвигом 2. Если текст достаточно длинный, мы можем применить частотный анализ и тем самым, раскрыть исходное сообщение. Получается, что разгадка этого шифра сводится к поиску длины ключевой фразы.

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

Попробуем расшифровать методом Касицкого следующий текст: «ОАИТАБНПХЮПМЪАЭМАЗЧАФРЮЯЦМАТВУШКГЮНШИЪДООЯВТЫХЧЪТЫЖПЫТЕЭНХЕАПНХДРСЕЗЬУНЯЗ». Зашифрованный текст содержит три повторяющихся биграммы МА (позиции 16 и 26), ТЫ (позиции 44 и 49) и НХ (позиции 57 и 62). Биграмма МА повторяется на расстоянии в 10 позиций, биграммы ТЫ и НХ на расстоянии в 5 позиций. Скорее всего позиции длина ключевой последовательности равна 5. Рассматриваемый метод требует некоторого везения, т.к. в тексте могут возникать «случайные» биграммы. Их вероятность много ниже, чем у «регулярных», но в небольших текстах они могут значительно усложнить расшифровку.

Прежде чем окончательно расшифровать текст, мы рассмотрим ещё один метод определения длины ключа, предложенный Фридманом. Суть метода в циклическом сдвиге сообщения. Полученные таким образом сообщения записываются под оригинальным шифротекстом и подсчитывается число совпавших букв в верхней и нижней строке. На основе этих чисел вычисляется т.н. индекс совпадений, равный отношению количества совпадений к полной длине сообщения. Для русских текстов индекс совпадений равен примерно 6%, но для случайных текстов этот индекс равен 1/32, т.е. приблизительно 3%. На этом факте и основан метод Фридмана. Текст записывается со сдвигом в 1,2,3 и т.д. позиций и для каждого сдвига вычисляется индекс совпадений. Циклический сдвигая наше сообщение получаем:
Сдвиг Совпадений Индекс
2 0 0.000
3 5 0.068
4 2 0.027
5 8 0.110 (!)
6 1 0.014
7 1 0.014
8 2 0.027
При сдвиге 5 индекс резко возрастает, следовательно длина ключевого слова скорее всего равна 5. Понять почему индекс резко возрастает довольно просто. В случае, когда все символы сдвигаются на одну и ту же позицию, индекс совпадения такой же, как и у исходного текста. В случае, когда мы вычисляем индекс для шифра Вижинера мы во всех случаях (кроме того, где длина сдвига равна длине ключа) сравниваем фактически случайный текст.

Определив длину ключа мы можем, воспользовавшись таблицей частоты букв, выяснить, что зашифровано было известное детское стихотворение:
Наша Таня громко плачет:
Уронила в речку мячик.
Таня, Танечка, не плачь,
Не утонет в речке мяч!
В качестве пароля была взята фамилия автора «Барто».

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

Источник

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

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

Этот метод является простой формой многоалфавитной замены. Шифр Виженера изобретался многократно. Впервые этот метод описал Джованни-Баттиста Беллазо (Giovan Battista Bellaso) в книге La cifra del. Sig. Giovan Battista Bellasо в 1553 году , однако в 19 веке получил имя Блеза Виженера , швейцарского дипломата. Метод прост для понимания и реализации, он является недоступным для простых методов криптоанализа.
Шифровани
Квадрат Виженера или таблица Виженера, может быть использована для заширования и расшифрования.
В шифре Цезаря каждая буква алфавита сдвигается на несколько позиций; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифрования может использоваться таблица алфавитов, называемая квадрат Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причем каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На разных этапах кодировки шифр Виженера использует различные алфавиты из этой таблицы. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Например, предположим, что исходный текст имеет вид:

ATTACKATDAWN

Человек, посылающий сообщение, записывает ключевое слово(«LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:

LEMONLEMONLE

Первый символ исходного текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; т.е. второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.
Пример
Исходный текст: ATTACKATDAWN
Ключ: LEMONLEMONLE
Зашифрованный текст: LXFOPVEFRNHR

Дешифрования

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

Из наблюдения за частотой совпадения следует:

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

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

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

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

Поиск длины ключа. Можно анализировать распределение частот в зашифрованном тексте с различным прореживанием. То есть брать текст, включающий каждую 2-ю букву зашифрованного текста, потом каждую 3-ю и т. д. Как только распределение частот букв будет сильно отличаться от равномерного (например, по энтропии), то можно говорить о найденной длине ключа.
Криптоанализ. Совокупность 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(
		'nn1. Шифр Гронсфельда (Урезанная версия шифра Виженера 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
);

Вау!! 😲 Ты еще не читал? Это зря!

симметричные шифры ,

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

Источник

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

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

Описание алгоритма

В шифре Цезаря каждая буква алфавита сдвигается на несколько позиций; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова.

Квадрат Виженера

Например, предположим, что исходный текст имеет вид:

ATTACKATDAWN

Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:

LEMONLEMONLE

Первый символ исходного текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.

Исходный текст:   ATTACKATDAWN

Ключ: LEMONLEMONLE

Зашифрованный текст: LXFOPVEFRNHR

Расшифрование

Криптоанализ шифра может быть построен в два этапа:

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

Практический пример

Задание:

Необходимо расшифровать данный текст:

LoatuvftYejeerzAgibeejwzriyazfrkknxefvoxvhanvmsxlizyjzhnxmvhnjwyhnonafjgmiunfrbjxnzrrgfkgearfywv.Bnotfrqgwesiprqzbvotvvgomcumozbklszuqzsypizhslbjtmkngrzggdgpccwkwsiireqk,tsceycoyvuztveu-kwgktrtvthlugvvgggdonafjgmibengdxhaihrj.HnxUtiivfybte’scfgomiunvehnxngtvfbgeutiivfybterneyoggypefjoweyprigatsovrvjowetcrkcomsgcuzsbxmkngj,ovhsotvmsofamenergiaysvfblhrkxpvzrxnie:FWsjNwgsnnoxwejtuv5hnilgcrzbzaeGnalorBnjecvbjxnzNnkwugarUazjkksotlIotditgf.JTkwUkqhzdybtygerrattksjzhnxsyeakwgesqiycgzhgovrkvkfaiozgszbtovrrrbtnzatvknxnotpfakltugrkhogggjbs.HnxktojcsjzegcdlwxxdgtFWsjNetaocsymhkmgfpuedrysrqkmhkdrdotwsgnqtvgelkntvguytne21fkqkgtarlrgcxlrafkcihnzrvsizxtutuvrkoerocdstmoltuvzuvarcbdaagizy.

Решение:

Для быстрого и качественного решения используем программу Cryptools: Вставляем наш текст в созданное окно:

Выбираем вкладку Analysis > Symmetric encryption (classic) > Ciphertext-only > Vigenere

Далее программа находит длину ключа :

Жмём > Continue Далее находит сам ключ:

Жмём> Decrypt , и получаем расшифрованный текст:

Расшифрованный текст: SoutdernFederalUnivensityisamodernreoearchuniversitysithemphasisoninjovationsandentrapreneurship.Initoacademicactiviteesitcombinesstuzieswithfundamenpalandappliedsciance,aswellascutteng-edgetechnologeesandinnovativewpproaches.TheUnirersity’spositionenthenationalunirersityrankingspnovidespersuasivaevidencetoitsacdievements,apositeveimageandapasseonforexcellence:OFedUwasawardedtde5thplaceintheAnjualIndependentNwtionalUniversituRankings.SFedUeqqipsitsgraduatessithessentialskihlstogivethemacoipetitiveadvantacewhenitcomestogattingajob.TheknosledgeacquiredatOFedUenablesthempoboldlyfacethedamandsandchallencesofthe21stcenturuaswellastocontrebutetothedevelolmentofthelocalckmmunity.

Скачать программу можно здесь: https://www.cryptool.org/en/ct1-downloads

Быстрая реализация на Python

Шифрование

m = "ATTACKATDAWN"  # исходное сообщение
k = "LEMON"  # ключ

k *= len(m) // len(k) + 1  # подгоняем ключ
c = ''.join([chr((ord(j) + ord(k[i])) % 26 + ord('A')) for i, j in enumerate(m)])  # шифруем
print(c) # LXFOPVEFRNHR

Расшифровывание

c = "LXFOPVEFRNHR"  # шифрованое сообщение
k = "LEMON"  # ключ

k *= len(c) // len(k) + 1  # подгоняем ключ
m = ''.join([chr((ord(j) - ord(k[i])) % 26 + ord('A')) for i, j in enumerate(c)])  # расшифровываем
print(m) # ATTACKATDAWN

results matching ««

No results matching ««

Источник

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

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

Были изобретены несколько методов, чтобы найти длину ключа. Один метод рассмотрим ниже. В так называемом тесте Казиского (Kasiski) криптоаналитик в зашифрованном тексте ищет повторные сегменты по крайней мере из трех символов. Предположим, что найдены два сегмента, и расстояние между ними d. Криптоаналитик предполагает, что m делит d, где m — длина ключа. Если можно найти больше повторных сегментов с расстоянием d₁, d₂, …., d_n, тогда НОД(d₁, d₂, …., d_n….)/ m. Это предположение логично, потому что если два символа одинаковы и (k = 1, 2…) — символы, выделенные в исходном тексте, то одинаковы и символы, выделенные в зашифрованном тексте. Криптоаналитик использует сегменты по крайней мере из трех символов, чтобы избежать случаев, где символы имеют один и тот же ключ. Пример 4.20 может помочь нам п
онять эти рассуждения.
После того как длина ключа была найдена, криптоаналитик использует идею, показанную в примере 4.18. Здесь зашифрованный текст делится на m различных частей и применяется метод, используемый в криптоанализе аддитивного шифра, включая атаку частоты. Каждая часть зашифрованного текста может быть расшифрована и соединена с другими, чтобы создать целый исходный текст, другие слова. Весь зашифрованный текст не сохраняет частоту отдельной буквы исходного текста, но каждая часть делает это.

Пример 4.19

Предположим, что мы перехватили следующий зашифрованный текст:

LIOMWGFEGGDVWGHHCQUCRHRWAGWIOWQLKGZETKKMEVLWPCZVG’TH
VTSGXQOVGCSVETQLTJSUMVWVEUVLXEWSLGFZMVVWLGYHCUSWXQH —
KVGSHEEVFLCFDGVSUMPHKIRZDMPHHBVWVWJWIXGFWLTSHGJOUEEHH-
VUCFVGOWICQLIJSUXGLW

Тест Казиского на повторение сегментов на три символа приводит к результатам, показанным в таблице 4.4.

Таблица
4.4.
Тест Казиского для примера 4.19

Комбинация	Первое расстояние	Второе расстояние	Разность
JSU	68	168	100
SUM	69	117	48
VWV	72	132	60
MPH	119	127	8

Наибольший делитель — 4, что означает длину ключа, пропорциональную 4. Сначала пробуем m = 4. Делим зашифрованный текст на четыре части. Часть C₁ состоит из символов 1, 5, 9…; часть C₂ состоит из символов 2, 6, 10…, и так далее. Используем статистическую атаку каждой части отдельно. Перебираем расшифровывающиеся части по одному символу одновременно, чтобы получить целый исходный текст.

С₁	LWGW	CRAO	KTEP	GTQC	TJVU	EGVG	UQGE	CVPR	PVJG	TJEU	GCJG
P₁	jueu	apym	ircn	eroa	rhts	thin	ytra	hcie	ixst	hcar	rehe
C₂	IGGG	QHGW	GKVC	TSOS	QSWV	WFVY	SHSV	FSHZ	HWWF	SOHC	OQSL
P₂	usss	ctsl	swho	feae	ceih	cete	soec	atnp	nkhe	rhck	esex
C₃	OFDN	URWQ	ZKLZ	HGVV	LUVL	SZWH	WKHF	DUKD	HVIW	HUHF	WLUW
P₃	lcae	rotn	whiw	edss	irsi	irh	eteh	retl	tiid	eatr	airt
C₄	MEVN	CWIL	EMWV	VXGE	TMEX	LMLC	XVEL	GMIM	BWHL	GEVV	ITX
P₄	iard	yseh	aisr	rtca	piaf	pwte	thec	arha	esft	erec	tpt

Если исходный текст не имеет смысла, попробуем с другим m.

В рассматриваемом случае исходный текст имеет смысл (читаем по столбцам).

Julius Caesar used a cryptosystem in his wars, which is now referred to as Caesar chipper. It is an additive chipper with the key set to three. Each character in the plaintext is shift three characters to create ciphertext.

Перевод этого текста приведен ниже.

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

Шифр Хилла

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

В шифре Хилла ключ — квадратная матрица размера ., в котором m. является размером блока. Если мы вызываем ключевую матрицу K, то каждый элемент k_i,j определяется матрицей, как показано на рис. 4.15.

Рис.
4.15.
Ключ в шифре Хилла

Покажем, как получается один блок зашифрованного текста. Если мы обозначим m символов блоков исходного текста P₁, P₂ …, P_m, соответствующие символы в блоках зашифрованного текста будут C₁, C₂ , …, C_m. Тогда мы имеем

C₁ = P₁k₁₁+P₂k₂₁+……+P_mk_m1
C₂ = P₁k₁₂+P₂k₂₂+……+P_mk_m2
………………………………………………………
C_m = P₁k_1m+ P₂k_2m +……+ P_mk_mm

Уравнения показывают, что каждый символ зашифрованного текста, такой, как C₁, зависит от символов всего исходного текста в блоке (P₁, P₂,…, P_m). Однако мы должны знать, что не все квадратные матрицы имеют мультипликативные инверсии в Z₂₆, так что Алиса и Боб должны быть осторожны в выборе ключа. Боб не сможет расшифровать зашифрованный текст, передаваемый Алисой, если матрица не имеет мультипликативной инверсии.

Ключевая матрица в шифре Хилла должна иметь мультипликативную инверсию.

Пример 4.20

Использование матриц позволяет Алисе зашифровать весь исходный текст. В этом случае исходный текст — матрица, в которой l является номером блоков. Например, исходный текст «code is ready» («код готов»), может быть представлен как матрица при добавлении дополнительного фиктивного символа «z» к последнему блоку и удалении пробелов; зашифрованный текст выглядит как «OHKNIHGKLISS». Боб может расшифровать сообщение, используя инверсную матрицу-ключ. Шифрование и дешифрование показано на рис. 4.16.

Рис.
4.16.
Пример 4.20

Криптоанализ шифров Хилла

Криптоанализ только для зашифрованного шифрами Хилла текста труден. Во-первых, атака грубой силы при шифре Хилла чрезвычайно сложна, потому что матрица-ключ — . Каждый вход может иметь одно из 26 значений. Во-первых, это означает размер ключа ${26^{m times m}}$ . Однако, не все матрицы имеют мультипликативную инверсию. Поэтому область существования ключей все же не такая огромная.

Во-вторых, шифры Хилла не сохраняют статистику обычного текста. Ева не может провести анализ частоты отдельных букв из двух или трех букв. Анализ частоты слов размера m мог бы cработать, но очень редко исходный текст имеет много одинаковых строк размера m. Ева, однако, может провести атаку на шифр, используя метод знания исходного текста, если она знает значение m и знает пары «исходный текст/зашифрованный текст», по крайней мере m блоков. Блоки могут принадлежать тому же самому сообщению или различным сообщениям, но должны быть различны. Ева может создать две . матрицы, P (обычный текст) и C (зашифрованный текст), в котором соответствующие строки представляют известные пары обычного/зашифрованного текста. Поскольку C = PK, Ева может использовать отношения K = CP^-1, чтобы найти ключ, если P является обратимым. Если P
не является обратимым, то Ева должна задействовать различные наборы m пар обычного/зашифрованного текста.

Если Ева не знает значение m, она может попробовать различные значения при условии, что m не является очень большим.

Пример 4.21

Предположим, что Ева знает, что m = 3. Она перехватила три пары блока исходного/зашифрованного текста (не обязательно из того же самого сообщения), как показано на рис. 4.17.

Рис.
4.17.
Пример 4.22, формирования шифра зашифрованного текста

Она составляет матрицы P и C из этих пар. Поскольку в данном случае матрица P обратима, она инвертирует эту матрицу и умножает ее на C, что дает матрицу ключей K, как это показано на рис. 4.18.

Рис.
4.18.
Пример 4.22, поиска ключа

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

Одноразовый блокнот

Одна из целей криптографии — идеальная секретность. Исследования Шеннона показали, что идеальная секретность может быть достигнута, если символы исходного текста зашифрованы с помощью ключа, выбранного случайно из некоторой области ключей. Например, аддитивный шифр может быть легко взломан, потому что используется один и тот же ключ. Но даже и этот шифр может быть идеальным, если ключ, который применяется для шифрования каждого символа, выбран случайно из множества ключей (00, 01, 02…. 25): если первый символ зашифрован с помощью ключа 04, второй символ — с помощью ключа 02, третий — с помощью ключа 21, и так далее. Атака «только для зашифрованного текста» становится невозможна. Если передатчик изменяет ключ, используя каждый раз иную случайную последовательность целых чисел, другие типы атак также будут невозможны.

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

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

Роторный шифр

Хотя шифры одноразового блокнота не применяются на практике, один шаг от него к более защищенному шифру — роторный шифр. Он возвращается к идее моноалфавитной подстановки, но меняет принцип отображения исходного текста в символы зашифрованного текста для каждого символа исходного текста. Рисунок 4.19 показывает упрощенный пример роторного шифра.

Рис.
4.19.
Роторный шифр

Ротор, показанный на рис. 4.19, применен только для 6 букв, но реальные роторы используют 26 букв. Ротор постоянно связывает символы исходного и зашифрованного текстов, но подключение обеспечивается щетками. Обратите внимание, что соединение символов исходного и зашифрованного текстов показано так, как если бы ротор был прозрачен и можно было видеть внутреннюю часть.

Начальная установка (позиция) ротора — ключ засекречивания между Алисой и Бобом — это зашифрованный первый символ исходного текста. Используя начальную установку, второй символ зашифрован после того, как проведено первое вращение (на рис. 4.19 — это поворот на 1/6 круга, на реальной установке — поворот на 1/26 ), и так далее.

Слово с тремя буквами, такими как «bee», зашифровано как «BAA«, если ротор неподвижен (моноалфавитный шифр подстановки), но оно будет зашифровано как «BCA«, если он вращается (роторный шифр). Это показывает, что роторный шифр — многоалфавитный шифр, потому что два появления того же самого символа исходного текста зашифрованы как различные символы.

Роторный шифр является стойким к атаке грубой силы, как моноалфавитный шифр подстановки, потому что Ева должна найти первое множество отображений среди возможных 26! (факториал). Роторный шифр является намного более стойким к статистической атаке, чем моноалфавитный шифр подстановки, потому что в нем не сохраняется частота употребления буквы.

Машина «Энигма»

Машина «Энигма» была первоначально изобретена в Сербии, но была изменена специалистами немецкой армии и интенсивно использовалась в течение Второй Мировой Войны. Машина базировалась на принципе шифров ротора. Рисунок 4.20 показывает упрощенную схему построения машины.

Рис.
4.20.
Примерное построение Машины Энгима

Ниже перечислены главные компоненты машины.

Клавиатура с 26 -ю ключами, используемыми для того, чтобы вводить исходный текст при шифровании, и для того, чтобы вводить зашифрованный текст при расшифровке.
Ламповая панель с 26 -ю лампами, которая показывает символы зашифрованного текста при шифровании и символы исходного текста при дешифровании.
Коммутационная панель с 26 -ю штепселями, вручную подключенными 13 -ю проводами. Конфигурация изменяется каждый день, чтобы обеспечить различное скрэмблирование.
Три замонтированных ротора, такие же как рассмотренные в предыдущей секции. Эти три ротора выбираются ежедневно из пяти доступных роторов. Быстрый ротор вращается на 1/26 поворота при каждом символе, введенном с помощью клавиатуры. Средний ротор делает 1/26 поворота при каждом полном повороте быстрого ротора. Медленный ротор делает 1/26 поворота для каждого законченного поворота среднего ротора.
Отражатель, который является постоянным и предварительно замонтированным.

Кодовая книга — справочник шифров

Чтобы использовать «Энигму», была издана кодовая книга, которая в течение каждого дня дает несколько параметров настройки, включая:

a. три ротора, которые должны быть выбраны из пяти доступных;

b. порядок, в котором эти роторы должны быть установлены;

c. параметры установок для коммутационной панели;

d. код с тремя буквами дня.

Источник

Дмитрий Михайлович Беляев

Эксперт по предмету «Информатика»

Задать вопрос автору статьи

Общие сведения о шифре Виженера

Замечание 1

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

Шифр Виженера, по сути, был изобретен несколько раз. Впервые данный метод был описан Джованом Баттистой Беллазо в его книге, выпущенной в 1553 году. Тем не менее, в девятнадцатом веке он был назван именем Блеза Виженера, который был французским дипломатом. Метод является простым для понимания и реализации, и его невозможно взломать при помощи простых методик криптографического анализа.

В шифре Цезаря все буквы алфавита должны сдвигаться на определенное количество позиций. К примеру, в шифре Цезаря, если выбран сдвиг плюс три позиции, то буква A стала бы D, а буква B стала бы E и дальше аналогично. Шифр Виженера составлен из очередности ряда шифров Цезаря с разными величинами сдвига. Для зашифровки текста можно использовать таблицу алфавитов, именуемую квадратом или таблицей Виженера.

Сдай на права пока
учишься в ВУЗе

Вся теория в удобном приложении. Выбери инструктора и начни заниматься!

Получить скидку 3 000 ₽

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

ATTACKATDAWN

Пользователь, который посылает сообщение, должен записать ключевое слово, например, «LEMON» циклически до тех пор, пока его длина не сравняется с длиной исходного текста:

LEMONLEMONLE

Первый символ исходного текста A шифруется последовательностью L, являющейся первой буквой ключа. Первый символ L зашифрованного текста расположен на пересечении строки L и столбца A в таблице Виженера. Таким же образом для второй буквы исходного текста должен использоваться второй символ ключа; то есть второй символ зашифрованного текста X расположен на пересечении строки E и столбца T. Оставшаяся часть исходного текста должна шифроваться аналогичным методом. Таким образом получаем:

«Взлом шифра Виженера» 👇

Исходный текст: ATTACKATDAWN.
Используемый ключ: LEMONLEMONLE.
Шифрованный текст: LXFOPVEFRNHR.

Расшифровка должна производиться следующим образом:

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

Взлом шифра Виженера

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

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

Тесты Фридмана и Касиски способны оказать помощь в определении длины ключа. В 1863-ем году Фридрих Касиски стал первым, кто сделал публикацию успешного алгоритма атаки на шифр Виженера. Но следует отметить, что Чарльз Беббидж создал данный алгоритм еще в 1854-ом году. В то время когда Беббидж пытался взломать шифр Виженера, Джон Холл Брок Твейтс предложил новый шифр в «Journal of the Society of the Arts». А когда Беббидж доказал, что шифр Твейтса представляет собой только частный случай шифра Виженера, Твейтс предложил ему его взломать. Беббидж сумел расшифровать текст, который оказался поэмой «The Vision of Sin» Альфреда Теннисона, зашифрованной при помощи ключевого слова Emily. Это было имя жены поэта.

Тест Касиски базируется на том факте, что отдельные слова, такие как «the», могут шифроваться при помощи одинаковых символов, что может приводить к повторению групп символов в зашифрованном тексте. К примеру, сообщение, зашифрованное ключом ABCDEF, может не всегда одинаково шифровать слово «crypto»:

Ключ: ABCDEF AB CDEFA BCD EFABCDEFABCD.
Исходный текст: CRYPTO IS SHORT FOR CRYPTOGRAPHY.
Зашифрованный текст: CSASXT IT UKSWT GQU GWYQVRKWAQJB.

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

Ключ: ABCDAB CD ABCDA BCD ABCDABCDABCD.
Исходный текст: CRYPTO IS SHORT FOR CRYPTOGRAPHY.
Зашифрованный текст: CSASTP KV SIQUT GQU CSASTPIUAQJB.

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

Тест Фридмана (иногда именуемый каппа-тестом) изобрел Вильям Фридман в 1920-ом году. Фридманом использовался индекс совпадения, измеряющий частоты повторения символов, для того чтобы взломать шифр. Зная вероятность Kp того, что пара случайно отобранных символов текста совпадает (примерно 0,067 для английского языка) и вероятность совпадения пары случайно отобранных символов алфавита Kr (примерно 1 / 26 = 0,0385 для английского языка), можно оценить длину ключа как:

Рисунок 1.

Наблюдения за частотой совпадения показали, что:

Рисунок 2.

где :

С является размером алфавита,
N является длинной текста,
ni является наблюдаемыми частотами повторения символов зашифрованного текста.

Находи статьи и создавай свой список литературы по ГОСТу

Поиск по теме

Источник