Это практично на маленьком суперкомпьютере?

Question

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

Конечно, 64-битное шифрование RC4 имеет 2 ^ 64 возможных ключей, так что это будет означать ~ 2 ^ 128 сравнений. Кроме того, для каждого сравнения необходимо сгенерировать 10 байтов, что составляет примерно 265 циклов. (256 для инициализации RC4, 10 для самих байтов).

Вниз к делу:

На суперкомпьютере с примерно 100 ядрами возможно ли выполнить около 2 ^ 135 вычислений за 20 дней?

(20 дней - это предел, пока меня не выкинут. У меня может быть только 8, или 400+, но я предполагаю, что 100 ядер).

Если это что-то значит, моя программа написана на Java. http://pastie.org/2118864

Answer 1

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

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

Допустим, ваша программа может сравнивать n ключей в секунду. Таким образом, идеальная (то есть линейная) 100-ядерная система будет вычислять 100n ключей в секунду. Для сравнения всех ключей (в худшем случае, реалистичным будет половина этого) потребуется (2^135/100n)/86400 дней.

Если n равно 1000, это займет 5041220250680569829087031221211 дней, что примерно в 100 тысяч миллионов раз больше, чем некоторые оценки возраста Вселенной.

Так что я собираюсь сказать ... нет :) Алгоритмы криптографии предназначены для такого рода атак. Кроме того, Java будет последним языком, выбранным при написании такого приложения: p

Answer 2

В идеальном мире вокруг:

2 ¹³⁵ операции ÷ 20 дней ÷ 24 часа / день ÷ 60 мин / час ÷ 60 сек / мин÷ 100 ядер = 10 ³² операций в секунду на ядро ​​(Гц / ядро), при условии, что моя математика не выключена.

Вам потребуется 10 ³² Гц ядра, которые выполняют однократное вычисление за такт.Обычно, это должно быть несколько.Это ... не очень достижимо в данный момент, чтобы не сказать больше.Лучшее, что вы бы достигли с суперкомпьютером, это, вероятно, около общей области ~ 10 ГГц = 10 ¹⁰ Гц / ядро, если вам повезет.

(И все это игнорирует закон Амдала ...)

Answer 3

Люди не понимают, насколько большим может быть число.

2 ^ 135 примерно 4e40, хорошо, 43556142965880123323311949751266331066368.

Предположим, у вас есть компьютер, способный выполнить 1 exaflop, намного быстрее, чем у нас сегодня. Таким образом, если бы он мог выполнять одно из этих вычислений в КАЖДОЙ операции с плавающей запятой, то он мог бы выполнить 10 ^ 18 из них в секунду. Это все еще оставляет вам 4e22 секунды. Примерно 31536000 секунд в год, поэтому вашему маленькому предприятию все равно потребуется больше 1-15 лет.

Хорошо, в зависимости от того, с кем вы говорите, вселенной где-то от 6000 лет до 13 миллиардов лет или около того.

Ява или нет, ответ - нет. (Скайнет уже здесь?)

Answer 4

Эти цифры являются несколько фикциями.Они в основном, чтобы сделать точку.Математика чрезмерно оптимистична, чтобы упростить ее.

1. Одно ядро ​​может обрабатывать 4 миллиарда (2 ³² ) операций в секунду (это чрезвычайно оптимистичнорисунок)

2. и, поскольку существует 86400 секунд (до 2 ¹⁷ ) в день

3. и 20 дней(округление до 2 ⁵ )

4. и 100 ядер (округление до 2 ⁷ )

затем ... 2 ³² * 2 ¹⁷ * 2 ⁵ * 2 ⁷ == 2 ^{(32+ 17 + 5 + 7)} == 2 ⁶¹ расчеты ... так:

Нет шансов.Даже близко не близко.Количество оставшихся вычислений настолько ошеломляет Я даже не могу понять, что это на самом деле .Извините: -)

(с приведенными выше цифрами это займет 2 ⁷⁹ дней ...)

Answer 5

Во вселенной есть по крайней мере 2 ^ 240 атомов, так что вам даже не понадобится половина из них, чтобы вычислять это даже по одному вычислению в день. Опять же, разве Билл Гейтс однажды не сказал: «Кому когда-нибудь понадобится больше половины атомов во вселенной?»