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

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

Рассмотрели Эль-Гамаля над конечными полями.

Можем обощить и рассматривать криптосистему не над циклической группой, порожденной конечным полем, а на прооизвольной циклической группе, надо только придумать, ака отобрадать одно в другое.

На сегодняшний день самыми рядовыми алгоритмами, но которые пока не везде имплементированы. Но во всех стандартах они уже есть, и в американских, и в российском стандарте цифровой подписи.

Сегодня такие планы:

* криптосистема эльгамаля
* квантовые вычисления, и что будет со всеми этими алгоритмами в постквантовую эру

[править] Эль-Гамаль

Используется интересный объект -- группа точек эллиптической кривой.

Понадобится аппарат аналичтичесой геометрии. Снова окунемся в мир эллиптиеских кривых.

Представьте, что есть произвольное конечное поле. Тогда над этим полем можно формально рассмотеть некую алгебраическую кривую.

Кривую над полем табуреток можно формально определить, но вот нарисовать её уже сложно.

Кривая над произвольным полем -- это геометрическое место точек, понятие, известное с школьной шеометрии.

Есть у нас некий однородный многочлен некоторой степени. Однородный многочлен -- каждый моном имеет одну и ту же степень.

Пример: F(x, y, z) = x^2 + y + z^2 неоднородный. А x^2 + xy + z^2 -- однородный.

Для чего мы рассматриваем именно однородные многочлены?

F(lx, ly, lz) = l^n * F(x,y,z)

Если мы рассматриваем алгебраическую кривую F(x,y,z) = 0, то если точка x,y,z лежит на этой кривой, то и любая точка, у которой координаты пропорциональны лежит на этой кривой. Все точки можно объединять в классы эквивалентности.

Для примера привел две алгебраических кривых. Первой степени ax+by+cz = 0. Второй степени...

На первом курсе вы изучали такие кривые над полем действительных чисел. Сначала изучали как классифицируются кривые первого порядка. И потом много времени посвятили классификации кривых порядка и определили некоторые их классы. Вы это делали не зря.

Любую алгебраическую кривую в проективных координатах можно всегда представить в афинных координатах. Фактически, рассмотреть некоторую проекцию.

Предположим, что z никогда не обращается в ноль. Тогда мы можем сделать замену, поделив все переменные на z. И тогда, вместо многочлена F(x,y,z) мы рассматриваем F(x/z, y/z, 1). Если мы возьмем пропорциональные точки, то в афинных координатах они будут абсолютно неразличимы.

Как называеются все точки. которые пропорциональны данной? Лучом? Правильно, пямой.

Геометрия в проективных координатах -- это геометрия чисел. В афинных координатах F(x,y) задана уже на прямых в проективных координатах. Есть тонкость с z=0, про которую чуть позже.

Как у нас преобразовываются вид кривых первого и второго порядка.

ax+by+c = 0 появляется неоднородность и свободный член.

Таким образом зачастую переход к афинным координатам нам помогает упростить вид кривой.

Единственная точка, на которой мы так не можем сделать z = 0.

После перехода в афинные координаты это точка называется бесконечно удаленной.

То есть, кривая отобрадатьжается в кривую + бесконечно удаленную точку. Которую мы не можем нарисовать, но про которую надо всегда помнить.

Если кривая была без разрывов, то тут мы получили разрыв.

Теперь несколько слов про классификацию кривых.

Как правило уравнения кривых можно упрощать.

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

В случае произвольного конечного поля тоже стоит задача, а как сделать так, чтобы ввести эквивалентность.

Полной аналогии в случае конечного поля тту сложно построить. Если перенос начала координат еще ладно, то с поворотом вообще неопнятно, потому что синус и косинус это действительные функции.

Номожно доказать, что если применить определенную замену координат ( на слайде), то можно разбить множество кривых на классы эквивалентности. Кривые эквивалентны если одну к другой можно привести этими заменами.

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

Можно рассматривать другие поля. например поля, порждаемое вычетами по некоторому простому модулю. F5 = {0,1,2,3,4}. Можно доказать, что нет полей характеристики 4, только 5 и 3.

Давайте рассматривать не поле вычиетов, а неокторое его расширение. Будем работать над веткорами, у которых эти координаты принадлежать полю F5.

Это будет булев куб с дополнительными операциями. Складывать двоичные векторы понятно как. Как умножать? Представить как многочлен и выполнять все операции как над многочленами.

Мы построили поле характеристики два, которое фактически является н-мерным пространством над полем из двух элементов. Также можно построить поля харакетристики пять и так далее.

Какова характеристика поля действительных чисел? Бесконечность.

Классификация очень сильно зависит от того, конечная характеристика или бесконечная. И еще будет зависеть от значения характеристикаи.

Если поля характеристики больше трех, то классификация будет одинаковая.

Любую кривую третьей степени над полями с характеристикой больше трех может быть представлена как y ^2 = x^3 + ax +b -- с этим работать гораздо проще, чем с общим видом кривой третьей степени с туевой хучей мономов. Это верно и если характеристика поля -- Бесконечность

Нас будет интересовать не абы какая кривая, а только хорошие.

Что такое хорошая кривая?

Что хорошего в эллипсе?

В матанализе больше всего любят дифференцировать. Если не знаешь что делать -- дифференцируй.

А в геометрии любят проводить касательные. Ко всему.

У эллипса в каждой точке можно провести касательную. Именно такие кривые нас и будут интересовать -- чтобы в каждой точке можно было провести касательную.

В каждой точке кривой можно провести касательную.

Здесь должен возникать следуюзий вопрос. Что такое касательная в поле табуеток? Надо использовать подход аналогий. Когда вы изучали численные методы, в них для того чтобы строить методы вычислений чего-нибудь, вы это приближаете какой-нибудь функцией и вычисляете эту функцию.

Так и тут, делаете по аналогии. Геометрия нам говорит, что каательной является прямая со следующим уравнением...

Касательной будет формальная прямя, удовлетворяющая соответствующему уравнению. Фактически это прямая, пересекающая нашу кривую ровно в одной точке.

Чтобы касательная существовала в каждой точке необходимо и достаточно чтобы все частные производные в этой точке не обращались одновременно в ноль.

Правда, мы берем производные берем в поле, где мы не умеем брать производные..

df(x,y)/dx = 3x^2 + a

df(x,y)/dy = -2y

Теперь нам надо, чтобы они одновременно не обращались в ноль.

4a^3 + 27b^2 не должно быть равно нулю. Это выражение называется дискриминантом кривой.

Подошли к основномму определению.

Эллиптической кривой называется кривая тертьей степени, на которой есть хотя бы одна точка и такая, что в каждой ее точке можно провести хотя бы одну касательную.

Чтобы работать дальше, надо чтобы наш объект превратился в алгебраический.

Надо сделать их точек эллиптической кривой группу.

И теперь то надо придумать, как нам из точек кривой сделать группу, объединить их единой операцией.

Здесь нам помогают следующие утверждения.

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

Если мы возьмем произвольную кривую и возьмем на ней две точки и проведем через них прямую. Уравнение прямой будет иметь следующий вид. Теперь мы не мудрствуя лукаво возьмем и попытаемся найти отсюда x,y и покажем, что найдется ровно одна точка, которая будет на этой прямой и на кривой. Подставим выражение х и у в уравнение кривой.

Получим кубическое уравнение относительно х. Любое уравение третьей степени имеет три корня. Два мы знаем. Третий можем найти по теореме Виета.

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

Как перенести идею криптосистемы ЭльГамаля?

Надо перенести исходное сообщение в точку эллиптической кривой.

Как мы будем погружать сообщение в точку эллиптической кривой.