2

几个月前，我们使用 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 生成功能感兴趣。

4

2 回答 2

3

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

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

加密网站会告诉您 ECB 模式存在安全问题，但这些问题仅适用于输入不唯一的情况。对于您需要的唯一“随机”数字生成，这些问题不适用，因为您的输入都是唯一的。

于 2018-06-09T10:45:51.167 回答
3

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

rand.c：

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()函数采用 type 的参数php_uint32。这意味着只有 2 32 个可能的种子状态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 16）：

$ sort <out | uniq -d
vnexqclzkaluntglgadgwzjnjfsvqfhp

$ grep -n vnexqclzkaluntglgadgwzjnjfsvqfhp out
34417:vnexqclzkaluntglgadgwzjnjfsvqfhp
52159:vnexqclzkaluntglgadgwzjnjfsvqfhp
于 2018-06-09T13:09:55.240 回答