Криптография, 08 лекция (от 19 октября)

Материал из eSyr's wiki.

В прошлый раз познакомились с критерием Рабина, а в этот раз познакомимся с его криптосистемой.

Можете увидеть, что закрытый ключ есть пара п и ку, а открытый -- их произведение. В рса дополнительно есть еще числа д и е, здесь ничего подобного нету. Есть два простых числа, есть их произведение, оно является открытым ключом.

Как происходит шифрование? шифрование есть возведение в квадрат.

Расшифрование -- решение квадратного уравнения.

Задача извлечения квадратного корня по модулю простого числа -- кандидат на одностороннюю функцию с секретом.

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

В этом преимущество критериемы Рабины, у РСА это утверждение было только в одну сторону.

Сколько всего будет корней у такого уравнения? 2 в какой-то степени. В какой? Почему больше двух.

Очевидно, что если м -- решение, то -м тоже решение. Надо сказать, что если н составное и имеет только два делителя, то уравнение будет иметь 4 решения. Если делителей будет три, то у уравнения будет 8 решений. Степень двойки задается количеством простых делителей числа н.

Решение квадратного уравнения. Делаем редукцию по модулям п и ку. Как устроено решение? Берем решение по ку, и умножаем на некоторую константу, зависящую от п и ку. Вторая часть решения строится так же. И соответственно плюс-минус, в итоге получим 4 решения.

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

Перейдем к решению

x^2 = a mod p

1. Выделим из p-1 максимальную степень двойки. Назовем. м.
 1. Если m = 1, то решение +-a^{(p+1)/4}.  p-1 = 2*(2k + 1) = 4k+3, то есть p = 4k+3. Простые числа такогов вида называются числами Блюма.
 1. Что делать если m > 1. Тут начинается некий треш. Алгоритм вероятностный, но в среднем он полиномиален. +-c^j*a^{(s+1)/2}. с зависит только от p, а вот j искать уже сложнее. (p - 1 = 2^m*s). Как же найти j?

Побитово. Биты решения j_t выражаются через \eps_t, которая выражается рекурсивно через некое h(a) и с, того самого, что мы ввели раньше. J_i это такая простая функция, которая принимает значение 1, если j_i = 0 и a, если j_i = 1. Теперь, что такое c. Так вот c это элемент b^s mod p. Но тут возникает вопрос что такое b. Это квадратичный невычет по модулю p. Число b называется квадратичным невычетом, если x^2 = b mod p не имеет решения. Понятно, что не из любого числа извлекается квадратный корень. Мы априори предполагаем, что из a он извлекается. А теперь еще нам оказывается нужен элемент, из которого он не извлекается. К сожалению, детерменированного алгоритма поиска невычета нет. Поэтому мы случайно выбираем элемент от 1 до p и проверям, имеет ли оно решение. Но как мы определеяем, если мы решать то не умеем? Но оказывается, что задача определения существования решения очень простая и решается за полиномиальное время.Как определить? Вычисляя такую интересную штуку, как символ лежандра. Обозначаетя дробью в скобках.

Не путайте,это не просто скобки, а символ лежандра. (b|p) . Он равен 0, если b делится на p, 1 если b mod p -- вычет, и -1 если невычет. символ лежандра = b^{(p-1)/2}, то есть вычисляется по простой формуле.

Но можно еще проше.

Алгоритм основан на следующих свойствах:

 1. (1/p) = 1 (а для -1 не всегда так). Если p это число Блюма, то -1 будет невычетом. Именно поэтому так легко все можно решить. 
 1. (-1/p) = (-1)^{(p-1)/2}
 1. Доказывается трудно, но весьма полезно (2/p) = (-1)^{(p^2-1)/8}
 1. Квадратичный закон взаимности. Оказвается (p/q) = (-1)^{(p-1)/2}{(q-1)/2}(q/p)
 1. (ab^2/p) = (a/p)
 1. мультипликативность (a_1 a_2/p) = (a_1/p)(a_2/p)

Давайте что-нибудь решим.

x^2 = 3 mod 97 * 107

В соответствии с редукцией должны решить два уравнения x^2 = 3 mod 97 и x^2 = 3 mod 107

Начнем с mod 107.

1. Выделим старшую степень двойки из p-1, 106 = 2*53. Это число Блюма, у нас простая формула. Первое решение

x_{107} = +-3 ^{(p+1/4)} mod p = +-3 ^{108/4} mod 107 = +- 3 ^{27} mod 107 = +-3^{16+8+2+1} mod 107 = +-89

Со второй частью так красиво не получится.

x^2 = 3 mod 97 

p-2 = 2^5*3.

Определили m = 5 и s = 3.

Теперь нам нужен невычет. Понятно, что b != 1. Проверим 2.

(2/97) = (-1)((97^2-1)/2) = 1

Проверим 3.

(3/97) = (-1)(97-1.2)(3-1/2) (97/3) = (1/3) = 1

Из 4 извлечения корень, она сразу не подходит.

Подойдет 5. Проверим это. (5/97) = (97/5) = (2/5) = (-1)^{4*6/8} = -1

Итак, вырисовался третий параметр нашего алгоритма, это b = 5.

Итак, дальше нам надо вычисить c = b^s mod p и h = a^s mod p

c = 5^3 mod 97 = 28

h = 3^3 mod 97 = 27 

Теперь мы должны вычислить h^2^r для всех r от 1 до l-1

H 0 1 2 3
  h^2^0 h^2^1 h^2^2 h^2^3
  27 50 75 96

В данном случае j0 = 1

Составим таблицу для с

0  1  2  3
28 8 64 22

Все готово, чтобы вычислять биты для j.

e1 = 75*22 mod 97 = 1  j_1 = 0
e2 = h1*c2 = 96 = -1 j_2 = 1
e3 = h0 c1 *  c3 = -1 

j = 1 + 2^2 + 2^3 = 13 

x = +-c
x = +- 28^13 * 3^2 mod 97 = 87

Нашли частные решения +-87 *107 (107 ^ -1 mod97) +- 89 * 97 * (97 ^ -1 mod 107)

Надо найти два чисоа.

10^{-1} mod 97

Применяем расширенный алгоритм Евклида.

97/10 = [9, 10/7] = [9,1, 7/3] = [9, 1, 2, 3]

   9 1  2  3
0 1 9 10 29 97

Итого получили -29 mod 97

Осталось посчитать последний элемен 97^-1 ьщв 107

97/107 = [1, 97/10] = [1, 9, 1, 2, 3]
   1 9  1  2  3 
0 1 1 10 11 32 107