Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика 2015

10.2. Шифрование сообщений различными методами

Вместо хвоста - нога, А на ноге - рога. Л. Дербенеёв.

Рассмотрим, как зашифровать сообщение методом замены (другими словами методом подстановки). Вначале используем шифр Цезаря. Предположим, что требуется зашифровать сообщение «ГДЕ АББА».

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

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

ЁЖЗ ГДДГ.

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

Замена может осуществляться на символы другого алфавита и с более сложным ключом (алгоритмом замены). Для простоты опять приведем лишь начальные части алфавитов. Линии показывают порядок замены букв русского алфавита на буквы латинскою алфавита. Зашифруем фразу «ГДЕ АББА»:

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

CDB EFFE.

Рациональнее использованный в последнем случае ключ записать в виде таблицы:

А

Б

В

Г

д

Е

Е

F

А

С

D

В

При шифровании буквы могут быть заменены числами

в простейшем

случае порядковыми номерами букв в алфавите). Тогда наша шифровка будет выглядеть так:

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

Более высокую криптостойкость но сравнению с шифром Цезаря имеют аффинные криптосистемы.

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

Аффинные криптосистемы задаются при помощи двух чисел а и Ь. Для русского алфавита эти числа выбираются из условия а > 0, Ь < 32. Максимальное число символов в используемом алфавите обозначаются символом у. Причем числа а и у = 33 должны быть взаимно простыми. Если это условие не будет выполняться, то две разные буквы могут отображаться (превращаться) в одну. Каждый код буквы открытого текста р заменяется кодом буквы криптограммы но следующему правилу. Вначале вычисляется число а = а-р + Ь, а затем выполняется операция целочисленного деления числа а на число у = 33, то есть а = p(mod (у)). В качестве кода символа шифрограммы используется остаток от целочисленного деления р.

Для определенности выберем такие числа: а = 5 и Ъ =3.

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

Буква открытого текста

А

Б

В

Г

Д

Е

Я

Код буквы открытого текста р

0

1

2

3

4

5

32

Код буквы шифрограммы Р

3

8

13

18

23

28

31

Буква шифрограммы

Г

3

М

С

Ц

Ы

Ю

Предположим, что нужно зашифровать сообщение «ГДЕ АББА». В результате получим:

Откры тый текст

Г

д

Е

А

Б

Б

А

Шифрограмма

С

ц

Ы

Г

3

3

Г

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

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

В следующей таблице приведены результаты шифрования фразы «ГДЕ АББА» разными одноалфавитными шифрами.

Шифр

Криптограмма

Шифр атбаш

ЬЫЪ ЯЮЮЯ

Шифр Цезаря

ЁЖЗ ГДДГ

Квадрат Полибия

14 15 1611 12 12 11

Аффинные криптоситстемы

сцы гззг

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

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

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

Ниже приведен фрагмент ключа многоалфавитной замены:

А

Б

В

Г

Д

Е

18

7

5

19

21

2

12

4

90

35

83

15

48

14

22

10

99

32

С помощью многоалфавитного шифра сообщение «ГДЕ АББА» можно зашифровать несколькими способами:

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

Рассмотрим еще один шифр многоалфавитной замены, который был описан в 1585 г. французским дипломатом Блезом де Инженером. Шифрование производится с помощью так называемой таблицы Виженера. Здесь, как и прежде, показана лишь часть таблицы для того, чтобы изложить лишь идею метода.

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

Предположим, что нужно зашифровать сообщение «ГДЕ АББА». В качестве ключа выберем слово «ДЕВА». В результате получим:

Сообщение

Г

Д

Е

А

Б

Б

А

Ключ

д

Е

В

А

д

Е

В

Шифровка

я

Я

Г

А

э

Ь

Ю

В результате преобразований получится шифровка

ЯЯГ АЭЫО.

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

Шифрование производится с помощью квадрата (или прямоугольника), в который занесены буквы соответствующего национального алфавита. Буквы записываются в квадрат или прямоугольник в произвольном порядке. Этот порядок записи букв, и конфигурация таблицы являются секретным ключом. Для определённости возьмём прямоугольную таблицу размером 8x4, в качестве букв алфавита - кириллицу, а буквы расположим в алфавитном порядке. Так как число русских букв 33, а число клеток - 32, исключим из таблицы букву Ё.

Предположим, что требуется зашифровать слово КРИПТОГРАФИЯ.

