· 

AND, OR oder XOR für das One-Time-Pad?

1. Einführung

In meinem Video zum One-Time-Pad habe ich erklärt, dass es durchaus entscheidend ist, was für eine Art von Verschlüsselungsfunktion verwendet wird bzw. wie das Verfahren umgesetzt ist, da man sonst aus dem verschlüsselten Ergebnis Rückschlüsse auf das Original ziehen kann (obwohl der verwendete Schlüssel völlig zufällig war).

Warum die Sicherheit des Verfahrens mit der ungeschickten Wahl eines logischen Operators kompromittiert werden kann, werden wir uns in diesem Artikel anschauen. 

Zunächst müssen wir aber ein paar mathematische Grundlagen zu den logischen Operationen schaffen. Als Vorbereitung kannst du dir mein Video zur Einführung in die Aussagenlogik mit Sherlock Holmes anschauen.


2. AND

Definition: AND-Verknüpfung

Seien \(A\) und \(B\) Aussagen. Die AND-Verknüpfung \(A\wedge B\) von \(A\) und \(B\) (in Worten: „\(A\) und \(B\)“) ist genau dann wahr, wenn \(A\) und \(B\) beide wahr sind. Ansonsten ist die Aussage falsch.
\begin{array}{|c|c|c|} \hline A & B & A\wedge B\\\hline 0 & 0 & 0 \\\hline 0 & 1 & 0 \\\hline 1 & 0 & 0 \\\hline 1 & 1 & 1 \\\hline \end{array}

3. OR

Definition: OR-Verknüpfung

Seien \(A\) und \(B\) Aussagen. Die OR-Verknüpfung \(A\vee B\) von \(A\) und \(B\) (in Worten: „\(A\) oder \(B\)“) ist genau dann wahr, wenn \(A\) oder \(B\) oder beide wahr sind. Ansonsten ist die Aussage falsch.
\begin{array}{|c|c|c|} \hline A & B & A\vee B\\\hline 0 & 0 & 0 \\\hline 0 & 1 & 1 \\\hline 1 & 0 & 1 \\\hline 1 & 1 & 1 \\\hline \end{array}

4. XOR

Umgangssprachlich meinen wir mit „oder“ meist „entweder ... oder“. Die OR-Verknüpfung entspricht dem Milch-oder-Zucker-Oder. Wenn man in einem Restaurant Kaffee bestellt, bekommt man meist die Frage „Wollen Sie Milch oder Zucker in Ihren Kaffee?“ gestellt. Man wird jedoch nicht schief angeschaut, wenn man beides nimmt. Dieses Oder ist also nicht kontravalent.
Anders ist das Exklusiv-Oder (XOR) zu interpretieren. Hierbei handelt es sich um ein entweder oder, d. h. \(A\) und \(B\) dürfen nicht beide wahr sein. Dann ist das Ergebnis \(0\). Übertragen wir das XOR auf die Situation in einem Restaurant, so hat dies zur Folge, dass man sich z.B. bei einem Menü-Angebot, in dem ein Getränk (Cola oder Wasser) enthalten ist, für eines entscheiden muss. Wird hier „Cola oder Wasser?“ gefragt, meint man auch entweder Cola oder Wasser (nicht beides!).
\begin{array}{|c|c|c|} \hline A & B & A\oplus B\\\hline 0 & 0 & 0 \\\hline 0 & 1 & 1 \\\hline 1 & 0 & 1 \\\hline 1 & 1 & 0 \\\hline \end{array}

5. Wie werden Bilder gespeichert?

Wir werden nun anhand der Verschlüsselung eines Bildes mit dem One-Time-Pad nachvollziehen, warum die Operationen OR und AND hierfür völlig ungeeignet sind. Dazu musst du zuerst (sehr vereinfacht) wissen, wie ein Bild im Computer gespeichert wird. 

