Twoim zadaniem jest zaimprowizowanie sprzętowego generatora liczb losowych z dowolnym sprzętem.

Wyzwanie

Napisz program o następujących właściwościach:

1. Drukuje albo 0albo 1(i nic więcej).
2. Wynik zależy od procesu fizycznego, a nie tylko od wewnętrznego stanu komputera.
3. Nie ma związku między wynikami kolejnych przebiegów (w odstępie jednej minuty).
4. Wynik nie jest przewidywalny przy żadnym realistycznym wysiłku.
5. Prawdopodobieństwo wyjścia 0wynosi od 0,2 do 0,8.
6. Działa w mniej niż minutę z dość dużym prawdopodobieństwem.

Musisz wyjaśnić, dlaczego twój program ma te właściwości, jeśli nie jest to oczywiste.

Wyjaśnienia i ograniczenia

Poniższe może się wydawać okropnym ograniczeniem dla konkursu popularności, ale ostatecznie chodzi o to, aby zapewnić, że program pozostanie w duchu pytania, w pewnym sensie zadziała i aby uniknąć rozwiązań, które są popularne ze względu na całkowitą przesadę, ale ostatecznie raczej nudny.

• Czas systemowy nie jest liczony jako proces fizyczny.
• Możesz używać dowolnego sprzętu konsumenckiego, takiego jak 8-calowe napędy dyskietek, wyrzutnię rakiet USB i słuchawki - chyba że jest on przeznaczony do generowania liczb losowych. Sprzęt jest klasy konsumenckiej, jeśli jest produkowany seryjnie i kosztuje mniej niż 1000 $ / € / £, więc nie można używać radioteleskopów, CERN, MRI ani domowego detektora cząstek.
• Możesz jedynie przyjąć najbardziej podstawowe założenia dotyczące stanu i wyrównania sprzętu, takie jak włączenie (jeśli ma przełącznik zasilania) oraz prawidłowe zainstalowanie i funkcjonowanie. Na przykład można założyć, że napęd CD jest ogólnie zdolny do odczytu dysku i nie może zostać zablokowany, ale nie można zakładać, że jest otwarty, zamknięty lub zawiera dysk. W innym przykładzie nie można założyć, że dwa elementy sprzętu zostaną wyrównane, aby umożliwić specjalną interakcję, ale można założyć, że znajdują się one w tym samym pomieszczeniu.
• Możesz pozostawić sprzęt w dowolnym stanie, chyba że go zepsujesz.
• Możesz i musisz założyć, że sprzęt jest w środowisku naturalnym, ale nic więcej. Na przykład można założyć, że sprzęt nie jest umieszczony w zbiorniku ciekłego helu ani w wyjątkowo dźwiękoszczelnym i światłotrwałym pomieszczeniu, ani w przestrzeni. Nie można jednak zakładać obecności żadnych źródeł dźwięku i światła, z wyjątkiem tych, których można uniknąć jedynie przy radykalnym wysiłku.
• Twój program musi działać na standardowym komputerze stacjonarnym z wybranym przez użytkownika nieezoterycznym systemem operacyjnym. Możesz użyć dowolnego oprogramowania, które nie zostało specjalnie zaprojektowane do generowania liczb losowych.
• Nie możesz założyć dostępu do Internetu.
• Nie możesz zakładać, że ludzie są obecni lub nieobecni, ale możesz założyć, że nikt celowo nie ingeruje w twój program, np. Ręcznie zatrzymując wentylator lub uruchamiając program, który wyłącza mikrofon tak często, jak to możliwe.
• Możesz jedynie przyjąć najbardziej podstawowe założenia dotyczące ustawień oprogramowania. Na przykład możesz założyć, że sterowniki zostaną zainstalowane i aktywowane, ale musisz być przygotowany na wyciszenie dźwięku.
• Możesz pozostawić ustawienia oprogramowania w dowolnym stanie.

Premia

Specjalną nagrodę przyznano szczególnie krótkiemu rozwiązaniu. Było to raczej według liczby instrukcji i podobnych niż według znaków. Zwycięzcami zostali (remis zgodnie z moimi kryteriami):

• Ta odpowiedź Franki.
• Ta odpowiedź Tejas Kale.

Mogłem przyznać tylko jedną odpowiedź, a odpowiedź Tejasa Kale'a wygrana przez los.

Muszla

