Криптоалгоритмы с открытым ключом

 

Суть криптографических алгоритмов с открытым ключом заключается в том, что адресатом генерируются два ключа, связанные между собой по определенному правилу. Один ключ объявляется открытым, а другой –секретным. Открытый ключ доступен любому, кто желает послать сообщение адресату. Секретный ключ сохраняется в тайне. Исходное сообщение шифруется открытым ключом адресата и передается ему. Дешифрование сообщения возможно только с использованием закрытого ключа, который известен только самому адресату [5, 6].

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

Стойкость криптосистемы RSA базируется на сложности задачи факторизации больших чисел, а стойкость алгоритма Эль-Гамаля – на сложности задачи логарифмирования в конечных полях [5].

Криптографические алгоритмы с открытым ключом в современных информационных системах используются в качестве средства:

1 Защита передаваемых и хранимых данных.

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

3 Аутентификация пользователей.

Среди недостатков криптографических алгоритмов с открытым ключом следует упомянуть:

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

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

3 Увеличение размера ключа приводит к усложнению аппаратной реализации криптографической системы.

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

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

Получатель:

1 Выбирает два различных простых числа p и q примерно одной размерности (100 – 150 знаков) и вычисляет их произведение:

 

n = p ∙ q.                                              (3.9)

 

2 Определяет функцию Эйлера от произведения (количество пар взаимно простых чисел, меньших n) по формуле:

 

φ(n) = (p−1)·(q−1).                              (3.10)

 

3 Выбирает случайное число K_O, которое будет открытым ключом и отвечает следующим условиям:

 

1 < K_O ≤ φ(n) и НОД(K_O, φ(n)) = 1.                                 (3.11)

4 Определяет секретный ключ, который является обратным величине открытого ключа по модулю φ(n):

 

K_C = (K_O⁻¹) mod φ(n).                      (3.12)

 

Для решения этого уравнения используют алгоритм Евклида:

‑– вводим два вектора:

j(n)) и (1,0,К_О);

– заполняем таблицу, приведенную ниже:

 

i	gi	u1	u2	u3	v1	v2	v3
–	–	0	1	φ(n)	1	0	KO
1	int(φ(n)/KO)	1	0	KO	−g	1	1−g·KO
…	…	…	…	…	…	…	…
…	…	KC	…	1

 

где , т.е. целая часть от деления координаты u_3,i-1 на v_3,i-1.

;

.

 

Вычисления производятся до тех пор, пока не получим u_3,i равным 1, тогда секретный ключ К_С = u_1,i. В случае отрицательного значение К_С берется его вычет по φ ( n).

 

5 Высылает отправителю открытый ключ К_О для шифрования.

 

Отправитель:

 

Зашифровывает сообщение M с помощью открытого ключа К_О отправителя по формуле:

 

                                    (3.13)

 

Получатель:

 

Расшифровывает сообщение с помощью секретного ключа К_С по формуле:

 

                                    (3.16)

 

Важная проблема практической реализации RSA – генерация больших простых чисел. Решение задачи «в лоб» – генерация случайного большого числа n (нечетного) и пpовеpка его делимости на множители от 3 вплоть до [‡]. В случае неуспеха следует взять n+2 и так далее.

В принципе, в качестве p и q можно использовать «почти» простые числа, то есть числа, для которых вероятность того, что они пpостые, стремится к 1. Но в случае, если использовано составное число, а не пpостое, кpиптостойкость RSA падает. Имеются неплохие алгоpитмы, котоpые позволяют генеpиpовать «почти» пpостые числа с уpовнем довеpия 2^-100 [6].