ОПРЕДЕЛЕНИЕ ПОРЯДКА ГРУППЫ ДИВИЗОРОВ ГИПЕРЭЛЛИПТИЧЕСКОЙ КРИВОЙ Авторы: Долгов В.И., Неласая А.В., Зайцев С.А. Докладчик: Неласая Анна Викторовна Кафедра. - презентация

1 ОПРЕДЕЛЕНИЕ ПОРЯДКА ГРУППЫ ДИВИЗОРОВ ГИПЕРЭЛЛИПТИЧЕСКОЙ КРИВОЙ Авторы: Долгов В.И., Неласая А.В., Зайцев С.А. Докладчик: Неласая Анна Викторовна Кафедра Программных Средств КМИС -2007

2 Нормативные документы Закон Украины Про електронний цифровий підпис Закон Украины Про електронний цифровий підпис Определяет правовой статус электронной цифровой подписи и регулирует отношения, возникающие при использовании электронной цифровой подписи. Определяет правовой статус электронной цифровой подписи и регулирует отношения, возникающие при использовании электронной цифровой подписи. Закон Украины Про електронні документи та електронний документообіг Закон Украины Про електронні документи та електронний документообіг Устанавливает основные организационно-правовые положения электронного документооборота и использования электронных документов Устанавливает основные организационно-правовые положения электронного документооборота и использования электронных документов

3 Стандарты, основанные на эллиптических кривых ДСТУ Державний стандарт України. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривых. Формування та перевірка. Київ:-Держстандарт України, ДСТУ Державний стандарт України. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривых. Формування та перевірка. Київ:-Держстандарт України, ГОСТ Р Государственный стандарт российской федерации. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи. М.: Госстандарт России, ГОСТ Р Государственный стандарт российской федерации. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи. М.: Госстандарт России, ANSI X9.62. Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), ANSI X9.62. Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), 1999.

4 Эллиптические кривые Е(К):y 2 + axy + by = x 3 +cx 2 + dx + e, где a, b, c, d, e K. Е(GF (p)) :y 2 = x 3 + ax + b mod p, где a, b GF (p), 4a 3 +27b 2 0 mod p p-простое число. Е(GF (2 m )) :y 2 +xy= x 3 + ax 2 + b mod (f(x),2), где a, b GF (2 m ), f(x) GF (2 m ) – неприводимый.

5 Сложение точек эллиптической кривой над GF(p)

6 Гиперэллиптические кривые Пусть - конечное поле и пусть - алгебраическое замыкание. Гиперэллиптическая кривая рода над представляет собой набор решений уравнения (1) где - полином степени не более, - нормированный полином степени и не существует решений, которые бы одновременно удовлетворяли уравнению (1) и уравнениям с частными производными и. Дивизор на кривой

7 Канторовы групповые операции на якобиане Сложение Дублирование (замена шагов 1-3)

8 Формирование ключа Задача дискретного логарифмирования на гиперэллиптической кривой (ЗДЛГЭК): найти с из D 2 =с D 1 при известных D 1 и D 2 D 2 - открытый ключ (точка ЭК) c - секретный ключ D 1 – базовый дивизор Пусть D 1 и D 2 два элемента якобиана гиперэллиптической кривой такие, что D 2

