Поиск основных факторов для больших чисел с помощью специально созданных процессоров

Question

Насколько я понимаю, многие криптографические алгоритмы с открытыми ключами в наши дни зависят от больших простых чисел, составляющих ключи, и сложность в разложении двух простых чисел затрудняет шифрование. Я также понимаю, что одна из причин того, что факторинг таких больших чисел так сложен, заключается в том, что большой размер используемых чисел означает, что ни один ЦП не может эффективно работать с числами, поскольку наши крошечные 32- и 64-разрядные ЦП не совпадают. для 1024, 2048 или даже 4096 битных чисел. Для обработки этих чисел необходимо использовать специализированные математические библиотеки Big Integer, и эти библиотеки по своей сути медленны, поскольку ЦП может хранить (и обрабатывать) только небольшие куски (например, 32 или 64 бита) за один раз.

Итак ...

Почему вы не можете создать специализированный специализированный чип с 2048-битными регистрами и гигантскими арифметическими схемами, во многом так же, как мы масштабировали с 8-16 до 32-64-битных процессоров, просто построите на много больше ? Эта микросхема не потребует большей части схем на обычных процессорах, в конце концов, она не будет обрабатывать такие вещи, как виртуальная память, многопоточность или ввод / вывод. Это даже не должен быть процессор общего назначения, поддерживающий хранимые инструкции. Просто необходимый минимум для выполнения необходимых арифметических вычислений с огромными числами.

Я не очень много знаю о дизайне ИС, но я помню, как узнал о том, как работают логические вентили, как построить половину сумматора, полный сумматор, а затем связать вместе кучку сумматоров для выполнения многоразрядной арифметики. Просто увеличьте масштаб. Много.

Теперь, я вполне уверен, что есть очень веская причина (или 17), что вышеперечисленное не сработает (поскольку в противном случае один из многих людей, умнее меня, уже сделал бы это), но я заинтересован зная почему это не сработает.

(Примечание. Этот вопрос может потребовать доработки, поскольку я даже не уверен, имеет ли этот вопрос смысл)

Answer 1

То, что сказал @cube, и тот факт, что гигантскому арифметическому логическому блоку потребовалось бы больше времени для стабилизации логических сигналов, а также другие сложности в цифровом дизайне. Цифровая логика включает в себя то, что вы принимаете как должное в программном обеспечении, а именно то, что сигналы с помощью комбинационной логики занимают небольшое, но ненулевое время для распространения и установления. Множитель 32х32 должен быть тщательно продуман. Множитель 1024x1024 не только потребует огромное количество физических ресурсов в микросхеме, но также будет медленнее, чем множитель 32x32 (хотя, возможно, быстрее, чем умножитель 32x32, вычисляющий все частичные продукты, необходимые для выполнения умножения 1024x1024). Кроме того, узким местом является не только множитель: у вас есть пути памяти. Вам придется потратить кучу времени, собирая 1024 бита из схемы памяти, ширина которой составляет всего 32 бита, и сохраняя полученные 2048 битов обратно в схему памяти.

Почти наверняка лучше получить группу "обычных" 32-битных или 64-битных систем, работающих параллельно: вы получаете ускорение без сложности проектирования оборудования.

edit: если у кого-то есть доступ к ACM (у меня его нет), возможно, посмотрите эту статью , чтобы узнать, что там написано.

Answer 2

Это потому, что это ускорение будет только в O (n), но сложность факторизации числа примерно равна O (2 ^ n) (по отношению к количеству битов). Поэтому, если бы вы сделали этот überprocessor и разложили числа в 1000 раз быстрее, мне нужно было бы только увеличить числа на 10 бит, и мы снова вернулись бы к старту.

Answer 3

Шамир и Тромер предлагают аналогичный подход с использованием вида грид-вычислений :

В этой статье обсуждается новый дизайн для нестандартного оборудования. осуществление этапа просеивания, который снижает [стоимость просеивания по сравнению с TWINKLE] примерно до 10 миллионов долларов. Новое устройство, называется TWIRL, можно рассматривать как продолжение TWINKLE устройство. Однако в отличие от TWINKLE это не имеет оптоэлектронных компонентов и может таким образом, изготавливаться с использованием стандартной технологии VLSI на кремниевых пластинах. Основная идея заключается в использовании единственная копия ввода для решения многих подзадач в параллели. Поскольку входное хранилище доминирует над стоимостью, если издержки распараллеливания сохраняются на низком уровне, а затем ускорение получается по сути бесплатно. Действительно, Основная проблема заключается в эффективном достижении этого параллелизма при одновременном компактном хранении входных данных. Решение этого включает в себя множество соображений, начиная от теории чисел до технологии СБИС.

Answer 4

Я не могу комментировать осуществимость подхода, точно такого же, как вы описали, но люди очень часто делают подобные вещи, используя ПЛИС:

• Взлом ключей DES
• Взломать разговоры GSM
• Видеокарта с открытым исходным кодом

Answer 5

Как указывалось выше, основная проблема заключается в том, сколько возможностей вам нужно пройти, чтобы вычислить число. При этом специализированные компьютеры существуют для подобных вещей.

Настоящий прогресс в криптографии такого рода заключается в улучшении алгоритмов числового факторинга. В настоящее время самым быстрым из известных общих алгоритмов является сито общего числа .

Исторически сложилось так, что мы, по-видимому, можем вдвое увеличивать число за каждое десятилетие. Часть этого - более быстрое аппаратное обеспечение, а часть - просто лучшее понимание математики и того, как выполнять факторинг.

Answer 6

Почему бы вам не попробовать собрать супер-квантовый компьютер и запустить алгоритм Шора на нем?

"... Если построить квантовый компьютер с достаточным количеством кубитов, алгоритм Шора можно использовать для взлома схем криптографии с открытым ключом, таких как широко используемая схема RSA. RSA основанный на предположении, что факторинг больших чисел невозможен в вычислительном отношении. Насколько известно, это предположение справедливо для классических (неквантовых) компьютеров; не известно ни одного классического алгоритма, способного вычислять полиномиальное время. Однако алгоритм Шора показывает, что факторинг эффективен на квантовом компьютере, поэтому достаточно большой квантовый компьютер может сломать RSA. ... " -Википедия