algorithm - 礼品卡代码算法

Question

我最近发布了这个关于用户可以在线兑换的类似礼品卡的优惠券代码的问题。我想在大键空间、低猜测性和人类可读性之间找到最佳折衷。现在我开始实施了，我意识到我遇到了另一个问题，更多的是算法挑战。

假设我采用某种代码格式——为简单起见，假设从 A 到 Z 的 10 个字符，然后我开始生成凭证。什么是正确的算法来做到这一点？！

我的第一种方法是从 0 到 308,915,776 对所有可能的代码进行编号，然后开始生成该范围内的随机数。不过，这显然有一个大问题——我必须对照所有以前生成的凭证代码检查我的随机数，如果它与现有的代码冲突，我将不得不丢弃代码并尝试另一个代码。随着系统积累更多数据，它会变慢。在只剩下一个代码的极端情况下，系统几乎不可能正确猜测它。

我可以预先生成所有代码并打乱它们，然后按顺序使用它们。但这意味着我必须存储很多代码，实际上我的密钥空间比我描述的要大，所以我们谈论的是非常大量的数据。所以这也不是太可取。

所以这让我可以按顺序使用代码。我不想要可猜测的优惠券代码。购买代金券“AAAAAAAAAY”的用户如果输入“AAAAAAAAAZ”，应该不太可能获得另一个有效代码。

我可以洗牌我的字母表和我的位置，而不是

'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 我用

'LYFZTGKBNDRAPWEOXQHVJSUMIC'

所以而不是职位

9 8 7 6 5 4 3 2 1 0 位置是

1 8 0 7 5 4 3 9 2 6

使用这个逻辑，给定代码

LNWHDTECMA

下一个代码是

LNEHDTECMA

这绝对是难以猜测的。但它们之间的距离仍然只有一个字符，并且只需其中两张凭证，您就会知道哪个位置在增加，并且您将有 90% 的机会在 24 次或更少的猜测中获得下一个代码。

我的“逃生舱”是抛弃所有这些并使用 GUID。它们的字符比我希望我的用户输入的字符多，并且包含类似的字符，例如 I/1 和 O/0，但它们神奇地使上述所有令人头疼的问题都消失了。不过，我觉得这个很有趣，也许你也是。我很想听听一些替代建议。你有什么？

谢谢！

score 15 · Accepted Answer

两个随机生成的代码发生冲突的可能性与用户猜测有效代码的可能性基本相同——您无法阻止用户猜测。所以你必须有一个比实际使用的代码数量大得多的密钥空间，随机冲突也极不可能发生（尽管，由于生日悖论，至少如果你想要你的代码，可能不足以完全忽略它们相当短），并且检查现有代码并在发生冲突时重新生成是一种完全可行的策略。

score 11 · Accepted Answer

使用 N 位序列号 R，结合连接对 (R, S) 的 M 位哈希 H，其中 S 是您不发布的一些秘密“盐”S。然后以您喜欢的任何可逆方式对 (R,H) 对进行字母数字编码。如果您喜欢 MD5* 或 SHA 之类的算法，但位数太高，则只需取标准哈希算法的 M 个最低有效位。

您可以轻松验证：解码字母数字编码，以便您可以看到 R 和 H。然后计算 H' = hash(R+S) 并验证 H = H'。

编辑： R 可以是递增的序列号或随机数或其他，只要确保您使用每个值不超过一次。

*在有人说“MD5 已损坏”之前，让我提醒您，MD5 的已知弱点是碰撞攻击，而不是原像攻击。此外，通过使用未发布的秘密盐值，您拒绝攻击者测试您的安全机制的能力，除非他/她可以猜测盐值。如果您感到偏执，请选择两个盐值 Sprefix 和 Ssuffix，并计算串联三元组 (Sprefix,R,Ssuffix) 的哈希值。

score 5 · Accepted Answer

一些随机数生成器有一个有趣的特性：使用得当，它们不会长时间生成重复的数字。它们产生一种叫做完整循环的东西。使用其中描述的一种算法，为其播种，您将拥有许多唯一数字，

添加一种将数字映射到字符的智能方法，您就得到了代码。

score 4 · Accepted Answer

4

于 2010-01-18T15:51:44.787 回答

score 4 · Accepted Answer

Programming Pearls有几个生成随机数集的算法示例，如果您对此类问题感兴趣，应该阅读它。

这本书表明，如果你生成m值小于的随机数n，生成数字并丢弃重复项的简单方法将生成的随机数不会超过2mif 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";
}

但是，数字的顺序不是随机的，所以这对您来说可能不是一个好的选择。

score 3 · Accepted Answer

我阅读了整个评论，发现许多人在其他地方使用非常聪明和复杂的手段来保护。猜测我的算法的机会是 1/2600000 你所要做的就是在每一代之后更改盐前缀盐后缀

我选择了 4 个数字的盐前缀
和4个数字的后缀
那么主码是9个数字可互换
然后使用这种格式sprefix +random_numbers+ssuffix
我将立即散列将其存储到数据库中的格式
该查询可以帮助删除类似的代码
一旦你打印了 9，就应该更改后缀和前缀！(362880) 次。

score 2 · Accepted Answer

我也回答了另一个问题：P

最好的方法是一次随机生成一个字母数字字符，直到你有 8 个。这将成为您的代金券。

理想情况下，最好的方法是选择一个足够长的序列，以便您可以安全地假设是否会有任何重复。请注意，也许与直觉相反，由于生日问题，这种情况发生的频率比您想象的要多。

例如，使用 8 个字符，您有 1785793904896 种可能的组合，但如果您只生成 1,573,415 个凭证，您将有 50% 的机会出现重复。

所以，这一切都取决于你想要生成多少，以及你能接受的代码的最大长度。如果你生成了很多并且你想保持简短，你应该保存你之前生成的那些，并检查数据库是否有重复。

score 2 · Accepted Answer

这是所有其他答案中最好的部分的总结。:)

您需要生成以下礼品卡号码：

独特
猜不透

随机数是不可猜测的，但不一定是唯一的。各种算法产生的数字是唯一的，但可以猜测（该算法可以进行逆向工程）。我不知道有一种算法可以同时提供这两种属性，而且由于需要对抗逆向工程，它属于密码学领域。当然，非专家不应该尝试设计密码系统。

幸运的是，您不必从同一个算法中获得这两个属性。您的礼品卡代码可以由两部分组成：一个是唯一的（使用线性同余生成器生成，也许是模算术，甚至只是一个您每次递增的整数）和一个不可猜测的部分（只是随机数）。

score 1 · Accepted Answer

我认为最好的方法是 Andreas 建议的方法。但我的回答是关于一个有趣的相关讨论。

您想生成一个数字序列，它们一起形成 S = {1, ..., MAX} 的排列。一种方法是在 S 上取循环群的元素。例如，数字在上R = {x modulo p, x^2 modulo p, x^3 modulo p, ..., x^(p-1) modulo p}形成循环群{1, ..., p-1}，前提p是是素数并且x互质于p。因此，如果您选择 MAX 作为质数，则确实使用此序列。

你想要一个“难以破解”的序列。用于足够难以破解的序列的生成器称为伪随机生成器（当然，您可能不需要那种难以破解的）。一个例子是R上面元素的最后一位，前提p是保密（我正确吗？）。但是安德烈亚斯的答案已经使用了（伪）随机数源，因此不能称为伪随机生成器。

如果您对伪随机生成器感兴趣，可以在 Knuth 著名著作的第 2 卷中详细讨论它们。

score 1 · Accepted Answer

根据Jason Orendoff 的回答，我整理了一个算法来生成礼品卡代码。基本上，它有两个 40 位数字：一个确保它是唯一的，另一个确保它难以猜测。

40 位随机数部分足以进行2^40次猜测中的 1 次；
40 位序列号部分足以保持34.8 年的唯一性（假设我们每毫秒生成一张礼品卡。）

然后使用Base32将总 80 位序列转换为 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);
    }
}

score 1 · Accepted Answer

可能有效的方法是简单地利用创作时间来发挥自己的优势。比如说，年的最后两位数，两位数的月份，两位数的日期，两位数的小时，两位数的分钟，两位数的秒，然后将秒数输出到微秒。如果需要进一步混淆，请将它们预先加扰（例如 MYmdshhdMmYs 而不是 YYMMddhmmss）。然后更改基数（也许是五进制）以进一步拒绝任何猜测尝试。这有两个主要好处： 1-使用日期，包括年份，将破坏任何重复，因为同一时间不会经过两次。一百年后才有风险。唯一需要担心的是可能会在同一微秒内创建两个，因此禁止一次创建多个是一项简单的任务。毫秒延迟将解决问题。

2-猜测将非常困难。不仅要弄清楚数字（和字母！）的基数和顺序将是一项艰巨的任务，而且精确到微秒会使序列在很大程度上无关紧要。更不用说客户很难弄清楚他们以多少微秒的时间购买以及他们的时钟与您的时钟如何匹配。

反对意见可能是“等等！那是 17 位数字 (YYMMDDhhmmss.sssss)，但之后带入更大的基数会减少它。使用 10 个数字和 26 个字母，以 36 为基数，意味着 11 位代码将涵盖所有可能性。如果大写和小写不可互换，则可以将数据压缩到 10 位数的目标，而不会出现零问题。

score 0 · Accepted Answer

0

于 2010-01-18T15:39:57.797 回答

score 0 · Accepted Answer

我支持使用加密哈希——从 MD5 中获取位非常简单。为了使事情可读，我想到了以下想法：获取单词列表，并使用键的位来索引单词列表。我的单词列表大约有 100 000 个单词，所以每个单词大约 16 位，对于四个单词来说，它提供了一个 64 位的键空间。结果通常是可读的。

例如，上一段的密码签名是

神风敢死队的新鲜豪宅在咳痰

（我的单词列表倾向于更大的键空间；如果你想要更短的短语，你的单词就更少。）

如果你手边有一个 MD5 库，那么这个策略很容易实现——我用大约 40 行 Lua 来实现。

algorithm - 礼品卡代码算法

13 回答 13

Related

Reference