php - PHP/MySQL で一意のコードを生成しますか?

Question

私は、雑誌のスクラッチカードやボトルキャップの賞品などで使用される何百万もの英数字コードを生成する必要があるクライアントと仕事をしています。キャップに印刷できるように十分に短くする必要があり、1 と I、0 と O などのあいまいな文字が含まれないようにする必要があり、将来の使用のために明示的に保存する必要があります。誰かが引き換えようとしたときに「有効性」を判断するアルゴリズムを持っているだけではありません。最後に、コードが大きな「コード空間」内にランダムに分散されていることを確認して、アルファベットをたどって追加のコードを推測できないようにしたいと考えています。

この種のコードセットを生成するための合理的に効率的なアルゴリズムへのポインタはありますか? 封筒の裏にいくつか引っかき傷をつけたことがありますが、この問題は不注意な人にとっては罠のようなにおいがします。

score 13 · Accepted Answer

たとえば、約 1,000 万個の一意のキーが必要な場合、最善のアプローチは、指数関数的に大きいキー空間を選択し、ランダムな生成を開始することです。誕生日のパラドックスについて読んでください- それはあなたが心配すべき主なことです. 2^n の一意で安全なキーが必要な場合は、少なくとも 2^(2 * n) の可能な値があることを確認してください。大まかな O(n log n) アルゴリズムは次のとおりです。

少なくとも 2^50 のキースペースを使用する (つまり、2^50 の可能な一意の値を許可する) と、データセット全体で衝突がほとんど発生しなくなります。 2^25 を試した場合にキーを取得する確率。
必要な数の乱数を生成する
キーでデータベースのインデックスを作成します (これは O(n lg n) ステップです: ソート)
DB をページングし、データセット全体を反復処理して重複を削除します (以下の疑似コード)。
重複する行を削除すれば完了です。

擬似コード:

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

score 7 · Accepted Answer

たとえば、明確な大文字、小文字、および数字の 40 記号の文字セットを使用できるとします。

n 文字のシーケンスの場合、40 ^{n 個}の組み合わせがあります

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

したがって、8 文字は作業するのに十分なスペースを提供します。1,000 万のコードを生成した場合、コードをブルートフォースするために何十万もの組み合わせを試す必要があります。

または、別の方向から来る -考えられるコードの数を教えてください。誕生日のパラドックスと呼ばれる罠を回避するには、いくつのコードを生成する必要がありますか?

8 文字のコードを使用すると、6,553,600,000,000 は約 2 ^{42になるため、そこから 2}²¹コード、つまり 2,097,152 を合理的に生成できます。

score 0 · Accepted Answer

ワンタイムパスワードアルゴリズムを使用しますか?

RFC4225 には、HMAC アルゴリズムに基づく詳細が記載されています。

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

ただし、0 ～ 9 桁の base10 エンコーディングを使用する代わりに、base32 を使用してください。

score 0 · Accepted Answer

どのような方法を使用する場合でも、数字の入力ミスや発明を試みる人に対する「最前線」の防御として、1 つまたは 2 つのチェックディジットを追加することをお勧めします。

score -3 · Accepted Answer

奇妙なことに、次のシードでは、32 個の一意の文字列しか生成できませんでした。

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

より長いシードを使用すると、さらに多くの文字列を生成でき、40,000 の一意の文字列を正常に生成できました。

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789

php - PHP/MySQL で一意のコードを生成しますか?

5 に答える 5

Related

Reference