В России таких результатов не было уже около десяти лет. Его получение потребовало настоящей кооперации между исследователями ИВМ РАН, Сколтеха и МГУ.
Разложение числа RSA -232 названо одним из символов года науки в России. Об этом было заявлено в докладе о важнейших научных достижениях российских ученых в 2020 году. Доклад был представлен на общем собрании членов Российской академии наук президентом РАН Александром Михайловичем Сергеевым.
Этот научный результат был получен сотрудниками Московского центра фундаментальной и прикладной математики в ИВМ РАН Николаем Замарашкиным и Дмитрием Желтковым совместно с научным сотрудником Сколтеха Сергеем Матвеевым (сейчас доцент МГУ). Для его достижения были использованы суперкомпьютер «Ломоносов» МГУ и суперкомпьютер «Жорес» Сколтеха.
RSA – это первая криптосистема с открытым ключом, используемая для шифрования и цифровой подписи. Огромные числа, входящие в эту систему, были опубликованы в 1991 году, и до сих пор около половины этих сложных чисел не разложена на множители. Разложения таких чисел на простые множители используется для декодирования информации. По мере роста размеров числа, которое подлежит разложению, количество действий растет очень быстро и для каждого числа нужно производить свой уникальный расчет.
Например, для разложения самого первого RSA-числа из 100 знаков в 1991 году хватило нескольких дней вычислений на одном компьютере. А вот RSA-129 в 1994 раскладывали с использованием более полутора тысяч компьютеров. Раскладывать RSA числа пробуют в разных странах: Франции, США и других.
«В нашей стране таких результатов не было уже около десяти лет, мы очень рады, что в год науки и технологий в России на этот итог обращено пристальное внимание сообщества. К тому же его получение потребовало настоящей кооперации между исследователями ИВМ РАН, Сколтеха и МГУ.
Квота на «Жоресе» позволила разрешить ключевой этап — этап решения сверхбольшой системы линейных уравнений из 0 и 1. Он потребовал около месяца непрерывных вычислений с использованием практически всего CPU-сегмента суперкомпьютера», – рассказывает один из участников работы Сергей Матвеев.
«В числе RSA-232 –232 десятичных знака, у него два делителя порядка корня из этого числа (то есть примерно 116 знаков). Если использовать поиск делителей от 2 до “корня”, то число вариантов, которые надо перебрать будет больше числа атомов во Вселенной (приблизительно в 10^20 раз).
Умный отбор кандидатов-делителей и выбор из набора “кандидатов” исключительно одной верной пары — трудная технологическая задача» – добавляет Сергей.
Использование одного из самых передовых суперкомпьютеров России – «Жорес», в Центре по Научным и Инженерным Вычислительным Технологиям Сколтеха, где проводил исследования Сергей, было решающим для достижения успеха.
Фото: Суперкомпьютер “Жорес” / ©Сколтех