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

Проблемой защиты информации путем ее преобразования занимается криптология (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. Что является криптографическим ключом в методе перестановки?