¿Generando códigos únicos en PHP / MySQL?

Question

Estoy trabajando con un cliente que necesita generar millones de los códigos alfanuméricos utilizados en las tarjetas de raspar de la revista, los premios de Bottlecap, etc. Deben ser lo suficientemente cortos como para imprimir en una tapa, quieren asegurarse de que no se incluyan los caracteres ambiguos como 1 y I, 0 y O, etc., y deben almacenarse explícitamente para su uso futuro. Solo tiene un algoritmo que determina la "validez" cuando alguien intenta canjear uno. Finalmente, quieren asegurarse de que los códigos se distribuyen aleatoriamente dentro de un gran espacio de código de " " para que las personas no puedan simplemente adivinar códigos adicionales recorriendo el alfabeto.

¿Hay algún indicador hacia algoritmos razonablemente eficientes para generar este tipo de conjuntos de códigos? He tachado algunos en la parte posterior de un sobre, pero este problema huele como una trampa para los incautos.

Answer 1

Si necesita alrededor de 10 millones de claves únicas (por ejemplo), el mejor enfoque es elegir un espacio de claves que sea exponencialmente más grande y comenzar a generar aleatoriamente. Lea sobre la Birthday Paradox : es lo más importante por lo que debe preocuparse. Si desea 2 ^ n claves únicas y seguras, asegúrese de que haya al menos 2 ^ (2 * n) valores posibles. Aquí hay un algoritmo O (n log n) aproximado:

• Use un espacio clave de al menos 2 ^ 50 (por lo que, en otras palabras, permita 2 ^ 50 valores únicos posibles), y apenas tendrá colisiones en todo su conjunto de datos, y cualquier persona que fuerce sus claves incluso tienen probabilidades de obtener una llave si intentan 2 ^ 25 de ellas.
• genere tantos números aleatorios como necesite
• indexar la base de datos en su clave (este es el paso O (n lg n): la clasificación)
• página a través de la base de datos e iterar sobre todo el conjunto de datos para recortar duplicados (pseudocódigo a continuación)
• Eliminar las filas duplicadas, y listo.

Pseudocódigo:

$last = null;
while ($current = getnext()) {
    if ($last == $current) {
        push($toDelete, $current);
    }
    $last = $current;
}

Answer 2

Supongamos que puede utilizar un conjunto de caracteres de, por ejemplo, 40 símbolos de caracteres superiores, inferiores y numéricos no ambiguos.

Para una secuencia de n caracteres, tienes 40 combinaciones ⁿ

• 40 ⁴ = 2,560,000
• 40 ⁵ = 102,400,000
• 40 ⁶ = 4,096,000,000
• 40 ⁷ = 163,840,000,000
• 40 ⁸ = 6,553,600,000,000

Por lo tanto, 8 caracteres proporcionan un espacio bastante bueno para trabajar: si generó 10 millones de códigos, tendría que probar cientos de miles de combinaciones para forzar un código.

O viene de la otra dirección: indique la cantidad de códigos posibles , cuántos códigos debería generar para evitar la trampa que llaman Birthday Paradox ?

Tomando el código de 8 caracteres, 6,553,600,000,000 es aproximadamente 2 ⁴² , por lo tanto, podría generar razonablemente 2 códigos ²¹ , o 2,097,152

Answer 3

¿Utilizar un algoritmo de contraseña de un solo uso?

RFC4225 detalla uno basado en el algoritmo HMAC.

http://www.ietf.org/rfc/rfc4226.txt

pero en lugar de usar 0-9 dígitos de codificación base10, usa base32.

Answer 4

Cualquiera que sea el método que utilice, sugeriría que agregue uno o dos dígitos de control como " primera línea " defensa contra personas que ingresan mal o intentan inventar un número.

Answer 5

Por extraño que parezca, con la siguiente semilla solo pude generar 32 cadenas únicas.

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

Con una semilla más larga pude generar muchas más, generé 40,000 cadenas únicas con éxito.

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ23456789234567892pancolucopoluciopucioparcamiento de los animales