А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

(1+4t₁)²≡1(mod 16)

1+8t₁+16t₁²≡1(mod 16)

8t₁≡0 (mod 16)

t₁≡0 (mod 2)

Тогда решение примет вид x=±(1+4t₁)=±(1+4(0+2t₂))=±(1+8t₂). Подставим получившееся решение в сравнение по модулю 32:

x²≡33(mod 32)

(1+8t₂)²≡1(mod 32)

1+16t₂+64t₂²≡1(mod 32)

16t₂≡0 (mod 32)

t₂≡0 (mod 2)

Тогда решение примет вид x=±(1+8t₂) =±(1+8(0+2t₃)) =±(1+16t₃). Подставим получившееся решение в сравнение по модулю 64:

x²≡33(mod 64)

(1+16t₃)²≡33(mod 64)

1+32t₃+256t₃²≡33(mod 64)

32t₃≡32 (mod 64)

t₃≡1 (mod 2)

Тогда решение примет вид x=±(1+16t₃) =±(1+16(1+2t₄)) =±(17+32t₄). Итак, по модулю 64 исходное сравнение имеет четыре решения: x≡±17(mod 64) и x≡±49(mod 64).

Теперь рассмотрим сравнение общего вида: x²≡a(mod m), (a,m)=1, - каноническое разложение модуля m. Согласно Теореме из п.4 §4, данному сравнению равносильна система

Если каждое сравнение этой системы разрешимо, то разрешима и вся система. Найдя решение каждого сравнения этой системы, мы получим систему сравнений первой степени, решив которую по китайской теореме об остатках, получим решение исходного сравнения. При этом количество различных решений исходного сравнения (если оно разрешимо) есть 2^k, если α=1, 2^k+1, если α=2, 2^k+2, если α≥3.

Пример:

Решить сравнение x²≡4(mod 21).

21 – составное число. Факторизуем его: 21=3·7. Проверим разрешимость исходного сравнения:

, . Сравнение разрешимо и имеет 2²=4 решения.

Составим систему: . Решим каждое из уравнений этой системы. Получим . Итак, имеем 4 системы:

1) 2) 3) 4)

Решая каждую из этих систем по китайской теореме об остатках, получим четыре решения: x≡±2(mod 21), x≡±5(mod 21).

5.6. Тест на простоту Миллера-Рабина.

Теперь, наконец, мы располагаем достаточной информацией для того, чтобы привести тест Миллера-Рабина. Этот тест, как и тесты Ферма и Соловея-Штрассена, строит вероятно простые числа, то есть число, опознанное этим тестом как простое, может с некоторой малой вероятностью оказаться составным, однако вероятность ошибки у теста Миллера-Рабина гораздо ниже, чем у первых двух тестов. Как правило, для опознания простого числа достаточно одной итерации теста, но все же рекомендуемое количество итераций – пять.

Тест Миллера-Рабина основан на двух важных фактах:

1) Согласно теореме Ферма, если n – простое число, то для любого a: 0<a<n выполняется a^n—1≡1(mod n);

2) Если n – простое число, то сравнение x²≡1(mod n) имеет только тривиальные корни x≡±1(mod n), а если n – составное, то такое сравнение имеет несколько корней помимо тривиальных.

Тест Миллера-Рабина:

Вход: n=2^sr+1 – нечетное число, проверяемое на простоту, s≥0, r – нечетное.

t - количество итераций, параметр надежности.

1. Повторить t раз следующие шаги:

1.1. Случайным образом выбрать a: 1<a<n—1.

1.2. Строим последовательность b₀, b₁,…,b_s, где b_j= mod n, j=0,1,…,s.

1.3. Если в построенной последовательности не встретилась «1», то идти на Выход с сообщением «n - составное число».

1.4. Если перед первой единицей в последовательности стоит не «-1», то идти на Выход с сообщением «n - составное число».

2. Идти на Выход с сообщением «n – простое число с вероятностью ε^t ».

Выход.

Обратим внимание на то, что в последовательности b₀, b₁,…,b_s каждый последующий член является квадратом предыдущего по модулю n, а последний член есть ни что иное как a^n—1 mod n.

Вероятность ошибки ε ≤ φ(n)/4n, то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма.

Пример 1.

n=65=64+1=2⁶+1. r=1, s=6.

t=5.

1. 1-я итерация:

1.1. a=8.

1.2. Составляем последовательность: 8, 64=—1, 1, 1, 1, 1.

1.3. В последовательности встретилась «1».

1.4. Перед первой единицей стоит —1.

1. 2-я итерация:

1.1. a=11.

1.2. Составляем последовательность: 11, 56, 16, 61, 16, 61.

1.3. В последовательности не встретилась «1».

Выход: « n - составное число».

В том случае, когда тест Миллера-Рабина определяет составность числа n на шаге 1.4, появляется возможность частично факторизовать n.

Действительно, пусть в последовательности b₀, b₁,…,b_s, где b_j= mod n, нашлось такое i, что b_i≠±1, b_i+1=1. Обозначим для краткости b_i=b. Тогда b_i+1=b²≡1(mod n). Тогда n\(b²—1) n\(b+1)(b—1). Но в силу того, что b ±1(mod n), n не делит (b+1), n не делит (b—1). Следовательно,

