|
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 02:53 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz