問(wèn)題描述

我似乎看到很多答案中有人建議使用 來(lái)生成隨機(jī)數(shù)，通常還有這樣的代碼:

I seem to see many answers in which someone suggests using <random> to generate random numbers, usually along with code like this:

std::random_device rd;  
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 5);
dis(gen);

通常這會(huì)取代某種邪惡的可憎"，例如:

Usually this replaces some kind of "unholy abomination" such as:

srand(time(NULL));
rand()%6;

我們可能會(huì)批評(píng)舊方法，認(rèn)為time(NULL) 提供低熵，time(NULL) 是可預(yù)測(cè)的，最終結(jié)果是非均勻的.

We might criticize the old way by arguing that time(NULL) provides low entropy, time(NULL) is predictable, and the end result is non-uniform.

但所有這些都適用于新方式:它只是具有更閃亮的飾面.

But all of that is true of the new way: it just has a shinier veneer.

• rd() 返回單個(gè) unsigned int.這至少有 16 位，可能有 32 位.這不足以為 MT 的 19937 位狀態(tài)播種.

• rd() returns a single unsigned int. This has at least 16 bits and probably 32. That's not enough to seed MT's 19937 bits of state.

使用 std::mt19937 gen(rd());gen()(用 32 位播種并查看第一個(gè)輸出)不能提供良好的輸出分布.7 和 13 永遠(yuǎn)不能是第一個(gè)輸出.兩顆種子產(chǎn)生 0.十二顆種子產(chǎn)生 1226181350.(鏈接)

Using std::mt19937 gen(rd());gen() (seeding with 32 bits and looking at the first output) doesn't give a good output distribution. 7 and 13 can never be the first output. Two seeds produce 0. Twelve seeds produce 1226181350. (Link)

std::random_device 可以，有時(shí)是，作為一個(gè)帶有固定種子的簡(jiǎn)單 PRNG 來(lái)實(shí)現(xiàn).因此，它可能會(huì)在每次運(yùn)行時(shí)產(chǎn)生相同的序列.(鏈接) 這比time(NULL)還要糟糕.

std::random_device can be, and sometimes is, implemented as a simple PRNG with a fixed seed. It might therefore produce the same sequence on every run. (Link) This is even worse than time(NULL).

更糟糕的是，復(fù)制和粘貼上述代碼片段非常容易，盡管它們存在問(wèn)題.對(duì)此的一些解決方案需要獲取較大 庫(kù)，可能并不適合所有人.

Worse yet, it is very easy to copy and paste the foregoing code snippets, despite the problems they contain. Some solutions to the this require acquiring largish libraries which may not be suitable to everyone.

有鑒于此，我的問(wèn)題是如何在 C++ 中簡(jiǎn)潔、可移植和徹底地植入 mt19937 PRNG?

鑒于上述問(wèn)題，一個(gè)很好的答案:

Given the issues above, a good answer:

• 必須完全播種 mt19937/mt19937_64.
• 不能僅僅依賴 std::random_device 或 time(NULL) 作為熵的來(lái)源.
• 不應(yīng)依賴 Boost 或其他庫(kù).
• 應(yīng)該適合少量的行，以便復(fù)制粘貼到答案中看起來(lái)不錯(cuò).

• Must fully seed the mt19937/mt19937_64.
• Cannot rely solely on std::random_device or time(NULL) as a source of entropy.
• Should not rely on Boost or other libaries.
• Should fit in a small number of lines such that it would look nice copy-pasted into an answer.

想法

• 我目前的想法是 std::random_device 的輸出可以與 time(NULL) 混合(可能通過(guò) XOR)，值來(lái)自 地址空間隨機(jī)化，以及一個(gè)硬編碼常量(可以在分發(fā)過(guò)程中設(shè)置)以獲得最佳效果- 對(duì)熵的努力.

• My current thought is that outputs from std::random_device can be mashed up (perhaps via XOR) with time(NULL), values derived from address space randomization, and a hard-coded constant (which could be set during distribution) to get a best-effort shot at entropy.

std::random_device::entropy() 沒(méi)有很好地說(shuō)明std::random_device可能會(huì)或不會(huì)做什么.

std::random_device::entropy() does not give a good indication of what std::random_device might or might not do.

推薦答案

