礼品卡代码算法

发布于 2024-08-18 14:44:33 字数 1121 浏览 3 评论 0原文

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

假设我采用某种代码格式 - 为简单起见，从 A 到 Z 为 10 个字符，然后我开始生成凭证。执行此操作的正确算法是什么？！

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

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

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

而不是

我可以打乱我的字母表和位置，这样我就可以使用

'LYFZTGKBNDRAPWEOXQHVJSUMIC'

'ABCDEFGHIJKLMNOPQRSTUVWXYZ' ，这样就可以代替位置

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 等类似字符，但它们神奇地使上述所有令人头疼的问题消失了。尽管如此，我还是很高兴思考这个问题，也许你也是。我很想听听一些替代建议。你有什么？

谢谢！

原文

I recently posted this question about codes for a gift-card-like voucher that users can redeem online. I wanted to find the best tradeoff between large keyspace, low guessability, and human readability. Now that I'm into implementation I realize I've got another problem altogether, more of an algorithmic challenge.

Let's assume I adopt some code format - say 10 characters from A to Z for simplicity, and I start generating vouchers. What is the correct algorithm to do this?!

My first approach is to number all possible codes from 0 to 308,915,776, then start generating random numbers in that range. This obviously has a big problem though - I have to check my random number against all previously generated voucher codes and if it collides with an existing one I'll have to discard the code and try another. As the system accumulates more data it will slow down. At the extreme when there is only one code left it will be nearly impossible for the system to guess it correctly.

I could pre-generate all codes and shuffle them, then consume them in order. But this means I have to store many codes, and in fact my keyspace is bigger than the one i described, so we're talking about a very large amount of data. So that's also not too desirable.

So this leaves me with using the codes sequentially. I do not want guessable voucher codes though. The user who buys voucher "AAAAAAAAAY" should not have a good chance of getting another valid code if they type in "AAAAAAAAAZ".

I can shuffle my alphabet and my positions so that instead of

'ABCDEFGHIJKLMNOPQRSTUVWXYZ' i use

'LYFZTGKBNDRAPWEOXQHVJSUMIC'

and so that instead of positions

9 8 7 6 5 4 3 2 1 0
the positions are

1 8 0 7 5 4 3 9 2 6

Using this logic, given the code

LNWHDTECMA

the next code would be

LNEHDTECMA

This is definitely way less guessable. But they're still only one character off from each other, and given just two of these vouchers you would know which position is incrementing, and you would have a 90% chance of getting the next code in 24 guesses or less.

My "escape hatch" is to ditch all this and go with GUIDs. They have more characters than I wanted my users to have to type in, and contain similar characters like I/1 and O/0, but they magically make all of the above headaches go away. Still, I'm having fun thinking about this, maybe you are too. I'd love to hear some alternate suggestions. What have you got?

Thanks!

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

庆幸我还是我 2024-08-25 14:44:34

有效的方法就是充分利用创作时间。例如，年份的最后两位数、月份的两位数、日期的两位数、小时的两位数、分钟的两位数、秒的两位数，然后将秒移至微秒。如果需要进一步混淆，请将它们预先加扰（例如 MYmdshhdMmYs 而不是 YYMMddhmmss）。然后更改基数（也许是十五进制）以进一步阻止任何猜测尝试。
这有两个主要好处：
1-使用日期（包括年份）将消除任何重复，因为同一时间不会出现两次。一百年后才有危险。唯一的问题是可能会在同一微秒内创建两个，对此，不允许一次创建多个将是一项简单的任务。延迟一毫秒就可以解决问题。

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

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

回复收藏 0 原文

半步萧音过轻尘 2024-08-25 14:44:34

这里有一个想法：

ID = 每个凭证都有一个唯一的（自动递增？） ID
CHECKSUM = 应用 Verhoeff 或 Luhn 算法对 ID
VOUCHER = 基础转换生成的 CHECKSUM从基数 10 到基数 36

另请参阅此相关 SO 问题：创建一个小（<10 位数字）、不（非常）安全的“哈希”的想法。

使此方法更安全的一种简单方法是使用非自动递增的 ID 值，一种选择可能是使用 ID 作为 UNIX 时间戳的最后 6 或 7 位数字并计算校验和。

回复收藏 0 原文

影子的影子 2024-08-25 14:44:34

我赞同使用加密哈希——从 MD5 中获取位非常简单。
为了使内容可读，我想到了以下想法：获取单词列表，并使用键的位来索引单词列表。我的单词列表大约有 100 000 个单词，因此每个单词大约有 16 位，这对于四个单词来说提供了 64 位密钥空间。结果通常非常可读。

例如上一段的密码签名是

神风特攻队的新鲜宅邸吐痰

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

如果你手边有一个 MD5 库，这个策略很容易实现——我用大约 40 行就可以完成的卢阿。

回复收藏 0 原文

一梦等七年七年为一梦 2024-08-25 14:44:33

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

回复收藏 0 原文

往事风中埋 2024-08-25 14:44:33

使用 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)。

回复收藏 0 原文

梦萦几度 2024-08-25 14:44:33

一些随机数生成器有一个有趣的特性：如果使用得当，它们不会在很长一段时间内生成重复的数字。他们产生了一种叫做完整周期的东西。
使用那里描述的算法之一，对其进行播种，您将拥有许多唯一的数字，

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

回复收藏 0 原文

伊面 2024-08-25 14:44:33

我想说使用“完美哈希” - http://en.wikipedia.org/wiki/Perfect_hash_function 与 4 位随机数相结合...

因此，只需每次增加您的优惠券代码，然后对其进行哈希处理，添加一个 4 位随机数，我还会在末尾添加一个校验位（正如 Alix Axel 建议的那样））。

这将非常安全，不会发生冲突 - 例如，如果有人计算出你的哈希算法，他们还必须猜测最后的 4 位代码......

回复收藏 0 原文

寄风 2024-08-25 14:44:33

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

本书表明，如果生成 m 个值小于 n 的随机数，则生成数字并丢弃重复项的简单方法将生成不超过 2m< /code> 随机数，如果 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。

甚至还有一种基于集合的算法来生成小于 n 的 m 个随机数，每个值的可能性均等，没有重复，并且保证生成的值不会超过 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";
}

不过，数字的顺序不是随机的，因此这对您来说可能不是一个好的选择。

Programming Pearls has several examples of algorithms to generate sets of random numbers, you should read it if you're interested in this kind of problem.

The book shows that if you generate m random numbers with value less than n, the simple approach of generating numbers and throwing out duplicates will generate no more than 2m random numbers if m < n / 2. Here it is, in 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";
}

Obviously, if you're worried about people guessing values, you will want m to be much less than n / 2.

There's even a set-based algorithm to generate m random numbers less than n with each value being equally likely, no duplicates, and a guarantee not to generate more than m random numbers:

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

The order of the numbers isn't random, though, so this is probably not a good choice for you.

回复收藏 0 原文

ヤ经典坏疍 2024-08-25 14:44:33

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

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

回复收藏 0 原文

泅人 2024-08-25 14:44:33

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

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

理想情况下，最好的方法是选择足够长的序列，以便您可以安全地假设是否会有重复项。请注意，也许与直觉相反，由于生日问题。

例如，如果有 8 个字符，则有 1785793904896 种可能的组合，但如果您仅生成 1,573,415 个优惠券，则有 50% 的机会出现重复。

因此，这完全取决于您想要生成的数量以及您满意的代码的最大长度。如果您要生成很多内容并且希望保持简短，则应该保存之前生成的内容，并检查数据库是否有重复项。

回复收藏 0 原文

梦言归人 2024-08-25 14:44:33

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

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

唯一
、不可猜测

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

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

回复收藏 0 原文

述情 2024-08-25 14:44:33

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

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

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

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

回复收藏 0 原文

别理我 2024-08-25 14:44:33

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

40 位随机数部分足以满足 2^40 的机会
猜测；
40 位连续数字部分足够 34.8 年
唯一性（假设我们每毫秒生成一张礼品卡。）

然后使用 Base32。

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

Based on Jason Orendoff's answer, I put together an algorithm to generate gift card codes.
Basically, it has two 40-bit numbers: one of them to assure it is unique and another to assure it is hard to guess.

the 40-bit random number part is enough for 1 in 2^40 chances of
guessing;
the 40-bit sequential number part is enough for 34.8 years
of uniqueness (assuming we generate one gift card per ms.)

The total 80-bit sequence is then converted to a 16-character string using Base32.

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

回复收藏 0 原文

~没有更多了~