1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Случайная инициализация состояния матери всех ГПСЧ

Тема в разделе "WASM.CRYPTO", создана пользователем l_inc, 6 дек 2011.

  1. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Всем добрый день. Агнер Фог на своей страничке приводит среди прочих ГПСЧ алгоритм Mother-of-all PRNG's, разработанный неким Джорджем Марсагли. Этот алгоритм я использовал при решении некоторой задачи, специфика которой подразумевает инициализацию именно всего состояния этого ГПСЧ некоторым заранее выбранным случайным значением (т.е. все 160 бит).

    Собственно, проблема в том, что длина цикла этого ГПСЧ согласно Фогу равна примерно 2158, что является примерно четвертью от числа всех возможных состояний (2160). Т.е. оставшиеся три четверти состояний могут давать зацикливание со значительно меньшей длиной. Соответственно, если инициализировать ГПСЧ вышеозначенным некошерным образом, то можно нарваться на цикл длиной в три состояния, что будет ни разу не криптостойко. Вопрос в следующем. Насколько просто (и как) узнать длину цикла (или хотя бы факт принадлежности к циклу с длиной 2158) для некоторого произвольно выбранного стартового состояния данного ГПСЧ?
     
  2. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Зря я, наверное, Марсагли "неким" назвал. А по поводу остального по всей видимости можно действительно инициализировать все 160 бит произвольно кроме двух наборов:
    Код (Text):
    1. DWORD state[] = {0,0,0,0,0};
    2. DWORD state[] = {4294967295,4294967295,4294967295,4294967295,2111119493};
    На обоих наборах ГПСЧ деградирует до периода 1. Любые другие наборы должны приводить к одному из двух возможных циклов длиной 2158, возможно с некоторой ведущей последовательностью, которая повторяться не будет.

    С другой стороны у Марсагли есть статья "Seeds for Random Number Generators", написанная для дилетантов вроде меня с минимумом математики, где он приводит более-менее общий вид complimentary-multiply-with-carry PRNG, где можно задавать желаемое количество произвольно задаваемых бит. У минимального варианта с 256-ю произвольно задаваемыми битами (полное состояние — 288 бит) период превышает 2285.