Generazione di codici univoci in PHP / MySQL?

Question

Sto lavorando con un cliente che ha bisogno di generare milioni di codici alfanumerici utilizzati nelle carte gratta e vinci di riviste, nei premi bottlecap e così via. Devono essere abbastanza corti da stampare su un berretto, vogliono assicurarsi che i caratteri ambigui come 1 e I, 0 e O, ecc. Non siano inclusi e debbano essere esplicitamente memorizzati per uso futuro - possiamo " Ho solo un algoritmo che determina la "validità" quando qualcuno cerca di riscattarne uno. Infine, vogliono assicurarsi che i codici siano distribuiti casualmente all'interno di un ampio "spazio di codice" in modo che le persone non possano semplicemente indovinare codici aggiuntivi camminando attraverso l'alfabeto.

Esistono indicazioni per algoritmi ragionevolmente efficienti per la generazione di questo tipo di insiemi di codici? Ne ho graffiate alcune sul retro di una busta, ma questo problema puzza di trappola per gli incauti.

Answer 1

Se hai bisogno di circa 10 milioni di chiavi univoche (ad esempio), l'approccio migliore è scegliere uno spazio-chiave che sia esponenzialmente più grande e iniziare a generare in modo casuale. Leggi il Birthday Paradox - è la cosa principale di cui dovresti preoccuparti. Se si desidera 2 ^ n chiavi univoche e sicure, assicurarsi che vi siano almeno 2 ^ (2 * n) valori possibili. Ecco un algoritmo O (n log n) approssimativo:

• Utilizza uno spazio chiave di almeno 2 ^ 50 (quindi, in altre parole, consenti 2 ^ 50 possibili valori univoci) e avrai a malapena collisioni nell'intero set di dati - e chiunque sia costretto a forzare le tue chiavi hanno persino probabilità di ottenere una chiave se provano 2 ^ 25 di esse.
• genera tutti i numeri casuali di cui hai bisogno
• indicizza il database sulla tua chiave (questo è il passo O (n lg n): l'ordinamento)
• sfoglia il DB e scorre l'intero set di dati per tagliare i duplicati (pseudocodice di seguito)
• Elimina le righe duplicate e il gioco è fatto.

Pseudocodice:

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

Answer 2

Supponiamo che tu possa usare un set di caratteri, diciamo, 40 simboli di caratteri univoci superiori, inferiori e numerici.

Per una sequenza di n caratteri, hai 40 ⁿ combinazioni

• 40 ⁴ = 2.560.000
• 40 ⁵ = 102.400.000
• 40 ⁶ = 4.096.000.000
• 40 ⁷ = 163.840.000.000
• 40 ⁸ = 6.553.600.000.000

Quindi 8 caratteri offrono uno spazio abbastanza buono in cui lavorare - se hai generato 10 milioni di codici, dovresti provare centinaia di migliaia di combinazioni per forzare un codice.

Oppure vieni dall'altra direzione - indica il numero di possibili , quanti codici dovrebbero che generi per evitare la trappola che chiamano Compleanno Paradox ?

Prendendo il codice 8 caratteri, 6.553.600.000.000 equivale a circa 2 ⁴² , quindi potresti ragionevolmente generare 2 ²¹ codici, o 2.097.152

Answer 3

Utilizzare un algoritmo password monouso?

RFC4225 ne dettaglia uno in base all'algoritmo HMAC.

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

ma invece di usare la codifica base10 da 0-9 cifre, usa base32.

Answer 4

Qualunque metodo tu usi, ti suggerirei di aggiungere una o due cifre di controllo come "prima riga" difesa contro le persone che entrano male o cercano di inventare un numero.

Answer 5

Stranamente, con il seguente seme sono stato in grado di generare solo 32 stringhe uniche.

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

Con un seme più lungo sono stato in grado di generare con successo molte più 40.000 stringhe uniche generate.

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789