代码之家 › 专栏 › 技术社区 › Eaton

在PHP/MySQL中生成唯一代码?

serial-number generator random mysql php

14

Eaton · 技术社区 · 17 年前

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

是否有任何指向生成这类代码集的合理高效算法的指针?我在信封背面抓了几个,但这个问题闻起来像是给粗心的人设的陷阱。

5 回复 | 直到 17 年前

1

13

ojrac 17 年前

如果你需要大约1000万个唯一密钥(例如),最好的方法是选择一个指数级更大的密钥空间,并开始随机生成。阅读 Birthday Paradox --这是你最应该担心的事情。如果你想要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;
}

2

7

Paul Dixon 14 年前

假设你可以使用一个字符集,比如40个明确的上、下和数字字符。

对于n个字符的序列,您有40个字符 ⁿ 结合

40 ^4. = 2,560,000
40 ^5. = 102,400,000
40 ^6. = 4,096,000,000
40 ^7. = 163,840,000,000
40 ^8. = 6,553,600,000,000

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

或者你从另一个方向过来——给出 可能的 代码,有多少个代码本应您生成以避免他们称之为的陷阱 Birthday Paradox ?

取8个字符的代码,65536000000000大约是2 ⁴² ,因此您可以合理地生成2 ²¹ 代码,或2097152

3

0

Ren Ren 17 年前

使用一次性密码算法?

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

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

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

4

0

staticsan 17 年前

无论你使用哪种方法,我建议你添加一两个校验位作为“一线”防御,防止人们误输入或试图发明一个数字。

5

-3

kalinma 16 年前

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

ABCDEFGHJKLMNPQRSTUVWXYZ23456789

有了更长的种子,我能够生成更多的种子——成功生成了40000个独特的字符串。

abcdefghjklmnpqrstuvxyz2345678923456789abcdefgjklmnpnqrstuvoxyz234567892345678923456789abcdevjklmnpkrstuvxyz 234567892234567892