Современные информационные технологии

К.т.н., доцент Пархоменко И. И., Сира Т. О.

Национальный авиационный университет

Системы шифрования с открытым ключом

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

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

Более точно, имеют место преобразования:

сообщение + ОТКРЫТЫЙ КЛЮЧ ПОЛЬЗОВАТЕЛЯ А =

ШИФРОТЕКСТ + секретный ключ пользователя А = сообщение

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

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

Идея криптографии с открытым ключом впервые появилась в 1976 г. в революционной работе Диффи и Хеллмана «Новые направления в криптографии». Но только год спустя была опубликована первая (и наиболее успешная) криптосистема с открытым ключом, а именно, RSА.

Алгоритм RSA

Описание алгоритма шифрования

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.

Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций :

1. Выбираются два простых числа p и q

2. Вычисляется их произведение n=p×q.

3. Вычисляется функция Эйлера φ(n)=(p-1)(q-1).

4. Выбирается произвольное число e (e<n), такое, что НОД(e,φ(n))=1, то есть e должно быть взаимно простым с числом φ(n).

5. Методом Евклида решается в целых числах уравнение e×d+φ(n)×y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

6. Два числа (e,n) – публикуются как открытый ключ.

7. Число d хранится в строжайшем секрете. Пара чисел (d,n) – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

Как же производится собственно шифрование с помощью этих чисел :

1. Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

2. Подобный блок может быть интерпретирован как число из диапазона (0;2^k-1). Для каждого такого числа (назовем его m_i) вычисляется выражение:

c_i=((m_i)^e)mod n.

Блоки c_i и есть зашифрованное сообщение. Их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i.

Проясним использование алгоритма RSA на конкретном примере. Выбираем два простые числа p = 7; q = 17 (на практике эти числа во много раз длиннее). В этом случае n = =p×q будет равно 119. Теперь необходимо выбрать e, выбираем e= 5. Следующий шаг связан с формированием числа d так, чтобы d*e=1 mod [(p-1)(q-1)]. D = 77 (использован расширенный алгоритм Эвклида). d - секретный ключ, а e и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать представляется M = 19. С = M^e (mod n). Получаем зашифрованный текст C = 66. Этот “текст” может быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М= C^d (mod n) и C=66. В результате получается M = 19.

На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать адресату. На использовании общедоступных ключей базируется и так называемая электронная подпись, которая позволяет однозначно идентифицировать отправителя. Сходные средства могут применяться для предотвращения внесения каких-либо корректив в сообщение на пути от отправителя к получателю. Быстродействующие аппаратные 512-битовые модули могут обеспечить скорость шифрования на уровне 64 кбит в сек. Готовятся ИС, способные выполнять такие операции со скоростью 1 Мбайт/сек. Разумный выбор параметра e позволяет заметно ускорить реализацию алгоритма.

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

На приемной стороне процесс дешифрования возможен при условии, что известно число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x^(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой.

Возведем обе ее части в степень (-y) : (x^{(-y)(p-1)(q-1)})mod n = 1^(-y) = 1. Теперь умножим обе ее части на x : (x^{(-y)(p-1)(q-1)+1})mod n = 1 × x = x.

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e × d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e×d). Получаем (x^e×^d)mod n = x. То есть для того чтобы прочесть сообщение c_i=((m_i)^e)mod n достаточно возвести его в степень d по модулю m :

((c_i)^d)mod n = ((m_i)^e×^d)mod n = m_i.

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

Литература:

1. Ян С. Й. Криптоанализ RSA. — М.—Ижевск: НИЦ «Регулярная и хаотическая динамика», Ижевский институт компьютерных исследований, 2011. — 312 с.

2. Венбо Мао. Современная криптография. Теория и практика – Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. — 768 с.

3. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си – Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с.