Como semear de forma sucinta, portátil e completa o PRNG mt19937?

Parece que vejo muitas respostas em que alguém sugere o uso <random>para gerar números aleatórios, geralmente junto com códigos como este:

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

Normalmente, isso substitui algum tipo de "abominação profana", como:

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

Podemos criticar a maneira antiga argumentando que time(NULL)fornece baixa entropia, time(NULL)é previsível e o resultado final não é uniforme.

Mas tudo isso é verdade no novo jeito: ele apenas tem um verniz mais brilhante.

• rd()retorna um único unsigned int. Isso tem pelo menos 16 bits e provavelmente 32. Isso não é suficiente para propagar os 19937 bits de estado do MT.

• Usando std::mt19937 gen(rd());gen()(semeando com 32 bits e olhando para a primeira saída) não dá uma boa distribuição de saída. 7 e 13 nunca podem ser a primeira saída. Duas sementes produzem 0. Doze sementes produzem 1226181350. ( Link )

• std::random_devicepode ser, e às vezes é, implementado como um PRNG simples com uma semente fixa. Portanto, pode produzir a mesma sequência em cada execução. ( Link ) Isso é ainda pior do que time(NULL).

Pior ainda, é muito fácil copiar e colar os trechos de código anteriores, apesar dos problemas que eles contêm. Algumas soluções para isso requerem a aquisição de bibliotecas maiores que podem não ser adequadas para todos.

Diante disso, minha pergunta é: Como alguém pode semear de forma sucinta, portátil e completa o PRNG mt19937 em C ++?

Dadas as questões acima, uma boa resposta:

• Deve semear totalmente o mt19937 / mt19937_64.
• Não pode contar apenas com std::random_deviceou time(NULL)como fonte de entropia.
• Não deve contar com Boost ou outras bibliotecas.
• Deve caber em um pequeno número de linhas, de forma que fique bem copiado e colado em uma resposta.

Pensamentos

• Meu pensamento atual é que as saídas de std::random_devicepodem ser combinadas (talvez via XOR) com time(NULL)valores derivados da randomização do espaço de endereço e uma constante codificada (que pode ser definida durante a distribuição) para obter uma melhor chance de entropia.

• std::random_device::entropy() não dá uma boa indicação do que std::random_devicepode ou não fazer.

Eu argumentaria que a maior falha com std::random_deviceé que é permitido um fallback determinístico se nenhum CSPRNG estiver disponível. Isso por si só é uma boa razão para não propagar um PRNG usando std::random_device, uma vez que os bytes produzidos podem ser determinísticos. Infelizmente, não fornece uma API para descobrir quando isso acontece ou para solicitar falha em vez de números aleatórios de baixa qualidade.

Ou seja, não existe uma solução totalmente portátil : no entanto, existe uma abordagem decente e mínima. Você pode usar um envoltório mínimo em torno de um CSPRNG (definido como sysrandomabaixo) para propagar o PRNG.

janelas

Você pode confiar em CryptGenRandomum CSPRNG. Por exemplo, você pode usar o seguinte código:

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-like

Em muitos sistemas semelhantes ao Unix, você deve usar / dev / urandom quando possível (embora não seja garantido que exista em sistemas compatíveis com 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;
}

De outros

Se nenhum CSPRNG estiver disponível, você pode optar por confiar em std::random_device. No entanto, eu evitaria isso se possível, uma vez que vários compiladores (mais notavelmente, MinGW) o implementam como um PRNG (na verdade, produzindo a mesma sequência todas as vezes para alertar os humanos de que não é propriamente aleatório).

Semeando

Agora que temos nossas peças com overhead mínimo, podemos gerar os bits desejados de entropia aleatória para semear nosso PRNG. O exemplo usa 32 bits (obviamente insuficientes) para propagar o PRNG e você deve aumentar esse valor (que depende do seu CSPRNG).

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

Comparação para Boost

Podemos ver paralelos com boost :: random_device (um verdadeiro CSPRNG) após uma rápida olhada no código-fonte . O Boost usa MS_DEF_PROVno Windows, que é o tipo de provedor para PROV_RSA_FULL. Falta apenas verificar o contexto criptográfico, o que pode ser feito com CRYPT_VERIFYCONTEXT. Em * Nix, Boost usa /dev/urandom. Ou seja, esta solução é portátil, bem testada e fácil de usar.

Especialização Linux

Se você está disposto a sacrificar a sucinta pela segurança, getrandomé uma excelente escolha no Linux 3.17 e superior e no Solaris recente. getrandomse comporta de forma idêntica /dev/urandom, exceto que bloqueia se o kernel ainda não inicializou seu CSPRNG após a inicialização. O snippet a seguir detecta se o Linux getrandomestá disponível e, caso não esteja, retorna ao /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

