Шифры

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

Засекреченная информация
Засекреченная информация
Шифр


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


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


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

Классифицировать шифры можно по разным основаниям. Наиболее популярны такие:

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

2.  По существованию дешифрующего преобразования: обратимое преобразование, для которого существует обратное преобразование (дешифрующее), и необратимое — т.е. такое, для которого такого преобразования не существует.

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

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

1.  Для обмена сообщениями участникам нужно знать этот ключ. То есть, необходим способ безопасного обмена ключами.

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

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

4. Если есть некий "центр" хранения ключей — он может выдать себя за кого угодно.

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

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

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

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

2.  Появляется возможность создавать электронную подпись — т.е. создать контрольный "отпечаток" сообщения. Создать его может только отправитель — т.е. абонент, имеющий оба ключа, а проверить — любой участник обмена, у которого есть открытый ключ.

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

Процесс шифрования
Процесс шифрования



Возникает вопрос: если ключ согласовывается фактически при обращении, то, как все-таки понять, кто на другом конце канала связи, особенно если это абонент совершенно неизвестный?
Есть два подхода к решению этой проблемы, реализуемых в виде комплексов программ и данных, имеющих общее название — "инфраструктура открытого ключа":

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

Конечно, чтобы проверить сертификат, нужно доверять центру. Знать все центры заранее невозможно, а поэтому центры связываются по цепочке, т.е. центр может выдать сертификат другому центру, тот — третьему и т.д. Если пользователь доверяет корневому центру и не знает о компрометации подчиненных ему центров, он может быть уверенным, что абонент — именно тот, за кого себя выдает.

Корневой сертификат пользователь устанавливает сам или получает вместе с ОС. Существует несколько крупных центров сертификации, сертификаты и открытые ключи которых приходят в поставке ОС Microsoft и в дальнейшем постоянно обновляются.
Такие сертификаты могут сопровождать web-страницы, программы (особенно ориентированные на распространение через Интернет), сообщения электронной почты и т.п. На базе такой инфраструктуры действуют платежные системы, торговые площадки, корпоративные системы и т.п.

2. Подход, ориентированный на коллективное доверие. То есть в этом случае создается структура, в которой вы лично определяете тех людей, которым доверяете. Если во время проверки выясняется, что кто-то из тех, с кем вы работали раньше, тоже доверяет этому сертификату, то сертификат считается доверенным. Такой подход использован в популярном и известном пакете программ Pretty Good Privacy, PGP.

 

Примеры шифров и заданий

Шифр Цезаря
Одним из самых первых известных методов шифрования носит имя римского императора Юлия Цезаря, который если и не сам изобрел его, то активно им пользовался. Этот метод основан на замене каждой буквы шифруемого текста на другую путем смещения в алфавите от исходной буквы на фиксированное количество символов, причем алфавит читается по кругу, т.е. после буквы я рассматривается буква а. Регистр символов не учитывается. Так, например, слово байт при смещении на два символа вправо кодируется словом гвлф.
Задание. Расшифруйте слово НУЛТХСЁУГЛЧЛВ, закодированное с помощью шифра Цезаря. Известно, что каждая буква исходного текста заменяется третьей после нее буквой.
Ответ: зашифрованное слово - криптография - наука о принципах, средствах и методах преобразования информации для защиты ее от несанкционированного доступа и искажения.

Шифр Вижинера
Шифр Вижинера представляет собой шифр Цезаря с переменной величиной сдвига. Величина сдвига задается некоторым ключевым словом. Например, слово ВАЗА означает следующую последовательность сдвигов букв исходного текста: 3 1 9 1 3 1 9 1 и т.д.
Задание. Используя ключевое слово ВАГОН, зашифруйте слова: АЛГОРИТМ, ПРАВИЛА, ИНФОРМАЦИЯ.
Ответ: при ключевом слове ВАГОН последовательность сдвигов букв при шифровании следующая: 3 1 4 16 15 3 4 и т.д. Это означает, что слово АЛГОРИТМ шифруется как ГМЖЮЯЛУР, слово ПРАВИЛА — как ТСДСЧОБ, слово ИНФОРМАЦИЯ — как ЛОШЮЯПБЪШН.

Шифр Тритемиуса
Еще большие трудности для криптоанализа представляет шифр, связы­ваемый с именем ученого аббата из Вюрцбурга Тритемиуса, которого к занятиям криптографией побуждало, быть может, не только монастырское уединение, но и потребность сохранять от огласки некоторые духовные тайны. Этот шифр является развитием описанного выше шифра Цезаря и состоит в следующем. Буквы алфавита нумеруются по порядку числами 0, 1, ..., 30 .При шифровании некоторое ключевое слово (или номера его букв) подписывается под сообщением с повторениями, как показано ниже:
всвязиссоздавшимсяположениемотодвигаемсрокивозвращениядомой
разаписьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзмзай анис
Каждая буква сообщения "сдвигается" вдоль алфавита по следующему правилу: буква с номером т в табл. 1, под которой стоит буква ключевого слова с номером k, заменяется на букву с номером / = т + k (если т + k < 31) или букву с номером 1 = тт т + k – 31 (если т + k > 31).
Задание. Используя ключевое слово байт, зашифруйте шифром Тритемиуса текст: "Срочно приезжай Ангел".
Ответ. 18.16.23.10.14.14.24.3.9.5.16.24.1.9.9.0.4.5.20.


