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

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

«Ивановский государственный энергетический университет имени »

Кафедра программного обеспечения компьютерных систем

Основы криптографии

Методические указания к лабораторным работам № 1,2 по курсу «Методы и средства защиты информации»

Иваново 2004

 ИГНАТЬЕВ

ГУСЕВ

Цель настоящих методических указаний – помочь студентам выполнить лабораторные работы по курсу «Методы и средства защиты информации».

Методические указания предназначены для студентов IV курса направления «Информатика и вычислительная техника».

Методические указания утверждены цикловой методической комиссией факультета информатики и вычислительной техники

Рецензент

кафедра программного обеспечения компьютерных систем ГОУ ВПО «Ивановский государственный энергетический университет»

ОСНОВЫ КРИПТОГРАФИИ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНЫМ РАБОТАМ № 1,2 ПО КУРСУ «МЕТОДЫ И СРЕДСТВА ЗАЩИТЫ ИНФОРМАЦИИ»

Составитель

Редактор

Лицензия ИД № 000 от 4 июля 2001 г.

Подписано в печать 4.11.04. Формат 60х84 1/16.

Печать плоская. Усл. печ. л. 1,39.

Тираж 50. Заказ № .

ГОУ ВПО «Ивановский государственный энергетический университет»

4

Отпечатано в РИО ИГЭУ

Введение

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

В криптографической терминологии исходный текст именуют открытым текстом (plaintext или clear text). Чтобы скрыть смысл исходного текста применяются два типа преобразований: кодирование и шифрование.

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

Шифрование, или зашифрование (encryption), представляет собой процедуру преобразования открытого текста в зашифрованное сообщение, или шифротекст (cipher text). Процесс, при котором из шифротекста извлекается открытый текст, называют расшифрованием (decryption). Обычно в процессе шифрования и расшифрования используется некий ключ и алгоритм обеспечивает, что расшифрование можно сделать, лишь зная этот ключ.

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

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

Незашифрованное сообщение будем обозначать символом P (от слова plaintext). Зашифрованное сообщение будем обозначать символом С (от слова chiphertext).

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

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

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

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

Лабораторная работа №1. Шифрование простой подстановкой и перестановкой. Генераторы псевдослучайных чисел, гаммирование

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

Перестановки

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

К перестановочным шифрам принадлежат такие шифры, как «маршрутная транспозиция», «решетка Кардано» и т. п.

Замены

Шифрование методом замены (подстановки) основано на алгебраической операции, называемой подстановкой. Подстановкой называется взаимно однозначное отображение некоторого конечного множества М на себя.

В шифрах замены символ открытого текста заменяется одним или несколькими символами зашифрованного текста.

В криптографии рассматриваются четыре типа подстановки (замены): моноалфавитная, гомофоническая, полиалфавитная и полиграммная.

Моноалфавитная подстановка

Такие подстановки называются прямыми подстановками или простой замены.

При моноалфавитной замене каждой букве алфавита открытого текста ставится в соответствие одна буква шифротекста из этого же алфавита.

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

C = (aP + s) mod N ,

где P – код символа исходного текста;

C – код символа зашифрованного текста;

N – количество символов в алфавите;

a – десятичный коэффициент (a и N не должны иметь общих делителей);

s – коэффициент сдвига.

Пpимеp1.

Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ".

Подстановка задана таблицей:

Алфавит открытого текста: А Б В Г Д …

Алфавит шифротекста: _ Я Ю Э Ь …

Шифротекст: "ИШМРТЮ_УШЫАЩ_ФЫУТЧ".

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

Гомофоническая подстановка

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

Пример 2.

Открытый текст: "ЗАМЕНА".

Подстановка задана таблицей:

Алфавит открытого текста: А Б … Е Ж З... М Н...

17 23 ………

Алфавит шифротекста:………

48 63 …… 61 34…

Шифротекст: "76".

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

Полиалфавитная подстановка

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

Х=x1x2… xkxk+1… x2kx2k+1…

заменяется шифротекстом:

Y=f1(x1)f2(x2)… fk(xk)f1(xk+1)… fk(x2k)f1(x2k+1)…

где fi(xj) означает символ шифротекста i-го алфавита для символа открытого текста xj.

Пример 3.

Открытый текст: "ЗАМЕНА", k=3.

Подстановка задана таблицей из примера 2.

Шифротекст: "76".

К полиалфавитным подстановкам относится шифр Вижинера, в котором шифрование выполняется по формуле

Ci = (Pi + Kj) mod N ,

где Pi – код i-го символа открытого текста в алфавите

(0 >= Pi >= N-1, 0 >= i >= M-1);

M – число символов открытого текста;

Ci – код i-го символа зашифрованного текста в алфавите

(0 >= Ci >= N-1);

N – количество символов в алфавите;

Kj – код j-го символа ключа (j = i mod L; 0 >= j >= L-1);

L – длина ключа.

Таблица кодов символов алфавита:

_	А	Б	В	Г	Д	Е	Ж	З	И	Й
0	1	2	3	4	5	6	7	8	9	10

К	Л	М	Н	О	П	Р	С	Т	У	Ф
11	12	13	14	15	16	17	18	19	20	21

Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
22	23	24	25	26	27	28	29	30	31	32

Пример 4.

Открытый текст: "ЗАМЕНА".

Ключ: "КЛЮЧ".

L=4; M=6.

З	А	М	Е	Н	А
К	Л	Ю	Ч	К	Л

