Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Algorithmen, Datenstrukturen und Klassendesign (https://www.delphipraxis.net/78-algorithmen-datenstrukturen-und-klassendesign/)
-   -   Noise XOR Signal = Noise? (https://www.delphipraxis.net/181065-noise-xor-signal-%3D-noise.html)

sx2008 12. Jul 2014 00:05

Noise XOR Signal = Noise?
 
Ich habe mal eine eher theoretische Frage.
Angenommen man hat einen guten Zufallsgenerator der einen Strom von zufälligen Bytes liefert.
Dann hat man einen Signalgenerator der eine frei wählbare Bytefolge liefert.
Die beiden Bytefolgen werden mit XOR verknüpft und das Ergebnis wird analysiert.
Man kann den Signalgenerator auch abschalten; dann wird immer Noise XOR $00 berechnet was natürlich genau
dem Ausgang des Zufallsgenerators entspricht.

Kann man an dem Ergebnis irgendwie erkennen, ob gerade der Signalgenerator an oder aus ist?
Oder anderst gefragt: kann man ein Signal erzeugen, dass sich messbar gegen das Rauschen des Zufallsgenerator absetzen kann?

BUG 12. Jul 2014 00:52

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von sx2008 (Beitrag 1265291)
Kann man an dem Ergebnis irgendwie erkennen, ob gerade der Signalgenerator an oder aus ist?

Bei einer 50% Chance für das Zufallsbit sollte man das nicht erkennen können. Stromverschlüsselungen basieren darauf.
Du kannst dir mal einfach einen Entscheidungsbaum für ein einzelnes Bit aufzeichnen, da kann man sich das gut überlegen.

Zitat:

Zitat von sx2008 (Beitrag 1265291)
Oder anderst gefragt: kann man ein Signal erzeugen, dass sich messbar gegen das Rauschen des Zufallsgenerator absetzen kann?

Was hast du vor? :gruebel:

Phoenix 12. Jul 2014 08:41

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von sx2008 (Beitrag 1265291)
Kann man an dem Ergebnis irgendwie erkennen, ob gerade der Signalgenerator an oder aus ist?
Oder anderst gefragt: kann man ein Signal erzeugen, dass sich messbar gegen das Rauschen des Zufallsgenerator absetzen kann?

1. Ja.
2. Nein.
3. Das ist nicht Praxisrelevant. ;-)

Du kannst den reinen Zufall statistisch analysieren, und erkennen, dass es echter Zufall ist.
Du kannst den Strom des Signalgenerators statistisch analysieren und erkennen, das es kein Zufall ist.

Der Signalstrom 'verzerrt' beim XORen den Zufall, denn er wird ohne Informationsverlust in den Zufall hineingewoben. Dadurch, das der Signalstrom nicht zufällig ist, wird er zwangsläufig *irgendwann* zu messbaren Patterns im modifizierten Zufallsstrom führen.

Die Unterschiede sind allerdings sehr gering. Du wirst nur über einen *längeren* Zeitraum durch sehr aufwändige Analysen des gesamten Datenstroms herausbekommen, ob in einem Teilstrom nun ein Signal eingewoben ist oder nicht.

Da wir hier auch nur über statistische Auffälligkeiten reden wirst Du auch den Beginn oder das Ende des Einwebens nie genau ermitteln können, sondern nur auf einem definierten Teilstrom mit einer gewissen Wahrscheinlichkeit sagen können: Hier war er an, und hier nicht.


Es ist also keineswegs so, dass Du den Strom mithörst und sagen kannst: 'Jetzt ist das Signal da, und jetzt nicht mehr', sondern Du kannst im Nachhinein nach der Analyse der Aufzeichnung vielleicht mal einigermassen sicher sagen: Damals, da in dem Teilbereich, ist es wahrscheinlich dass das Signal da war.

Wir reden hier aber über Datenmengen, die in der Praxis nicht zu bewältigen sind (ausser, Du bist die NSA oder hast unbegrenzte finanzielle Mittel um den nötigen Storage und die Rechenkapazität aufzubringen). Deswegen habe ich oben das 'nicht Praxisrelevant' dazugeschrieben.

Dejan Vu 12. Jul 2014 09:59

AW: Noise XOR Signal = Noise?
 
Klingt logisch, ist aber trotzdem (in meinen Augen) nicht richtig. Ich glaube eher, das ein Signalstrom etwaige Schwächen des Zufallsgenerators aufdecken würde, mehr nicht. Ein 'perfekter' bzw. hinreichend guter Zufallsstrom wird dir nicht den Gefallen tun. Voraussetzung ist natürlich, das die Wertebereiche beider Signale (Rauschen und Muster) identisch sind.

Deiner Ansicht nach gilt: Zufall xor Muster = Kein Zufall (vereinfacht). Das stimmt aber meiner Meinung nach nicht.
Ein Gedankenexperiment soll das belegen.
Du hast ein Gefäß mit zwei Bällen (schwarz und weiß). Du greifst blind in das Gefäß, nimmst einen Ball und schreibst die Farbe auf (Zufallsstrom). Nun kommt das Signal (111100001111000). Bei einer '1' schreibst Du die Farbe des gezogenen Balles auf, bei einer '0' die andere.
Preisfrage: Wird sich die Sequenz bzw. der Informationsgehalt dadurch in irgend einer Weise verändern? Selbst wenn Du das Ausgangssignal 1000 Jahre analysierst, wirst Du nicht merken, ob die Sequenz durch das blinde Ziehen oder erzeugt wurde, oder eine Regel zur Veränderung angewandt wurde.

BUG 12. Jul 2014 15:15

AW: Noise XOR Signal = Noise?
 
Angenommen man hat einen Generator für echten Zufall (z.B. radioaktiver Zerfall, thermisches Rauschen, usw.), dann entspräche das in Grunde einem One-Time-Pad.
Die Argumentation ist natürlich verkehrt herum, weil das OTP gerade sicher ist, weil dort diese Eigenschaften ausgenutzt werden; aber wenn Phoenix recht hätte wäre das OTP nicht sicher :wink:

Auch die Theorie mit dem Informationsverlust hat einen Haken: Die Information ist steckt eben nicht in dem Endresultat, sondern nur in der Kombination aus Schlüssel und dem Resultat ... also exakt so viele Bits wie vorher.

nuclearping 12. Jul 2014 18:14

AW: Noise XOR Signal = Noise?
 
Ich denke das Hauptproblem ist hier auch, dass man
Delphi-Quellcode:
Byte XOR Byte
macht. Also beide Positionen haben einen Wertbereich von 0-255. Daran direkt zu erkennen, ob ein zusätzlicher Prozess das Signal beeinflusst oder nicht, schließt sich wohl damit auch aus.

Ich denke auch, dass der Ansatz von Phoenix, über eine indirekte Analyse, hier eher zum Ergebnis führen würde, vorrausgesetzt es handelt sich um einen "echten" Zufall.

Namenloser 12. Jul 2014 18:37

AW: Noise XOR Signal = Noise?
 
Es kommt wohl darauf an, um was für eine Art Zufall es sich handelt, bzw. wie der Zufall verteilt ist.

Wenn man gleichverteilete Zufallswerte von 0..255 generiert und diese Byte-weise mit dem Signal XORt, dann kann man unter Umständen eine Analyse durchführen, denn durch das XOR mit dem Signal ändert sich die Verteilung (beispielsweise ist der Mittelwert dann u.U. nicht mehr 127).

Hantiert man dagegen mit zufälligen Bits, wobei jedes Bit eine 50%ige Chance hat, 1 oder 0 zu sein, dann sollte es unmöglich sein, das Signal zu rekonstruieren. Das ist ja gerade das Prinzip des One-Time-Pad.


Edit:
Schwachsinn, bei gleichverteilten Bytes ist jedes Bit auch wieder gleichverteilt.

Also man kann das Signal so oder so nicht rekonstruieren.

Bei Stochastik verknoten sich mir immer die Hirnwindungen :duck:

BUG 12. Jul 2014 18:55

AW: Noise XOR Signal = Noise?
 
Bist du sicher das gleich-verteilte Bytes nicht gleich-verteilte Bits implizieren?

Ich würde mir das so überlegen: Angenommen man hat ein Byte aus einer gleich-verteilten Quelle. Nun wähle man ein beliebiges Bit in diesem Byte. Für jeden Wert dieses Bits gibt es gleich viele Byte-Werte, bei dem dieses Bit gesetzt bzw. nicht gesetzt ist. Jeder dieser Byte-Werte ist gleich wahrscheinlich. Daraus folgt, dass das einzelne Bit auch eine 50% Chance hat, gesetzt zu sein.

Beispiel: das höchstwertige Bit
Gesetzt für 0..127, also 128 Werte
Nicht gesetzt für 128..255, also 128 Werte
Die Wahrscheinlichkeit für beide Mengen von Werten ist jeweils (1/256)*128 = 1/2.

@rote Box: Ich poste es jetzt trotzdem :tongue:

Dejan Vu 12. Jul 2014 22:04

AW: Noise XOR Signal = Noise?
 
Ich will nur daran erinnern, das es hier nicht um Ver/Entchlüsselung geht, sondern *ob* man erkennt, ob eine Signalveränderung durch XOR stattgefunden hat, oder nicht.

Aphton 12. Jul 2014 22:48

AW: Noise XOR Signal = Noise?
 
Ich kann mich intuitiv an Phonix #3 anschließen..

Als ein einfaches Beispiel habe ich mir ein Geradensegment vorgestellt, das beliebig durch den Raum verläuft, wo man aber mit dem freien Auge bereits ein Muster erkennt.
Wenn man nun die Operation "Xor" in diesem Fall durch "Addition" substituiert und dem Geradensegment ein Noise "draufaddiert", kann man folglich Änderungen am Muster warnehmen. Komplizierter wirds dann natürlich, wenn die Muster komplexer werden. Hängt m.M.n also von der Mustererkennung ab.

Ob die Änderung der Operation ohne Weiteres möglich ist und die Schlussfolgerung dadurch nicht beeinträchtigt wird, ist mir moment nicht bewusst.

Medium 13. Jul 2014 00:05

AW: Noise XOR Signal = Noise?
 
Selbst bei Phoenix' Methode (welche ich auch für die einzig denkbare mit (vielen) weltlichen Mitteln halte), ist nochmals zu betonen, dass man auch damit nicht dazu kommt, das Signal zu rekonstruieren. Es geht dabei nur darum, ob ein Signal auf das Rauschen ge-xor-t ist oder nicht. Null Aussage darüber, wie dieses Signal wohl aussehen mag.

Uwe Raabe 13. Jul 2014 00:18

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von Medium (Beitrag 1265338)
Es geht dabei nur darum, ob ein Signal auf das Rauschen ge-xor-t ist oder nicht. Null Aussage darüber, wie dieses Signal wohl aussehen mag.

Die Frage war ja auch:
Zitat:

kann man ein Signal erzeugen, dass sich messbar gegen das Rauschen des Zufallsgenerator absetzen kann?
Demnach ist die tatsächliche Form des Signals eigentlich egal, solange man am Ende erkennen kann, ob es eingeschaltet war oder nicht.

Ein trivialer Lösungsansatz wäre, das Signal aus dem Zufallsgenerator zu nehmen und mit diesem per XOR zu verwursten. Dann ist das Ausgangssignal immer $00 wenn das Signal an ist. Der Umkehrschluß (wenn $00 ankommt ist das Signal an) gilt aber auch da nicht. Eine Folge von Nullen wäre dann auch erst ab einer gewissen Länge mit hoher Wahrscheinlichkeit ein Indiz für ein eingeschaltetes Signal.

Namenloser 13. Jul 2014 00:23

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von Aphton (Beitrag 1265336)
Ich kann mich intuitiv an Phonix #3 anschließen..

Als ein einfaches Beispiel habe ich mir ein Geradensegment vorgestellt, das beliebig durch den Raum verläuft, wo man aber mit dem freien Auge bereits ein Muster erkennt.
Wenn man nun die Operation "Xor" in diesem Fall durch "Addition" substituiert und dem Geradensegment ein Noise "draufaddiert", kann man folglich Änderungen am Muster warnehmen.

XOR ist aber nicht das gleiche wie Addition.

Für ein einzelnes Bit zwar schon, aber mit einem einzigen Bit kann man deine Gerade (oder irgendwas „komplexeres“) auch gar nicht erst bilden.

BUG 13. Jul 2014 00:37

AW: Noise XOR Signal = Noise?
 
Ich würde mich sogar aus dem Fenster lehnen und behaupten, das die Addition modulo 256 genau so effektiv ist, wenn man gleich-verteilten Noise mit Elementen 0..255 aufaddiert. Mit den gleichen Argumenten wie zuvor. Oder vielleicht sogar für alle endlichen Gruppen ... darauf würde ich mich adhoc aber nicht festnageln lassen.

Klar kann man ein Muster (die Gerade) erkennen, wenn man keine inversen Elemente auswählen kann.


@Namenloser: Mit etwas Augen zudrücken kann man eine 1-Bit "Gerade" haben; es gibt dann sogar 4 verschiedene :mrgreen:
Code:
y = 0*x + 0 (mod 2) => 0
y = 0*x + 1 (mod 2) => 1
y = 1*x + 0 (mod 2) => Identität
y = 1*x + 1 (mod 2) => Not
Modulo 2 entspricht die Addition dem XOR und die Multiplikation dem AND.

Namenloser 13. Jul 2014 00:56

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von BUG (Beitrag 1265342)
Ich würde mich sogar aus dem Fenster lehnen und behaupten, das die Addition modulo 256 genau so effektiv ist, wenn man gleich-verteilten Noise mit Elementen 0..255 aufaddiert. Mit den gleichen Argumenten wie zuvor.

Ergibt für mich Sinn.

himitsu 13. Jul 2014 01:21

AW: Noise XOR Signal = Noise?
 
Hab zwar keine Ahnung, aber meine Vermutung, wenn ich davon ausgeh, daß es sich um echten Zufall handelt und nicht um einen Zufall aus soeinem 32-Bit-Gernerator, wie im Delphi:

Dann ist die Anzahl der Werte unendlich.
Und betrachten kann man nur einen kleinen Bereich davon.
Also ist es doch unmöglich rauszubekommen, ob in dem betrachteten Bereich etwas Anderes eingerechnet wurde, denn irgendwo in allen Werten des Zufallsgenerators steckt ganz bestimmt der betrachtete Bereich, egal ob da was eingerechnet wurde oder nicht und wenn man nicht weiß welchen Bereich des Zufalls man betrachtet, dann kann man doch auch nichts wissen oder sonstwie irgendein Muster erkennen?

BUG 13. Jul 2014 01:44

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von himitsu (Beitrag 1265345)
denn irgendwo in allen Werten des Zufallsgenerators steckt ganz bestimmt der betrachtete Bereich

Ich glaube die Meinung von Phoenix (und anderen) ist weniger, das es nicht doch Zufall sein könnte, sondern dass sich die Wahrscheinlichkeiten für bestimmte Folgen verschieben, also diese eine andere Wahrscheinlichkeit haben als bei dem originalen Zufallsgenerator. Das könnte man feststellen.

Die andere Meinung ist, dass das nicht passiert, wenn die Bits aus dem Generator echter Zufall und gleich-verteilt sind.

Dejan Vu 13. Jul 2014 09:37

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von BUG (Beitrag 1265347)
Ich glaube die Meinung von Phoenix (und anderen) ist weniger, das es nicht doch Zufall sein könnte, sondern dass sich die Wahrscheinlichkeiten für bestimmte Folgen verschieben, also diese eine andere Wahrscheinlichkeit haben als bei dem originalen Zufallsgenerator. Das könnte man feststellen.

Die Wahrscheinlichkeit 'für bestimmte Folgen' ist bei einem guten RNG immer gleich, d.h. es gibt keine präferierte Sequenz. Gäbe es die, wäre es kein 'guter Zufallsgenerator'. Das ist aber die Grundannahme für dieses Gedankenexperiment.

Wenn ich einen gleichverteilt zufälligen Bitstrom (Input) habe und verändere jedes Bit per XOR mit einem vom [u]Input unabhängigen Bitstrom (mein Nutzsignal)[/b], wie kann das Ausgangssignal dann nicht zufällig sein? Wie kann ich die Wahrscheinlichkeit einer '1' erhöhen, wenn ich gar nicht weiß, wann eine '1' ankommt?

In dem Augenblick, wo ich die Gleichverteilung meines Inputs verändere, also z.B. etwas mehr Einsen als Nullen produziere, werde ich sehr wohl erkennen, ob das Signal verändert wurde, weil dieses Ungleichgewicht durch das Nutzsignal verändert wird. Gleiches gilt für bestimmte Sequenzen. Der Eingangstrom '01010101' ist auch gleichverteilt, seine Entropie wird aber verändert, sobald ich ihn manipuliere.

Zitat:

Zitat von sx2008 (Beitrag 1265291)
Oder anders gefragt: kann man ein Signal erzeugen, dass sich messbar gegen das Rauschen des Zufallsgenerator absetzen kann?

Ja. Das Signal muss eine Funktion des Eingangssignals (Rauschen) sein. Ich kann ein Signal z.B. so aufbauen, das es selbst aus Rauschen besteht, aber in jedem 100sten Byte das Byte aus dem Inputsignal kopiert. Dann habe ich im Output alle 100 Bytes eine 0, ergo eine Veränderung der Entropie, die kann ich messen und fertig.

BUG 13. Jul 2014 15:45

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von Dejan Vu (Beitrag 1265352)
Wenn ich einen gleichverteilt zufälligen Bitstrom (Input) habe und verändere jedes Bit per XOR mit einem vom [u]Input unabhängigen Bitstrom (mein Nutzsignal)[/b], wie kann das Ausgangssignal dann nicht zufällig sein? Wie kann ich die Wahrscheinlichkeit einer '1' erhöhen, wenn ich gar nicht weiß, wann eine '1' ankommt?

Das ist genau das, was wir hier diskutieren :mrgreen:

Dejan Vu 13. Jul 2014 15:49

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von BUG (Beitrag 1265381)
Das ist genau das, was wir hier diskutieren :mrgreen:

Erstens habe ich hoffentlich das Problem vereinfacht (1/0) und zweitens war ja auch eine rethorische Frage. Es geht nämlich nicht, ;-)

Blup 14. Jul 2014 11:01

AW: Noise XOR Signal = Noise?
 
Ich schließe mich der Aussage von Dejan Vu an.

Angenommen ich mische einem zufälligen Bitstrom per Xor ein stetiges Signal zu, bei dem alle Bits 1 sind.
Solange im Ausgangssignal genausoviele 0 wie 1-Bit vorkommen, wird auch das Ergebnis dieser Bedingung entsprechen.

Angenommen ich mische einem zufälligen Bitstrom per Xor ein Signal zu, bei dem die Bits 1 und 0 jedesmal wechseln (10101010...).
Im Ausgangssignal folgt auf eine 0 genauso häufig eine 1 wie erneut eine 0.
Das Ergebnis entspricht auch dieser Regel.

Phoenix 14. Jul 2014 11:49

AW: Noise XOR Signal = Noise?
 
Das gilt aber genau nur solange, wie das Signal entweder absolut gleichförmig (den Zufall also immer gleich verändert) oder aber selber auch absolut zufällig ist (und damit keine Information beinhaltet).

Sobald der Signalstrom ein Muster enthält, schlägt sich dieses im erzeugten Datenstrom zwangsläufig wieder. Und dieses Muster kann, bei ausreichend intensiver Analyse des Bereiches der das Muster enthält gegenüber anderen Bereichen die nicht manipuliert wurden, mit einer gewissen Wahrscheinlichkeit erkannt werden.

