Тема: РЕАЛИЗАЦИЯ И АНАЛИЗ МЕТОДОВ УСКОРЕНИЯ ФАКТОРИЗАЦИИ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ

Одним из популярнейших разделов в современной алгебраической геометрии становится раздел, посвященный эллиптическим кривым, в сторону которых ведутся активные научные исследовании в теории чисел и особенно в эллиптической криптографии. Это объясняется тем, что в эллиптических кривых используется иная алгебра, отличающаяся от ранее известной модульной, и задача дискретного логарифмирования на эллиптических кривых намного сложнее задачи дискретного логарифмирования на конечном поле.
Эллиптические кривые были известны еще давно, но их активное применение в криптографии началось после независимых публикаций Нила Коблица[8] и Виктора Миллера[10] в 1985 году, в которых они предлагали воспользоваться некоторыми свойствами этих кривых.
Кроме алгоритмов шифрования и электронной цифровой подписи, в криптографии эллиптические кривые используются также в задаче факторизации целых чисел, которая является односторонней, т.е. является легко вычислимой в одну сторону, но не наоборот. Факторизация - это разложение числа на его делители. На вычислительной сложности этой задачи строится один из самых популярных на сегодняшний день криптографических алгоритмов с открытым ключом - RSA. В нем берутся два больших простых числа одинаковой длины и вычисляется их произведение, которое является открытым ключом. Сумев разложить это число на множители, можно однозначно восстановить секретный ключ и прочесть зашифрованное сообщение.
Алгоритм факторизации, работающий на эллиптических кривых был предложен Хендриком Ленстрой[9] в 1987 году. Преимуществом данного алгоритма являлось то, что он работал за субэкспоненциальное время, и скорость его работы зависела только от наименьшего делителя входного числа, а не от самого этого числа. В том же году Питер Монтгомери[11] предложил использовать специальный вид кривых для ускорения вычислений, которые впоследствии были названы его именем. Самый большой скачок в развитии данного алгоритма произошел после появления статьи Гарольда Эдвардса[7] 2007 года, в которой описывалась новая форма кривых, и статьи Дэниэла Бернштейна[2] 2008 года, в которой проводилось их обобщение. Так появились скрученные кривые Эдвардса, которые нашли свое применение во многих современных криптографических алгоритмах. Большой раздел по факторизации на эллиптических кривых уделен в монографии Ишмухаметова Ш.Т.[15]
Купить

Некоторые современные шифры, в том числе и RSA, строятся на задаче целочисленной факторизации, т.е. разложения большого числа на простые множители равной длины. Задача эта сильно осложняется ограниченностью вычислительных ресурсов, поэтому для более эффективного взлома таких шифров используются специально разработанные алгоритмы факторизации.
Одни из самых первых алгоритмов факторизации, среди которых р- метод Полларда, p - 1 метод Полларда, метод Шенкса и другие, работают за экспоненциальное время, поэтому сегодня применяются очень редко или вовсе не применяются на практике в то время, как алгоритм Ленстры применяется очень часто. На больших числах с большими минимальными делителями этот алгоритм сильно уступает методу квадратичного решета и методу решета числового поля, но при малых делителях имеет среди них наибольшую скорость, поэтому его основной задачей является отсеивание относительно небольших делителей (до нескольких десятков разрядов) для дальнейшего облегчения работы вышеперечисленных методов.
Подводя итоги, можно с уверенностью сказать, что в результате проделанной ВКР удалось достигнуть поставленные в начале цели в полной мере. Сперва был реализован классический алгоритм факторизации на эллиптических кривых Вейерштрасса, затем на нем были успешно реализованы некоторые модификации, а именно: были применены
проективные системы координат и был произведен перенос алгоритма на кривые Монтгомери и скрученные кривые Эдвардса. Последим выполненным улучшением было применение распараллеливания. Таким образом, удалось ускорить изначальный вариант алгоритма более чем в 20 раз. Кроме того, удалось выявить достоинства и недостатки применения кривых Монтгомери в задаче факторизации. К достоинствам можно отнести очень быстрое выполнение первой стадии, а к недостаткам - отсутствие возможности применения ускорений для умножения на второй стадии. Наиболее оптимальными оказались скрученные кривые Эдвардса, как более быстрые и перспективные. Самыми быстрыми системами координат для них оказались инвертированные и расширенные системы, слегка опередив классические проективные. Применение кривых Эдвардса с большим кручение также оказалось очень полезным в ускорении, повысив скорость работы алгоритма в 1,5 - 2 раза. С помощью всех этих улучшений в проделанной работе удалось факторизовать RSA числа вплоть до 200 бит (60 десятичных разрядов) за приемлемое время. Главным недостатком алгоритма Ленстры является то, что он является вероятностный, т.е. разброс времени выполнения в разных экспериментах на одних и тех же данных достаточно велик.

Купить