mt19937 PRNG を簡潔かつ移植性高く徹底的にシードするにはどうすればよいでしょうか? 質問する

mt19937 PRNG を簡潔かつ移植性高く徹底的にシードするにはどうすればよいでしょうか? 質問する

<random>乱数を生成するためにを使用することを提案する回答を多く見かけますが、通常は次のようなコードも一緒に表示されます。

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

通常、これは次のような「不浄な忌まわしいもの」に代わるものです。

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

私達は多分批判するtime(NULL)エントロピーが低く、time(NULL)予測可能であり、最終結果が均一ではないと主張する古い方法。

しかし、新しい方法もすべて同じで、表面がより輝いているだけである。

  • rd()単一の を返しますunsigned int。これは少なくとも 16 ビット、おそらく 32 ビットあります。これは MT の 19937 ビットの状態をシードするには不十分です。

  • (32 ビットでシードし、最初の出力を見る)を使用するとstd::mt19937 gen(rd());gen()、適切な出力分布が得られません。7 と 13 が最初の出力になることはありません。2 つのシードでは 0 が生成されます。12 個のシードでは 1226181350 が生成されます。(リンク

  • std::random_device固定シードを持つ単純な PRNG として実装されることもあります。そのため、実行するたびに同じシーケンスが生成される場合があります。(リンク) これは よりもさらに悪いですtime(NULL)

さらに悪いことに、前述のコードスニペットは、問題を抱えているにもかかわらず、コピーして貼り付けるのが非常に簡単です。これを解決するには、大きめ 図書館すべての人に適しているわけではないかもしれません。

これを踏まえて私の質問はC++ で mt19937 PRNG を簡潔かつ移植可能かつ徹底的にシードするにはどうすればよいでしょうか?

上記の問題を考慮すると、良い答えは次のようになります。

  • mt19937/mt19937_64 を完全にシードする必要があります。
  • エントロピーの源として、std::random_deviceまたはエントロピーのみに依存することはできません。time(NULL)
  • Boost や他のライブラリに依存しないでください。
  • 回答にコピー&ペーストしたときに見栄えがよくなるように、行数が少なくなるようにする必要があります。

考え

  • 私の現在の考えでは、 からの出力は とstd::random_deviceマッシュアップ(おそらくXOR経由)できtime(NULL)、 から得られた値はアドレス空間のランダム化、そしてエントロピーを最大限に高めるためのハードコードされた定数(配布中に設定可能)です。

  • std::random_device::entropy() ではないstd::random_device何ができるか、何ができないかを適切に示します。

ベストアンサー1

の最大の欠点は、std::random_deviceCSPRNG が利用できない場合に決定論的なフォールバックが許可されることだと私は主張します。これだけでも、std::random_device生成されるバイトが決定論的である可能性があるため、 を使用して PRNG をシードしない十分な理由になります。残念ながら、いつこれが発生するかを調べるための API や、低品質の乱数の代わりに失敗を要求するための API は提供されていません。

つまり、完全にポータブル解決策: ただし、適切で最小限のアプローチがあります。 CSPRNG (sysrandom以下のように定義) の最小限のラッパーを使用して、PRNG をシードできます。

ウィンドウズ


CSPRNGに依存できますCryptGenRandom。たとえば、次のコードを使用できます。

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系システムでは、/dev/urandom可能な場合は (ただし、POSIX 準拠のシステムではこれが必ず存在するとは限りません)。

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

他の


CSPRNGが利用できない場合は、 に頼ることもできますstd::random_device。しかし、さまざまなコンパイラ(特にMinGW)が として を実装しているため、可能であればこれを避けることをお勧めします。ランダム性(実際、毎回同じシーケンスを生成して、それが適切にランダムではないことを人間に警告します)。

シーディング


最小限のオーバーヘッドでピースができたので、PRNG のシードに必要なランダム エントロピー ビットを生成できます。この例では、PRNG のシードに (明らかに不十分な) 32 ビットを使用していますが、この値を増やす必要があります (CSPRNG によって異なります)。

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

Boostとの比較


boost::random_device (真のCSPRNG)と似ている点が、ざっと見ただけでわかります。ソースコード. Boost はMS_DEF_PROVWindows で を使用します。これは のプロバイダー タイプですPROV_RSA_FULL。唯一欠けているのは、 で実行できる暗号化コンテキストの検証ですCRYPT_VERIFYCONTEXT。 *Nix では、Boost は を使用します/dev/urandom。IE では、このソリューションは移植性が高く、十分にテストされており、使いやすいです。

Linux 専門分野


セキュリティのために簡潔さを犠牲にするつもりなら、getrandomは、Linux 3.17 以降、および最近の Solaris では優れた選択肢です。は、getrandomと同じように動作します/dev/urandomが、起動後にカーネルがまだ CSPRNG を初期化していない場合はブロックします。次のスニペットは、Linux がgetrandom利用可能かどうかを検出し、利用できない場合は にフォールバックします/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

オープンBSD


最後に注意点が1つあります。最近のOpenBSDには がありません/dev/urandomエントロピーその代わり。

#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

他の考え


暗号的に安全なランダム バイトが必要な場合は、fstream を POSIX のバッファなしの open/read/close に置き換える必要があります。これは、との両方basic_filebufFILE内部バッファが含まれており、標準のアロケータによって割り当てられる (したがって、メモリから消去されない) ためです。

次のように変更することで簡単に実行できますsysrandom

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

ありがとう


FILEバッファ読み取りを使用しているため、使用すべきではないことを指摘してくれた Ben Voigt に特に感謝します。

getrandomまた、 と OpenBSD の の欠如について言及してくれた Peter Cordes にも感謝したいと思います/dev/urandom

おすすめ記事