Глава 7. Криптосистемы с открытыми ключами

7.1. Односторонние функции с секретом и асимметричные системы

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

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

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

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

Главным понятием СОК является однонаправленная функция с секретом (one-way trapdoor function). Однонаправленную функцию с секретом : легко вычислить для всех , но очень трудно обратить почти для всех значений из . Однако, если используется некоторая секретная информация , то для всех значений легко вычислить величину, удовлетворяющую условию .

Криптосистемы с открытым ключом, использующие однонаправленные функции с секретом, еще называются асимметричными (asymmetric cryptosystems).

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

Эта функция была использована в широко распространенном криптографическом протоколе – протоколе обмена ключами Диффи-Хеллмана (Diffie-Hellman key exchange protocol).

Ранее, в 1974 году, Меркл (Merkle) изобрел механизм согласования криптографического ключа путем явных асимметричных вычислений, получивших название головоломка Меркла.

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

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

В последнее время стало известно, что первую криптосистему с открытым ключом разработал британский математик Кокс (Cocks) еще в 1973 году. Алгоритм Кокса, получивший название алгоритма с несекретным ключом шифрования, использовал сложность разложения целого числа на простые множители и, по существу, совпадал с криптосистемой RSA.

Первоначально алгоритм Кокса был засекречен и только в декабре 1997 года Группа по электронной защите средств связи (Communications Services Electronic Security Group – CESG) его рассекретила.

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

В настоящее время алгоритмы шифрования с открытым ключом получили широкое распространение в информационных системах.

Так, алгоритм RSA [1,16,18] фактически стал стандартом для открытых систем и рекомендован международной организацией по стандартизации ISO, соответствующие приложения лежат в основе электронной коммерции, осуществляемой через Internet.

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

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

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

Рис. 7.1. Криптосистема с открытым ключом

Таким образом, односторонняя функция с секретом, используемая в асимметричной системе, является взаимнооднозначной, но вместе с тем обладает свойствами необратимости.

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

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

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

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

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

– разложение больших чисел на простые множители;

– вычисление логарифма в конечном поле;

– нахождение кратности точки (дискретный логарифм) на эллиптической кривой;

– вычисление корней алгебраических уравнений над кольцами и полями.

Отметим, области применения СОК [4,6,7,12,20].

1. Средства шифрования передаваемых и хранимых данных.

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

3. Механизмы распределения ключей.

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

Наибольшее распространение получили системы с открытым ключом на основе алгоритма RSA, криптосистема Эль-Гамаля и криптосистемы на основе эллиптических кривых.