Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
46 Системы с открытым ключом
Глава 4
тивный алгоритм вычисления f известен, то никакое, пусть самое полное, описание его работы не должно давать возможности построить эффективный алгоритм вычисления /-1. Секрет, с помощью которого, тем не менее, можно эффективно вычислить функцию /-1, как раз и называется потайным ходом, или лазейкой для функции f.
Наш первый кандидат на однонаправленную функцию с потайным ходом во многом похож на нашего второго кандидата на просто однонаправленную функцию. Это — модульное возведение в степень, но с фиксированной экспонентой и модулем. Пусть тип — целые числа, а Жп определено так же, как ранее. Тогда модульное возведение в степень (относительно экспоненты т и модуля п) есть функция jra „: Жп —>¦ Жп, определяемая следующим образом: gm,n{a) = ят mod п. Необходимо быть уверенным в понимании различия между функциями /0]П и дт,п-Опять по аналогии с вещественным анализом, операция, обратная дт,п, известна как извлечение корня т-ой степени из х по модулю п: даны целые числа т, п и х, найти такое целое а (если оно существует), что ат mod п = х. Например, 5 — это корень 4-ой степени из 16 по модулю 21, потому что, как мы уже видели, 54 mod 21 = 16. Очевидно, что 2 также является корнем
4-ой степени из 16 по модулю 21. Можете ли Вы найти другие корни 4-ой степени из 16 по модулю 21? Найдите целое число х, которое не имеет корней 4-ой степени по модулю 21.
В том случае, когда экспонента т и модуль п фиксированы, мы уже приводили эффективный алгоритм вычисления дт,п{а) для любого основания а. В противоположность задаче дискретного логарифмирования, тем не менее известно, что существует также и эффективный алгоритм извлечения корня m-ой степени из х по модулю п (или выяснения, что такого корня нет) для любого заданного х. Любопытный феномен заключается в том, что мы не знаем, как эффективно построить этот эффективный алгоритм при заданных лишь тип. Иными словами, известно, что функция дт,п на самом деле является не однонаправленной, поскольку мы знаем, что она может быть эффективно обращена, но, несмотря на этот факт, не знаем, как это сделать! Тем не менее, легко построить эффективный алгоритм вычисления т-ого корня по модулю п при условии, что известно разложение п на простые множители. Именно по этой причине gm<n и является
Однонаправленные функции 47
кандидатом на однонаправленную функцию с потайным ходом, для которой шип используются как Открытая информация, тогда как разложение служит в качестве секретного потайного хода. Мы еще увидим, каким образом это может быть использовано, когда будем изучать знаменитую криптосистему RSA (см. § 4).
Важным частным случаем модульного возведения в степень является тот, при котором экспонента равна 2, а модуль — число некоторого специального вида. Для понимания того, что это и есть еще один кандидат на однонаправленную функцию с потайным ходом, необходимы дополнительные сведения из теории чисел. Если ри q — два различных больших простых числа примерно одинакового размера, и кроме того и р, и q сравнимы с 3 по модулю 4, то мы будем говорить, что их произведение п = p-q является целым числом Блюма. Определим Ж*п как множество целых чисел от 1 до п — 1, которые не делятся ни на р, ни на д. Наконец, определим QRn как подмножество множества Ж*п, состоящее из чисел, которые являются совершенными квадратами по модулю п. Элементы QRn известны как квадратичные вычеты по модулю п. В качестве небольшого примера положим р = 19, a q — 23, откуда имеем п — 437 = 19 • 23. Тогда 135 является элементом .Z*, в то время как 133 — нет (поскольку 133 = 19-7). Более того, 135 не является квадратичным вычетом по модулю 437, так как не существует целого числа а, такого, что а2 = 135 (mod 437), тогда как 139 является таковым, поскольку 242 = 576 = 139 (mod 437).
Теперь сформулируем без доказательства несколько утверждений, необходимых для понимания всего дальнейшего изложения. Число элементов в Ж*п равно (р — l)(g — 1), причем в точности четвертую их часть составляют квадратичные вычеты. Каждый квадратичный вычет допускает ровно четыре различных «квадратных корня» в .Z* , из которых лишь один единственный является квадратичным вычетом. Этот особый корень мы назовем примитивным (первообразным) квадратным корнем. В нашем примере 24 — это примитивный квадратный корень из 139 по модулю 437, другими тремя корнями являются числа 185, 252 и 413. Имеющий криптографическое значение факт заключается в том, что способность определять примитивные квадратные корни по модулю такого числа п оказывается вычислительно эквивалентной умению раскладывать это п на множители.
48 Системы с открытым ключом
Глава 4
Иначе говоря, тот, кто знает разложение п на множители, может эффективно вычислять и примитивные квадратные корни по модулю п, тогда как такие вычисления столь же трудны, сколь и факторизация п, для того, кто сомножителей п не знает.
Теперь наш второй кандидат на однонаправленную функцию с потайным ходом совершенно очевиден. Вы случайно выбираете р и q и вычисляете п = р ¦ q, которое открыто объявляете. После этого любой человек может эффективно возводить в квадрат по модулю п, но только ваш друг сможет эффективно произвести обратные вычисления (в предположении, что факторизация трудна). Открытой информацией здесь является число щ а секретным потайным ходом, опять таки, служит его разложение на множители.
