Криптография, 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 mod 107

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


Современная криптография


01 02 03 04 05 06 07 08 09 10 11 12


Календарь

Октябрь
01 08 15 22 29
Ноябрь
05 12 19 26
Декабрь
03 10 17


Эта статья является конспектом лекции.
Личные инструменты
Разделы