Sua tarefa é improvisar um gerador de números aleatórios de hardware com o hardware que você tem.

Desafio

Escreva um programa com as seguintes propriedades:

1. Imprime um 0ou 1(e nada mais).
2. A saída depende de um processo físico e não apenas do estado interno do computador.
3. Não há relação entre as saídas das execuções subsequentes (com um minuto de diferença).
4. A saída não é previsível com nenhum esforço realista.
5. A probabilidade de a saída estar 0entre 0,2 e 0,8.
6. É executado em menos de um minuto, com uma probabilidade razoavelmente alta.

Você deve explicar por que seu programa possui essas propriedades, se não for óbvio.

Esclarecimentos e Restrições

A seguir, pode parecer uma enorme quantidade de restrições para um concurso de popularidade, mas ultimamente é tudo para garantir que o programa permaneça dentro do espírito da pergunta, funcione um pouco e para evitar soluções que são populares devido a um exagero total, mas são ultimamente entediante.

• A hora do sistema não conta como um processo físico.
• Você pode usar qualquer hardware de nível de consumidor que desejar, desde unidades de disco floopy de 8 polegadas a um lançador de foguetes USB e fones de ouvido - a menos que seja destinado à geração de números aleatórios. Uma peça de hardware é do tipo consumidor, se é produzida em massa e custa menos de 1000 $ / € / £, portanto você não pode usar radiotelescópios, CERN, MRIs ou seu detector de partículas construído em casa.
• Você só pode fazer as suposições mais básicas sobre o estado e o alinhamento do hardware, como estar ligado (se houver um interruptor de energia) e estar adequadamente instalado e funcional. Por exemplo, você pode supor que uma unidade de CD seja geralmente capaz de ler um disco e não ficar congestionada, mas não pode assumir que ela esteja aberta ou fechada ou que contenha um disco. Em outro exemplo, você não pode assumir que duas peças de hardware estejam alinhadas para permitir uma interação especial, mas você pode presumir que elas estejam na mesma sala.
• Você pode deixar o hardware no estado que desejar, a menos que o quebre.
• Você pode e deve assumir que o hardware esteja em um ambiente natural, mas nada mais. Por exemplo, você pode assumir que o hardware não está posicionado em um tanque de hélio líquido, nem em uma sala extremamente à prova de som e luz, nem no espaço. No entanto, você não pode assumir que fontes de som e luz estejam presentes, exceto aquelas que são evitáveis ​​apenas com esforços radicais.
• Seu programa deve ser executado em um computador desktop padrão com um sistema operacional não esotérico de sua escolha. Você pode empregar qualquer software que não seja projetado especificamente para geração de números aleatórios.
• Você não pode assumir acesso à Internet.
• Você não pode assumir que os humanos estejam presentes ou ausentes, mas você pode assumir que ninguém interfere intencionalmente com o seu programa, por exemplo, parando manualmente um ventilador ou executando um programa que não faz nada além de desligar o microfone o mais rápido possível.
• Você pode apenas fazer as suposições mais básicas sobre as configurações do software. Por exemplo, você pode assumir que os drivers estejam instalados e ativados, mas você deve estar preparado para que o som seja silenciado.
• Você pode deixar as configurações do software no estado que desejar.

Bônus

Uma recompensa especial foi concedida a uma solução particularmente curta. Isso foi mais pelo número de instruções e similar do que pelos caracteres. Os vencedores foram (empatados de acordo com meus critérios):

• Esta resposta por Franki.
• Esta resposta de Tejas Kale.

Eu só pude atribuir uma resposta e a resposta de Tejas Kale venceu por sorteio.

Concha

Lê uma única amostra do fluxo do microfone e imprime seu bit menos significativo, que deve ser dominado pelo ruído.

EDIT: Alterado para ativar o som do microfone ... e tudo o mais!

# Warning - unmutes EVERYTHING!
for DEV in `amixer | grep Simple | sed -e "s/.*'\(.*\)'.*/\\1/" -e "s/ /~/g"`
do
    amixer -q -- sset "`echo $DEV | sed 's/~/ /g'`" unmute 100% 2>/dev/null
done

echo $(( `od -N1 -d < /dev/dsp | head -n1 | sed 's/.* //'` & 1 ))

Bater

echo $[`ping -qc1 127.1|sed 's/[^1-9]/+/g'`0&1]

Reúne entropia a partir do tempo de resposta de um único ping para o host local.

