ИИ-агент взломал число, не поддававшееся 35 лет

Инженер стартапа Cognition Эрик Лу факторизовал рекордное 260-значное число RSA — задачу, над которой безуспешно бились математики почти три с половиной десятилетия. Настоящим автором взлома оказался вовсе не человек, а рой из десятков ИИ-агентов Devin, которые три недели почти без присмотра писали программу для взлома шифра на видеокартах.

Твит на 130 цифр, который сломал интернет

3 сентября инженер Cognition (компания, разрабатывающая ИИ-агента для программирования Devin) Эрик Лу опубликовал в соцсети X пост из одних только цифр — 130-значное число — и подпись: «делит RSA-260». Больше в посте не было ни слова.

Для тех, кто не в теме это выглядело как бессмыслица. Но для криптографического сообщества это была бомба: RSA-260 — одно из чисел легендарного RSA Factoring Challenge, публичного списка «неберущихся» чисел, который лаборатория RSA составила ещё в 1991 году, чтобы проверять на прочность одноимённый алгоритм шифрования. Приз за решение отменили в 2007-м, но задачки остались висеть как спортивный рекорд для математиков и энтузиастов. Предыдущий рекорд — RSA-250 — держался с февраля 2020 года, когда его взяла команда сразу из нескольких специалистов.

Лу же справился в одиночку — по крайней мере, так это выглядело со стороны. Через пару часов после поста откликнулся Алек Маффетт, участник команды, факторизовавшей RSA-155 ещё в 1999 году: поздравил коллегу по цеху. На Hacker News тем временем скопились десятки комментариев с вопросом «а как именно?» — Лу не раскрыл ни алгоритм, ни софт, ни железо, ни потраченное время.

Пустоту тут же заполнили слухи. Коллега Лу в шутку написал, что тот «подбирал и проверял случайные простые числа вручную семь месяцев подряд — трудолюбие побеждает талант». Шутку восприняли всерьёз: агрегаторы новостей и даже другие ИИ-модели (до того как об этом написали в Википедии) пересказывали байку как факт.

Как было на самом деле

9 сентября Cognition выпустила подробный технический разбор, и версия про семь месяцев ручного подбора рассыпалась. Никакого квантового компьютера тоже не оказалось — Лу прямо это подчеркнул. Число факторизовали классическим методом — общим решетом числового поля (GNFS), самым эффективным из известных алгоритмов для разложения больших чисел на множители. Именно GNFS использовался во всех предыдущих рекордах, включая RSA-250.

Разница — в исполнении. До сих пор самый тяжёлый этап GNFS, решетчатое просеивание (lattice sieving), всегда считали на процессорах: эффективно перенести его на видеокарты долго не получалось из-за особенностей доступа к памяти. Лу решил проверить, получится ли у Devin.

13 августа в 00:11 по тихоокеанскому времени он отправил агенту короткий запрос: собрать быструю GPU-реализацию модуля решета из открытого пакета CADO-NFS (стандартного инструмента для GNFS-вычислений), пользуясь тем, что видеокарты обладают куда большей пропускной способностью памяти, чем процессоры. Дал Devin доступ к одной тестовой видеокарте — и лёг спать. Через девять часов агент отчитался: новый GPU-модуль уже обгонял процессорную версию.

Дальше неделю Лу «гонял» параллельно от 3 до 18 сессий Devin одновременно, поручая им то ускорять отдельные части конвейера, то прогонять сквозные тестовые вычисления на кластере. Агенты переписали почти весь конвейер GNFS — от подбора полиномов до решения разреженных линейных систем — и за первые пять дней подняли производительность настолько, что число из 190 цифр обрабатывалось за то же время, что раньше уходило на 157-значное. Сам Лу признаётся: в математике решета числового поля он разбирается примерно как «автолюбитель средней руки» в устройстве двигателя — понимает роль деталей, но не физику процесса.

