Пособие «Защита информации» (МФТИ)

Министерство Образования Российской Федерации

Московский ФизикоТехнический Институт (Государственный Университет)

Учебный материал

По курсу лекций:

«Защита Информации»

Москва, 2004

Моноалфавитные шифры и их криптоанализ.

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

Шифр Цезаря.

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

Открытый текст: a,b,c,d,e,f,g,h,I,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z.

Шифрованный текст: D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A,B,C

В шифре Цезаря каждая буква замещается на букву, находящуюся k символами правее. Ck(j)=(j+k)(mod n), n - количество букв в алфавите, j – текущая буква.

Очевидно, что обратной подстановкой является

Ck-1(j)=Сn-k=(j+n-k)(mod n)

Аффинная криптосистема.

Обобщением системы Цезаря является аффинная криптосистема. Она определяется двум числами a и b, где 0<=a,b<=n-1. n - как и раньше, является мощностью алфавита. Числа a

и n должны быть взаимно просты.

Соответствующими заменами являются: Aa,b(j)=(a*j+b)(mod n)

A-1a,b(j)=(j-b)*a-1(mod n)

Обратную замену также можно получить, просто поменяв местами строки в таблице замен.

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

Шифр Цезаря с ключевым словом

В данной разновидности шифра Цезаря ключ задается числом k (0<=k<=n-1) и коротким ключевым словом или предложением. Выписывается алфавит, а под ним, начиная с k-й позиции, ключевое слово. Оставшиеся буквы записываются в алфавитном порядке после ключевого слова. В итоге мы получаем подстановку для каждой буквы. Требование, чтобы все буквы ключевого слова были различными не обязательно - можно записывать ключевое слово без повторения одинаковых букв. Количество ключей в системе Цезаря с ключевым словом равно n!.

Криптоанализ.

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

1

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

U Z Q S O V U O H X M O P V G P O Z P E V S G Z W S Z O P F P E S X U D B M E T S X A I Z

V U E P H Z H M D Z S H Z O W S F P A P P D T S V P Q U Z W Y M X Z U H S X

E P Y E P O P D Z S Z U F P O M B Z W P F U P Z H M D J U D T M O H M Q

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

В английском языке БукваЧастотаБукваЧастотаБукваЧастота

a	0.0804	b	0.0154	c	0.0306
d	0.0399	e	0.1251	f	0.0230
g	0.0196	h	0.0549	i	0.0726
j	0.0016	k	0.0067	l	0.0414
m	0.0253	n	0.0709	o	0.0760
p	0.0200	q	0.0011	r	0.0612
s	0.0654	t	0.0925	u	0.0271
v	0.0099	w	0.0192	x	0.0019
y	0.0173	z	0.0009

Сравнивая эти результаты с данными, показанными в таблице, можно заключить , что, скорее всего, буквы Р и Z шифрованного текста являются эквивалентами букв e и t открытого текста, хотя трудно сказать, какой именно букве –Р или Z- соответствует е, а како –t. Буквы S,U,O,M,H, обладающие относительно высокой частотой появления в тексте, скорее всего, соответствует буквам из множества {r,n,i,o,a,s}. Буквы с низкой частотой появления (а именно A,S,G,Y,I,J), по –видимому, соответствуют буквам множества {w,v,b,k,x,q,j,z}.

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

Один из очень эффективных методов заключается в подсчете частоты использования комбинаций, состоящих из двух букв (биграмм). Для значений относительной частоты появления в тексте биграмм тоже можно построить гистограмму, подобную показанной на рис . Известно, что в английском языке самой распространенной является биграмма th. В нашем шифрованном тексте чаще всего ( три раза) встречается комбинация ZW. Поэтому можно предположить, что Z соответствует t, а W-h. Тогда из ранее сформулированной

2

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

Теперь рассмотрим комбинацию ZWSW в первой строке. Конечно, пока нет уверенности, что эти буквы принадлежат одному и тому же слову, но, если предположить, что это так, они соответствуют слову th?t. Отсюда заключаем, что букве S соответствует а.

