Предоставляет ли криптографически безопасный генератор псевдослучайных чисел, чтобы энтропия была собрана таким образом, чтобы значение не могло происходить дважды при сгенерированном в другое время?CSPRNG: В любое время гарантии?
Я знаю, что это очень маловероятно, но существуют ли конкретные гарантии?
Мне нужно создать серию уникальных идентификаторов из CSPRNG, которые не должны иметь конфликтов.
Идеальный (CS) PRNG гарантирует, что вероятность извлечения определенного значения является постоянной и не изменяется со временем, независимо от того, было ли это значение уже выведено в прошлом.
Например, предположим, что ваш идентификатор длиной 32 бит и сегодня вы извлекаете 0x12345678. То, что только что произошло, имело вероятность 1/(2^32).
Завтра (и в любой момент в будущем) вы по-прежнему будете иметь ту же вероятность 1/(2^32) извлечения значения 0x12345678.
Однако birthday paradox говорит нам, что если вы создаете 65 536 (= 2^(32/2)) значения, существует вероятность 50%, что два идентификатора одинаковы.
Другими словами, нет твердых гарантий, что вывод CSPRNG не будет таким же. Скорее всего, вероятность того, что ваши шансы достаточно малы, зависит от того, как долго ваш идентификатор и сколько идентификаторов вы ожидаете получить в общей сложности за всю жизнь вашей системы (особое внимание следует уделить соображениям безопасности, когда злоумышленник может генерировать идентификаторы по желанию).
Для полноты, все это применимо к любому хорошему PRNG - включая простейшую монету для переворота. Криптографически сильные PRNG имеют дополнительные свойства о сложности прогнозирования будущих или прошлых результатов от любого заданного результата (это должно быть сложно), способности восстанавливаться после компрометации состояния и способности кормить энтропию.
Я сильно сомневаюсь. Если вы хотите покрыть/почти покрыть некоторый диапазон, [перетасовка] (http://en.wikipedia.org/wiki/Knuth_shuffle#The_modern_algorithm) предоставит вам эту гарантию. – Dukeling
Как один пример - [«повторные звонки гарантированы никогда не уменьшать случайность»] (http://docs.oracle.com/javase/6/docs/api/java/security/SecureRandom.html). Я считаю, что это уменьшит случайность, если мы узнаем, что новое значение отличается от предыдущего значения, поэтому эта реализация не имеет этой гарантии (хотя в ней сказано: «C ** strong ** RNG» не «C ** secure ** RNG «). Я не уверен, что это [«незначительное преимущество»] (https://en.wikipedia.org/wiki/Pseudorandom_number_generator#Cryptographically_secure_pseudorandom_number_generators). Вероятно, это зависит от того, сколько последовательных чисел должно быть уникальным. – Dukeling