Observe que o tempo de resposta aparece exatamente três vezes na saída de ping -qc1:

PING 127.1 (127.0.0.1) 56(84) bytes of data.

--- 127.1 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 0.044/0.044/0.044/0.000 ms

Todos os outros números são constantes e - mais importante - independentes do tempo de resposta.

sed 's/[^1-9]/+/g'converte todos os zero e não dígitos em sinais de adição e echo $[...0&1]imprime a paridade da soma resultante.

JavaScript + HTML5 DeviceMotion

var hash = function(x) {
    var h = 0
    for (var i = 0; i < x.length; i++) {
        h += x.charCodeAt(i)
        h ^= h << 5
        h ^= h >> 3
        h ^= h << 13
        h &= 0xffff
    }
    return h
}
var listener = function(e) {
    var accelerationString = JSON.stringify(e.acceleration)
    var hashed = hash(accelerationString)
    alert(hashed % 2)
    window.removeEventListener("devicemotion", listener, true)
}
window.addEventListener("devicemotion", listener, true);

JSFiddle aqui .

Usa a API DeviceMotion HTML5 em dispositivos suportados (principalmente dispositivos móveis). Transforma o accelerationobjeto resultante em JSON, faz o hash e pega o restante do módulo 2.

A maior parte do código é a função hash (maldito seja JavaScript, e sua total falta de uma biblioteca padrão). Provavelmente poderia ser mais curto, mas sou um otário por uma boa função de hash.

Python + Webcam

Usar o código roubado descaradamente a partir daqui , tira uma foto usando sua webcam, faz o hash dos dados e imprime o bit menos significativo.

#!/usr/bin/python
import pygame.camera, hashlib

pygame.camera.init()
cam = pygame.camera.Camera(pygame.camera.list_cameras()[0])
cam.start()
raw = cam.get_raw()
cam.stop()
pygame.camera.quit()

h = hashlib.sha256()
h.update(raw)
print ord(h.digest()[-1]) % 2

Perl

Verifica o tempo de resposta do seu disco rígido, cronometrando três operações:

• Lendo sua própria fonte
• Excluindo-se
• Escrevendo-se novamente

Finalmente, o tempo gasto é empacotado como um flutuador e o 11º bit mais significativo é usado (o segundo bit mais significativo da mantissa).

use Time::HiRes qw(time);

$t1 = time;
open SELF, "<$0";
read SELF, $_, $^H;
close SELF;

unlink $0;

open SELF, ">$0";
print SELF $_;
close SELF;

print 1&unpack(xB3, pack(f, time-$t1))

Bater

echo $[`sensors|sed 's/[^1-9]/+/g'`0&1]

sensors imprime as temperaturas atuais do sistema, juntamente com a velocidade do ventilador.

acpitz-virtual-0
Adapter: Virtual device
temp1:        +52.0°C  (crit = +98.0°C)

thinkpad-isa-0000
Adapter: ISA adapter
fan1:        3510 RPM

coretemp-isa-0000
Adapter: ISA adapter
Physical id 0:  +54.0°C  (high = +86.0°C, crit = +100.0°C)
Core 0:         +51.0°C  (high = +86.0°C, crit = +100.0°C)
Core 1:         +46.0°C  (high = +86.0°C, crit = +100.0°C)

sed 's/[^1-9]/+/g'converte todos os zero e não dígitos em sinais de adição e eco $[...0&1]exibe a paridade da soma resultante.

Regex e cálculo de paridade foram emprestados da resposta de dennis.

Bater

(echo -en "ibase=16;";(find /proc/[0-9]*/s* -type f -maxdepth 2 ; find /sys /proc/[^0-9]* -type f) 2>&1 | xargs -n1 sha256sum  2>&1 | sha256sum | tr abcdef ABCDEF | sed 's/  -/%2/' )| bc

Usa tudo, apenas no caso de ...

Depende de

• leituras de sensores da maioria dos sensores de hardware (quase todos expõem seus valores em algum lugar /sysou /proc)
• número, layout da memória e tempos de execução de todos os processos no sistema (que podem ser considerados "estado do sistema", mas geralmente dependem do tempo do hardware)
• dependendo do sistema, vários valores em /proc/<pid>/s*(por exemplo, sched / schedstat) dependem da velocidade do hardware necessário para dar vida a esses processos.
• coisas que talvez eu não tenha pensado também estão disponíveis nesses arquivos.

