Zufällige Zahl auf Zahlenbereich abbilden

[Valle]

Hallo DPler! :hi:

Mittels der Blockdatei /dev/random auf einem Unix-System kann man byteweise kryptografisch sichere Zufallszahlen auslesen. Diese reichen also jeweils von 0 bis 2^(8n)-1, wobei n die Anzahl an gelesenen Bytes und damit beliebig ist. Gegeben sei jetzt eine Liste mit k Elementen. Wie kann ich eine ausgelesene Zufallszahl kryptografisch korrekt dazu verwenden, ein zufälliges Element aus der Liste auszuwählen?

Folgender Pseudocode sollte tun was er soll; ich weiß aber nicht ob das theoretisch so gemacht werden darf. Es geht um sicherheitstechnisch "heikle" Sachen. ;-)

Code:

zufall = -1
solange zufall < 0 oder zufall > k-1:
    zufall = lese_zufalls_bytes(1) // falls k <= 255
ergebnis = liste[zufall]

(es geht nicht um Delphi!)

Liebe Grüße,
Valentin

[Medium]

Code:

zufall = abs(lese_zufall) % K

sollte die Gleichverteilung (die Pseudo-RNGs üblicherweise generieren) beibehalten. (K = Anzahl Listenelemente)
Edit: Wenn die Zahen eh nur von 0..max gehen, kann das abs() weg, sowie auch dein "<0".

[himitsu]

Ich würde nicht unbedingt nach einer passenden Zahl suchen, sondern einfach den gegebenen Wertebereich auf den gewünschten Wertebereich umrechnen.

Code:

zufall = Runden(lese_zufalls_bytes(1) / 256 * k)
ergebnis = liste[zufall]

zufall = Integer(lese_zufalls_bytes(1)) * k div 256
ergebnis = liste[zufall]

// angenommen das Byte von lese_zufalls_bytes wird automatisch vergrößert 
zufall = lese_zufalls_bytes(1) * k div 256
ergebnis = liste[zufall]

Falls es dir egal ist, wenn untere Felder öfters ausgewählt werden, als höhere, dann wäre auch sowas möglich

Code:

zufall = lese_zufalls_bytes(1) mod k
ergebnis = liste[zufall]

aber bedenke (gegeben sei

Delphi-Quellcode:

0 <= lese_zufalls_bytes < 20

und

Delphi-Quellcode:

k = 6

)

Code:

 0  1  2  3  4  5
 6  7  8  9 10 11
12 13 14 15 16 17
18 19

[Medium]

Wenn "K" zudem eine Zweierpotenz ist, kann man das mod (%) auch schneller mit logischen OPs machen: zufall = (zieltyp)(lese_zufall & 0xHHHHHHHH), wobei "HHHHHHHH" bei (byte) eben 000000FF wäre.

[Valle]

Hallo,

vielen Dank für deine Antwort! Gleichverteilung war wohl genau das Wort, das ich gesucht habe. :)

Der Betrag ist in der Tat unnötig in diesem Fall. Mein "< 0" allerdings ist vom Code her nötig (damit der erste Schleifendurchlauf auch tatsächlich stattfindet).

k ist keine Zweierpotenz.

@himitsu: Dein Code leuchtet mathematisch sogar ein, Dankeschön dafür. :) Sofern das kryptografisch in Ordnung ist, ziehe ich den von Medium der Einfachheit halber aber vor. ;)

Liebe Grüße,
Valentin

[himitsu]

Bei

Delphi-Quellcode:

k = Zweierpotenz

ist medium's Vorschlag nur eine Code-/Laufzeitoptimierung,
verändert aber am rechnerischen Ergebnis nicht.

Eventuell kannst du auch auf eine MulDiv-Funktion zurückgreifen, um die Berechnung von * und DIV zusammenzufassen.

[Valle]

Zitat:

Zitat von himitsu (Beitrag 1127576)

Bei

Delphi-Quellcode:

k = Zweierpotenz

ist medium's Vorschlag nur eine Code-/Laufzeitoptimierung,
verändert aber am rechnerischen Ergebnis nicht.

Ja, ich weiß. ;-) Ist aber unerheblich, da k keine Zweierpotenz sein muss.

Zitat:

Zitat von himitsu (Beitrag 1127576)

Eventuell kannst du auch auf eine MulDiv-Funktion zurückgreifen, um die Berechnung von * und DIV zusammenzufassen.

Mir ist keine derartige Funktion in Python bekannt. Macht aber auch nichts, der Zeitaufwand fällt hier kaum ins Gewicht.

Liebe Grüße,
Valentin

[Blup]

Dein urspünglicher Ansatz scheint mit ok zu sein, aber langsam.

Zitat:

Zitat von Medium (Beitrag 1127570)

Code:

zufall = abs(lese_zufall) % K

Wie schon von himitsu bemerkt, die unteren Elemente im Array werden häufiger ausgewählt.

Zitat:

Zitat von himitsu (Beitrag 1127573)

Ich würde nicht unbedingt nach einer passenden Zahl suchen, sondern einfach den gegebenen Wertebereich auf den gewünschten Wertebereich umrechnen.

Code:

zufall = Runden(lese_zufalls_bytes(1) / 256 * k)
ergebnis = liste[zufall]

zufall = Integer(lese_zufalls_bytes(1)) * k div 256
ergebnis = liste[zufall]

// angenommen das Byte von lese_zufalls_bytes wird automatisch vergrößert 
zufall = lese_zufalls_bytes(1) * k div 256
ergebnis = liste[zufall]

Auch dieser Ansatz liefert eine ungleiche Verteilung, bestimmte Elemente werden häufiger ausgewählt als andere.
In Extremfällen wird dies deutlich:
k = (Zufallszahlendbereich + 1) -> ein bestimmtes Element wird niemals gewählt
k = (Zufallszahlendbereich - 1) -> ein bestimmtes Element wird doppelt so häufig gewählt wie die anderen

Ist der Zufallszahlenbereich allerdings hinreichend groß, kann dieses Problem vernachlässigt werden.
Ich würde den Zufallszahlenbereich dafür > (k ^ 2) wählen.

[Medium]

Ui stimmt, wenn bei der "mod"-Variante die Anzahl der Listenelemente kein Vielfaches von max(random) ist, hat man eine Bevorzugung. Dann wäre das Skalieren "zufall = round((get_random / max(random)) * anz_einträge)" besser, wobei auch hier Verzerrungen durch Rechenungenauigkeiten mit den Floats und dem Runden auftreten könnten, die aber schwerer zu bewerten sind. Sie sollten aber klein genug ausfallen, um für den Anwendungsfall locker zu genügen. Für mathematisch korrekte Verwendung ggf. nicht. Dann blieben eigentlich nur 2^n-Listen, da die RNGs i.A. nur "random bits" garantieren.