Das hat grundsätzlich nichts mit der Sicherheit von OTP's zu tun, denn ohne den originalen, nicht veränderten Zufallsstrom als Schlüssel ist eine Rekonstruktion der Information nicht möglich (da gibts genug mathematische Beweise für ;-) ).

Nichts desto trotz ist es aber so, dass der erzeugte Datenstrom durch das eingeflochtene Muster den sonst reinen Zufall an den modifizierten Stellen mit der Ungleichverteilung des Input-Signals verzerrt, und diese Verzerrung ist bei globaler Betrachtung sehr wahrscheinlich irgendwann erkennbar.

jfheins 14. Jul 2014 22:17

AW: Noise XOR Signal = Noise?
 
Unter den Annahme:
1. wir reden hier von "echtem Zufall"
2. das Dignal wird ohne Kenntnis des Zufalls generiert
schlage ich mich mal auf die Seite von

Noise XOR Signal = Noise.

Zitat:

Sobald der Signalstrom ein Muster enthält, schlägt sich dieses im erzeugten Datenstrom zwangsläufig wieder.
Jein. Natürlich verändert sich der Ergebnisstrom. Muster sind dort allerdings keine mehr zu erkennen. Du kannst jedes beliebige Mustersuchverfahren anwenden und wirst keine Muster finden. Diese erscheinen erst wieder, falls du das Ergebnis wieder mit denselben Zufallswerden xorst.

Oder Mathematisch formuliert: Das Zufallsbit kann 0 oder 1 sein, je mit Wahrscheinlichkeit 50%. D.h. eine 1 Im Signal wird zu 50% eine 1 bleiben, oder zu 50% geflippt. Es ist (auch bei geschickter, trickreicher Wahl des Signals) unmöglich, aus dem Ergebnis Rückschlüsse auf das Signal zu erlangen.

Oder als Herausforderung:
Zitat:

Phonix, konstruiere ein Signal, dass auch nach xor mit einem zufälligen Bitstrom noch ein Bit Information überträgt. :stupid:
Etwas ähnliches wird übrigens bei UMTS eingesetzt: CDMA ermöglicht gleichzeitig Multiplex und ein bisschen Verschlüsselung. Die äquivalente Fragestellung (wo wir schon bei Verschlüsselung sind) wäre ja "Kann ich die Aufgabe eines OTP von Zufall unterscheiden?" Und OTP wäre ziemlich unpraktisch, wenn dem so wäre.

Namenloser 14. Jul 2014 22:30

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von Phoenix (Beitrag 1265452)
Das hat grundsätzlich nichts mit der Sicherheit von OTP's zu tun, denn ohne den originalen, nicht veränderten Zufallsstrom als Schlüssel ist eine Rekonstruktion der Information nicht möglich (da gibts genug mathematische Beweise für ;-) ).

