Votre tâche consiste à improviser un générateur de nombre aléatoire de matériel avec le matériel que vous possédez.

Défi

Ecrivez un programme avec les propriétés suivantes:

1. Il imprime soit 0ou 1(et rien d'autre).
2. La sortie dépend d'un processus physique et pas seulement de l'état interne de l'ordinateur.
3. Il n'y a pas de relation entre les sorties des analyses suivantes (à une minute d'intervalle).
4. La sortie n'est pas prévisible avec aucun effort réaliste.
5. La probabilité que la sortie soit 0comprise entre 0,2 et 0,8.
6. Il s'exécute en moins d'une minute avec une probabilité raisonnablement élevée.

Vous devez expliquer pourquoi votre programme possède ces propriétés, si ce n’est pas évident.

Clarifications et restrictions

Ce qui suit peut sembler énormément de restrictions pour un concours de popularité, mais en fin de compte, tout est fait pour que le programme reste dans l'esprit de la question, fonctionne un peu et pour éviter les solutions qui sont populaires parce qu'elles sont excessives mais ultimement plutôt ennuyant.

• L’heure du système ne compte pas comme un processus physique.
• Vous pouvez utiliser n'importe quel matériel grand public que vous aimez, des lecteurs de disque floopy de 8 pouces au lance- roquettes USB en passant par les écouteurs - sauf s'il est destiné à la génération de nombres aléatoires. Une pièce de matériel est de qualité grand public, si elle est produite en série et coûte moins de 1000 $ / € / £ / £, vous ne pouvez donc pas utiliser les radiotélescopes, le CERN, les IRM ou votre détecteur de particules construit à la maison.
• Vous pouvez uniquement émettre les hypothèses de base sur l'état et l'alignement du matériel, par exemple être allumé (s'il dispose d'un commutateur d'alimentation), être correctement installé et fonctionnel. Par exemple, vous pouvez supposer qu'un lecteur de CD est généralement capable de lire un disque et ne pas être bloqué, mais vous ne pouvez pas supposer qu'il est ouvert ou fermé ou qu'il contient un disque. Dans un autre exemple, vous ne pouvez pas supposer que deux composants matériels sont alignés pour permettre une interaction spéciale, mais vous pouvez également supposer qu'ils se trouvent dans la même pièce.
• Vous pouvez laisser le matériel dans l'état de votre choix, à moins que vous ne le cassiez.
• Vous pouvez et devez supposer que le matériel se trouve dans un environnement naturel, mais rien de plus. Par exemple, vous pouvez supposer que le matériel n'est pas placé dans un réservoir d'hélium liquide ni dans une pièce extrêmement insonorisée et insonorisée, ni dans un espace. Cependant, vous ne pouvez pas présumer de la présence de sources sonores ou lumineuses, à l'exception de celles qui ne peuvent être évitées qu'avec des efforts radicaux.
• Votre programme doit être exécuté sur un ordinateur de bureau standard avec un système d'exploitation non ésotérique de votre choix. Vous pouvez utiliser tout logiciel non spécialement conçu pour la génération de nombres aléatoires.
• Vous ne pouvez pas supposer un accès Internet.
• Vous ne pouvez pas supposer que les humains sont présents ni absents, mais vous pouvez supposer que personne ne gêne intentionnellement votre programme, par exemple, en arrêtant manuellement un ventilateur ou en exécutant un programme qui ne fait rien, mais éteint le microphone aussi souvent que possible.
• Vous ne pouvez faire que les hypothèses les plus élémentaires sur les paramètres du logiciel. Par exemple, vous pouvez supposer que les pilotes sont installés et activés, mais vous devez être prêt pour que le son soit mis en sourdine.
• Vous pouvez laisser les paramètres du logiciel dans l'état de votre choix.

Prime

Une prime spéciale a été attribuée à une solution particulièrement courte. C'était plutôt par nombre d'instructions et similaire que par caractères. Les gagnants étaient (à égalité selon mes critères):

• Cette réponse de Franki.
• Cette réponse de Tejas Kale.

Je n'ai pu attribuer qu'une seule réponse et celle de Tejas Kale a été tirée au sort.

coquille

Lit un seul échantillon du flux de microphone et imprime son bit le moins significatif, qui devrait être dominé par le bruit.

EDIT: Modifié pour réactiver le microphone ... et tout le reste aussi!

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

Frapper

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

Recueille l'entropie du temps de réponse d'un seul ping à localhost.

Notez que le temps de réponse apparaît exactement trois fois dans la sortie 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

Tous les autres chiffres et constants et - plus important encore - indépendants du temps de réponse.

sed 's/[^1-9]/+/g'convertit chaque zéro et chaque chiffre non numérique en signes plus et echo $[...0&1]imprime la parité de la somme résultante.

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

Utilise l'API HTML5 DeviceMotion sur les appareils pris en charge (principalement les appareils mobiles). Il transforme l' accelerationobjet résultant en JSON, le hache et prend le reste modulo 2.

La majeure partie du code est la fonction de hachage (putain de JavaScript, et de votre absence totale d'une bibliothèque standard). Il pourrait probablement être plus court, mais je suis une ventouse pour une bonne fonction de hachage.

Python + Webcam

Utiliser du code volé sans vergogne à partir d’ ici , prend un cliché en utilisant votre webcam, hache les données et affiche le bit le moins significatif.

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

Vérifie le temps de réponse de votre disque dur en chronométrant trois opérations:

• Lire sa propre source
• Se supprimer
• Se réécrire

Enfin, le temps pris est stocké sous forme de float et le 11ème bit le plus significatif est utilisé (le second bit le plus significatif de la mantisse).

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

Frapper

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

sensors imprime les températures actuelles du système ainsi que la vitesse du ventilateur.

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'convertit chaque zéro et chaque chiffre non numérique en signes plus et echo $[...0&1]imprime la parité de la somme résultante.

Calcul de la regex et de la parité emprunté à la réponse de dennis.

Frapper

(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

Utilise tout, juste au cas où ...

Dépend de

• les lectures des capteurs de la plupart des capteurs matériels (à peu près toutes exposent leurs valeurs quelque part /sysou /proc)
• nombre, disposition de la mémoire et durée d'exécution de tous les processus du système (qui peuvent être considérés comme "l'état du système" mais dépendent généralement eux-mêmes du minutage du matériel)
• En fonction du système, différentes valeurs /proc/<pid>/s*(par exemple, sched / schedstat) dépendent de la vitesse du matériel nécessaire pour mettre ces processus en activité.
• des éléments auxquels je n'aurais peut-être pas pensé sont également disponibles dans ces fichiers.

Le temps d’exécution sur mon système est d'environ 10 secondes, mais peut varier considérablement. Surtout, ne lancez pas cela en tant que root, ou du moins modifiez-le pour l'exclure /proc/kcore(à moins que vous ne souhaitiez passer beaucoup de temps à inclure l'entropie qui y est contenue, ce qui inclurait probablement vraiment tout)

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

Met la carte wi-fi en mode moniteur, affiche 30 secondes de paquets reçus (y compris des données cryptées illisibles provenant de réseaux voisins), prend le hachage sha512 des données du paquet et renvoie 1 si la première lettre du hachage est 0-7 . Suppose que votre carte Wi-Fi est wlan0, et que vous n'avez pas d' mon0appareil.

S'il n'y a pas d'appareils Wi-Fi à proximité, la sortie sera prévisible, car elle sera la même à chaque fois.

Les processeurs modernes compatibles Intel 8086 fabriqués par Intel contiennent un périphérique facilement accessible générant un caractère aléatoire adéquat. Le pilotage de ce périphérique s'effectue à l'aide de l' rdrandinstruction qui génère un modèle de bits aléatoire ou active l'indicateur de retenue si le périphérique est indisponible ou ne présente pas d'entropie.

Le programme court suivant pour 80386 Linux vérifie si le périphérique est disponible au moyen de l’ cpuidinstruction et essaie de générer un nombre aléatoire. Si le périphérique ou un nombre aléatoire n'est pas disponible, le programme se termine avec le statut 1. Si un nombre aléatoire peut être généré, un 1ou un0 est imprimé et le programme se termine avec le statut de sortie 0.

Enregistrer sous rand.set assembler avec

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

Voici l'assemblage complet:

        .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

Et une sauvegarde des 77 octets de code machine obtenus:

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

frapper

Viser la méthode la plus inutile de collecte de nombres aléatoires. Indiquez combien de temps il faut pour générer emacs un million de fois, puis utilisez l’astuce de Dennis pour transformer le temps pris en un simple booléen (prend environ 7 secondes sur ma machine).

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

Arduino Mega1280

edit: version mise à jour qui est robuste contre tout ce qui est branché sur les broches. L'idée repose sur le fait que l'ATMega1280 utilise un oscillateur interne séparé pour l'oscillateur de surveillance. Je configure simplement une interruption de chien de garde qui définit un drapeau, un compteur basé sur l'horloge système (sur l'Arduino, il s'agit d'un cristal externe de 16 MHz) et permet à la gigue et à la variance de faire le travail.

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

Prend une entrée vidéo.

Vous pouvez voir la capture d'écran utilisée pour calculer le nombre aléatoire.

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 sur Linux

Mesurer la vitesse de lecture d'un disque dur + le temps d'accès d'un répertoire fréquemment mis à jour sur ce disque, dont la disposition est imprévisible.

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

a besoin:

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.

Cette approche a l'avantage de ne modifier aucune donnée sur le système et de ne pas nécessiter de perl par rapport à celui de primo.

coquille

Testé sur Linux, mais peut-être que votre U * IX a également / proc / stat?

Cela ne démarre qu’un seul processus supplémentaire, lit un seul fichier supplémentaire (même sur disque) et contient 37 caractères. C'est aussi assez rapide.

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

On peut penser que ceci est déterminé par tous les états de processus du noyau et de l’utilisateur, mais ce n’est pas le cas, car / proc / stat inclut dépendent de l'entrée matérielle externe.

Matlab

La solution de microphone:

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

Enregistre 10 secondes de son, recherche le nombre d'échantillons négatifs dans l'enregistrement et génère 0 si ce nombre est pair et 1 s'il est impair. Donc 0 avec une probabilité de 50%. Cette approche signifie que même de petites quantités de bruit, inévitables dans un enregistrement silencieux, seront suffisantes pour générer une sortie aléatoire. Le code légèrement plus long suivant accélère le générateur de numéros en utilisant un enregistrement plus court, compensé par un débit binaire plus élevé, ce qui génère plus de bruit.

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

Dans un test dans des conditions calmes, je trouve que sur 100 exécutions du dernier code, le code affiche zéro 51 fois. 100 courses dans des conditions bruyantes ont été produites zéro à 40 fois.

Edit: Merci à Emil pour avoir signalé une faille dans le code original :-)

Frapper

(Merci, Dennis.)

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

Prend le bit le moins significatif de l'accéléromètre de l'ordinateur (nécessite le hdapsmodule 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)

Cela mesure essentiellement le bruit du capteur.

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.

Utilise le capteur de mouvement de la 3DS. L'axe Z de l'accéléromètre se situe généralement autour de -1 (en raison de la gravité) et, en raison du bruit aléatoire, il peut parfois être supérieur ou inférieur à celui-ci.

En voici un qui utilise le microphone:

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

Frapper

J'ai pris la suggestion de Soham (en utilisant top):

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

Edit: Cela fonctionne de la même manière que Soham. Il transforme tous les caractères non numériques de la sortie de top en '+', puis évite la parité de la chaîne résultante.

l'indicateur 'b' en haut le lance en mode batch de manière à signaler tous les processus, pas seulement le premier écran et 'n1' indique d'exécuter une seule itération de top.