Нахождение простых множителей больших чисел с помощью специально созданных процессоров

Question

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

Так...

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

Я не могу комментировать осуществимость подхода, точно такого же, как тот, который вы описали, но люди похожий вещи, которые очень часто используют FPGA:

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

Answer 5

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

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

Answer 6

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

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