Таблицы радуги как решение большого главного факторинга
В объяснениях я читал о шифровании с открытым ключом, сказано, что некоторое большое количество придумано путем умножения вместе 2 чрезвычайно больших начал. Начиная с факторинга продукта больших начал является почти невозможно трудоемким, у Вас есть безопасность.
Это походит на проблему, которая могла быть тривиально решена с таблицами радуги. Если Вы знаете приблизительный размер используемых начал и знаете, что существует 2 из них, Вы могли быстро создать таблицу радуги. Это была бы могущественная большая таблица, но это могло быть сделано, и задача могла быть параллелизирована через аппаратные средства.
Почему таблицы радуги не являются эффективным способом разбить открытый ключ crypto на основе умножения больших начал?
Отказ от ответственности: очевидно, десятки тысяч сознательных людей сумасшедшей умной безопасности, только оказалось, пропускали в течение многих десятилетий, что я продумал днем. Я предполагаю, что неправильно понимаю это, потому что я читал упрощенные объяснения неспециалиста (например: если больше чем 2 числа используются), но я не знаю достаточно все же для знания, где мой разрыв знаний.
Править: Я знаю, что "таблица радуги" касается использования предрасчетных хешей в справочной таблице, но вышеупомянутое походит на нападение таблицы радуги, таким образом, я использую термин здесь.
Редактирование 2: Как отмечено в ответах, нет никакого способа сохранить просто все начала, а тем более все их продукты.
- Этот сайт говорит, что существует об этом много начал на 512 битов: ((2^511) * 1) / (512 журналов (2)) = 4.35 × 10151
- Масса солнца составляет 2 × 1 030 кг или 2 × 1 033 г
- Это - начала 2.17 × 10124 на грамм солнца.
- Количество. из чисел на 512 битов, которые могут поместиться в килобайт: 1 Кбит = 1 024 байта = 8 192 бита / 512 = 16
- Это может поместиться в терабайт: 16*1024*1024*1024 = 1.72 × 1010
- Петабайт: 16*1024*1024*1024*1024 = 1.72 × 1013
- Эксабайт: 16*1024*1024*1024*1024*1024 = 1.72 × 1016
Даже если 1 эксабайт весил 1 грамм, мы нигде не близко к достижению 2.17 × 10124, должен был смочь вместить все эти числа в жесткий диск с массой солнца
3 ответа
Из одной из моих любимых книг, «Прикладная криптография» Брюса Шнайера
«Если бы кто-то создал базу данных всех простых чисел, разве он не будет в состоянии ли использовать эту базу данных для взлома алгоритмов с открытым ключом? Да, но он не может этого сделать. Если бы вы могли хранить один гигабайт информации о накопителе весом один грамм, затем список всего 512-битных простых чисел будет весить так много, что превысит предел Чандрасекара и рухнет в черная дыра ... так что вы все равно не сможете получить данные "
Другими словами, это невозможно или неосуществимо, или и то, и другое.
Я думаю, что основная проблема заключается в том, что предварительно сгенерированные для определенных алгоритмов радужные таблицы используют довольно "небольшой" диапазон (обычно что-то в диапазоне 128 бит). Обычно это не охватывает весь диапазон, но ускоряет процесс грубой силы. Обычно они занимают некоторую ТБ дискового пространства.
При разложении на простые множители простые числа намного больше (для безопасного RSA рекомендуется 2048 бит). Таким образом, радужные таблицы не были бы «очень большими», но их невозможно было бы где-либо хранить (они занимали бы миллионы ТБ пространства).
Кроме того, в радужных таблицах используются цепочки хеширования, которые еще больше ускоряют процесс ( Википедия дает хорошее объяснение), которые нельзя использовать для простых чисел.
Простые числа, используемые в RSA и Диффи-Хеллмана, обычно имеют порядок 2 512 . Для сравнения: в известной Вселенной всего около 2 256 атомов. Это означает, что 2 512 достаточно велико, чтобы присвоить 2 256 уникальных номеров каждому атому во Вселенной.
Просто невозможно сохранить / вычислить такой объем данных.
В стороне, я предполагаю, что вы имеете в виду «большую таблицу простых чисел» - радужные таблицы специально созданы для хешей и не имеют здесь реального значения.