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 비트 상태를 시드하기에 충분하지 않습니다.

• 사용 std::mt19937 gen(rd());gen()(32 비트로 시드하고 첫 번째 출력보기)을 사용하면 좋은 출력 분포가 제공되지 않습니다. 7과 13은 첫 번째 출력이 될 수 없습니다. 두 개의 씨앗이 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 .

---

가장 큰 결함 std::random_device은 CSPRNG를 사용할 수없는 경우 결정 론적 폴 백이 허용된다는 것입니다. 이것은 std::random_device생성 된 바이트가 결정적 일 수 있으므로를 사용하여 PRNG를 시드하지 않는 좋은 이유 입니다. 안타깝게도 이것이 언제 발생하는지 알아 내거나 낮은 품질의 난수 대신 실패를 요청하는 API를 제공하지 않습니다.

즉, 완전히 이식 가능한 솔루션 은 없지만 적절한 최소한의 접근 방식이 있습니다. CSPRNG ( sysrandom아래에 정의 됨) 주위에 최소 래퍼를 사용 하여 PRNG를 시드 할 수 있습니다.

윈도우

---

CryptGenRandomCSPRNG를 사용할 수 있습니다 . 예를 들어 다음 코드를 사용할 수 있습니다.

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

유닉스 유사

---

많은 유닉스 계열 시스템에서 가능하면 / 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 비트를 사용하여 PRNG를 시드하고이 값을 늘려야합니다 (CSPRNG에 따라 다름).

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

부스트 비교

---

소스 코드를 간략히 살펴본 후 boost :: random_device (진정한 CSPRNG)에 대한 유사점을 볼 수 있습니다 . Boost는 MS_DEF_PROVWindows에서 사용 하며 PROV_RSA_FULL. 빠진 유일한 것은 암호화 컨텍스트를 확인하는 것입니다 CRYPT_VERIFYCONTEXT. * Nix에서 Boost는 /dev/urandom. IE,이 솔루션은 이식 가능하고 잘 테스트되었으며 사용하기 쉽습니다.

Linux 전문화

---

보안을 위해 간결함을 희생하려는 경우 getrandomLinux 3.17 이상 및 최신 Solaris에서 탁월한 선택입니다. 커널이 부팅 후 아직 CSPRNG를 초기화하지 않은 경우 차단된다는 점을 제외하면 getrandom과 동일하게 작동 /dev/urandom합니다. 다음 스 니펫은 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

OpenBSD

---

마지막 경고가 하나 있습니다. 최신 OpenBSD에는 /dev/urandom. 대신 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

다른 생각들

---

암호 학적으로 안전한 임의 바이트가 필요한 경우 fstream을 POSIX의 버퍼링되지 않은 열기 / 읽기 / 닫기로 대체해야합니다. 모두 있기 때문이다 basic_filebuf및 FILE표준 할당을 통해 할당 (따라서 메모리에서 닦여 생략)한다 내부 버퍼를 포함한다.

다음과 같이 변경 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에게 특별히 감사드립니다 . 따라서 사용해서는 안됩니다.

나는 또한 언급 한 Peter Cordes getrandom와 OpenBSD의 /dev/urandom.

---

In a sense, this can't be done portably. That is, one can conceive a valid fully-deterministic platform running C++ (say, a simulator which steps the machine clock deterministically, and with "determinized" I/O) in which there is no source of randomness to seed a PRNG.

---

You can use a std::seed_seq and fill it to at least the requires state size for the generator using Alexander Huszagh's method of getting the entropy:

size_t sysrandom(void* dst, size_t dstlen); //from Alexander Huszagh answer above

void foo(){

    std::uint_fast32_t[std::mt19937::state_size] state;
    sysrandom(state, sizeof(state));
    std::seed_seq s(std::begin(state), std::end(state));

    std::mt19937 g;
    g.seed(s);
}

If there was a proper way to fill or create a SeedSequence from a UniformRandomBitGenerator in the standard library using std::random_device for seeding properly would be much simpler.

---

The implementation I am working on takes advantage of the state_size property of the mt19937 PRNG to decide how many seeds to provide on initialization:

using Generator = std::mt19937;

inline
auto const& random_data()
{
    thread_local static std::array<typename Generator::result_type, Generator::state_size> data;
    thread_local static std::random_device rd;

    std::generate(std::begin(data), std::end(data), std::ref(rd));

    return data;
}

inline
Generator& random_generator()
{
    auto const& data = random_data();

    thread_local static std::seed_seq seeds(std::begin(data), std::end(data));
    thread_local static Generator gen{seeds};

    return gen;
}

