Случайные и не очень числа
November 13th, 2008 Posted in ТехнологииНа конкурсе женской логики победил
генератор случайных чисел.
Генератор случайных чисел знаком каждому программисту и применяется повсеместно. Наверняка каждый на заре обучения программированию написал программку, заполняющую экран случайными точками. Обычно получается что-то такое.
Нетрудно видеть, что экран заполняется неравномерно. Встроенные в языки программирования генераторы потому и называет "генераторами псевдо-случайных чисел". Алгоритм достаточно примитивен. Каждое новое число рассчитывается на основании предыдущего числа последовательности.
Насколько важна разница между генераторами псевдослучайных и случайных чисел? Скажем у вас в плейлисте 100 песен. Плейер каждый раз после второй песни будет играть тридцать девятую, а после нее четырнадцатую. Ну и что, все равно плейлист поменяется быстрее, чем этот порядок запомнится. Ерунда.
Однако бывают ситуации более серьезные, где использование неправильного (слабого) алгоритма ставит под угрозу всю систему. Рассмотрим, например, игровые веб-сайты, где люди играют в покер на деньги. Вот эта статья рассказывает, как группе программистов удалось обнаружить уязвимость в алгоритме раздачи карт игрового сайта PlanetPoker. Это проще, чем может показаться на первый взгляд.
9 Responses to “Случайные и не очень числа”
By Bytamine on Nov 14, 2008
Ну это же легко обходится. Достаточно просто каждый раз инициализировать рандомайзер заново, например передавая текущее время.
By Алексей on Nov 14, 2008
У Кнута в книге “искусство программирования” целый том посвящен алгоритмам генерирования случайных чисел. Так что согласен, задача не тривиальная.
By ArkanoiD on Nov 14, 2008
Ну, открыли америку! Качество генератора случайных чисел – одна из основных проблем реализации криптографической защиты.
By Сергей Корнилов on Nov 15, 2008
@ArkanoiD:
для меня эта тема новая – вот и заинтересовался. Не думал, что этой уязвимостью так легко воспользоваться.
By Gregory on Nov 15, 2008
Существуют hardware’ные генераторы случайных чисел основанные на различных физических явлениях.
Такие генераторы выдают взаправдашние случайные числа.
Так что, PlanetPoker схалявили.
By Игорь on Nov 16, 2008
ПланетПокер не схалявили, а попытались схитрить, скорее всего. Большинство электронных карточных игр почти не используют генераторов случайных чисел для раздачи карт. Карты раздаются по сложным алгоритмам, обеспечивающим у играющего ощущение, что ему везет, при этом не давая играющему серьезно выигрывать. Так что, “генератор случайных чисел” на покерном сайте — нонсенс. Не должно его там быть. Но, если есть алгоритм, его можно взломать… Побочный эффект, однако!
Кстати, генератор настоящих случайных чисел имеет право взять, и нарисовать на экране фигуру Лиссажу, в приведенном в начале примере. Ну просто может так случайно совпасть. Или еще одна проблема настоящих генераторов настоящих случайных чисел, о которой слышал в прошлом подобном обсуждении — настоящий рэндом имеет полное право выдать два-три десятка одинаковых значений подряд. Чисто случайно. Т.е. требуется дописывать анализаторы, которые проверяют генератор на такие вот ляпы…
By Игорь on Nov 16, 2008
Да, кстати, если делать что-нибудь типа “Randomise(-Time)” перед каждым рэндомом, то большинство генераторов случайных чисел заполнят экран прямыми линиями, ну или иначе демонстрируют полное отсутствие случайности. Так что, слишком часто заставлять генератор менять “точку отсчета” тоже неправильно.
By Слава on Nov 16, 2008
Молодцы, не поленились проверить все это. Интересно заработали ли они на этом.
By NRozina on Jan 3, 2009
Если я все правильно поняла — то генератор случайных чисел — это тоже алгоритм и его тоже можно “обмануть”.