Noise XOR Signal = Noise?

[himitsu]

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]

Zitat von himitsu:

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]

Zitat von BUG:

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

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]

Zitat von Dejan Vu:

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

[Dejan Vu]

Zitat von BUG:

Das ist genau das, was wir hier diskutieren

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

[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.