AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Zufällige Zahl auf Zahlenbereich abbilden

Ein Thema von Valle · begonnen am 29. Sep 2011 · letzter Beitrag vom 30. Sep 2011
Antwort Antwort
Benutzerbild von Valle
Valle

Registriert seit: 26. Dez 2005
Ort: Karlsruhe
1.223 Beiträge
 
#1

Zufällige Zahl auf Zahlenbereich abbilden

  Alt 29. Sep 2011, 21:57
Hallo DPler!

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
Valentin Voigt
BOFH excuse #423: „It's not RFC-822 compliant.“
Mein total langweiliger Blog
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.673 Beiträge
 
Delphi 2007 Enterprise
 
#2

AW: Zufällige Zahl auf Zahlenbereich abbilden

  Alt 29. Sep 2011, 22:06
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".
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.480 Beiträge
 
Delphi 11 Alexandria
 
#3

AW: Zufällige Zahl auf Zahlenbereich abbilden

  Alt 29. Sep 2011, 22:12
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 0 <= lese_zufalls_bytes < 20 und k = 6 )
Code:
 0  1  2  3  4  5
 6  7  8  9 10 11
12 13 14 15 16 17
18 19
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list

Geändert von himitsu (29. Sep 2011 um 22:19 Uhr)
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.673 Beiträge
 
Delphi 2007 Enterprise
 
#4

AW: Zufällige Zahl auf Zahlenbereich abbilden

  Alt 29. Sep 2011, 22:15
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.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Benutzerbild von Valle
Valle

Registriert seit: 26. Dez 2005
Ort: Karlsruhe
1.223 Beiträge
 
#5

AW: Zufällige Zahl auf Zahlenbereich abbilden

  Alt 29. Sep 2011, 22:17
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
Valentin Voigt
BOFH excuse #423: „It's not RFC-822 compliant.“
Mein total langweiliger Blog
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
40.480 Beiträge
 
Delphi 11 Alexandria
 
#6

AW: Zufällige Zahl auf Zahlenbereich abbilden

  Alt 29. Sep 2011, 22:23
Bei 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.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list
  Mit Zitat antworten Zitat
Benutzerbild von Valle
Valle

Registriert seit: 26. Dez 2005
Ort: Karlsruhe
1.223 Beiträge
 
#7

AW: Zufällige Zahl auf Zahlenbereich abbilden

  Alt 29. Sep 2011, 22:32
Bei 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.

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
Valentin Voigt
BOFH excuse #423: „It's not RFC-822 compliant.“
Mein total langweiliger Blog
  Mit Zitat antworten Zitat
Blup

Registriert seit: 7. Aug 2008
Ort: Brandenburg
1.394 Beiträge
 
Delphi 10.4 Sydney
 
#8

AW: Zufällige Zahl auf Zahlenbereich abbilden

  Alt 30. Sep 2011, 09:36
Dein urspünglicher Ansatz scheint mit ok zu sein, aber langsam.

Code:
zufall = abs(lese_zufall) % K
Wie schon von himitsu bemerkt, die unteren Elemente im Array werden häufiger ausgewählt.

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.
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.673 Beiträge
 
Delphi 2007 Enterprise
 
#9

AW: Zufällige Zahl auf Zahlenbereich abbilden

  Alt 30. Sep 2011, 10:41
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.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:56 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf