Принципы криптографии

Презентация

 

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

 

1. Немного истории

 

Первым  документально зафиксированным  в письменности шифром является шифр Цезаря, хотя существуют свидетельства  о наличии простейших устройств  шифрования и у древних греков в V—VI веках до нашей эры. Историки относят к шифрованным даже некоторые  письмена еще более древних цивилизаций  — Месопотамии и Египта, хотя в то время сам факт письменного  изложения уже являлся барьером для большой части населения. В те времена использование своего, несоответствующего общепринятому, идеографического или слогового письма было почти 100% гарантией сохранности сообщения  в секрете.

 

Шифр Цезаря (I в. до н.э.), по свидетельству летописцев применявшийся  в переписке с подотчетными ему  правителями покоренных земель и  в военных походах, состоял из замены одних букв на соответствующие  им другие во всем тексте (Рисунок1). Закон  замены был очень прост: при шифровании сообщения вместо пятой буквы  латинского алфавита ставилась вторая, вместо четвертой — первая, вместо третьей — двадцать шестая и т. д. При дешифровании, естественно, сдвиг  уже нужно было делать в прямом направлении: вместо первой буквы брать  четвертую и т. д.

 

Исходный текст

 

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

 

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

 

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

 

Зашифрованный текст 

 

A

Б

В

Г

Д

Е

Ё

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

T

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ь

Ы

Э

Ю

Я

 

Э

Ю

Я

A

Б

В

Г

Д

Е

Ё

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

T

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ь

Ы

 

Зашифрованный текст 
Рисунок 1

В современной терминологии шифр Цезаря и его модификации, отличающиеся только законом выбора соответствий между буквами открытого и  секретного текстов, относятся к  одноалфавитным подстановкам или одноалфавитным заменам. Пожалуй, ни один из шифров за историю человечества не имел столько вариантов, областей применения и связанных с ним судеб, как этот. Его даже увековечили произведения, вошедшие в классику литературного жанра, — "Пляшущие человечки" Артура Конан Дойла, "Золотой жук" Эдгара По. Необходимо отметить, что и два слабых места этого шифра, использованные героями этих книг и известные теперь, пожалуй, каждому школьнику, были обнаружены довольно давно. Этот момент, к сожалению, скрытый глубоко в истории, несомненно, является зарождением криптоанализа — науки, имеющей противоположные цели с криптографией и занявшей советствующее место среди других в современном мире.

 

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

Редкие буквы  обычно не отслеживают подобным способом — их просто подбирают по смыслу в тех словах, где большая часть  распространенных букв уже раскрыта.

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

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

 

Квадрат Полибия или тюремная азбука

 

Рисунок  2. Квадрат Полибия

 

 

1	2	3	4	5
А	В	С	D	Е	1
F	G	Н	I	К	2
L	М	N	О	Р	3
Q	R	S	T	U	4
V	W	X	Y	Z	5

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

Вместо  буквы в письме записывалась пара чисел: номер строки и номер столбца  ячейки, в котором она располагалась. Также как и у шифра Цезаря, у данной схемы не счесть модификаций. В связи с тем, что в латинском  алфавите 26 букв (а в современном  русском — 33), и оба эти числа  очень "неудачно" раскладываются на сомножители, модификации либо выбрасывали  редко встречающиеся буквы, либо добавляли знаки препина­ния, цифры  и пустые элементы, добиваясь прямоугольников  и квадратов: 5x5, 5x6, 4x7, 6x6, 5x7.

 

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

 

Квадрат Кардано 

 

Для шифрования Кардано предложил использовать квадрат с прорезанными в нем  несколькими ячейками (Рисунок 3). Ячейки прорезались таким образом, чтобы  при повороте квадрата вокруг своего центра на 90°, потом на 180°, а затем  на 270° в прорезях поочередно появлялись все позиции исходного квадрата и, причем только по одному разу накладывался на листок для послания сначала в  исходном положении —выписывалась  слева направо сверху вниз первая порция (четверть) послания. Затем квадрат  поворачивался на 90°, скажем, по часовой  стрелке — выписывалась вторая четверть сообщения и т. д.

 

 

 

Рисунок 3. Квадрат Кардано

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

Например, для  квадрата 6x6 это число уже равняется 262 144, т. е. несет 18 бит информации.

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

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

 

Таблица Виженера

 

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

Пароль  с повторениями выписывался буква  к букве под исходным сообщением.

Каждая буква  зашифрованного текста бралась из таблицы  на пересечении строки, соответствовавшей  букве исходного текста, и столбца, соответствовавшего текущей букве  пароля. Подобный шифр получил название многоалфавитной замены. Очевидно, что он полностью лишен проблемы коротких слов и значительно более устойчив к частотному анализу. Для проведения настолько же успешного подбора букв необходим более чем в L раз больший объем шифрованного текста (где L — длина пароля). Это вызвано тем, что таблицы частот вычисляются отдельно для каждой из L групп букв, а, кроме того, и сама процедура подбора несколько усложняется.

 

А

B

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

В

C

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

N

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

О

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

Р

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Q

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

R

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

S

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

Т

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

U

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

)

J

К

L

М

N

О

Р

Q

R

S

Т

V

W

X

Y

Z

А

В

С

О

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

W

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

X

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

Y

Z

А

В

С

D

Е

F

G

Н

I

J

К

L

М

N

О

Р

Q

R

S

Т

U

V

W

X

Z

А

В

С

D

Е

F

G

Н

I

J

К

I

М

N

О

Р

Q

R

S

Т

U

V

W

X

Y