|
Современная криптография в значительной мере использует результаты таких дисциплин как алгебра, теория чисел, теория сложности. Студентам, изучающим криптографию, необходимо знание ее математических основ. Среди этих основ одно из ведущих мест занимает проблема дискретного логарифмирования.
Дискретное логарифмирование – задача обращения функции 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проектировать и разработать учебные модули;
• создать документацию;
• сформировать базу учебных заданий по теме "Дискретное логарифмирование";
• обеспечить интеграцию созданных модулей с основным ядром системы.
|
На уровень вверх
Купить