Gerando códigos únicos em PHP / MySQL?

StackOverflow https://stackoverflow.com/questions/219475

Pergunta

Eu estou trabalhando com um cliente que precisa gerar milhões de códigos alfanuméricos utilizados na revista scratch-off cartões, bottlecap prêmios, e assim por diante. Eles têm de ser suficientemente curto para imprimir em um boné, eles querem ter certeza de que personagens ambíguos como 1 e I, 0 e O, etc. não estão incluídos, e eles têm de ser explicitamente armazenada para uso futuro - podemos' t apenas tem um algoritmo que determina 'validade' quando alguém tenta resgatar um. Finalmente, eles querem ter certeza de que os códigos são distribuídos aleatoriamente dentro de um grande "espaço de código" para que as pessoas não podem apenas adivinhar códigos adicionais, caminhando através do alfabeto.

Existem ponteiros para com algoritmos razoavelmente eficientes para gerar esses tipos de conjuntos de códigos? Eu riscado alguns para fora na parte de trás de um envelope, mas este problema cheira como uma armadilha para os incautos.

Foi útil?

Solução

Se você precisa de cerca de 10 milhões de chaves únicas (por exemplo), a melhor abordagem é escolher um espaço-chave que é exponencialmente maior, e começar aleatoriamente gerando. Leia sobre o aniversário Paradox - é a principal coisa que você deve se preocupar. Se você quiser 2 ^ n chaves únicas e seguras, certifique-se que há pelo menos 2 ^ (2 * n) valores possíveis. Aqui está uma áspera O (n log n) algoritmo:

  • Use um espaço de chave de pelo menos 2 ^ 50 (assim, em outras palavras, permitir que 2 ^ 50 possíveis valores exclusivos), e você terá quase nenhum colisões em todo o seu conjunto de dados - e qualquer força bruta suas chaves vai ter sobre até mesmo chances de conseguir uma chave, se tentar 2 ^ 25 deles.
  • gerar tantos números aleatórios como você precisa
  • índice de banco de dados em sua chave (esta é a O (n lg n) passo: o tipo)
  • página através do DB e repita ao longo de todo o conjunto de dados de duplicatas guarnição (pseudocódigo abaixo)
  • Excluir as linhas duplicadas, e você está feito.

Pseudocódigo: 

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

Outras dicas

Vamos supor que você pode usar um conjunto de caracteres de, digamos, 40 símbolos de superior inequívoca, abaixar e caracteres numéricos.

Para uma seqüência de n caracteres, você tem 40 n combinações

  • 40 4 = 2560000
  • 40 5 = 102400000
  • 40 6 = 4096000000
  • 40 7 = 163840000000
  • 40 8 = 6.553.600.000.000

Assim, 8 caracteres dá um bom espaço bonito trabalhar em - se você gerou 10 milhões de códigos, você teria que tentar centenas de milhares de combinações para a força bruta de um código.

Ou você vem a partir de outra direção - dar o número de possíveis códigos, quantos códigos deve você gera para evitar a armadilha que eles chamam de aniversário Paradox ?

Como o código de 8 char, 6.553.600.000.000 é de aproximadamente 2 42 , assim que você pode razoavelmente gerar 2 21 códigos a partir dele, ou 2.097.152

Use um algoritmo de senha uma vez?

detalhes RFC4225 uma baseada em algoritmo HMAC.

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

mas em vez de usar 0-9 dígitos Base10 codificação, uso base32.

método Tudo o que você usar, eu sugiro que você adicionar um dígito de verificação ou dois como uma defesa "de primeira linha" contra pessoas mal entram ou tentando inventar um número.

Curiosamente, com a seguinte semente que eu só foi capaz de gerar 32 cordas únicas.

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

Com uma semente mais eu era capaz de gerar muitos mais -. Gerados 40.000 cordas únicas com sucesso

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top