Новый подход к решению систем уравнений в задачах дискретного логарифмирования


The Presentation inside:

Slide 0

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


Slide 1

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


Slide 2

Алгоритмы дискретного логарифмирования в конечных полях, использующие факторную базу Алгоритм Адлемана Алгоритм COS Index-calculus Решето числового поля Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. - М.: МЦНМО, 2004 .


Slide 3

Постановка задачи Решить систему n линейных уравнений c m неизвестными: Операции сложения и умножения определены по правилам: (здесь p - некоторое целое положительное число)


Slide 4

Сведение задачи к : решению семейства систем над полями Галуа решению системы над кольцом целых чисел решению уравнения над кольцом матриц Анализ методов решения систем линейных уравнений в кольцах вычетов


Slide 5

Анализ методов решения систем линейных уравнений в кольцах вычетов Сведение задачи к : решению семейства систем над простыми полями решению системы над кольцом целых чисел решению уравнения над кольцом матриц


Slide 6

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


Slide 7

Метод сведения к решению системы над простыми полями: пример (продолжение)


Slide 8

Метод сведения к решению системы над простыми полями: пример (продолжение)


Slide 9

Метод сведения к решению системы над простыми полями: пример (продолжение)


Slide 10

Метод сведения к решению системы над простыми полями: пример (продолжение) По Китайской теореме об остатках:


Slide 11

Недостатки метода сведения к решению семейства систем над простыми полями Решение не одной, а нескольких систем Факторизация числа p: открытая проблема современной теории чисел (не существует алгоритма с полиномиальной сложностью)


Slide 12

Анализ методов решения систем линейных уравнений в кольцах вычетов Сведение задачи к : решению семейства систем над простыми полями решению системы над кольцом целых чисел решению уравнения над кольцом матриц


Slide 13

Метод сведения к решению системы над кольцом целых чисел (1): пример Сведение: Общее решение: экспоненциальный рост коэффициентов Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. - М.: Мир, 1999.


Slide 14

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


Slide 15

Анализ методов решения систем линейных уравнений в кольцах вычетов Сведение задачи к : решению семейства систем над простыми полями решению системы над кольцом целых чисел решению уравнения над кольцом матриц


Slide 16

Метод сведения к уравнению над кольцом матриц Ax=b x=A-1b Елизаров В.П. Успехи мат. наук. – 1993. Т. 48, вып. 2. с. 181-182. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I - М.: Гелиос АРВ, 2003


Slide 17

Предложенный метод В основе: Расширенный алгоритм Евклида Схема Жордана Применим для: колец вычетов полей Галуа Эффективность: По временной и емкостной сложности эквивалентен классическим алгоритмам Жордана и Гаусса решения систем в полях Галуа


Slide 18

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


Slide 19

Схема Жордана


Slide 20

Матрицы над кольцом Опр.2 Матрица называется строчно эквивалентной матрице если она может быть получена из A с помощью конечной последовательности элементарных преобразований строк. Элементарными преобразованиями строк матрицы называют: умножение любой ее строки на обратимый элемент кольца R; прибавление к любой ее строке другой строки, умноженной на произвольный элемент кольца R; транспозицию строк. Опр.1 Множество всех матриц размером m x n с элементами из кольца R будем обозначать через Rm,n


Slide 21

Применение алгоритма Евклида к матрице


Slide 22

Работа алгоритма Решение системы: Вычисление обратной матрицы:


Slide 23

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


Slide 24

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


Slide 25

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


Slide 26

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


Slide 27

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


Slide 28

Временная сложность алгоритмов Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005 Метод сведения к уравнению над кольцом матриц Метод сведения к диофантовым уравнениям (с построением матрицы Смита) Метод сведения к полям Галуа Метод, предложенный в данной работе


Slide 29

Временная сложность алгоритмов Метод сведения к уравнению над кольцом матриц Метод сведения к диофантовым уравнениям (с построением матрицы Смита) Метод сведения к полям Галуа Метод, предложенный в данной работе


Slide 30

Решение систем, возникающих при дискретном логарифмировании Свойства: Большой размер (миллионы уравнений с миллионами неизвестных) Разреженные матрицы Поля: структурированное гауссово исключение Кольца: модифицированный алгоритм структурированного гауссова исключения


Slide 31

Заключение Результаты, полученные в данной работе: Проведен анализ известных методов решения систем линейных уравнений над кольцом вычетов Разработан алгоритм, эквивалентный по сложности методам Жордана и Гаусса решения систем линейных уравнений над полями Галуа Программа, реализующая разработанный алгоритм, зарегистрирована Федеральной службой по интеллектуальной собственности, патентам и товарным знакам (Роспатент) Результаты исследований опубликованы в журнале «Информационные технологии» (№2, 2006)


Slide 32

Направление дальнейшей работы Теоретическое и экспериментальное исследование влияния полученного метода на временную сложность алгоритмов дискретного логарифмирования, использующие факторную базу: Алгоритм Адлемана Index-calculus Алгоритм COS Решето числового поля


Slide 33

Кольца вычетов Операции сложения и умножения определяют кольцо вычетов по модулю p . Оно является коммутативным кольцом с единицей. Опр.1 Делителем нуля в произвольном кольце R называется любой его элемент для которого в R существует элемент удовлетворяющий условию a ·b=0 или b ·a=0 Опр.2 Обратимым элементом в произвольном кольце R называется любой его элемент для которого в R существует обратный элемент a-1, удовлетворяющий условию a · a-1 =1 или a-1 ·a=1


Slide 34

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


Slide 35

Пример решения системы в поле Галуа порядка 37


Slide 36

Пример решения системы в кольце вычетов по модулю 36 Все коэффициенты системы являются делителями нуля, т.е. необратимы. Однако решение существует и единственно:


×

HTML:





Ссылка: