В поисках криптостойкого ГПСЧ

[Scratch]

Все никак не соберусь написать статью о fortuna ) Вот там ГПСЧ так ГПСЧ

[NeverWalkAloner]

Сам генератор там вроде несложный. Похож на CTR, только вместо блочного шифра, хэш функции используются. А вот функции сбора и хранения энтропии это да. Тема для отдельного топика.
А вообще соберись уже) Очень интересно про него будет подробности почитать.

[Scratch]

Там вообще два вида генератора, один основной с очень красивой самокоррекцией на случай подставы, и кучка второстепенных, которые держат энтропию до поры до времени. Единственный минус — надо постоянно его подкармливать, но это не страшно. Можно и счетчиком тикать.
А статью написать то несложно, просто у меня в голове очень давно крутится один большой проект, который либо я буду делать сам, либо опишу его идею в виде цикла статеек (в т.ч. и про фортуну) и заброшу. Так что я пока в терзаниях )

[x0wl]

Я не в теме, а что за Fortuna?

[NeverWalkAloner]

Целый комплекс алгоритмов, предназначенный для создания криптографически стойкого ГПСЧ. Разработан Брюсом Шнайером и Нилом Фергюссоном. Хорошее описание есть в их совместной книге «Практическая криптография».

[DrSmile]

В последнем варианте вы возвращаете только один бит результата (ну или несколько). Разве, если делать то же самое для Мерсенна и сдвигового регистра, это не увеличит криптостойкость?

[NeverWalkAloner]

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

[Nokta_strigo]

Надо ещё добавить, что есть и другие стойкие и не очень генераторы ПСП.
Интересно, кстати, а если на выход того же регистра сдвига добавить хэш — функцию (т.е. накапливать например 160 бит информации и брать SHA1 от этого) это сильно увеличит его криптостойкость? По скорости это наверно получится как CTR.

[NeverWalkAloner]

По идеи, при добавлении хэш-функции к тому же самому Вихрю Мерсенна получится криптостойкий ГПСЧ. Скорость думаю будет повыше чем у блочного шифра, все таки хэш функции гораздо быстрее.
Просто для меня такое решение имеет один минус. Возможно, это весьма субъективно, но все же. Используя сразу два инструмента: ГПСЧ и хэш-функцию мы усложняем всю схему. Соответственно больше шансов на ошибку, меньше шансов учесть все возможные угрозы. Поэтому я как то в этом плане консервативен, чем проще тем лучше. Для меня BBS вообще идеальный генератор, с которым никакая fortuna не сравнится:)

[PsyHaSTe]

Как я уже отмечал выше, если атакующий имеет 624 числа сгенерированных с помощью Вихря Мерсенна этого достаточно для того чтобы восстановить все внутреннее состояние и предугадывать с вероятностью 100% все генерируемые в последующем числа.

А что если каждые 600 выборок в таком случае менять seed на случайный другой? Тоже своего рода каскад сделать. Разве не поможет?

[NeverWalkAloner]

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

[PsyHaSTe]

Ну дак это не важно. Что-то вроде

class CryptoMercenVortex
{
   private const int MaxCalls = 600;
   private Random _rand = new Random();
   private int _calls = 0;
   private MT19937 _mercen = new MT19937();
   
   public int Next()
   { 
      if (_calls++ > MaxCalls )
      {
         _mercen = new MT19937(_rand.Next());
         _calls = 0;
      }
      return _mercen.Next();
   }
}

длина последовательности будет влиять только на то, сколько раз будет пересоздаваться внутренний обычный mercen.

[NeverWalkAloner]

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

[PsyHaSTe]

Ясно, спасибо за ответ (репы нет, спасибо пишу «ручками», по старинке).