Ассимметричные криптосистемы

Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифровки сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

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

1. Если известно x, то f(x) вычислить относительно просто

2. Если известно y=f(x), то для вычисления x нет простого (эффективного) пути.

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

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

Пусть K — пространство ключей, а e и d — ключи шифрования и расшифрования соответственно. E_e — функция шифрования для произвольного ключа , такая что . Здесь , где C — пространство шифротекстов, а , где M — пространство сообщений. D_d — функция расшифрования, с помощью которой можно найти исходное сообщение m, зная шифротекст c: . — набор шифрования, а — соответствующий набор для расшифрования. Каждая пара (E,D) имеет свойство: зная E_e, невозможно решить уравнение , то есть для данного произвольного шифротекста , невозможно найти сообщение . Это значит, что по данному невозможно определить соответствующий ключ расшифрования d.

Ниже показана схема передачи информации лицом А лицу В (рис.).

1. B выбирает пару (e,d) и шлёт ключ шифрования e (открытый ключ) А по открытому каналу, а ключ расшифрования d (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу).

2. Чтобы послать сообщение m B, А применяет функцию шифрования, определённую открытым ключом , c — полученный шифротекст.

3. B расшифровывает шифротекст с, применяя обратное преобразование D_d, однозначно определённое значением d.

 

Рисунок 2.16 - Криптосистема с открытым и закрытым ключами

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

RSA -ключи генерируются следующим образом:

1. Выбираются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое).

2. Вычисляется их произведение , которое называется модулем.

3. Вычисляется значение функции Эйлера от числа n: .

4. Выбирается целое число , взаимно простое со значением функции . Обычно в качестве e берут простые числа, содержащие небольшое количество единичных битов в двоичной записи, например, простые числа Ферма 17, 257 или 65537.

· Число e называется открытой экспонентой.

· Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в e.

· Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.

5. Вычисляется число d, мультипликативно обратное к числу e по модулю , то есть число, удовлетворяющее условию: или , где k — некоторое целое число.

· Число d называется секретной экспонентой.

· Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

6. Пара e, n публикуется в качестве открытого ключа RSA.

7. Пара d, n играет роль секретного ключа RSA и держится в секрете.