Вступление. Секретная система.

 Подстановочные шифры обычно относят к классической криптографии и, всилу их низкой стойкости к взлому по сравнению с современными шифрами, их теперь мало используют. Но их взлом вовсе не так прост как может показаться. Для начала рассмотрим базовые понятия современной криптографии, введенные К.Шенноном. Важнейшим из них является понятие Секретной системы. На схеме присутствует два случайных процесса - источник сообщений и источник ключей, которые с некоторой вероятностью передают ключ и сообщение Шифровальщику. Шифровальщик применяет к сообщению некоторую функцию в зависимости от выбранного ключа. Tk - некоторое взаимно однозначное отображение множества сообщений во множество криптограмм. Ключ, по которому выбрано это отображение, передается по секретной линии (почтой, курьером или из рук в руки). Криптограмма (зашифрованное сообщение) - по небезопасной линии (в газете, по телевизору,...). Криптоаналитик противника может перехватить её и попытаться расшифровать.
 Секретная система – семейство однозначно обратимых отображений Ti множества возможных сообщений во множество криптограмм , при этом отображение Ti имеет вероятность pi.
Необходимо также определить, какой информацией обладает противник. Во-первых, он обладает криптограммой, а также некоторой информацией о том, какого рода информация находится в криптограмме - язык, характер переписки,... Во-вторых, обычно предполагается, что противник знает, по какому алгоритму зашифровано сообщение. Это предположение известно как Правило Киргхофса (Auguste Kerckhoffs ‘Военная криптография’ 1883 г.) - стойкость криптосистемы должна определяться только секретностью ключа шифрования. Другими словами, при оценке надёжности шифрования необходимо предполагать, что противник знает всё об используемой системе шифрования – семейство отображений Ti и вероятности выбора различных ключей.. Ведь алгоритмов, по которому может быть зашифровано сообщение не так уж много по сравнению с возможными ключами. И поэтому противнику не составит труда перебрать их всех. В конце концов он может узнать о системе шифрования просто дизассемблировав программу, послать шпиона, или дать взятку кому-нибудь...

Подстановочные шифры

  Подстановочным шифром называется шифр, в котором каждый символ открытого текста в шифротексте заменяет другим символом. Получатель инвертирует подстановку шифротекста, восстанавливая открытый текст. В классической криптографии подстановочные шифры делят на следующие виды:   Примеры подстановочных шифров:
Шифр Цезаря (Caesar) - алфавит сдвигается циклически на некоторое количество символов. Количество таких сдвигов равно размеру алфавита. Поэтому ключей столько же, сколько символов в алфавите (26 для английского).
Афинный шифр - алфавит сдвигается по некоторой линейной функции yi=a*xi+b. Ключом является упорядоченная пара пара (a,b).
Простая подстановка - один из символов в тексте заменяется на другой. Ключом является некоторая перестанова алфавита. Поэтому всего ключей N! , где N - количество символов в алфавите.
Перестановка с периодом D - cообщение делится на группы символов по D штук, в каждой из которых выполняется перестановка , заданная ключом из первых D чисел. Ключ - некоторая перестановка D различных чисел.
Шифр Хилла - сначала выбираем числовое кодирование всех символов некоторого алфавита. Ключом является квадратная матрица из тех же самых чисел некоторого размера n, обратимая над кольцом вычетов ZN (N - размер алфавита). В шифруемом тексте символы заменяются их числовыми эквивалентами , и записываются построчно в матрицу из n строчек.( если текст не заполняет всю матрицу, то оставшиеся позиции можно заменить некоторыми символами). Криптограмма получается умножением матрицы-ключа на матрицу сообщения. Обратное преобразование осуществляется с помощью обратной к ключу матрицы.
Роторная машина - состоит из движущихся дисков, каждый из которых проводит замену одного символа другим. Диски движутся В результате входной символ шифруется несколькими заменами. Период шифра замены равен 26k , где k - количество дисков . Самая знаменитая шифровальная машинка - Энигма - была взломана англичанами (Э.Пост, А.Тьюринг).
Шифр Виженера (Vigenerе cipher) - текст шифруется ключевым словом, длинна которого является периодом шифра. Шифрование происходит по формуле ei = mi + ki(mod 26) , где ei - i-й символ криптограммы, mi - i-й символ шифруемого текста, ki - i mod D символ ключа.
Шифр Бофора - похож на шифр Виженера, но шифрование происходит по формулам ei = ki - mi(mod 26) или ei = mi - ki(mod 26)
Шифр Вернама - шифр Виженера с неограниченным, неповторяющимся ключом.

Почему можно взломать шифр?

   Взломать шифр - значит определить наиболее вероятное сообщение из возможных.
Пусть возможные исходные сообщения M1...Mn преобразованы во множество криптограмм E1... En (E = TiM). Тогда шифровальщик до того как получить криптограмму может вычислить априорные вероятности этих сообщений, основываясь на знаниях о языке, о характере переписки, и тд. Например, если противник знает, что мы обмениваемся словами длинны N на английском языке, то вероятнее всего, что это будет самое частое слово длинны N в языке. Кроме того , зная алгоритм шифрования, противник может вычислить априорные вероятности ключей. Так, если все ключи в шифре простой подстановке равновероятны, то априорная вероятность любого из них 1/26! (для алфавита в 26 символов). После перехвата сообщения противник может вычислить апостериорные вероятности исходных сообщений и ключей и в заыисимости от этого корректировать свои действия при расшифровке. Ясно, что если априорные вероятности равны апостериорным , то получение криптограммы не дает противнику никакой информации (строгое доказательство в статье К.Шеннон "Теория связи в секретных системах"). Такая система называется совершенно секретной В совершенно секретной системе число возможных сообщений и число ключей равны. Каждое сообщение M связывается с каждым E только одной линией. Все ключи равновероятны. Если число сообщений бесконечно, то никакой конечный ключ не даст абсолютной секретности. Ключ должен иметь размер равный длине сообщения (Шифр Вернама, "одноразовый блокнот") и быть непериодическим. Получатель расшифровывает сообщение используя тот же самый ключ. Так как все исходные тексты равновероятны, у противника нет возможности определить , какой из них является правильным.

Избыточность.

  Апостериорные вероятноси сообщений, написанных на некотором языке, можно вычислить всиду избыточности языка, на котором оно написано.
Энтропия языка - мера количества информации, приходящейся на одну букву. Она вычисляется по формуле HL=limr->inf Hr/r , где Hr - энтропия r-граммы. Например, избыточность 75% показывает, что 3 из 4 букв текста можно выкинуть без потери информации. Устранить избыточность можно сжатием, например по алгоритму Хаффмана.

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

   При взломе шифра Виженера можно выделить следующие этапы:
1) Определение длинны ключа (периода).
2) Определление самого ключа.
(1)Определение длинны ключа (периода)
Тест Казиски (1863г.).
Если в шифротексте встречаются два одинаковых отрезка, то с большой вероятностью расстояние между ними кратно длине ключа.
Тест Фридмана (1920г.).
Индекс совпадения – вероятность того, что две случайно выбранные буквы строки совпадут. Он вычисляется по формуле где fi - число вхождений i-й буквы алфавита в строку, m - длина строки. Для естественного языка можно вычислить взаимный индекс совпадений как сумма квадратов частот всех символов языка. На схеме показан взаимный индекс совпадений для различных языков. Если N - длина ключа, то для строки , составленной из каждой N-й буквы криптограммы взаимный индекс совпадений останется таким же, как и в исходном тексте, так как эта строка шифруется обычной заменой по Цезарю.
y0yNy2*Ny3*N...
y1yN+1y2*N+1y3*N+1...
...............
yN-1y2*N-1y3*N-1y4*N-1...
Последовательно перебирая возможные периоды, вычисляя индекс совпадений и выбирая период , при котором он будет более приближен к индексу совпадений языка , можно легко определить период .


(2) Определение самого ключевого слова. Взаимный индекс совпадений – вероятность того, что случайно выбранная буква из одной строки совпадет со случайно выбранной буквой другой строки. Он вычисляется по формуле , где fi и fi1 - число вхожденйи i-й буквы алфавита в каждую из двух строк, m - длина строки. Пусть s=(s1 ,s2 ,…, sN ) – истинное ключевое слово, Yi – i-ая строка таблицы из пункта (1). (строка , составленная из N-ых символов строки со смещением i – всего N строк). Каждая из этих строк зашифрована шифром Цезаря. Тогда для любых двух строк можно вычислить Взаимный индекс совпадений. , где pi - частота соответствующего символа. (si - sj ) mod 26 - относительный сдвиг Yi и Yj . Из таблицы относительных сдвигов для английского языка видно, что более всего выделяется сдвиг на 0 символов (т.е отсутствие сдвига). Теперь берем две каких-нибудь строки Yi и Yj и , перебирая различные сдвиги считаем взаимные индексы совпадений. MIc(Yi,Yj+s), 0<=s<=n-1, 1<=i < j<=N. Если сдвиг s - настоящий сдвиг между этими строками, то Взаимный индекс совпадений близок к 0.066.

Предполагаемый период12345678
Индексы совпадений для подстрок 0.0458 0.0467
0.0434		 0.0415
0.0427
0.0542		 0.0485
0.0399
0.044
0.0451		 0.0559
0.0359
0.0532
0.0418
0.0446		 0.0439
0.0418
0.0567
0.0367
0.0395
0.0518		 0.0728
0.0621
0.0583
0.0612
0.0708
0.0835
0.0664		 0.0513
0.0349
0.0431
0.0459
0.0437
0.0382
0.0431
0.0415
среднее арифметическое индексов совпадений 0.0458 0.045 0.0461 0.0443 0.0462 0.045 0.0678 0.0427
Пример: Зашифруем текст :

"In 1863, Friedrich Kasiski published a method (probably discovered secretly and independently before the Crimean War by Charles Babbage) which enabled the calculation of the length of the keyword in a Vigenere ciphered message. Once this was done, ciphertext letters that had been enciphered under the same alphabet could be picked out and attacked separately as a number of semi-independent simple substitutions - complicated by the fact that within one alphabet letters were separated and did not form complete words, but simplified by the fact that usually a tabula recta had been employed."

Словом "awengar". Получится криптограмма :

"ij 1863, jeoeuregu qajioov vuslewukd r maxuud (grkfnhlp dewpuvvrah fkcieppl gnu ijhrveedargry sebsek tye yvvsern see hy thwvyks saxfnme) nhegu knrbhiq zhv cwppalrtesa uf kha prtgkh kj gne beuabxd zn w zvmeeeni popyeniq sejswkr. unte plvy wrs zsak, czpdiezeot higzeis plnz hrd xirt eecetukrvd qrqkr kha wnse rlllnhek ckyyj bv pegxkd fup eaj aktwgxkd jeleegtvlu ef g nlmxie uf jeim-vtdvparqknk seqcre juxwgotltesay - cfmlpviakez fl zhv fwgg zhrt smgnie oji nrpyaxig rektavf ceie oicgrrtah ntd uiz rbz ffri gbspcepi jurus, xyg yidphmsoeu bu xuk frcp xugt lsqeyry r twfhra ieyxn nau baia kmglkcrj."

