Wie zufällig ist Random(x)?

[negaH]

Zitat:

Interessanterweise kann aber (noch) niemand die Zahlenfolge einer der benannten Hardwarelösungen (atmosphärisches Rauschen, radioaktiver Zerfall von Atomen, Photonendurchgang halbdurchlässiger Spiegel) vorhersagen. Damit ist das nicht nur für jeden nicht eingeweihten sondern eben auch für jeden Eingeweihten absolut zufällig - und damit an und für sich zuverlässiger und besser als jegliche berechenbare Zahlenfolge. Dein Vergleich hinkt da nämlich ein wenig.

Gut, wenn ich nicht beweisen kann das 1 <> 0 ist so kann ich auch nicht beweisen das 0 == 1 ist.
D.h. wenn wir nicht beweisen können das der Zufall tatsächlich zufällig ist so kann ich auch nicht behaupten das der HW-RNG auch wirklichen Zufall produziert. Der einzigste Grund warum wir HW-RNGs als Zufallsgeneratoren benutzen ist das Wissen das alle Menschen in der Welt nicht das Wissen besitzen die HW-RNGs vorauszuberechnen. Aber exakt das kann ein Drugschluß sein. Somit gleicht die Benutzung von HW-RNGs nichts anders als dem Glauben, wir wissen rein garnichts.

Tatsächlich ist es sogar so das die Wissenschaftler garnicht bestreiten das deren HW-RNGs keinen echten Zufall produzieren. Jeder Wissenschaftler wird behaupten das es garkeinen echten Zufall geben kann, sondern das JEDES Ereignis eine Folge von Ursache und Wirkung ist. Nur, die Komplexität ist so hoch und der Erkenntisstand ist so gering das wir eben diese Ereignisse nicht vorausberechnen können.

Somit dreht sich bei der logisch richtigen Wahl zwischen HW-RNG und PseudoRNG in keinem Fall um die Frage "wie zufällig ist der Zufall des Generators" sondern nur "Was ist mit unserem derzeitigen Wissenstand durch uns nachvollziehbarer und beweisbarer Zufall". Statt also HW-RNGs mit im Grunde mathemtisch nicht bewiesenen Eigenschaften und Seiteneffekten zu benutzen, plädiere ich also nur dafür das beweisbare Wissen zu benutzen, sprich PRNGs. Denn beides sind und müssen immer nur pseudozufällig sein, das einzig relavante an beiden Generatoren ist die Frage nach deren Komplexität. Ein PRNG kann heutzutage so komplex sein, bzw. dessen benutzte Daten, das er ohne diese Daten nicht mehr berechenbar ist. Somit erzielt man mit einem solchen PRNG den gleichen Zufallseffekt wie mit einem HW-RNG. ABER!! eben mit einem wesentlichen Unterschied, beim HW-RNG wissen wir garnichts über seine Mathematik, den PRNG haben wir dagegen aus unserem Wissen heraus so konstruiert das wir beweisen können das er funktioniert. Wir können ihn also explizit konstruieren und nach unseren Wünschen modellieren. Der produzierte Zufall unterscheidet sich in seinen statistischen Eigenschaften in nichts von jedem anderen Zufall.

Zitat:

Natürlich kann ich auch ein ungeheuer geheimes und kompiziertes Verfahren zur Verschlüsselung verwenden. Solange nur ich und mein Gegenüber dies kennen können wir auch absolut geheim und nicht abhörbar kommunizieren. Aber jeder dem das Verfahren bekannt ist, kann es gezielt angreifen. Eine solche Verschlüsselung ist also defakto unsicher. Quantenkryptographie ist hingegen sicher, auch wenn das Verfahren hinlänglich bekannt ist. Und auch hier verlassen wir uns wieder auf die Hardware.

Das Verfahren solcher PRNG, bzw. aller Verschlüsselungen, sollte aus sich heraus sicher sein egal ob man es kennt,bzw. sogar weil man es kennt. Die Kenntnis über die Algorithmen darf eben NICHT die Sicherheit beeinflussen. D.h. nur die Passwörter bzw. der Seed beim PRNG muß so enorm groß gewählt sein das die Komplexität so groß wird das mit heutiger Technik und Wissensstand die Daten sicher sind. Exakt so kann man PRNGs konstruieren. D.h. nur derjenige der den Startwert kennt und eventuell einige Arbeitsparamter kann die Zufallsbit vorhersagen. Für jeden anderen produziert der PRNG aber Zufallsbits die wie echter Zufall oder eben wie HW-RNGs nicht vorhersagbar sind. D.h. nur die Komplexität der benutzten Daten -> Seed, Passwort, Primzahlen etc. pp., bestimmt die Sicherheit. Die Beweisbarkeit das das dann sicher sein muß liegt direkt im Beweis des benutzten Algorithmus. Gibt es keinen effizienteren "Gegen-Algorithmus" so kann man das System nur knacken -> entschlüsseln oder Zufallsbits vorhersagen, wenn man das Passwort/Seed etc. findet. Statt also die Mathematik NUR als Reaktion durch uns Menschen auf unsere Umwelt zu betrachten, benutzen wir die Mathematik um von uns exakt vorgegebene Modelle und Ziele zu verwirklichen. Wir benutzen die Mathematik um einen PRNG zu bauen der beweisbar so gut ist wie "echter" Zufall und denoch für nicht authorisierte Personen nicht vorhersagbar sein wird. Somit bekommen wir das doppelte was uns ein HW-RNG bieten kann. Beide RNGs sind genauso zufällig, beide RNGs sind aus unserere Sicht gleich komplex, aber NUR der PRNG ist durch uns auch mathematisch beweisbar !

So, wir wissen also ganz genau was wir machen müssten um einen sicheren PRNG vorhersagen zu können, OHNE dessen Paramter zu kennen, eben weil wir den benutzten Algorithmus = die Mathematik kennen.

Bei HW-RNGs wissen wir das eben nicht, wir wissen rein garnichts, und nehmen einfach mal an das es auch kein anderer weis. Somit enthalten die HW-RNGs aus ihrem philospohischen Grundkonzept heraus einen entscheidenen Fehler, einen Fehler der sie im Grunde widersinnig erscheinen lässt. Warum sollte man HW-RNGs in der Kryptographie benutzen wollen um die Sicherheit zu erhöhen. Das ist das gleiche als wenn man einen unüberprüften, nicht beweisbar sicheren, prohibitären Verschlüsselungsalgorithmus benutzen würde. Wir müssten dem Hersteller absolut vertrauen und die effektive Sicherheit wäre gleich NULL !

Es besteht heutzutage nicht im geringsten die Notwendigkeit HW-RNGs zu benutzen.
Für Statistische Berechnungen werden eh nur PRNGs benutzt, damit man die statistischen Berchenungen exakt reproduzieren kann. Das betrifft alle Gebiete der technischen Simulation, ob Genetische Algorithmen, Modelling, Statistiken oder neuronale Netze. Für die Kryptographie sind HW-RNGs sogar tödlich da sie insich ja schon auf Unsicherheit=Unwissen beruhen.


Nach diesem vielen Gerede und der Eingangsfrage wie man einen guten RNG konstruiert möchte ich auch darauf noch antworten.

Der einzigste mathematisch bewiesene PRNG der sicher ist, sprich bei Nichtwissen der Seed/Primzahlen nur die Aussage zulässt "mit einer Wahrscheinlichkeit von 50% ist das nächste Bit eine 0 oder 1", ist der "Quadratische Reste Generator". Er wird auch nach seinen Erfindern der Blum Blum Shub Generator genannt.
Das Verfahren ist so einfach wie genial:

1.) erzeuge 2 Primzahlen P und Q, jede kongruent zu 3 mod 4. Die Bitgröße dieser Primzahlen bestimmt wie hoch der Aufwand wäre deisen Genrator zu brechen.
2.) erzeuge einen Seed R

Um 1 Bit zu erzeugen rechne

R := R^2 mod (P * Q);
Bit = Odd(R);


Wurden P und Q zb. mit jeweils 1024 Bit erzeugt, so ergibt sich N = P*Q mit 2048 Bit, ergo unser Seed R hat durchschnittlich 2048 Bit.

Man kann die Zufallsbits die dieser Generator erzeugt nur vorausberechnen wenn man R kennt, oder aber P und Q kennt, oder aber in der Lage wäre N = P*Q in deren beiden Primzahlen zu faktorisieren. Durch die Wahl der Größe von P,Q kann man als ganz exakt vorherbestimmen ob man die Zufallsbits vorhersagen kann oder nicht.

Wer von euch schon mein DECmath installiert hat kann mit nachfolgendem Source rumexperimentieren:

Delphi-Quellcode:

var
  P,Q,N,R: IInteger;
  I: Integer;
begin
// erzeuge zwei Primzahlen
  repeat
  // P, 512 Bit groß, P == 3 mod 4
    NRnd(P, 512);
    NBit(P, 511, True);
    NMakePrime(P, 3, 4, [1, 2]);

  // Q, 512 Bit groß, Q == 3 mod 4
    NRnd(Q, 512);  
    NBit(Q, 511, True);
    NMakePrime(Q, 3, 4, [1, 2]);

  // N = P * Q
    NMul(N, P, Q);
  until NCmp(P, Q) <> 0;

// initialisiere Seed mit Passwort oder Entropie erzeugt durch indivuduellen menschlichen Input
  NSet(R, 'Password');

// erzeuge 10000 Zufallsbits
  for I := 0 to 9999 do
  begin
    NSqrMod(R, N);
    Bit := NOdd(R);
  end;  
end;

Gruß hagen