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

Наш первый кандидат на однонаправленную функцию с потайным ходом во многом похож на нашего второго кандидата на просто однонаправленную функцию. Это - модульное возведение в степень, но с фиксированной экспонентой и модулем. Пусть шип - целые числа, а Z„ определено так же, как ранее. Тогда модульное возведение в степень (относительно экспоненты ш и модуля п) есть функция дт,п-п п, определяемая следующим образом: дт,п{а) - mod п. Необходимо быть уверенным в понимании различия между функциями /а,„ и дт,п-Опять по аналогии с вещественным анализом, операция, обратная дт,п, известна как извлечение корня т-ой степени из х по модулю п: даны целые числа т, пи х, найти такое целое а (если оно существует), что а" mod п = х. Например, 5 - это корень 4-ой степени из 16 по модулю 21, потому что, как мы уже видели, 5 mod 21 = 16. Очевидно, что 2 также является корнем 4-ой степени из 16 по модулю 21. Можете ли Вы найти другие корни 4-ой степени из 16 по модулю 21? Найдите целое число х, которое не имеет корней 4-ой степени по модулю 21.

В том случае, когда экспонента т и модуль п фиксированы, мы уже приводили эффективный алгоритм вычисления дт,п(а) для любого основания а. В противоположность задаче дискретного логарифмирования, тем не менее известно, что существует также и эффективный алгоритм извлечения корня т-ой степени из X по модулю п (или выяснения, что такого корня нет) для любого заданного х. Любопытный феномен заключается в том, что мы не знаем, как эффективно построить этот эффективный алгоритм при заданных лишь га и п. Иными словами, известно, что функция gjn,n на самом деле является не однонаправленной, поскольку мы знаем, что она может быть эффективно обращена, но, несмотря на этот факт, не знаем, как это сделать! Тем не менее, легко построить эффективный алгоритм вычисления т-ого корня по модулю п при условии, что известно разложение п на простые множители. Именно по этой причине Qffin И является

S 1 Однояаправледные функции 47

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

Важным частным случаем модульного возведения в степень является тот, при котором экспонента равна 2, а модуль - число некоторого специального вида. Для понимания того, что это и есть еще один кандидат на однонаправленную функцию с потайным ходом, необходимы дополнительные сведения из теории чисел. Если рид - два ргьзличных больших простых числа примерно одинакового размера, и кроме того и р, и q сравнимы с 3 по модулю 4, то мы будем говорить, что их произведение п= p-q является целым числом Блюма. Определим Z* как множество целых чисел от 1 до п - 1, которые не делятся ни на р, ни на д. Наконец, определим QRn как подмножество множества Z*, состоящее из чисел, которые являются совершенными квадратами по модулю п. Элементы QRn известны как квадратичные вычеты по модулю п. В качестве небольшого примера положим р = 19, а g = 23, откуда имеем тг = 437 = 19 23. Тогда 135 является элементом , в то время как 133 - нет (поскольку 133 = 19-7). Более того, 135 не является квадратичным вычетом по модулю 437, так как не существует целого числа а, такого, что = 135 (mod 437), тогда как 139 является таковым, поскольку 242 = 576= 139 (mod 437).

Теперь сформулируем без доказательства несколько утверждений, необходимых для понимания всего дальнейшего изложения. Число элементов в равно (р - l){q - 1), причем в точности четвертую их часть составляют квадратичные вычеты. Каждый квадратичный вычет допускает ровно четыре ргьзлич-ных «квадратных корня» в , из которых лишь один единственный является квадратичным вычетом. Этот особый корень мы назовем примитивным (первообразным) квадратным корнем. В нашем примере 24 - это примитивный квадратный корень из 139 по модулю 437, другими тремя корнями являются числа 185, 252 и 413. Имеющий криптографическое значение факт заклкь чается в том, что способность определять примитивные квадратные корни по модулю такого числа п оказывается вычислительно эквивалентной умению раскладывать это п на множители.

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

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

Для более основополагаюших сведений по вычислительной теории чисел для криптографии мы отсылаем читателя к замечательной книге Евангелоса Кранакиса [244].

§ 2. Открытое распределение ключей

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

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