Определим длину ключевого слова по (1). Из таблицы видно, что при периоде 7 средний индекс совпадений в подстроках максимален. Период очевидно равен 7.
Определим смещения по (2).
0.0861 0)0.0471 1)0.0326 2)0.0383 3)0.0397 4)0.0206 5)0.0214 6)0.0351 7)0.034 8)0.0295 9)0.0381 10)0.0606 11)0.0408 12)0.0371 13)0.0408 14)0.0606 15)0.0381 16)0.0295 17)0.034 18)0.0351 19)0.0214 20)0.0206 21)0.0397 22)0.0383 23)0.0326 24)0.0471 25)0.0861 26) 0.0861 0
0.0459 0)0.0265 1)0.0269 2)0.0432 3)0.0659 4)0.0361 5)0.0293 6)0.0512 7)0.0544 8)0.0269 9)0.0326 10)0.0416 11)0.032 12)0.0279 13)0.0373 14)0.0569 15)0.0289 16)0.031 17)0.0397 18)0.052 19)0.0385 20)0.0369 21)0.0408 22)0.0448 23)0.0271 24)0.0244 25)0.0459 26)0.0659 4
0.0457 0)0.0287 1)0.0306 2)0.0365 3)0.0346 4)0.031 5)0.0334 6)0.0469 7)0.0353 8)0.0402 9)0.0389 10)0.053 11)0.0461 12)0.042 13)0.03 14)0.0377 15)0.0265 16)0.0191 17)0.0308 18)0.0361 19)0.0361 20)0.043 21)0.0714 22)0.0446 23)0.0402 24)0.0406 25)0.0457 26)0.0714 22
0.0385 0)0.0312 1)0.0467 2)0.0369 3)0.0383 4)0.0279 5)0.044 6)0.0385 7)0.0269 8)0.0406 9)0.0395 10)0.0314 11)0.0365 12)0.0632 13)0.0471 14)0.0363 15)0.0279 16)0.0546 17)0.0304 18)0.0257 19)0.0316 20)0.0359 21)0.0304 22)0.0361 23)0.0616 24)0.0412 25)0.0385 26)0.0632 13
0.0271 0)0.0434 1)0.0389 2)0.0259 3)0.0261 4)0.0532 5)0.0306 6)0.0297 7)0.0414 8)0.0577 9)0.0448 10)0.0332 11)0.0387 12)0.0463 13)0.0265 14)0.0193 15)0.0389 16)0.0367 17)0.0355 18)0.0406 19)0.0761 20)0.0422 21)0.023 22)0.0414 23)0.0518 24)0.0297 25)0.0271 26)0.0761 20
0.079 0)0.0438 1)0.0354 2)0.0374 3)0.0523 4)0.0258 5)0.0306 6)0.0354 7)0.036 8)0.03 9)0.03 10)0.0472 11)0.0325 12)0.0461 13)0.0482 14)0.0635 15)0.0366 16)0.0368 17)0.0229 18)0.0269 19)0.0225 20)0.0227 21)0.0325 22)0.037 23)0.0409 24)0.0467 25)0.079 26)0.079 0
0.0395 0)0.037 1)0.0424 2)0.03 3)0.0211 4)0.0269 5)0.0304 6)0.0318 7)0.0393 8)0.066 9)0.0527 10)0.0335 11)0.0356 12)0.0592 13)0.0267 14)0.0219 15)0.0362 16)0.0366 17)0.0271 18)0.0362 19)0.0581 20)0.0409 21)0.0347 22)0.0385 23)0.0556 24)0.0409 25)0.0395 26)0.066 9
Глядя на эту таблицу можно определить смещения всех строк yi относительно первой строки (первое число в последней колонке - наибольшее значение Взаимного индекса совпадений, второе - относительное смещение, при котором оно произошло ). Действительно, между 'a' и 'w' 4 символов, между 'a' и 'e' - 22 символа и т.д. Количество возможных ключей сокращается до 26. Заметим, что мы считали Взаимный индекс совпадений лишь для строки y0 и нам повезло, что смещения определились однозначно. Если бы текст был намного короче , то смещения считаются не так однозначно. Поэтому для успешного взлома нужно, чтобы криптограмма была значительно длиннее , чем ключ.
(программы автора можно скачать здесь определить длину ключа определить смещения)

Взлом шифра простой замены.

  Шифр простой подстановки - один из самых древних. Он или его виды получили широкое распространение благодаря простоте шифрования и дешифрования. Первое пособие по криптоанализу – 14-томная энциклопедия Шехаба Калкашанди (1412). Он выпустил некоторые рекомендации по взлому простых подстановок на арабском языке ("самом красивом и широкораспространенном"). Во-первых, криптоаналитик должен изучить язык, на котором написана криптограмма. Это значит провести анализ частот встречаемости букв, а также двойных и тройных сочетаний. Если шифровальщик зашифровал и символ, разделяющий слова, то можно последовательно перебирать длинны первого слова криптограммы, пока "вы не почувствуете, что на что-то напали". Ясно, что в этом пособии содержится скорее алгоритм для человека, а не для компьютера. Но нужно иметь ввиду, что это первое пособие подобного рода. Эго можно попытаться формализовать следующим образом
Алгоритм 1:
  1. Подсчитать частоту встречаемости шифрообозначений, а так же их сочетаний – биграмм, триграмм ,…
  2. Выявление гласных и согласных (удвоение гласных – реже чем удвоение согласных, гласные расположены равномерно по тексту и чередуютс иногда через 2-3 знака,с ней чаще всего сочетается согласная)
  3. Выдвижение гипотез о значениях шифрообозначений , их проверка.Восстановление исходного текста.
