Шифрование данных методами подстановки, перестановки и полиалфавитными шифрами

ЗАДАНИЕ № 1.

ШИФРОВАНИЕ ДАННЫХ МЕТОДАМИ ПОДСТАНОВКИ, ПЕРЕСТАНОВКИ И ПОЛИАЛФАВИТНЫМИ ШИФРАМИ

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

 

Теоретические основы криптографии

Проблемой защиты информации путем ее преобразования занимается криптология (kryptos - тайный, logos - наука). Криптология разделяется на два направления - криптографию и криптоанализ.

 Цели этих направлений прямо противоположны:

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

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

 

1.1.1. Терминология

 

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

Алфавит - конечное множество используемых для кодирования информации знаков.

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

- алфавит Z₃₃ - 32 буквы русского алфавита и пробел;

- алфавит Z₂₅₆ - символы, входящие в стандартные коды ASCII и КОИ-8;

- бинарный алфавит - Z₂ = {0,1};

- восьмеричный алфавит или шестнадцатеричный алфавит;

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

Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.

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

 

Классификация криптографических методов

 

По характеру используемого ключа криптографические методы делятся на:

- симметричные: для шифрования и дешифрования используется один и тот же секретный ключ;

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

К симметричным криптографическим алгоритмам относят простейшие методы шифрования (подстановки, перестановки), потоковые и блочные шифры.

 

Обзор используемых методов

Метод подстановки

 

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

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

,                                                                       (1.1)                                     

где А – символ открытого текста,

В – заменяющий символ,

i – номер буквы в алфавите,

   n –количество букв в алфавите.

Обратная подстановка осуществляется по правилу

                                                                   (1.2)

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

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

Пусть подстановочный алфавит составлен по следующему правилу:

А (2 k -1)= В (2 k); А (2 k)= В (33-2 k),                                                            (1.4)

где А - исходный перестановочный алфавит;

В - подстановочный  алфавит;       1£ k £ 16.

Формула 1.3 используется для замены букв с нечетными номерами в алфавите, формула 1.4 - для замены букв с четными номерами.

Воспользуемся новым алфавитом для шифрования фразы:

ОСНОВЫ ЗАЩИТЫ ИНФОРМАЦИИ

Каждая буква в этой фразе имеет порядковый номер в исходном алфавите. При шифровании методом подстановки необходимо заменить буквы исходного алфавита соответствующими буквами подстановочного алфавита (О - П, С - О, Н - Т и т.д.). Так буква О в исходном алфавите имеет номер 16, k =8. По правилу А (2×8)= В (33-2×8) буква О заменяется буквой с номером 17, т.е. П.

В шифрованном виде эта фраза примет следующий вид:

ПОТПГЭ ШБЖЙУЭ ЙТХПСНБЧЙЙ.

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

 

Метод перестановки

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

é1 2 3 4 ù

ë2 4 1 3û

В этом случае фраза:

ОСНОВЫ ЗАЩИТЫ ИНФОРМАЦИИ

будет представлена в следующем виде:

СООНЫЗВ ЩТАИ НЫИОМФРИАИ.

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

 

Многоалфавитные шифры

     Слабая криптостойкость моноалфавитных подстановок преодолевается с применением подстановок многоалфавитных. Для защиты от частотного анализа были разработаны многоалфавитные шифры, в которых для шифрования сообщения периодически используется несколько различных подстановочных алфавитов. Если задано r подстановочных алфавитов, то исходное сообщение разбивается на группы по r символов, для шифрования i -го символа группы используется i -ый подстановочный алфавит. Например, для r =4 буквы с номерами 1,5,9,13,... шифруются 1 алфавитом, буквы с номерами 2,7,10,14,... - 2 алфавитом, и т.д.

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

        

Задание на лабораторную работу

 

1. Разработать алгоритм и составить программу, позволяющую закодировать любой текст одним из вышеизложенных методов и выполнить обратное преобразование. Метод, которым необходимо зашифровать исходную информацию, выбирается в соответствии с вариантом из таблиц 1.1, 1.2, 1.3. Язык программирования выбирается произвольно.

2. Осуществить вывод на экран или принтер полученной криптограммы.

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

4. Результаты работы оформить в виде отчета.

5. Содержание отчета:

- описание используемого метода,

- описание исходных данных,

- алгоритм работы программы,

- текст программы,

- результаты работы программы,

- анализ результатов

-  выводы.

 

Варианты индивидуальных заданий

Таблица 1.1 - Методы шифрования

Ном вар.	Метод шифрования	Таблица	Номер зада-ния в таблице	Представление исходного текста
1	Подстановка	2	3	Английский алфавит
2	Перестановка	3	1	ASCII-код
3	Многоалфавитные шифры	2	1, 2, 5	Русский алфавит
4	Перестановка	3	2	Русский алфавит
5	Подстановка	2	4	Английский алфавит
6	Многоалфавитные шифры	2	1, 3	Русский алфавит
7	Подстановка	2	1	Английский алфавит
8	Многоалфавитные шифры	2	2, 5	Английский алфавит
9	Перестановка	3	3	ASCII-код
10	Подстановка	2	2	Русский алфавит
11	Перестановка	3	4	ASCII-код
12	Многоалфавитные шифры	2	1, 3, 4	Русский алфавит

Таблица 1.2 – Подстановочные алфавиты

Ном. вар.

Исходный алфавит

Подстановочный алфавит

1

2

3

4

5

1

А

A

Б

V

С

C

О

Z

Ю

C

М

V

2

Б

B

Ю

W

О

D

П

пробел

Я

D

Н

W

3

В

C

Г

X

У

A

М

.

Ы

A

О

X

4

Г

D

Ы

Y

М

B

Н

X

Э

B

П

Y

5

Д

E

Е

Z

К

H

Х

Y

Ь

H

Р

Z

6

Е

F

Ь

пробел

Х

I

Л

,

Ъ

I

С

пробел

7

Ё

G

З

.

Ч

J

И

!

Ш

J

Т

.

8

Ж

H

Ш

,

И

E

Й

S

Щ

E

У

,

9

З

I

Й

!

Щ

F

Ж

T

Ц

F

Ф

!

10

И

J

Ц

:

Ж

G

З

:

Ч

G

Х

:

11

Й

K

Л

;

Ъ

O

Д

;

Ф

O

Ц

;

12

К

L

Ф

?

Д

P

Е

Q

Х

P

Ч

?

13

Л

M

Н

-

Э

Q

В

R

Т

Q

Ш

-

14

М

N

Т

K

В

R

Г

?

У

R

Щ

K

15

Н

O

П

L

Я

K

А

-

Р

K

Ъ

L

16

О

P

Р

M

А

L

Б

N

С

L

Ь

M

17

П

Q

С

N

Б

M

Ю

O

О

M

Ы

N

18

Р

R

О

O

Ю

N

Я

P

П

N

Э

O

19

С

S

У

P

Г

U

Ы

L

М

U

Ю

P

20

Т

T

М

Q

V

Э

M

Н

V

Я

Q

21

У

U

Х

R

Е

W

Ь

N

К

W

пробел

R

22

Ф

V

К

S

Ь

:

пробел

O

Л

:

А

S

23

Х

W

Ч

T

З

S

Ш

P

про бел

S

Б

T

24

Ц

X

И

U

Ш

T

Щ

A

Й

T

В

U

25

Ч

Y

Щ

A

Й

Z

Ц

B

Ж

Z

Г

A

26

Ш

Z

Ж

B

Ц

пробел

Ч

C

З

пробел

Д

B

27

Щ

пробел

Ъ

C

Ё

X

Ф

D

Д

X

Е

C

28

Ъ

.

Д

D

Ф

Y

К

E

Е

Y

Ё

D

29

Ь

,

Э

E

Н

;

Т

F

В

;

Ж

E

30

Ы

!

В

F

Т

?

У

G

Г

?

З

F

31

Э

:

Я

G

П

-

Р

H

А

-

И

G

32

Ю

;

пробел

H

Р

.

С

I

Б

.

Й

H

33

Я

?

А

I

Ы

,

Ъ

J

Ё

,

К

I

34

про бел

-

ё

J

Л

!

Ё

K

И

!

Л

J

 

Таблица 1.3 - Группы перестановок

Номер вар.	Группа перестановки
1
2
3
4
5

 

1.5. Контрольные вопросы

1. Почему метод подстановки имеет слабую надежность?

2. Что такое частотный анализ?

3. Что является криптографическим ключом в методе перестановки?

ЗАДАНИЕ №2.

Задание на лабораторную работу

1. Выбрать в таблице параметры генератора ПСЧ: A, C, T(0), b.