"Тарабарская грамота"
Задание. Найдите ключ к "тарабарской грамоте" - тайнописи, применявшейся ранее в России для дипломатической переписки:
Пай цике тсюог т "камащамлтой чмароке"- кайпонили, нмирепяшвейля ш Моллии цся цинсоракигелтой неменилти
Ключом в данном случае будем называть правила, по которым шифруется исходный текст.
Ответ. Обратим внимание на слово Моллии в шифрограмме. Оно очень похоже на слово России. Предположим, что ш Молли - это в России. Тогда можно заметить, что все гласные остались без изменения, т.е. они не шифруются. Посмотрим на согласные. Мы уже выяснили, что в шифрограмме м - это р, ш - в, а л - с. Выпишем все согласные буквы:
б в г д ж з к л м н п р с т ф х ц ч ш щ
Примечание. В верхней строке записаны буквы в шифрограмме, в нижней- зашифрованные буквы.
Проанализировав табличку, можно увидеть "симметрию" (предпоследняя буква ш означает вторую согласную букву в). Исследовав эту закономерность, можно установить следующее правило шифрования согласных букв: каждая согласная буква заменяется на "симметричную" ей букву в перечне всех согласных букв:


б

в

г

д

ж

з

к

л

м

н

р

с

т

ф

х

ц

ч

ш

щ

щ

ш

ч

ц

х

ф

т

с

р

п

м

л

к

з

ж

ц

г

в

б

В этом шифре каждая согласная меняется на букву, расположенную непосредственно над ней или под ней в таблице.

Номера вместо букв
Задание. Если в некотором слове заменить буквы на номера этих букв в алфавите, то получится число 222122111121. Какое это слово?
Ответ. Достаточно рассмотреть лишь буквы с номерами 1, 2, 11, 12, 21 и 22. Это буквы А, Б, К, Л, У, Ф. Проанализировав возможные варианты, можно получить ответ: ФУФАЙКА.

Однажды в поезде
Когда-то давно, когда еще существовала страна под названием "СССР", автор ехал в поезде и с удивлением обнаружил, что если в названиях пунктов отправления и назначения поезда заменить буквы их номерами, в алфавите то они (названия) записываются с помощью всего лишь двух цифр: 211221 и 21221.
Задание. Откуда и куда ехал автор?
Ответ. Маршрут движения поезда, которым ехал автор: БАКУ - УФА.

Частотный анализ
Восстановить буквы зашифрованного текста с большой уверенностью можно, анализируя частоту появления тех или иных букв и их сочетаний. Этот метод (он так и называется — частотный анализ) основывается на том, что известно, как часто встречается та или иная буква в русском языке (или в английском языке — именно это учитывал герой рассказа Эдгара По "Золотой жук", расшифровывая найденный пергамент). Даже если в каких-то частях текста возникает неоднозначность, она легко устраняется по смыслу.
Относительные частоты букв русского языка указаны в табл. 1.
Таблица 1


К9

Буква

Относит.
частота

Ns

Буква

Относит.
частота

N9.

Буква

Относит.
частота

о

а

0,062

10

к

0,028

20

ф

0,002

1

б

0,014

11

л

0,035

21

х

0,009

2

в

0,038

12

м

0,026

22

ц

0,004

3

г

0,013

13

н

0,053

23

ч

0,012

4

д

0,025

14

о

0,090

24

ш

0,006

5

е, ё

0,072

15

п

0,023

25

щ

0,003

б

ж

0,007

16

р

0,040

26

ы

0,016

7

з

0,016

17

с

0,045

27

ь, ъ

0,014

8

и

0,062

18

т

0,053

28

э

0,003

9

й

0,010

19

у

0,021

29

ю

0,006

 

 

 

 

 

 

30

я

0,018

Буквы е и ё, а также ь, ъ кодируются обычно одинаково, поэтому в таблице они не различаются. Как явствует из таблицы, наиболее частая буква русского языка — о. Ее относительная частота, равная 0,090, означает, что на 1000 букв русского текста приходится в среднем 90 букв о. В таком же смысле понимаются относительные частоты и остальных букв. В таблице не указан еще один "символ" — промежуток между словами (пробел). Его относительная частота наибольшая и равна 0,175.

 

Hosted by uCoz