XOR-Verschlüsselung
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.