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

Question

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

Итак ...

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Реальный прогресс для такого рода криптографии - это усовершенствование алгоритмов численного факторинга. В настоящее время самым быстрым известным общим алгоритмом является general number field sieve.

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

Answer 4

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

• Crack DES keys
• Crack GSM conversations
• Open source graphics card

Answer 5

Почему нет, Вы пытаетесь создать компьютер с расширенным квантом и запустить на нем Shor's algorithm?

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

Answer 6

Shamir & Tromer предложить подобный подход, с использованием своего рода grid computing:

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