Doch hat es, denn „Signal an oder Signal aus“ ist Information. Wenn du also nach Analyse erkennen könntest, ob das Signal an war oder nicht, dann entspricht das der Rekonstruktion der Information.

Du könntest ja über An- und Ausschalten des Signals sogar jede beliebige Information (Nachrichten, Dateien, ...) binär kodiert übertragen.

Was du schreibst ist also ein ganz klarer Widerspruch zur Sicherheit des One-Time-Pad.

Phoenix 14. Jul 2014 23:12

AW: Noise XOR Signal = Noise?
 
Zitat:

Zitat von Namenloser (Beitrag 1265544)
Was du schreibst ist also ein ganz klarer Widerspruch zur Sicherheit des One-Time-Pad.

Ist es nicht. Du legst mir ja auch wieder Sachen in den Mund die ich nie gesagt habe.

Das One-Time-Pad wird nicht als permanenter Zufallsstrom verwendet, in dem ab und zu eine Nachricht eingeflochten wird.
Das One-Time-Pad ist eine doppelt gespeicherte (endliche) folge von Zufall, aus dem pro Nachricht immer genau so viel als Schlüssel verwendet wird, um die Nachricht vollständig zu verschlüsseln. Andersrum: Habe ich eine 100 Byte lange Nachricht, nehme ich die nächsten 100 Byte aus dem OTP als Schlüssel. Da die gesamte(!) Nachricht aus Noise XOR Signal besteht, ist eine statistische Analyse wo denn jetzt Signal anfängt oder aufhört weder Sinnvoll (es steckt eh immer Signal drin), und vor allem wäre es auch aussichtslos, da nie genug Daten für eine Analyse vorlägen.


