Новый подход к решению систем уравнений в задачах дискретного логарифмирования Выполнила: Савельева А.А. Научный руководитель: проф., к.т.н. Авдошин С.М. - презентация

1 Новый подход к решению систем уравнений в задачах дискретного логарифмирования Выполнила: Савельева А.А. Научный руководитель: проф., к.т.н. Авдошин С.М.

2 2006 МАТИ-РГТУ им. К.Э.Циолковского 1 Криптографические системы, основанные на сложности дискретного логарифмирования n Схема открытого распределения ключей Диффи-Хеллмана n Схема ЭЦП Эль-Гамаля n ГОСТ Р (Россия) n ANSI X9.62/ (США)

3 2006 МАТИ-РГТУ им. К.Э.Циолковского 2 Алгоритмы дискретного логарифмирования в конечных полях, использующие факторную базу n Алгоритм Адлемана n Алгоритм COS n Index-calculus n Решето числового поля Решение систем линейных уравнений в кольцах вычетов Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. - М.: МЦНМО, 2004.

4 2006 МАТИ-РГТУ им. К.Э.Циолковского 3 Постановка задачи Решить систему n линейных уравнений c m неизвестными: Операции сложения и умножения определены по правилам: (здесь p - некоторое целое положительное число)

5 2006 МАТИ-РГТУ им. К.Э.Циолковского 4 Сведение задачи к : n решению семейства систем над полями Галуа n решению системы над кольцом целых чисел n решению уравнения над кольцом матриц Анализ методов решения систем линейных уравнений в кольцах вычетов

6 2006 МАТИ-РГТУ им. К.Э.Циолковского 5 Анализ методов решения систем линейных уравнений в кольцах вычетов Сведение задачи к : n решению семейства систем над простыми полями n решению системы над кольцом целых чисел n решению уравнения над кольцом матриц

7 2006 МАТИ-РГТУ им. К.Э.Циолковского 6 Метод сведения к решению системы над простыми полями: пример Василенко О.Н. Теоретико- числовые алгоритмы в криптографии. - М.: Институт проблем информационной безопасности МГУ, МЦНМО, 2004.

8 2006 МАТИ-РГТУ им. К.Э.Циолковского 7 Метод сведения к решению системы над простыми полями: пример (продолжение) 1 2 2

9 2006 МАТИ-РГТУ им. К.Э.Циолковского 8 Метод сведения к решению системы над простыми полями: пример (продолжение)

10 2006 МАТИ-РГТУ им. К.Э.Циолковского 9 Метод сведения к решению системы над простыми полями: пример (продолжение)

11 2006 МАТИ-РГТУ им. К.Э.Циолковского 10 Метод сведения к решению системы над простыми полями: пример (продолжение) По Китайской теореме об остатках:

12 2006 МАТИ-РГТУ им. К.Э.Циолковского 11 Недостатки метода сведения к решению семейства систем над простыми полями n Решение не одной, а нескольких систем n Факторизация числа p : открытая проблема современной теории чисел (не существует алгоритма с полиномиальной сложностью)

13 2006 МАТИ-РГТУ им. К.Э.Циолковского 12 Анализ методов решения систем линейных уравнений в кольцах вычетов Сведение задачи к : þ решению семейства систем над простыми полями n решению системы над кольцом целых чисел n решению уравнения над кольцом матриц

14 2006 МАТИ-РГТУ им. К.Э.Циолковского 13 Метод сведения к решению системы над кольцом целых чисел (1): пример n Сведение: n Общее решение: экспоненциальный рост коэффициентов Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. - М.: Мир, 1999.

15 2006 МАТИ-РГТУ им. К.Э.Циолковского 14 Метод сведения к решению системы над кольцом целых чисел (2): модификации Способы избежать экспоненциального роста коэффициентов: Использование диагональной формы Смита Модификация метода Гаусса Недостаток: Асимптотическая временная и емкостная сложность значительно больше сложности метода Жордана решения систем в полях Галуа Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. - Нижегородский Государственный Университет им. Н.И. Лобачевского. – Полиномиальный рост коэффициентов

16 2006 МАТИ-РГТУ им. К.Э.Циолковского 15 Анализ методов решения систем линейных уравнений в кольцах вычетов Сведение задачи к : þ решению семейства систем над простыми полями þ решению системы над кольцом целых чисел n решению уравнения над кольцом матриц

17 2006 МАТИ-РГТУ им. К.Э.Циолковского 16 Метод сведения к уравнению над кольцом матриц Ax=bx=A -1 b Елизаров В.П. Успехи мат. наук. – Т. 48, вып. 2. с Эффективный алгоритм вычисления обратной матрицы ? Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I - М.: Гелиос АРВ, 2003

18 2006 МАТИ-РГТУ им. К.Э.Циолковского 17 Предложенный метод n В основе: l Расширенный алгоритм Евклида l Схема Жордана n Применим для: l колец вычетов l полей Галуа n Эффективность: l По временной и емкостной сложности эквивалентен классическим алгоритмам Жордана и Гаусса решения систем в полях Галуа

19 2006 МАТИ-РГТУ им. К.Э.Циолковского 18 Расширенный алгоритм Евклида АЛГ Евклид(a,b) ПОКА ЦИКЛ К.Ц. К.АЛГ. Вход : Выход : d, x, y, r, s такие, что

20 2006 МАТИ-РГТУ им. К.Э.Циолковского 19 Схема Жордана

21 2006 МАТИ-РГТУ им. К.Э.Циолковского 20 Матрицы над кольцом строчно эквивалентной матрице Опр.2 Матрица называется строчно эквивалентной матрице если она может быть получена из A с помощью конечной последовательности элементарных преобразований строк. Элементарными преобразованиями строк Элементарными преобразованиями строк матрицы называют: умножение любой ее строки на обратимый элемент кольца R ; прибавление к любой ее строке другой строки, умноженной на произвольный элемент кольца R ; l транспозицию строк. Опр. 1 Множество всех матриц размером m x n с элементами из кольца R будем обозначать через R m,n

22 2006 МАТИ-РГТУ им. К.Э.Циолковского 21 Применение алгоритма Евклида к матрице Коэффициенты Безу для a=26, b=9 :

23 2006 МАТИ-РГТУ им. К.Э.Циолковского 22 Работа алгоритма n Решение системы: n Вычисление обратной матрицы:

24 2006 МАТИ-РГТУ им. К.Э.Циолковского 23 Алгоритм АЛГ Жордан(А, n, m, p) ДЛЯ i=1 ДО n ЦИКЛ {обнуляем эл-ты i-го столбца ниже i-й строки} ДЛЯ j=i+1 ДО n ЦИКЛ К.Ц. {для j} Вход : {расширенная матрица} Выход : А {преобразованная матрица}

25 2006 МАТИ-РГТУ им. К.Э.Циолковского 24 Алгоритм (продолжение) ЕСЛИ НОД(a ii, p)>1 ТО выйти из алгоритма {матрица вырождена} ИНАЧЕ {обнуляем элементы i-го столбца выше i-й строки} К.Е. ВЕРНУТЬ(А) К.АЛГ.

26 2006 МАТИ-РГТУ им. К.Э.Циолковского 25 Временная сложность алгоритмов Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. - Нижегородский Государственный Университет им. Н.И. Лобачевского. – Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I - М.: Гелиос АРВ, 2003 Елизаров В.П. Успехи мат. наук.–1993.Т. 48, вып. 2. Метод сведения к уравнению над кольцом матриц Метод сведения к диофантовым уравнениям (с построением матрицы Смита) Метод сведения к полям Галуа Метод, предложенный в данной работе Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. - М.: Институт проблем информационной безопасности МГУ, МЦНМО, 2004 Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ : «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ

27 2006 МАТИ-РГТУ им. К.Э.Циолковского 26 Временная сложность алгоритмов Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ : «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. - Нижегородский Государственный Университет им. Н.И. Лобачевского. – Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I - М.: Гелиос АРВ, 2003 Елизаров В.П. Успехи мат. наук.–1993.Т. 48, вып. 2. Метод сведения к уравнению над кольцом матриц Метод сведения к диофантовым уравнениям (с построением матрицы Смита) Метод сведения к полям Галуа Метод, предложенный в данной работе