Há uma advertência final: o OpenBSD moderno não tem /dev/urandom. Você deve usar getentropy em vez disso.

#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

outros pensamentos

Se você precisa de bytes aleatórios criptograficamente seguros, você provavelmente deve substituir o fstream pelo open / read / close sem buffer do POSIX. Isso ocorre porque basic_filebufe FILEcontém um buffer interno, que será alocado por meio de um alocador padrão (e, portanto, não apagado da memória).

Isso pode ser feito facilmente mudando sysrandompara:

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

obrigado

Agradecimentos especiais a Ben Voigt por apontar o FILEuso de leituras em buffer e, portanto, não deve ser usado.

Eu também gostaria de agradecer a Peter Cordes por mencionar getrandom, e a falta do OpenBSD /dev/urandom.

Em certo sentido, isso não pode ser feito de forma portátil. Ou seja, pode-se conceber uma plataforma totalmente determinística válida rodando C ++ (digamos, um simulador que acelera o relógio da máquina deterministicamente, e com E / S "determinada") na qual não há fonte de aleatoriedade para semear um PRNG.

Você pode usar um std::seed_seqe preenchê-lo até pelo menos o tamanho de estado necessário para o gerador usando o método de Alexander Huszagh para obter a entropia:

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

Se houvesse uma maneira adequada de preencher ou criar um SeedSequence a partir de um UniformRandomBitGenerator na biblioteca padrão, o uso std::random_devicepara propagação correta seria muito mais simples.

A implementação na qual estou trabalhando aproveita a state_sizepropriedade do mt19937PRNG para decidir quantas sementes fornecer na inicialização:

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

Eu acho que há espaço para melhorias porque std::random_device::result_typepodem ser diferentes std::mt19937::result_typeem tamanho e alcance, então isso realmente deve ser levado em consideração.

Uma nota sobre std :: random_device .

De acordo com o C++11(/14/17)(s) padrão (ões):

26.5.6 Classe random_device [ rand.device ]

2 Se as limitações de implementação impedirem a geração de números aleatórios não determinísticos, a implementação pode empregar um mecanismo de número aleatório.

Isso significa que a implementação só pode gerar valores determinísticos se for impedida de gerar valores não determinísticos por alguma limitação.

O MinGWcompilador Windowsnotoriamente não fornece valores não determinísticos de seu std::random_device, apesar de estarem facilmente disponíveis no sistema operacional. Portanto, considero isso um bug e provavelmente não uma ocorrência comum em implementações e plataformas.

Não há nada de errado em semear usando o tempo, supondo que você não precise dele para ser seguro (e você não disse que isso era necessário). A ideia é que você pode usar o hash para corrigir a não aleatoriedade. Descobri que isso funciona adequadamente em todos os casos, incluindo e em particular para simulações pesadas de Monte Carlo.

Um bom recurso dessa abordagem é que ela generaliza para a inicialização a partir de outros conjuntos de sementes não realmente aleatórios. Por exemplo, se você deseja que cada thread tenha seu próprio RNG (para threadsafety), você pode apenas inicializar com base no ID do thread em hash.

O seguinte é um SSCCE , destilado da minha base de código (para simplificar; algumas estruturas de suporte OO eliminadas):

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

Aqui está minha própria tentativa de resolver a questão:

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

A ideia aqui é usar XOR para combinar muitas fontes potenciais de entropia (tempo rápido, tempo lento, std::random-devicelocais de variáveis ​​estáticas, locais de heap, locais de função, locais de biblioteca, valores específicos do programa) para fazer um melhor esforço na tentativa de inicializar o mt19937. Contanto que pelo menos uma vez a fonte seja "boa", o resultado será pelo menos "bom".

Essa resposta não é tão curta quanto seria preferível e pode conter um ou mais erros de lógica. Portanto, estou considerando um trabalho em andamento. Por favor, comente se você tiver feedback.

• Use getentropy () para propagar um gerador de números pseudo-aleatórios (PRNG).
• Use getrandom () se quiser valores aleatórios (em vez de, digamos, /dev/urandomou /dev/random).

Eles estão disponíveis em sistemas modernos do tipo UNIX, como Linux, Solaris e OpenBSD.

Uma determinada plataforma pode ter uma fonte de entropia, como /dev/random. Nanossegundos desde a época com std::chrono::high_resolution_clock::now()é provavelmente a melhor semente na Biblioteca Padrão.

Eu já usei algo como (uint64_t)( time(NULL)*CLOCKS_PER_SEC + clock() )obter mais bits de entropia para aplicativos que não são críticos para a segurança.