Что общего у любителей проходить видеоигры на скорость, азартных игроков и криптографов? Они зависят от случайных чисел. От перетасовки музыки до шифрования интернета, случайные числа — важнейшая часть современной жизни. И мы, как правило, полагаемся на компьютеры, которые генерируют их.
Это заставляет задуматься: как именно компьютеры это делают? Скорее всего, вы когда-либо использовали генератор случайных чисел. Языки программирования очень упрощают это действие. Например, в Ruby достаточно вызвать rand .
На первый взгляд, создание случайных чисел может показаться простым. В конце концов, числа на компьютере — это набор единиц и нулей. Компьютеру просто нужно случайным образом выбрать 1 или 0 и повторить это столько раз, сколько необходимо.
Человеку не составит труда сделать это:
100101011010010110001101
Примечание: ведутся споры о том, может ли человек демонстрировать по-настоящему случайное поведение. Но это выходит за рамки данной статьи.
Тем не менее, все еще остается вопрос: как компьютер случайно выбирает между нулем и единицей? Ответ оказывается довольно сложным. Он коренится в таких темах, как рекурсивные алгоритмы, компьютерное оборудование и немного — теория хаоса.
Генераторы случайных чисел в лотереях ГСЧ
Если это звучит для вас интересно, тогда погрузимся глубже.
Как компьютеры генерируют случайные числа?
Простой ответ на этот вопрос заключается в том, что они не могут. По крайней мере, не сами по себе.
Люди создали компьютеры, чтобы они были тем, чем не являемся мы, — полностью логическими машинами. Случайность не в их природе. В конце концов, вы же не хотите, чтобы сервер спонтанно решил не следовать логике приложения.
По своей сути компьютеры — простые машины, которые принимают данные и выдают их обратно. Чтобы компьютеры могли генерировать случайные числа, им нужен внешний источник случайности. И этот источник будет варьироваться в зависимости от того, каким генератором случайных чисел вы решите воспользоваться.
Вероятно, последнее предложение вызвало несколько растерянных взглядов. Что подразумевается под “своего рода генератором случайных чисел”? Разве они не все одинаковы?
Не совсем. Существует два основных типа генераторов случайных чисел.
Примечание: далее названия генераторов случайных чисел будут использоваться в сокращении.
Генератор псевдослучайных чисел (ГПСЧ)
Наиболее распространенный тип — генератор псевдослучайных чисел. Он называется псевдослучайным, потому что не создает “по-настоящему” случайных чисел.
“ГПСЧ — это алгоритмы, которые могут автоматически создавать длинные ряды чисел с хорошими случайными свойствами, но в конечном итоге последовательность повторяется”.
Несмотря на то, что ГПСЧ следуют определенной схеме, эта схема не прослеживается людьми. Поэтому они “достаточно хороши” для большинства случаев, к примеру для видеоигр.
Генераторам псевдослучайных чисел для работы необходимы две составляющие:
Генератор случайных чисел для Инстаграм розыгрыша или конкурса
- алгоритм генерации случайных чисел;
- семя.
Первоначально в качестве алгоритмов ГПСЧ применялись линейные конгруэнтные генераторы. Это рекурсивные алгоритмы, которые генерируют следующую величину на основе предыдущей. Вот почему этим алгоритмам требуется “семя” (seed) или начальное значение. О семени можно думать как о фрагменте случайности.
Однако со временем на смену линейным конгруэнтным генераторам пришел вихрь Мерсенна, и он по сей день остается самым популярным алгоритмом ГПСЧ.
Хотя псевдослучайные числа на самом деле не случайные, есть множество причин ими пользоваться. Во-первых, они быстры и дешевы в создании. Кроме того, поскольку ГПСЧ — всего лишь алгоритмы, их можно протестировать и убедиться, что они всегда будут работать правильно.
Вот почему в большинстве, если не во всех, языках программирования случайные числа по умолчанию генерируются именно через ГПСЧ.
Но у генерации псевдослучайных чисел есть и свои недостатки. ГСПЧ работают, потому что случайны для неподготовленного глаза. Однако, если бы вы знали начальное значение для определенной последовательности ГПСЧ, то могли бы предсказать, какие числа будут следующими.
Этой уязвимостью часто пользуются любители ускоренного прохождения видеоигр — они называют это манипулированием ГСЧ. Они заставляют игру работать предсказуемо, чтобы пройти ее как можно быстрее. К счастью, если семя видеоигры будет скомпрометировано, ничего особенного не случится. В этом нет ни вреда, ни зла.
Но бывают случаи, когда предсказание случайных чисел имеет гораздо большее значение. Например, создание ключей безопасности.
Если злоумышленник выяснит исходное значение, используемое для создания ключей RSA в сертификатах TLS, он потенциально может расшифровать сетевой трафик. Это означает, что он сможет получать пароли и другую личную информацию, передаваемую через интернет.
В таких ситуациях нужен более безопасный способ получения случайных чисел.
Генератор истинно случайных чисел (ГИСЧ)
Как вы можете догадаться, истинно случайные числа непредсказуемы и не следуют шаблону.
Но как компьютер может достичь этого? Как было указано ранее, компьютерам требуется внешний источник случайности. В случае ГПСЧ, это было семя. В случае ГИСЧ, это энтропия.
Теория хаоса и термодинамика выходят далеко за рамки данной статьи. Достаточно сказать, что энтропия — это чистый нефильтрованный хаос. И лучший источник этого хаоса — сам компьютер.
Компьютер не может функционировать случайным образом, но составляющие его части — могут. Компьютер — это сложная система со множеством движущихся частей и изменчивостью. Тепловой шум, фотоэффект и другие квантовые явления происходят постоянно.
Компьютерное оборудование — не единственный источник энтропии. Также можно использовать движения мыши и клавиатуры пользователя.
Но хаос был бы бесполезен, если бы его нельзя было обуздать. К счастью, инженеры-аппаратчики придумали, как это сделать. Посредством сложной схемы аппаратных микросхем и компонентов, компьютеры могут преобразовывать этот физический шум в цифровые нули и единицы.
Один из наиболее очевидных вариантов применения ГИСЧ — цифровые азартные игры. Бросание костей, перетасовка карт и вращение колеса рулетки — все это зависит от того, чтобы быть неопределимым. Хотя он часто используется при опросах общественного мнения, призыве на военную службу и отборе присяжных, а также там, где случайность используется как метод справедливости.
В действительности сферы применения ГИСЧ довольно ограничены, поскольку у них есть свой набор недостатков. Во-первых, они медлительны. Хотя это варьируется, ГИСЧ может выдавать только небольшое количество бит в секунду.
Кроме того, ГИСЧ не всегда надежны. Компьютерам требуется достаточное количество энтропии для производства истинно случайных чисел. Но суть случайности в том, что она возникает случайным образом. Простаивающий или новый сервер не сможет генерировать числа настолько же качественно, как активный.
Эта ненадежность создает угрозу безопасности при использовании ГИСЧ для создания криптографических ключей. В 2012 году в исследовательской работе под названием Ron was Wrong, Whit is Right обнаружилось, что тысячи SSL-ключей небезопасны. Хотя основная причина неизвестна, обычно считается, что это результат ошибочной генерации случайных чисел.
Криптографически стойкий генератор псевдослучайных чисел (КСГПЧ)
Из-за недостатков ГИСЧ и ГПСЧ криптографы разработали гибридный подход, называемый криптографически защищенной генерацией псевдослучайных чисел. Этот метод направлен на обеспечение скорости ГПСЧ с гарантией безопасности ГИСЧ.
КСГПЧ прост в теории. В нем применяется высококачественный источник энтропии для получения начального значения, которое дальше вводится в алгоритм, а тот затем выдает безопасные случайные числа.
Проще говоря, он задействует ГИСЧ при создании начального значения для ГПСЧ. Если все сделано правильно, КСГПЧ гарантирует, что начальное значение действительно случайное, и ГПСЧ не может быть скомпрометирован или изменен.
Пример этому — /dev/random в системах Unix и Linux.
Несмотря на преимущества КСГПЧ, здесь, как и везде в технологической отрасли, нельзя гарантировать полную безопасность.
Завершающие мысли
Многие разработчики программного обеспечения не понимают сложности, связанной с генерацией случайных чисел. Это свидетельствует в пользу архитекторов, которые создали существующую систему. От инженеров-аппаратчиков, которые разрабатывали чипы для преобразования шума в данные, до разработчиков ядра и языков программирования, которые преобразовали эти данные в простые для использования API.
Возможно, в следующий раз, когда вы будете играть в видеоигру, слушать музыку в случайном порядке или просто генерировать произвольное число у себя в коде, вы лучше станете понимать волшебство, которое происходит под капотом.
- Как сгенерировать настоящие случайные числа в Solidity с блокчейном
- Векторы — прошлое ИИ, хэши — будущее
- NeuralHash от Apple: принцип работы и слабые места
Источник: medium.com
Случайности не случайны, Или как компьютеры генерируют случайные числа
Генератор случайных чисел — это намного сложнее, чем кажется.
Как думаете, что общего в компьютерных гонках, азартных играх и криптографии? На первый взгляд кажется, что ничего. Но на самом деле все они зависят от случайных чисел. От прослушивания музыки до шифрования всего Интернета — случайные числа являются важной частью жизни современного человека. И чаще всего мы полагаемся на компьютеры, которые генерируют их для нас.
Это заставляет задуматься: а как именно компьютеры генерируют случайные числа?
Если вы занимались программированием, то наверняка использовали в своем коде генератор случайных чисел. Для этого в Ruby достаточно вызвать «rand», а в Python — «random ()». Создание ряда случайных чисел может показаться простым. В конце концов числа на компьютере — это набор единиц и нулей. Машине просто нужно случайным образом выбрать 1 или 0 и повторить это столько раз, сколько нужно.
Даже мы, люди, можем сделать это легко и просто на листе бумаги.
Однако если копнуть глубже, то мы создали компьютеры, чтобы стать теми, кем не являемся — полностью логическими устройствами. Получается, случайность противоречит их природе. Ну кто захочет, чтобы сервер спонтанно решил не следовать логике приложения?
По своей сути компьютеры — это простые машины, которые принимают данные и выводят их обратно. И чтобы эти машины могли генерировать случайные числа, им нужен внешний источник случайности. Этот источник будет зависеть от того, какой генератор случайных чисел вы захотите использовать. Таких генераторов два — конечно, если говорить об основных.
Первый и самый распространенный тип называется «генератор псевдослучайных чисел (ГПСЧ)». Как следует из названия, он не создает «истинных» случайных чисел. Чтобы сгенерировать с помощью него число, понадобится единственное начальное значение, откуда последует псевдослучайность. Алгоритмы генерации, используемые для ГПСЧ, включают в себя «метод извлечения квадратов», «линейный конгруэнтный метод», «регистр сдвига с линейной обратной связью» и «вихрь Мерсенна».
ГПСЧ автоматически создает длинные серии чисел с хорошими случайными свойствами и делает это быстро и дешево — в этом его преимущества. Но есть и очевидный минус: с ограниченными ресурсами любой ГПСЧ рано или поздно зацикливается и начинает повторять одну и ту же последовательность чисел. Однако чаще всего этот шаблон не воспринимается людьми, что делает ГПСЧ подходящим для использования в видеоиграх и программировании.
Нельзя не сказать о том, что слабым местом ГПСЧ все-таки пользуются: например, любители гонок, которые манипулируют ГСЧ и заставляют игру работать предсказуемо, чтобы пройти ее как можно скорее. Есть случаи, когда предсказание случайных чисел имеет более серьезные последствия. Зная начальное значение, злоумышленник может угадать сгенерированный пароль и получить доступ к личным данным пользователя.
Второй тип генератора — генератор «истинно» случайных чисел (ГИСЧ или TRNG). В качестве внешнего источника случайности он использует энтропию. Не углубляясь в теорию хаоса и термодинамику, отметим, что энтропия — это чистый нефильтрованный хаос. И лучший источник этого хаоса — сам компьютер. Компьютер не может работать случайным образом, чего не скажешь о его составляющих.
Компьютер — это сложная система со множеством движущихся частей и непостоянством, где регулярно возникают тепловой шум, фотоэффект и другие квантовые явления. В конце концов инженеры по аппаратному обеспечению выяснили, что, используя сложную схему аппаратных микросхем и компонентов, компьютеры могут преобразовывать физический шум в цифровые единицы и нули.
Чаще всего ГИСЧ используют в цифровых азартных играх: бросание костей, тасование карт, рулетка — все это завязано на неопределенности. А еще в общественных вопросах, военных призывах и выборе присяжных, где случайность выступает в качестве метода справедливости.
Однако на самом деле спектр использования ГИСЧ тоже ограничен, ведь у него есть свои недостатки. Во-первых, для генерации чисел требуется много времени. А еще ГИСЧ не всегда надежны. Компьютерам требуется достаточное количество энтропии для создания истинных случайных чисел, но случайность заключается в том, что она возникает… случайно! Неактивный или новый сервер не сможет создавать номера такого же высокого качества, как активный.
Поскольку и ГПСЧ, и ГИСЧ имеют свои недостатки, их можно без проблем использовать в гейм-сфере и азартных играх, но нельзя — в криптографии, которая требует высокой безопасности. По этой причине появился гибридный тип — «криптографически стойкий генератор псевдослучайных чисел (КСГПЧ или CSPRNG)», который обладает скоростью ГПСЧ и безопасностью ГИСЧ.
КСГПЧ — это генератор, использующий высококачественный источник энтропии для создания начального числа. Затем оно вводится в алгоритм, который производит случайные и безопасные числа. Проще говоря, он использует ГИСЧ для создания начального числа для ГПСЧ. Если все сделано правильно, КСГПЧ гарантирует, что начальное число действительно случайно, а полученный результат нельзя взломать или реконструировать. Обычно его используют в операционных системах вроде Unix и Linux.
Тем не менее, даже несмотря на преимущества КСГПЧ, как и всего остального в технологической индустрии, абсолютная безопасность недостижима.
Теперь, когда в следующий раз вы будете играть в видеоигру, слушать музыку в случайном порядке или просто генерировать случайное число в своем коде, вы осознаете всю магию, которая творится «под капотом».
Источник: 1gai.ru
Случайное число. Генератор на C++
Возможность генерации случайных чисел необходима для работы некоторых программ, например, игр или приложений научно-статистического моделирования. В игре без рандомных событий монстры будут атаковать вас одинаково, вы будете постоянно находить одни и те же артефакты и т. д. Именно поэтому уметь генерировать случайные числа — обязанность любого программиста.
Случайные и псевдослучайные числа. В чём разница?
В реальной жизни, чтобы получить случайный результат мы кидаем кости или тасуем колоду карт. Итог будет зависеть от множества физических переменных (силы тяжести, трения, сопротивления воздуха, мастерства игрока и т. п.). Во многих смыслах мы действительно получаем случайный результат, ведь спрогнозировать его почти невозможно.
У компьютеров всё иначе. Они находятся в строго контролируемом цифровом мире, где существуют лишь два значения: правда и ложь. Именно поэтому ПК изначально создан для получения прогнозируемого результата. Следовательно, он неспособен генерировать случайные числа в полном смысле этого слова. Однако компьютер может имитировать случайность, а достигается это путём использования генераторов псевдослучайных чисел.
Что такое генератор случайных чисел?
Генератор случайных (псевдослучайных) чисел, он же ГСЧ (ГСПЧ) — это программа, принимающая начальное значение и выполняющая с этим значением ряд математических операций, что приводит к конвертации числа в другую цифру, отличную от стартовой. После этого программа применяет новое сгенерированное значение для дальнейших математических операций с последующей генерацией очередного числа, не связанного ни с первым, ни со вторым. И так далее. Таким образом, алгоритм генерирует ряд новых чисел, которые будут нам казаться действительно случайными.
Простой алгоритм случайных чисел
Написать простейший генератор случайных чисел несложно. Вот как выглядит программа на C++, которая позволяет генерировать 100 рандомных чисел:
#include unsigned int PRNG() < // Начальное число — 4 541 static unsigned int seed = 4541; // Берём начальное число и генерируем новое значение // Из-за применения очень больших чисел (и переполнения) угадать следующее число, исходя из предыдущего, довольно сложно seed = (8253729 * seed + 2396403); // Берём начальное число и возвращаем значение в диапазоне от 0 до 32 767 return seed % 32768; >int main() < // Выводим 100 случайных чисел for (int count=0; count < 100; ++count) < std::cout >
А вот результат:
Каждое число в этом ряду кажется нам случайным по отношению к предыдущему. Однако, говоря по правде, данный алгоритм достаточно примитивен.
Но зачем изобретать велосипед, когда для генерации у нас есть специальные функции?
Функции srand() и rand()
В языки программирования C и C++ встроены собственные генераторы случайных чисел. Реализованы они с помощью двух отдельных функций, которые находятся в заголовочном файле cstdlib: 1) srand() . Устанавливает значение, передаваемое пользователем, в качестве стартового. Вызывается лишь 1 раз: в начале программы (как правило, в верхней части функции main()) ;
2) rand() . Обеспечивает генерацию следующего случайного числа в имеющейся последовательности. Число будет находиться в промежутке от нуля до RAND_MAX (это константа в cstdlib, значение которой составляет 32 767).
Источник: otus.ru