Aber mal ganz praktisch:

Noise XOR Noise = 0. Alle Bits sind null. Eine Glatte Nulllinie.

Das heisst: lege ich perfekten Zufall über perfekten Zufall, und analysiere diesen Zufall statistisch in seiner Gesamtheit, so werde ich absolut keinerlei Auffälligkeiten finden.


Noise XOR Noise ist also 0, und nicht Signal.
Daher kann Noise XOR Signal nicht Noise sein, denn Noise XOR Noise ist wieder Null und das Signal wäre flöten. Daher ist Noise XOR Signal maximal Noise2. Nur dann können wir aus Noise2 XOR Noise wieder das Signal erhalten.


Dort, wo das Signal anliegt, unterscheiden sich Noise und Noise2. An den Stellen, an denen das Signal nicht anliegt, ist Noise2 wieder mit Noise1 identisch. An den Stellen, an denen Noise2 nun von Noise unterschiedlich ist, wird ein XOR mit Noise nicht mehr zu glatten Nullen führen, sondern zu anderen Werten - nämlich dem Signal.


Perfekter Zufall beinhaltet auch Muster, und diese wiederholen sich zufällig. Die Wiederholung jedes einzelnen Patterns in einem Zufallsstrom ist wieder rein zufällig und daher auch normalverteilt.

