Основы криптографии (стр. 3 )

Имена текстовых файлов с исходным и зашифрованным сообщением, константы m и n должны задаваться в качестве параметров.

13.  Напишите программы шифрования и расшифрования методом перестановки символов открытого текста, нанесенных на грани "кубика Рубика". Последовательность поворотов одна и та же для всех групп символов.

14.  Напишите программу генерации псевдослучайных чисел (ПСЧ), применяя линейный конгруэнтный генератор ПСЧ, вырабатывающий последовательность T1, T2, …, Tm, …, используя соотношение

Ti+1 = (a Ti + c) mod m ,

где a и c – константы (с – нечетное, а mod 4 = 1);

T0 – исходная величина, выбранная в качестве порождающего числа;

m – константа; обычно устанавливается равной 2b или 2b-1;

b – длина слова ЭВМ в битах (взять b=8).

Сгенерируйте m чисел. Определите числа от 0 до m-1, которые ни разу не были сгенерированы. Определите числа, сгенерированные более одного раза.

Постройте график частоты попадания сгенерированных чисел в интервалы по 1000 чисел. Такой же график постройте для функции Random() языка Pascal. Исследуйте, как влияют на характер распределения генерируемой последовательности чисел константы a и c. Определите период повторяемости генерируемых чисел.

15.  Напишите программы шифрования и расшифрования, использующие генератор ПСЧ (см. задание №14). Программы должны применять операцию "исключающее ИЛИ" для объединения очередного сгенерированного числа и символа из текста. Открытый и зашифрованный тексты должны находиться в текстовых файлах.

16.  Напишите программы шифрования и расшифрования методом многоалфавитной подстановки (см. задание №2). Kj получайте с помощью генератора ПСЧ. Начальное (инициализационное) число псевдослучайной последовательности чисел будет являться ключом шифра.

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

18.  Были перехвачены два зашифрованных сообщения:

05262C5269143F314C2A69651A264B5E7EE9

B63072CB425E7DA745

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

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

Лабораторная работа №2. Дешифрование, частотный анализ. Маскировка длины символа

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

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

Клод Шеннон ввел понятия диффузии и конфузии для описания стойкости алгоритма шифрования.

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

Конфузия – это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом.

Если Х – это исходное сообщение и K – криптографический ключ, то зашифрованный передаваемый текст можно записать в виде

Y = EK [X].

Получатель, используя тот же ключ, расшифровывает сообщение

X = DK [Y].

Противник, не имея доступа к K и Х, должен попытаться узнать Х, K или и то, и другое.

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

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

Все естественные языки и большинство искусственных имеют характерное частотное распределение букв и других знаков. Например, в английском языке буква E встречается наиболее часто, а буква Z – наиболее редкая (рис. 2).

Рис. 2. Частотность букв английского алфавита

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

Чем больше длина шифротекста, тем легче его дешифровать.

Криптоаналитики часто используют индекс соответствия текстов, вычисляемый по формуле

где fi – общее число встречаемости буквы i в тексте;

N – общее число букв в тексте;

A – первая буква в алфавите;

z – последняя буква в алфавите.

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

m:

ИС: 0,066 0,052 0,047 0,045 0,044 0,041

При гаммировании криптостойкость определяется размером ключа. Покажем это на примере:

C1 = P1 Å K

С2 = P2 Å K

C1 Å С2 = P1 Å P2 ,

где K – символ гаммы;

P1 и P2 – символы разных открытых текстов, зашифрованных на одной гамме;

C1 и С2 – зашифрованные символы, соответствующие P1 и P2.

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

Маскировка длины символа

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

Выполнение битовых операций

Для выполнения заданий по данной лабораторной работе могут потребоваться операции с битами. Ниже приводятся некоторые простейшие манипуляции с битами на языке Pascal.

Младший (самый правый) разряд считается нулевым.

1. Выделить i-й бит из переменной A:

(A shr i) AND $01.

Распечатать содержимое переменной A как последовательность битов:

for i:=7 downto 0 do

write ((A ShR i) AND $01).

2. Установить i-й бит

а) в 1: A OR ($01 ShL i);

б) в 0: A AND NOT ($01 ShL i).

3. Обнулить A:

A XOR A.

4. Поменять местами i-й и j-й биты целого числа:

type bitik = 0..14;

bin = 0..1;

var i, J : bitik;

bi, bj : bin;

X, a,ap: Integer;

…

bi:=(a ShR i) AND $01; bj:=(a ShR J) AND $01;

if bi<>bj then

if bi=1

then begin ap:=a-(1 ShL i); ap:=ap+(1 ShL j) end

else begin ap:=a-(1 ShL j); ap:=ap+(1 ShL i) end;

5. Циклический сдвиг содержимого n-разрядной переменной A на i битов

а) влево: ROL (A, i) или (A shl i) OR (A shr (n-i));

б) вправо: ROR (A, i) или (A shr i) OR (A shl (n-i)).

Сжатие методом Хаффмана

При сжатии этим методом 8-битовый код каждого символа заменяется на код, у которого разрядность зависит от частоты встречаемости данного символа.

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

R N O A T E

Возьмем два символа с наименьшей частотой: R (5) и N (6). Сформируем из узлов R и N новый узел, частота вхождения для которого будет равна сумме частот R и N (11). После этого снова ищем два узла с самыми низкими частотами вхождения, исключая из просмотра R и N и рассматривая вместо них новый узел с суммарной частотой вхождения. И так продолжаем до тех пор, пока не получим вершину дерева с общим количеством символов. В результате получится дерево для генерации кодов (рис. 3).

 

Рис. 3. Дерево кодов для сжатия по методу Хаффмана

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

E – 11	А – 101	N – 001
Т – 01	O – 100	R – 000

Для наиболее часто встречающихся символов мы получили более короткие коды. Сжатый файл вместо 48 байт будет занимать 16 байт [(5×3+6×3+7×3+8×3+9×2+13×2) / 8].

Задания

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

2.  Напишите программу частотного анализа встречаемости символов и пар символов.

Проведите частотный анализ для алфавитов английского языка:

·  "_", "A", …, "Z"

·  "_", "A", …, "Z", "a", ..., "z", "0", …, "9", "(", ")", "[", "]", "{", "}", ".", ",", ":", ";", "?", "!", "-", """, "+", "=", "№", "%", "*", "/"

·  все символы с кодами от 0 до 255.

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

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

3.  Проведите частотный анализ встречаемости символов и пар символов (условия см. задание №2) для алфавитов русского языка:

·  "_", "А", …, "Я"

·  "_", "А", …, "Я", "а", ..., "я", "0", …, "9", "(", ")", "[", "]", "{", "}", ".", ",", ":", ";", "?", "!", "-", """, "+", "=", "№", "%", "*", "/"

·  все символы с кодами от 0 до 255.

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

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

Проведите частотный анализ встречаемости символов для алфавитов:

·  "_", "А", …, "Я"

·  "_", "A", …, "Z",

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

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

Используя программы шифрования и расшифрования методом многоалфавитной подстановки (см. задание №3), вычислите ИС для зашифрованных текстов при длине ключа от 1 до 15 знаков.

6.  Напишите программы шифрования и расшифрования с использованием тюремной азбуки. Азбука устроена следующим образом: в прямоугольную матрицу 6 х 5 вписываются по строкам буквы русского алфавита в обычном порядке следования, кроме букв ё, й, ъ. Код каждой буквы теперь можно определить парой чисел – номером строки и столбца. Для каждого числа используйте по три бита. Для обозначения пробела – 000. Оставшиеся в конце закодированного сообщения биты заполните нулями.

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

Для английского алфавита коды Хаффмана могут быть следующие:

A	1111	G	00001	M	00011	S	0110	Y	00000
B	011100	H	0101	N	1100	T	001	Z
C	01000	I	1010	O	1110	U	00010
D	11011	J		P	110101	V	1101001
E	100	K		Q		W	011101
F	01001	L	01111	R	1011	X

8.  Напишите программы шифрования и расшифрования с использованием азбуки Морзе (русского варианта), в которой точки заменены битом 1, а тире – 0.

А-10	Б–0111	В–100	Г–001	Д–011	Е–1	Ж–1110	З–0011
И–11	Й-1000	К–010	Л–1011	М–00	Н–01	О-000	П-1001
Р-101	С-111	Т-0	У-110	Ф-1101	Х-1111	Ц-0101	Ч-0001
Ш-0000	Щ-0010	Ы-0100	ЪЬ-0110	Э-11011	Ю-1100	Я-1010

1-10000	2-11000	3-11100	4-11110	5-1111
6-01111	7-00111	8-00011	9-00001	0-00000
[.]-111111	[,]-101010	[:]-000111	[;]-01010	[!]-001100
["]-101101	[()]-010010	[-]-011110	[/]-01101

Начало-011001

Конец-10101

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

9.  Напишите программы шифрования и расшифрования методом перестановки битов в группе из 4 битов открытого (зашифрованного) текста. Все возможные перестановки битов хранятся в массиве. Например: 0-1234, 1-2134, 2-3214, 3-4231, 4-1324, 5-1432, 6-1243 и т. д. Индекс используемой последовательности битов задается числом, которое выдается генератором ПСЧ. Открытый текст и зашифрованный текст должны находиться в текстовых файлах.

10.  Напишите программы шифрования и расшифрования методом циклического сдвига. Каждая порция открытого текста состоит из m блоков. Каждый блок, состоящий из n байт, сдвигается влево (при расшифровании вправо) на k0, k1, …, km-1 битов соответственно. Проверьте работу программ при m=3, n=4 и K=11,5,9.

11.  Напишите программы шифрования и расшифрования методом подстановки, используя квадрат Полибия [8x8] для русского алфавита ("_", "А", … , "Я", "0", …, "9", "(", ")", "[", "]", "{", "}", ".", ",", ":", ";", "?", "!", "-", """, "+", "=", "№", "%", "*", "/"). В квадрат по строкам последовательно вписываются все символы алфавита. Каждый символ открытого текста кодируется парой чисел – номером строки и номером столбца. Для кодирования номера строки и номера столбца используются по 3 бита. Открытый текст храните в текстовом файле. Строчные буквы русского алфавита заменяйте на прописные.

12. 
Реализуйте программно генератор последовательности битов (регистр сдвига), изображенный на рис. 4.

Рис. 4. Генератор битовой последовательности

Генерация кодирующей последовательности битов производится циклически из небольшого начального объема информации – ключа (10000) по следующему алгоритму. Из текущего набора битов выбираются значения определенных разрядов (0-го и 3-го) и складываются по XOR между собой. Все разряды сдвигаются на 1 бит, а только что полученное значение (0 или 1) помещается в освободившийся самый младший разряд. Значение, находившееся в самом старшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом. Очередной бит кодирующей последовательности складывается по XOR с очередным битом исходного потока. В результате получается очередной бит зашифрованной информации.

Определите, на каком шаге генерируемая последовательность начнет повторяться?

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

13.  Напишите программу дешифрования текста, зашифрованного методом перестановки битов в каждом байте, если известно, что открытый текст должен начинаться с известной подстроки, например: "Совершенно секретно".

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

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

15.  Напишите программы шифрования и расшифрования с использованием метода Дика Френдберга, выпускника университета Беркли. Этот метод комбинирует многоалфавитную подстановку с генератором псевдослучайных чисел для получения шифра подстановки с характеристиками “бесконечного ключа”.

Алгоритм метода:

1). Установить генератор псевдослучайных чисел с заданным порождающим числом R0. Установить список подстановки из n знаков.

2). Определить, есть ли еще какие-либо символы открытого (зашифрованного) текста, которые необходимо зашифровать (расшифровать)? Если нет, то ОСТАНОВ.

3). Определить место (a) следующего символа открытого (зашифрованного текста) в исходном алфавите (списке подстановки). Подставить вместо него соответствующий знак из списка подстановки (первоначального исходного алфавита).

4). Сгенерировать псевдослучайное число R в интервале от 1 до n.

5). Переставить R-й и a-й знаки в исходном алфавите.

6). Перейти к пункту 2.

Постройте диаграммы частотного распределения зашифрованного текста для сообщения, состоящего из 100, 1000 и 10000 пробелов.

16.  Напишите программы шифрования и расшифрования методом двойного ключа, где два периодических ключа длиной в 125 и 123 слова добавляются по модулю 2 к исходному тексту. С каждым i‑м словом открытого текста (из первых 123 слов) складываются первое слово первого ключа и i-ое слово второго ключа, то есть получается что-то вроде шифрования с одним ключом длиной, равной произведению длин двух ключей (в нашем случае 125 х 123 = 15375 слов). Открытый текст, каждый из ключей и зашифрованный текст должны находиться в текстовых файлах.

17.  Напишите программы шифрования и расшифрования методом «Сигнатура». Алгоритм зашифрования заключается в преобразовании (с помощью байтов ключа) битов входной последовательности в выходную последовательность битов:

0).  В текущий байт B помещается синхропосылка S, а в текущий байт ключа K помещается первый байт из файла содержащего ключевую информацию.

1).  Текущий байт B складывается с текущим байтом ключа K с помощью операции XOR (рис. 5).

2).  Подсчитывается сумма битов (по модулю 2) полученного байта, т. е. все биты байта складываются по правилу 1+1=0, 1+0=1, 0+1=1, 0+0=0 так, чтобы в результате получился один бит.

3).  Полученный бит складывается со следующим битом файла открытого текста (входного потока).

4).  Левый бит текущего байта B записывается в выходной поток, и весь текущий байт сдвигается влево на один бит. Вместе с ним сдвигается и текущий байт ключа K.

5).  На освободившийся правый бит в текущем байте B записывается бит, полученный в пункте 3, а на освободившийся правый бит в текущем байте ключа K записывается очередной бит из файла ключевой информации.

И так продолжается до тех пор, пока не закончится входная последовательность.

Открытый текст, ключ и зашифрованный текст должны находиться в текстовых файлах.

Рис. 5. Генератор битовой последовательности

18.  Напишите программу помещения (извлечения) содержимого текстового файла в тело (из тела) графического файла. Для этого можно использовать метод последнего значащего бита (Lasst Significant Bit, LSB). Например, полноцветные файлы в формате RGB кодируют каждый пиксел тремя байтами для представления соответственно красной, зеленой и синей составляющих. Изменение каждого из трех младших битов (для записи битов скрываемого сообщения) приведет к изменению цвета данной точки менее чем на 1%, что абсолютно незаметно. Таким образом в файле размером 800 килобайт можно скрыть сообщение размером до 100 килобайт. Методы направленные на скрытие самого присутствия конфиденциальной информации называются стеганографией.

19.  Напишите программы перевода произвольного файла в формат Base64 и обратно. Эта система широко используется в электронной почте для представления бинарных файлов в тексте письма (транспортное кодирование). Для того, чтобы преобразовать данные в base64, первый байт помещается в самые старшие восемь бит 24-битного буфера, следующие в средние восемь и третий в младшие значащие восемь бит. Если кодируется менее чем три байта, то соответствующие биты буфера устанавливаются в ноль. Далее каждые шесть бит буфера, начиная с самых старших, используются как индексы строки «ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/» и её символы, на которые указывают индексы, помещаются в выходную строку. Если кодируются только один или два байта, используются только первые два или три символа строки и выходная строка дополняется двумя или одним символами «=». Это предотвращает добавление дополнительных битов к восстановленным данным. Процесс повторяется над оставшимися входными данными.