Ein Bild besteht aus einzelnen Pixeln. Wenn wir von einem Graustufenbild ausgehen, dann ist für jedes Pixel im Computer ein Zahlenwert zwischen von 0 bis (einschließlich) 255 vorgesehen. 0 bedeutet "schwarz" und 255 bedeutet "weiß". Alles dazwischen sind Grautöne. Ein Bild ist zweidimensional, d. h. es besitzt eine Höhe und eine Breite. Als Datenstruktur kann zum Speichern eines Bildes kann eine zweidimensionale Matrix verwendet werden. Die Anzahl der Zeilen der Matrix entspricht der Höhe des Bildes (in Pixeln) und die Breite des Bildes (in Pixeln) gibt an, wie viele Spalten diese Matrix hat. 

Wir schreiben uns für unsere Analyse ein kleines Python-Programm, das das folgende Bild zuerst in ein Graustufenbild übersetzt und dann mit einem randomisierten Schlüssel (der nur einmal verwendet wird und perfekt zufällig sein soll) jedes Pixel "verschlüsselt". 

Jedes verschlüsselte Pixel ist ebenfalls ein Zahlenwert zwischen 0 und 255. Der Zufallsschlüssel enthält genauso viele Zahlenwerte wie das Bild Pixel besitzt. Wie du einen Zahlenwert vom Dezimalsystem ins Binärsystem umwandeln kannst, erfährst du in diesem Video. Jedes Pixel mit den Werten 0 bis 255 kann durch 8 Bits dargestellt werden. 


5. Analyse in Python

Wir schreiben uns nun das Python-Programm, mit dem wir unsere Untersuchungen durchführen können. Zunächst benötigen wir einige Imports, nämlich cv2, random und deepcopy. cv2 ist die Python-Version von OpenCV, mit der du Bildverarbeitungsoperationen durchführen kannst. random wird für die Generierung eines Zufallsschlüssel verwendet (du kannst aber auch einen Quantenzufallszahlengenerator verwenden, wie ich ihn in diesem Video programmiert habe). deepcopy wird verwendet, um das eingelesene Bild zu kopieren.

import cv2
from random import *
from copy import deepcopy

Als nächstes lesen wir mit der Funktion imread des Moduls cv2 das zu verschlüsselnde Bild ein. Danach wandeln wir es zu Demonstrationszwecken in ein Grayscale-Image (also ein Graubild) um. Ich werde an anderer Stelle noch einmal näher auf RGB-Farbwerte eingehen, die man hervorragend zur Bildsteganographie verwenden kann. Für das Verständnis sind Graustufenbilder an dieser Stelle besser. 

img = cv2.imread('gunnar.jpg')
gray_img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

Als nächstes wollen wir uns einen Zufallsschlüssel generieren. Da beim One-Time-Pad der Schlüssel genauso groß sein muss wie die Datei, die zu verschlüsseln ist, erzeugen wir eine echte Kopie des Graustufenbildes, die wir später mit den Zufallsdaten füllen - somit haben wir die Struktur bereits gegeben. 

key = deepcopy(gray_img) 

Da wir unsere Ergebnisse nach der Verschlüsselung zur späteren Auswertung abspeichern wollen, erzeuge wir für die OR-, AND- und XOR-Verknüpfung analog zum Schlüssel Bildhüllen als echte Kopien des Originals. 

AND = deepcopy(gray_img) 
OR = deepcopy(gray_img) 
XOR = deepcopy(gray_img) 

Um für jedes Pixel in unserem Bild-Container einen Zufallswert zwischen 0 und 255 einzutragen, brauchen wir zunächst die Maße (also die Höhe und Breite) unseres Bildes. 

height, width = gray_img.shape[:2]

Die nachfolgende doppelte for-Schleife wird nun mehrfach benötigt. Zuerst erzeugen wir uns den Schlüssel. Hierfür laufen wir über jede Zeile und jede Spalte der Bildmatrix und erzeugen für jedes Pixel einen Zufallswert mit der Funktion randint von (inklusive) 0 bis (inklusive) 255. Das sind die bereits angesprochenen Graustufen. 

for i in range(height):
    for j in range(width):
        key[i,j] = randint(0,255)

Um nun das One-Time-Pad mit dem so entstandenen Schlüssel umzusetzen, laufen wir wieder die Schleife ab, doch diesmal ersetzen wir jeden Wert im AND-Container durch das Ergebnis der bitweisen AND-Operation des Originals (als Graustufenbild) und des Schlüssels. 

for i in range(height):
    for j in range(width):
        AND[i,j] = gray_img[i,j] & key[i,j]

Mit der Funktion imshow, der du einen Titel für das Fenster, in dem das Bild geöffnet werden soll und die Bildmatrix übergibst, kannst du dir das Ergebnis anzeigen lassen:

cv2.imshow('AND', AND)

Das sieht nicht wirklich sicher verschlüsselt aus, denn der Mann auf dem Bild ist immer noch einwandfrei zu erkennen! Die AND-Verknüpfung scheidet also als geeignete Verschlüsselungsfunktion für das One-Time-Pad aus.

Wie sieht es mit der bitweisen OR-Verknüpfung aus? Hierzu ersetzen wir den AND-Container durch den OR-Container und das logische & durch das logische Oder in Python (|):

for i in range(height):
    for j in range(width):
        OR[i,j] = gray_img[i,j] | key[i,j]

Wenn du dir das Ergebnis anzeigen lässt, erhältst das folgende Bild: 

Auch das sieht noch nicht wirklich gut verschlüsselt aus (nur etwas heller).

Unsere letzte Hoffnung ist also die XOR-Verknüpfung. Ersetze OR-Container durch den XOR-Container und das logische & durch das logische XOR in Python (^):

for i in range(height):
    for j in range(width):
        XOR[i,j] = gray_img[i,j] ^ key[i,j]

Das Ergebnis sieht, wenn du es ausgibst, dann wie folgt aus: 

Das ist sehr sicher! Oder erkennst du hier irgendwelche Muster? Wo ist der Mann auf dem Bild hin? Gibt es irgendwelche Anhaltspunkte, wie das Bild vorher aussah? Nein! Und das Tolle ist: Das Bild kann ohne den Schlüssel nicht entschlüsselt werden (egal, welches mathematische Modell du darauf wirfst - Voraussetzung ist natürlich, dass der verwendete Zufallszahlengenerator "echte" Zufallszahlen liefert). 

Wenn du das Bild wieder entschlüsseln willst, nimmst du das Ergebnis der Verschlüsselung als Input und wendest darauf erneut den Schlüssel mit der XOR-Operation an. Das kannst du mal selbst als kleine Aufgabe programmieren :) 


6. Quellcode

Hier kannst du dir den gesamten Quellcode herunterladen. 

import cv2
from random import *
from copy import deepcopy

img = cv2.imread('gunnar.jpg')
gray_img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

key = deepcopy(gray_img) 
AND = deepcopy(gray_img) 
OR = deepcopy(gray_img) 
XOR = deepcopy(gray_img) 

height, width = gray_img.shape[:2]

# Schlüssel erzeugen
for i in range(height):
    for j in range(width):
        key[i,j] = randint(0,255)

# AND
for i in range(height):
    for j in range(width):
        AND[i,j] = gray_img[i,j] & key[i,j]
cv2.imshow('AND', AND)
cv2.imwrite("GUNNAR_AND.jpg", AND) 
cv2.waitKey(0)

# OR
for i in range(height):
    for j in range(width):
        OR[i,j] = gray_img[i,j] | key[i,j]
cv2.imshow('OR', OR)
cv2.imwrite("GUNNAR_OR.jpg", OR) 
cv2.waitKey(0)

# XOR
for i in range(height):
    for j in range(width):
        XOR[i,j] = gray_img[i,j] ^ key[i,j]
cv2.imshow('XOR', XOR)
cv2.imwrite("GUNNAR_XOR.jpg", XOR) 
cv2.waitKey(0)