Современная прикладная криптография (стр. 17 )

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

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

- пространство открытых текстов ;

- пространство шифрованных текстов ;

- пространство секретных ключей ;

- множество преобразований зашифрования ,

, где ;

- множество преобразований расшифрования .

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

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

2. По каждому выбранному легко найти пару обратимых преобразований и .

3. Для всех ,, величины и легко вычисляются (в полиномиальное время).

4. Для почти всех вычислительно невозможно из вывести какое-либо легко вычисляемое преобразование, эквивалентное преобразованию .

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

Так как злоумышленник имеет доступ к преобразованию зашифрования , то он может всегда выбрать любой открытый текст и получить соответствующий ему шифрованный текст. Поэтому криптосистемы с открытым ключом должны быть всегда устойчивы к методам по выбранному открытому тексту (chosen-plaintext attacks).

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

В ряде учебников по криптографии [24] секретное преобразование называют секретным ключом (private key), a открытое преобразования - открытым ключом (public key), а сами системы называют также двухключевыми криптосистемами (two key cryptosystem). Другим синонимом этих систем является понятие асимметричной криптосистемы (asymmetric cryptosystem), в то время как обычные криптосистемы с секретным ключом называются симметричными (symmetric cryptosystem).

Криптосистемы с открытым ключом обеспечивают только практическую стойкость.

Интересно, что авторы идеи и понятия о системах открытого шифрования не смогли сразу предложить такую систему для реализации (в отличие от схемы открытого распределения ключей). Первыми из таких систем являются ранцевая криптосистема Меркля-Хеллмана [24] и криптосистема Райвеста-Шамира-Адлемана (RSA) [9].

2.6. Криптосистема RSA

Название криптосистемы образовано от первых букв фамилий предложивших ее авторов (Rivest Н., Shamir A., Adleman L.) [9].

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

,

где (е, n) - ключ преобразования зашифрования.

При расшифровании блок открытого текста M восстанавливается также экспоненцированием, но с другой степенью d в качестве ключа расшифрования

Зашифрование и расшифрование могут быть выполнены с использованием быстрых алгоритмов экспоненцирования не более чем за операций.

В основе приводимых выше преобразований лежит теорема Эйлера (Euler), согласно которой для каждого числа M, взаимно простого с модулем n, выполнено соотношение , где - функция Эйлера, то есть число целых положительных чисел, не превосходящих n и взаимно простых с n.

Теорема. Если числа e и d удовлетворяют соотношению , a взаимно просто с n, то . (Это и означает, что d(e(m)) = M.)

Действительно, . Условие означает, что для некоторого целого t. Таким образом,

, где .

Значит, .

(Можно показать, что для n=pq (произведение простых чисел) соотношение также верно для любого М).

При наличии можно легко найти пару чисел е и d удовлетворяющих соотношению . Для этого выбирается число е взаимно простое с , что проверяется с помощью алгоритма Евклида. Взаимная простота нужна для разрешимости сравнения относительно неизвестного х. Число d находится с помощью расширенного алгоритма Евклида, определяющего числа d и t, удовлетворяющих соотношению ed+t fi(n)= 1, которое и означает, что . Сложность алгоритма Евклида не превосходит 0(log n)^3 операций.