Gleichung umstellen mit XOR

[Paulchen]

Hallo,
ich hab ein Problem, und zwar habe ich folgende Gleichung:
Y = (X+K) ^ K

Wobei ^ XOR, + die Addition (modulo 2^32, da 32 bit integer) sein soll.

Ich kenne die Werte von Y und X und möchte nun K berechnen.

Aber leider komm ich gerade irgendwie nicht weiter (hoffentlich nur ein Brett vor den Augen) und es wäre super wenn einer von euch mir evt. helfen könnte, wie ich die Gleichung dort oben nach K umstelle.

Grüße
Paulchen

[Gunnar Bittersmann]

@@Paulchen:

Die wiederholte XOR-Operation liefert wieder den Ausgangswert: A ^ K ^ K = A

Y = (X+K) ^ K

auf beiden Seiten ^ K:

Y ^ K = (X+K) ^ K ^ K = X+K

Die Subtraktion von K (modulo 2^32) sollte dann nicht das Problem sein.

Live long and prosper,
Gunnar

[Paulchen]

Hallo,
vielen Dank für deine Antwort, nur hilft es mir nicht weiter :(

auf beiden Seiten ^ K:

Y ^ K = (X+K) ^ K ^ K = X+K

Die Subtraktion von K (modulo 2^32) sollte dann nicht das Problem sein.

Dann habe ich dort stehen:
(Y ^ K) - K = X

Allerdings möchte ich K haben (X und Y sind bekannt).

Grüße
Paulchen

[Gunnar Bittersmann]

@@Paulchen:

Allerdings möchte ich K haben (X und Y sind bekannt).

Ähm ja, da schriebst du. Wer lesen kann, ist klar im Vorteil.

Nun, die Klammer aufzulösen dürfte tricky sein, da bei XOR jedes Bit unabhängig von den anderen backert wird, während bie der Addition Übertrage von einem auf das jeweils nächst höherwertige auftreten.

Die Gleichung Y = (X+K) ^ K hat im Allgemeinen keine eindeutige Lösung für K. Wie man leicht sieht, gilt sie für X = Y = 0 für alle K. Für Y ≠ 0, X = 0 hat sie keine Lösung, ebenso für Y = 0, X ≠ 0.

Man kann auch leicht zeigen: Damit es Lösungen gibt, müssen X und Y im LSB übereinstimmen, also entweder beide gerade oder beide ungerade sein.

Und allgemeiner: Damit es Lösungen gibt, müssen, wenn die letzten n Bits von X den Wert 0 haben, X und Y in den letzten n + 1 Bits übereinstimmen, d.h. wenn X auf 10…0 endet, muss es auch Y tun (gleich viele Nullen).

Live long and prosper,
Gunnar

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

Die Gleichung Y = (X+K) ^ K hat im Allgemeinen keine eindeutige Lösung für K.

So wie ich das sehe, hat sie das nie. Lösungen treten wenn, dann immer paarweise auf: Wenn 0k₁₄k₁₃…k₁k₀ Lösung ist, dann auch 1k₁₄k₁₃…k₁k₀ und andersrum.

Live long and prosper,
Gunnar

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

Wer lesen kann, ist klar im Vorteil.

[…] backert wird, während bie […]

Wer schreiben kann, auch.

Live long and prosper,
Gunnar

[Gunnar Bittersmann]

@@Paulchen:

Y = (X+K) ^ K

Betrachten wir das Ding mal bitweise:
[latex]y_i = (x_i + k_i + c_i) \operatorname{xor} k_i[/latex]
wobei cᵢ der Übertrag der Addition der nächst niederwertigen Bits ist:
[latex]c_i =
\begin{cases}
  0,  & i = 0 \
  \operatorname{HSB}(c_{i-1} + x_{i-1} + k_{x-1}), & i > 0
\end{cases}[/latex]

Zerlegen wir das Ergebnis der Addition xᵢ + kᵢ + cᵢ in das LSB Σᵢ und das HSB cᵢ₊₁ (Übertrag in das nächst höherwertige Bit), so ergibt sich mit yᵢ = Σᵢ xor kᵢ:
[latex]\begin{array}{c|c|c||c|c||c} x_i & c_i & k_i & c_{i+1} & \Sigma_i & y_i \
\hline
0&0&0&0&0&0\
0&0&1&0&1&0\
0&1&0&0&1&1\
0&1&1&1&0&1\
1&0&0&0&1&1\
1&0&1&1&0&1\
1&1&0&1&0&0\
1&1&1&1&1&0\
\end{array}[/latex]

Man sieht, dass yᵢ nicht von kᵢ abhängt, sondern nur von xᵢ und cᵢ (und damit von kᵢ₋₁, kᵢ₋₂, …). Es gilt
[latex]y_i = x_i \operatorname{xor} c_i[/latex]
Umgestellt für gegebene X und Y:
[latex]c_i = x_i \operatorname{xor} y_i[/latex]

Obere Tabelle anders sortiert (bekannt sind xᵢ, cᵢ und cᵢ₊₁; unbekannt ist kᵢ) ergibt:
[latex]\begin{array}{c|c|c||c} x_i & c_i & c_{i+1} & k_i \
\hline
0&0&0&*\
0&0&1&-\
0&1&0&0\
0&1&1&1\
1&0&0&0\
1&0&1&1\
1&1&0&-\
1&1&1&*\
\end{array}[/latex]
'*' bedeutet: beliebig 0 oder 1 (Kombination (xᵢ, cᵢ, cᵢ₊₁) kommt in oberer Tabelle doppelt vor)
'-' bedeutet: keine Lösung      (Kombination (xᵢ, cᵢ, cᵢ₊₁) kommt in oberer Tabelle nicht vor)

Der Algorithmus sieht also so aus:
(1) C = X xor Y                ; lässt sich in einem Rutsch berechnen
(2) FOR i = 0 TO 14
(2a)    bestimme kᵢ aus Tabelle
(2b)    IF kᵢ = '-' THEN EXIT   ; keine Lösung
(3) k₁₅ = '*'                  ; wie ich schon sagte

Beispiel: Für
X = 0001011101010000
K = 1010010111010110
ergibt sich:
Σ = 1011110100100110
Y = 0001100011110000

Sind also gegeben
X = 0001011101010000
Y = 0001100011110000
ergibt sich
C = 0000111110100000
K = ***00***1101****

Zehn Sterne heißt: Es gibt 2¹⁰ = 1024 verschiedene Lösungen für K. Das im Beispiel gewählte ist eine davon.

Live long and prosper,
Gunnar

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

Der Algorithmus sieht also so aus:

Hm, doch nicht ganz so. Der gibt für X = 0, Y = 1 als Lösung für K *…*0 aus, obwohl es gar keine Lösung gibt.

Irgendwas hab ich noch übersehen. Vielleicht nur eine Kleinigkeit. Oder ich war völlig auf dem Holzweg.

Live long and prosper,
Gunnar

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

Irgendwas hab ich noch übersehen. Vielleicht nur eine Kleinigkeit.

Ja, beim LSB kann natürlich noch kein Übertrag auftauchen. Sagte ich doch:
[latex]c_i =
\begin{cases}
0,  & i = 0 \
\operatorname{HSB}(c_{i-1} + x_{i-1} + k_{x-1}), & i > 0
\end{cases}[/latex]

Also ist nach
(1) C = X xor Y
zu prüfen, ob c₀ = 0 ist, d.h. ob X und Y im LSB übereinstimmen. Auch das sagte ich schon.

(1) C = X xor Y
(2) IF c₀ ≠ 0 THEN EXIT          ; es gibt keine Lösungen für K
(3) FOR i = 0 TO 14
(3a)    bestimme kᵢ aus Tabelle
(3b)    IF kᵢ = '-' THEN EXIT   ; es gibt keine Lösungen für K
(4) k₁₅ = '*'

Hoffe, jetzt stimmt’s.

Live long and prosper,
Gunnar

[Gunnar Bittersmann]

@@Gunnar Bittersmann:

[latex]c_i =

\begin{cases}
0,  & i = 0 \
\operatorname{HSB}(c_{i-1} + x_{i-1} + k_{x-1}), & i > 0
\end{cases}[/latex]

Das sollte natürlich kᵢ₋₁ heißen.

Und für alle, die ein Kästchen mit "1D62" drin sehen: U+1D62 ist LATIN SUBSCRIPT SMALL LETTER I.

Live long and prosper,
Gunnar