Hallo!
Ich beschäftige mich im Moment damit, aus vorhandenen (Zufalls-)Daten Passwörter zu generieren.
Vorhanden ist ein 512 Bit langer Datenstrom (in meinem Fall: ein Byte-Array mit 64 Elementen), aus dem ein möglichst langes Wort generiert werden soll. Die Ausgabemenge ist in Form eines Alphabets angegeben (z.B. ein String: "ABC...XYZabc...xyz012...789"), welches eine feste Mächtigkeit besitzt (im Beispiel: 62 Zeichen). Der Einfachheit halber nehme ich an, dass das Alphabet die Länge 256 nicht überschreitet.
Momentan erzeuge ich meine Zufallszeichen so:
Code:
(zufälliges Byte) mod (Länge des Alphabets)
Das funktioniert prinzipiell, allerdings bringt diese Unterteilung der möglichen Byte-Werte in Äquivalenzklassen in den meisten Fällen ein Ungleichgewicht bei den Wahrscheinlichkeiten der einzelnen Zeichen mit sich, mit dem ich nicht zufrieden bin. So treten beim obigen Alphabet die Großbuchstaben A bis H mit 5/256 Wahrscheinlichkeit auf, alle anderen Zeichen aber nur mit 4/256.
Eine andere Möglichkeit wäre:
Code:
Round((zufälliges Byte) * (Länge des Alphabets) / 256)
Abgesehen davon, dass dies in jedem Fall weniger performant ist, gibt es auch hier Probleme: Dadurch, dass die Rundungsintervalle an den Rändern des Zahlenbereichs teilweise außerhalb des Wertebereichs liegen, treten das erste und das letzte Zeichen nur halb so häufig auf.
Nun könnte ich natürlich ans Ende des Alphabets noch einmal das erste Zeichen anfügen und hätte dann eine nährungsweise homogene Zufallsverteilung (ich kann jetzt nicht sagen, inwieweit die Ungenauigkeit von Fließkommazahlen hier bereits eine Rolle spielt). Ein kurzer Praxistest mit einigen Millionen Zufallsbytes scheint mir da recht zu geben.
Aber geht es besser/schneller? Perfekt wär natürlich die Modulo-Methode, wenn ich meine 512 Bit als eine riesige Zahl auffassen würde, dann könnte ich so lange teilen und die Divisionsreste speichern, bis die Zahl halt "aufgebraucht" ist. Aber die einzige BigNum-Implementierung für Delphi/Object Pascal, die ich
finden kann, bekomme ich mit FPC nicht kompiliert (irgendwie inkompatible Assembly-Syntax).
Wer hat sich vielleicht schon damit beschäftigt und kann mir mehr erzählen?