在 PHP/MySQL 中生成唯一的代码？

Question

我正在与一位客户合作，该客户需要生成数百万个用于杂志刮刮卡、瓶盖奖品等的字母数字代码。 它们必须足够短才能打印在帽子上，他们希望确保不包含 1 和 I、0 和 O 等不明确的字符，并且必须显式存储它们以供将来使用 - 我们可以”当有人试图兑换时，不只是有一种算法可以确定“有效性”。 最后，他们希望确保代码随机分布在一个大的“代码空间”内，这样人们就不能通过浏览字母表来猜测其他代码。

是否有任何指向合理有效的算法来生成此类代码集的指针？ 我在信封背面划了一些，但这个问题对于粗心的人来说就像是一个陷阱。

Answer 1

例如，如果您需要大约 1000 万个唯一密钥，最好的方法是选择一个指数级更大的密钥空间，并开始随机生成。 了解生日悖论——这是您应该担心的主要事情。 如果您需要 2^n 个唯一且安全的密钥，请确保至少有 2^(2 * n) 个可能的值。 这是一个粗略的 O(n log n) 算法：

• 使用至少 2^50 的键空间（因此，换句话说，允许 2^50 个可能的唯一值），并且整个数据集中几乎不会发生任何冲突 - - 任何暴力破解你的密钥的人，如果尝试 2^25 次，获得密钥的几率大约为偶数。
• 生成所需数量的随机数
• 在密钥上索引数据库（这是 O(n lg n) 步骤：排序）
• 分页浏览数据库并迭代整个数据集以删除重复项（下面的伪代码）
• 删除重复项行，就完成了。

伪代码：

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

Answer 2

假设您可以使用包含 40 个明确的大写、小写和数字字符的字符集。

对于 n 个字符的序列，您有 40ⁿ 种组合

• 40⁴ = 2,560,000
• 40⁵ = 102,400,000
• 40^{6 = 4,096,000,000}
• 40⁷ = 163,840,000,000
• 40⁸ = 6,553,600,000,000

因此，8 个字符提供了一个相当好的工作空间 - 如果您生成了 1000 万个代码，则必须尝试数十万种组合来暴力破解代码。

或者您从另一个方向来 - 给出可能代码的数量，您应该生成多少代码以避免他们称之为生日悖论？

采用 8 个字符的代码，6,553,600,000,000 约为 2⁴²，因此您可以合理地从中生成 2²¹ 代码，即 2,097,152

Answer 3

使用一次性密码算法？

RFC4225详细介绍了一种基于HMAC的算法。

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

但不是使用0-9位base10编码，使用base32。

Answer 4

无论您使用什么方法，我建议您添加一两个校验位，作为防止人们错误输入或试图发明数字的“第一线”防御。

Answer 5

奇怪的是，使用以下种子我只能生成 32 个唯一的字符串。

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

使用更长的种子，我能够生成更多的字符串，成功生成了 40,000 个唯一的字符串。

ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789