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


Купить