Всего же на разгон и саму факторизацию RSA-260 ушло около трёх недель и порядка 4900 GPU-дней (13,5 GPU-лет) вычислений — по рыночным ценам это около 400 тысяч долларов (порядка 32 млн рублей). Причём эти деньги компания фактически не потратила: вычисления шли на «осколках» простаивающих видеокарт — узлах, которые ИИ-кластеры Cognition не успели загрузить основной работой по обучению и обслуживанию моделей. По оценке Лу, такие простои обычно составляют единицы процентов от общей мощности кластера — и раньше эти крохи просто пропадали впустую.

Значит ли это, что шифрование сломано?

Нет — и это главное, на чём настаивает сам Лу. RSA-260 (862 бита) в тысячи раз проще современных стандартов шифрования: сегодняшние ключи RSA обычно имеют длину 2048 бит, а устаревший и небезопасный формат в 1024 бита официально вывели из обращения ещё в 2013 году.

По расчётам инженера, RSA-1024 при нынешних ценах на GPU-мощности можно было бы взломать этим же методом примерно за 30 млн долларов (порядка 2,4 млрд рублей) — и это не новость: о теоретической уязвимости 1024-битных ключей эксперты предупреждали ещё в середине 2000-х. А вот RSA-2048 от результата практически не пострадал: по подсчётам Лу, разница в сложности между 1024 и 2048 битами — это множитель порядка миллиарда, и решетом её пока не пробить.

Куда интереснее другое наблюдение автора: главные изменения — не в математике, а в доступности. Раньше такие вычисления были уделом узкого круга криптографов с редким сочетанием навыков в теории чисел и низкоуровневом программировании GPU. Теперь порог входа резко упал: по сути, нужен был лишь человек, способный правильно сформулировать задачу для ИИ-агента и вовремя поправить его, когда тот сворачивал не туда.

Кто делал работу — человек или машина

Сам Лу в итоговом посте честно признаётся, что не может однозначно поделить заслугу между собой, агентом, железом и удачей. По подсчётам Devin, за три недели Лу отправил агентам свыше 82 тысяч слов в более чем 3300 сообщениях в рамках 233 сессий — то есть постоянно направлял, останавливал бесполезные эксперименты и указывал на нерациональные решения. При этом десятки дочерних сессий агент запускал и обрабатывал вовсе без его участия.

Показательно и другое признание: без открытого проекта CADO-NFS, на основе которого агенты дорабатывали свой код, ничего бы не вышло — готовая архитектура и рабочая CPU-версия задавали Devin ориентир, без которого он терял направление. А чем сильнее итоговый код отходил от исходного CADO-NFS, тем чаще агент начинал путаться — то ли из-за нарастающей сложности, то ли потому, что именно эта библиотека хорошо знакома моделям по обучающим данным.

Восторга по этому поводу разделяют не все. Scientific American в своём разборе истории отметил, что ажиотаж вокруг результата не должен маскировать главное: никакого алгоритмического прорыва в самой факторизации не произошло — только грубая сила и инженерная оптимизация. А сам Лу в заключительной части поста честно пишет, что его тревожит риск потери человеческого понимания предмета: он признаёт, что разобрался в теории решета и GPU-программировании куда хуже, чем разобрался бы, делай он всё сам — хотя и лучше, чем если бы вообще не привлекал ИИ.

Показательно совпадение по времени: буквально за несколько дней до публикации Cognition в математическом сообществе разошлась ещё одна громкая (и спорная) новость — о попытке ИИ решить одну из «Задач тысячелетия». На этом фоне история с RSA-260 выглядит куда скромнее и куда лучше подтверждена: результат Лу любой желающий может перепроверить за секунды простым делением в столбик — весь смысл публичных криптографических вызовов именно в этом.

Источники :

cognition.com

scientificamerican.com

lilting.ch

Xrust ИИ-агент взломал число, не поддававшееся 35 лет

ИИ-агент взломал число, не поддававшееся 35 лет https://xrust.ru/news/313980-ii-agent-vzlomal-chislo-ne-poddavavsheesja-35-let.html

Оригинал статьи размещен в Новости Xrust https://xrust.ru/news/

https://ufatimes.ru

https://ufatimes.ru/ufa/ii-agent-vzlomal-chislo-ne-poddavavsheesia-35-let/

Телеграм: t.me/ainewsline

Источник: ufatimes.ru

Комментарии: