Псевдослучайный генератор с тем же выходом

Question

Я наткнулся на статью о системе дистанционного входа в автомобиль на сайте http://auto.howstuffworks.com/remote-entry2.htm В третьем пункте автор говорит:

И передатчик, и приемник используют один и тот же генератор псевдослучайных чисел.Когда передатчик отправляет 40-битный код, он использует генератор псевдослучайных чисел, чтобы выбрать новый код и сохранить его в памяти.С другой стороны, когда получатель получает действительный код, он использует тот же генератор псевдослучайных чисел, чтобы выбрать новый.Таким образом, передатчик и приемник синхронизируются.Получатель открывает дверь только в том случае, если получает ожидаемый код.

Возможно ли иметь две функции PRNG, производящие одни и те же случайные числа одновременно?

Answer 1

В функциях PRNG вывод функции зависит от «начального» значения, так что один и тот же вывод будет предоставлен при последовательных вызовах с одинаковым начальным значением.Так да.

Пример (с использованием C#) будет выглядеть примерно так:

// Provide the same seed value for both generators:
System.Random r1 = new System.Random(1);
System.Random r2 = new System.Random(1);

// Will output 'True'
Console.WriteLine(r1.Next() == r2.Next());

Все это, конечно, зависит от генератора случайных чисел, использующего какую-то детерминированную формулу для генерации своих значений.Если вы используете так называемый генератор «истинных случайных» чисел, который использует при своей генерации свойства энтропии или шума, то будет очень сложно получить те же значения с учетом некоторых входных данных, если только вы не сможете дублировать энтропийное состояние для оба вызова функции - что, конечно, противоречит цели использования такого генератора...

В случае систем удаленного доступа без ключа они, скорее всего, используют детерминированную функцию PRNG, чтобы воспользоваться этой функцией.Существует множество микросхем, которые обеспечивают такого рода функциональность для создания случайных чисел для электронных схем.

Редактировать:по запросу, вот пример недетерминированного генератора случайных чисел, который не полагается на указанное начальное значение: Квантовый генератор случайных чисел.Конечно, как отмечает Freespace в комментариях, это не генератор псевдослучайных чисел, поскольку он генерирует действительно случайные числа.

Answer 2

Большинство PRNG имеют внутреннее состояние в форме seed , которое они используют для генерации своих следующих значений. Внутренняя логика выглядит примерно так:

nextNumber = function(seed);
seed = nextNumber;

Таким образом, каждый раз, когда вы генерируете новый номер, начальное число обновляется. Если вы дадите двум PRNG, использующим один и тот же алгоритм, одно и то же начальное число, функция function (seed) будет вычислять одно и то же число (учитывая, что они являются детерминированными, а большинство из них).

Применяется непосредственно к вашему вопросу: передатчик выбирает код и использует его в качестве начального числа. Получатель, получив его, использует его для заполнения своего генератора. Теперь они выровнены, и они будут генерировать одинаковые значения.

Answer 3

Как сказали Эрик и Клаудиу, до тех пор, пока вы заполняете свой PRNG одним и тем же значением, вы получите одинаковый результат.

Пример можно увидеть при использовании AES (или любого другого алгоритма шифрования) в качестве основы вашего PRNG. Пока вы продолжаете использовать входы, которые совпадают на обоих устройствах (передатчик и приемник), выходы также будут совпадать.