Gleichung umstellen mit XOR

[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