Odczytuje pojedynczą próbkę ze strumienia mikrofonu i drukuje jej najmniej znaczący bit, który powinien być zdominowany przez szum.

EDYCJA: Zmieniono, aby wyciszyć mikrofon ... i wszystko inne też!

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

Grzmotnąć

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

Zbiera entropię od czasu odpowiedzi pojedynczego polecenia ping do hosta lokalnego.

Zauważ, że czas odpowiedzi pojawia się dokładnie trzy razy na wyjściu 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

Wszystkie pozostałe liczby oraz stały i - co ważniejsze - niezależny od czasu odpowiedzi.

sed 's/[^1-9]/+/g'konwertuje każde zero i cyfrę na znaki plus i echo $[...0&1]drukuje parzystość wynikowej sumy.

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 tutaj .

Używa HTML5 DeviceMotion API na obsługiwanych urządzeniach (głównie urządzeniach mobilnych). Zamienia wynikowy accelerationobiekt w JSON, haszy go i przejmuje resztę modulo 2.

Większość kodu to funkcja skrótu (cholera, JavaScript i całkowity brak standardowej biblioteki). Prawdopodobnie może być krótszy, ale jestem frajerem dobrej funkcji skrótu.

Python + kamera internetowa

Używając bezwstydnie skradzionego kodu z tego miejsca , wykonuj migawkę za pomocą kamery internetowej, mieszając dane i drukując najmniej znaczący bit.

#!/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

Sprawdza czas reakcji dysku twardego, mierząc trzy operacje:

• Czytanie własnego źródła
• Usuwam się
• Piszę ponownie

Na koniec czas jest pakowany jako liczba zmiennoprzecinkowa i używany jest 11. najbardziej znaczący bit (drugi najbardziej znaczący bit mantysy).

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

Grzmotnąć

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

sensors drukuje bieżące temperatury systemu wraz z prędkością wentylatora.

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'konwertuje każde zero i cyfrę na znaki plus, a echo $[...0&1]drukuje parzystość wynikowej sumy.

Regex i obliczanie parzystości zapożyczone z odpowiedzi Dennisa.

Grzmotnąć

(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

Używa wszystkiego, na wszelki wypadek ...

Zależy od

• odczyty czujników większości czujników sprzętowych (prawie wszystkie ujawniają swoje wartości gdzieś w /syslub /proc)
• liczba, układ pamięci i środowiska uruchomieniowe wszystkich procesów w systemie (które można uznać za „stan systemu”, ale zwykle same zależą od taktowania sprzętu)
• w zależności od systemu różne wartości /proc/<pid>/s*(np. harmonogram / harmonogram) zależą od szybkości sprzętu niezbędnego do ożywienia tych procesów.
• rzeczy, o których mogłem nie myśleć, są również dostępne w tych plikach.

Czas działania w moim systemie wynosi około 10 sekund, ale może się znacznie różnić. Zwłaszcza nie uruchamiaj tego jako root, ani przynajmniej nie modyfikuj go, aby wykluczyć /proc/kcore(chyba że jesteś gotów poświęcić dużo czasu na dołączenie zawartej w nim entropii, która prawdopodobnie naprawdę zawiera wszystko)

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

Przełącza kartę Wi-Fi w tryb monitorowania, zrzuca pakiety o wartości 30 sekund (w tym nieczytelne zaszyfrowane dane z sąsiednich sieci), pobiera skrót sha512 danych pakietu i zwraca 1, jeśli pierwsza litera skrótu ma wartość 0–7 . Zakłada, że ​​twoja karta Wi-Fi jest wlan0, i że obecnie nie masz mon0urządzenia.

Jeśli w pobliżu nie ma urządzeń Wi-Fi, wyjście będzie przewidywalne, ponieważ za każdym razem będzie takie samo.

Nowoczesne procesory zgodne z 8086 produkowane przez Intel zawierają łatwo dostępne urządzenia peryferyjne, które generują odpowiednią losowość. Sterowanie tym urządzeniem peryferyjnym odbywa się za pomocą rdrandinstrukcji, która albo generuje losowy wzorzec bitów, albo ustawia flagę przenoszenia, jeśli urządzenie peryferyjne jest niedostępne lub nie ma entropii.

Poniższy krótki program dla systemu Linux 80386 sprawdza, czy urządzenie peryferyjne jest dostępne za pomocą cpuidinstrukcji i próbuje wygenerować losową liczbę. Jeśli numer peryferyjny lub losowy nie jest dostępny, program zakończy działanie ze statusem 1. Jeśli można wygenerować losowy numer, albo 1czy 0jest drukowany i program kończy działanie z kodem wyjścia 0.

Zapisz jako rand.si zmontuj z

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

Oto cały zestaw:

        .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

I zrzut wynikowego 77 bajtów kodu maszynowego:

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

grzmotnąć

Celowanie w najbardziej niepotrzebnie kosztowną metodę zbierania liczb losowych. Czas, jaki zajmuje odrodzenie emacsa milion razy, a następnie użyj sztuczki Dennisa, aby zmienić czas na pojedynczy logiczny (zajmuje to około 7 sekund na mojej maszynie).

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

Arduino Mega1280

edit: zaktualizowana wersja, która jest odporna na cokolwiek podłączonego do pinów. Pomysł opiera się na fakcie, że ATMega1280 wykorzystuje oddzielny wewnętrzny oscylator dla oscylatora watchdog. Po prostu konfiguruję przerwanie watchdoga, które ustawia flagę, mam licznik oparty na zegarze systemowym (na Arduino jest to zewnętrzny kryształ 16 MHz) i pozwalam na jitter / wariancję zegara.

#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/

Pobiera wejście wideo.

Możesz zobaczyć zrzut ekranu użyty do obliczenia liczby losowej.

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 w systemie Linux

Zmierz prędkość odczytu dysku twardego + czas dostępu do często aktualizowanego katalogu na tym dysku, którego układ jest nieprzewidywalny.

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

wymaga:

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.

Podejście to ma tę zaletę, że nie modyfikuje żadnych danych w systemie i nie wymaga perla w stosunku do danych primo.

Muszla

Testowany na Linuksie, ale może twój U * IX ma również / proc / stat?

To uruchamia tylko jeden dodatkowy proces, odczytuje tylko jeden dodatkowy plik (nawet na dysku) i ma 37 znaków. Jest również dość szybki.

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

Może się wydawać, że determinują to wszystkie stany procesu jądra i przestrzeni użytkownika, ale tak nie jest, ponieważ / proc / stat obejmuje także czas oczekiwania na IO, czas na przerwanie sprzętowe, czas spędzony na bezczynnym zadaniu i inne, które wszystkie zależą od zewnętrznego wejścia sprzętowego.

Matlab

Rozwiązanie mikrofonowe:

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

Nagrywa 10 sekund dźwięku, znajduje liczbę próbek ujemnych w nagraniu i wyprowadza 0, jeśli liczba ta jest parzysta, i 1, jeśli jest nieparzysta. Zatem 0 z 50% prawdopodobieństwem. Podejście to oznacza, że ​​nawet niewielkie ilości hałasu, nieuniknione w cichym nagraniu, wystarczą do wygenerowania losowego wyniku. Poniższy nieco dłuższy kod przyspiesza generator liczb dzięki zastosowaniu krótszego nagrania, skompensowanego wyższą przepływnością, co daje większy szum.

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

W teście w cichych warunkach stwierdzam, że w 100 seriach tego ostatniego kodu kod wyprowadza zero 51 razy. 100 przebiegów w hałaśliwych warunkach wygenerowało zero 40 razy.

Edycja: Podziękowania dla Emila za wskazanie błędu w oryginalnym kodzie :-)

Grzmotnąć

(Dzięki, Dennis.)

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

Pobiera najmniej znaczący akcelerometr komputera (wymaga hdapsmodułu 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)

To w zasadzie mierzy hałas czujnika.

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.

Wykorzystuje czujnik ruchu 3DS. Oś Z akcelerometru wynosi zwykle około -1 (z powodu grawitacji), a ze względu na przypadkowy hałas może czasami znajdować się powyżej lub poniżej.

Oto taki, który używa mikrofonu:

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

Grzmotnąć

Wziąłem własną sugestię Soham (używając top):

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

Edycja: Działa tak samo jak Soham. Zamienia wszystkie znaki nienumeryczne na wyjściu top na „+”, a następnie ewaluuje parzystość wynikowego łańcucha.

flaga „b” na górze uruchamia ją w trybie wsadowym, dzięki czemu zgłasza wszystkie procesy, a nie tylko pierwszy przegląd, a „n1” mówi, aby po prostu uruchomić 1 iterację na górze.