Теперь имеем следующий результат:

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

t a	e	e t e	a t a t e e a		a t
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
e t	t a t	h a e e e	a e t h	t	a
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
e e e t a t e		t h e	t

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

it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in Moscow.

Моноалфавитные шифры легко раскрываются, так как они наследуют частотность употребления букв оригинального алфавита. Контрмерой в данном случае является применение для одной буквы не одного, а нескольких заменителей ( называемых омофонами). Например, букве е исходного текста может соответствовать несколько разных символов шифра, ( скажем, 16,74,35 и 21), причем каждый такой символ может использоваться либо поочередно, либо по случайному закону. Если число символовзаменителей, назначенных букве, выбрать пропорциональным частоте появления этой буквы, то подсчет частотности употребления букв в г=шифрованном тексте становится бессмысленным. Однако при употреблении омофонов ( их предложил Карл Фридрих Гаусс) каждому элементу открытого текста соответствует только один элемент шифрованного текста, поэтому в последнем попрежнему должны наблюдаться характерные показатели частоты повторения комбинаций нескольких букв ( например, биграмм) , и в результате задача криптоанализа попрежнему остаться достаточно элементарной.

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

3

Полиалфавитные шифры и их криптоанализ

Шифрование. Исходный открытый текст разбивается на последовательные группы длины m , где m -- период, выбираемый криптографом и держащийся в секрете. Для удобства объяснений сообщение переписывается в виде матрицы, строками которой являются последовательные группы. Например, пусть открытый текст будет "Игры различаются по содержанию характерным особенностям а также по тому какое место они занимают в жизни детей их воспитании и обучении" и пусть период будет равен 4. Представим открытый текст как матрицу размера 17х4:

и	г	р	ы
р	а	з	л

Далее криптограф выбирает 4 различных моноалфавитных шифра. Первый столбец (буквы и р и т о ....е) шифруются первым шифром; второй столбец (буквы г а ч с м ...н) -- вторым шифром, и т.д.

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

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

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

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

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

В рассматриваемом примере:

Группа СЪС встречается в позициях 1, 373, 417, 196. Соответствующие расстояния равны

372=(4)(3)(31), 44 = (4)(11) и 196 = (4)(49). Наибольший общий делитель равен 4. Делаем вывод, что период кратен 4.

Группа ЩГЖ встречается в позициях 5, 781, 941. Соответствующие расстояния равны 776=(8)(97) и 160 = (32)(5). Делаем вывод, что период кратен 8, что не противоречит выводу для предыдущей группы (кратен 4).

Группа ЫРО встречается в позициях 13, 349, 557. Соответствующие расстояния равны 336=(16)(3)(7) и (4)(53). Делаем вывод, что период кратен 4.

Правдоподобным является предположение, что период равен 4.

Автокорреляционный метод состоит в том, что исходный шифртекст (C1,C2 ,K ,CL ) выписывается в строку, а под ней выписываются строки, полученные сдвигом вправо на t =1,

t	i	[		]	таких,	что
2, 3, ... позиций. Для каждого t подсчитывается число n индексов		1, L −t
Ci = Ci+t . Вычисляются автокорреляционные коэффициенты γt = nt		/(L −t) .	Для чисел t,
кратных периоду, коэффициенты γt должны быть заметно больше,		чем для сдвигов,				не
кратных периоду.

Пример. Для рассматриваемой криптограммы выделим те значения t, для которых γt > 0,5 .

Получим ряд чисел

