Генератор псевдослучайных чисел с тем же выходом

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

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

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


random security protocols algorithm
person BlueGene    schedule 27.10.2008    source источник

Ответы (3)


arrow_upward
11
arrow_downward

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

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

// 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 в комментариях, это не генератор псевдослучайных чисел, поскольку он генерирует действительно случайные числа.

person Erik Forbes    schedule 27.10.2008
comment
Пожалуйста, приведите пример PRNG, который не зависит от семени. Пожалуйста, также приведите пример PRNG, который не является детерминированным. - person freespace; 27.10.2008
comment
Ну вот - это действительно тот же самый пример. Вероятно, это не совсем то, что вы искали, но для недетерминированных ГСЧ требуется оборудование, способное использовать энтропию для генерации случайного битового потока. В приведенном выше случае они используют недетерминированные квантовые свойства фотонов для генерации своего потока. - person Erik Forbes; 27.10.2008
comment
Онлайн-казино используют такое оборудование (хотя и более сложное) для тасования своих карт. - person Erik Forbes; 27.10.2008
comment
Спасибо за ответ Эрик, но вы не ответили на мой вопрос. Мой первоначальный комментарий состоял в том, чтобы заставить вас задуматься о том, насколько избыточно говорить, что генератор псевдослучайных чисел требует начального числа и является детерминированным. Квантовый генератор случайных чисел — это настоящий генератор случайных чисел, а не PRNG. - person freespace; 28.10.2008
comment
Ах. Хорошая точка зрения. =) Отредактировал мой ответ, чтобы отразить это. Что касается того, чтобы заставить меня задуматься - я знаю разницу между ними, проблема в том, что я просмотрел ваш комментарий, а не прочитал его четко - если бы я это сделал, я бы уловил это различие. Спасибо хоть. знак равно - person Erik Forbes; 28.10.2008
comment
У меня просто была эта злая идея, что вы должны доказать, что все числа одинаковы, заменив Console.WriteLine на while в вашем коде :) - person Michał Piaskowski; 28.10.2008
comment
Лол - это было бы действительно зло. знак равно - person Erik Forbes; 28.10.2008
comment
В Linux у вас есть /dev/random и /dev/urandom, которые могут быть аппаратными или могут накапливать шум от аппаратного обеспечения для создания начальных значений. - person S.Lott; 26.11.2008

arrow_upward
3
arrow_downward

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

nextNumber = function(seed);
seed = nextNumber;

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

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

person Claudiu    schedule 27.10.2008

arrow_upward
1
arrow_downward

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

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

person Andrew Edgecombe    schedule 27.10.2008
comment
Я так не думаю. Я думаю, что передатчик отправляет серийный номер и его зашифрованную версию, а получатель использует то же шифрование для этого серийного номера + согласованное начальное значение. - person Kirk Strauser; 27.10.2008