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

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

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

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

В 1976 году Уитфрид Диффи и Мартин Хеллман заложили основы нового направления в криптографии, предложив понятие шифрования с открытым ключом. Сходное понятие было независимо открыто Ральфом Мерклем.

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

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

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

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

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

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

Однако, если известно значение функции y = f(x), то нет простого пути для вычисления значения аргумента x.

Например, функция SIN. Зная x, легко найти значение SIN(x) (например, x = p - SIN(p) = 0).

Однако, если SIN(x)=0, однозначно определить х нельзя, т.к. в этом случае х может быть любым числом, определяемым по формуле i*p, где i – целое число.

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

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

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

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

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

1. Разложение больших чисел на простые множители (алгоритм RSA).

2. Вычисление дискретного логарифма или дискретное возведение в степень (алгоритм Диффи-Хелмана, схема Эль-Гамаля).

3. Задача об укладке рюкзака (ранца) (авторы Хелман и Меркл).

4. Вычисление корней алгебраических уравнений.

5. Использование конечных автоматов (автор Тао Ренжи).

6. Использование кодовых конструкций.

7. Использование свойств эллиптических кривых.

Алгоритм RSA. Был опубликован в 1978 году и получил свое название в честь авторов - Рональда Ривеста (R. Rivest), Ади Шамира (A. Shamir) и Леонарда Адльмана (L. Adleman). Стойкость RSA основывается на большой вычислительной сложности известных алгоритмов разложения произведения простых чисел на сомножители. Например, легко найти произведение двух простых чисел 7 и 13 даже в уме – 91.

Попробуйте в уме найти два простых числа, произведение которых равно 323 (числа 17 и 19). Конечно, для современной вычислительной техники найти два простых числа, произведение которых равно 323, не проблема.

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

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

Таблица 5