1<НОД(n, b—1)<n, 1<НОД(n, b+1)<n.

Значит, НОД(n,b—1) и НОД(n,b+1) являются нетривиальными делителями числа n.

Пример 2

n=161=160+1=2⁵·5+1. r=5, s=5.

1. 1-я итерация:

1.1. a=22. a⁵ mod 161 = 22⁵ mod 161=22.

1.2. Составляем последовательность: 22, 1, 1, 1, 1, 1.

1.3. В последовательности встретилась «1».

1.4. Перед первой единицей стоит 22.

Выход: « n - составное число».

Факторизуем 161: b=22. b+1=23, b—1=21.

Вычислим НОД(161, 23): 161=23·7+0.

НОД(161,21): 161=21·7+14

21=14·1+7

14=7·2+0.

Итак, нашли два нетривиальных делителя 161, и получили 161=23·7.

Надо заметить, что на самом деле случай, когда в тесте Миллера-Рабина возникает возможность факторизации, происходит весьма редко. Гораздо чаще сообщение о составности мы получаем на шаге 1.3.

5.7. Связь задач извлечения квадратных корней и факторизации по модулю RSA. Криптосистема Рабина.

Пусть дано сравнение x²≡a(mod pq), p, q – различные большие простые числа. Как следует из предыдущего пункта, решение данного сравнения можно найти, решив систему , при этом необходимым условием существования решения является . В том случае, если решения существуют, исходное сравнение имеет четыре различных решения: x≡±x₁(mod pq), x≡±x₂(mod pq)

Утверждение.

Для модуля RSA (n=pq, p, q – различные большие простые числа) задачи факторизации и извлечения квадратных корней вычислительно эквивалентны.

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

Доказательство:

1) Действительно, если умеем факторизовать модуль, то сможем извлечь квадратные корни по этому модулю (разложив исходное сравнение в систему и решив ее за полиномиальное время).

2) Если же разложения модуля RSA на простые сомножители неизвестно, но известны 4 различных решения сравнения x²≡a(mod n), и эти решения суть ±x(mod n), ±y(mod n). Выберем пару чисел x, y. Заметим, что x²≡y²(mod pq), x ±y(mod pq).

x²≡y²(mod pq) x²—y² =(x+y)(x—y)≡0 (mod pq), причем x+y 0(mod pq),

x—y 0(mod pq). То есть pq\(x+y)(x—y), но pq не делит x+y, pq не делит x—y. Пользуясь основным свойствам простых чисел а также в силу равноправия сомножителей p и q, заключаем, что p\(x+y), q\(x—y), и тогда

p=НОД(x+y, n)

q=НОД(x—y, n).

Вычисление наибольшего общего делителя осуществляется при помощи полиномиального алгоритма – алгоритма Евклида.

□

Доказуемо стойкая криптосистема Рабина.

Криптосистема Рабина является асимметричной системой. Ее параметрами являются n=pq, p, q – различные большие простые числа. В качестве открытого ключа (ключа шифрования) выступает k₁=n, в качестве секретного ключа (ключа расшифрования) – k₂=(p,q).

Открытый текст x≠0 возводится в квадрат по модулю n, и получается криптограмма y=x² mod n. Для расшифрования последней требуется вычислить квадратный корень из y по модулю n. При решении сравнения y≡x² (mod n) возникнет четыре различных корня. Для того чтобы получатель мог выбирать нужный корень, в открытый текст x до шифрования вносится избыточность – участок текста определенного вида.

Для дешифрования криптограммы, то есть для вычисления x по y в отсутствие закрытого ключа требуется извлечь квадратный корень по составному модулю, не зная его разложения на простые сомножители.

Криптосистема называется доказуемо стойкой, если для нее доказана невозможность дешифрования без решения вычислительно трудной задачи. В силу доказанной вычислительной эквивалентности задач факторизации и извлечения квадратных корней, задача извлечения квадратных корней так же сложна, как задача факторизации, а последняя считается вычислительно сложной задачей. Поэтому криптосистема Рабина – доказуемо стойкая.

5.8. Квадраты и псевдоквадраты.

Пусть n – модуль RSA, то есть n=pq, p, q – различные большие простые числа.

Возьмем произвольное число a: (a,n)=1. Возможны следующие случаи:

1) . Тогда число a является квадратичным вычетом, или квадратом, по модулю n.

2) , , или , . Тогда , и a не является квадратом по модулю n. То есть, не зная разложения модуля RSA на простые сомножители и получив отрицательное значение символа Якоби, можем с определенностью сказать, что a – не квадрат по модулю n.

3) , тогда a не является квадратом по модулю n, но символ Якоби, как и для квадрата по модулю n, равен единице: . То есть, не зная разложения модуля n на простые сомножители и получив положительное значение символа Якоби, не можем наверняка определить, является ли a квадратом по модулю n. Числа a: называются псевдоквадратами по модулю n=pq. Множество псевдоквадратов по модулю n обозначается .

Утверждение (о мощности множеств квадратов и псевдоквадратов по модулю RSA).

n=pq, p, q – различные простые числа |Q(n)|=| |=φ(n)/4.

Характеристики

Список файлов книги