Noise XOR Signal = Noise?

[Blup]

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]

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]

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.

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]

Zitat von Phoenix:

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]

Zitat von Namenloser:

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 von jfheins:

Oder als Herausforderung:

Zitat:

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

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]

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