Comments 62
Ничего не понял, но звучит легендарно!
Когда-то казалось, что такие цифры недостижимы
Чтоб читатели не надеялись зря — такие цифры и недостижимы.
Число из примера раскладывается так быстро, потому что оно из очень структурированных множителей: с кучей бинарных 1'чек подряд (FFFFFF...)
Я попробовал воспроизвести, запустив код из статьи. Kissat успешно разложил число из примера за 6ч реального времени / 3ч процессорного. Дальше я поменял число на какое-нибудь реалистичное, с нормальными рандомными множителями — 53ч реального / 25ч процессорного времени спустя сат-солвер так ничего и не засолвил.
Сат-солвер на такой задаче может чуть-чуть упростить формулу, а дальше ему остаётся только обильно брутфорсить. Когда искомые числа очень структурированные (куча единичных бит), этот брутфорс быстро натыкается на решение. А в общем случае — не натыкается.
Если что, число из статьи — это:
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
q = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
N = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFEFFFFFC2F000003CFFFFFFC2EFFFFFFFFFFFFFFFEFFFFFC2F0000000000000001000003D1
const uint64_t expected[8] = {
0x00000001000003d1ULL, 0xfffffc2f00000000ULL,
0xfffffffffffffffeULL, 0x000003cffffffc2eULL,
0xfffffffefffffc2fULL, 0x00000000ffffffffULL,
0x0000000000000000ULL, 0xffffffff00000001ULL
};
А моё рандомное, которое сат-солвер ожидаемо не осилил:
p = 0x587A9436A2C29AF0556EFF9F0D4E401845C04BB620E51F66CF4AB11D61783561
q = 0xDFB1F31B89B8AFAE7B09356C026210DB8266314972775A1B99A6E6F764DECC2D
N = 0x4D5047E1F0C4F9EA3BB6860776E59E9C7F507FFA245F99041E786EB80A7EDF5514B4FA4F00EF2ECF36C749062673F8208F1BD394D2757236A7A8AD851AC8AE0D
const uint64_t expected[8] = {
0xA7A8AD851AC8AE0Dull, 0x8F1BD394D2757236ull,
0x36C749062673F820ull, 0x14B4FA4F00EF2ECFull,
0x1E786EB80A7EDF55ull, 0x7F507FFA245F9904ull,
0x3BB6860776E59E9Cull, 0x4D5047E1F0C4F9EAull
};
Сорри, что хайджекнул верхний коммент :)
То есть солвер вывел ограничения на исходные числа, исходя из их произведения.
Если такое ограничение можно сформулировать на обычном языке, а не в виде последовательности упрощений КНФ, то это может ускорить другие алгоритмы разложения чисел.
Не, ускорить не получится, у умножения самого по себе нету какой-то хитрой скрытой структуры, с которой сат-солвер мог бы помочь. И у умножения хороший «лавинный эффект» — если посмотреть на умножение двух длинных чисел в виде битов, биты в середине результата зависят сразу от большинства бит обоих множителей. Солверу остаётся только перебирать.
Это задача "Синтез микропрограмм на основе решения булевых формул" из дальнейших исследований, которые я упоминаю в статье. По прямому алгоритму (например умножение или хеширование), сгенерировать обратный алгоритм используя выполнимость булевых формул.
Это ясно что не каждое число может быть разложено раньше окончания времени Вселенной, потому что солвер экспоненциальный, а не полиномиальный. Время в лучшем и худшем случае может сильно отличаться и для полиномиальных алгоритмов, а не то что экспоненциальных.
Но вот от количества единичек в числе это вряд ли зависит. Попробуйте ещё несколько чисел, чтобы найти вероятность, какую долю чисел солвер успевает вычислить за резонное время (нужно дать хотя бы те же 6 часов на вашем оборудовании).
Дело в том что после преобразования алгоритма умножение в формулу КНФ, все эти единички и нолики в числах очень сильно перемешиваются, до неузнаваемости, а как мы знаем - отличить лёгкую булеву формулу от сложной является тоже NP-трудной задачей. Раз вы её не решили, то и утверждать то что выше не можете.
А как вам кажется, скорее моё число какое-то особенное, что его сат-солвер не может разложить, или ваше в примере особенное, что его успешно раскладывает? По-моему вас запутал чатгпт, взяв для примера в своём скрипте очень структурированные множители, что создало иллюзию что этот подход может факторизовать 512-битные числа.
Попробуйте ещё несколько чисел, чтобы найти вероятность, какую долю чисел солвер успевает вычислить за резонное время (нужно дать хотя бы те же 6 часов на вашем оборудовании)
Предлагаю наоборот: я ж уже поставил 2 эксперимента с 512-битными числами (первый репро из статьи разложился, второй рандомный не разложился), а вы только один :) Попробуйте найти всего лишь ещё одно 512-битное случайное полупростое, с которым бы сат-солвер справился. Если верить статье, это должно быть сделать очень легко — тем более у вас отрабатывает за 3.5ч вместо моих 6ч.
Ток на деле статья-то не работает.
я в демагогию вступать не буду - ищите кого другого хейтить, в идеале себя.
Справедливо, комменты ведь не место для дискуссий, правдива ли статья
От создателей "Парламент - не место для дискуссий". На мой взгляд, автор, отказавшись от обсуждения, статью полностью дискредитировал. Спасибо, что обратили внимание на число из статьи, действительно легко не заметить
Ещё один хейтер. Так а что обсуждать? Будет более быстрый солвер (может даже полиномиальный) - будет всё работать. А вам бы лишь бы загадить всё и всех.
Что вы подразумеваете под "хейтом"? Такими заявлениями вы понижаете уровень дискуссии. Нет, дело не в хейте. Вы привели как пример действительно одно очень интересное число. Да, нельзя утверждать на основании одного контрпримера, что метод нерабочий, но по-хорошему на вас, как на авторе, как раз лежит бремя показать, что он работает. А пока что есть одно "удобное" число и одно "неудобное". Убедительных доказательств работы кроме примера не представлено. Вот и все - это здоровый скептицизм и пространство для вас
Наличие полиномиального солвера ведь эквивалентно открытию P=NP...
Если продемонстрировать что P=NP, мы можем не то что RSA факторить, а вообще делов натворить
Ничего не понятно, но если звучит так, как звучит, это весьма сильно (и может даже довольно опасно)
Дело в том что любую программу, в том числе и программу произведения двух длинных чисел, можно переписать как булеву формулу в КНФ (конъюнктивной нормальной форме)
Мне кажется, что эта формула ( КНФ ) будет очень длинной. По сути дела она будет содержать все возможные ответы.
Да, формулы получаются немаленькие, но некоторые эвристики их берут. В данном случае, для 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" в криптографии обычно означает нахождение способа расшифровки без приватного ключа, а не просто факторизацию числа. Автор смешивает теоретическую сложность задач с практическими возможностями конкретных алгоритмов.
512 бит факторизовать тоже не 2**512 времени заняло, так что и ваше предположение неверно. Другое дело что одни числа для SAT солвера просто берутся, а другие не берутся за время существования Вселенной, потому что солвер экспоненциальный. Но отличить простые от сложных - тоже NP-трудная задача, поэтому сказать что одно число простое а другое трудное для взятия солвером вы не можете. Как минимум, не предоставив полиномиального алгоритма выполнимости булевых формул.
Синтез микропрограмм на основе решения булевых формул.
Уже: https://github.com/nickgildea/z3_codegen
Работает, проверял как-то. Но интересно было бы посмотреть и на ваше решение :)
Не сказал бы что ваш процессор прям таки старый)
Как ломается RSA512 за 3.5 часа на одном ядре старого ноутбука