Zum Inhalt springen

XOR-Verschlüsselung

Aus FLBK-Wiki

Computer speichern Texte, Bilder und Programme als Bitmuster. Die XOR-Verschlüsselung verschlüsselt solche Bitmuster mit einer einzigen, sehr einfachen Rechenoperation.

Definition

Bei der XOR-Verschlüsselung wird der Klartext als Bitfolge geschrieben und Bit für Bit mit einem Schlüssel verknüpft, der ebenfalls eine Bitfolge ist. Die Verknüpfung ist das exklusive Oder, kurz XOR, mit dem Zeichen [math]\displaystyle{ \oplus }[/math]. Ist der Schlüssel kürzer als der Klartext, wird er so oft wiederholt, wie es nötig ist.

Das Verfahren ist symmetrisch: Sender und Empfänger verwenden denselben Schlüssel.

Lange Bitfolgen werden zur besseren Lesbarkeit in Vierergruppen geschrieben. Wie aus Zeichen Bitmuster werden, erklären die Artikel Zeichen und Dualsystem.

Verknüpfung XOR

Das exklusive Oder zweier Bits ist 1, wenn die beiden Bits verschieden sind, und 0, wenn sie gleich sind:

[math]\displaystyle{ x }[/math] [math]\displaystyle{ y }[/math] [math]\displaystyle{ x \oplus y }[/math]
0 0 0
0 1 1
1 0 1
1 1 0

Wichtige Eigenschaften, mit [math]\displaystyle{ x }[/math], [math]\displaystyle{ y }[/math] und [math]\displaystyle{ z }[/math] für beliebige Bits:

  • [math]\displaystyle{ x \oplus 0 = x }[/math]: Ein Schlüsselbit 0 lässt das Bit unverändert.
  • [math]\displaystyle{ x \oplus 1 }[/math] kehrt das Bit um.
  • [math]\displaystyle{ x \oplus x = 0 }[/math]: Ein Bit, mit sich selbst verknüpft, ergibt 0.
  • Die Reihenfolge spielt keine Rolle: [math]\displaystyle{ x \oplus y = y \oplus x }[/math] und [math]\displaystyle{ (x \oplus y) \oplus z = x \oplus (y \oplus z) }[/math].

Weitere Verknüpfungen von Wahrheitswerten behandelt der Artikel Boolesche Algebra.

Verschlüsseln und Entschlüsseln

Für jedes Klartextbit [math]\displaystyle{ m_i }[/math], jedes Schlüsselbit [math]\displaystyle{ k_i }[/math] und jedes Geheimtextbit [math]\displaystyle{ c_i }[/math] gilt:

[math]\displaystyle{ c_i = m_i \oplus k_i }[/math]
[math]\displaystyle{ m_i = c_i \oplus k_i }[/math]

Verschlüsseln und Entschlüsseln sind derselbe Vorgang. Wer den Geheimtext noch einmal mit dem Schlüssel verknüpft, erhält den Klartext:

[math]\displaystyle{ c_i \oplus k_i = (m_i \oplus k_i) \oplus k_i = m_i \oplus (k_i \oplus k_i) = m_i \oplus 0 = m_i }[/math]

Sicherheit

Wie gut das Verfahren die Vertraulichkeit schützt, hängt vom Schlüssel und von seiner Verwendung ab:

  • Kurzer Schlüssel: Ein Schlüssel aus [math]\displaystyle{ b }[/math] Bit hat [math]\displaystyle{ 2^b }[/math] Möglichkeiten (siehe Anzahl der Bitmuster). Bei einem kurzen Schlüssel probiert ein Brute-Force-Angriff sie sofort durch.
  • Wiederholter Schlüssel: Wird ein Schlüssel aus 8 Bit für jedes Zeichen wiederholt, ergibt dasselbe Zeichen immer dasselbe Geheimtextmuster. Das ist eine monoalphabetische Substitution, die Häufigkeitsanalyse bricht sie.
  • Bekannter Klartext: Aus [math]\displaystyle{ c_i = m_i \oplus k_i }[/math] folgt [math]\displaystyle{ k_i = c_i \oplus m_i }[/math]. Wer zu einem Stück Geheimtext den Klartext kennt, berechnet daraus den Schlüssel (siehe Known-Plaintext-Angriff).
  • Zufälliger Schlüssel in voller Länge: Ist der Schlüssel zufällig, so lang wie die Nachricht und wird er nur einmal verwendet, ist das Verfahren nicht zu brechen. Das ist das One-Time-Pad.

Umsetzung in Java

In Java verknüpft der Operator ^ zwei ganze Zahlen bitweise mit XOR. Die Methode verschlüsselt jedes Zeichen mit demselben Schlüssel aus 8 Bit, der als Zahl von 0 bis 255 übergeben wird. Ein zweiter Aufruf mit demselben Schlüssel entschlüsselt.

public static String xor(String text, int schluessel) {
    String ergebnis = "";
    for (int i = 0; i < text.length(); i++) {
        ergebnis = ergebnis + (char) (text.charAt(i) ^ schluessel);
    }
    return ergebnis;
}

Beispiele

Zeichen mit einem 8-Bit-Schlüssel verschlüsseln

Die Zeichenfolge OK wird mit dem Schlüssel 0011 1010 verschlüsselt. Jedes Zeichen wird nach der ASCII-Tabelle zu 8 Bit: O hat den Code 79, K den Code 75. Der Schlüssel ist 8 Bit lang und wird für jedes Zeichen wiederholt.

Zeichen O K
Klartext 0100 1111 0100 1011
Schlüssel 0011 1010 0011 1010
Geheimtext 0111 0101 0111 0001

Der Geheimtext ist das Bitmuster 0111 0101 0111 0001.

Geheimtext entschlüsseln

Der Empfänger verknüpft den Geheimtext 0111 0101 0111 0001 mit demselben Schlüssel 0011 1010:

Geheimtext 0111 0101 0111 0001
Schlüssel 0011 1010 0011 1010
Klartext 0100 1111 0100 1011
Zeichen O K

Es entsteht wieder OK. Verschlüsseln und Entschlüsseln sind bei XOR derselbe Vorgang.

Schlüssel aus bekanntem Klartext berechnen

Eve kennt den Geheimtext 0111 0101 0111 0001 und weiß, dass die Nachricht mit dem Zeichen O beginnt. Sie verknüpft das erste Geheimtextzeichen mit dem bekannten Klartextzeichen:

Bitmuster
Geheimtext 0111 0101
bekannter Klartext O 0100 1111
Schlüssel 0011 1010

Das Ergebnis ist der Schlüssel 0011 1010. Damit entschlüsselt Eve auch alle weiteren Zeichen.