Tengo una aplicación de consola C++ no administrada en la que estoy usando srand() y rand(). No necesito esto para resolver un problema en particular, pero tenía curiosidad: ¿la semilla original pasó a srand() almacenada en algún lugar de la memoria que puedo consultar? ¿Hay alguna manera de descubrir qué era la semilla?Averigüe con qué se sembró un generador de números aleatorios en C++
No es necesario almacenar la semilla, solo aparece el último número aleatorio devuelto.
Así es el ejemplo de la página de manual:
static unsigned long next = 1;
/* RAND_MAX assumed to be 32767 */
int myrand(void) {
next = next * 1103515245 + 12345;
return((unsigned)(next/65536) % 32768);
}
void mysrand(unsigned seed) {
next = seed;
}
Teóricamente, no - el valor de inicialización se utiliza para calcular el siguiente valor aleatorio y que el valor es (teóricamente) utilizaron para sembrar el siguiente número aleatorio y así sucesivamente .
En cuanto a la seguridad, poder echar un vistazo a la semilla (ya sea la original o la nueva) es un problema serio de seguridad, así que no deberías poder mirarla a pesar de que debe almacenarse en algún lugar .
Si usted tiene un simple generador de congruencia lineal, para los que tiene varios valores de esta se obtiene un sistema de ecuaciones:
v1 = (seed * a + b) % m
v2 = ( v1 * a + b) % m;
v3 = ( v2 * a + b) % m;
...
Si conoce el primer valor, se puede ir hacia atrás en la secuencia:
seed = (v1 - b)/a (mod m)
usted no sabe la semilla única, sólo se sabe que mod m (que es por lo general muy bien ya (0 < semilla < m) de todos modos) Si v1 - b es negativo es necesario agregar de m hasta su nuevo positiva .
También puede consultar el Chinese Remainder Theorem, aunque no es una coincidencia exacta.
¿Acabas de decir "simplemente prueba todas las semillas de 64 bits"? ¿Qué tan rápido de una computadora tienes? : D –
¿Probar todas las semillas de 64 bits? Eso es 18,446,744,073,709,551,616 posibilidades diferentes, un poco más allá de lo factible. – Eclipse
Lo que podrías hacer con un poco de información sobre de dónde viene la semilla, es intentar algunos millones de conjeturas. A menudo srand se siembra con la hora actual. Si sabe aproximadamente cuándo se sembró por primera vez el generador, puede adivinar muy bien cuál fue el valor del tiempo() en ese punto. – Eclipse
No sé cuál es su nivel de competencia de ensamblaje, o si tiene acceso al código fuente/símbolos de depuración para la aplicación no administrada, pero fuera de ese tipo de engaño, no hay manera factible de determinar la valor original de la semilla El punto principal de los generadores de números aleatorios es encontrar una forma de darle números impredecibles: la relación entre dos llamadas a rand() no debería ser deducible. En generadores de números pseudoaleatorios criptográficamente fuertes, se consideraría una falla seria poder adivinar la semilla en base a un número aleatorio generado.
La manera más fácil de hacerlo es iniciar la aplicación en un depurador y establecer un punto de interrupción donde se llama srand(); luego, simplemente mire el parámetro pasado.
Lo siguiente sería desmontar la aplicación y conocer las circunstancias de la llamada srand. Es completamente posible que esté siendo sembrado con la hora actual, entonces puedes intentar un montón de conjeturas (probablemente puedes reducirlo a unos pocos miles más o menos) y ver si alguno da la misma secuencia de números aleatorios que la aplicación está usando . (Por supuesto, esto supone que tienes alguna forma de saber cuáles son los valores aleatorios que se generan). También es posible que la semilla sea algo tonto como '0' todo el tiempo.
-1. rand() no es criptográficamente seguro; casi siempre devuelve los bits de orden superior de un LCG. La salida de un par de llamadas a rand() generalmente es suficiente para deducir el estado actual y así trabajar hacia atrás. –
Supongo que 'should' se supone que es 'should not' (ya que no tiene mucho sentido) –
No sé qué usa la función rand(), pero la mayoría de los buenos mantienen un shuffle tabla, no solo un estado 'actual'. – Justin
@Dan: correcto, reparado. – Guss