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

Question

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

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

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

Answer 1

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

Пример (с использованием 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, которая является детерминированной, чтобы воспользоваться этой функцией. Существует множество интегральных схем, которые предоставляют такую ​​функциональность для создания случайных чисел для электронных схем.

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

Answer 2

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

nextNumber = function(seed);
seed = nextNumber;

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

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

Answer 3

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

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