[ 4 12 16 24 28 32 36 40 44 48 52 56 64 68 72 76 80 84 88 92 96 100 итд

Все эти числа делятся на 4.

4

Правдоподобно, что период равен 4.

Метод индекса совпадений. Для последовательности x = (x1, x2 ,K , xL ) из букв алфавита из

A букв индексом совпадения Ic (x) называется вероятность того, что два случайных элемента этой последовательности совпадают. Экспериментально индекс совпадений приближенной равен

A

∑ fi ( fi −1)

	Ic (x) =	i=1	,
		L(L −1)

где fi число появлений буквы i в последовательности x.

Период можно определить по формуле

m ≈	kp −kr						,
	Ic (x) −kr +	k	p	−I	c	(x)
				L

A

где kr =1/ A, kp = ∑pi2 , pi -- частота появления буквы I в естественном языке.

i=1

Пример. В рассматриваемой криптограмме для облегчения приведены числа fi . Для русского языка A=32, kp = 0.0529. Проведя вычисления, получаем

m ≈ 3.376.

Правдоподобно, что период равен 4.

Далее проводим 4 раза анализ моноалфавитных шифров (здесь этот этап опускается). В Примере на этом все заканчивается. В других случаях может быть, что период все же определен неверно. Тогда следует испытать значения периода на 1 меньше или на 1 больше.

5

Блоковые и поточные шифры и тд

Существует два основных типа симметричных алгоритмов: блочные и потоковые шифры. Блочные шифры работают с блоками открытого текста и шифротекста – обычно длиной 64 бита, но иногда длиннее. Потоковые шифры работают с битовыми или байтовыми потоками открытого текста и шифротекста (иногда даже с потоками 32-битных слов). Блочный шифр ,использующий один и тот же ключ, при шифровании всегда превращает один и тот же блок открытого текста в один и тот же блок шифротекста. Потоковый шифр при каждом шифровании превращает один и тот же бит открытого текста в различные биты или байты шифротекста.

Замена алфавита.

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

Полиалфавитные шифры.Исходный открытый текст разбивается на последовательные группы длины

m , где m -- период, выбираемый криптографом и держащийся в секрете. Для удобства объяснений сообщение переписывается в виде матрицы, строками которой являются последовательные группы. Например, пусть открытый текст будет "Игры различаются по содержанию характерным особенностям а также по тому какое место они занимают в жизни детей их воспитании и обучении" и пусть период будет равен 4. Представим открытый текст как матрицу размера 17х4. Далее криптограф выбирает 4 различных моноалфавитных шифра. Первый столбец шифруются первым шифром; второй столбец – вторым шифром, и т.д.

Омофоны.

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

Шифруя букву исходного сообщения, выбирают случайным образом одну из ее замен. Замены (часто называемые омофонами) могут быть представлены трехразрядными числами от 000 до 999. Например, в английском алфавите букве Е присваиваются 123 случайных номера, буквам В и G - по 16 номеров, а буквам J и Z - по 1 номеру. Если омофоны (замены) присваиваются случайным образом различным появлениям одной и той же буквы, тогда каждый омофон появляется в шифртексте равновероятно.

Преобразования блоков.

Перестановки , подстановки в блоки (например, S-блоки DES’a) с расширением или со сжатием.

6

Симметричные алгоритмы шифрования DES,

ГОСТ, Rijndael.

1.Блочный шифр – определение – прямое и обратное преобразование выполняются над блоками фиксированной длины. 2 в степени n длина блока, часто 64, 256 и т.д.

2.Принцип итерирования – основа при разработке шифров. Многократная из нескольких циклов обработки открытого текста.

3.Схема Файстеля.

Li

Ri

Ki

F

Li+1		Ri+1

При шифровании блок данных разбивается на две равные части – правую и левую.

Далее: (Li , Ri ) = (Ri−1 , Li−1 f (Ri−1 , Ki ))

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

Также f(f(x))=x. Это свойство позволяет использовать для дешифрования ту же структуру алгоритма. DES и ГОСТ построены на основе данной схемы.

I.Стандарт DES (Data Encryption Standart)

•Длина блока – 64 бит.

•Длина ключа 56 бит.

•Для шифрования и дешифрования используются одинаковые алгоритм и ключ.

•Состоит из 16 циклов.

Схема работы: Открытый текст ->Начальная перестановка ->16 циклов -> Обращение начальной перестановки->Шифртекст.

Использует стандартную арифметику 64 битных чисел, легко реализуется. Начальная и конечная перестановки не влияют на криптостойкость алгоритма. Генерация ключа: для каждого из 16 циклов из 56 битного ключа генерируется 48 битный подключ. Для этого сначала 56 битный подключ делится на 2 28битных половины. Затем половины циклически сдвигаются на 1 или 2 бита в зависимости от номера блока. После этого происходит перестановка со сжатием, из 56-48 бит (не зависит от номера цикла).

На каждом цикле 32 битный блок преобразуется в 48 битный (перестановка с расширением)

7

Смысл операции: из-за влияния одного бита на 2 подстановки быстрее возрастает зависимость битов результата от битов исходных данных. Называется также E блок (expansion).

После этого выполняется операция XOR с расширенным ключом . Затем выполняется операция подстановки (Применение S box). Используется всего 8 S box с 6 битовыми входами, каждая из них дает на выходе 4 бита. Подстановка является ключевым этапом DES, обеспечивая нелинейность алгоритма. Затем происходит перестановка с помощью P блоков.

Нестоек к линейному и дифференциальному криптоанализу. Силовая атака – не более 40 дней стойкости.

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

Тройной Des – тройное DES шифрование.

II. Гост – разработан в Советском Союзе (государственный стандарт)

•64 битный алгоритм

•длина ключа 256 бит

•количество блоков 32

Для Госта (Li , Ri ) = (Ri−1 , Li−1 f (Ri−1 , Ki ))

8

Использует 8 различных S блоков; (включенных параллельно) Ключ складывается с правой частью по модулю 2^32. S box – перестановка от 0 до 15. Генерация подключей: 256 битный ключ разбивается на 8 подключей по 32 бит. Далее они используются в определенном порядке.

S блоки не определяются в стандарте.

Общая длина ключа при неизвестных S box велика; более стоек, чем DES к линейному и дифференциальному криптоанализу.

II.Rijndael (AES, Advanced Encryption Standart).

Поиски AES (Advanced Encryption Standart) начались три года назад. В конце сентября NIST (национальный институт стандартов и технологий) объявил имя победителя. Из пяти алгоритмов был выбран алгоритм под названием Рэйндол (Rijnael). Это название состоит из имен двух бельгийских ученых, создателей шифра : Vincent Rijmen и Joan Daemen.

При разработке Rijnael во внимание принималось три критерия:

1)Устойчивость по отношению ко всем известным атакам

2)Быстрота исполнения и компактность кода на разных платформах

3)Простота алгоритма

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

Rijnael это блочный шифр с различной длиной блока шифрования и длиной ключа. Длины блока и ключа шифрования могут быть 128, 192 и 256 бит. Шифрование блока осуществляется за несколько раундов, так, например, при длине блока 128 бит и длине ключа 128 бит алгоритм включает 10 раундов.

Первому раунду предшествует операция добавления кругового ключа

(смотреть пункт 4).

В отличие от DES, раунды Rijnael не обладают фейстелевской структурой. Вместо этого каждый раунд включает различные обратимые преобразования под названием слои. Схематически каждый раунд, кроме последнего, можно представить в виде 4 операций. Далее мы будем рассматривать вариант шифрования 128 битного блока при длине ключа 128 бит. При других длинах блока шифрования и длины ключа схема алгоритма не меняется, изменяются лишь некоторые константы реализации алгоритма (число раундов и прочее).

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

данных следующим образом: a0,0 , a1,0 , a2,0 , a3,0 , a4,0 , a0,1 , a0,2 , a0,3 …………….

a0,0	a0,1	a0,2	a0,3
a1,0	a1,1	a1,2	a1,3
a2,0	a2,1	a2,2	a2,3
a3,0	a3,1	a3,2	a3,3

k0,0	k0,1	k0,2	k0,3
k1,0	k1,1	k1,2	k1,3
k2,0	k2,1	k2,2	k2,3
k3,0	k3,1	k3,2	k3,3

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

9