在 PHP/MySQL 中生成唯一的代码?
-
03-07-2019 - |
题
我正在与一位客户合作,该客户需要生成数百万个用于杂志刮刮卡、瓶盖奖品等的字母数字代码。他们必须足够短才能打印在帽子上,他们希望确保 1 和 I、0 和 O 等不明确的字符能够被打印出来。不包括在内,并且必须明确存储它们以供将来使用 - 我们不能仅仅拥有一种算法来确定当有人尝试兑换时的“有效性”。最后,他们希望确保代码随机分布在一个大的“代码空间”内,这样人们就不能通过浏览字母表来猜测其他代码。
是否有任何指向合理有效的算法来生成此类代码集的指针?我在信封背面划了一些,但这个问题对于粗心的人来说就像是一个陷阱。
解决方案
例如,如果您需要大约 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;
}
其他提示
假设您可以使用包含 40 个明确的大写、小写和数字字符的字符集。
对于 n 个字符的序列,您有 40 个n 组合
- 404 = 2,560,000
- 405 = 102,400,000
- 406 = 4,096,000,000
- 407 = 163,840,000,000
- 408 = 6,553,600,000,000
因此,8 个字符提供了相当好的工作空间 - 如果您生成 1000 万个代码,则必须尝试数十万种组合才能暴力破解代码。
或者你从另一个方向来 - 给出数量 可能的 代码,有多少个代码 应该 你生成以避免他们称之为陷阱的 生日悖论?
采用 8 个字符的代码,6,553,600,000,000 约为 242, ,因此你可以合理地生成 221 来自它的代码,或 2,097,152
使用一次性密码算法?
RFC4225详细介绍了一种基于HMAC算法的方法。
http://www.ietf.org/rfc/rfc4226.txt
但不是使用0-9位base10编码,而是使用base32。
无论您使用何种方法,我建议您添加一个或两个校验位作为“第一行”。防止人们误入歧途或试图发明数字。
奇怪的是,使用下面的种子,我只能生成32个唯一的字符串。
ABCDEFGHJKLMNPQRSTUVWXYZ23456789
使用更长的种子,我能够生成更多 - 成功生成40,000个唯一字符串。
ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789ABCDEFGHJKLMNPQRSTUVWXYZ234567892345678923456789