На этой страничке будет N-ое количество ссылок на страницы Марьяж Интернет Клуба, к сожалению, на этих страницах нет явного указания использованной кодировки (Windows-1251). Поэтому если Вы используете что-либо другое кроме русского Windows 95, то у Вас могут возникнуть некоторые, небольшие, проблемы.

Анализ оригинального генератора раскладов


    Часть исходного кода генератора был опубликован в http конференции "Расклады и люди" одним из авторов программы XaN. В нём отвалился не большой кусок. Восстановленный вариант привожу ниже:


/*+++
 * Алгоритм тасования и раздачи колоды
 +++*/
void shuffle() {
    int i, j, k;

    srand((int)time(NULL));
    for (i=32; i>0; i--) {
        j=rand()%i;
        packbuf[i-1]=pack[j];
        for (k=j; k /* Далее, до XXXX, восстановлено по смыслу */
                    + 1 < i; k++) {
            pack[k] = pack[k+1];
        }
        /* XXXX */
    }
    for (i=0; i<32; i++) pack[i]=packbuf[i];
    // это уже раздача размешанных карт
    for (k=0; k<3; k++) {
        hand[k].cards=10;
        for (i=0; i<10; i++)
            hand[k].card[i]=pack[k*10+i];
        sort_hand=hand+k;
        hsort(sort_hand->cards,less_card,swap_card);
    }
}

Анализ алгоритма

Устанавливает внутренне состояние стандартного ДСЧ в 32-битное представление времени в секундах. Это добавляет пару случайных бит, но, к сожалению, создаёт определённые проблемы "безопасности";

В предположении, что rand() выдаёт "хорошие" равномерно распределённые числа в диапазоне 0..MAX_RAND, этот цикл получает случайную перестановку колоды. Доказательство этого алгоритма см. [Д.Кнут Искусство программирования т.2, 3.4.2.Р, стр. 155];

В предположении, что колода хорошо перемешена, раздавать карты можно как угодно.


    Получаем, что алгоритм корректен, с точностью до качества встроенного ДСЧ. "Случайность" получаемая с системных часов рандомизируется с помощью встроенного ДСЧ и накапливается в массиве "pack".

Анализ "статистических" свойств

Общие слова

    Если предположить, что используется компилятор фирмы Microsoft, то их датчик можно глянуть в файле ports.c. Легко видеть, что с его помощью по выше приведённой программе можно получить примерно 2^32 различных перестановок из 32! (~2^117) возможных. Это не очень хорошо, но не так уж и плохо, т.к. мы накапливаем эти перестановки в массиве "pack". А мизера, как известно всей мировой интеллигенции, должных ходить парами, ну а здесь они будут ходить тройками. :)

Практическая проверка

    Проводится на компиляторе фирмы Microsoft VC 6.0. Ещё не окончена и, честно говоря, после обнаружения проблем с "безопасностью", мне тоскливо её проводить.

Анализ свойств "безопасности"

Общие слова

    Назовём "злоумышленником", человека пытающегося предсказать получаемый программой расклад. Такая уж у меня работа. :)

    "Злоумышленник" может сравнительно легко получить и/или вычислить время на сервере с точностью до 1 сек., т.к. типичная задержка от клиента до сервера не превышает 300 мс. Следовательно, он может получить числа выдаваемые функцией rand(), т.к. согласно POSIX, её результат однозначно обуславливается аргументом функции srand().

    Так что перед "злоумышленником" стоит только одна задача: получить из расклада выдаваемой на экран программой клиентом (~52 бит), порядок карт в колоде (~117 бит). Вариант, когда в начале партии колода приводится в начальное состояние, мы не рассматриваем, как не спортивный. К сожалению, эта задача решается сравнительно легко по 3-12 раздачам см. ниже.

Практическая проверка

    С тестового генератора получили несколько раздач за определённые моменты времени:
hand0: 7п 8п 10к Вк Kк 9ч 10ч Вч 9б Tб; hand1: 9п 10п Вп Дп Tп 8к 7ч 8ч 7б Вб
hand2: Kп 7к 9к Дк Tк Дч Kч 8б 10б Дб;  Прикуп: Tч Kб

Sec: 920126588
hand0: 7п 8п Дп 8к 9к Дк Tч 7б Вб Дб;   hand1: 9п Вп Kп 7к 7ч 8ч Дч Kч Kб Tб
hand2: 10п Tп Вк Kк Tк 9ч Вч 8б 9б 10б; Прикуп: 10к 10ч

Sec: 920126590
hand0: 9п 10п 9к Дк 7ч 9ч Вч Дч Дб Kб;  hand1: 7п 8п Tп 10к Kк Tк Tч 7б 10б Вб
hand2: Дп 7к 8к Вк 8ч 10ч Kч 8б 9б Tб;  Прикуп: Вп Kп

Sec: 920126592
hand0: 7п 9п Вп 8к 10к Вк Kк 8ч Дч 8б;  hand1: 10п Tп 9к Дк 10ч Kч Tч 7б Вб Tб
hand2: 8п Дп 7к 7ч 9ч Вч 9б 10б Дб Kб;  Прикуп: Kп Tк

