Entwickler-Ecke :: Thema anzeigen - nicht zurückverfolgbares Random

IhopeonlyReader - Di 17.09.13 21:22
Titel: nicht zurückverfolgbares Random

Guten Tag,
da jaenicke mich aufgeklärt hat, dass bei Randomize nur ein Seed erstellt wird (über die Systemzeit) erstellt und danach die Zufallszahlen aus einer "Liste" genommen werden. Der Seed sei 32 Bit groß und somit gäbe es 2^32 Möglichkeiten. Egal wieviele Werte ich Randome.

Wie kann ich das ganze so gestalten, dass es nicht nur 2^32 Möglichkeiten gibt?
Wenn ich z.B. ein Byte-Array mit 10^6 Werte haben will, dass 2^(8* 10^6) Möglichkeiten hätte und nicht nur 2^(8*4) Byte.

Meine Überlegung war,

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

- Randomize
- 65535(10^4) Bytes "Randomen"
- Randomize;
- 256 Words randomen
- Randomize;
- 1 Bytes randomen, ab da werden aus den 256 Word-Werten 2 Words genommen  (Word1 ist Start, Word2 ist Ende)
- An das ByteArray Byte[Wert1] bis Byte[Wert2] anhängen

Wiederholen bis man 10^6 Bytes hat.

Aber es gibt doch sicher mehr als nur die "blöde" Variante, oder? Habe in Google nichts zu selbstgebauten Random-Funktionen gefunden... :(

dann lasst mal euren Ideenreichtum spielen,
mfg Ihopeonlyreader

Mathematiker - Di 17.09.13 21:31

Hallo,

IhopeonlyReader hat folgendes geschrieben :

Wie kann ich das ganze so gestalten, dass es nicht nur 2^32 Möglichkeiten gibt?
Wenn ich z.B. ein Byte-Array mit 10^6 Werte haben will, dass 2^(8* 10^6) Möglichkeiten hätte und nicht nur 2^(8*4) Byte.

Du hast einen Denkfehler, denn 2^32 = 4294967296, also mehr als 4*10^9.
Das Potenzgesetz ergibt 2^32 = ( 2^8 )^4.
2^(8* 10^6) ist eine Zahl mit über 2,4 Millionen Stellen.

Willst Du einen Zufallsgenerator mit einer längeren Periode als 2^32, so gibt es im Netz eine ganze Menge.
Interessant ist Floyds Zyklenalgorithmus:
Die Elemente a(k) werden z.B. mit

Quelltext

1:	a(k+1) = a(k)² + c (mod p)

berechnet, wobei c verschieden -2 und 0 sein soll. Nach einer gewissen Vorperiode tritt die Folge a(k) in eine Periode der Länge von rund Wurzel(p). Zur Berechnung mit p > 2^64 brauchst Du dann aber eine Langzahlarithmetik.

Beste Grüße
Mathematiker

Mathematiker - Di 17.09.13 21:56

Hallo,

IhopeonlyReader hat folgendes geschrieben :

... und somit 2^(8*10^6) Möglichkeiten

Noch einmal. 2^(8*10^6) ist eine Zahl mit 2,4 Millionen Stellen, d.h. mehr als 10^2400000.

Diese Zahl von Möglichkeiten benötigt man nicht! Das ist unvorstellbar mehr als alle Elementarteilchen des sichtbaren Weltalls. Kein Computer irgendeiner Welt wird jemals diese Möglichkeiten vollständig abarbeiten können. Es geht einfach nicht.
Du kannst 10^6 Werte doch mit einem normalen Zufallsgenerator füllen. Der liefert mehr als 4*10^9 verschiedene Werte. Wo ist das Problem?
Ich denke, wir reden aneinander vorbei.

Beste Grüße
Mathematiker

Nachtrag: Ich glaube jetzt Dein Ziel verstanden zu haben. Du willst 8 Millionen Bit = 1 Million Byte zufällig füllen.
Das geht problemlos mit

Delphi-Quelltext

1:	for i:=1 to 1000000 do wert[i]:=random(256);

Zwar sind einige wert[i] mit anderen wert[j] gleich. Durch randomize/randseed sind es aber jedes Mal andere. Dadurch bekommst Du stets eine Pseudozufallsfolge.
Echte Zufallszahlen bekommst Du mit einem deterministischen Zufallsgenerator ohnehin nicht.

IhopeonlyReader - Di 17.09.13 22:10

ja, 2^(8* 10^6) ist die Anzahl der Möglichkeiten die ein ByteArray mit einer länge von 10^6 annehmen kann, das ist aber richtig ooder?

Wenn man das so machen würde:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

var aByteArr: Array of Byte;
C: Cardinal;
const ZHS = 10*1000*1000; // Zehn Hoch Sechs (10^6)
begin
Randomize;
setlength( aByteArr, ZHS );
For C:=0 to ZHS-1 do
  aByteArr[C] := Random(256); 
end;

dann hätte man zwar so viele Pseudo-Zufallszahlen (10^6 Byte voll damit) aber eigentliche Information sind nur 4 Byte. Egal wie lang das ByteArray wäre, es enthielt 4 Byte Informationen (den Random-Seed) wenn man den kennt, kennt man alle 10^6 Bytes. Das will ich vermeiden (Information von Jaenicke aus http://www.entwickler-ecke.de/viewtopic.php?t=112027)

Moderiert von Narses: Beiträge zusammengefasst

Zu deinem Nachtrag:

Mathematiker hat folgendes geschrieben :

Du willst 8 Millionen Bit = 1 Million Byte zufällig füllen. [...]
Zwar sind einige wert[i] mit anderen wert[j] gleich. Durch randomize/randseed sind es aber jedes Mal andere. Dadurch bekommst Du stets eine Pseudozufallsfolge.
Echte Zufallszahlen bekommst Du mit einem deterministischen Zufallsgenerator ohnehin nicht.

ja, genau. Leider hat man dann nach ein paar werten evt. schon den Seed ! (gibt nur 2^32 Seeds!) Wenn man den Seed dann (z.B. durch die ersten 10 Bytes) kennt, kennt man auch alle anderen Bytes !

Mathematiker - Di 17.09.13 22:34

Hallo,

IhopeonlyReader hat folgendes geschrieben :

Leider hat man dann nach ein paar werten evt. schon den Seed !

Das glaube ich nicht, allerdings weiß ich nicht, mit welchem Zufallsgenerator Delphi tatsächlich arbeitet.
Wäre es z.B. der kongruentielle Zufallsgeneratoren von Lehmer, so entstehen die x(i) durch die Rekursionsvorschrift

Quelltext

1:	x(i) = (c · x(i-1)) mod p

zum Beispiel mit c = 23 und p = 10^7+1.
Ganz so sicher bin ich Zahlentheorie nicht. Aber ich denke, dass man aus der Kenntnis einiger x(i) nicht auf den Startwert schließen kann. Dazu müsste man c und p kennen und ich denke, die würden bei randomize ebenfalls variieren.
Daher behaupte ich einmal (ohne es genau zu wissen), dass man aus einigen bekannten x(i) nach einem randomize in vertretbarer Zeit nicht auf die Startzahl zurückrechnen kann.
Aber vielleicht kennt sich in dieser Materie jemand anderes besser aus.

Beste Grüße
Mathematiker

IhopeonlyReader - Di 17.09.13 22:46

Wenn man alle 2^32 Möglichkeiten aufbaut (der Randomseed) und dann die Bytewerte mit dem Bytearray vergleichen würde, so käme man denke ich schon relativ schnell dazu, welcher Seed verwendet wurde...
wie gesagt user profile icon

jaenicke hat mich auf den seed aufmerksam gemacht: http://docwiki.embarcadero.com/Libraries/XE5/de/System.RandSeed

Moderiert von Narses: Beiträge zusammengefasst

FinnO hat folgendes geschrieben :

Machs richtig ;)

klar ;) am besten verwende ich die Quantenphysik

hathor hat folgendes geschrieben :

Zufallszahlen gibt es auch im Internet mit 1.41 trillion random bits

cool :D aber sicherlich steckt da auch ein "vorhersehbarer" algerithmus hinter. (kennt man sagen wir 80% der werte, könnte man die anderen 20% vorhersagen). Habe leider nicht gefunden, wie die Seite arbeitet !

Mathematiker - Di 17.09.13 23:00

Hallo,

hathor hat folgendes geschrieben :

Zufallszahlen gibt es auch im Internet mit 1.41 trillion random bits :

Ja, diese Trillionen. Es sind insgesamt 1412449787797 bits, d.h. nach der "richtigen" Bezeichnung 1,4 Billionen bits, also rund 176 Milliarden Bytes. Das ist schon 'ne ganze Menge.
Meine Festplatte ist ziemlich leer. Vielleicht downloade ich mal die 164 GiB. Bei meiner Internetverbindung dauert das wohl 1 Jahr oder mehr.

IhopeonlyReader hat folgendes geschrieben :

Du willst für 2^32 = 4294967296 Folgen, sagen wir 10 Glieder, ausrechnen? Das sind 42 Milliarden Bytes! Und die willst Du in vertretbarer Zeit abgleichen.
Ich lasse mich gern vom Gegenteil überzeugen. Aber ich denke nicht, dass das so einfach und hinreichend schnell ist.
Und wenn ich bösartig bin und vor dem Füllen der Werte erst 100 Zufallszahlen "wegwerfe" und dann erst nutze, brauchst Du zum Abgleich schon 110 oder mehr berechnete Glieder.

Beste Grüße
Mathematiker

Mathematiker - Mi 18.09.13 00:00

Hallo,

jfheins hat folgendes geschrieben :

Da du offenbar gerne Rätsel stellst, generiere doch mal eine Folge mit Hilfe des Delphi-PRNG, poste die ersten 100 Glieder und lasse andere Leute die nächsten paar Zahlen herausfinden. :wink:

Obwohl ich nicht weiß, ob Du mich meinst :nixweiss: , bitte gern:

Quelltext

1:

65, 84, 227, 44, 90, 133, 59, 140, 155, 66, 83, 10, 72, 7, 255, 163, 64, 169, 122, 162, 109, 174, 11, 139, 198, 160, 162, 218, 129, 34, 24, 245, 46, 178, 252, 230, 214, 101, 34, 191, 89, 8, 80, 196, 175, 120, 198, 175, 190, 22, 129, 188, 229, 158, 105, 64, 124, 229, 218, 254, 220, 35, 46, 135, 182, 227, 52, 71, 202, 184, 198, 30, 66, 71, 229, 151, 74, 93, 7, 38, 163, 4, 132, 252, 70, 226, 82, 87, 92, 79, 117, 101, 37, 236, 210, 27, 135, 174, 82, 143,

Hier sind 100 Zufallsbytes mit dem normalen Delphi 5-Zufallsgenerator. Den Randseed-Wert behalte ich mal für mich. Der Quelltext zum Erstellen dieser Zahlen ist

Quelltext

1:

327B0797CD195BD801B0A20D9CF879358C967AFB5DC845BA1719AFF827C5AC236E8FE679A382E56709F11A13F0AB14BD4F71A41D42ACC5156D4230019BBDB8C489E57F2F98D9024B5A77C3CA84EBA1D9E772533833E94F97AD25924BD34B63EE3E29F1D1F0E988C196BB424B30C736F6D7E4157F6A1C6AB14DD0DF2AAB5245F3E55C335A22B80A3BB99B26388339E94859EB3AF1471F51E120D7C7552AE87BECD775F1FB18FC5AE1BA74C3767F70894CA8203CCED488E3922EE82DEEF5D433159E215E17EEB57F9E5E0ED599058F809D41847C2E49E54F74F34E1A2ADB32F192C60EE39D718171748D05807337F957

RC4-verschlüsselt. Damit keiner sagt, ich würde nicht fair spielen. :wink:
Viel Spaß beim Ermitteln der nachfolgenden Zufallszahlen.

Beste Grüße
Mathematiker

IhopeonlyReader - Mi 18.09.13 00:50

Quelltext

1:
2:
3:

65, 84, 227, 44, 90, 133, 59, 140, 155, 66, 83, 10, 72, 7, 255, 163, 64, 169, 122, 162, 109, 174, 11, 139, 198, 160, 162, 218, 129, 34, 24, 245, 46, 178, 252, 230, 214, 101, 34, 191, 89, 8, 80, 196, 175, 120, 198, 175, 190, 22, 129, 188, 229, 158, 105, 64, 124, 229, 218, 254, 220, 35, 46, 135, 182, 227, 52, 71, 202, 184, 198, 30, 66, 71, 229, 151, 74, 93, 7, 38, 163, 4, 132, 252, 70, 226, 82, 87, 92, 79, 117, 101, 37, 236, 210, 27, 135, 174, 82, 143, 
//ab hier neu:
91, 150, 129, 196, 200, 160, 22, 247, 51, 151, 6, 200, 136, 206, 35, 229, 253, 2, 90, 14, 131, 208, 17, 131, 129, 144, 67, 82, 163, 127, 80, 3, 194, 124, 160, 149, 52, 216, 153, 217, 23, 235, 127, 150, 89, 114, 51, 255, 143, 237, 7, 105, 226, 128, 255, 80, 166, 7, 54, 17, 97, 101, 92, 237, 76, 73, 99, 52, 160, 215, 219, 183, 56, 2, 158, 215, 87, 144, 189, 212, 145, 246, 214, 47, 62, 153, 69, 71, 225, 42, 211, 128, 107, 21, 218, 153, 90, 66, 1, 13, 251,

:P morgen zeig ich code ^^
35 sek zum knacken gebraucht und nur 33 Werte von deinen 100 benutzt (weniger gingen bestimmt auch) !

Mathematiker - Mi 18.09.13 08:32

Hallo,
es war ein typischer Denkfehler meinerseits. Man muss ja nicht alle Glieder speichern. Es genügt, wenn man die erste Zufallszahl prüft und nur bei Gleichheit die restlichen Zahlen.
Meine Lösung:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:

var i,x,r,test:integer;
    zahl :array[1..110] of byte;
    k:string;
    gefunden:boolean;
begin
    randseed:=14031959;
    for i:=1 to 177 do x:=random(256);
    k:='';
    for i:=1 to 110 do
    begin
      zahl[i]:=random(256);
      k:=k+inttostr(zahl[i])+', ';
    end;
    memo1.lines.add(k);
    //-------------------
    //Randseed suchen
    //-------------------
    gefunden:=false;
    r:=0;
    repeat
       randseed:=r;
       test:=random(256);
       if test=zahl[1] then
       begin
         gefunden:=false;
         i:=2;
         while (i<=100) and (zahl[i]=random(256))
           do inc(i);
         if i=101 then gefunden:=true;
       end;
       inc(r);
     until gefunden;
     memo1.lines.add('Randseed = '+inttostr(r-1));
     //Kontrolle
     randseed:=r-1;
     k:='';
     for i:=1 to 110 do
     begin
       zahl[i]:=random(256);
       k:=k+inttostr(zahl[i])+', ';
     end;
     memo1.lines.add(k);
end;

braucht nur Bruchteile einer Sekunde und das randseed ist gefunden, selbst wenn man die Zufallszahlen nicht ab dem ersten Wert benutzt.

Beste Grüße
Mathematiker

IhopeonlyReader - Mi 18.09.13 16:30

Mein Quelltext war:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

var T: TDateTime;
    C: Int64;
    S: Integer;
    W: Byte;
    H: Cardinal;
    F: Boolean;
const Start = - MaxInt;
      ZF: Array[0..32] of Byte = (65, 84, 227, 44, 90, 133, 59, 140, 155, 66, 83, 10, 72, 7, 255, 163, 64, 169, 122, 162, 109, 174, 11, 139, 198, 160, 162, 218, 129, 34, 24, 245, 46);
begin
//find start seed and "last" seed
T := Now;

RandSeed := Start;
C := 0;

repeat
  S := RandSeed;
  For H:=Low(ZF) to High(ZF) do
    begin
    W := Random(256);
    F := (W=ZF[H]);
    if not F then break;
    end;
  inc(C);
until
  (RandSeed=Start) or F;

T := Now - T;
Showmessage(  'Needed Time: ' + FormatDateTime('hh:nn:ss.zzz', T) +#13#10+
              'Needed Runs: ' + IntToStr(C) +#13#10 +
              'Last Seed: ' + IntToStr(RandSeed) +#13#10+
              'StartSeed: ' + IntToStr( S ) );
end;

ZF ist das Array, wovon der Seed gefunden werden soll. Hiervon sollten 2 Bytes mindestens bekannst sein, 4 oder mehr wären gut, mehr als 10 schon wieder unnötig.

Es gibt sicherlich optimierungsmöglichkeiten, aber das war halt meine "Möglichkeit"..

P.S: Um zu verstehen warum das geht:
Aus Seed 1 wird eine Zahl gerandomed und dann springt er zu einem Seed S1 (S1 ist der Nachfolger vom Seed 1, dieser ist immer derselbe Nachfolger!)
randomed man wieder, so entsteht aus S1 S(s1) also der Nachfolger-Seed von S1

Deshalb kann man ruhig Seed 1 verwenden und die ersten 100 wegwerfen, dass wäre das gleiche als wenn man direkt bei Seed -1089172691 (der 100 Nachfolger von Seed 1) einsetzen würde.

Moderiert von Narses: Beiträge zusammengefasst

Mathematiker hat folgendes geschrieben :

Es ist hinreichend schnell und "einfach" den Seed zu finden (max. 20 sek und nur 3 bis 5 Bytes werden benötigt)

Martok - Do 19.09.13 03:20

Wozu braucht man einen Zufallsgenerator? Meistens, um Schlüssel zu erzeugen oder stochastische Verfahren zu initialisieren. Letzteres kann man schön in dem Video sehen, dass user profile icon

FinnO oben verlinkt hat. Für ersteres habe ich grade ein schön anschauliches Beispiel gefunden.

user profile icon