我認(rèn)為 std::random_device 的最大缺陷是，如果沒(méi)有可用的 CSPRNG，它允許確定性回退.僅此一項(xiàng)就是不使用 std::random_device 播種 PRNG 的一個(gè)很好的理由，因?yàn)楫a(chǎn)生的字節(jié)可能是確定性的.不幸的是，它沒(méi)有提供 API 來(lái)確定何時(shí)發(fā)生這種情況，或者請(qǐng)求失敗而不是低質(zhì)量的隨機(jī)數(shù).

I would argue the greatest flaw with std::random_device is the that it is allowed a deterministic fallback if no CSPRNG is available. This alone is a good reason not to seed a PRNG using std::random_device, since the bytes produced may be deterministic. It unfortunately doesn't provide an API to find out when this happens, or to request failure instead of low-quality random numbers.

也就是說(shuō)，沒(méi)有完全便攜的解決方案:但是，有一種體面的、最小的方法.您可以使用 CSPRNG 周圍的最小包裝器(在下面定義為 sysrandom)來(lái)為 PRNG 設(shè)定種子.

That is, there is no completely portable solution: however, there is a decent, minimal approach. You can use a minimal wrapper around a CSPRNG (defined as sysrandom below) to seed the PRNG.

您可以依賴 CryptGenRandom，一個(gè) CSPRNG.例如，您可以使用以下代碼:

You can rely on CryptGenRandom, a CSPRNG. For example, you may use the following code:

bool acquire_context(HCRYPTPROV *ctx)
{
    if (!CryptAcquireContext(ctx, nullptr, nullptr, PROV_RSA_FULL, 0)) {
        return CryptAcquireContext(ctx, nullptr, nullptr, PROV_RSA_FULL, CRYPT_NEWKEYSET);
    }
    return true;
}


size_t sysrandom(void* dst, size_t dstlen)
{
    HCRYPTPROV ctx;
    if (!acquire_context(&ctx)) {
        throw std::runtime_error("Unable to initialize Win32 crypt library.");
    }

    BYTE* buffer = reinterpret_cast<BYTE*>(dst);
    if(!CryptGenRandom(ctx, dstlen, buffer)) {
        throw std::runtime_error("Unable to generate random bytes.");
    }

    if (!CryptReleaseContext(ctx, 0)) {
        throw std::runtime_error("Unable to release Win32 crypt library.");
    }

    return dstlen;
}

類Unix

在許多類 Unix 系統(tǒng)上，您應(yīng)該使用 /dev/urandom可能(盡管不保證在符合 POSIX 的系統(tǒng)上存在).

Unix-Like

On many Unix-like systems, you should use /dev/urandom when possible (although this is not guaranteed to exist on POSIX-compliant systems).

size_t sysrandom(void* dst, size_t dstlen)
{
    char* buffer = reinterpret_cast<char*>(dst);
    std::ifstream stream("/dev/urandom", std::ios_base::binary | std::ios_base::in);
    stream.read(buffer, dstlen);

    return dstlen;
}

其他

如果沒(méi)有可用的 CSPRNG，您可以選擇依賴 std::random_device.但是，如果可能的話，我會(huì)避免這種情況，因?yàn)楦鞣N編譯器(最著名的是 MinGW)將其作為 PRNG(實(shí)際上，每次生成相同的序列以提醒人們它不是正確隨機(jī)的).

Other