2. Разработать программу шифрования и дешифрования текста.

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

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

5. Результаты работы оформить в виде отчета.

6. Содержание отчета:

- описание используемого метода,

- описание исходных данных,

- алгоритм работы программы,

- текст программы,

- результаты работы программы,

- анализ результатов

- выводы.

 

Варианты индивидуальных заданий

Таблица 2.1 – Генераторы ПСЧ

№ варианта	Вид генератора ПСЧ	Количество разрядов b
1	Линейные конгруэнтные датчики ПСЧ	6
2	Гаммирование с обратной связью	7
3	Линейные конгруэнтные датчики ПСЧ	8
4	Гаммирование с обратной связью	6
5	Линейные конгруэнтные датчики ПСЧ	7
6	Гаммирование с обратной связью	8
7	Линейные конгруэнтные датчики ПСЧ	6
8	Гаммирование с обратной связью	7
9	Линейные конгруэнтные датчики ПСЧ	8
10	Гаммирование с обратной связью	6
11	Линейные конгруэнтные датчики ПСЧ	7
12	Гаммирование с обратной связью	8
13	Линейные конгруэнтные датчики ПСЧ	6
14	Гаммирование с обратной связью	7
15	Линейные конгруэнтные датчики ПСЧ	8

 

 

2.5. Контрольные вопросы

 

1. Какие параметры конгруэнтного генератора необходимо выбрать для получения максимальной длины последовательности псевдослучайных чисел?

2. От чего зависит длина псевдослучайной последовательности?

3. Принцип действия генераторов с обратной связью?

4. Какие стандарты используют методы гаммирования?

ЗАДАНИЕ № 3.

СЕТИ ФЕЙШТЕЛЯ

                               

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

 

Задание на лабораторную работу

1. Выбрать в таблице параметры для сети Фейштеля

2. Разработать программу шифрования и дешифрования текста.

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

4. Результаты работы оформить в виде отчета.

5. Содержание отчета:

- описание используемого метода,

- описание исходных данных,

- алгоритм работы программы,

- текст программы,

- результаты работы программы,

- анализ результатов

- выводы.

Варианты индивидуальных заданий

Варианты заданий представлены в таблице 3.1. номер варианта выбирается в соответствии с номером студента в списке группы.

 

 

Таблица 3.1 – Параметры сети Фейштеля

Номер вар.	Количество раундов		Образующая функция
1	8		Сложение
2	10		Исключающее ИЛИ
3	12		Циклический сдвиг вправо
4	14		Умножение по модулю 2^N
5	10		Арифметический сдвиг вправо
6	18		Арифметический сдвиг влево
7	20		Сложение
8	8		Умножение по модулю 2^N
9	24	Исключающее ИЛИ
10	20	Сложение
11	18	Умножение по модулю 2^N
12	28	Исключающее ИЛИ
13	12	Сложение
14	14	Циклический сдвиг влево
15	24	Исключающее ИЛИ

3.4 Контрольные вопросы

1. Какова структура классической сети Фейштеля?

2. Что называется раундом в сети Фейштеля?

3. Какими свойствами обладает сеть Фейштеля?

4. Каким образом используется материал ключа при шифровании?

 

ЗАДАНИЕ №4.

ИЗУЧЕНИЕ АЛГОРИТМОВ RSA

 

    Цель работы: Освоить механизм шифрования и дешифрования данных в криптографической системе с открытыми ключами RSA.

 

 

Криптосистема RSA

 

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

Алгоритм RSA работает следующим образом:

Пусть p и q - два больших различных простых числа, и пусть n = p × q и e некоторое целое, взаимно простое с (p -1)×(q -1).

Пространства открытых текстов M_k и зашифрованных сообщений C_k представляют собой множество неотрицательных целых чисел Z_n, меньших n. Если исходное сообщение окажется слишком длинным, чтобы принадлежать Z_n, его необходимо разбить на части, равные m.

Соответствующая ключу k функция шифрования E_k: M_k -> C_k определяется как E_k (m) = m ^e mod(n). Для того, чтобы полностью определить алгоритм ее вычисления, достаточно записать e и n в открытый справочник. Такая пара называется открытым ключом.

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

