Радужные столы как решение для большого простого факторинга

Question

В объяснениях, которые я читал о криптографии с открытым ключом, говорится, что получается какое-то большое число путем умножения вместе 2 чрезвычайно больших простых чисел.Поскольку факторизация произведения больших простых чисел практически невозможна, у вас есть безопасность.

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

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

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

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

---

Редактировать 2: Как отмечалось в ответах, невозможно сохранить только все простые числа, а тем более все их продукты.

• На этом сайте сказано, что существует около 512-битных простых чисел: ((2 ^ 511) * 1) / (512 log (2)) = 4,35 × 10 ¹⁵¹
• . масса Солнца составляет 2 × 10 ³⁰ кг или 2 × 10 ³³ г
• Это 2,17 × 10 ¹²⁴ простых чисел на грамм солнца.
• Кол-во.из 512 битных чисел, которые могут поместиться в килобайтах: 1 кбайт = 1024 байта = 8192 битов / 512 = 16
• , которые могут уместиться в терабайтах: 16 *1024* 1024 * 1024 = 1,72 × 10 ¹⁰
• Петабайт: 16 *1024* 1024 *1024* 1024 = 1,72 × 10 ¹³
• Exabyte: 16 *1024* 1024 *1024* 1024 * 1024 = 1,72 × 10 ¹⁶

Даже если 1 эксабайт весил 1 грамм, мынигде близко к достижению 2,17 × 10 ¹²⁴ , необходимого для того, чтобы можно было уместить все эти числа в жесткий диск с массой солнца

Answer 1

Из одной из моих самых любимых книг - «Прикладная криптография» Брюса Шнайера

«Если кто-то создаст базу данных всех простых чисел, он не сможет использовать эту базу данных для взлома открытого ключа»алгоритмы? Да, но он не может этого сделать. Если бы вы могли хранить один гигабайт информации на диске весом один грамм, то список только из 512-битных простых чисел весил бы настолько, что он превысил бы предел Чандрасекара и обрушился быв черную дыру ... чтобы вы все равно не могли получить данные "

Другими словами, это невозможно или невозможно, или и то, и другое.

Answer 2

Простые числа, используемые в RSA и Diffie-Hellman, обычно имеют порядок 2 ⁵¹² . Для сравнения, в известной вселенной всего около 2 ²⁵⁶ атомов. Это означает, что 2 ⁵¹² достаточно велико, чтобы назначить 2 ²⁵⁶ уникальных чисел каждому атому во вселенной.

Просто нет способа хранить / рассчитывать столько данных.

---

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

Answer 3

Я думаю, что основная проблема состоит в том, что радужные таблицы, предварительно созданные для определенных алгоритмов, используют довольно «маленький» диапазон (обычно что-то в диапазоне 128 бит).Обычно это не охватывает весь диапазон, но ускоряет процесс грубой силы.Обычно они занимают несколько ТБ места.

При простой разложении простые числа намного больше (для безопасного RSA рекомендуется 2048 бит).Таким образом, радужные таблицы не будут «очень большими», но их невозможно хранить где-либо (используя как миллионы ТБ пространства).

Кроме того, радужные таблицы используют цепочки хеширования, что еще больше ускоряет процесс ( Википедия имеет хорошее объяснение), которую нельзя использовать для простых чисел.