Mejorar la calidad de aleatoriedad en Objective-C

Question

Estás en una mazmorra. Antes que tú, hay un grupo de Nerds de nivel 5. Quieren que ejecutes una campaña de Dungeons and Dragons para ellos.

Ejecutas algunas sesiones, tus jugadores están subiendo de nivel, y las cosas son generalmente increíbles. El combate es un poco lento, sin embargo. Decides sacar tu Halberd +4 de Objective-C y escribir una aplicación para iPad para automatizar el rodaje de los dados de NPC en combate. Los nerds se mueven hacia ti amenazadoramente. "Los números generados algorítmicamente", gruñe, "son una imitación hueca de la verdadera aleatoriedad. ¡No mancharás nuestra santa campaña con tu inmundicia pseudoaleatoria!"

Ruedas para convencerlo de que arc4random_uniform() es más que suficiente ... y falla. Los nerds se conformarán con nada menos que la verdadera aleatoriedad. Te mantienen prisionero mientras te aferras desesperadamente a tu MacBook y escribes una clase que recupera datos de random.org.

NSDateFormatter *formatter = [[NSDateFormatter alloc] init]; 
[formatter setDateFormat:@"YYYY/YYYY-MM-dd"]; 
NSURL *url = [NSURL URLWithString:[NSString stringWithFormat:@"%@%@%@", 
       @"http://www.random.org/files/", 
       [formatter stringFromDate:[NSDate date]], 
       @".bin"]]; 
NSURLConnection *theConnection = [[NSURLConnection alloc] initWithRequest: 
       [NSURLRequest requestWithURL:url] delegate:self]; 

Una vez que los datos se han guardado, permiten la generación de números aleatorios, 0-255, a partir de los bytes descargados.

-(int) nextInt:(int)start end:(int)end 
{ 
    int upperBound = end - start + 1; 
    unsigned char result; 
    int maxModulo = 255 - (255 % upperBound); 
    do { 
     NSRange range = {index, sizeof(char)}; 
     [randos getBytes:&result range:range]; 
     index += sizeof(char); 
    } while (result > maxModulo); //avoid modulo bias 
    result = result % upperBound; 
    result += start; 
    return result; 
} 

Los nerds parecen satisfechos, pero aparece un nuevo enemigo: ¡otro Dungeon Master! Él exige que le des una copia del software para sus propios fines. El problema es evidente: si ambos usan datos de random.org del mismo día, obtendrán el mismo conjunto de dados.

Así que mi pregunta es la siguiente: ¿cómo puedo modificar los datos de random.org de modo que conserven algo así como "verdadera aleatoriedad" pero sean diferentes en cada instancia del programa? Puedo imaginar una solución que implicaría obtener algunos movimientos del touchpad (supuestamente aleatorios) por parte del usuario, like TrueCrypt does, pero una vez que tengo esa constante, no estoy seguro de a dónde ir desde allí. De alguna manera hash todos los números usando mi constante? Eso producirá un número mucho mayor; ¿Estoy estadísticamente bien si trunco ​​o modulo eso hasta la tirada de dados? No sé qué pasos algorítmicos tomar.

Answer 1

Tengo una solución diferente. Uno que satisfaga a todos, espero. Cada vez que desee generar una nueva tirada, hágalo de esta manera:

Presente una barra de progreso y solicite al usuario que sacuda el dispositivo.

• Mientras espera, filtre los datos de aceleración adecuadamente (algunos IIR de paso bajo deberían funcionar bien) y busque picos con una magnitud determinada. Contar los cambios de nivel usando histéresis. Muestra una barra de progreso que muestra la cantidad de temblores.
• Al mismo tiempo, alimente los datos de aceleración en bruto a una función de cifrado criptográfica adecuada, por ejemplo, SHA-2.

Cuando la barra de progreso llega a la derecha, reproduce el sonido de los dados y utiliza la salida de la función hash (256 bits) para generar los valores del dado. Esto no funcionará por más de 59d20. También puede guardar el estado de la función hash como entrada en la siguiente tirada.

Esto es lo que le dices a esos nerds: La tirada de ninguna manera es algorítmicamente predecible. La única información que se usa para determinar el valor de la tirada del dado es cómo agitas el dispositivo, lo cual también es cierto para los dados reales. En teoría podría sacudir el dispositivo de la misma manera dos veces, al igual que en la teoría un jugador muy hábil podría tirar dados reales para que salgan como él quiere.

Cómo usar la salida: Tiene 256 bits de datos aleatorios y desea obtener tiradas de dados.

struct bits { 
    unsigned data[8]; 
    unsigned pos; 
}; 

// Get next n bits, or -1 if out of entropy. 
int get_bits(struct bits *b, int n); 

// Roll an n-sided die, or -1 if out of entropy 
int uniform(struct bits *b, int n) 
{ 
    int nbits, x; 
    for (nbits = 0; (1 << nbits) < n; ++nbits); 
    do { 
     x = get_bits(b, nbits); 
     if (x < 0) 
      return -1; 
    } while (x >= n); 
    return x + 1; 
} 

Esta función se activa por rebanar unos pocos bits de entropía a la vez para sus tiradas de dado. Entonces, para un d8, recorta de 3 bits y usa el resultado. Para un d20, corte 5 bits para un d32, y vuelva a enrollar si el resultado es mayor que 20. Si se queda sin entropía (poco probable, pero posible) para una tirada de dados determinada, entonces sugiero imprimir un "dado "jacked" mensaje y pidiendo al usuario que agite un poco más para los dados restantes.

Nota al pie: la probabilidad de que se quede sin entropía es muy baja, a menos que tire una gran cantidad de dados. 256 bits es suficiente. Se necesitan 24d20 antes de que la posibilidad de quedarse sin entropía llegue al 1%.

Answer 2

Descargue bin-files.txt y elija aleatoriamente una de las entradas (por ejemplo, use NSDate timeIntervalSinceNow modulo el número de entradas en el archivo txt). Luego descarga ese archivo.

Además, una vez que descarga un archivo, comience con un desplazamiento basado en un aleatorizador diferente.

Answer 3

No es realmente una respuesta y es un comentario, pero se hizo largo y aquí está.

Puedo imaginar una solución que supondría conseguir algunos (supuestamente aleatorios) los movimientos del touchpad del usuario,

Tenga en cuenta que arc4random_stir() lee de /dev/urandom, ver the man page. Entonces se planta con el "ambiente".

O bien, compre una fuente radiactiva y un contador Geiger, conéctelo al USB y genere el número aleatorio según la lectura del contador. La descomposición nuclear es mecánica cuánticamente aleatoria.

Answer 4

Genera una matriz de bytes aleatorios criptográficamente seguros.

int SecRandomCopyBytes (
    SecRandomRef rnd, 
    size_t count, 
    uint8_t *bytes 
); 

Apple Randomization Services Reference Docs

o simplemente utilizar arc4random(), que es lo más cerca posible al azar como se puede notar, que se siembra de forma automática desde/dev/urandom.