Faire Online-Verlosungen

Wie lässt sich der Gewinner in einer Onlineverlosung gerecht und transparent ermitteln? Fair bedeutet, dass alle Teilnehmer die gleiche Chance haben, transparent, dass die Ziehung reproduzierbar, also nachvollziehbar abläuft, ohne dass die physische Präsenz der Teilnehmer erforderlich ist.

Bei Online-Verlosungen ist es gängige Praxis, dass sich alle Teilnehmer einfach in eine Liste eintragen. Wenn diese Liste zum Beispiel 2304 Einträge hat, muss man lediglich eine zufällige Ganzzahl zwischen 1 und 2304 erzeugen, um den Gewinner zu ermitteln.

Freie Quellen für Zufallsdaten

Die Webseite www.random.org stellt echte Zufallsdaten, die aus atmosphärischem Rauschen gewonnen werden, zur Verfügung. Rechts oben auf der Startseite von random.org kann man sich jederzeit eine Zufallszahl in einem bestimmten Wertebereich generieren lassen. So lässt sich eine faire Ziehung realisieren. Allerdings ist die Auswahl für die Teilnehmer nicht transparent, weil jeder Besucher der Seite eine neue Zufallszahl bekommt.

Zum Glück bietet random.org aber auch vorab generierte Zufallsdateien für jeden Tag an. Die Regeln der Verlosung könnten dann beispielsweise so gestaltet werden, dass der Gewinner aus dem Inhalt der Zufallsdatei für den Tag, der auf den Einsendeschluss folgt, ermittelt wird. Leider hat random.org den Zugriff auf die Zufallsdateien im Moment wegen übermäßiger Downloads eingestellt.

Glücklicherweise gibt es aber eine weitere Quelle für echte Zufallsdaten, die ebenfalls aus atmosphärischem Rauschen gewonnen werden, nämlich die Tweets von Donald J. Trump. Dafür müssen die Regeln nur geringfügig angepasst werden: Anstatt aus den Zufallsdaten von random.org wird der Gewinner aus dem Inhalt des ersten Tweets von Trump am Tag nach dem Einsendeschluss ermittelt.

Erzeugen einer Zufallszahl aus zufälligem Text

Für unser Beispiel müssen wir Mister Trumps Twitter Account @realDonaldTrump besuchen. Im Moment ist sein letzter Tweet "SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!" (Weißes Haus! Die Tastatur des Präsidenten PRELLT ...)

Damit besitzen wir nun einen Zufallstext. Dieser kann in eine Zufallszahl gewandelt werden, indem eine Prüfsumme - auch Message Digest genannt - über den Text gebildet wird. Das geht zum Beispiel mit dem Kommandozeilen-Tool openssl:

$ echo 'SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!' \
    | openssl sha -whirlpool
(stdin)= 821e5d159ac7a472bb18daafe758a573dae21fcd1458ac1b85f4af0b1715b4b530c39fe36dcbdd4820f0ea8dc25cb8e6fdc2b9946ba238b99d31b0defd8f2d66

Der Whirlpool-Algorithmus ist einer der Message-Digest-Algorithmen, die von openssl unterstützt werden (openssl sha -h listet weitere Algorithmen auf). Ich nehme hier Whirlpool, weil ein Whirlpool auch beim Bierbrauen Anwendung findet. Bei der Verlosung, die diesen Beitrag inspiriert hat, ging es um einen schicken Braukessel.

Die Ausgabe von openssl ist (stdin)= GROSSE-HEX-ZAHL. Das (stdin)= ist im Weg und muss noch mit sed weggefiltert werden:

$ echo 'SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!' \
    | openssl sha -whirlpool \
    | sed -e 's/.*= //'
821e5d159ac7a472bb18daafe758a573dae21fcd1458ac1b85f4af0b1715b4b530c39fe36dcbdd4820f0ea8dc25cb8e6fdc2b9946ba238b99d31b0defd8f2d66

Damit bleibt nur noch die Hexadezimalzahl übrig. Später werden wir den Kommandozeilenrechner bc, der mit Zahlen fast beliebiger Größe umgehen kann, für die Mathematik verwenden, und bc verlangt, dass für Hexziffern Großbuchstaben verwendet werden. Das erreichen wir mit tr:

