Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
239
Из следствия 6.2 видно, что число у (modp) имеет два разных квадратных корня, которые мы обозначим как хр и р—хр соответственно. Аналогично обозначим квадратные корни числа y(mod q) как xq и q — xq соответственно. Вследствие изоморфизма между группой Z* и пространством Z* х Z* (теорема 6.2) число у € QR„ имеет в группе Z* ровно четыре квадратных корня, которые можно вычислить с помощью алгоритма 6.5.
Х\ — \рхр \qxq х2 \рхр + lq(q - xq)
Х3 = 1р(р - Хр) + lgXq
x4 = lp(p-Xp) + lq(q-xq)
> (modn) (6.6.8)
Применяя формулу (6.6.8) на шаге 2 алгоритма 6.5, можно вычислить все четыре квадратных корня исходного числа.
В качестве упражнения поставим следующую задачу: сколько разных квадратных корней имеет число у € QR„, если п = pqr, где р, q и г — разные простые числа?
Итак, если известно разложение числа п на множители, существует эффективный алгоритм, позволяющий вычислить квадратные корни любого заданного числа из множества QR„. А что делать, если разложение числа п на множители неизвестно? На этот вопрос дает ответ третья часть следующей теоремы.
Теорема 6.17. Пусть п = pq, где числа р и q —разные нечетные простые числа и J/GQR„. Тогда четыре корня числа у, вычисленные по формуле (6.6.8), обладают следующими свойствами.
1. Все они отличаются друг от друга.
2. Х\ + х4 = х2 + хз = п.
3. gcd(a;i +х2, п) = gcd(x3 + X4, п) = q, gcd(a;i +х3, п) = gcd(a;2+Ж4, п) = р. Доказательство.
1. Учитывая смысл обозначений 1р и lq, определенных формулами (6.2.15) и (6.2.16), приходим к выводу, что, например, x\(modq) = xq и x2(modq) = = q — xq. Напомним, что xq и q — xq — два разных квадратных корня числа y(modq). Из условия rEi^a^modg) следует, что xi?x2(modn), т.е. числа х\ и х2 отличаются друг от друга. Другие варианты доказываются аналогично.
2. Из формулы (6.6.8) следует, что
х\ + х4 — х2 + х3 = 1рр + lqq.
240
Часть II. Математические основы
Правая часть этого уравнения сравнима с нулем по модулю р и по модулю q. Поскольку эти корни принадлежат группе Z*, выполняется условие 0 < х\ + х4 = х2 + з>з < 2п. Очевидно, что число п — единственное число в интервале (0,2п), сравнимое с нулем по модулю р и по модулю q. Следовательно, xi = п — х^ и х2 = п — х$.
3. Рассмотрим лишь число х\+х2. Другие варианты доказываются аналогично. Исследуя формулу (6.6.8), приходим к выводу, что
xi + x2 = 2- IpXp + lqq.
Следовательно, xi + ^(modp) = 2xp Ф 0 и x\ + x2 = O(modQ). Таким образом, число xx + x2 не равно нулю и кратно числу q, но не кратно числу р. Отсюда следует, что gcd(a;i + х2,п) = q. о
Допустим, что существует алгоритм А, получающий на вход число у € QR„ и вычисляющий число х, удовлетворяющее условию х2 = y(mod п). Следовательно, для вычисления квадратного корня х' числа х2 можно выполнить алгоритм А(х2,п). По теореме 6.17.3 вероятность события 0 < gcd(a; + х',п) < п равна 1 /2 (вероятностное пространство состоит из четырех квадратных корней числа у). Значит, алгоритм А эффективно выполняет факторизацию числа п.
Объединяя алгоритм 6.5 и теорему 6.17.3, получаем следующее утверждение.
Следствие 6.3. Пусть п — pq, где числа ри q —разные нечетные простые числа. Тогда факторизация числа п эквивалентна вычислению квадратного корня по модулю п. о
Из теоремы 6.17.2 и того факта, что число п — нечетное, вытекает следующее утверждение.
Следствие 6.4. Пусть п = pq, где числа р и q — разные нечетные простые числа. Тогда для любого числа у ? QR„ два квадратных корня числа у меньше п/2, а другие два корня — больше п/2. о
6.7 Целые числа Блюма
Целые числа Блюма широко применяются в криптографии с открытым ключом.
Определение 6.4 (Целые числа Блюма). Составное целое число п называется целым числом Блюма, если п =¦ pq, где ри q —разные простые числа, удовлетворяющие условию p = q = 3(mod 4).
Глава 6. Теория чисел
241
Целые числа Блюма обладают рядом интересных свойств. Некоторые из них оказались весьма полезными для криптографии с открытым ключом и криптографических протоколов.
Теорема 6.18. Пусть п — целое число Блюма. Тогда выполняются следующие условия.
1. (—- | == (— | = —1, следовательно, (—| = 1. \Р J \ Я J \п )
2. Для уЕЪ*п если (—^ = 1, то либо у € QR„, либо —у = п — уЕ QR„-
3. Любое число у Е QR„ имеет четыре квадратных корня и, —и, v и —v, удовлетворяющих следующим условиям. [ — | =1. [ — ) = 1, т.е. и Е QR„;
\pj \qJ
4. Функция f{x) = ж2 (mod п) является перестановкой над множеством QR„.
5. Для любого числа у Е QR„ существует только один квадратный корень, который меньше п/2, и символ Якоби которого равен единице.
6. Группа Z* разбивается на четыре класса эквивалентности: одну мультипликативную группу, QRji, и три смежных класса (—lJQR^^QR^ и (—?)QR„, где ? — квадратный корень единицы, символ Якоби которого равен —1.
Доказательство.
1. Из условия р = 3(mod4) следует, что р^ = 2k + 1. Тогда по критерию Эйлера (6.5.1) получаем
Аналогично
(тН-
= (-i)
2fe+l
-1.
2. Из условия (^) = 1 следует, что (?j = (^j — 1 или - = -1.
В первом случае у Е QR„ вследствие определения символа Лежандра (определение 6.3) и теоремы 6.14. Во втором случае из утверждения 1 следует,