Эффективный алгоритм вычисления Dk легко получить, задав дополнительную секретную информацию p и q. С этой целью, используя обобщенные алгоритмы Евклида для нахождения наибольшего общего делителя, чтобы вычислить целое число d, такое что e × d = 1 mod ф (n), где ф (n) = (p -1)× (q -1) – функция Эйлера. По теореме Эйлера m ^(ed) = m mod(n) для любого целого числа m и, следовательно, (m ^e) ^d mod(n) = m, при условии что  0 <= m < n, что обеспечивается, когда m принадлежит M_k.

Функция дешифрования D_k: C_k -> M_k в связи с этим определяется как D_k (c) = с ^d mod(n), и эффективный алгоритм для модульного возведения в степень также может быть использован и для ее вычисления. Тогда каждый пользователь криптосистемы RSA должен выбрать целые числа p, q и e и вычислить с их помощью d. После чего он делает свой открытый ключ доступным в пользовательском справочнике, тогда как d сохраняет в секрете. Это дает возможность любому другому пользователю шифровать посылаемые ему сообщения, которые только он и может расшифровать. Для того чтобы эта идея была реализована практически, решающим является удовлетворение требование, чтобы генерация больших случайных простых чисел и вычисление d были легко осуществимы.

Например, пусть p = 19 и q = 23, тогда n = 437 и ф (n) = 396. Пусть также e = 13, и поэтому d = 61, так как 13×61 = 793 = 2 ф (n)+1. Тогда сообщение в открытом текcте m = 123 будет зашифровано как c = 123¹³ mod(437) = 386. Действительно, 386⁶¹ mod(437) = 123.

Если бы существовали эффективные методы разложения на сомножители (факторинга), то, разложив n на сомножители (факторы) p и q, можно было бы получить секретный (private) ключ d. Таким образом надежность криптосистемы RSA основана на трудноразрешимой задаче разложения n на сомножители (то есть на невозможности факторинга n) так как в настоящее время эффективного способа поиска сомножителей не существует.

 

4.1.2. Алгоритм шифрования и дешифрования RSA.

 

1. Выберем два больших простых p и q.

2. Определим n = p × q.

3. Выберем большое случайное число, которое назовем e. Это число должно быть взаимно простым с результатом (p -1)×(q -1).

4. Определим такое число d, для которого является истинным соотношение

(e × d) mod((p -1)×(q -1))=1.

5. Назовем открытым ключом числа e и n, а секретным ключом - числа d, p и q.

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

- разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа М (i)= 0,1,..., n -1;

- зашифровать текст, рассматриваемый как последовательность чисел M (i) по формуле:

         C (i) = (M (i)^e)mod n;                                                                         (4.1)        

    Чтобы расшифровать эти данные, используется секретный ключ { d, n } и выполняются следующие вычисления:

       M (i) = (C (i)^d) mod n.                                                                            (4.2)

    В результате получают исходный текст M (i).

 

Задание на лабораторную работу

 

1. Разработать программу, осуществляющую шифрование и дешифрование алгоритмом RSA.

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

3. Зашифрованный текст оформить в виде самостоятельного файла.

4. В программе предусмотреть проверку, являются ли два числа взаимно простыми.

5. Результаты работы оформить в виде отчета.

6. Содержание отчета:

- описание используемого метода,

- описание исходных данных,

- алгоритм работы программы,

- текст программы,

- результаты работы программы,

- анализ результатов

- выводы.

 

4.3. Контрольные вопросы

 

1. Что такое однонаправленные функции?

2. Основные свойства однонаправленных функций с потайным ходом?

3. Какие криптоалгоритмы используют однонаправленные функции?

4. Как реализуется программное возведение в степень для больших чисел?

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Шаньгин В.Ф. Защита информации в компьютерных системах и сетях /В.Ф.Шаньгин. - М: ДМК, 2012.-593 с.

2. Введение в криптографию: новые математические дисциплины. Учебник/под ред. В.В.Ященко.- СПб: Питер, 2001.-287 с.

3. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях./ М.А. Иванов.- М.: Кудиц-образ, 2001.-363с.

4. Анин Б. Защита компьютерной информации./ Анин Б. - СПб,Киев,М.: БХВ-Петербург, 2000.- 368 с.

5. Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си./ Брюс Шнайер- М:Триумф, 2002. – 816 с.

 

 

ЗАДАНИЕ № 1.

ШИФРОВАНИЕ ДАННЫХ МЕТОДАМИ ПОДСТАНОВКИ, ПЕРЕСТАНОВКИ И ПОЛИАЛФАВИТНЫМИ ШИФРАМИ

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