Was heisst das nun aber, wenn wir uns Noise2 an den Stellen angucken, an denen das Signal anlag?

Richtig: Noise2 unterscheidet sich von Noise. Das heisst, es findet sich dort eine andere Bitfolge - ein anderes Muster - das bei perfektem Zufall eben nicht genau dort wäre. Dieses Muster wird sich in im normalen Zufallsstrom auch - mehrmals - wiederfinden, aber an anderer Stelle. Das Muster, das in Noise an dieser Stelle war, ist entsprechend auch nicht mehr an dieser Stelle vorhanden.

Schaue ich mir nun Noise2 in einer ausreichend großen Menge an, so wird mir auffallen, das zwei bestimmte Muster auffallen. Eines kommt statistisch gesehen zu wenig vor (nämlich das, was in Noise1 an dieser Stelle war), und ein anderes Muster tritt zu oft auf (nämlich das, das durch das Signal erzeugt wurde). Wenn man sich nun die zufällig auch normalverteilten Abstände zwischen den Mustern anschaut, dann wird man, wieder bei ausreichender Datenmenge, auch erkennen können, dass der Abstand zwischen zwei bestimmten Mustern deutlich größer ist als normal und interessanterweise genau an dieser Stelle auch das andere auffällige Muster, mit einem sehr wahrscheinlich auffallend engen Abstand zu anderen seines gleichen vorkommt.

Voilá, ich habe mit einer leicht erhöhten Wahrscheinlichkeit feststellen können, das vermutlich an dieser Stelle der echte Zufall modifiziert wurde.



Zitat:

Zitat von jfheins (Beitrag 1265542)
Oder als Herausforderung:
Zitat:

Phonix, konstruiere ein Signal, dass auch nach xor mit einem zufälligen Bitstrom noch ein Bit Information überträgt. :stupid:

Siehe oben. Da braucht man nichts zu konstruieren.
Nehme eine beliebige Zahl und XORe sie mit Zufall. XORe den gleichen Zufall erneut, und die Original-Information ist weiterhin vorhanden. Wenn die Information nicht im Ergebnisstrom wäre, dann wäre das ja keine umkehrbare Verschlüsselung, sondern z.B. ein Hash-Algorithmus, bei dem die Original-Information verloren geht und nur ein (reproduzierbares) Abbild der Information übrig bleibt.

Namenloser 15. Jul 2014 00:56

AW: Noise XOR Signal = Noise?
 
Natürlich gehen wir davon aus, dass Signal und Noise stochastisch unabhängig voneinander sind, wie es bei echtem Zufall sein sollte.


Alle Zeitangaben in WEZ +1. Es ist jetzt 23:58 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 by Thomas Breitkreuz