Базовые криптографические алгоритмы

⇐ ПредыдущаяСтр 5 из 5

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

В предыдущем подразделе упоминалось о двух классах криптосистем, реализующих подобные алгоритмы: симметричные и асимметричныесистемы. Симметричность означает, что ключи, задающие пару взаимно обратных преобразований, идентичны либо могут быть получены один из другого путем простых преобразований. Асимметричность подразумевает, что ключи различны и знание одного (K₁) не должно позволять определению другого (по крайней мере, нахождение другого должно быть чрезвычайно трудным).

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

(или M′ ). (5.1)

Предполагается, что возможно Е_k= D_k= K.

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

В асимметричных алгоритмах невозможно выполнение равенств Е_k= D_k= K.

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

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

Примером такого шифра является знаменитый шифр Цезаря, в котором каждый символ открытого текста заменяется символом, находящимся тремя символами правее (по модулю 26 или по принципу кольца): «A» меняется на «D», «B» – на «E», «W» – на «Z», «X» – на «A» и т. д. (в некоторых случаях во внимание принимается 27-й символ – пробел). Для расшифрования необходимо выполнить обратную замену.

Пример 5.1. Имеем открытый текст М = «cba». На основе шифра Цезаря С = «gfd».

Простой подстановочный шифр применяется, например, в системе UNIX: простая программа шифрования (ROT13) использует смещение на 13 позиций, т. е. символ «А» заменяется на «N» и т. д.

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

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

Пример 5.2. М = «ВАСЯ ЛЮБИТ МАШУ». Запишем этот текст как показано на рис. 5.2.

Рис. 5.2. Использование простого

вертикального перестановочного шифра

Считывание по столбцам снизу вверх приводит к такому шифр-тексту: С = «_ЛВМЮААБСШИЯУТ_».

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

Рис. 5.3. Использование перестановочного шифра

Осуществляя считывания по уровням, начиная с верхнего, получим следующий шифртекст: С = «СЮ_УАЯЛБТМШВ_ИА».

Характеристики и реализация симметричных

И асимметричных алгоритмов

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

Однако, если известны b, a и n, то x можно найти на основе вычисления логарифма. Оказывается, что при некоторых значениях b, a и n определить х является большой проблемой.

Например, если , то . Однако нетрудно заметить, что у следующего уравнения нет решений: . Еще труднее решить задачу для 1024-битовых чисел.

Особый интерес представляют дискретные логарифмы мультипликативных групп полей простых чисел: GF(p). Если р – простое число, используемое в качестве модуля, то сложность поиска дискретных логарифмов в GF(p)соответствует разложению на множители числа n того же размера, где n – произведение двух простых чисел примерно равной длины, т. е. вычисление дискретных логарифмов тесно сопряжено с разложением на множители. Если стоит вопрос дискретного логарифмирования, то решается задача разложения на множители (истинность обратного пока никем не доказана).

С. Полиг (S. Pohlig) и М. Хеллман (M. Hellman) нашли способ быстрого вычисления дискретных логарифмов в поле GF(p) при условии, что р –1 раскладывается только на малые простые множители. По этой причине в криптографии используются только такие поля, в которых у числа р –1 есть хотя бы один большой простой множитель.

Описанные особенности имеют отношение в основном к асимметричным алгоритмам. Далее рассмотрим наиболее известные алгоритмы, относящиеся к обоим типам шифрования.

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

Для понимания существа анализируемого алгоритма целесообразно рассмотреть следующий простой пример.

Пример 5.4. Пусть открытое сообщение в двоичной форме имеет следующий вид: М_{(0, 1)}= 10101100. Считаем, что выбран симметричный ключ K₁= K₂= K = 1010. Используется самая простая операция шифрования:

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

где i – i-й блок шифрования; M_i – i-я часть сообщения.

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

Алгоритм DES (Data Encryption Standard), как и другие симметричные и асимметричные алгоритмы, использует множественные арифметическо-логические преобразования исходного текста.

DEA оперирует с блоками данных размером 64 бит и использует ключ длиной 56 бит. Каждый 8-й бит ключа (всего – 8) применяется для контроля четности, т. е. предназначен для контроля ошибок. Такая длина ключа соответствует 10¹⁷ комбинациям, что обеспечивало до недавнего времени достаточный уровень безопасности.

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

Для реализации упомянутых действий вводится функция f, которая оперирует с 32-разрядными словами исходного текста (А) и использует в качестве параметра 48-разрядный ключ (J; в каждом из фиксированного множества преобразований биты ключа сдвигаются и затем из 56 битов ключа выбираются 48).

Схема работы функции f показана на рис. 5.4.

Рис. 5.4. Схема реализации функции f

Сначала 32 входных разряда расширяются до 48, при этом некоторые разряды повторяются. Результирующий 48-разрядный код преобразуется в 32-разрядный с помощью S-матриц. На выходе S-матриц осуществляется перестановка символов, согласно рекомендуемой схеме перестановок.

Преобразование начинается с перестановки (пермутации) бит в 64-разрядном блоке исходных данных: 58-й бит становится первым, 50-й – вторым и т. д.

Полученный блок делится на две 32-разрядные части: L₀ и R₀. Далее 16 раз (раундов) повторяются 4 процедуры в соответствии с рис. 5.5.

5.3.2. Криптографические системы с открытым (публичным) ключом. Асимметричное шифрование. Математическое решение проблемы перехода на аcимметричное шифрование нашли в 1976 г. Диффи (Diffie) и Хеллман (Hellman)^{^[2]}. Основное отличие асимметричных систем от симметричных заключается в том, что ключ для зашифрования отличается от ключа для расшифрования сообщений (K₁ ¹ K₂). Более того, ключ для расшифрования не может быть вычислен из ключа зашифрования.

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

. (5.2)

Последнее равенство можно также записать в виде:

(5.3)

В (5.3) параметр a^–1 называют обратным значением. Задача вычисления обратных значений намного сложнее обычной. Рассмотрим это на примере.

Функция Эйлера, которую иногда называют функцией «фи» Эйлера и записывают как j(n), указывает количество положительных целых чисел, меньших n и взаимно простых с n для любого n, большего 1.

Если n – простое число, то . При , где p и q –простые числа, то . Эти числа используются в некоторых системах с открытым ключом, в том числе и в наиболее известной и широко используемой системе RSA.

⇐ Предыдущая 1 2 3 45