Можно руководствоваться множеством правил и наблюдений , например: удвоение гласных происходит реже, чем удвоение согласных, если шифрообозначение равномерно раполагается по тексту, чередуется через 1,2,3 символа, сочетается со средними по частоте и редкими символами, то скорее всего это гласная, с гласными чаще всего сочетаются согласные... Но все эти правила довольно трудно внести в компьютер, к тому же для них почти всегда будут исключения, которые порушат всю логику. Необходим способ быстро проверять некоторый текст на читабельность и близость к возможному исходному тексту. Следующий алгоритм основан на сравнении матриц биграмм криптограммы и матрицы биграмм нормалного текста (Thomas Jakobsen. “A fast method of Cryptoanalysis of Substitutional Ciphers”).
Пусть Di,j - матрица биграмм для криптограммы (матрица NxN, где N - размер алфавита), Ei,j - матрица биграмм , составленная на основе частот биграмм для некоторого языка (например английского). Тогда функция будет показывать эффективность очередной выбранной подстановки алфавита. Чем меньше эта функция, тем вероятнее подстановка.
    0) a=b=1
    5a) A= sa ,B= sa+b , переставить символы A и B в k`.
    5b) a++
    5c) если a+b<=27 goto (7)
    5d) a=1 ,b++
    6e) если b==27 прерваться.
    8b) a=b=1
    Алгоритм 2:
  1. k = первоначальная перестановка алфавита, основанная на частоте символов.
  2. Получить матрицу Di ,j .
  3. v=f(t) для матрицы Di,j
  4. k=k`, D`=D
  5. Переставить два элемента из k`
  6. Переставить в матрице D` соответствующие строки и столбцы.
  7. v`=f(t) для матрицы D`i,j
  8. Если v`>=v то перейти на шаг 4
  9. v=v` , k=k`, D=D`, перейти на шаг 6
Эффективнее всего делать перевстановку не произвольным образом, а на основе частоты символов, переставляя последовательно сначала соседние символы, потом через один, через два,...
Заметим, что этот способ хорошо работает, если сообщение имеет довольно большую длину - около 1000 символов - и статистика символов в нем не нарушена. В противном случае он даст неправильный результат.

Чистые шифры

   T – чистый шифр , если для любых Ti и Tj, Tk(операции отображения с ключами i и j) имеется такое Ts, что TiTj-1Tk=Ts и все ключи равновероятны. В противном случае он является смешанным. В чистом шифре операции Ti Tj-1, образуют группу. Сообщения и криптограммы распадаются на определенные подмножества – остаточные классы. Любой выбор ключа в чистом шифре приводит к одинаковым трудностям при дешифровании, т.к. любой ключ приводит к формированию криптограмм из одного остаточного класса, что приводит к одним и тем же апостериорным вероятностям. На практике это дает нам большое преимущество - расшифровывая криптограмму мы рассматриваем только тот остаточный класс, в котором находится сообщение.
Примеры:

Метод характерных слов (G.Hart “To Decode short cryptograms”)

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

		sub compare {
			if (length($_[0]) !=length($_[1])){return 0;}
			 for ($i=1; $i<=length($_[0]); $i++){
				 for ($j=0;$j<$i; $j++){
				if ((substr($_[0],$i,1) eq substr($_[0],$j,1)) != (substr($_[1],$i,1) eq substr($_[1],$j,1))){
						return 0;
					}
				}
			}
			return 1;
		}
После выделения для каждого выбранного слова множества слов из того же остаточного класса строится дерево. Узлы – частичные расшифровки текста. Если есть путь от корня до листа, то мы нашли еще одну расшифровку криптограммы.
    Алгоритм 3:
  1. Распарсить текст на слова.
  2. Найти для каждого слова (из разных групп) множество возможных расшифровок. Убрать все слова, для которых не нашлось расшифровки.
  3. Упорядочить слова по одному из трех алгоритмов.
  4. Совершить обход дерева(в прямом порядке), частично заполняя алфавит и исключая коллизии (т.е если в частично заполненный алфавит попытаться подставить другую расшифровку буквы, нежели та , которая определена ранее, то для данного слова эта его расшифровка не подходит и нужно брать другое (другого потомка)).
Большое значение имеет выбор слов, для которых подбираются множества расшифровок:
  1. Слова с меньшим количеством расшифровок должны идти раньше. (тогда велика вероятность, что мы будем перебирать меньше, чем все дерево полностью, так как слова с большим количеством расшифровок возможно вообще не будут достигаться)
  2. Слова , в которых есть одинаковые буквы должны следовать раньше (тогда велика вероятность получить коллизию раньше и отсечь большую часть дерева )
  3. Более длинные слова должны идти раньше.( тогда мы заполним больше символов в алфавите и вероятность того, что вскоре мы получим коллизию больше)
Ссылка на мою программу(возможно пока не работает) Заметим, что данный алгоритм целиком зависит от размера словаря. В частности для английского языка он наиболее эффективен. Для русского языка наиболее полный составить словарь труднее из-за большого количества форм слов, а обход дерева всилу этого может занимать большое время.

Список литературы