С0 = 8 + 11 (mod 33) = 19 → Т

С1 = 1 + 12 (mod 33) = 13 → М

С2 = 13+ 31 (mod ЗЗ) = 11 → К

С3 = 6 + 24 (mod 33) = 30 → Э

С4 = 14+11 (mod 33) = 25 → Ш

С5 = 1 +12 (mod 33) = 13 → М

Шифротекст: "ТМКЭШМ".

Шифры Бофора (также полиалфавитные) используют формулы:

уi = ki - xi (mod n) и yi = xi - ki (mod n).

Полиграммная подстановка

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

В этом шифре алфавит располагается в матрице. Открытый текст разбивается на пары символов XiXi+1. Каждая пара символов открытого текста заменяется на пару символов из матрицы следующим образом:

1) если символы находятся в одной строке, то каждый из символов пары заменяется на стоящий правее его (за последним символом в строке следует первый);

2) если символы находятся в одном столбце, то каждый символ пары заменяется на символ, расположенный ниже его в столбце (за последним нижним символом следует верхний);

3) если символы пары находятся в разных строках и столбцах, то они считаются противоположными углами прямоугольника. Символы заменяются на символы, находящиеся в тех же столбцах, но соответствующие другим углам прямоугольника;

4) если в открытом тексте встречаются два одинаковых символа подряд, то перед шифрованием между ними вставляется специальный символ (например, тире).

Пример 5.

Открытый текст: "ШИФР_ПЛЭЙФЕРА".

Матрица алфавита:

А	Х	Б	М	Ц	В
Ч	Г	Н	Ш	Д	О
Е	Щ	,	Х	У	П
.	З	Ъ	Р	И	Й
С	Ь	К	Э	Т	Л
Ю	Я	_	Ы	Ф	-

Шифротекст: "РДЫИ,-СТ-И.ХЧС"

Обратимые операции

При шифровании часто применяются обратимые (биективные) операции. Самая популярная – операция "Исключающего ИЛИ" – XOR:

a Å b = 1, если a ¹ b;

a Å b = 0, если a = b.

Например:

10 xor 250 = 240; 240 xor 250 = 10 .

Обратимой операцией является также операция сложения по модулю 2n, где n – число разрядов у операндов, участвующих в сложении.

Например:

(10 + 250) mod 256 = 4; (4 – 250) mod 256 = 10 .

Если мы имеем дело с байтовыми переменными, то будут справедливы следующие операторы: c := a + b; a:= c – b.

Гаммирование

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

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

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

Задания

1.  Напишите программу генерации шифра для заданных a и s по формуле:

Ci = (a Pi + s) mod N ,

где Pi – код i-го символа открытого текста (0 ≤ Pi ≤ N-1);

Ci – код i-го символа зашифрованного текста (0 ≤ Ci ≤ N-1);

N – количество символов алфавита;

a – десятичный коэффициент;

s – коэффициент сдвига.

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

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

Шифрование выполняется по формуле

Ci = (Pi + Kj) mod N ,

где Pi – код i-го символа открытого текста (0 ≤ Pi ≤ N-1);

Ci – код i-го символа зашифрованного текста (0≤Ci≤ N-1);

N – количество символов алфавита;

Kj – код j-го символа ключа (j = i mod L; 0 ≤ j ≤ L-1);

L – длина ключа.

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

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

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

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

4.  Напишите программу перекодировки символов из одной кодировки в другую для кодировок ASCII, КОИ-8, Windows и т. п. Используя эту программу, напишите программы шифрования и расшифрования для русского текста путем перекодирования. Последовательность перекодировок должна задаваться целым числом, каждая цифра которого обозначает ту или иную кодировку.

5.  В России в XIII в. для тайнописи применяли «тарабарскую грамоту». В этой системе согласные буквы заменяются по схеме

	Б	В	Г	Д	Ж	З	К	Л	М	Н
Щ	Ш	Ч	Ц	Х	Ф	Т	С	Р	П

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

Напишите программы шифрования, расшифрования и дешифрования для текстовых файлов.

6.  Напишите программы шифрования и расшифрования с использованием "цифирной азбуки". В госархиве сохранились письма Петра I, в которых он передавал цифири различным деятелям для корреспонденции (П. А. Толстому, и др.). Цифирь – это шифр простой замены, в котором буквам сообщения соответствовали шифрообозначения, представляющие собой буквы, слоги, слова или другие какие-нибудь знаки. При этом использовались и "пустышки" – шифрообозначения, которым не соответствовали никакие знаки открытого текста.

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

А-ме	Б-ли	В-ко	Г-ин	Д-зе	Е-жу	Ж-ню	З-ою	И-пы	К-ра
Л-су	М-ти	Н-у	О-хи	П-от	Р-ца	С-чу	Т-ше	У-ам	Ф-ик
Х-ъ	Ц-то	Ч-ь	Ш-ю	Щ-я	Ъ-ф	Ы-ас	Ь-бе	Э-за	Ю-гу
Я-ди	« »-е

7.  Напишите программу, обеспечивающую генерацию случайным или псевдослучайным образом моноалфавитной подстановки для алфавита из n символов. Сформируйте массив [0..255], содержащий коды подстановки символов. Для остальных (255-n) символов, не вошедших в алфавит, в ячейки массива запишите код 0. Напишите программы шифрования и расшифрования, использующие полученный массив. Подстановочная таблица, открытый текст и зашифрованный текст должны находиться в текстовых файлах.