algorithm - una - Algoritmo para códigos de tarjetas de regalo

tarjeta itunes para que sirve

Question

Hace poco publiqué esta pregunta sobre códigos para un cupón similar a una tarjeta de regalo que los usuarios pueden canjear en línea. Quería encontrar la mejor compensación entre un gran espacio de teclas, poca capacidad de cálculo y legibilidad humana. Ahora que estoy en la implementación, me doy cuenta de que tengo otro problema por completo, más un desafío algorítmico.

Supongamos que adopto algún formato de código; digamos 10 caracteres de la A a la Z para simplificar, y comienzo a generar vales. ¿Cuál es el algoritmo correcto para hacer esto?

Mi primer enfoque es numerar todos los códigos posibles de 0 a 308,915,776, luego comenzar a generar números aleatorios en ese rango. Sin embargo, esto obviamente tiene un gran problema: tengo que comparar mi número aleatorio con todos los códigos de cupones generados anteriormente y si choca con uno existente, tendré que descartar el código y probar otro. A medida que el sistema acumule más datos, se ralentizará. En el extremo, cuando solo queda un código, será casi imposible que el sistema lo adivine correctamente.

Podría generar previamente todos los códigos y mezclarlos, luego consumirlos en orden. Pero esto significa que tengo que almacenar muchos códigos y, de hecho, mi espacio de teclas es más grande que el que describí, por lo que estamos hablando de una gran cantidad de datos. Así que eso tampoco es demasiado deseable.

Así que esto me deja con usar los códigos secuencialmente. Sin embargo, no quiero códigos de vales adivinables. El usuario que compra el cupón "AAAAAAAAAAY" no debería tener una buena posibilidad de obtener otro código válido si escribe "AAAAAAAAAZ".

Puedo mezclar mi alfabeto y mis posiciones para que en lugar de

''ABCDEFGHIJKLMNOPQRSTUVWXYZ'' yo uso

''LYFZTGKBNDRAPWEOXQHVJSUMIC''

y para que en lugar de posiciones.

9 8 7 6 5 4 3 2 1 0 las posiciones son

1 8 0 7 5 4 3 9 2 6

Usando esta lógica, dado el código

LNWHDTECMA

el siguiente código sería

LNEHDTECMA

Esto es definitivamente mucho más difícil de adivinar. Pero aún están a un solo personaje del otro, y solo con dos de estos cupones sabría qué posición está aumentando, y tendría un 90% de probabilidad de obtener el siguiente código en 24 intentos o menos.

Mi "escotilla de escape" es deshacerse de todo esto e ir con GUIDs. Tienen más caracteres de los que yo quería que mis usuarios tuvieran que escribir, y contienen caracteres similares como I / 1 y O / 0, pero mágicamente hacen que desaparezcan todos los dolores de cabeza anteriores. Aún así, me estoy divirtiendo pensando en esto, quizás tú también lo estés. Me encantaría escuchar algunas sugerencias alternativas. ¿Qué tienes?

¡Gracias!

Answer 1

Algunos generadores de números aleatorios tienen una propiedad interesante: se usan correctamente y no generan números duplicados en mucho tiempo. Producen algo llamado un ciclo completo . Use uno de los algoritmos descritos allí, sembrándolo, y tendrá muchos números únicos,

Agregue una forma inteligente de asignar dígitos a los caracteres y obtendrá sus códigos.

Answer 2

Aquí hay un sin embargo:

• ID = cada cupón tiene un ID único (¿auto-incrementado?)
• CHECKSUM = aplicar N iteraciones del algoritmo de Verhoeff o Luhn en el ID
• VOUCHER = base convierte el CHECKSUM generado de la base 10 a la base 36

Vea también esta pregunta SO relacionada: Ideas para crear un "hash" pequeño (<10 dígitos), no (muy) seguro .

Una forma sencilla de hacer que este método sea más seguro es usar un valor de ID sin incremento automático, una opción podría ser usar ID como los últimos 6 o 7 dígitos de una marca de tiempo de UNIX y calcular la suma de comprobación.

Answer 3

Basándome en la respuesta de Jason Orendoff, armé un algoritmo para generar códigos de tarjetas de regalo. Básicamente, tiene dos números de 40 bits: uno de ellos para asegurar que es único y otro para asegurar que sea difícil de adivinar.

• la parte del número aleatorio de 40 bits es suficiente para 1 en 2^40 posibilidades de adivinar;
• la parte del número secuencial de 40 bits es suficiente para 34.8 años de singularidad (suponiendo que generemos una tarjeta de regalo por ms).

La secuencia total de 80 bits se convierte luego en una cadena de 16 caracteres utilizando Base32 .

import java.security.SecureRandom;
import java.util.Random;
import java.util.concurrent.atomic.AtomicLong;

import org.apache.commons.codec.binary.Base32;

public class GiftCardUtil {

    private AtomicLong sequence;
    private Random random;

    public GiftCardUtil() {
        // 1325383200000L == 1 Jan 2012
        sequence = new AtomicLong(System.currentTimeMillis() - 1325383200000L);
        random = new SecureRandom();
    }

    public String generateCode() {
        System.out.println(sequence.get());
        byte[] id = new byte[10];
        longTo5ByteArray(sequence.incrementAndGet(), id);
        byte[] rnd = new byte[5];
        random.nextBytes(rnd);
        System.arraycopy(rnd, 0, id, 5, 5);
        return new Base32().encodeAsString(id);
    }

    private void longTo5ByteArray(long l, byte[] b) {
        b[0] = (byte) (l >>> 32);
        b[1] = (byte) (l >>> 24);
        b[2] = (byte) (l >>> 16);
        b[3] = (byte) (l >>> 8);
        b[4] = (byte) (l >>> 0);
    }
}

Answer 4

Creo que la mejor manera de hacerlo es la sugerida por Andreas. Pero mi respuesta es sobre una interesante discusión relacionada.

Desea generar una secuencia de números que juntos forman una permutación de S = {1, ..., MAX}. Una forma de hacer esto es tomar los elementos de un grupo cíclico sobre S. Por ejemplo, los números R = {x modulo p, x^2 modulo p, x^3 modulo p, ..., x^(p-1) modulo p} forme un grupo cíclico sobre {1, ..., p-1} , siempre que p sea ​​primo x sea ​​coprime a p . Entonces, si elige MAX como un número primo, use esta secuencia.

Quieres una secuencia "difícil de romper". Un generador para la secuencia suficientemente resistente a la fisuración se denomina generador pseudoaleatorio (por supuesto, es probable que no necesite esa resistencia a la fisuración). Un ejemplo es el último dígito de los elementos en R arriba, siempre que p se mantenga en secreto (¿estoy en lo cierto?). Pero la respuesta de Andreas ya utiliza una fuente de (pseudo) números aleatorios, por lo que no se puede llamar un generador pseudoaleatorio.

Si está interesado en los generadores pseudoaleatorios, se analizan en detalle en el volumen 2 del conocido libro de Knuth.

Answer 5

La probabilidad de que dos códigos generados aleatoriamente colisionen es básicamente la misma que un usuario que adivina un código válido, y no puede evitar que los usuarios adivinen. Por lo tanto, debe tener un espacio clave mucho más grande que el número de códigos realmente utilizados, por lo que las colisiones aleatorias también son extremadamente improbables (aunque, gracias a la paradoja del cumpleaños, probablemente no sea lo suficientemente improbable como para ignorarlos por completo, al menos si desea sus códigos). ser razonablemente corto), y verificar con los códigos existentes y volver a generar en caso de una colisión es una estrategia perfectamente viable.

Answer 6

Leí todo el comentario y descubrí algo que muchas personas en otros para proteger utilizan medios muy inteligentes y sofisticados. las posibilidades de adivinar mi algoritmo son 1/2600000 todo lo que tiene que hacer es cambiar el sufijo de sal del prefijo de sal después de cada generación

• Elegí un prefijo de sal de 4 números
• y sufijo de 4 numeros
• entonces el código principal es 9 números intercambiables
• luego usando este formato sprefix +random_numbers+ssuffix
• Hashearé el formato almacenándolo en la base de datos inmediatamente.
• La consulta puede ayudar a eliminar códigos similares.
• y el sufijo y el prefijo deben cambiarse una vez que haya impreso 9. (362880) veces.

Answer 7

Lo que puede funcionar de manera efectiva es simplemente usar el tiempo de creación en su beneficio. Por ejemplo, los dos últimos dígitos del año, el mes de dos dígitos, el día de dos dígitos, la hora de dos dígitos, los minutos de dos dígitos, los segundos de dos dígitos y luego los segundos para, digamos, el microsegundo. Si se desea una nueva ofuscación, pídales que lo programen previamente (por ejemplo, MYmdshhdMmYs en lugar de YYMMddhmmss). Luego cambie la base (a pentadecimal, tal vez) para rechazar cualquier intento de adivinación. Esto conlleva dos beneficios principales: 1-Usar la fecha, incluido el año, destruirá cualquier duplicación, ya que al mismo tiempo no pasará dos veces. Solo después de cien años hay algún riesgo. La única preocupación es potencialmente tener dos creados en el mismo microsegundo, por lo que sería una tarea simple rechazar la creación de más de uno a la vez. Un retraso de milisegundos solucionaría el problema.

2-Adivinar será muy difícil. No solo es determinar en qué base y en qué orden van a ser los números (¡y las letras!), Sino que salir al microsegundo hace que la secuencia sea en gran medida irrelevante. No mencione lo difícil que sería para un cliente averiguar cómo compró en qué microsegundo y cómo coincide su reloj con el suyo.

La objeción puede ser "¡Espere! Eso es de 17 dígitos (YYMMDDhhmmss.sssss), pero luego llevarlo a una base más grande lo disminuiría. Ir a la base 36, usando 10 números y 26 letras, significa que un código de 11 dígitos cubriría cada posibilidad. Si las mayúsculas y minúsculas no son intercambiables, los datos se pueden comprimir hasta alcanzar el objetivo de 10 dígitos con cero problemas.

Answer 8

Segundo, el uso de un hash criptográfico: tomar bits de MD5 es muy simple. Para hacer las cosas legibles, pego a la siguiente idea: tomar una lista de palabras y usar bits de la clave para indexar una lista de palabras. Mi lista de palabras es de aproximadamente 100 000 palabras, así que aproximadamente 16 bits por palabra, lo que para cuatro palabras proporciona un espacio de clave de 64 bits. Los resultados suelen ser bastante legibles.

Por ejemplo, la firma criptográfica del párrafo anterior es

expectoración de la mansión de freshet de kamikaze

(Mi lista de palabras está inclinada hacia un espacio de teclas más grande; si desea frases más cortas, tiene menos palabras).

Si tiene una biblioteca MD5 a mano, esta estrategia es muy fácil de implementar: lo hago en aproximadamente 40 líneas de Lua.

Answer 9

Use un número de serie R de N bits, combinado con un hash H de bit M del par concatenado (R, S) donde S es un secreto de "sal" S que usted NO publica. Luego codifique el par (R, H) alfanuméricamente de la forma reversible que desee. Si le gustan los algoritmos como MD5 * o SHA, pero el recuento de bits es demasiado alto, simplemente tome los M bits menos significativos de un algoritmo hash estándar.

Puedes verificar fácilmente: descodifica la codificación alfanumérica para que puedas ver R y H. Luego calcula H ''= hash (R + S) y verifica que H = H''.

edición: R puede ser un número de serie incremental o aleatorio o lo que sea, solo asegúrese de usar cada valor no más de una vez.