template<typename Number>
Number random_number(Number from, Number to)
{
    using Distribution = typename std::conditional
    <
        std::is_integral<Number>::value,
        std::uniform_int_distribution<Number>,
        std::uniform_real_distribution<Number>
    >::type;

    thread_local static Distribution dist;

    return dist(random_generator(), typename Distribution::param_type{from, to});
}

I think there is room for improvement because std::random_device::result_type could differ from std::mt19937::result_type in size and range so that should really be taken into account.

A note about std::random_device.

According to the C++11(/14/17) standard(s):

26.5.6 Class random_device [ rand.device ]

2 If implementation limitations prevent generating non-deterministic random numbers, the implementation may employ a random number engine.

This means the implementation may only generate deterministic values if it is prevented from generating non-deterministic ones by some limitation.

The MinGW compiler on Windows famously does not provide non-deterministic values from its std::random_device, despite them being easily available from the Operating System. So I consider this a bug and not likely a common occurrence across implementations and platforms.

---

There's nothing wrong with seeding by using time, assuming you don't need it to be secure (and you didn't say this was necessary). The insight is that you can use hashing to fix the non-randomness. I've found this works adequately in all cases, including and in-particular for heavy Monte Carlo simulations.

One nice feature of this approach is that it generalizes to initialization from other not-really-random sets of seeds. For example, if you want each thread to have its own RNG (for threadsafety), you can just initialize based on hashed thread ID.

The following is a SSCCE, distilled from my codebase (for simplicity; some OO support structures elided):

#include <cstdint> //`uint32_t`
#include <functional> //`std::hash`
#include <random> //`std::mt19937`
#include <iostream> //`std::cout`

static std::mt19937 rng;

static void seed(uint32_t seed) {
    rng.seed(static_cast<std::mt19937::result_type>(seed));
}
static void seed() {
    uint32_t t = static_cast<uint32_t>( time(nullptr) );
    std::hash<uint32_t> hasher; size_t hashed=hasher(t);
    seed( static_cast<uint32_t>(hashed) );
}

int main(int /*argc*/, char* /*argv*/[]) {
    seed();
    std::uniform_int_distribution<> dis(0, 5);
    std::cout << dis(rng);
}

---

Here's my own stab at the question:

#include <random>
#include <chrono>
#include <cstdint>
#include <algorithm>
#include <functional>
#include <iostream>

uint32_t LilEntropy(){
  //Gather many potential forms of entropy and XOR them
  const  uint32_t my_seed = 1273498732; //Change during distribution
  static uint32_t i = 0;        
  static std::random_device rd; 
  const auto hrclock = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  const auto sclock  = std::chrono::system_clock::now().time_since_epoch().count();
  auto *heap         = malloc(1);
  const auto mash = my_seed + rd() + hrclock + sclock + (i++) +
    reinterpret_cast<intptr_t>(heap)    + reinterpret_cast<intptr_t>(&hrclock) +
    reinterpret_cast<intptr_t>(&i)      + reinterpret_cast<intptr_t>(&malloc)  +
    reinterpret_cast<intptr_t>(&LilEntropy);
  free(heap);
  return mash;
}

//Fully seed the mt19937 engine using as much entropy as we can get our
//hands on
void SeedGenerator(std::mt19937 &mt){
  std::uint_least32_t seed_data[std::mt19937::state_size];
  std::generate_n(seed_data, std::mt19937::state_size, std::ref(LilEntropy));
  std::seed_seq q(std::begin(seed_data), std::end(seed_data));
  mt.seed(q);
}

int main(){
  std::mt19937 mt;
  SeedGenerator(mt);

  for(int i=0;i<100;i++)
    std::cout<<mt()<<std::endl;
}

The idea here is to use XOR to combine many potential sources of entropy (fast time, slow time, std::random-device, static variable locations, heap locations, function locations, library locations, program-specific values) to make a best-effort attempt at initializing the mt19937. As long as at least once source is "good", the result will be at least that "good".

This answer is not as short as would be preferable and may contain one or more mistakes of logic. So I'm considering it a work in progress. Please comment if you have feedback.

---

A given platform might have a source of entropy, such as /dev/random. Nanoseconds since the Epoch with std::chrono::high_resolution_clock::now() is probably the best seed in the Standard Library.

I previously have used something like (uint64_t)( time(NULL)*CLOCKS_PER_SEC + clock() ) to get more bits of entropy for applications that aren’t security-critical.

참고URL : https://stackoverflow.com/questions/45069219/how-to-succinctly-portably-and-thoroughly-seed-the-mt19937-prng