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

Я изучаю 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


java supercomputers
person Ryan Amos    schedule 25.06.2011    source источник
comment
@ Митч Он там, как бы похоронен. Я должен переместить код в pastebin. На суперкомпьютере с примерно 100 ядрами (у меня может быть только 8, или у меня может быть 400+, но я предполагаю, что 100), можно ли будет выполнить около 2^135 вычислений за 20 дней?   -  person Ryan Amos    schedule 25.06.2011

Ответы (5)


arrow_upward
4
arrow_downward

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

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

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

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

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

person bcoughlan    schedule 25.06.2011
comment
Да, радужные таблицы не генерируют весь набор возможных ключей, они обычно берут словари/списки слов и генерируют из них ключи, чтобы их можно было хранить и искать. WPA предлагает некоторую защиту от этого, хэшируя ключ против SSID перед шифрованием (это означает, что для каждого SSID необходимо создавать радужные таблицы). - person bcoughlan; 25.06.2011
comment
Спасибо за помощь! Я посмотрю больше на радужные таблицы. - person Ryan Amos; 25.06.2011

arrow_upward
4
arrow_downward

В идеальном мире это примерно:

2135 операций ÷ 20 дней ÷ 24 часа/день ÷ 60 мин/час ÷ 60 сек/мин ÷ 100 ядер = 1032 операций на секунд на ядро ​​(Гц/ядро), если моя математика не ошиблась.

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

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

person user541686    schedule 25.06.2011
comment
Что делать, если я делаю несколько вычислений одновременно (потоки). Это что-то меняет? - person Ryan Amos; 25.06.2011
comment
@Ryan: ... эй, ты мне скажи. Допустим, у вас 1 ТРИЛЛИОН потоков на ядро. Что получится, если 10^32 разделить на один триллион? Насколько это близко к 10^10...? - person user541686; 25.06.2011
comment
Вы будете выполнять один расчет на одном ядре, так что это ускорит работу МАКСИМУМ в 100 раз. Еще далеко - person bcoughlan; 25.06.2011
comment
@Mehrdad Полагаю, я слишком надеюсь :P - person Ryan Amos; 25.06.2011
comment
@ Райан Амос - математика не лжет. - person Stephen C; 25.06.2011
comment
@Stephen C: я хорошо знаю об этом. - person Ryan Amos; 25.06.2011
comment
Так почему же вы сказали Полагаю, я слишком много надеюсь? Надежда не имеет к этому никакого отношения. Как я уже сказал, математика не лжет. (Извините, но мне трудно смириться с тем, что кто-то здесь не способен самостоятельно произвести этот простой расчет.) - person Stephen C; 25.06.2011
comment
@Stephen C: я провел расчеты и нашел необходимое количество операций. Я подумал, что это немного нелепо, но когда я рассказал об этом отцу, он сказал, что это возможно. Обратите внимание, что мой папа имеет докторскую степень по математике. Поэтому я решил, что я также могу проверить SO, чтобы узнать, потратил ли я свое время на написание программы. Это так неправильно? Кроме того, я НИКОГДА не занимался исследованиями суперкомпьютеров. - person Ryan Amos; 25.06.2011
comment
@ Райан Амос - он должен быть чистым математиком. Или, возможно, он просто тянул тебя за ногу :-) - person Stephen C; 25.06.2011

arrow_upward
3
arrow_downward

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

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

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

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

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

person Community    schedule 25.06.2011
comment
Так что ответ таков: мне не следовало так долго ждать, чтобы начать этот проект: я должен был начать 3 миллиарда лет назад. - person Ryan Amos; 25.06.2011
comment
Да, и каждая потерянная секунда — это еще несколько миллиардов потерянных вычислений, так что приступайте к работе! - person ; 25.06.2011
comment
+1 (И немного от себя) Число на самом деле выглядит довольно крошечным, когда написано как 43556142965880123323311949751266331066368. Я имею в виду, никаких забавных показателей, и я могу написать его на одной строке бумаги. Просто напишите 40 миллиардов (американское, а не английское) 3 раза подряд, и вот оно ;-) ... истинная внушительность больших чисел не очевидна без какого-то масштаба, чтобы просто показать, как они могут работать только с такие понятия в теории. (Гораздо проще удвоить [теоретическое] число, чем удвоить скорость или мощность машины.) - person ; 25.06.2011
comment
@pst Запишите это в подсчетах: D. И я согласен, удивительно, как растут большие числа: экспоненциально. Попробуйте запустить генератор ключей, который я написал. Оно прекрасно это демонстрирует. Поначалу довольно быстро пролетает первый ряд. Прохождение второго ряда занимает в 256 раз больше времени, но все же управляемо. В 3-м и 4-м рядах вы просто говорите Когда это закончится???. - person Ryan Amos; 25.06.2011

arrow_upward
3
arrow_downward

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

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

  2. и так как в сутках 86400 секунд (округлить до 217)

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

  4. и 100 ядер (округлить до 27)

тогда... 232 * 217 * 25 * 27 == 2( 32 + 17 + 5 + 7) == 261 вычисления... итак:

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

(С приведенными выше цифрами это займет 279 дней...)

person Community    schedule 25.06.2011
comment
2^135 звучало немного за пределами диапазона, но я должен был проверить, просто чтобы быть уверенным :D Спасибо за помощь - person Ryan Amos; 25.06.2011

arrow_upward
1
arrow_downward

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

person Dax Fohl    schedule 25.06.2011
comment
Как это связано? Мы еще не перешли на 6-й этап эволюции: en.wikipedia.org/wiki/< /а> - person Ryan Amos; 25.06.2011
comment
даже половина не понадобится, это немного преуменьшение (или преувеличение?) ;-) - person ; 25.06.2011
comment
@pst @Dax: 1/2 будет 2 ^ 239 ;) Вам потребуется около 2 ^ 240 * 2 ^ -100 атомов, при условии, что 1 атом на вычисление - person Ryan Amos; 25.06.2011
comment
Конечно, если мы сможем использовать каждый атом во Вселенной для выполнения вычислений, они смогут вычислить способ создания новых атомов из эфира. Так что да, я думаю, это не связано. - person Dax Fohl; 26.06.2011