O tempo de execução no meu sistema é de ~ 10s, mas pode variar bastante. Especialmente, não execute isso como root ou, pelo menos, modifique-o para excluir /proc/kcore(a menos que você esteja disposto a gastar muito tempo para incluir a entropia contida nele, o que provavelmente incluiria tudo)

Shell + Wi-Fi

sudo airmon-ng start wlan0 > /dev/null && sudo dumpcap -a duration:30 -i mon0 -w out.cap > /dev/null && sha512sum out.cap | grep -c "^[0-7]" && sudo airmon-ng stop mon0 > /dev/null

Coloca o cartão wi-fi no modo monitor, despeja 30 segundos em pacotes recebidos (incluindo dados criptografados ilegíveis de redes vizinhas), pega o hash sha512 dos dados do pacote e retorna 1 se a primeira letra do hash for 0-7 . Supõe que seu cartão wi-fi seja wlan0e que você não possui um mon0dispositivo no momento.

Se não houver dispositivos wi-fi próximos, a saída será previsível, pois sempre será a mesma.

Os modernos processadores compatíveis com o 8086 fabricados pela Intel contêm um periférico de fácil acesso que gera aleatoriedade adequada. A condução desse periférico é feita usando a rdrandinstrução que gera um padrão de bits aleatório ou define o sinalizador de transporte se o periférico estiver indisponível ou fora da entropia.

O seguinte programa curto para o 80386 Linux verifica se o periférico está disponível por meio da cpuidinstrução e tenta gerar um número aleatório. Se o número periférico ou aleatório não estiver disponível, o programa terminará com um status de 1. Se um número aleatório puder ser gerado, a 1ou a 0é impresso e o programa termina com o status de saída 0.

Salvar como rand.se montar com

as --32 -o rand.o rand.s
ld -melf_i386 -o rand rand.o

Aqui está a montagem inteira:

        .globl _start
        .type _start,@function
_start:
        # check if the cpuid instruction is available by trying to
        # toggle the id flag in the eflags register
        pushfl
        mov (%esp),%eax
        btc $21,%eax    # toggle id bit
        push %eax
        popfl           # check if id bit was saved
        pushfl
        pop %eax        # load new flags
        pop %ecx        # load original flags
        xor %ecx,%eax   # difference is in %eax
        bt $21,%eax     # check if bit was flipped
        jnc .Lfailure

        # if we reach this part, we have a cpuid instruction
        # next, check if rdrand exists
        mov $1,%eax     # load cpuid leaf 1
        cpuid
        bt $30,%ecx     # is rdrnd available?
        jnc .Lfailure

        # let's try to get some random data
        rdrand %ax      # don't waste randomness; one bit would suffice
        jnc .Lfailure   # no randomness available
        and $1,%eax     # isolate one bit of randomness
        add $0x30,%al   # 0x30 = '0'
        push %eax
        mov $4,%eax     # prepare a write system call
        mov $1,%ebx
        mov %esp,%ecx   # where we placed the data before
        mov %ebx,%edx   # one byte
        int $0x80

        # okay, we're done here. Let's exit
        mov %ebx,%eax   # do an exit system call with status 0
        xor %ebx,%ebx
        int $0x80

.Lfailure:
        mov $1,%eax     # do an exit system call with status 1
        mov %eax,%ebx
        int $0x80

        .size _start,.-_start

E um despejo dos 77 bytes de código de máquina resultantes:

08048098 <_start>:
 8048098:   9c                      pushf  
 8048099:   8b 04 24                mov    (%esp),%eax
 804809c:   0f ba f8 15             btc    $0x15,%eax
 80480a0:   50                      push   %eax
 80480a1:   9d                      popf   
 80480a2:   9c                      pushf  
 80480a3:   58                      pop    %eax
 80480a4:   59                      pop    %ecx
 80480a5:   31 c8                   xor    %ecx,%eax
 80480a7:   0f ba e0 15             bt     $0x15,%eax
 80480ab:   73 2f                   jae    80480dc <_start+0x44>
 80480ad:   b8 01 00 00 00          mov    $0x1,%eax
 80480b2:   0f a2                   cpuid  
 80480b4:   0f ba e1 1e             bt     $0x1e,%ecx
 80480b8:   73 22                   jae    80480dc <_start+0x44>
 80480ba:   66 0f c7 f0             rdrand %ax
 80480be:   73 1c                   jae    80480dc <_start+0x44>
 80480c0:   83 e0 01                and    $0x1,%eax
 80480c3:   04 30                   add    $0x30,%al
 80480c5:   50                      push   %eax
 80480c6:   b8 04 00 00 00          mov    $0x4,%eax
 80480cb:   bb 01 00 00 00          mov    $0x1,%ebx
 80480d0:   89 e1                   mov    %esp,%ecx
 80480d2:   89 da                   mov    %ebx,%edx
 80480d4:   cd 80                   int    $0x80
 80480d6:   89 d8                   mov    %ebx,%eax
 80480d8:   31 db                   xor    %ebx,%ebx
 80480da:   cd 80                   int    $0x80
 80480dc:   b8 01 00 00 00          mov    $0x1,%eax
 80480e1:   89 c3                   mov    %eax,%ebx
 80480e3:   cd 80                   int    $0x80

bater

Visando o método de coleta de números aleatórios mais desnecessariamente caro. Tempo quanto tempo leva para gerar emacs um milhão de vezes, depois use o truque de Dennis para transformar o tempo gasto em um único booleano (leva cerca de 7 segundos na minha máquina).

$[`(time (seq 1000000 | xargs -P1000 emacs  >/dev/null 2>&1)) |& sed 's/[^1-9]/+/g'`0&1]

Arduino Mega1280

edit: versão atualizada que é robusta contra ter qualquer coisa conectada aos pinos. A idéia baseia-se no fato de que o ATMega1280 usa um oscilador interno separado para o oscilador de vigilância. Simplesmente configurei uma interrupção de watchdog que define um sinalizador, tenho um contador baseado no relógio do sistema (no Arduino, este é um cristal externo de 16MHz) e permito que o jitter / variação do relógio faça o trabalho.

#include <avr/interrupt.h>

int time;
volatile bool wdt_ran;

// watchdog interrupt handler
ISR(WDT_vect, ISR_BLOCK)
{
  wdt_ran = true;
}

void setup()  
{
  // setup watchdog interrupt
  cli();
  MCUSR &= ~(1 << WDRF);
  WDTCSR |= (1<<WDCE) | (1<<WDE);
  WDTCSR = (1<<WDIE) | (1<<WDP2) | (1<<WDP1) | (1<<WDP0);
  sei();
  // Open serial communications and wait for port to open:
  Serial.begin(57600);
}

void loop()
{
  if(wdt_ran)
  {
    Serial.println(abs(time%2));
    wdt_ran = false;
  }
  ++time;
}

Javascript

http://jsfiddle.net/prankol57/9a6s0gmv/

Toma entrada de vídeo.

Você pode ver a captura de tela usada para calcular o número aleatório.

var m = (navigator.getUserMedia || navigator.webkitGetUserMedia || navigator.mozGetUserMedia || navigator.msGetUserMedia);

var constraints = {
  video: {
    mandatory: {
      maxWidth: 350,
      maxHeight: 350
    }
  },
  audio: false
};

var video = document.querySelector("video"), canvas = document.createElement("canvas");
document.body.appendChild(canvas);
canvas.width = 350;
canvas.height = 350;

function start() {
    m.call(navigator, constraints, function (stream) {
        video.src = window.URL.createObjectURL(stream);
    }, function() {
        alert("An error occured. Did you deny permission?");
    });
}

if (m) {
    start();
} else {
    alert('getUserMedia() is not supported in your browser');
}

function getRandomData() {
    var ctx = canvas.getContext("2d");
    ctx.drawImage(video, 0, 0);
    var data = ctx.getImageData(0, 0, 350, 350).data;
    var total = 0;
    for (var i = 0; i < data.length; ++i) {
        total += data[i];
        total %= 2;
    }
    alert("The random number is " + total);
}

document.querySelector("button").onclick = getRandomData;

Shell no Linux

Meça a velocidade de leitura de um disco rígido + o tempo de acesso de um diretório atualizado com freqüência neste disco, cujo layout é imprevisível.

