Комментарии 44
Ничего не понял, но звучит легендарно!
Когда-то казалось, что такие цифры недостижимы
Ничего не понятно, но если звучит так, как звучит, это весьма сильно (и может даже довольно опасно)
Дело в том что любую программу, в том числе и программу произведения двух длинных чисел, можно переписать как булеву формулу в КНФ (конъюнктивной нормальной форме)
Мне кажется, что эта формула ( КНФ ) будет очень длинной. По сути дела она будет содержать все возможные ответы.
Да, формулы получаются немаленькие, но некоторые эвристики их берут. В данном случае, для RSA-512 получается формула из 202657 переменных и 1127580 выражений.
О, это похоже на нормальность числа Пи )) В нём, якобы, обязательно будет искомая комбинация символов, твоя дата рождения, твой номер телефона, все сочинения Пушкина и тд ) Такое вот следствие из гипотезы о нормальности числа π, правдоподобно, но без математического доказательства(пока что)
Intel i9 13го поколения полномощный - старый и пыльный?
обожаю запах кликбейта тёплыми летними вечерами
Полагаю, что статья написана не для маленького пика посещаемости в первые часы, а на годы вперёд. Это разговор с вечностью!
Спустя 10-15 лет, Ваша придирка будет выглядет смехотворно.
Так это ноутбучный проц, только 36 МБ кеша, а пыльный потому что ноут давно в чистку не сдавал. В итоге частота далека от заявленных 5.6 ГГц, а ноут с Ryzen 9955HX3D работает в разы быстрее на том же одном ядре, особенно когда данные в кеш вмещаются.
https://yurichev.com/news/20220210_RSA/
3 года назад RSA 512 за 4 дня ломали на Ryzen 5 3600@64 GB, прямой факторизацией числа на CADO-NFS. Тут же машина с несколько раз производительнее. Да и сама программа факторизации взята более эффективная.
Не вижу принципиальной разницы, учитывая, что сложность факторизации двух произвольно взятых 512-битных чисел может на порядок(ки) различаться.
Для начала разберёмся, какой алгоритм использует CADO-NFS: https://chatgpt.com/share/68a3e312-c7c8-8000-abc5-9f7f1cf7bb44 . В кратце, числовое решето.
Этот алгоритм легко распределяется на много потоков и/или машин, поэтому 6-ядерный десктопный Ryzen 3600 должен быть помощнее, чем одноядерный ноутбучный 13980HX.
В моей статье используется совершенно другой алгоритм, а именно выполнимость булевых формул.
Эффективность факторизации трудно оценивать. Тот алгоритм работает за его алгоритмическую сложность, и нахождения числа - вероятностно, как я понимаю. Здесь же в статье используется алгоритм, чья алгоритмическая сложность в худшем случае - невообразимое число даже на квантовых компьютерах. Но эвристики делают его практичным.
Да, для разных чисел может существенно отличаться время работы солвера.
Да, для разных чисел может существенно отличаться время работы солвера.
Это-то и вызывает вопросы. У вас и 512-битное число, и оба числа его разложения, таковы, что почти все старшие разряды либо f либо 0, причем большими блоками подряд. Сравните это с числами из моей ссылки - они намного ближе к нормальным (в математическом смысле). Поэтому разница во времени работы солвера скорее всего обусловлена разницей в нормальности выбраных случайных чисел, а не алгоритмическим преимуществом
чем одноядерный ноутбучный 13980HX
Откуда у вас такая интересная спецификация процессора? У него 24 ядра (и 32 потока, что немаловажно)
>Думаю за какую недельку вычислений kissat возьмёт и используемый сейчас широко RSA-2048
как бы 512 бит от 2048 отличается далеко не в 4 раза по сложности!
Если RSA-512 разламывается за 3,5 часа, то RSA-2048 будет разламываться на той же машине за ~1 500 000 лет, а RSA-4096 - за ~20 000 000 000 000 лет
Более точные оценки скажу, если предоставите время хотя бы для 3-4 значений битности менее 512
Смотрите ответ выше - формула для RSA-512 стала в 10-15 раз больше чем для RSA-512. Конечно, это вопрос алгоритма решения выполнимости булевых формул - с текущим экспоненциальным алгоритмом и ускоряющими эвристиками, мы никогда не знаем, займёт это неделю или больше чем всё время Вселенной. Плюс для разных чисел сложность может существенно отличаться.
За разложение на множители 2048-битного числа полагается 200 килобаксов, не проходите мимо и обязательно напишите потом статью :)
спасибо Вам большое что сообщили, я не знал. Сейчас прямо вычисляю, но наверное другое число 2048-битное.
А все остальные, кто дочитал до этого коммента теперь вычисляют именно то число по вашему методу... :D
вот только вроде как конкурс закрыли в 2007-м году: https://en.wikipedia.org/wiki/RSA_numbers . Или есть теперь другие конкурсы по факторизации?
Ну так может они как я - пошли по прямой ссылке из предыдущего коммента, а про то что конкурс уже закрыли не доскролили наверх страницы.
P.S. Если что, я не вычисляю.
Есть! Но, правда, это посложнее.
150 000$ за простое число со 100 миллионами цифр.
Зачем тебе это...?
Так, ради публикации или признания?
За такие решения будет наблюдение.
И кто сказал что не существует полиномиального алгоритма факторизации больших чисел...
И признание, и публикация конечно же важны. К наблюдению мне не привыкать. Вот именно что для дальнейшего развития ИИ очень важны быстрые алгоритмы выполнимости булевых формул, это добавило бы логику к ИИ, который сейчас (чисто нейронные сети) - с большего статистический и решать задачи может только в одно-два действия. Факторизация - это лишь способ продемонстрировать теперешние возможности SAT солверов. Главное всё-таки создать ИИ с логикой, а не чисто болтолога. Тогда автоматическое доказательство теорем позволит ИИ делать изобретения - типа межзвёздного двигателя.
есть сильное подозрение, что любой специализированный алгоритм типа elliptic curve или GNFS на этом же примере и оборудовании отработает гораздо быстрее.
А можете дать своё число на 512 бит в десятичном виде?
Подскажите, какие есть способы превратить алгоритм в булеву формулу? Или она только возникает в неявном виде внутри cbms, и никак её не вытащить?
Когда дело касается криптографии необходимо консультироваться со специалистом. Описанный алгоритм имеет мало общего с RSA, а разложение случайного 512-битного числа на простые множители будет проходить меньше чем за секунду на одном ядре любого современного процессора при использовании тривиальных алгоритмов из "школьного" курса.
Заголовок не совсем точно отражает содержание. Автор факторизует произведение двух известных простых чисел (secp256k1 prime и P-256 prime), а не настоящий RSA-ключ. Это существенно разные задачи по сложности.
Прогноз про RSA-2048 ("за какую недельку вычислений kissat возьмёт") не учитывает экспоненциальный рост сложности факторизации. Переход от 512 к 2048 битам означает увеличение времени вычислений в миллиарды раз, а не в 4 раза. SAT-формула для RSA-2048 будет содержать миллионы переменных.
Также есть неточности в терминологии - "ломание RSA" в криптографии обычно означает нахождение способа расшифровки без приватного ключа, а не просто факторизацию числа. Автор смешивает теоретическую сложность задач с практическими возможностями конкретных алгоритмов.
Синтез микропрограмм на основе решения булевых формул.
Уже: https://github.com/nickgildea/z3_codegen
Работает, проверял как-то. Но интересно было бы посмотреть и на ваше решение :)
Как ломается RSA512 за 3.5 часа на одном ядре старого ноутбука