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

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

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

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

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

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

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

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

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

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

Сколько всего будет корней у такого уравнения? 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

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.us/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F%2C_08_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_19_%D0%BE%D0%BA%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 123: / Строка 123: @@
 Итого получили -29 mod 97
-Осталось посчитать последний элемен 97^-1 mod 107
+Осталось посчитать последний элемен 97^-1 ьщв 107
 /107 = [1, 97/10] = [1, 9, 1, 2, 3]
 9  1  2  3
 1 1 10 11 32 107
-{{Криптография}}