Теоретические основы криптосистем с открытым ключом

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

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

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

Алгоритмы шифрования с открытым ключом используют так называемые необратимые или односторонние функции. Эти функции обладают следующим свойством: при заданном значении аргумента х относительно просто вычислить значение функции f (x), однако, если известно значение функции y = f (x), то нет простого пути для вычисления значения аргумента x.

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

Криптосистема RSA

 

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

Алгоритм RSA работает следующим образом:

Пусть p и q - два больших различных простых числа, и пусть n = p × q и e некоторое целое, взаимно простое с (p -1)×(q -1).

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

Соответствующая ключу k функция шифрования E_k: M_k -> C_k определяется как E_k (m) = m ^e mod(n). Для того, чтобы полностью определить алгоритм ее вычисления, достаточно записать e и n в открытый справочник. Такая пара называется открытым ключом.

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

Эффективный алгоритм вычисления Dk легко получить, задав дополнительную секретную информацию p и q. С этой целью, используя обобщенные алгоритмы Евклида для нахождения наибольшего общего делителя, чтобы вычислить целое число d, такое что e × d = 1 mod ф (n), где ф (n) = (p -1)× (q -1) – функция Эйлера. По теореме Эйлера m ^(ed) = m mod(n) для любого целого числа m и, следовательно, (m ^e) ^d mod(n) = m, при условии что  0 <= m < n, что обеспечивается, когда m принадлежит M_k.

Функция дешифрования D_k: C_k -> M_k в связи с этим определяется как D_k (c) = с ^d mod(n), и эффективный алгоритм для модульного возведения в степень также может быть использован и для ее вычисления. Тогда каждый пользователь криптосистемы RSA должен выбрать целые числа p, q и e и вычислить с их помощью d. После чего он делает свой открытый ключ доступным в пользовательском справочнике, тогда как d сохраняет в секрете. Это дает возможность любому другому пользователю шифровать посылаемые ему сообщения, которые только он и может расшифровать. Для того чтобы эта идея была реализована практически, решающим является удовлетворение требование, чтобы генерация больших случайных простых чисел и вычисление d были легко осуществимы.

Например, пусть p = 19 и q = 23, тогда n = 437 и ф (n) = 396. Пусть также e = 13, и поэтому d = 61, так как 13×61 = 793 = 2 ф (n)+1. Тогда сообщение в открытом текcте m = 123 будет зашифровано как c = 123¹³ mod(437) = 386. Действительно, 386⁶¹ mod(437) = 123.

Если бы существовали эффективные методы разложения на сомножители (факторинга), то, разложив n на сомножители (факторы) p и q, можно было бы получить секретный (private) ключ d. Таким образом надежность криптосистемы RSA основана на трудноразрешимой задаче разложения n на сомножители (то есть на невозможности факторинга n) так как в настоящее время эффективного способа поиска сомножителей не существует.

 

4.1.2. Алгоритм шифрования и дешифрования RSA.

 

1. Выберем два больших простых p и q.

2. Определим n = p × q.

3. Выберем большое случайное число, которое назовем e. Это число должно быть взаимно простым с результатом (p -1)×(q -1).

4. Определим такое число d, для которого является истинным соотношение

(e × d) mod((p -1)×(q -1))=1.

5. Назовем открытым ключом числа e и n, а секретным ключом - числа d, p и q.

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

- разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа М (i)= 0,1,..., n -1;

- зашифровать текст, рассматриваемый как последовательность чисел M (i) по формуле:

         C (i) = (M (i)^e)mod n;                                                                         (4.1)        

    Чтобы расшифровать эти данные, используется секретный ключ { d, n } и выполняются следующие вычисления:

       M (i) = (C (i)^d) mod n.                                                                            (4.2)

    В результате получают исходный текст M (i).

 

Задание на лабораторную работу

 

1. Разработать программу, осуществляющую шифрование и дешифрование алгоритмом RSA.

2. Исходное открытое сообщение М должно состоять не менее, чем из 2 n символов. Допускается использование как русского, так и любого другого алфавита для написания исходного текста.

3. Зашифрованный текст оформить в виде самостоятельного файла.

4. В программе предусмотреть проверку, являются ли два числа взаимно простыми.

5. Результаты работы оформить в виде отчета.

6. Содержание отчета:

- описание используемого метода,

- описание исходных данных,

- алгоритм работы программы,

- текст программы,

- результаты работы программы,

- анализ результатов

- выводы.

 

4.3. Контрольные вопросы

 

1. Что такое однонаправленные функции?

2. Основные свойства однонаправленных функций с потайным ходом?

3. Какие криптоалгоритмы используют однонаправленные функции?

4. Как реализуется программное возведение в степень для больших чисел?

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Шаньгин В.Ф. Защита информации в компьютерных системах и сетях /В.Ф.Шаньгин. - М: ДМК, 2012.-593 с.

2. Введение в криптографию: новые математические дисциплины. Учебник/под ред. В.В.Ященко.- СПб: Питер, 2001.-287 с.

3. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях./ М.А. Иванов.- М.: Кудиц-образ, 2001.-363с.

4. Анин Б. Защита компьютерной информации./ Анин Б. - СПб,Киев,М.: БХВ-Петербург, 2000.- 368 с.

5. Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си./ Брюс Шнайер- М:Триумф, 2002. – 816 с.