Sec: 920126594
hand0: 8к 10к Дк Kк 8ч 9ч Вч Дч Tч Tб;  hand1: 8п 9п Вп Дп Kп Tп Вк Kч 9б 10б
hand2: 7п 10п 7к Tк 10ч 7б 8б Вб Дб Kб; Прикуп: 9к 7ч

Sec: 920126596
hand0: 9п Дп Kп Вк Дк 7ч 9ч Вч Tч 7б;   hand1: 7п 8п Вп Tп 7к 9к 10к Tк Дб Kб
hand2: 8к Kк 8ч 10ч Дч Kч 9б 10б Вб Tб; Прикуп: 10п 8б

    Для каждого момента времени вычислили перестановку колоды:
Sec: 920126588
27 18  9 26 23 19 13  8 31 14 25 16 20 15 24 21 17 30 10  1  6  2 29 28  4 12  7 22  0 11  5  3

Sec: 920126590
16  4 13  3  0 17 25 24 20 15  9 30  2 29 26 27 22  8  7  1  5 19  6 14 28 23 11 12 21 31 18 10

Sec: 920126592
 9  0 26 25 30 14 11 18 22 24  6 29  4 13 17  1 27 21 10 19 15  5 12  2 23  3  7 28  8 20 31 16

Sec: 920126594
17  2 15  0  8 14 28  5  6 26 29 27 20 30 22  9  4 16 13  1 19 21 25 24 18  7  3 11 31 10 12 23

Sec: 920126596
31 13 10 24  6  5 15  2  9 19 23 22 16 30 25 21 14 28 18  8 27 11  7 12  3 20  1  4 17  0 26 29

    Потом по прикупам, как наиболее простое вычислили 11 карт [y1], по hand1 раздачи 920126588 ещё 4 карты [y2], и т.д. [y4][y5]. Всего вычисляется 30 карт из 32, что не плохо. :(

    Написать программу осуществляющую эту работу - как два байта переслать. :(

 

Генератор раскладов на основе ГОСТ 28147-89


    В http конференции "Вопросы по программе" одним из авторов программы XaN было предложено присылать альтернативные генераторы. Предлагаемый мною генератор находится здесь.

Описание алгоритма

 

Анализ "статистических" свойств

Общие слова

    В алгоритме используется два ДСЧ по ГОСТ 28147-89 с 64 битным состоянием каждый. Без подмешивания времени они могут создать только ~2^72 различных перестановок колоды из 32!(~2^117) возможных, это значительно лучше оригинального датчика. Но, т.к. всего возможно примерно 2^52 различных раскладов преферанса, то 2^72 можно принять как приемлемую характеристику.

    На каждой сдаче, к внутреннему состоянию обоих ДСЧ добавляется преобразованное по ГОСТ 28147-89 состояние тактового генератора ЦП, что при предположении о случайности времени розыгрыша сдачи +/- 8 сек, добавляет около 20 бит случайной информации. Т.к. ДСЧ работают на разных ключах можно предположить, что коэффициент корреляции между ними порядка 2^-60 после 3-4 сдач (подмешиваний).

    В целом, мне кажется, что данный генератор раскладов будет получать значительно более случайные расклады по сравнению с ручной тасовкой и сдачей. О мизерах парами придётся забыть. Но я не очень понимаю, как снизить случайность без снижения "безопасности" [сейчас то уже понимаю].

Практическая проверка

    Проводится на компиляторе фирмы Microsoft VC 6.0. Ещё не окончена.

    Если кто либо обнаружит проблемы, буду весьма признателен (в размере ящика "Балтики", но в Москве :).

Анализ свойств "безопасности"

Общие слова

    Назовём "злоумышленником", человека пытающегося предсказать получаемый программой расклад. Такая уж у меня работа. :)

    В общем, если "злоумышленнику" известно всё текущее состояние алгоритма расклада:


    То после сдачи он, с существенной вероятностью, сможет поддержать своё знание, т.к. ему будет достаточно выяснить, как изменилось состояние ДСЧ. Состояние ДСЧ изменяется при помощи времени ЦП в тактах, а по анализу обмена с сервером можно попробовать восстановить время сдачи с точностью порядка 1 мс. Следовательно, неизвестно примерно 16-18 бит. После сдачи "злоумышленник" видит свои карты (25 бит), следовательно, известной информации больше неизвестной и можно попробовать (Примечание: в экспериментах с оригинальным датчиком, для однозначного восстановления требовалось превышение известной информацией над неизвестной в 3-6 раз).

    Что рекомендовать, для дополнительной защиты:

Практическая проверка

    Если кто либо обнаружит проблемы "безопасности", буду весьма признателен (в размере не менее ящика "Балтики" :).


Ваши комментарии и благодарности присылайте по адресу:leo@sai.msu.ru

 

Эта страница создана с помощью: Netscape Navigator Gold, Emacs, XVScan и GIMP.