* antes de que alguien diga "El MD5 está roto", permítame recordarle que las debilidades conocidas del MD5 son los ataques de colisión y no los ataques de preimagen . Además, al utilizar un valor de sal secreto no publicado, le niega a un atacante la capacidad de probar su mecanismo de seguridad, a menos que pueda adivinar el valor de sal. Si te sientes paranoico, elige dos valores de sal, Sprefix y Ssuffix, y calcula el hash del triple concatenado (Sprefix, R, Ssuffix).

Answer 10

Yo diría que usar un "hash perfecto" - http://en.wikipedia.org/wiki/Perfect_hash_function combinado con un número aleatorio de 4 dígitos ...

Entonces solo incremente su código de cupón cada vez, luego córtelo, agregue un número aleatorio de 4 dígitos y también agregaré un dígito de verificación al final (como sugirió Alix Axel).

Esto sería muy seguro sin choques; por ejemplo, si alguien desarrollara su algoritmo de hash, también tendría que adivinar el código de 4 dígitos al final ...

Answer 11

Yo también respondí la otra pregunta: P

La mejor manera es generar un carácter alfanumérico a la vez, al azar, hasta que tenga 8 de ellos. Este será entonces tu cupón.

Idealmente, la mejor manera sería elegir una secuencia el tiempo suficiente para que pueda asumir con seguridad si habrá duplicados. Tenga en cuenta que, tal vez en forma contraria a la intuición, esto ocurre con más frecuencia de lo que cree debido al problema de cumpleaños .

Por ejemplo, con 8 caracteres tiene 1785793904896 combinaciones posibles, pero si genera solo 1,573,415 cupones, tendrá un 50% de probabilidad de tener un duplicado.

Entonces, todo depende de la cantidad que desee generar y la longitud máxima del código con el que se sienta cómodo. Si está generando muchos y desea que sea breve, debe guardar los que generó anteriormente y verificar si hay duplicados en la base de datos.

Answer 12

Programming Pearls tiene varios ejemplos de algoritmos para generar conjuntos de números aleatorios, debes leerlo si estás interesado en este tipo de problema.

El libro muestra que si genera m números aleatorios con un valor menor que n , el método simple de generar números y desechar duplicados no generará más de 2m números aleatorios si m < n / 2 . Aquí está, en C ++:

void gensets(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    while (S.size() < m) {
        int t = bigrand() % n;
        S.insert(t);
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "/n";
}

Obviamente, si le preocupa que la gente adivine valores, querrá que m sea ​​mucho menor que n / 2 .

Incluso hay un algoritmo basado en conjuntos para generar m números aleatorios menores que n y cada valor es igualmente probable, sin duplicados, y una garantía de no generar más de m números aleatorios:

void genfloyd(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    for (int j = n-m; j < n; j++) {
        int t = bigrand() % (j+1);
        if (S.find(t) == S.end())
            S.insert(t); // t not in S
        else
            S.insert(j); // t in S
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "/n";
}

Sin embargo, el orden de los números no es aleatorio, por lo que probablemente no sea una buena opción para usted.

Answer 13

Este es un resumen de los mejores fragmentos de todas las otras respuestas. :)

Necesitas generar números de tarjetas de regalo que sean:

• único
• indiscutible

Los números aleatorios son indiscutibles pero no necesariamente únicos. Los números producidos por varios algoritmos son únicos pero adivinables (el algoritmo puede ser de ingeniería inversa). No conozco un solo algoritmo que proporcione ambas propiedades y, debido a la necesidad de desafiar la ingeniería inversa, cae en el dominio de la criptografía. Los no expertos, por supuesto, no deberían intentar diseñar criptosistemas.

Afortunadamente, no es necesario obtener ambas propiedades del mismo algoritmo. Los códigos de su tarjeta de regalo pueden constar de dos partes: una parte que es única (generada usando un generador lineal congruente , quizás, o módulo aritmético, o incluso solo un número entero que se incrementa cada vez) y una parte que no se puede adivinar (solo números aleatorios) ).