Криптография, 08 лекция (от 19 октября)
Материал из eSyr's wiki.
(Новая: В прошлый раз познакомились с критерием Рабина, а в этот раз познакомимся с его криптосистемой. Может...) |
|||
| Строка 123: | Строка 123: | ||
Итого получили -29 mod 97 | Итого получили -29 mod 97 | ||
| - | Осталось посчитать последний элемен 97^-1 | + | Осталось посчитать последний элемен 97^-1 mod 107 |
97/107 = [1, 97/10] = [1, 9, 1, 2, 3] | 97/107 = [1, 97/10] = [1, 9, 1, 2, 3] | ||
1 9 1 2 3 | 1 9 1 2 3 | ||
0 1 1 10 11 32 107 | 0 1 1 10 11 32 107 | ||
| + | |||
| + | {{Криптография}} | ||
Текущая версия
В прошлый раз познакомились с критерием Рабина, а в этот раз познакомимся с его криптосистемой.
Можете увидеть, что закрытый ключ есть пара п и ку, а открытый -- их произведение. В рса дополнительно есть еще числа д и е, здесь ничего подобного нету. Есть два простых числа, есть их произведение, оно является открытым ключом.
Как происходит шифрование? шифрование есть возведение в квадрат.
Расшифрование -- решение квадратного уравнения.
Задача извлечения квадратного корня по модулю простого числа -- кандидат на одностороннюю функцию с секретом.
Доказано, что если суметь найти все корни такого уравнения, то это эквивалентно задачи факторизации.
В этом преимущество критериемы Рабины, у РСА это утверждение было только в одну сторону.
Сколько всего будет корней у такого уравнения? 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 |
