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

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

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

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

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

.

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

Открытый ключ абонент публикует в сети, а параметры являются секретным (закрытым) ключом.

Когда один абонент хочет послать другому абоненту зашифрованное сообщение, но выполняет операцию . Для злоумышленника вычисление по и публичному ключу будет эквивалентно решению задачи об укладке рюкзака в общем случае. Легальный абонент, которому адресована криптограмма , применяя секретные параметры, решает задачу «об укладке рюкзака» в случае быстрорастущей последовательности».

Вначале абонент вычисляет

.

Таким образом, абонент просто умножает криптограмму на мультипликативное обратное , а затем решает задачу «об укладке рюкзака» в случае быстрорастущей последовательности и отыскивает . Алгоритм решения задачи «об укладке рюкзака» в случае быстрорастущей последовательности подробно описан в [2].

В 1982 году Ади Шамир открыл атаку, позволяющую эффективно решать задачу «об укладке рюкзака». Это оказалось началом падения криптосистем, основанных на задаче «об укладке рюкзака». Единственная, используемая в настоящее время и не раскрытая криптосистема, основанная на укладке рюкзака – криптосистема Бен-Цион Хора [2,7].

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

1. Дайте определение криптосистемы с открытым ключом.

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

3. Опишите алгоритмы шифрования и расшифрования основных типов криптосистем с открытым ключом.

4. Дайте сравнительную оценку криптосистем с открытым ключом.

5. В чем заключается различие и сходство криптосистемы Эль Гамаля и криптосистем на эллиптических кривых?

6. Назовите основные характеристики ассиметричных криптосистем.

Дата добавления: 2014-12-26