Майзаков Максим Александрович Разработка модулей автоматической генерации заданий с решениями по теме «Дискретное логарифмирование» диплом
| Вид материала | Диплом |
- Мозжевилов Максим Александрович Разработка модулей генерации заданий и решений по теме, 891.19kb.
- Дидин Максим Александрович Переславль-Залесский Гимназия 7 7 7 7 7 7 7 7 56 диплом, 189.17kb.
- Дидин Максим Александрович Переславль-Залесский Гимназия 10 8 3 10 10 15 8 64 диплом, 103.28kb.
- Разработка урока по теме: «Развитие мышления через постановку проблемно творческих, 84.71kb.
- Отчет о выполеннии ниокр по теме Разработка унифицированных функциональных модулей, 219.08kb.
- Методы подготовки тестов по информатике и программированию, 55.02kb.
- Лоскутов Савва Александрович г. Асбест >26,5 диплом, 483.81kb.
- От двоичного кодирования к системам автоматической генерации кода, 2820.18kb.
- Тест №1 (из 6 заданий); Тест №2 (из 5 заданий); Тест №3 (в двух вариантах из 10 заданий);, 336.57kb.
- Название проекта, 6.03kb.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Институт математики и компьютерных наук
Кафедра информационной безопасности
Допустить к защите в ГАК
Заведующий кафедрой
информационной безопасности,
д.т.н., профессор А.А. Захаров
“____” _________ 2010 г.
Майзаков Максим Александрович
Разработка модулей автоматической генерации заданий с решениями по теме «Дискретное логарифмирование»
(дипломная работа)
Научный руководитель:
к.ф.-м.н., доцент кафедры ИБ
__________ Ниссенбаум О.В.
Автор работы:
__________ Майзаков М. А.
Тюмень – 2010
Оглавление
Оглавление 2
1.2 Шаг младенца – шаг великана 8
1.2 Ро-метод Полларда для дискретного логарифмирования 10
1.3 Алгоритм Полига-Хеллмана 14
1.4 Алгоритм исчисления порядка (art-calculus algorithm) 16
1.5 Оценка сложности решения 19
ГЛАВА 2. Обзор существующих методов контроля знаний 21
2.1 Методы контроля знаний при изучении курса «Теоретико-числовые методы в криптографии» 21
2.2 Тесты 22
2.3 Контрольные и самостоятельные работы 26
2.4 Итоги 27
ГЛАВА 3. Реализация модулей 28
3.2 Взаимодействие с ядром 29
3.3 Экспорт данных 31
3.4 Документация 32
3.5 Модуль BABYSTEP (Шаг младенца - шаг великана) 32
3.6 Модуль POLARD (Ро-метод Полларда дискретного логарифмирования) 35
3.8 Модуль INDEXCLCL (Алгоритм исчисления порядка (art-calculus algorithm) 40
ЗАКЛЮЧЕНИЕ 41
Приложение 1. Документация для пользователя. 45
Приложение 2. Документация для программиста. 49
Приложение 3. Примеры генерируемых заданий. 52
ВВЕДЕНИЕ
Современная криптография в значительной мере использует результаты таких дисциплин как алгебра, теория чисел, теория сложности. Студентам, изучающим криптографию, необходимо знание ее математических основ. Среди этих основ одно из ведущих мест занимает проблема дискретного логарифмирования.
Дискретное логарифмирование – задача обращения функции gx в некоторой конечной мультипликативной группе G.
Для заданных g и a решение x уравнения gx = a называется дискретным логарифмом элемента a по основанию g.
Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа x удовлетворяющего данному уравнению. Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы.
В отличие от логарифма непрерывного, дискретный логарифм не является дифференцируемой монотонной функцией, его нельзя найти приближенно, разложив в ряд Тейлора, и вообще никакого приближенного значения здесь не может быть, ведь x – целое число.
Именно трудность решения этой задачи лежит в основе многих криптосистем. Это и шифр Эль-Гамаля, Шамира, такие криптостандарты как подпись DSA , ГОСТ Р 34.10-94, ГОСТ Р 34.10-2001 и другие.
Например в том же шифре Эль-Гамаля открытым ключом является тройка (p, g, y), закрытым ключом — число x, и связаны они между собой cоотношением y=gxmod p. А процедура восстановления закрытого ключа по открытому есть решение задачи дискретного логарифмирования.
К тому же очень важное место в криптоанализе асимметричных шифров занимает эффективность используемых алгоритмов. Если, к примеру, в симметричной криптографии для взлома шифра используется в основном только полный перебор, то для взлома асимметричных шифров применяются специальные алгоритмы, сокращающие время в разы. Чем лучше алгоритм, тем более быстро он приводит к желаемому результату.
Наиболее очевидным и легким в реализации является алгоритм исчерпывающего поиска (прямого перебора). Этот наивный метод является самым трудоемким, он требует O(n) умножений, то есть обладает экспоненциальной сложностью.
Состоит он в следующем: вычисляются g0, g1, g2,…, gp—1 пока не попадется gi≡a(mod p). Полученное i будет искомым дискретным логарифмом i=logga(mod p—1).
Как видим, алгоритм абсолютно неэффективен в реальных условиях при больших p, которые используются в криптографии.
Первым алгоритмом, позволяющим не использовать обычный перебор, был Baby-step-giant-step (Шаг младенца, шаг великана), предложенный Даниелем Шэнксом (Shanks) в 1973 году.
Сложность данного алгоритма составляет O(
) умножений по модулю и O(
) операций сравнения. Как видим, алгоритм эффективнее прямого перебора, но в связи с малой распространенностью асимметричных шифров он оставался малоизвестным.
Но уже в конце 70х, в 80х вместе с развитием асимметричных шифров и подписей, данная тема получила большое распространение. Стали появляться все новые и новые алгоритмы с все большой и большой скоростью работы.
К примеру, ρ-алгоритм Полларда для вычисления дискретного логарифма.
Основные идеи этого алгоритма известны в теории чисел довольно долгое время, однако только в 1979 г. американским ученым Адлеманом был предложен данный алгоритм как метод решения задачи нахождения дискретного логарифма. В реальных условиях использования этого алгоритма (в том числе и его усовершенствованных вариантов) дает довольно быстрое решение задачи нахождения дискретного логарифма. Самым быстрым на данное время считается алгоритм Полига-Хеллмана. Этот алгоритм используется в случае известной факторизации порядка p группы G. Алгоритм Полига-Хеллмана является наиболее сложным для написания, так как требует реализации других теоретико-числовых алгоритмов, таких как китайская теорема об остатках.
Трудоемкость данного метода составляет:
умножений в группе при условии, что разложение n известно.
Как видим, выбор алгоритма напрямую влияет на скорость. Поэтому для будущего специалиста в области компьютерной безопасности и криптоанализа так важно понимание и корректное усвоение основ дискретного логарифмирования.
Один из способов обеспечения объективной оценки – использование индивидуальных вариантов контрольных и домашних заданий. Такой подход снижает вероятность списывания и помогает в раннем выявлении неуспевающих студентов.
Но внедрению такого подхода мешает большой объем подготовительной работы, необходимой для создания проверочных заданий, и время, затрачиваемое преподавателем для проверки работ студентов.
К тому же данные алгоритмы обладают следующей особенностью: при одних входных параметрах процесс решения может занять две-три итерации, а при других – десятки.
Если у нас, к примеру:
g – порождающий элемент,
p – простое число,
a – аргумент логарифма,
то количество итераций любого метода может насчитывать от 1 до p-1, при этом при одних a количество итераций будет не велико (1-3), а при других a очень большим (до p-1). Причем заранее выяснить количество невозможно.
Поэтому, прежде чем дать студенту задание, преподавателю необходимо предварительно узнать степень его сложности.
Так, в курсе «Теоретико-числовые методы в криптографии» ТюмГУ общий объем домашних и контрольных работ составляет около 150 задач на студента, а число студентов на курсе – от 30 до 45 человек. Таким образом, для обучения одного потока студентов необходимо составить и решить более 4500 различных задач.
Поэтому цель моей дипломной работы – разработка модулей автоматической генерации случайных заданий и решений к ним по теме «Алгоритмы дискретного логарифмирования» в дисциплине «Теоретико-числовые методы в криптографии».
Для ее достижения были поставлены следующие задачи:
- определить необходимый набор модулей;
- cпроектировать и разработать учебные модули;
- создать документацию;
- сформировать базу учебных заданий по теме "Дискретное логарифмирование";
- обеспечить интеграцию созданных модулей с основным ядром системы.
ГЛАВА 1. Алгоритмы дискретного логарифмирования
1.1 Общие сведения
Для реализации в виде модулей были выбраны следующие алгоритмы:
- шаг Младенца – шаг Великана;
- ро-метод Полларда;
- алгоритм Полинг-Хэмминга;
- алгоритм исчисления порядков (art-calculus algorithm).
Все эти алгоритмы являются обязательными для изучения в курсе "Теоретико-числовых методов в криптографии". К тому же все они достаточно просты для самостоятельного применения и являются базисом для более сложных.
К каждому из модулей предъявляются следующие требования:
- формирование произвольного количества индивидуальных вариантов;
- наличие в каждом варианте любого количества заданий;
- возможность выбора степени сложности заданий;
- генерация соответствующих решений к данным заданиям;
- взаимосвязь с ядром системы.
В качестве входных параметров в модуль передается: количество заданий и параметры, определяющие их сложность:
- пределы в которых находится модуль - число p;
- пределы в которых находится количество итераций;
- размер факторной базы для некоторых алгоритмов.
Все входные параметры приводятся к разумным значениям, не допустимые исключаются. Количество итераций в не должно превышать 30, а генерируемых заданий больше 2000.
Каждый модуль должен работать в двух режимах: в первом он выступает как отдельное приложение, работает независимо и имеет собственный интерфейс; во втором – он общается с основным ядром системы, получая входные данные только от него.
В результате работы формируется два текстовых файла: один с самими заданиями, а другой с их решениями.
Рассмотрим каждый модуль подробно по отдельности.