Devin от Cognition факторизовал RSA-260, поставив новый рекорд
Автор поста в блоге компании Cognition, имя в источнике не указано, рассказал, как в последние недели вместе с исследовательской командой компании дорабатывал планировщик задач кластера, а заодно, ради проверки идеи на практике и потому что уже около десяти лет увлекается факторизацией чисел как хобби, с помощью ИИ-агента Devin факторизовал RSA-260, 260-значное число: получил два простых множителя длиной по 130 цифр каждый. Это новый рекорд для самого большого публично решённого числа в конкурсе RSA Factoring Challenge, предыдущий рекорд, RSA-250, был установлен в феврале 2020 года. Для сравнения: современные ключи RSA используют числа длиной 2048 бит (~617 цифр), а 1024-битные ключи (~309 цифр) официально выведены из употребления ещё в 2013 году как небезопасные.
Разложение получено новой GPU-реализацией общего решета числового поля (GNFS, general number field sieve), алгоритма, который применялся и в предыдущих рекордных факторизациях RSA, но всегда с решетом на CPU: эффективно перенести его на GPU долгое время не удавалось. Реализация, сильно переработанная версия свободного пакета CADO-NFS; по словам автора, никаких алгоритмических прорывов в работе нет, перенос решета и разреженной линейной алгебры на GPU потребовал «обычной» инженерии производительности, использующей высокую пропускную способность памяти видеокарт. Ключевую роль сыграл Devin: 13 августа в 0:11:58 по тихоокеанскому времени автор поставил ему задачу написать GPU-замену CPU-программе решета las из CADO-NFS (получившую впоследствии название glas), дал доступ к облачной платформе Modal для тестов производительности, и лёг спать. Через 7 часов Devin самостоятельно получил рабочую версию, уже превосходившую по скорости исходный CPU-вариант. В течение следующей недели Devin под руководством автора довёл до готовности весь конвейер GNFS: переписал под GPU выбор полинома (программу gps1, часть кода, из проекта msieve), само решето, блочный алгоритм Видемана для решения линейной системы и извлечение квадратного корня на финальном шаге, а также вспомогательные скрипты. По словам автора, его собственная роль сводилась к постановке приоритетов, определению контрольных показателей и вмешательству, когда работа уходила не туда; измерения, управление кластером и саму оптимизацию Devin вёл автономно. Автор оценивает, что у команды профильных специалистов такая работа заняла бы несколько месяцев.
По оценке автора, вся факторизация обошлась примерно в $400 тысяч по нынешним рыночным ценам на GPU, это около 4900 GPU-дней, или 13,5 GPU-года. Основная часть, 3813 GPU-дней, ушла на решето, самый ресурсоёмкий этап GNFS; выбор полинома занял 643 GPU-дня (сам автор называет эту цифру аномально высокой, «попросту из-за некомпетентности оператора»); ещё 467 GPU-дней ушло на решение линейной системы, из которых около 7% не дали прогресса из-за сбоев или вытеснения более приоритетными задачами. Отдельного бюджета факторизация не потребовала: она считалась на «лишних» мощностях, простаивающих GPU-узлах в стойках NVL72, которые Cognition использует для обучения и инференса языковых моделей. Из-за того, как задачи упаковываются в стойки, и из-за резерва узлов на случай сбоев такие простои обычно составляют однозначный процент от общих мощностей компании; автор настроил планировщик так, чтобы заполнять эти узлы низкоприоритетными одноузловыми заданиями, а решето, которое можно мгновенно прервать и которое делится на миллиарды независимых кусков, оказалось для этого идеальным кандидатом. Новое GPU-решето, по словам автора, в 10 раз дешевле лучшей из прежних публично известных реализаций.
По расчётам автора, факторизация RSA-1024 (309-значного числа) требует примерно в 78 раз больше вычислений, чем RSA-260, то есть гиперскейлерам (крупным облачным провайдерам) или ведущим ИИ-лабораториям она обошлась бы примерно в $30 млн за одно число по рыночным ценам на GPU, а при дальнейшей оптимизации, по его словам, вероятно, заметно дешевле; автор допускает, что умеренная доработка может снизить эту стоимость ещё примерно вдвое, но подаёт это как осторожное предположение, а не установленный факт. При этом уязвимость RSA-1024 не новость: такие ключи официально выведены из обращения в 2013 году, а предположения о том, что АНБ могло позволить себе факторизовать их экономически ещё с середины 2000-х (в связи со специализированными проектами вроде архитектуры TWIRL или «матричной машины Бернштейна»), высказывались и раньше. Куда важнее, подчёркивает автор, что на актуальный стандарт RSA-2048 работа почти не влияет: он остаётся примерно в миллиард раз сложнее RSA-1024, и достигнутый прирост эффективности не меняет практическую невозможность факторизовать числа такого размера методом GNFS.
Главный вывод поста, по мысли автора, не про криптографию, а про возможности ИИ-агентов: порог входа в криптоаналитические задачи, а шире, в другую вычислительную математику и крупномасштабные научные вычисления, теперь заметно ниже, чем раньше, раз подобную работу способен вытянуть один человек с автономным программирующим агентом вместо команды узких специалистов. При этом сам автор признаёт, что понимает построенные Devin компоненты лишь поверхностно, «примерно так, как автолюбитель средней руки понимает устройство машины»: их общую роль, влияние на производительность и что считается нормальной работой, но не то, как они устроены «под капотом» и из чего сделаны.
Ключевые факты
- ИИ-агент Devin (продукт компании Cognition) самостоятельно построил GPU-реализацию алгоритма GNFS (general number field sieve) на основе пакета CADO-NFS и факторизовал 260-значное число RSA-260, новый рекорд RSA Factoring Challenge, обновивший рекорд RSA-250 от февраля 2020 года.
- Работа заняла около 4900 GPU-дней (13,5 GPU-года) и обошлась примерно в $400 тысяч по рыночным ценам на GPU; основная часть, 3813 GPU-дней, ушла на решето, самый ресурсоёмкий этап GNFS.
- Отдельного бюджета факторизация не потребовала: расчёты шли на простаивающих GPU-узлах кластера Cognition, которые обычно заняты обучением и инференсом языковых моделей и составляют лишь однозначный процент от общих мощностей компании.
- По оценке автора, факторизация RSA-1024 (309 цифр, примерно в 78 раз больше вычислений, чем RSA-260) обошлась бы гиперскейлерам или ведущим ИИ-лабораториям примерно в $30 млн за число по рыночным ценам на GPU, а дальнейшая оптимизация может удешевить её ещё заметнее.
- На защищённость актуального стандарта RSA-2048 (~617 цифр) это почти не влияет: по словам автора, он остаётся примерно в миллиард раз сложнее уже небезопасного RSA-1024, ключи которого официально выведены из употребления в 2013 году.
Почему это важно
Здесь важен не столько сам криптографический результат, сколько то, кто его получил. По словам автора поста, ИИ-агент Devin (продукт компании Cognition) почти без участия человека спроектировал и оптимизировал под GPU весь конвейер общего решета числового поля (GNFS), сложную вычислительную задачу на стыке теории чисел и низкоуровневой инженерии производительности видеокарт, которую раньше решали только узкие специалисты. Автор оценивает, что у команды профильных инженеров такая работа заняла бы несколько месяцев, а с Devin, около трёх недель, причём без отдельного бюджета: расчёты шли на простаивающих GPU-узлах кластера Cognition. Это не заявка на криптографический прорыв, сам автор пишет, что новых алгоритмов тут нет, а демонстрация того, что автономные программирующие агенты уже способны довести до результата целый исследовательский вычислительный проект, а не только написать код по готовому техническому заданию.
Кому это важно
Инженерам и исследователям, которые оценивают потолок возможностей автономных программирующих агентов вроде Devin на задачах уровня «спроектировать и довести до результата», а не «написать функцию по готовой спецификации». Командам с большими GPU-кластерами для обучения и инференса моделей, как пример того, что узлы, простаивающие из-за особенностей планировщика задач, можно почти бесплатно направлять на подходящие по свойствам параллельные вычисления. Специалистам по криптографии и компьютерной безопасности, как свежий ориентир по текущей стоимости факторизации RSA-чисел разного размера: практического вывода для защиты действующих систем здесь нет, поскольку актуальный стандарт RSA-2048 работа не затрагивает, но для уже выведенных из употребления более коротких ключей стоимость атаки становится нагляднее.
Как это применить
Сам пост описан автором как побочный экспериментальный проект, а не готовый к использованию продукт, но методика в нём переносима. Во-первых, это шаблон постановки задачи для автономного агента на исследовательскую инженерную работу: чётко описанная цель («GPU-замена конкретной CPU-программы, которая должна превзойти её по скорости»), доступ к вычислительным ресурсам для тестов и точечное, но своевременное вмешательство человека в моменты, когда работа уходит не туда. Во-вторых, это пример приёма для владельцев больших GPU-кластеров: выделить узлы, простаивающие из-за неполной упаковки задач в стойки, в отдельную низкоприоритетную очередь и заполнять их предельно распараллеливаемыми, мгновенно прерываемыми заданиями, в данном случае решетом GNFS, но подход годится для любых вычислений с такими же свойствами.
Можно ли доверять
Пост опубликован в блоге самой Cognition, компании, которая делает Devin и прямо заинтересована показать его с лучшей стороны; автор не назван, весь текст, рассказ от первого лица без подписи, и в источнике нет ни слова о независимой проверке или воспроизведении результата третьей стороной. При этом заявленная факторизация, не голое утверждение: в посте приведены оба множителя, и их можно перепроверить самостоятельно. Прямая проверка показывает, что произведение двух указанных 130-значных чисел действительно даёт заявленное 260-значное число, а оба множителя проходят стандартный тест на простоту (тест Миллера, Рабина), то есть математический результат согласован сам с собой. А вот все цифры по стоимости, времени счёта и доле сбоев, это собственные оценки автора, нигде не подтверждённые сторонним аудитом.
Риски и подводные камни
Главный риск, не в самой новости, а в её возможном упрощении при пересказе: результат не означает, что «ИИ взломал RSA». Автор прямо пишет, что алгоритмических прорывов здесь нет, это перенос известного алгоритма (GNFS) на GPU за счёт более качественной инженерии, и на защищённость актуального стандарта RSA-2048 (~617 цифр) это почти не влияет: он остаётся примерно в миллиард раз сложнее уже небезопасного RSA-1024. Сама уязвимость RSA-1024 тоже не новость, ключи такой длины официально выведены из употребления ещё в 2013 году, а предположения о том, что АНБ могло позволить себе их факторизацию ещё с середины 2000-х (в связи со специализированными проектами вроде архитектуры TWIRL или «матричной машины Бернштейна»), высказывались и раньше. Практический смысл работы в другом: по оценке автора, довести такой подход до RSA-1024 при рыночных ценах на GPU могло бы обойтись примерно в $30 млн за число, а значит, подобные вычисления теоретически доступны не только спецслужбам, но и гиперскейлерам или крупным ИИ-лабораториям с достаточным числом GPU. Отдельная деталь для трезвой оценки: сам автор признаёт, что понимает построенные Devin компоненты лишь поверхностно, как «автолюбитель средней руки» понимает устройство машины, то есть о независимом человеческом аудите написанного агентом кода в посте речи нет.