Криптография, 09 лекция (от 26 октября)
Материал из eSyr's wiki.
Сегодня рассмотрим квадратичное решето, которое является базисом для многих современных методов факторизации.
Основан на идее Лежандра -- найти такие два квадрата, которые были бы сравнимы по модулю раскладываемого числа. В этом случае если повезет надо будет найти только НОД x+y или x-y и N.
Первая идея, как искать квадратичное сравнение -- похожа на идею Полларда.
Вторая идея -- попытаться строить соотношение из известных блоков. Есть несколько квадратичных сравнений. Что тогда мы моггли бы сделать? Предположим гипотетически, что произведение есть квадрат какого-то числа по модулю н. Перемножая эти соотношения пытаемся построить справа полный квадрат по модулю эн.
Есть соотношение
41^2 = 32 mod 1649 42^2 = 115 43^2 = 200
32*200 = 80^2
1649 = 17*97
Мы не взяли соотношение среднее. Мы для формирования нашего квадрата взяли те, которые делятся на маленькие простые числа. Возникает идея использовать справа только числа, делящиеся на маленькие простые числа. Граница малости называется Б и называется границей гладкости, является параметром алгоритма.
Если число имеет большой делитель, то чтобы оно давало квадрат он тоже должен иметь большой делитель. Поэтому еси мы такие исключим, то наша жизнь наладится.
Если мы знаем, что все правые части делятся только на простые исла не превосходящие б. то мы можем каждому такому числу сопоставить вектор степеней простых чисел. Длина этого вектора равна числу простых чисел, не превсходящих б.
Когда у нас б-гладкое число является полным квадратом? Когда степень в разложении является четной. Нас интересуют таки числа, у которых все компоненты вектора степеней -- четные. Значит, нач интеересует только остаток от деления компонент этого вектора на два.
Берем два б-гладких числа, перемножили их. Вектора при этом сложились.
Наша задача найти такой набор б-гладких чисел, что совокупность их веткоров линейно зависима.
Поиск набора линейноо зависимых векторов равносилен решению СЛАУ.
А как нам гарантировать наличие зависимой системы7
Все векторы принадлежат пространству \pi(b), пространство конечномерно. Любая система из векторов больше, чем размерность пространства будет линейно зависима. Вам достаточно рассмотреть в среднем расзмерность пространства + 1 вектор.
Сложность атаки O(e^sqrt(lnlnln n)). Борьба идет за константу, и это борьба включает весь курс современной алгебры. Происходит пееход в разные интересные алгебраические структуры, типа идеалов.
Криптосистема Эль-Гамаля.
В России имеется стандарт гост Р34-10-2001/2013 -- стандарт ЭЦП.
Достоинство криптосистемы Эль -Гамаля в том, что она не так как рса привязана к числам. Она позволяет переходить к тяжелым алгебраичесим объектам. Так вот, кто такой Эль-Гамаль? Египетский математик, провел десттво и молодость в Каире. Уехал в Стэнфорд, в котором знаменитый Мартин Хэлман был его научным руководителем. Он дал ему совместную с Диффи работу и попросил проанализироват и может чего-нибудь придумать.
Как устроена криптосистема Эль-Гамаля.
Рассмотрим элемент g, где g^q = g, где q -- простое ичисло. Оно называется порядком элемента.
g^(q-1) = 1 mod p, и можем составить ряд разлиных чисел.
Параметры криптосистемы p, g, q.
Каким образом генерировать ключи? Абонент генрирует случайное число x и вычисляет y = g^x mod p. Степень элемента x -- секретный ключ, а y - открытый ключ. Нет никакой работы по генерации простых чисел.
Как происходит шифрование?
c = m * y^k mod p \gamma = g^k mod p -- нужно чтобы дать понять пользователю, какое случайное к мы выбрали k -- случайное число Длин шифротекста в два раза больше, чем длина открытого текста. Поэтому говорят, что эль гамаль замедляет передачу в два раза.
Очень часто случается так, что криптосистемы замедляют канал. РСА одна из немногих, кто скорость передачи не замедляет. 1/2 это очень маленькая скорость. Есть криптоситемы у которых скорость передачи между 1 и 1/2, есть те у которых они близки к 1.
Расшифрование
m = c* \gamma^{-x}
На основе чего мы считаем, что криптосистема является стойкой?
По поводу задачи восстановления по шифротексту и открытому ключу открытого текста. Даны c, \gamma, y, надо найти m.
Вспомните, что такое с = m*g^{kx}, g^k, g^x следовательно надо имея g, g^k, g^x надо найти g^kx -- то есть задача поиска открытого текста полиомиально эквивалентна проблеме Диффи-Хеллмана.
Проблема Диффи-Хеллмана, так же как и вторая задача эквивалентна задаче дискретного логарифмирования.
Вторая проблема эквивалентна проблеме дискретного лоагрфифмироавния.
Эти проблемвы не эквивалентны, сводимость есть только в одну сторону.
Про эль гамаля мы не уверены, что ее нельзя взломать не решая задачу дискретного лоагрфмирования.
Методы дискретного лоагрифмирования
Давайте рассмотрим частный случай. Предположим, что у нас имеется простое число p, знаем что g это элемент порядка q, нам дано y и мы хотим найти x.
Предположим, что у нас частный случай, когда q-1 равно степени двойки. Например, это все простые числа ферма.
Простые ферма -- простые числа вида 2^2^n - 1.
Как же мы можем решить задачу дискретного логарифмирования для таких чисел? Раз степень x не может быть больше q-1, то можно попробовать представить х в двоичом виде и попытатьс ярешить задачу.
Давайте рассмотрим первый шаг алгоритма.
y = g^x
y^{(q-1)/2} = g^{x*(q-1)/2} = g^{x_0*(q-1)/2 + (q-1)*\~x} = g^{x_0*(q-1)/2}
Отсюда вывод, что x_0 = 0 если y^{(q-1)/2} = 1 и равно 1 в противном случае.
Нашли x_0. Как будем искать x_1.
Нужно каким то образом модифицировать y с учетом выясненного x_0. Как? надо просто его оттуда убрать.
y_1 = y*g^{-x_0}
Алгоритм Похлига-Хэллмана.
Сложность логарифмическая.
Что делать, если число q-1 не является степенью двойки, а явлется произведением простых чисел в каких-то степенях.
Ищем частные решения по отдельным взаимно простым модулям, и по китайской теореме об остатках ищем x.
Китайская теорема об остатках обощается на проивзольное количество соотношений, а не только на два, как давалось ранее.
Чтобы полностью описать метод, надо описать, как находить корень. Мы разобрались, когда р = 2, теперь разберемся со случаем. когда р любое число.
Та же аналогия. Опять мы ищем решение в битовом виде, но биты будут не двоичные, а р-ичные. Далее почти дословно повторяем выкладки, но там возникает тонкость.
y^{(q-1)/r} = g^{x_0 (q-1)/r}
х_0 идентифицируем, перебирая по таблице, потому что все числа соответствующие различным х_0 будут различны.
Эти числы называются корнями из единицы степени р.
Где же появляется экспонента? Когда вы будете раскладывать q-1 на множители. Если же все делители q-1 будут меньше либо равны б, где б это либо полином, либо константа. то сложность будет полином.
Это к выбору простых чисел. Мы должны брать такие простые числа, чтобы у ку-1 были большие простые делители. Такое же требовнаие как в рса. Но, в отличие от рса здесь нам не нужно рекурсивности этого требования. Это упрощает генерацию простых чисел.
Можно ли предложить субэкспоненциальный алгоритм дискретного логарифмирования?
Оказывается, метод квадратичного решета для дискретного логарифмирования и получить слово в слово повторяющийся метод для дискретного лоагрифмирвоания.
Получается. никакого выигрыша кроме удобной генерации ключей нет, если мы говорим про группу из чисел.
Зато она может быть обощена на группу точек жллиптических кривых. Это мы рассмотрим в следующий раз.
