Атаки на криптосистемы, основанные на сложности задачи дискретного логарифмирования.

Очевидное направление криптоанализа систем шифрования и цифровой подписи, основанных на сложности решения задачи дискретного логарифмирования – разработка переспективных методов дискретного логарифмирования.

Наиболее известные методы дискретного логарифмирования:

1. Алгоритм согласования.

2. Алгоритм Полига-Хеллмана.

3. δ-метод Полларда для дискретного логарифмирования.

4. Дискретное логарифмирование в простых полях (алгоритмы Адлемана, COS.)

5. Дискретное логарифмирование в полях Галуа (алгоритмы index-calculus, Эль-Гамаля, Копперсмита).

6. Алгоритмы решета числового поля для дискретного логарифмирования.

Рекорды дискретного логарифмирования: логарифмирование по простому модулю (алгоритм COS с гауссовыми целыми). Сложность 60 MIPS-лет для нахождения соотношений и около трех недель – решение системы линейных уравнений.

Криптоанализ рюкзачных систем.

Доказано, что существует алгоритм полиномиальной сложности получения открытого текста по шифртексту на основе так называемой «косозубой функции». Алгоритм известен под названием LLL (Ленстры-Ленстры-Ловаша).

 

Перспективные направления в криптографии

Эллиптические кривые.

Проективная плоскость P²(K) над полем K определяется как множество троек (X, Y, Z) не равных одновременно нулю элементов X, Y, Z Î K, на котором введено отношение эквивалентности:

(X, Y, Z) ~ (lX, lY, lZ) для любых l Î K ^*.

Так, например, две точки (4, 1, 1) и (5, 3, 3) эквивалентны в P²(F ₇).

Класс эквивалентности троек называется проективной точкой.

Эллиптической кривой E называется множество точек проективной плоскости, удовлетворяющих однородному уравнению Вейерштрасса

E: F (X, Y, Z) = – X ³ + Y ² Z + a ₁ XYZ – a ₂ X ² Z + a ₃ YZ ² – a ₄ XZ ² – a ₆ Z ³ = 0,

c a_i Î K.

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

Множество K-рациональных точек кривой E (то есть точек, удовлетворяющих уравнению кривой) обозначается через E (K).

Кривая имеет только одну точку, чья координата Z = 0, а именно (0, 1, 0). Ее принято называть бесконечно удаленной точкой (или точкой на бесконечности) и обозначать символом O.Для удобства часто пользуются аффинной версией уравнения Вейерштрасса:

E: Y ² + a ₁ XY + a ₃ Y = X ³ + a ₂ X ² + a ₄ X + a ₆, c a_i Î K.

K-рациональные точки в аффинном случае – это решения уравнения в K ² и бесконечно удаленная точка O.

Переход от аффинных к проективным координатам:

- точка на бесконечности всегда переходит в бесконечно удаленную точку, как при переходе от аффинных координат к проективным, так и наоборот;

- проективная точка (X, Y, Z) кривой, отличная от бесконечно удаленной (Z ¹ 0), переходит в аффинную точку с координатами (X/Z, Y/Z);

- чтобы найти проективные координаты аффинной точки (X, Y), не лежащей на бесконечности, достаточно выбрать произвольное значение Z Î K ^* и вычислить (X·Z, Y·Z, Z).

Иногда удобнее пользоваться модифицированной формой проективной плоскости, когда проективные координаты (X, Y, Z) представляют аффинную точку (X/Z ², Y/Z ³).

Для эллиптической кривой вводятся следующие константы:

Дискриминант кривой E определяется по формуле

Если char K ¹ 2, 3, то дискриминант можно вычислить и так:

Деление на 1728 = 2⁶3³ имеет смысл только в тех полях, чья характеристика отлична от 2 и от 3. Кривая E неособа тогда и только тогда, когда . Далее рассматриваются только неособые кривые.

Для неособых кривых вводится j -инвариант

он тесно связан с понятием изоморфизма эллиптических кривых.

Говорят, что кривая E с координатами X и Y изоморфна над полем K кривой E’ с координатами X’, Y’ (обе заданы уравнением Вейерштрасса), если найдутся такие константы r, s, t Î K и u Î K ^*, что при замене переменных

X = u ² X’ + r, Y = u ³ Y’ + su ² X’ + t

кривая E перейдет в кривую E’. Отметим, что изоморфизм кривых определен относительно поля K. Изоморфизм эллиптических кривых является отношением эквивалентности.

Лемма. Изоморфные над полем K кривые имеют один и тот же j -инвариант. С другой стороны, любые кривые с совпадающими j -инвариантами изоморфны над алгебраическим замыканием поля K. То есть j -инвариант разделяет классы эквивалентности отношения изоморфизма над алгебраическим замыканием поля K.

Групповой закон

Рассмотрим для char K ¹ 2, 3 замену переменных

переводящую кривую заданную длинной формой Вейерштрасса в изоморфную ей кривую, определяемую короткой формой Вейерштрасса E: Y ² = X ³ + aX + b при некоторых a, b Î K. На таких представителях классов изоморфных эллиптических кривых можно наглядно ввести групповой закон методом хорд и касательных.

Сложение точек определяется с помощью хорд. Пусть P и Q – две точи кривой. Соединим их прямой линией. Она обязательно пересечет кривую в какой-то третьей точке R поскольку мы пересекаем кубическую кривую прямой. Точка R будет определена над тем же полем, что сама кривая и исходные точки P и Q. Отразим затем точку R относительно горизонтальной оси координат и получим точку, определяемую над основным полем. Последняя точка и будет суммой P + Q.

Рис.38. Групповой закон. Сложение точек.

Касательные служат для удвоения точек (используя хорду нельзя сложить точку с собой). Пусть P – произвольная точка эллиптической кривой. Проведем касательную к кривой в точке P. Она пересечет кривую в какой-то третьей точке R (кубическая кривая пересекается по трем точкам с учетом кратности пересечения). Отразив R относительно горизонтальной оси, мы получим точку [2] P = P + P. Вертикальная касательная в точке P «пересекает» кривую в бесконечно удаленной точке. В этой ситуации P + P = O и говорят, что P – точка порядка 2.

Рис.39. Групповой закон. Удвоение точек.

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

Y = a ₁ X + a ₃

Алгебраические формулы, реализующие сложение точек по методу хорд и касательных.

Лемма. Пусть E – эллиптическая кривая, определяемая уравнением

E: Y ² + a ₁ XY + a ₃ Y = X ³ + a ₂ X ² + a ₄ X + a ₆,

на которой выбраны точки P ₁(x ₁, y ₁) и P ₂(x ₂, y ₂). Точка – P ₁ имеет координаты

– P ₁(x ₁ – y ₁ – a ₁ x ₁ – a ₃).

 

Введем коэффициенты

при x ₁ ¹ x ₂ и

если x ₁ = x ₂, но P ₂ ¹ – P ₁. Если P ₃(x ₃, y ₃) = P ₁ + P ₂ ¹ O, то x ₃ и y ₃ вычисляются по формулам:

Фиксируем натуральное число m и обозначим через [ m ] отображение кривой на себя, сопоставляющее каждой точке P ее кратное [ m ] P, то есть

Это отображение – основа криптографических систем, опирающихся на эллиптическую кривую, поскольку его можно легко вычислить, но крайне сложно обратить, то есть по данным координатам P (x, y) и [ m ] P (x’, y’) найти m очень трудно. (Конечно сложность обращения предполагает специальный выбор эллиптической кривой и соблюдения других условий).

⇐ Предыдущая14151617181920212223Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: