На этой страничке будет 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);
}
}
Анализ алгоритма
- srand((int)time(NULL));
Устанавливает внутренне состояние стандартного ДСЧ в 32-битное представление времени в секундах. Это добавляет пару случайных бит, но, к сожалению, создаёт определённые проблемы "безопасности";
- Цикл: for (i=32;
i>0; i--) {
В предположении, что rand() выдаёт "хорошие" равномерно распределённые числа в диапазоне 0..MAX_RAND, этот цикл получает случайную перестановку колоды. Доказательство этого алгоритма см. [Д.Кнут Искусство программирования т.2, 3.4.2.Р, стр. 155];
- Цикл: for (k=0; k<3; k++) {
В предположении, что колода хорошо перемешена, раздавать карты можно как угодно.
Получаем, что алгоритм корректен, с точностью до качества
встроенного ДСЧ. "Случайность" получаемая с системных часов рандомизируется с помощью встроенного ДСЧ и накапливается в
массиве "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
было предложено
присылать альтернативные генераторы. Предлагаемый мною генератор находится здесь.