СодержаниеВВЕДЕНИЕ 3
ГЛАВА 1. Алгоритмы дискретного логарифмирования 7
1.1 Общие сведения 7
1.2 Шаг младенца - шаг великана 8
1.2 Ро-метод Полларда для дискретного логарифмирования 10
1.3 Алгоритм Полига-Хеллмана 13
1.4 Алгоритм исчисления порядка (index-calculus algorithm) 16
1.5 Оценка сложности решения 19
ГЛАВА 2. Обзор существующих методов контроля знаний 20
2.1 Методы контроля знаний при изучении курса "Теоретико-числовые методы в криптографии" 20
2.2 Тесты 21
2.3 Контрольные и самостоятельные работы 25
2.4 Итоги 26
ГЛАВА 3. Реализация модулей 27
3.1 Среда разработки 27
3.2 Взаимодействие с ядром 28
3.3 Экспорт данных 30
3.4 Документация 31
3.5 Модуль BABYSTEP (Шаг младенца - шаг великана) 31
3.6 Модуль POLARD (Ро-метод Полларда дискретного логарифмирования) 34
3.7 Модуль POLIHELL (дискретное логарифмирование при помощи алгоритма Полига-Хеллмана) 36
3.8 Модуль INDEXCLCL (Алгоритм исчисления порядка (index-calculus algorithm) 38
ЗАКЛЮЧЕНИЕ 39
СПИСОК ЛИТЕРАТУРЫ 40
Приложение 1. Документация для пользователя. 42
Приложение 2. Документация для программиста. 46
Приложение 3. Примеры генерируемых заданий. 49ВведениеСовременная криптография в значительной мере использует результаты таких дисциплин как алгебра, теория чисел, теория сложности. Студентам, изучающим криптографию, необходимо знание ее математических основ. Среди этих основ одно из ведущих мест занимает проблема дискретного логарифмирования.
Дискретное логарифмирование - задача обращения функции gx в некоторой конечной мультипликативной группе G.
Для заданных g и a решение x уравнения gx = a называется дискретным логарифмом элемента a по основанию g.
Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа x удовлетворяющего данному уравнению. Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы.
В отличие от логарифма непрерывного, дискретный логарифм не является дифференцируемой монотонной функцией, его нельзя найти приближенно, разложив в ряд Тейлора, и вообще никакого приближенного значения здесь не может быть, ведь x - целое число.
Именно трудность решения этой задачи лежит в основе многих криптосистем. Это и шифр Эль-Гамаля, Шамира, такие криптостандарты как подпись DSA , ГОСТ Р 34.10-94, ГОСТ Р 34.10-2001 и другие.Литература1. А.В.Рожков, О.В. Ниссенбаум. Теоретико-числовые методы в криптографии: Учебное пособие. Тюмень: Издательство Тюменского государственного университета, 2007. 160с.
2. Виноградов И.М. Основы теории чисел. М.: Наука, 1972. 402с.
3. Бухштаб А.А. Теория чисел. Издательство: Лань. Серия: Учебники для вузов. Специальная литература. 2008 г. ISBN: 978-5-8114-0847-4
4. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. Учебное пособие. М.: Гелиос-АРВ, 2001.
5. Б. Я. Рябко, А. Н. Фионов. Основы современной криптографии для специалистов в информационных технологиях. Издательство - Научный мир, 2004 год. ISBN: 5-89176-233-1
6. Трей Нэш. C# 2008: ускоренный курс для профессионалов. Язык программирования C# 3.0 для .NET 3.5. М.: Вильямс, 2008. 576c.
7. Эндрю Троелсен. С# 2008 и платформа .NET 3.5 Framework = Pro C# 2008 and the .NET 3.5 Framework. - 4-е изд. - М.: Вильямс, 2009. - С. 1368. - ISBN 978-5-8459-1589-4
8. Герберт Шилдт. C# 3.0: полное руководство = C# 3.0: The Complete Reference. - 4-е изд. - М.: Вильямс, 2009. - С. 992. - ISBN 978-5-8459-1565-8
9. Кристиан Нейгел, Карли Уотсон и др. Visual C# 2008: базовый курс. Visual Studio® 2008 = Beginning Visual C# 2008. - М.: Диалектика, 2009. - ISBN 978-5-8459-1317-3
10. Кристиан Нейгел, Билл Ивьен и др. C# 2008 и платформа .NET 3.5 для профессионалов = Professional C# 2008. - М.: Диалектика, 2008. - ISBN 978-5-8459-1458-3
11. В.В. Гузеев. Образовательная технология: от приёма до философии. М.:Сентябрь, 1996.
12. В.И. Загвязинский - Теория обучения: Современная интерпретация: Учеб. пособие для студ. высш. пед. учеб. заведений. - М.: Издательский центр "Академия", 2001-192 с.
|
