Générer des codes uniques en PHP / MySQL?

Question

Je travaille avec un client qui doit générer des millions de codes alphanumériques utilisés dans les cartes à gratter de magazine, les prix des cartes d'embouteillage, etc. Ils doivent être suffisamment courts pour imprimer sur une casquette, ils veulent s'assurer que les caractères ambigus tels que 1 et I, 0 et O, etc. ne sont pas inclus et qu'ils doivent être explicitement stockés pour une utilisation future - nous pouvons ' t juste un algorithme qui détermine la «validité» quand quelqu'un essaie de le racheter. Enfin, ils veulent s’assurer que les codes sont distribués de manière aléatoire à l’intérieur d’un grand "espace de code". afin que les gens ne puissent pas deviner des codes supplémentaires en parcourant l’alphabet.

Existe-t-il des arguments en faveur d’algorithmes raisonnablement efficaces pour générer ce type de jeux de codes? J'en ai gratté quelques-uns au verso d'une enveloppe, mais ce problème sent le piège des imprudents.

Answer 1

Si vous avez besoin d’environ 10 millions de clés uniques (par exemple), la meilleure approche consiste à choisir un espace clé exponentiellement plus grand et à commencer à générer de manière aléatoire. Découvrez le le paradoxe de l'anniversaire - c'est la principale chose qui devrait vous inquiéter. Si vous voulez 2 ^ n clés uniques et sécurisées, assurez-vous qu'il existe au moins 2 ^ (2 * n) valeurs possibles. Voici un algorithme approximatif O (n log n):

• Utilisez un espace de clé d'au moins 2 ^ 50 (en d'autres termes, autorisez 2 ^ 50 valeurs uniques possibles), et vous n'aurez pratiquement aucune collision dans l'ensemble de votre jeu de données - et toute personne qui forcera brutalement vos clés ont même des chances d'obtenir une clé s'ils essaient 2 ^ 25 d'entre eux.
• générer autant de nombres aléatoires que nécessaire
• indexez la base de données sur votre clé (il s’agit de l’étape O (n lg n): le tri)
• parcourez la base de données et parcourez l'ensemble de données afin de supprimer les doublons (pseudocode ci-dessous)
• Supprimez les lignes en double et vous avez terminé.

Pseudocode:

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

Answer 2

Supposons que vous puissiez utiliser un jeu de caractères, par exemple, 40 symboles de caractères supérieurs, inférieurs et numériques non ambigus.

Pour une séquence de n caractères, vous avez 40 ⁿ combinaisons

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

Ainsi, 8 caractères donnent assez d’espace de travail. Si vous générez 10 millions de codes, vous devrez essayer des centaines de milliers de combinaisons pour forcer brutalement un code.

Ou vous venez de l’autre sens - indiquez le nombre de codes possibles, le nombre de codes que vous devriez générer pour éviter le piège qu’ils appellent Anniversaire Paradox ?

Si vous prenez le code à 8 caractères, 6 553 600 000 000 correspond à environ 2 ⁴² , vous pouvez donc générer 2 codes ²¹ , ou 2 097 152

.

Answer 3

Utilisez un algorithme de mot de passe à utilisation unique?

La RFC4225 détaille l’un basé sur l’algorithme HMAC.

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

mais au lieu d'utiliser un codage base10 de 0 à 9 chiffres, utilisez base32.

Answer 4

Quelle que soit la méthode que vous utilisez, je vous suggère d'ajouter un ou deux chiffres de contrôle en guise de "première ligne". défense contre les personnes qui entrent ou tentent d’inventer un numéro.

Answer 5

Curieusement, avec la graine suivante, je n'ai pu générer que 32 chaînes uniques.

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

Avec une graine plus longue, j'ai pu générer beaucoup plus de 40 000 chaînes uniques.

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567894545894545898945458989456789ABCDEFGHJKLMNPQRSTUVWXYZ2345678945458945454589