# Set this to the device node of whatever drive you want to measure
DRIVE_DEVICE=sda
# This must be a path that is
# a) on device "/dev/$DRIVE_PATH"
# b) frequently updated to add additional access time randomization due to
#    less-predictable disk layout due to less-predictable time, amount and
#    ordering uf updates, like logfile directories, maybe cache directories.
FIND_PATH=/var/log
# Better than using 'sync' - sync only the disk that we actually read from
# also sync both internal drive and system buffers
hdparm -f -F "/dev/$DRIVE_DEVICE"
# Note: bash's built-in time command doesn't support formats :/
# Note: the result is only going to be as good as the system's time command,
#       which isn't necessarily equally good on other U*ICes
t=$(command time -f '%e' -- find "$FIND_PATH" -printf '' 2>&1)
echo $((${t#*.}&1))

requer:

1) read and execute access to every directory under "$FIND_PATH"
2) sending (flush) control commands to a hard drive via a device node.
   Requires root access per default, but can be delegated to a less privileged user
   either by using sudo on this script or by applying
       chgrp 'some_system_group' "$DRIVE_DEVICE" &&
       chmod g+rx "$DRIVE_DEVICE"
   if this is acceptable on your system.

Essa abordagem tem a vantagem de não modificar nenhum dado no sistema e não exigir perl sobre o do primo.

Concha

Testado no Linux, mas talvez o seu U * IX também possua / proc / stat?

Isso inicia apenas um único processo adicional, lê apenas um único arquivo adicional (nem mesmo no disco) e possui 37 caracteres. Também é bem rápido.

t=1`sum /proc/stat`;echo $[${t% *}&1]

Pode-se pensar que isso é determinado por todos os estados do processo do kernel e da terra do usuário, mas esse não é o caso, já que / proc / stat também inclui tempo de espera de E / S, tempo para corrigir interrupções de hardware, tempo gasto na tarefa inativa e outros que todos depende da entrada de hardware externo.

Matlab

A solução do microfone:

recObj=audiorecorder;recordblocking(recObj,10);rem(sum(getaudiodata(recObj)<0),2)

Grava 10 segundos de som, localiza o número de amostras negativas na gravação e gera 0 se esse número for par e 1 se for ímpar. Assim 0 com 50% de probabilidade. A abordagem significa que mesmo pequenas quantidades de ruído, inevitáveis ​​em uma gravação silenciosa, serão suficientes para gerar uma saída aleatória. O código um pouco mais longo a seguir acelera o gerador de números usando uma gravação mais curta, compensada com uma taxa de bits mais alta, o que gera mais ruído.

recObj=audiorecorder(8000,16,1);recordblocking(recObj,0.1);rem(sum(getaudiodata(recObj)<0),2)

Em um teste em condições silenciosas, acho que em 100 execuções do último código, o código gera zero 51 vezes. 100 corridas em condições ruidosas produzem zero 40 vezes.

Edit: Obrigado a Emil por apontar uma falha no código original :-)

Bater

(Obrigado, Dennis.)

echo $[`w|sed 's/[^1-9]/+/g'`0&1]

Toma o bit menos significativo do acelerômetro do computador (precisa do hdapsmódulo Linux):

#!/usr/bin/env python
import re
m = re.search('([-\d]+),([-\d]+)',
              open('/sys/devices/platform/hdaps/position', 'r').read())
print((int(m.group(1)) ^ int(m.group(2))) & 1)

Isso basicamente mede o ruído do sensor.

SmileBASIC

XON MOTION 'enable motion sensor
ACCEL OUT ,,Z 'get Z acceleration (up/down)
PRINT Z<-1 'if Z is less than -1, output 1, otherwise 0.

Usa o sensor de movimento do 3DS. O eixo Z do acelerômetro geralmente é de cerca de -1 (devido à gravidade) e, devido ao ruído aleatório, às vezes pode estar acima ou abaixo dele.

Aqui está um que usa o microfone:

XON MIC 'enable microphone
DIM REC%[0] 'make array
MICSTART 0,3,1 'start recording. 0=8180Hz, 3=8 bit unsigned, 1=1 second
WAIT 1 'delay (1 frame is enough since we only check the first sample)
MICSAVE MIC 'save recording
PRINT MIC[0]>0 'if the first sample isn't negative, output 1

Bater

Peguei a sugestão de Soham (usando top):

echo $[`top -bn1|sed 's/[^1-9]/+/g'`0&1]

Edit: Funciona da mesma maneira que Soham. Ele transforma todos os caracteres não numéricos na saída de top em '+' e, em seguida, elimina a paridade da sequência resultante.

o sinalizador 'b' para cima executa-o no modo em lote, para que ele relate todos os processos, não apenas a primeira tela e 'n1' diz para executar apenas uma iteração da parte superior.