Mezclar la cadena grande de forma segura

Question

Mezclar la cadena grande de forma segura

#1 de Luis Casillas (2 votos)

0

Tengo una cadena grande que debo barajar de manera segura. Será alrededor de 4000 caracteres. La permutación resultante de dicha cadena debe ser una en el conjunto de todas las permutaciones posibles (4000!). Por supuesto, las permutaciones resultantes también deben estar distribuidas equitativamente entre todos los estados posibles. Necesito probar razonablemente que mi implementación cumple con esos requisitos, pero no se necesitan métodos formales.

Estaba planeando usar un Knuth-Fisher-Yates simple para esto, pero me preocupa mi RNG. Estoy obligado a implementar esto en JavaScript, ya que mi aplicación debe ejecutarse en Thunderbird. De (lo que puedo leer) [ enlace , Mozilla puede proporcionar un criptográficamente asegure un valor aleatorio, y planeo combinarlo con (this) [ enlace para obtener números aleatorios en el rango deseado.

Ahora, creo que podría tener problemas con el espacio de estado interno del PRNG. Si tiene pocos, se "envolverá" y producirá un sesgo para ciertos números. Si tiene demasiados, podría aplicarse el módulo a escala reducida, lo que también produce un sesgo para los números en el rango inferior.

¿Cuánto tiempo necesitaría una semilla para inicializar un PRNG usado para KFY-Shuffle una cadena de 4000 caracteres? ¿Estoy pensando demasiado en esto, hay algo en lo que no pensé?

cryptography random javascript

pregunta Andreas 05.10.2016 - 20:32

fuente

1 respuesta

Lea otras preguntas en las etiquetas cryptography random javascript

Comparando TLS y seguridad de cifrado Decodificación de la carga útil de MSSQL

score 2 · Answer 1

Ahora, creo que podría tener problemas con el espacio de estado interno del PRNG. Si tiene pocos, se "envolverá" y producirá un sesgo para ciertos números. Si tiene demasiados, podría aplicarse el módulo a escala reducida, lo que también produce un sesgo para los números en el rango inferior.

No, el espacio de estado de un buen PRNG no hará que parezca parcial en las formas en que usted teme aquí. Un buen RNG no criptográfico producirá resultados que parezcan no sesgados e independientes de algún conjunto de pruebas estadísticas. Uno criptográficamente seguro, además, producirá un resultado que parece imparcial e independiente para cualquier observador eficiente ; es decir, no puede escribir un programa eficiente para distinguir su salida de una secuencia verdaderamente aleatoria.

¿Cuánto tiempo necesitaría una semilla para inicializar un PRNG usado para KFY-Shuffle una cadena de 4000 caracteres? ¿Estoy pensando demasiado en esto, hay algo en lo que no pensé?

¡El número de permutaciones distintas de una secuencia de 4,000 elementos es 4,000! (factorial), que es algo así como 2^43000 , por lo que técnicamente necesita una cadena de 43,000 bits (5,263 bytes) para poder abordar de manera única cualquiera de estas permutaciones.

Respuesta práctica: solo use un crypto RNG. Si bien, en el mejor de los casos, es poco probable que pueda generar todas las permutaciones posibles incluso cuando se alimenta con entropía externa, lo que importa es que ningún atacante de la vida real podrá distinguir la diferencia.