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

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

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

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

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

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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

Существует просто нет возможности хранить/вычислять столько данных.

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

Ответ 3

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

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

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