$ echo 'SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!' \
    | openssl sha -whirlpool \
    | sed -e 's/.*= //' \
    | tr '[:lower:]' '[:upper:]'
821E5D159AC7A472BB18DAAFE758A573DAE21FCD1458AC1B85F4AF0B1715B4B530C39FE36DCBDD4820F0EA8DC25CB8E6FDC2B9946BA238B99D31B0DEFD8F2D66

Wir haben jetzt also eine sehr große Zahl in Hexadezimalschreibweise aus dem Eingabetext generiert, und weil wir einen kryptographisch sicheren Algorithmus verwenden, können wir nach dem heutigen Stand der Kryptographie und Zahlentheorie davon ausgehen, dass sich diese Zahl vollständig, und in nicht vorhersehbarer Weise ändert, wenn auch nur ein Bit in der Eingabe wechselt.

Wir brauchen noch eine Teilnehmerliste mit zufälligen Namen:

1. Erika Mustermann
2. Max Mustermann
3. Dornröschen
4. Froschkönig
5. Rumpelstilzchen

Einen zufälligen Eintrag aus der Liste auszuwählen ist einfach, wenn wir eine hinreichend große Zufallszahl haben. Nehmen wir an, diese Zufallszahl sei 508. Sie muss dann einfach durch die Anzahl der Teilnehmer dividiert werden, und der Divisionsrest plus eins zeigt dann auf den glücklichen Gewinner:

508 ÷ 5 = 101, Rest 3

508 = 101 × 5 + 3, und somit ist der Divisionsrest 3. Weil der Wertebereich für den Divisionsrest jedoch 0 bis 4 statt 1 bis 5 ist, muss noch 1 zum Ergebnis addiert werden. In unserem Beispiel hat also Teilnehmer Nummer 3 + 1, Froschkönig, gewonnen.

Mit bc lässt sich dies - auch für große Zahlen - leicht ermitteln. Der Modulo-Operator, mit dem der Divisionsrest berechnet wird, ist das Prozentzeichen % in bc:

$ bc
508 % 5 + 1
4
quit

Allerdings liegt unsere Zufallszahl in Hexadezimalnotation vor. 508 ist in Hex 1FC. Die Eingabe für bc muss für hexadezimale Eingabe leicht geändert werden:

ibase = 16
n = 1FC
ibase = A
n % 5 + 1
4

In Zeile 1 des bc-Skripts wird die Eingabebasis auf 16 gesetzt. Zahlen in der Eingabe werden dadurch mit der Basis 16 interpretiert, die Ausgabe bleibt jedoch dezimal. Die Hex-Zahl 1FC (508 dezimal) wird danach der Variablen n zugewiesen, und in Zeile 3 wird die Eingabebasis wieder auf dezimal zurückgestellt (A ist die Hexadezimalschreibweise für die Dezimalzahl zehn).

In Zeile 4 wird schließlich die gleiche Berechnung wie vorher durchgeführt, und das Ergebnis bleibt natürlich 4.

Mit Perl lässt sich dieses bc-Skript direkt auf der Kommandozeile erzeugen:

$ echo 1FC | perl -lne 'print "ibase=16;n=$_;ibase=A;n%5+1"' | bc
4

Voilà! Auf der Kommandozeile müssen die Zeilenumbrüche für bc nur durch Semikolons ersetzt werden.

Zurück zum ursprünglichen Beispiel mit dem Message-Digest von Donald Trumps Tweet und 2304 Teilnehmern:

$ echo 'SEE YOU IN COURT, THE SECURITY OF OUR NATION IS AT STAKE!' \
    | openssl sha -whirlpool \
    | sed -e 's/.*= //' \
    | tr '[:lower:]' '[:upper:]' \
    | perl -lne 'print "ibase=16;n=$_;ibase=A;n%2304+1"' \
    | bc
1639

Teilnehmer Nummer 1639 hat gewonnen!

Jetzt muss nur noch 2304 durch die Anzahl der Teilnehmer ersetzt werden und als Entropiequelle Trumps aktueller Tweet eingesetzt werden. Und schon hat die eigene Onlineverlosung ein grundsolides, kryptographisch sicheres Fundament!