Gammatester hat für die Generierung der Schlüsselpaare in seiner RSA-Implementation eine Auswahl von verschiedenen kryptographischen Pseudozufallsgeneratoren (CSPRNG [http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator]) mit ziemlich großer Periode (ISAAC hat 256bit x 32bit Internal State plus 3x32bit in Zählern u.ä., im besten Fall also eine Periode von 2^8295 32bit-Werten nach Aussage [http://burtleburtle.net/bob/rand/isaacafa.html] des Erfinders) implementiert. Die müssen natürlich irgendwie geseeded werden. Das passiert mit Daten aus dem Delphi-eigenen Random().

Delphi verwendet einen einfachen Kongruenzgenerator. Falls jemand das Modulo sucht: Der 32bit-Überlauf ist das.

Aus Assembler rückübersetzt:

1:
2:

RandSeed:= RandSeed * $08088405 + 1;
Result:= (range * RandSeed) div 2^32;

In FPC wird ein Mersenne-Twister MT19937 verwendet. Aber auch dort ist nur ein Seed von 32bit drin. Die Periode ist lang, aber der Startwert ist begrenzt.

Und da geht das Problem los.
Es gibt also maximal 2^32 Startwerte. Damit ist auch maximal so viele Ketten, die den zweiten Zufallsgenerator initialisieren. Und da nicht alle davon in einer Zahl resultieren, die aus exakt 2 Primzahlen besteht, werden das nochmal weniger und mit etwas Freizeit kann man alle denkbaren Schlüssel vorberechnen und braucht dann nicht mehr den diskreten Logarithmus von sehr großen Zahlen lösen, was ein schweres Problem ist, sondern nur noch in einer Tabelle mit nur einigen hunderttausend bis Millionen Einträgen nachsehen. Das ist nur eine Frage davon wie viele Festplatten man kaufen will.

Das wird besser wenn man irgendwo 64bit herbekommt, da das immerhin die Tabelle aufbläst. Ohne echte Entropiequelle wird das aber nicht grundsätzlich anders.

Anmerkung: user profile icon

Gammatester hat nicht wirklich was falsch gemacht, bitte nicht falsch verstehen. Vielleicht hab ich auch nur irgendwo eine spezielle Funktion übersehen (die zum Entropie hinzufügen kenne ich), und wenn man sowas verwendet sollte man eh immer drüber nachdenken. Das ist meine Aufgabe als derjenige, der irgendwas damit baut. War nur grade so ein schönes Beispiel, dass eben meistens nicht das Verfahren sondern die konkrete Implementation angreifbar ist.

Edit: Blödsinn nach Hinweis reduziert

Gammatester - Do 19.09.13 12:15

Martok hat folgendes geschrieben :

Gammatester hat für die Generierung der Schlüsselpaare in seiner RSA-Implementation eine Auswahl von verschiedenen kryptographischen Pseudozufallsgeneratoren (CSPRNG [http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator]) mit ziemlich großer Periode (ISAAC hat 256bit Internal State, also im besten Fall eine Periode von 2^256; falls die Mischung perfekt ist) implementiert. Die müssen natürlich irgendwie geseeded werden. Das passiert mit Daten aus dem Delphi-eigenen Random().

Ich weiß nicht, woher Du die maximale Periode von 2^256 hast, Bob Jenkins [http://burtleburtle.net/bob/rand/isaacafa.html] (der Entwickler von ISAAC) gibt eine durchschnittliche Periode von 2^8295 an, und der InternalState hat 8192 Bits. Weiter ist die Verwendung von isaac_init0 nur eine von drei Seeding-Methoden, ja diese verwendet randomize und random, die Basis-Init-Routine isaac_inita verwendet 8192 Bits.

In MPArith/RSA wird zusätzlich noch der TSC verwendet (falls vorhanden und gewünscht). Und das zeigt ein Problem von solchen Bibliotheken: Sie sollen mit vielen Compilern, Betriebssystemen und Hardware laufen, die unterschiedliche Vorraussetzungen mitbringen: Linux und BSD liefern /dev/(u)random, Windows hat CryptGenRandom etc. Ob man den trauen kann ist wieder eine andere Frage. Hashen von willkürlichen Mausbewegungen, Tastaturevents ... ist eine weitere Möglichkeit; ist allerdings bei Embedded-Systemen nicht möglich usw.

Martok - Do 19.09.13 17:03

Gammatester hat folgendes geschrieben :

Ich weiß nicht, woher Du die maximale Periode von 2^256 hast

Äh, ich bin doof, ist doch klar ;)
"256 four-octet integers" schreibt die Wikipedia. Eher unübliche Einheit, da hab ich bei jedem mal Lesen gleich 256bit draus gemacht...

Gammatester hat folgendes geschrieben :

In MPArith/RSA wird zusätzlich noch der TSC verwendet (falls vorhanden und gewünscht).

Ah, das war also dieser seltsame Assembler. Hättest ja wenigstens mal RDTSC drankommentieren können ;)

Gammatester hat folgendes geschrieben :

Weiter ist die Verwendung von isaac_init0 nur eine von drei Seeding-Methoden, ja diese verwendet randomize und random, die Basis-Init-Routine isaac_inita verwendet 8192 Bits.

Es ist die, die man standardmäßig bekommt, wenn man den Debugmodus deaktiviert, das meinte ich. Klar, Entropie selber generieren und da reinfüttern ist natürlich möglich.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!