|
ВИДЕОТЕКА |
|
Факторизация числа RSA-232: решения и нерешенные вопросы в задачах отображения алгоритмов на реальные вычислительные системы Н. Л. Замарашкин Институт вычислительной математики им. Г.И. Марчука Российской академии наук, г. Москва |
|||
Аннотация: Пусть \begin{equation} \label{eq:1} y = x^d \mod n, \end{equation} рассматривают как зашифрованное сообщение. Дешифровка (восстановление \begin{equation} \label{eq:2} x = y^d \mod n. \end{equation} В системе шифрования RSA параметры Между научными группами ведется соревнование по разложению больших RSA-чисел. За последние 15 лет все рекорды получены с помощью общего метода решета числового поля (Generalized Number Field Sieve, GNFS). В основе GNFS лежит следующая последовательность шагов:
В ИВМ РАН создание программной реализации шага г) осуществлялось более 10 лет. Существующий программный код уникален. Парадоксальный выбор в пользу формально последовательного алгоритма Ланцоша-Монтгомери решения линейных систем над полем из двух элементов был компенсирован детальным изучением внутреннего параллелизма метода. Реализация ИВМ РАН использует практически все известные параллельные технологии (многопоточность, распределенные вычисления, специализированные ускорители), масштабируется на вычислительные системы с десятками тысяч ядер. Структуры данных и методы вычислений оптимизированы под эффективное использование современных вычислительных систем и современной оперативной памяти. Отказ от применения любой из вышеназванных технологий приводит к многократным потерям в производительности. Таким образом, программный код ИВМ РАН является одновременно высоко технологичным продуктом и решением математической задачи эффективного отображения алгоритмов на реальные вычислительные системы. 17 февраля 2020 года в ИВМ РАН была закончена факторизация числа RSA-232 (число с Website: https://talantiuspeh.webex.com/talantiuspeh-ru/j.php?MTID=m55570f44dd449faf2b424bad81fd836c |