|
Wie zufällig ist Random(x)?
Eigentlich ist doch alles recht logisch in der Programmierung, doch eine Funktion die irgendeine Zahl zurück geben soll ist doch eigentlich absolut untypisch.
Wie würdet ihr Random nachschreiben (hätte da leichte Probleme sowas unlogisches zu coden :roll: )? Falls ihr was habt, wie zufällig ist diese Zahl dann. Oder gibt es dann immer noch Zahlen die öfter vorkommen als andere? Wie schauts mit Random aus, absolut zufällig oder bedarf es einer neuen Version? :mrgreen: |
Re: Wie zufällig ist Random(x)?
Darüber habe ich auch schon oft nachgedacht.
Wie zufällig ist zufällig? Irgendwie muss der Computer ja auch "zufällige" Zahlen berechnen. Aber nach welchem Schema oder nach welchem Verfahren? MfG Florian :hi: |
Re: Wie zufällig ist Random(x)?
eine möglichkeit von vielen ist das rauschen einer diode ( mit einer elektronischen schaltung ) zu digitalisieren und dadurch die gewünschten zufallszahlen zu erzeugen
könnte vielleicht in der FPU stecken oder sonstwo im prozessor.. weil auf rein programmiertechnischer weise lässt sich das wohl nicht "zufällig genug" lösen.. gibt ja immerhin sehr viele security algorithmen die darauf aufsetzen und dadurch sicher sein müssen.. ja es gibt auch extra hardware die noch zufälligere und sichere zufallszahlen erzeugt.. aber das is eher was für bank servern und hochsicherheits anwendungen wie das im pc haargenau funzt kann ich nur vermuten |
Re: Wie zufällig ist Random(x)?
Letzten Endes kann ein Computer nur pseudozufällige Zahlen liefern die, so man das Verfahren + Startwert/Randbedingungen kennt, völlig deterministisch sind. Das ist nun mal prinzipbedingt (auch wenn man hier und da mal meint ein PC hätte mehr mit Unlogik zu tun als anders herum ;))
Soweit ich das beurteilen kann liefert die Random-Funktion in Delphi eine sehr homogene Verteilung der Werte (bei scheinbar beliebigen Mengen an generierten Werten), und erweckt einen sehr guten Anschein von Zufälligkeit. Das Verfahren ist imho auch nicht wirklich trivial und ist schon eine ordentliche Denkleistung gewesen (es hat auch glaube ich einen Namen - der mir aber leider entfallen ist...) Mich persönlich dürstet es nicht unbedingt nach Ersatz, wobei es aber niemals schaden kann die Wahl zu haben :) gruss, dizzy \\edit: Diodenrauschen ist eine schöne Sache, da es sich meine ich um einen Quanteneffekt handelt (jede elektrische Leitung rauscht immer und minimal dadurch). Das wäre dann nur noch seeeehr seeeehr schlecht vorhersehbar ;) (Bleibt generell die Frage: Wie "zufällig" kann überhaupt etwas sein? Aber nu, ist ja kein Philosophie-Forum hier :D) |
Re: Wie zufällig ist Random(x)?
Dann stellt sich mir aber doch die (philosophische) Frage ob es überhaupt Zufälle gibt.
Seit Newton wissen wir, dass actio = reactio gilt. Demzufolge gibt es keine Zufälle oder die Zufälle sind Reaktionen auf Ereignisse... Oder? MfG Florian :hi: [edit] Jetzt editiert der da noch meine Frage mit rein... :roll: [/edit] |
Re: Wie zufällig ist Random(x)?
Zitat:
Aber die Frage zwang sich einem so schön auf *g* |
Re: Wie zufällig ist Random(x)?
Wie Zufallszahlen generiert werden steht
 hier ausführlichst. Sie werden kompliziert mathematisch berechnet und weisen nach genügend langer Ausführungszeit eine gewisse Regelmäßigkeit auf. Sie werden auch Pseudozufallszahlen (siehe wikipedia) genannt da sie durch einen determinantischen Algorithmus generiert werden (siehe wikipedia).Es gibt jedoch neuerdings eine PCI-Steckkarte, die Zufallszahlen generieren kann. Dabei werden Photonen durch ein halb-durchlässiges Plättchen (keine Ahnung welcher Stoff) geschossen. Da aus einer Lichtquelle die Photonen zufällig austreten, bedeutet dies dass die Zufallszahl einzigartig und nicht linear ist. Der Auftreffpunkt ist die Zufallszahl (wenn ich mich richtig erinnere). Wurde mal bei Heise gepostet, ich finde den Link aber nicht mehr. Eine weitere interessante Sache ist Quantenkryptographie. Siehe hier.So ich hoffe ich konnte Licht ins Dunkel bringen ;) Hab mir auch viel Mühe geben ^^ |
Re: Wie zufällig ist Random(x)?
also ich weiß nur das sich delphi beim zufall die Uhrzeit zu hilfe nimmt
|
Re: Wie zufällig ist Random(x)?
Wobei GetTickCount auch wieder ungenau wäre, das geht ja nur auf 5 ms.
Und wenn man schnell hintereinander die random-funktion aufruft und die mit GetTickCount funktioniert, ist es auch wieder nicht mehr so zufällig. Ich glaube aber auch nicht, dass sie das mit QueryPerformanceCounter gemacht haben...aber irgendwie sind die Zahlen dann doch zufällig :stupid: |
Re: Wie zufällig ist Random(x)?
Hallo!
Zitat:
Die Funktion "Random" berechnet den nächsten Wert aus der globalen Variablen "RandSeed". Bei gleichem Wert von RandSeed und gleichem Wertebereich kommt immer dasselbe heraus! Die Prozedur "Randomize" setzt RandSeed auf einen aus der Uhrzeit stammenden Wert. Folge: Randomize vor jedem Random erzeugt bei hinreichend schnellem Aufruf mehrfach dieselbe Zahl (Uhrzeit hat sich zwischen den Aufrufen nicht geändert). Das manuelle Setzen von RandSeed vor den Randoms auf einen festen Wert ergibt bei jedem Programmaufruf dieselbe Folge von "Zufallszahlen". Allerdings weist Borland darauf hin, daß bei späteren Delphi-Versionen die Implementierung von Randon geändert werden könnte, so daß dann die Zahlenfolge eine andere wäre (Programm kann nicht auf neuere Versionen portiert werden). Gruß Dietmar Brüggendiek |
Re: Wie zufällig ist Random(x)?
Zufallszahlen die mit random() erzeugt wurden sind nicht zufällig. D.h. jede einzelne und sequentiell erzeugte Zahl ist überhaupt nicht zufällig, sondern musste exakt beim aktuellen Aufruf von Random() berechnet werden.
ABER, um diese "Zufälligkeit" geht es im Grunde garnicht, es ist sogar gut so. Das was Random() mathematisch machen soll ist das es nichtzufällige Zahlen produziert deren statistische Verteilung/Wahrscheinlichkeit, ihre Häufigkeit und ihr Auftauchen, eben einer Zufallsverteilung entspricht. Die erzeugten Zahlen sind also keinesweigs zufällig, aber eine beliebige Menge von Zahlen die mit Random() erzeugt wurden, sollte immer nach Zufall aussehen. Die statistischen Eigenschaften der Menge sollte dem Zufall entsprechen. Es gibt aber auch Hardware Generatoren, sei es als extra Hardware oder über das Internet. Im WEB gibt es einfachste API's per HTTP um eine Anzahl von Zufallsbits bei bestimmten Servern abzufragen. Meistens wurden diese per radioaktivem Zerfall erzeugt. Wir kommen damit auch zum Problem der Hardware-Generatoren. Ja, sie basieren auf angeblich zufälligen Ereignissen, wie dem Rauschen einer Diode oder dem Zerfall radioaktiver Elemente. Das Problem dabei ist aber das das nur per Axiom, also physikalischen Beobachtungen, ABER NICHT durch mathematische Beweise exakt als Zufällig bewiesen wurde. Deshalb gilt in den meisten Anwendung das ein guter Pseudo-Zufallsgenerator, mit exakt nachvollziehbaren mathematischen Eigenschaften, JEDEM Hardware-Zufalls-Generator vorzuziehen ist. D.h. obwohl Random() eben NICHT zufällig Zahlen produziert, ist das besser als echt zufällige Zahlen zu benutzen. Der Algorithmus von Random() kann ganz exakt mathematisch bewiesen werden, und mit den entsprechenden Parametern kannst du dir 100%tig sicher sein das die durch Random() erzeugten Zahlen als Menge den Eigenschaften von Zufall entsprechen. Bei einem Hardwaregenerator stützt man sich auf angeblich = beobachtete zufällige Ereignisse. KEIN Mensch kann heutzutage den Zerfall radioaktiver Elemente oder das Rauschen einer Diode vorhersagen, aber das heist nicht das es nicht möglich wäre. Wir stützen uns also bei HW-RNG's auf physikalische Ereignisse die sich der Mensch NICHT vollständig erklären kann. Nun, für viele Anwendungen ist eine solche Basis von Zufall unerwünscht. Die Random() Funktion benutzt einen LCG = Linear Congruential Generator. Man kann Pseudo-RNG's bauen die mathematisch so beweisbar sicher sind das man als Aussenstehnder die Folge der produzierten Zahlen nur dann bestimmen kann wenn man den Startwert=Seed des RNG's kennt. Wird dieser Seed geheim gehalten, dann sind die produzierten Zahlen immer noch pseudo-zufällig, aber denoch ist die Komplexität des benutzten Algorithmus dann so hoch das kein Mensch oder Maschine in der Lage wäre eine Vorhersage der nächsten Zahlen zu machen. Der Vorteil von solchen math. Verfahren gegenüber Hardware-Generatoren, ist eben der Punkt das ALLE Eigenschaften EXAKT mathematisch beweisbar und somit die notwendigen Parameter und Schranken kalkulierbar sind. Dies ist bei HW-RNGs nicht der Fall. Philosophisch gesehen gibt es keine Zufälle, egal welche Ideologie man vertitt. In diesem Punkt sind sich Christen, Buddhisten, Marxisten usw. alle einig. Der einzigste Unterschied zwichen Pseudo-Zufall und echtem Zufall besteht in der Komplexität und unserem Wissensstand. Gruß Hagen |
Re: Wie zufällig ist Random(x)?
Meines Wissens ist die Ermittlung von Pseudozufallszahlen eine Kombination von Stephans Darstellung (komplizierter Mathe-Algo) und der Zeitnahme aus dem System.
Die Berechnung geht immer von einer bestimmten Zahl aus, um die nächste Zufallszahl zu berechnen. Bei fortlaufender Berechnung ist dies jeweils die zuletzt ermittelte Zufallszahl. Die Zeit spielt hierbei nur beim Start des Algorithmus eine Rolle. Sie stellt nämlich die Zahl bereit, mit der das Ganze losgeht. Deswegen kommt (kam?) ohne Randomize auch immer die gleiche Folge von Zufallszahlen bei raus. Niels |
Re: Wie zufällig ist Random(x)?
Zitat:
|
Re: Wie zufällig ist Random(x)?
wie schon gesagt wurde: es wird mit hilfe der Uhrzeit und Datum gemacht. Allerdings nur wenn man vorher randomize; eingegeben hat(egal wo, es muss nur audgeführt werden(am besten in Form.Create))
ich hab mal in einem php-buch gelesen, wenn man etwas mit session ids machen möchte kann man anstatt sessid() auch random benutzen, weil das sich auf die zeit und das datum des servers bezieht und somit diese zahl/code eindeutig ist(die uhrzeit steht nicht drin, aber angeblich kommt diese Zahl/string nicht noch einmal vor) |
Re: Wie zufällig ist Random(x)?
Hallo zusammen,
Ich hatte bei meiner schriftlichen Matura (Abi) unter anderem die Aufgabe auf einem C167-Controler einen Würfel zu realisieren. Ich habs so gemacht, dass ich mit einem Taster einen digitalen Eingang angesteuert habe. Ab der steigenden Flanke hab ich begonnen die Zeit zu zählen, bis der Taster wieder losgelassen wurde. Ne Modulo-Operation drüber, um auf 1-6 zu kommen und fertig war der pseudozufällige Würfel. Ähnlich wirds vermutlich hier auch laufen. Außer der Zeit muss sich nichts ändern. grüße, daniel |
Re: Wie zufällig ist Random(x)?
Zitat:
|
Re: Wie zufällig ist Random(x)?
Dann hab ich nix gesagt. :oops:
Ich dacht halt, das das was damit zu tun haben könnte. |
Re: Wie zufällig ist Random(x)?
Meines wissens nach wird die Random(x) Funktion über eine Mathematische Formel berechnet, die aber immer bei 0 startet. Das hat zur Folge, dass man unter umständen (zB bei Timer Einsatz) immer die gleichen Zahlen erhält.
Ich nutze inzwischen immer die Randomize(x) Funktion Da startet es immer bei einer anderen Zahl... Gruß Thomas |
Re: Wie zufällig ist Random(x)?
Zitat:
Ich verwende immer randomize und danach random(x), deine Funktion kennt Delphi su aich nicht. ;) |
Re: Wie zufällig ist Random(x)?
Ich habe einmal ein Lotto spiel in delphi (3 glaub ich) programmiert und je nach tag und uhrzeit kamen da manche zahlen häufiger vor als andere , manche soager nur ein bis zweimal in mehreren tausend durchgängen
MfG tn249 |
Re: Wie zufällig ist Random(x)?
Zitat:
http://og4all.de/s.jpg, sCrAPt |
Re: Wie zufällig ist Random(x)?
Liste der Anhänge anzeigen (Anzahl: 1)
Und genau um das zu testen habe ich mal vor langer Zeit ein kleines Prog angefangen...
Im Edit-Feld gibt man an wieviele Zahlen erstellt werden sollen und dann kann man grafisch sehen wie viel besser Delphi mit den einzelnen Durchläufen wird! Eigentlich war das Ergebniss natürlich klar aber da ich es gemacht hab kann ichs ja mal zeigen... :zwinker: P.S: Speichern und Laden is egal... wollte mehrere Messreihen machen und habs dann sein lassen... |
Re: Wie zufällig ist Random(x)?
Es gibt eine echte Quelle von Echten Zufallszahlen, und das ist
Random.org, der zum Beispiel per SOAP abgefragt werden kann.Hier wird live das atmosphärische Rauschen aufgenommen (ihr wisst schon... Radio auf irgendeine Frequenz einstellen auf der nicht gesendet wird, das Rauschen ganze Ding aufzeichnen und in einen Bitstream umwandeln - reine Entropie und die ist wirklich Zufällig). Dieser Bitstream wird dann hergenommen und daraus die Zufallszahlen ermittelt. Nachtrag: Als Beispiel wurde ein 1MB grosses File genommen, das aus diesen Zufallswerten bestand. Eine optimale Kompression konnte das Megabyte um kein einziges Bit verkleinern, will heissen es gab keine Wiederholungen, die komprimierbar gewesen wären. |
Re: Wie zufällig ist Random(x)?
Zitat:
Der Zufall hat keine Erinnerungen, deshalb hätten ja eigentlich auch 400 Einsen hintereinanderer kommen können :roll: http://og4all.de/s.jpg, sCrAPt |
Re: Wie zufällig ist Random(x)?
@Phoenix,
und da haben wir es schon, unser Problem mit den HW-RNGs. Denn exakt zu dem Zeitpunkt wo ich bei Random.org meinen Zufall abfrage um meine hochgeheimen Schlüssel zu produzieren, fängt gleich neben dem Rausch-Empfänger ein Radiosender an zu senden. Und das genau auf der Frequenz auf der der HW-RNG von Random.org läuft. Das Problem für Random.org ist aber jetzt zu unterscheiden ob der gelieferte Zufall tatsächlich noch Zufall ist. Denn bei echtem Zufall ist es durchaus statistisch wahrscheinlich das eine 10 Stunden Folge von 0101010 Bits erzeugt wird. Und wieder das Problem mit den HW-RNGs, der Beweis das die Zufallsfolgen die ein HW-RNG produziert auch tatsächlich echte Zufallsfolgen sind ist nicht durchführbar. Eben exakt dadurch das für HW-RNGs Sensoren benutzt werden die auf physikalischen Ereignissen beruhen die der Mensch bis heute nicht mathematisch als nicht zufällig beweisen kann. Man nimmt eben einfach an das das Hintergrundrauschen auf leeren Frequenzbändern zufällig ist, aber man kann es nicht beweisen das es so ist. Oder anders gesagt: weil ich nicht weis das es keinen Gott gibt nehmen wir an es gäbe ihn. Weil für uns Menschen in den physikalischen Prozessen, wie Photonenaustritt, keine mathematische Regelmäßigkeit zu entdenken wa, nehmen wir einfach mal an das das alles zufällig ist. Nur, es könnte trotzdem eine Regelmäßigkeit geben die wir eben nicht verstehen ! Und das ist eben keine sichere Grundlage um behaupten zu können das HW-RNGs echten Zufall produzieren. Nochmal: jeder mathematische Pseudozufallsgenerator der eine bestimmte Komplexität in seinen mathematischen Verfahren überschreitet ist definitiv beweisbar zufällig. Denn aus Sicht desjenigen der den Startwert/Paramter dieses PRNG nicht kennt, sind die produzierten Zufallsfolgen in keinster weise berechnenbar und demnach zufällig. Er kann nur eine Aussage über diesen PRNG treffen : "das nächste Bit ist mit einer Wahrscheinlichkeit von exakt 50% eine 0 oder eine 1". Diese Aussage beschreibt den perfekten Zufallsgenerator. Man muß also die Parameter/Seeds/Algos. des benutzten PRNGs nur so hoch schrauben das mit der heutigen Technik und dem heutigen Wissen es unmöglich wird ohne diese Paramater den Zufallsstrom vorherzusagen. Wir haben dann eine Pseudozufallsgenerator der für jeden nicht eingeweihten absolut zufällig sein muß, und nur für diejenigen die die Parameter kennen vorhersagbar ist. Bewegt man sich in diesem Bereich so bewegt man sich nicht mehr auf dünnem Eis, sondern im Bereich der absolutistischen Mathematik. Man kann also mit absoluter Bestimmtheit die Qualität und Sicherheit der erzeugten Zufallsdaten voraus berechnen. Fazit: Pseudo-Zufallsgeneratoren sind, wenn man die richtigen Algos/Paramater benutzt, immer wesentlich besser als jede Hardware Lösung. Gruß Hagen |
Re: Wie zufällig ist Random(x)?
Liste der Anhänge anzeigen (Anzahl: 1)
Diese Pseudozufallsgeneratoren (wie z.B. in Delphi) sind meines Wissens auch noch ein bissl optimiert - in wirklich keit währe es ja möglich viele male hintereinander den selben Wert zu erreichen, was ja nicht der Fall ist, ausserdem sind diese so gemacht, das die Werte schön verteilt sind (was bei atreju2oo0's Programm nicht so auffällt, bei den wenigen Werten kommt es auch mal vor, das es einen/zwei... Wert(e) nicht gibt) .......
also wenn man mal ein paar mehr Werte nimmt (siehe Anhang), dann sollte auch die vorher schonmal gestellte Frage, über die Quallität der Verteilung der Zufallszahlen erledigt sein. Da ja "fast" eine schöne Linie rauskommt, sollten die Werte wohl auch schön verteilt sein ^^ |
Re: Wie zufällig ist Random(x)?
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. Natürlich... sollte morgen jemand morgen auf die Weltformel stossen und damit nachweisen können, das Entropie berechenbar ist, oder sollte jemand morgen die Heisenberg'sche Unschärferelation kippen, dann sind die Zufallszahlen berechenbar und auch die Quantenkryptographie unsicher - aber solange das nicht passiert sind wir mit diesen Lösungen auf jeden Fall besser bedient als durch irgendeine nachgeahmte Methode, die eben gar nichts mit Zufall gemeinsam hat. |
Re: Wie zufällig ist Random(x)?
Also für Verschlüsslungstechniken sollte doch der "Zufall" berechenbar sein, den beide Seiten müssten ja die Selbe Zahlenfolge besitzen (der eine für's ver- und der andere für's entschlüsseln)
|
Re: Wie zufällig ist Random(x)?
Zitat:
Was mir noch aufgefallen ist: zufällig bedeutet "nur" keine Vorhersagbarkeit, hat aber überhaubt nix mit einer Gleichverteilung zu tun! Und wenn die Radiostation anfängt zu senden und das Hintergrundrauschen stört ist das ja auch Zufall - schließlich kann keiner vorraussagen wie die Wellen bei mir ankommen. |
Re: Wie zufällig ist Random(x)?
Zitat:
Nehmen wir das Beispiel mit einem perfekten Würfel auf einer Ebene, der aus einer bestimmten Höhe ohne äussere Einflüsse aus immer gleicher Position fallen gelassen wird: Auch dieser springt zufällig umher. Dennoch ist die Chance auf eine seiner Seiten zu fallen genau 1/6tel, und demnach werden alle 6 Ziffern bei ausreichend häufiger Wiederholung in etwa gleich oft auftauchen. Das ist einfach ein Phänomen, das wir dabei bisher immer beobachtet haben, bei einer entsprechenden Quelle von Zufall werden wir dies aller Wahrscheinlichkeit nach auch dort beobachten können. |
Re: Wie zufällig ist Random(x)?
Zitat:
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:
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:
Gruß hagen
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; |
Re: Wie zufällig ist Random(x)?
Ich sehe da immer noch ein Problem:
Da der Algorithmus bekannt ist, nur die Eingangswerte unbekannt sind, aber die erzeugte Folge wiederum bekannt ist, kann man früher oder später als 'Unwissender' dennoch mit steigender Anzahl der berechneten Bits den Seed errechnen, ausser man verwendet eine Mathematisch nicht-umkehrbare Funktion (was auch beweisen sein muss), oder aber man verwendet eine Brute-Force Attacke und sieht nach wann die erzeugten Reihen identisch sind. Diese Möglichkeit besteht nicht, wenn man z.B. das Hintergrundrauschen eines Radioteleskopes als binäre Signalquelle hernimmt. Egal wie lang eine hieraus ausgelesene Folge ist, niemand wird langfristig dazu in der Lage sein, aus der bekannten Folge irgendwie auf die zukünftigen Werte zu schliessen, da deren Herkunft nicht in unserem Einflussbereich liegt und wir auch nicht gucken können, was denn die Entstehung dieser 'Werte' beeinflusst hat, weil uns diese Information auch frühestens in dem Moment erreicht, wie das Quellsignal bei uns ankommt. Im ersteren Fall wird es früher oder später für jeden möglich sein, mit 100%iger Genauigkeit vorherzusagen, ob das nächste Bit 1 oder 0 ist, im zweiten Falle ist dies tatsächlich unmöglich, da wir nach dem heutigen Stand der Physik vor dem Zeitpunkt der Erzeugung gar nicht über die notwendigen Informationen verfügen könnten, die uns eine Berechnung vielleicht ermöglichen könnte. Dies bedeutet wiederum, das sich die Folge vielleicht irgendwann berechnen lassen können wird, aber nur aufgrund von Daten, über die wir einfach nicht rechtzeitig verfügen können. Unter diesen Umständen ist es wiederum nur möglich, eine Aussage mit 50% Genauigkeit zu machen. Was ja unser Ziel ist. |
Re: Wie zufällig ist Random(x)?
Zitat:
BTW: Das 1<>0 ist, ist eine Definition... definitionen zu beweisen ist nicht sinnvoll :-) |
Re: Wie zufällig ist Random(x)?
[offTopic]
Zitat:
Axiome sind nicht zu beweisen... Definitionen die Aussagen enthalten müssen auch nachweisbar sein. Zum Beispiel gibt es ja auch für Primzahlen eine Aussage(keinen Teiler) die für die Zahl bewiesen werden muss. Wenn ich mich richtig entsinne ist das der Beweis für die unterschiedlichkeit von neutralen Elementen bezgl. Adition und Multiplikation... :gruebel: [/offtopic] |
Re: Wie zufällig ist Random(x)?
Zitat:
Korrekt, und genau darum geing es mir die ganze Zeit. Hast du schon mal ausgerechent welche Periode ein BBS mit den obigen Primzahlen a 1024 Bits hat ?? Jo, du kannst damit 2^2048 Bits am Stück produzieren OHNE Widerholung. Das schöne am BBS ist das er VOLLSTÄNDIG mathemtisch analysiert und bewiesen wurde. JEDE Eigenschaft, sei es statistische Verteilung der Bits oder Sicherheit des Verfahrens wurde durch die Erfinder/Entdecker Blum, Blum und Shub mathematisch korrekt bewiesen. Bei unbekannten P,Q,R bleibt nur eine Möglichkeit, nämlich eine Brute Force Attacke. Nungut, dann viel Spaß beim Knacken von einem 2048 Bit Schlüssel. Und wenn du diesen dann in 1 Mio Jahren hast, erzeuge ich mal eben in 5 Minuten den nächsten 4196 Bit Schlüssel zum knacken für dich. Das ist Sicherheit, denn ich kann aufbauend auf mathematischem Wissen die Schranken so hoch setzen das dieser PRNG für dich ein echter Zufallsgenerator ist. Einen Bitstrom der damit produziert wird kannst du NIEMALS in vertretbarer Zeit als PRNG Zufall identifizieren, für dich IST es echter Zufall. Nur ich wiederum kann dies dir mathematisch beweisen. Dafür kannst du mir aber nicht beweisen das der Zufall eines HW-RNG auch tatsächlich zufällig ist, selbst der Beweis das der HW-RNG nur Pseudozufällig ist ist für dich unmöglich. Gut dann behaupte ich mal das alle HW-RNGs garkeinen Zufall produzieren sondern nur Funktionswerte ausspucken die durch so komplizierte physikalische Prozesse und den dahinter stehenden mathematischen Formeln erzeugt wurden das wir diese heute noch nicht kennen. Du kannst es drehen wie du willst: entweder glaubst du an Gott,und somit hat Gott den Zufall erschaffen, sprich der Zufall ist nicht zufällig, oder aber du glaubst an die Mathematik und somit muß alles nicht-zufällig sein. Die Heisenberg Theorie hat damit rein garnichts zu tun, denn sie besagt nur das der Beobachter nur durch seine Beobachtungen selber in das System eingreift und somit niemals in der Lage ist die realen Verhältnisse im System zu beobachten. Man muß also zwangsläufig an eine Grenze stoßen ab der uns immer was verborgen bleibt. Das bedeutet aber nicht das hinter dieser Grenze die Gültigkeit der Mathematik erlischt, oder Zufall echt zufällig ist und nicht mehr dem Ursache Wirkung Prinzip unterliegt, oder das diese Grenze tatsächlich absolut ist, oder das man nicht analytisch das System denoch erkennen und beweisen kann. Das muß alles noch bewiesen werden. Heisenberg beschreibt in seinen Thesen primär erstmal nur ein physikalisches Phenomän aber kein analytisches. Und weil dies alles schon reine und unbeweisbare philosophie ist, auf der aber die HW-RNGs schlußendlich aufbauen, vertrete ich die gleiche Meinung wie viele Krypto-Experten und Mathematiker, gute PRNGs mit groß gewählter Komplexität sind besser als HW-RNGs. Weil sie eben geschlossene Systeme sind die wir nicht als reine Beobachter analysieren sondern als Konstrukteure exakt erschaffen haben ! Angenommen wir benutzen das Rauschen einer Diode als HW-RNG. Nun halte ich aber ein Feuerzeug dran und pfutsch ist der Zufall, da sich die elektischen Kenndaten verändern. Wie willst du aber einen Zufallsstom der durch ein so defektiöses System erzeugt wurde als falschen Zufall erkennen ?? Ein PRNG dagegen ist überprüfbar weil der Algorithmus überprüfbar ist. Ich benötige nur den Seed +Primzahlen und kann 1 zu 1 die gleiche Zufallssequenz auf anderer Hardware reproduzieren und somit verifizieren. Natürlich habe ICH dann die Wahl wem ich diese Überprüfung gestatte, denn ich besitze die Schlüssel die das mathematische Problem im konkreten lösbar machen. Für alle anderen ist es echter Zufall und die Komplexität ist so hoch das keiner mit dem heutigen Wissen in der Lage wäre das Gegenteil zu beweisen. Sogesehen machen diese Personen das gleiche wie bei HW-RNGs, sie glauben aber wissen nicht ob es nun echter oder künstlicher Zufall ist. Sobald du aber die Umweltbedinungen und physikalischen Vorgänge beim Rauschen einer Diode exakt kennst und manipulieren kannst, gelingt dir diese Reproduktion der durch diesen HW-RNG erzeugten Zufallsdaten auf anderen Systemen. Dies ist eine logische Konsequenz. Die erzeugten Zufallsbits sind denoch statistisch gesehen sogut wie jeder andere "echte" Zufall. Warum sollte man sich auf Techniken verlassen die noch garnicht 100%tig erklärbar sind wenn man ähnliche Techniken kennt die genauso gut sind aber durch uns selber 100%'tig verstanden, reproduzierbar und beweisbar sind ? Das ist die Frage auf die ich hinweisen wollte. Sozusagen die Kernaussage: Pseudo-Zufall ist garnicht so schlecht, er ermöglicht Eigenschaften die kein Hardware Generator jemals garantieren kann. Sie funktioneren sicher weil sie reproduzierbar sind. Gruß hagen |
Re: Wie zufällig ist Random(x)?
Zitat:
Gruß Hagen |
Re: Wie zufällig ist Random(x)?
Zitat:
Und genau das kann man durch PRNGs 100%'tig verhindern, den sie arbeiten deterministisch auf deterministischen Systemen. Und wenn ich mir nicht sicher bin dann geben ich ein zweites mal auf einem anderen Rechner die gleichen Startwerte ein und MUSS dann den gleichen Zufall erzeugen. Beim Zufall geht es im Grunde wirklioch nur darum das er unverhersehbar ist. Das ist das Ziel, der Weg dahin kann unsicher und unbeweisbar sein oder aber eben deterministisch konstruiert aber von so hoher Komplexität das er nur für die authorisierten Personen reproduzierbar und somit auch erkennbar nicht zufällig ist. Puh, wie soll ich euch denn noch überzeugen ;)? Ok, ich gebe zu auch ich musste das PostScript aus dem ich das gelernt habe mehrmals lesen. Gruß Hagen |
Re: Wie zufällig ist Random(x)?
Zitat:
Zitat:
Du kannst es drehen und wenden wie du willst, das das Gesamtsystem nicht geschlossen ist und nicht durch uns konstruiert wurde können wie nie zu 100% sicher sein, wir müssen als glauben das HW-RNGs Zufall produzieren wir wissen es aber nicht. Somit kannst du auch nie beweisen das eine Machine die ja als Hardware Zufall produizert nicht irgendwo einen fehler enthält. Was dazu führen würde das der durch sie garantierte Zufall keiner mehr ist. Lange Zeit schreiten die Sicherheits-Dealer wie Banken etc. nach HW-RNGs auf Kryptographischer hardware, wie zB. der Geldkarte. Mittlerweile ist man wieder davon abgekommen da es dem Hersteller nicht möglich war eine Schnittstelle anzubieten die es ermöglicht die korrekte Funktion dieser HW-RNGs von aussen zu verifizieren. Es geht auch garnicht. Somit wurden wieder PRNGs eingeführt deren Komplexität so hoch ist das keiner ohne die Schlüssel sie vorhersagen kann. Der Hardwarehersteller musste dann nur die Möglichkeit schaffen das eine Hardwarelösung ohne Sicherheitsverluste ihren PRNG mit einer anderen Hardware synchroniseieren kann. Nach diesem Schritt kann also ohne Sicherheitseinbusen 100%'tig verifiziert werden das die Hardware auch ohne physikalicher Prüfungen einwandfrei funktioniert. Gruß Hagen |
Re: Wie zufällig ist Random(x)?
Zitat:
Das gute alte Doppelspaltexperiment zum thema Welle/Teilchen-Dualismus könnte man dafür hernehmen. Man nehme einen Photonenemiter (oder Elektronen, Protonen, bzw. alles andere was klein und schnell ist ;) ), der immer nur ein Photon auf einmal herauslässt. Trifft dieses Photon auf den Doppelspalt, ist es absolut unvorhersehbar durch welche Seite es "schlüpft". Das arme Teilchen weiß es ja noch nicht einmal selbst. ;) Links ist 0 rechts ist 1 -> wiederhole das 1024-mal und du hast ein absolut zufälliges KiloByte. :mrgreen: |
Re: Wie zufällig ist Random(x)?
Guter Einwand, wenn mich aber nicht alles täuscht hat man herausgefunden das dieses EINE Photon durch BEIDE Schlitze schlüpft. Im Raum Zeit Gefüge exitiert angeblich ein Zwilling dieses Photons mit entgegengesetzem Drift.
Nun laufen schon Experimente wie man damit Informationen in Echtzeit über große Distanzen übertragen kann, denn man hat zudem noch festgestellt das der Drift den man bei einem Photon verändert dazu führt das sich der Drift des Zwillings ebenfalls ändert. Aber auf alle Fälle so es durch beide Schlitze gleichzeitg gehen, bzw. dessen Zwilling aus dem Nichts auftauchen. Andere wiederum behaupten das Heisenberg sein Spaß mit deisem Problem hat. Allerdings, das geht weit über meine Begriffe hinaus. Ich habe nur mal, ich glaube PM (schlagt micht nicht :)) darüber gelesen. Gruß Hagen |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 05:43 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz