Zahlen in festem Bereich aus Datenstrom erzeugen

[xJulian]

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?

[peschai]

Hallo,

das klingt für mich danach, daß du eine Hash funktion erstellen möchtest ...
Google doch mal nach SHA160 bzw. SHA256.... oder MD5
Das sind anerkannte Algorithmen ...

[xJulian]

Danke für dein Interesse. :)

Grundsätzlich hast du Recht damit, dass die von mir gesuchte Funktion ähnliche Eigenschaften wie ein Hash hat (sie soll deterministisch und möglichst kollisionsfrei sein). Die Crux liegt aber woanders, nämlich darin, dass der Computer seine Daten ja normalerweise in Bytes speichert. Ich möchte aus diesen Daten (ein 64 Zeichen breites Wort aus einem 256 Zeichen umfassenden Alphabet) jedoch ein möglichst langes Tupel aus Zeichen eines Alphabets beliebiger Länge n erzeugen. Diese Abbildung soll eindeutig, aber nicht notwendigerweise umkehrbar sein.

Normalerweise bietet sich hierzu die Konvertierung einer (riesigen) Zahl vom 256er- ins n-er-System (z.B. n=62) an. Allerdings ist das Datenmaterial viel zu lang, um als eine Zahl aufgefasst und ohne Weiteres verarbeitet werden zu können. Deshalb suche ich nach alternativen Vorschlägen.

[SnuffMaster23]

Um vom 256er- ins 62er-System umzuwandeln musst du doch die 512 Bits nicht als eine (Binär-)Zahl behandeln. Wenn dus als Stringdarstellung dieser Zahl siehst musst du immer nur mit einzelnen Bytes hantieren ;)

[xJulian]

Das ist richtig, so erhalte ich für jedes Byte meiner Quelldaten ein Zeichen aus dem Ausgabealphabet. In der Praxis reicht das auch. Am liebsten hätte ich allerdings eine effizientere Nutzung der Daten, da, wenn ich aus einem Byte immer nur ein Zeichen generiere, bei kleinen Alphabeten immer Bits "ungenutzt" bleiben. Um diese nahtlos zu nutzen, müsste ich die Quelldaten als eine große Zahl betrachten (s.o.).

[SnuffMaster23]

Hm stimmt, du würdest beim richtigen umwandeln die Zahl ja auch 'ganz' im Speicher haben wollen/müssen.
In der Unit FMTBcd sind Routinen um mit BCD-Zahlen zu rechnen, mit denen gings. Allerdings hab ich das auch nur grad gegoogelt und nciht ausprobiert.

Oder du teibst noch zwei Ausgabezeichen auf, dann kannst du ja ins 64er-System umwandeln, das geht Byte-weise :D