28 2006 МАТИ-РГТУ им. К.Э.Циолковского 27 Временная сложность алгоритмов Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ : «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I - М.: Гелиос АРВ, 2003 Елизаров В.П. Успехи мат. наук.–1993.Т. 48, вып. 2. Метод сведения к уравнению над кольцом матриц Метод сведения к диофантовым уравнениям (с построением матрицы Смита) Метод сведения к полям Галуа Метод, предложенный в данной работе

29 2006 МАТИ-РГТУ им. К.Э.Циолковского 28 Временная сложность алгоритмов Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ : «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ Метод сведения к уравнению над кольцом матриц Метод сведения к диофантовым уравнениям (с построением матрицы Смита) Метод сведения к полям Галуа Метод, предложенный в данной работе

30 2006 МАТИ-РГТУ им. К.Э.Циолковского 29 Временная сложность алгоритмов Метод сведения к уравнению над кольцом матриц Метод сведения к диофантовым уравнениям (с построением матрицы Смита) Метод сведения к полям Галуа Метод, предложенный в данной работе

31 2006 МАТИ-РГТУ им. К.Э.Циолковского 30 Решение систем, возникающих при дискретном логарифмировании n Свойства: l Большой размер (миллионы уравнений с миллионами неизвестных) l Разреженные матрицы Поля : структурированное гауссово исключение Кольца : модифицированный алгоритм структурированного гауссова исключения

32 2006 МАТИ-РГТУ им. К.Э.Циолковского 31 Заключение Результаты, полученные в данной работе : n Проведен анализ известных методов решения систем линейных уравнений над кольцом вычетов n Разработан алгоритм, эквивалентный по сложности методам Жордана и Гаусса решения систем линейных уравнений над полями Галуа n Программа, реализующая разработанный алгоритм, зарегистрирована Федеральной службой по интеллектуальной собственности, патентам и товарным знакам (Роспатент) n Результаты исследований опубликованы в журнале «Информационные технологии» (2, 2006)

33 2006 МАТИ-РГТУ им. К.Э.Циолковского 32 Направление дальнейшей работы n Теоретическое и экспериментальное исследование влияния полученного метода на временную сложность алгоритмов дискретного логарифмирования, использующие факторную базу: l Алгоритм Адлемана l Index-calculus l Алгоритм COS l Решето числового поля

34 2006 МАТИ-РГТУ им. К.Э.Циолковского 33 Кольца вычетов кольцо вычетов по модулю p Операции сложения и умножения определяют кольцо вычетов по модулю p. Оно является коммутативным кольцом с единицей. Делителемнуля Опр.1 Делителем нуля в произвольном кольце R называется любой его элемент для которого в R существует элемент удовлетворяющий условию a ·b=0 или b ·a=0 Обратимым элементом Опр.2 Обратимым элементом в произвольном кольце R называется любой его элемент для которого в R существует обратный элемент a -1, удовлетворяющий условию a · a -1 =1 или a -1 ·a=1

35 2006 МАТИ-РГТУ им. К.Э.Циолковского 34 Обратный элемент обратным Элемент называется обратным к, если Для нахождения обратного элемента нужно решить линейное диофантово уравнение: коэффициентов Безу расширенный алгоритм Евклида Уравнение разрешимо относительно u и v тогда и только тогда, когда НОД(x,p)= 1; в этом случае Для вычисления u и v ( коэффициентов Безу ) используется расширенный алгоритм Евклида.

36 2006 МАТИ-РГТУ им. К.Э.Циолковского 35 Пример решения системы в поле Галуа порядка 37

37 2006 МАТИ-РГТУ им. К.Э.Циолковского 36 Пример решения системы в кольце вычетов по модулю 36 Все коэффициенты системы являются делителями нуля, т.е. необратимы. Однако решение существует и единственно: