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