If no CSPRNG is available, you might choose to rely on std::random_device. However, I would avoid this if possible, since various compilers (most notably, MinGW) implement it with as a PRNG (in fact, producing the same sequence every time to alert humans that it's not properly random).

現(xiàn)在我們的片段開(kāi)銷最小，我們可以生成所需的隨機(jī)熵位來(lái)為我們的 PRNG 做種子.該示例使用(顯然不夠)32 位作為 PRNG 的種子，您應(yīng)該增加此值(這取決于您的 CSPRNG).

Now that we have our pieces with minimal overhead, we can generate the desired bits of random entropy to seed our PRNG. The example uses (an obviously insufficient) 32-bits to seed the PRNG, and you should increase this value (which is dependent on your CSPRNG).

std::uint_least32_t seed;    
sysrandom(&seed, sizeof(seed));
std::mt19937 gen(seed);

對(duì)比提升

快速瀏覽源代碼.Boost 在 Windows 上使用 MS_DEF_PROV，這是 PROV_RSA_FULL 的提供程序類型.唯一缺少的是驗(yàn)證加密上下文，這可以通過(guò) CRYPT_VERIFYCONTEXT 完成.在 *Nix 上，Boost 使用 /dev/urandom.IE，此解決方案可移植、經(jīng)過(guò)充分測(cè)試且易于使用.

Comparison To Boost

We can see parallels to boost::random_device (a true CSPRNG) after a quick look at the source code. Boost uses MS_DEF_PROV on Windows, which is the provider type for PROV_RSA_FULL. The only thing missing would be verifying the cryptographic context, which can be done with CRYPT_VERIFYCONTEXT. On *Nix, Boost uses /dev/urandom. IE, this solution is portable, well-tested, and easy-to-use.

如果你愿意為了安全而犧牲簡(jiǎn)潔性，getrandom 是 Linux 3.17 及更高版本以及最近的 Solaris 上的絕佳選擇.getrandom 的行為與 /dev/urandom 相同，除了它在啟動(dòng)后內(nèi)核尚未初始化其 CSPRNG 時(shí)會(huì)阻塞.以下代碼段檢測(cè) Linux getrandom 是否可用，如果不可用，則回退到 /dev/urandom.

If you're willing to sacrifice succinctness for security, getrandom is an excellent choice on Linux 3.17 and above, and on recent Solaris. getrandom behaves identically to /dev/urandom, except it blocks if the kernel hasn't initialized its CSPRNG yet after booting. The following snippet detects if Linux getrandom is available, and if not falls back to /dev/urandom.

#if defined(__linux__) || defined(linux) || defined(__linux)
#   // Check the kernel version. `getrandom` is only Linux 3.17 and above.
#   include <linux/version.h>
#   if LINUX_VERSION_CODE >= KERNEL_VERSION(3,17,0)
#       define HAVE_GETRANDOM
#   endif
#endif

// also requires glibc 2.25 for the libc wrapper
#if defined(HAVE_GETRANDOM)
#   include <sys/syscall.h>
#   include <linux/random.h>

size_t sysrandom(void* dst, size_t dstlen)
{
    int bytes = syscall(SYS_getrandom, dst, dstlen, 0);
    if (bytes != dstlen) {
        throw std::runtime_error("Unable to read N bytes from CSPRNG.");
    }

    return dstlen;
}

#elif defined(_WIN32)

// Windows sysrandom here.

#else

// POSIX sysrandom here.

#endif

OpenBSD

最后一個(gè)警告:現(xiàn)代 OpenBSD 沒(méi)有 /dev/urandom.您應(yīng)該改用 getentropy.

#if defined(__OpenBSD__)
#   define HAVE_GETENTROPY
#endif

#if defined(HAVE_GETENTROPY)
#   include <unistd.h>

size_t sysrandom(void* dst, size_t dstlen)
{
    int bytes = getentropy(dst, dstlen);
    if (bytes != dstlen) {
        throw std::runtime_error("Unable to read N bytes from CSPRNG.");
    }

    return dstlen;
}

#endif

其他想法

如果您需要加密安全的隨機(jī)字節(jié)，您可能應(yīng)該將 fstream 替換為 POSIX 的無(wú)緩沖打開(kāi)/讀取/關(guān)閉.這是因?yàn)?basic_filebuf 和 FILE 都包含一個(gè)內(nèi)部緩沖區(qū)，它將通過(guò)標(biāo)準(zhǔn)分配器分配(因此不會(huì)從內(nèi)存中擦除).

Other Thoughts

If you need cryptographically secure random bytes, you should probably replace the fstream with POSIX's unbuffered open/read/close. This is because both basic_filebuf and FILE contain an internal buffer, which will be allocated via a standard allocator (and therefore not wiped from memory).

這可以很容易地通過(guò)將 sysrandom 更改為:

This could easily be done by changing sysrandom to:

size_t sysrandom(void* dst, size_t dstlen)
{
    int fd = open("/dev/urandom", O_RDONLY);
    if (fd == -1) {
        throw std::runtime_error("Unable to open /dev/urandom.");
    }
    if (read(fd, dst, dstlen) != dstlen) {
        close(fd);
        throw std::runtime_error("Unable to read N bytes from CSPRNG.");
    }

    close(fd);
    return dstlen;
}

謝謝

特別感謝 Ben Voigt 指出 FILE 使用緩沖讀取，因此不應(yīng)使用.

Thanks

Special thanks to Ben Voigt for pointing out FILE uses buffered reads, and therefore should not be used.

我還要感謝 Peter Cordes 提到 getrandom，以及 OpenBSD 缺少 /dev/urandom.

I would also like to thank Peter Cordes for mentioning getrandom, and OpenBSD's lack of /dev/urandom.

這篇關(guān)于如何簡(jiǎn)潔、便攜、徹底地播種 mt19937 PRNG?的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！