algorithm - ギフトカードコードのアルゴリズム

Question

最近、ユーザーがオンラインで利用できるギフトカードのようなバウチャーのコードに関するこの質問を投稿しました。私は、大きなキースペース、低い推測可能性、および人間の読みやすさの間の最良のトレードオフを見つけたかったのです。実装に取り​​掛かった今、私はまったく別の問題を抱えていることに気付きました。それは、よりアルゴリズム的な課題です。

簡単にするためにAからZまでの10文字など、いくつかのコード形式を採用し、バウチャーの生成を開始するとします。これを行うための正しいアルゴリズムは何ですか？！

私の最初のアプローチは、0から308,915,776までのすべての可能なコードに番号を付けてから、その範囲の乱数の生成を開始することです。ただし、これには明らかに大きな問題があります。以前に生成されたすべてのバウチャーコードに対して乱数を確認する必要があり、既存のバウチャーコードと衝突する場合は、コードを破棄して別のコードを試す必要があります。システムがより多くのデータを蓄積すると、速度が低下します。極端な場合、コードが1つしか残っていない場合、システムがそれを正しく推測することはほぼ不可能です。

すべてのコードを事前に生成してシャッフルしてから、順番に使用することができます。しかし、これは私が多くのコードを保存しなければならないことを意味し、実際、私のキースペースは私が説明したものよりも大きいので、非常に大量のデータについて話しています。したがって、それもあまり望ましくありません。

したがって、これにより、コードを順番に使用することになります。ただし、推測可能なバウチャーコードは必要ありません。バウチャー「AAAAAAAAAY」を購入したユーザーは、「AAAAAAAAAZ」と入力した場合、別の有効なコードを取得する可能性は高くありません。

アルファベットと位置をシャッフルして、代わりに

'ABCDEFGHIJKLMNOPQRSTUVWXYZ'私が使用する

'LYFZTGKBNDRAPWEOXQHVJSUMIC'

位置の代わりに

9 8 7 6 5 4 3 210位置は

1 8 0 7 5 4 3 9 2 6

このロジックを使用して、コードを指定します

LNWHDTECMA

次のコードは

LNEHDTECMA

これは間違いなく推測しにくいです。しかし、それらはまだ互いに1文字しか離れておらず、これらのバウチャーのうち2つだけが与えられると、どの位置が増加しているかがわかり、24回以内の推測で次のコードを取得する可能性が90％になります。

私の「エスケープハッチ」は、これらすべてを捨ててGUIDを使用することです。ユーザーが入力する必要のある文字よりも多くの文字があり、I/1やO/0のような類似の文字が含まれていますが、魔法のように上記の頭痛の種をすべて解消します。それでも、私はこれについて考えるのを楽しんでいます、多分あなたもそうです。私はいくつかの代替案を聞きたいです。あなたはどれだけ持ってる？

ありがとう！

Answer 1

ランダムに生成された 2 つのコードが衝突する可能性は、ユーザーが有効なコードを推測するのと基本的に同じです。ユーザーが推測するのを防ぐことはできません。したがって、実際に使用されるコードの数よりもはるかに大きなキースペースが必要であり、ランダムな衝突が発生する可能性も非常に低くなります (ただし、誕生日のパラドックスのおかげで、少なくともコードが必要な場合は、それらを完全に無視する可能性は低いとは言えません)。既存のコードと照合して衝突が発生した場合に再生成することは、完全に実行可能な戦略です。

Answer 2

連結されたペア (R, S) の M ビット ハッシュ H と組み合わせた N ビットのシリアル番号 R を使用します。ここで、S は公開しない秘密の「ソルト」S です。次に、ペア (R,H) を任意の可逆的な方法で英数字でエンコードします。MD5* や SHA などのアルゴリズムが好きで、ビット数が多すぎる場合は、標準のハッシュ アルゴリズムの最下位 M ビットを使用します。

簡単に確認できます。英数字エンコーディングをデコードして、R と H を確認します。次に、H' = hash(R+S) を計算し、H = H' であることを確認します。

編集: R は、インクリメントするシリアル番号またはランダムなどにすることができます。ただし、各値を複数回使用しないようにしてください。

*誰かが「MD5 は壊れている」と言う前に、MD5 の既知の弱点は衝突攻撃であり、プリイメージ攻撃ではない ことを思い出させてください。また、公開されていない秘密のソルト値を使用することで、攻撃者がソルト値を推測できない限り、セキュリティ メカニズムをテストする能力を拒否します。偏執的であると感じる場合は、2 つのソルト値 Sprefix と Ssuffix を選択し、連結されたトリプル (Sprefix,R,Ssuffix) のハッシュを計算します。

Answer 3

一部の乱数ジェネレーターには興味深い特性があります。正しく使用すると、長期間にわたって重複する数値が生成されません。それらはフルサイクルと呼ばれるものを生成します。そこで説明されているアルゴリズムの1つを使用してシードすると、多くの一意の番号が得られます。

数字を文字にマッピングするスマートな方法を追加すると、コードを取得できます。

Answer 4

I would say to use a "perfect hash" - http://en.wikipedia.org/wiki/Perfect_hash_function combined with a 4-digit random number...

So just increment your voucher code each time, then hash it, add a 4 digit random number and I would also add a check digit to the end (as Alix Axel suggested).

This would be very secure with no clashes - for example if someone worked out your hashing algorithm, they would also have to guess the 4-digit code at the end...

Answer 5

Programming Pearlsには、一連の乱数を生成するアルゴリズムの例がいくつかあります。この種の問題に興味がある場合は、それを読んでください。

この本は、m値が 未満の乱数を生成した場合、数値nを生成して重複を捨てるという単純なアプローチでは、 の場合に2m乱数しか生成されないことを示していますm < n / 2。これが 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";
}

明らかに、人々が値を推測することを心配している場合は、mよりもはるかに小さくする必要がありn / 2ます。

m各値の可能性が等しいより少ない乱数を生成するセットベースのアルゴリズムもあり、重複はなく、乱数n以上を生成しないことが保証されます。m

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";
}

ただし、数字の順序はランダムではないため、これはおそらく適切な選択ではありません。

Answer 6

私はコメント全体を読み、他の多くの人々が非常に巧妙で洗練された手段を使用して保護していることを発見しました。私のアルゴリズムで推測できる可能性は 1/2600000 必要なのは、生成ごとにソルト接頭辞のソルト接尾辞を変更することだけです

• 4 桁のソルト プレフィックスを選択しました
• および 4 つの数字のサフィックス
• メインコードは交換可能な9つの数字です
• 次に、この形式を使用してsprefix +random_numbers+ssuffix
• すぐにデータベースに保存する形式をハッシュします
• クエリは同様のコードを削除するのに役立ちます
• 9 を印刷したら、サフィックスとプレフィックスを変更する必要があります。(362880) 回。

Answer 7

私も他の質問に答えました：P

最良の方法は、8文字になるまで、一度に1文字の英数字をランダムに生成することです。これがバウチャーになります。

理想的には、重複があるかどうかを安全に推測できるように、十分な長さのシーケンスを選択するのが最善の方法です。おそらく直感に反して、これは誕生日の問題のためにあなたが思っているよりも頻繁に起こることに注意してください。

たとえば、8文字の場合、1785793904896の組み合わせが可能ですが、1,573,415のバウチャーしか生成しない場合、50％の確率で重複することになります。

したがって、それはすべて、生成するコードの数と、快適なコードの最大長によって異なります。多くを生成していて、それを短くしたい場合は、以前に生成したものを保存し、データベースと重複していないかどうかを確認する必要があります。

Answer 8

これは、他のすべての回答の最良の部分の要約です。:)

次のようなギフトカード番号を生成する必要があります。

• 個性的
• 推測できない

乱数は推測できませんが、必ずしも一意ではありません。さまざまなアルゴリズムによって生成される数値は一意ですが、推測可能です（アルゴリズムはリバースエンジニアリングできます）。両方のプロパティを提供する単一のアルゴリズムを知りません。リバースエンジニアリングに逆らう必要があるため、暗号化の領域に分類されます。もちろん、専門家でない人は暗号システムを設計しようとすべきではありません。

