Bagaimana cara menyemai mt19937 PRNG secara ringkas, portabel, dan menyeluruh?

Sepertinya saya melihat banyak jawaban di mana seseorang menyarankan penggunaan <random>untuk menghasilkan angka acak, biasanya bersama dengan kode seperti ini:

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

Biasanya ini menggantikan beberapa jenis "kekejian yang tidak suci" seperti:

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

Kita mungkin mengkritik cara lama dengan alasan yang time(NULL)memberikan entropi rendah, time(NULL)dapat diprediksi, dan hasil akhirnya tidak seragam.

Tapi semua itu benar dengan cara baru: hanya memiliki lapisan yang lebih berkilau.

• rd() mengembalikan satu unsigned int . Ini memiliki setidaknya 16 bit dan mungkin 32. Itu tidak cukup untuk menyemai kondisi 19937 bit MT.

• Menggunakan std::mt19937 gen(rd());gen()(seeding dengan 32 bit dan melihat keluaran pertama) tidak memberikan distribusi keluaran yang baik. 7 dan 13 tidak pernah bisa menjadi keluaran pertama. Dua biji menghasilkan 0. Dua belas biji menghasilkan 1226181350. ( Link )

• std::random_devicedapat, dan terkadang, diimplementasikan sebagai PRNG sederhana dengan benih tetap. Oleh karena itu, mungkin menghasilkan urutan yang sama di setiap proses. ( Link ) Ini bahkan lebih buruk dari time(NULL).

Lebih buruk lagi, sangat mudah untuk menyalin dan menempelkan potongan kode sebelumnya, terlepas dari masalah yang dikandungnya. Beberapa solusi untuk ini memerlukan memperoleh largish perpustakaan yang mungkin tidak cocok untuk semua orang.

Sehubungan dengan hal ini, pertanyaan saya adalah Bagaimana cara menyemai mt19937 PRNG secara ringkas, portabel, dan menyeluruh dalam C ++?

Mengingat masalah di atas, jawaban yang bagus:

• Harus sepenuhnya menyemai mt19937 / mt19937_64.
• Tidak bisa hanya mengandalkan std::random_deviceatautime(NULL) sebagai sumber entropi.
• Sebaiknya tidak mengandalkan Boost atau libaries lainnya.
• Harus muat dalam sejumlah kecil baris sehingga akan terlihat bagus saat disalin ke dalam jawaban.

Pikiran

• Pemikiran saya saat ini adalah bahwa keluaran dari std::random_devicedapat dihaluskan (mungkin melalui XOR) dengan time(NULL), nilai yang berasal dari pengacakan ruang alamat , dan konstanta hard-code (yang dapat diatur selama distribusi) untuk mendapatkan bidikan upaya terbaik di entropi.

• std::random_device::entropy() tidak memberikan indikasi yang baik tentang apa yang std::random_devicemungkin dilakukan atau tidak dilakukan.

Saya berpendapat bahwa kekurangan terbesar std::random_deviceadalah bahwa ia diizinkan untuk melakukan fallback deterministik jika tidak ada CSPRNG yang tersedia. Ini saja merupakan alasan yang baik untuk tidak menggunakan PRNGstd::random_device , karena byte yang dihasilkan mungkin bersifat deterministik. Sayangnya tidak menyediakan API untuk mencari tahu kapan ini terjadi, atau untuk meminta kegagalan alih-alih nomor acak berkualitas rendah.

Artinya, tidak ada solusi yang sepenuhnya portabel : namun, ada pendekatan minimal yang layak. Anda dapat menggunakan pembungkus minimal di sekitar CSPRNG (didefinisikan seperti di sysrandombawah) untuk menyemai PRNG.

Windows

Anda dapat mengandalkan CryptGenRandom, CSPRNG. Misalnya, Anda dapat menggunakan kode berikut:

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

Seperti Unix

Pada banyak sistem mirip Unix, Anda harus menggunakan / dev / urandom bila memungkinkan (walaupun ini tidak dijamin ada pada sistem yang mendukung 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;
}

Lain

Jika CSPRNG tidak tersedia, Anda mungkin memilih untuk mengandalkan std::random_device. Namun, saya akan menghindari ini jika memungkinkan, karena berbagai kompiler (terutama, MinGW) mengimplementasikannya dengan sebagai PRNG (sebenarnya, menghasilkan urutan yang sama setiap saat untuk mengingatkan manusia bahwa itu tidak acak dengan benar).

Penyemaian

Sekarang setelah kami memiliki bagian kami dengan overhead minimal, kami dapat menghasilkan bit entropi acak yang diinginkan untuk menyemai PRNG kami. Contoh ini menggunakan (jelas tidak cukup) 32-bit untuk menyemai PRNG, dan Anda harus meningkatkan nilai ini (yang bergantung pada CSPRNG Anda).

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

Perbandingan Untuk Meningkatkan

Kita dapat melihat paralel untuk meningkatkan :: random_device (CSPRNG yang sebenarnya) setelah melihat sekilas kode sumber . Boost digunakan MS_DEF_PROVdi Windows, yang merupakan jenis penyedia PROV_RSA_FULL. Satu-satunya hal yang hilang adalah memverifikasi konteks kriptografi, yang dapat dilakukan dengan CRYPT_VERIFYCONTEXT. Di * Nix, Boost menggunakan /dev/urandom. IE, solusi ini portabel, teruji dengan baik, dan mudah digunakan.

Spesialisasi Linux

Jika Anda bersedia mengorbankan kesederhanaan demi keamanan, getrandomini adalah pilihan yang sangat baik di Linux 3.17 ke atas, dan di Solaris terbaru. getrandomberperilaku identik dengan /dev/urandom, kecuali itu memblokir jika kernel belum menginisialisasi CSPRNG-nya setelah booting. Cuplikan berikut mendeteksi apakah Linux getrandomtersedia, dan jika tidak kembali ke /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

Ada satu peringatan terakhir: OpenBSD modern tidak memilikinya /dev/urandom. Anda harus menggunakan getentropy sebagai gantinya.

#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

Pikiran Lainnya

Jika Anda memerlukan byte acak yang aman secara kriptografik, Anda mungkin harus mengganti fstream dengan open / read / close POSIX yang tidak disangga. Ini karena keduanya basic_filebufdan FILEberisi buffer internal, yang akan dialokasikan melalui pengalokasi standar (dan karenanya tidak dihapus dari memori).

Ini dapat dengan mudah dilakukan dengan mengubah sysrandom ke:

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

Terima kasih

Terima kasih khusus kepada Ben Voigt karena telah menunjukkannya FILE penggunaan pembacaan buffer, dan oleh karena itu sebaiknya tidak digunakan.

Saya juga ingin berterima kasih kepada Peter Cordes karena menyebutkan getrandom, dan kekurangan OpenBSD /dev/urandom.

Dalam arti tertentu, ini tidak bisa dilakukan secara portabel. Artinya, seseorang dapat membayangkan platform deterministik penuh yang valid yang menjalankan C ++ (katakanlah, simulator yang mengukur jam mesin secara deterministik, dan dengan I / O yang "ditentukan") di mana tidak ada sumber keacakan untuk menyemai PRNG.

Anda dapat menggunakan std::seed_seqdan mengisinya hingga setidaknya ukuran status yang dibutuhkan untuk generator menggunakan metode Alexander Huszagh untuk mendapatkan entropi:

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

void foo(){

    std::array<std::mt19937::UIntType, std::mt19937::state_size> state;
    sysrandom(state.begin(), state.length*sizeof(std::mt19937::UIntType));
    std::seed_seq s(state.begin(), state.end());

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

Jika ada cara yang tepat untuk mengisi atau membuat file SeedSequence dari UniformRandomBitGenerator di perpustakaan standar, menggunakan std::random_deviceseeding dengan benar akan jauh lebih sederhana.

Implementasi yang saya kerjakan memanfaatkan state_sizeproperti mt19937PRNG untuk memutuskan berapa banyak benih yang akan disediakan saat inisialisasi:

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

Saya pikir ada ruang untuk perbaikan karena std::random_device::result_typebisa berbeda daristd::mt19937::result_type dalam ukuran dan jangkauan sehingga harus benar-benar diperhitungkan.

Catatan tentang std :: random_device .

Menurut C++11(/14/17)standar:

26.5.6 Kelas random_device [ rand.device ]

2 Jika batasan implementasi mencegah pembuatan bilangan acak non-deterministik, implementasi dapat menggunakan mesin bilangan acak.

Ini berarti implementasi hanya dapat menghasilkan nilai deterministik jika dicegah untuk menghasilkan nilai non-deterministik dengan beberapa batasan.

The MinGWcompiler pada Windowsterkenal tidak memberikan non-deterministik nilai dari yang std::random_device, meskipun mereka menjadi mudah tersedia dari Sistem Operasi. Jadi saya menganggap ini bug dan sepertinya bukan kejadian umum di seluruh implementasi dan platform.

Tidak ada yang salah dengan penyemaian dengan menggunakan waktu, dengan asumsi Anda tidak membutuhkannya agar aman (dan Anda tidak mengatakan ini perlu). Wawasannya adalah Anda dapat menggunakan hashing untuk memperbaiki non-keacakan. Saya telah menemukan ini berfungsi secara memadai dalam semua kasus, termasuk dan khususnya untuk simulasi Monte Carlo yang berat.

Salah satu fitur bagus dari pendekatan ini adalah ia menggeneralisasi inisialisasi dari kumpulan benih lain yang tidak benar-benar acak. Misalnya, jika Anda ingin setiap utas memiliki RNG sendiri (untuk keamanan utas), Anda dapat menginisialisasi berdasarkan ID utas berciri.

Berikut ini adalah SSCCE , disaring dari basis kode saya (untuk kesederhanaan; beberapa struktur pendukung OO dihilangkan):

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

Inilah tusukan saya sendiri pada pertanyaan itu:

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

Idenya di sini adalah menggunakan XOR untuk menggabungkan banyak sumber entropi potensial (waktu cepat, waktu lambat, std::random-device lokasi variabel statis, lokasi heap, lokasi fungsi, lokasi perpustakaan, nilai khusus program) untuk melakukan upaya terbaik dalam menginisialisasi mt19937. Selama setidaknya satu sumber "baik", hasilnya setidaknya akan "baik".

Jawaban ini tidak sesingkat yang diharapkan dan mungkin mengandung satu atau lebih kesalahan logika. Jadi saya menganggapnya sedang dalam proses. Tolong beri komentar jika Anda memiliki umpan balik.

• Gunakan getentropy () untuk melakukan seed generator nomor pseudorandom (PRNG).
• Gunakan getrandom () jika Anda menginginkan nilai acak (bukan, katakanlah, /dev/urandomatau /dev/random).

Ini tersedia pada sistem modern mirip UNIX, seperti Linux, Solaris, dan OpenBSD.

Platform tertentu mungkin memiliki sumber entropi, seperti /dev/random. Nano sejak Epoch dengan std::chrono::high_resolution_clock::now()mungkin adalah benih terbaik di Perpustakaan Standar.

Saya sebelumnya telah menggunakan sesuatu seperti (uint64_t)( time(NULL)*CLOCKS_PER_SEC + clock() )untuk mendapatkan lebih banyak bit entropi untuk aplikasi yang tidak penting bagi keamanan.