随机令牌生成 - 发生了据称不太可能的冲突

Question

几个月前，我们使用UUID来生成随机字符串ID，这些ID需要全面唯一。然后，我更改了算法，以便在我们的数据库中保存一些数据和索引空间。我测试了几种生成唯一字符串 ID 的方法，并决定使用此函数：

function generateToken($length) {
$characters = '0123456789abcdefghijklmnopqrstuvwxyz';
$max = strlen($characters) - 1;
$token = '';
for ($i = 0; $i < $length; $i++) {
$token .= $characters[mt_rand(0, $max)];
}
return $token;
}

我正在使用这个函数使用数字和字母生成 20 个字符长的 ID，或者你可以说这些 ID 是以 36 为基数的数字。任何 2 个 ID 碰撞的概率应该是 1/36^20，但由于生日悖论，可以预期在大约 36^10 条记录之后会发生碰撞 - 即 3.6 万亿条记录。然而，就在几个小时前，发生了冲突，当时数据库中只有530万条现有记录。是我非常倒霉，还是我的ID生成功能在随机性方面存在缺陷？我知道mt_rand((不是真正的随机，但它足够随机，不是吗？

我会编写一个循环来检查生成的 ID 是否唯一，如果不是，则会生成一个新 ID，但我认为发生冲突的可能性很小，以至于这种循环的性能成本不值得。我现在将在代码中包含这样的循环，但如果它确实有缺陷，我仍然对完善 ID 生成函数感兴趣。

Answer 1

PHP 中mt_rand()的实现相当流畅，因此它可能因版本而异。但是，以下是 PHP 版本 5 中使用的代码的一些摘录：

php_rand.h：

/* MT Rand */
#define PHP_MT_RAND_MAX ((long) (0x7FFFFFFF)) /* (1<<31) - 1 */ 
#ifdef PHP_WIN32
#define GENERATE_SEED() (((long) (sapi_get_request_time(TSRMLS_C) * GetCurrentProcessId())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))
#else
#define GENERATE_SEED() (((long) (sapi_get_request_time(TSRMLS_C) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))
#endif
PHPAPI void php_srand(long seed TSRMLS_DC);
PHPAPI long php_rand(TSRMLS_D);
PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC);
PHPAPI php_uint32 php_mt_rand(TSRMLS_D);

兰德：

PHP_FUNCTION(mt_rand)
{
long min;
long max;
long number;
int  argc = ZEND_NUM_ARGS();
if (argc != 0) {
if (zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE) {
return;
} else if (max < min) {
php_error_docref(NULL TSRMLS_CC, E_WARNING, "max(%ld) is smaller than min(%ld)", max, min);
RETURN_FALSE;
}
}
if (!BG(mt_rand_is_seeded)) {
php_mt_srand(GENERATE_SEED() TSRMLS_CC);
}

从上面的最后三行中，您可以看到mt_rand()在第一次调用时会自动设定种子。但是，php_mt_srand()函数采用类型php_uint32的参数。这意味着只有 2³²个可能的种子状态可用于mt_rand()。因此，如果您的脚本运行大约 2^{到 16}次，则mt_rand()很可能会产生完全相同的随机数序列。

正如Rossum所建议的那样，将AES加密应用于递增的128位值会是一个更好的主意。如果对加密结果进行 base64 编码并丢弃尾随==，则生成的字符串长度将只有 22 个字符。

---

补遗

今天下午外出时，我让以下脚本运行：

for i in $(seq 1 100000) ; do
php -r 'for ($n=0; $n<32; $n++) echo chr(mt_rand(97,122)); echo chr(10);' >>out
done &

正如预期的那样，第一次碰撞发生在大约 2 16 次迭代之后(远不及 26¹⁶(：

$ sort <out | uniq -d
vnexqclzkaluntglgadgwzjnjfsvqfhp
$ grep -n vnexqclzkaluntglgadgwzjnjfsvqfhp out
34417:vnexqclzkaluntglgadgwzjnjfsvqfhp
52159:vnexqclzkaluntglgadgwzjnjfsvqfhp

Answer 2

如果你想要保证唯一的 16 字节 ID，那么我会使用加密。 AES 使用 16 字节(128 位(块，只要输入是唯一的，输出也保证唯一。

在 ECB 模式下设置 AES(更简单、更快捷(并加密数字 0、1、2、3、4、...您的输入是唯一的，因此输出也将是唯一的。

加密网站会告诉您 ECB 模式存在安全问题，但这些问题仅在输入不唯一时才适用。 对于唯一的"随机"数生成，正如您所要求的那样，这些问题不适用，因为您的输入都是唯一的。