幸い、同じアルゴリズムから両方のプロパティを取得する必要はありません。ギフトカードコードは、2つの部分で構成できます。一意の部分（線形合同法を使用して生成されるか、モジュロ算術、または毎回インクリメントする整数）と推測できない部分（乱数だけ）です。 ）。

Answer 9

効果的に機能する可能性があるのは、単純に創造の時間を有利に利用することです。たとえば、年の下 2 桁、2 桁の月、2 桁の日、2 桁の時、2 桁の分、2 桁の秒、そして秒を繰り上げて、たとえばマイクロ秒にします。さらに難読化が必要な場合は、それらを事前にスクランブルしてください (たとえば、YYMMddhmmss の代わりに MYmdshhdMmYs)。次に、基数を (おそらく 5 進数に) 変更して、それ以上の推測を阻止します。これには 2 つの大きな利点があります。100年経って初めて危険が生じます。唯一の懸念は、同じマイクロ秒で 2 つが作成される可能性があることです。一度に複数の作成を禁止するのは簡単な作業です。ミリ秒の遅延で問題が解決します。

2-推測は非常に困難です。数値 (および文字!) の基数と順序を理解するのは困難な作業になるだけでなく、マイクロ秒にまで踏み出すことは、シーケンスをほとんど意味のないものにします。何マイクロ秒で購入したか、時計があなたの時計とどのように一致するかを顧客が把握するのがどれほど難しいかは言うまでもありません。

反対意見は、「待ってください! これは 17 桁 (YYMMDDhhmmss.sssss) ですが、後で基数を大きくすると小さくなります。10 桁の数字と 26 文字を使用して基数 36 にすると、11 桁のコードですべての可能性がカバーされることになります。大文字と小文字が互換性がない場合、データは問題なく 10 桁の目標まで圧縮できます。

Answer 10

Jason Orendoff の回答に基づいて、ギフト カード コードを生成するアルゴリズムをまとめました。基本的に、2 つの 40 ビット数値があります。1 つは一意であることを保証するためのもので、もう 1 つは推測しにくいことを保証するためのものです。

• 40 ビットの乱数部分は、2^40の確率で 1回の推測に十分です。
• 40 ビットの連番部分は、34.8 年間 の一意性に十分です (ミリ秒ごとに 1 つのギフト カードを生成すると仮定します)。

次に、合計 80 ビットのシーケンスがBase32を使用して 16 文字の文字列に変換されます。

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 11

アンドレアスが提案した方法が最善の方法だと思います。しかし、私の答えは、興味深い関連する議論についてです。

S = {1, ..., MAX} の順列を形成する数列を生成したいとします。これを行う 1 つの方法は、S 上の巡回群の元を取ることです。たとえば、が素数であり、と互いに素である場合、数値R = {x modulo p, x^2 modulo p, x^3 modulo p, ..., x^(p-1) modulo p}は 上の巡回群を形成します。したがって、素数として MAX を選択した場合は、この数列を使用します。 {1, ..., p-1}pxp

「クラックしにくい」シーケンスが必要です。十分にクラックしにくいシーケンスのジェネレーターは、疑似乱数ジェネレーターと呼ばれます (もちろん、クラックするのに十分なタフなシーケンスは必要ありません)。例は、R上記の要素の最後の桁です。ただし、p秘密にされている場合 (私は正しいですか?)。しかし、Andreas による回答では、(疑似) 乱数のソースが既に使用されているため、疑似乱数ジェネレーターとは言えません。

疑似乱数発生器に興味がある場合は、Knuth の有名な本の第 2 巻で詳しく説明されています。

Answer 12

Answer 13

MD5 からビットを取得するのは非常に簡単です。読みやすくするために、次のアイデアを思いつきました。単語のリストを取得し、キーのビットを使用して単語のリストにインデックスを付けます。私の単語リストは約 100,000 語なので、1 語あたり約 16 ビットで、4 語で 64 ビットのキースペースになります。結果は通常、非常に読みやすいものです。

たとえば、前の段落の暗号署名は

カミカゼの新生屋敷の吐き気

(私の単語リストは、より大きなキースペースに傾いています。短いフレーズが必要な場合は、単語が少なくなります。)

MD5 ライブラリが手元にある場合、この戦略は非常に簡単に実装できます。Lua の約 40 行で実装できます。