Рассмотрим правила шифрования.

  • 1. Открытый текст делится на блоки но две буквы (по два символа), причем буквы в одном блоке не должны быть одинаковыми. Произведём разделение исходного слова на блоки по две буквы КР-ИП-ТО-ГР-АФ-ИЯ.
  • 2. Если буквы шифруемого блока находятся в разных строках и столбцах таблицы, то в качестве заменяющих букв используются буквы таблицы, расположенные в углах прямоугольника, охватывающего буквы открытого текста. При формировании криптограммы первой берётся буква, которая расположена в одном столбце со второй буквой блока открытого текста.

Например, блок КР шифруется символами ИТ.

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

Блок открытого текста ЖЦ будет преобразован в символы ОЮ, а блок ТЪ - в символы ЪВ.

  • 5. Если открытый текст содержит нечетное число символов, то к открытому тексту добавляется незначащий символ (например, знаки препинания или пробел).
  • 6. Если в открытом тексте есть блоки с одинаковыми символами, то эти два символа разделяют знаками препинания или пробелом.

В соответствии с описанными правилами слово КРИПТОГРАФИЯ будет преобразовано в криптограмму ИТЙИЦКАУДРПШ.

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

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

Данный шифр для отдельно взятой буквы можно считать многоалфа- вигным. Однако пары букв шифруются везде одинаково. Поэтому в широком смысле понятия криптографическую систему Хилла следует отнести к одноалфавитным шифрам.

Первоначально открытый текст методом замены следует преобразовать в совокупность чисел. Предположим, что шифруется текст, написанный с использованием 26-ги латинских букв. Выберем следующий алгоритм замены букв на числа: латинские буквы А, В, С, D, ..., Z будем заменять соответственно числами 1, 2, 3, 4,..., 26. Другими словами: пронумеруем буквы в порядке их расположения в алфавите, и при замене будем использовать их порядковые номера. В данном случае выбран такой алгоритм замены, но понятно, что он может быть любым.

Предположим, что нужно зашифровать немецкое слово ZEIT. Заменим буквы в соответствии с их порядковыми номерами в алфавите четырьмя числами: 26- 5- 9- 20.

Далее следует выбрать некоторое число d > 2. Это число показывает, порядок разбиения открытого текста на группы символов (определяет, сколько букв будет в каждой lpyrine). С математической точки зрения число d показывает, сколько строк должно быть в векторах-столбцах. Примем d = 2. Это означает, что числа 26 - 5 - 9 - 20 нужно разбить на lpyniibi по два числа в каждой группе и записать их в виде векторов-столбцов:

Далее следует записать матрицу исходного текста:

Шифрование выполняется путем вычисления следующих выражений:

В результате расчетов получится:

Окончательный результат шифрования получается путем целочисленного деления элементов векторов-столбцов С1 и С2 по модулю 26 (нахождение остатка от целочисленного деления).

В результате шифрования по каналу связи будет оправлена последовательность чисел: 19 - 22 - 24 - 3. Для ранее выбранного ключа замены это будет соответствовать шифрограмме SVXC. Данный пример иллюстрирует тот факт, что системы шифрования часто базируются на математических преобразованиях.

Рассмотрим примеры шифрования сообщения методом перестановок.

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

Для пояснения идеи возьмем квадратную таблицу (матрицу) 8x8. Будем записывать открытый текст в эту матрицу последовательно но строкам сверху вниз, а считывать криптограмму по столбцам последовательно слева направо.

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

н

А

П

Е

Р

в

О

м

к

У

Р

С

Е

т

Я

ж

Е

Л

О

У

ч

И

т

Ь

С

Я

т

о

Л

ь

К

О

П

Е

р

В

ы

Е

Ч

Е

Т

ы

р

Е

г

О

д

А

д

Е

К

А

н

А

Т

В таблице символом «_» обозначен пробел.

В результате преобразований получится шифровка:

НА ПЕРВОМ КУРСЕ ТЯЖЕЛО УЧИТЬСЯ ТОЛЬКО ПЕРВЫЕ ЧЕТЫРЕ ГОДА ДЕКАНАТ.

НМТЧОРЫ А ЯИЛВРД КЖТЬЫЕЕПУЕЬКЕ КЕРЛСО ГАРСОЯ ЧОНВЕ__ПЕДЛО_УТЕТЛТ

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

Ключом в данном случае является размер матрицы, порядок записи открытого текста в матрицу и порядок считывания шифрограммы. Естественно, что ключ может быть другим. Например, запись открытого текста по строкам может производиться в таком порядке: 48127653, а считывание криптограммы может происходить по столбцам в следующем порядке: 81357642.

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

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

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

Рассмотрим пример дешифрации криптограммы, полученной методом перестановок. Известно, что при шифровании использованы матрица 6x6, ключ записи 352146 и ключ считывания 425316. Текст шифрограммы таков: ДК АГЧЬОВ А_ РУ А АКОЕБЗЕРЕ_ ДСОХТЕСЕ_ Т_ ЛУ Разобьем шифрограмму на группы но 6 символов:

ДКАГЧЬ ОВАРУ ААКОЕБ ЗЕРЕД СОХТЕС Е_Т_ЛУ Затем первую фунпу символов запишем в столбец 4 матрицы 6x6, так как первая цифра ключа считывания - 4 (см. рисунок а). Вторую группу из 6 символов запишем в столбец 2 (см. рисунок б), третью ipynny символов - в столбец 5 (см. рисунок в), пропустив две фазы заполнения матрицы, изобразим полностью заполненную матрицу (см. рисунок г).

Считывание открытого текста в соответствии с ключом записи начинаем со строки 3, затем используем строку 5 и т.д. В результате дешифрования получаем открытый текст:

ХАРАКТЕР ЧЕЛОВЕКА СОЗДАЕТ ЕГО СУДЬБУ Естественно, что описанная процедура дешифрования криптограммы производится компьютером автоматически с помощью заранее разработанных нрофамм.

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

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

Генератор гаммы выдает последовательность битов: уц уг, уз,..., Уп- Этот ноток битов и поток битов открытого текста pi, р>, Рз,..., д, подвергаются поразрядно логической операции Исключающее ИЛИ (суммирование по модулю два). В результате получается поток битов криптограммы:

При дешифровании на приемной стороне операция Исключающее ИЛИ выполняется над битами криптограммы и тем же самым потоком гаммы:

Благодаря особенностям логической операции Исключающее ИЛИ на приемной стороне операция вычитания заменяется данной логической операцией. Сказанное иллюстрируется примером.

р

1

0

0

1

1

0

0

1

G

1

1

0

0

1

1

1

0

С

0

1

0

1

0

1

1

1

Предположим, что открытый текст Р = 10011001, а гамма G = 11001110. В результате шифрования криптограмма С будет иметь следую- щий вид:_

На приемной стороне повторно выполняется логическая операция Ис- ключающее ИЛИ:_

с

0

1

0

1

0

1

1

1

G

1

1

0

0

1

1

1

0

Р

1

0

0

1

1

0

0

1

Из этих таблиц видно, что переданный и принятый байты одинаковые.

В ЭВМ преобразование открытого текста в числа происходит естественным путем, так как каждый символ кодируется двоичным числом. Вид этого преобразования зависит от используемой операционной системы. Для определенности будем считать, что сообщение в ЭВМ кодируется с помощью кодовой таблицы СР-1251. Итак, будем считать, что секретная гамма добавляется к открытому тексту но правилу сложения по модулю два без переносов в старшие разряды (логическая операция Исключающее ИЛИ). Результаты всех преобразований поместим в таблицу.

Открытый текст

Г

д

Е

А

Б

Б

А

Десятичное число

195

196

197

192

193

193

192

Двоичное число

11000011

11000100

11000101

11000000

11000001

11000001

11000000

Гамма (цесятич.)

32

18

36

11

61

23

3

Гамма (двоич.)

00100000

00010010

00100100

00001011

00111101

00010111

00000011

Криптогр. (твоич.)

11100011

11010110

11100001

11001011

11111100

11010110

11000011

Криптогр. (тесят .)

227

214

225

203

252

214

195

Криптограмма

Г

Ц

б

Л

Ь

Ц

г

Для наглядности результат шифрования (шифрограмма) переведен с помощью таблицы СР-1251 в буквы. Из таблицы видно, что открытый текст был записан прописными буквами, а криптограмма содержит как прописные, так и строчные буквы. Естественно, что при реальном (а не учебном) шифровании набор символов в шифрограмме будет еще богаче. Кроме русских букв будут присутствовать латинские буквы, знаки препинания, управляющие символы.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы