четверг, 31 октября 2013 г.

Помогите с оптимизацией кода перечисления всех возможных GUID

Это перевод Help me optimize this code which enumerates all possible GUIDs. Автор: Реймонд Чен.

Добрый день, мне нужна помощь с оптимизацией этого кода. Он должен создать файл, содержащий все возможные GUID.
class Program {
 public static void Main(string[] args)
 {
  using (var w = new System.IO.StreamWriter("all_guids.txt")) {
   for (long l1 = 0; l1 <= 0xFFFFFFFFL; l1++)
   for (long l2 = 0; l2 <= 0xFFFFFFFFL; l2++)
   for (long l3 = 0; l3 <= 0xFFFFFFFFL; l3++)
   for (long l4 = 0; l4 <= 0xFFFFFFFFL; l4++)
    System.Console.WriteLine(
     new System.Guid(string.Format("{0:X8}{1:X8}{2:X8}{3:X8}",
                                   l1, l2, l3, l4)));
  }
 }
}
Я знаю, что этот код будет выполняться очень долго, поэтому мне нужны советы по его оптимизации.

Подожди-ка, ты же понимаешь, что будь у тебя даже компьютер с процессором на 100 ГГц, способный генерировать новый GUID за один тик процессора, то всё равно этот код работал бы 2128 ÷ 1011 = 3 × 1011 секунд или 1019 лет.

Ага. Вот именно поэтому я и думаю, как бы мне его оптимизировать.

Посмотри на это с такой стороны: предположим, что ты оптимизировал алгоритм так, что он выполняется в зиллион раз быстрее - скажем, всего за год. Тогда твой результирующий файл будет иметь размер в 2128 × 16 = 2132 байт. Это примерно 1027 терабайт. Один терабайт на SSD диске весит примерно 100 грамм. Масса нашей планеты 1024 килограмм. Что означает, что для запуска этой программы тебе нужно где-то взять сто планет размером с Землю и превратить их в SSD диски.

Зачем вообще тебе нужен список всех GUID?

Есть тут один web-сайт, который использует GUID для идентификации ресурсов. Я хотел взять все GUID и запросить web-сервер, есть ли у него что-то интересное по каждому GUID.

Ну тогда не имеет значения как быстро будет выполняться твой код, потому что узкое место - не в нём. Бутылочным горлышком здесь является скорость атакуемого web-сервера (а к этому моменту уже можно сказать, что ты атакуешь web-сервер). Даже если web-сервер мог бы выполнять миллиард обращений в секунду, то всё равно у него уйдёт 1022 лет, чтобы ответить на все твои вопросы.

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

И, знаешь, администраторы сервера могут заподозрить неладное после... семи столетий.

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

Я уже связывался с владельцами сайта, но они не заинтересованы в помощи мне. Так что у меня нет другого выхода, кроме перебора всех GUID.

Ну, твой компьютер наверняка достаточно мощный, чтобы генерировать GUID быстрее, чем их обрабатывает web-сервер. Быть может, ты сможешь обновить свой кабельный модем на более мощный.

А вообще-то, на самом деле, тебе нужно обновить железо с другой стороны. Потому что это они узкое место, а не ты.

"Вот вам миллион долларов на покупку новых серверов. Да, это просто подарок от меня, я не делаю ничего подозрительного. Просто купите железо помощнее и включите его побыстрее, окей?"

Что ж, удачи тебе.

Читать далее: Отчёт об уязвимости, раздвигающий границы криптографии.

2 комментария:

  1. Вот это кадр! :D
    Только я, значит, дочитал у психиатра в блоге про то, что Наполен нынче не в моде, а тут еще про одного пациента!

    Жалко, что новые посты редко появляются... Спасибо за хорошее настроение!

    ОтветитьУдалить
  2. Есть массив целых чисел (пусть это будет uint32_t) размером 100 элементов, заполненный случайными числами. Один человек хотел чтобы ему написали хеш-функцию, которая расчитывала бы из этого массива 32-байтный хеш, при чем функция должна была выдавать уникальный хеш для любого возможного варианата заполнения массива. А ведь знал бы тот человек комбинаторику, то бы не возникало у него таких глупых вопросов.

    ОтветитьУдалить

Можно использовать некоторые HTML-теги, например:

<b>Жирный</b>
<i>Курсив</i>
<a href="http://www.example.com/">Ссылка</a>

Вам необязательно регистрироваться для комментирования - для этого просто выберите из списка "Анонимный" (для анонимного комментария) или "Имя/URL" (для указания вашего имени и ссылки на сайт). Все прочие варианты потребуют от вас входа в вашу учётку.

Пожалуйста, по возможности используйте "Имя/URL" вместо "Анонимный". URL можно просто не указывать.

Ваше сообщение может быть помечено как спам спам-фильтром - не волнуйтесь, оно появится после проверки администратором.

Примечание. Отправлять комментарии могут только участники этого блога.