9 Методы решения ЗДЛГЭК Гиперэллиптические кривые, определенные над, где m - составное имеют потенциальную криптографическую слабость к Weil descent –атаке. Гиперэллиптические кривые, определенные над, где m - составное имеют потенциальную криптографическую слабость к Weil descent –атаке. Tate – спаривание, является билинейным отображением группы дивизоров кривой над конечным полем в мультипликативную группу. Tate – спаривание, является билинейным отображением группы дивизоров кривой над конечным полем в мультипликативную группу. Вычислительная сложность index-calculus алгоритма для вычисления дискретного логарифма на якобиане гиперэллиптической кривой, определенной над конечным полем ниже чем сложность метода -Полларда для кривых рода выше чем 4. Вычислительная сложность index-calculus алгоритма для вычисления дискретного логарифма на якобиане гиперэллиптической кривой, определенной над конечным полем ниже чем сложность метода -Полларда для кривых рода выше чем 4. В работах П. Гаудри, Н. Териаулта и др. показано, как атаковать гиперэллиптические кривые рода 3 и 4. Предложенные методы являются модификациями index calculus алгоритмов с использованием понятий «больших простых» и «двойных больших простых» дивизоров. В работах П. Гаудри, Н. Териаулта и др. показано, как атаковать гиперэллиптические кривые рода 3 и 4. Предложенные методы являются модификациями index calculus алгоритмов с использованием понятий «больших простых» и «двойных больших простых» дивизоров.

10 Параметры криптосистем на гиперэллиптических кривых Конечное поле, над которым определена кривая. Здесь, где p – простое, m – целое. Конечное поле, над которым определена кривая. Здесь, где p – простое, m – целое. Гиперэллиптическая кривая – гладкая кривая вида Гиперэллиптическая кривая – гладкая кривая вида, где – нормированный полином степени, – полином степени максимум (род кривой)., где – нормированный полином степени, – полином степени максимум (род кривой). Порядок якобиана заданной кривой, то есть количество элементов в полученной абелевой группе дивизоров. Порядок якобиана заданной кривой, то есть количество элементов в полученной абелевой группе дивизоров. Базовая точка якобиана – дивизор, представленный в форме Мамфорда двумя полиномами, принадлежащий якобиану кривой и являющийся генератором подгруппы большого простого порядка. Базовая точка якобиана – дивизор, представленный в форме Мамфорда двумя полиномами, принадлежащий якобиану кривой и являющийся генератором подгруппы большого простого порядка.

11 Основные требования к параметрам 1. Порядок якобиана кривой должен иметь большой простой делитель n длиной как минимум 160 бит. 2. Большое простое n не должно быть делителем для всех простых k, для которых проблема дискретного логарифма в конечном поле разрешима за практически приемлемое время. 3. Когда - простое, не должно быть подгрупп порядка в 4. Род кривой должен быть достаточно мал. На сегодня известны эффективные методы дискретного логарифмирования кривых большого рода вплоть до рода 4 и 3

12 Интервал Хассе-Вейла F q - поле, над которым определена кривая g - род кривой

13 Алгоритмы определения порядка якобиана l-адические. Основная идея заключается в использовании морфизма Фробениуса l-адические. Основная идея заключается в использовании морфизма Фробениуса p-адические. Основаны на каноническом поднятии абелева множества над в абелево множество над (множество p-адических чисел) p-адические. Основаны на каноническом поднятии абелева множества над в абелево множество над (множество p-адических чисел)

14 Кривые специального вида кривые Коблица вида, где кривые Коблица вида, где кривые Булера –Коблица, где кривые Булера –Коблица, где – квадратичный вычет в – квадратичный вычет в кривые Фурукавы кривые Фурукавы 1), где 2), где – квадратичный невычет в.

15 Результаты работы p = , a = 11,13,19,33,34,37,39,44,52,57,62,65,71,76,77,89,91,94,95,99, #J = = (2) ( ) (2) ( ) p = , a = 3,10,11,12,13,14,19,23,27,31,37,40,41,44,45,48,52,56,58,59,61,63,73, 76,86,92,97,99, #J = = (2) ( ) (2) ( ) p = , a =11,17,22,34,55,61,66,69,77,79,85,92, #J = = (2) ( ) p = , a = 3,6,12,15,21,24,27,29,30,37,39,41,42,47,48,54,58,60,61,69,74,75,78,82,84,94,96,97, #J = = (2) ( ) (2) ( )

16 Классы изоморфных кривых Например, для p= коэффициенты а =11 и а =33 связаны следующим образом: для восьми возможных значений с: с = , с = , с = , с = , с = , с = , с = , с =

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