Visuelle Kryptografie ist eine relativ neue Spielart der Verschlüsselung von Bildern oder anderem gedrucktem Material, die 1994 von Moni Naor und Adi Shamir entwickelt wurde.

In this paper we consider a new type of cryptographic scheme, which can decode concealed images without any cryptographic computations. The scheme is perfectly secure and very easy to implement. We extend it into a visual variant of the k out of n secret sharing problem, in which a dealer provides a transparency to each one of the n users; any k of them can see the image by stacking their transparencies, but any k-1 of them gain no information about it.

Im Grunde genommen geht es um folgendes: Ein Bild, also der Klartext, wird dergestalt verschlüsselt, dass man es auf zwei (oder mehr) durchsichtige Folien aufteilt, die jede für sich genommen keinerlei Informationen über den Inhalt des Bildes enthalten und nicht anders aussehen als „White Noise“. Zur Entschlüsselung werden die Folien übereinander gelegt und das ursprüngliche Bild wird sichtbar.

Das Schöne an der visuellen Kryptographie ist, dass man den Klartext (das ursprüngliche Bild) wiederherstellen kann, ohne Berechnungen anstellen zu müssen, dadurch minimiert man Fehler und spart Zeit. Das Verschlüsseln hingegen, also das Erstellen der Folien, ist per Hand aufwändig, kann aber natürlich auch vom Rechner erledigt werden.

In ihrem Aufsatz betrachten Naor und Shamir die visuelle Kryptografie als eine Variante der Geheimnisteilung, bei der ein Geheimnis, zum Beispiel eine Zahl, unter mehreren Beteiligten n so aufgeteilt werden soll, dass kein Beteiligter ohne die anderen das Geheimnis rekonstruieren kann. Es gibt Varianten, bei der nur eine Teilmenge k der Beteiligten erforderlich sind, um das Geheimnis zu erfahren, das sogenannte k von n geteilte Geheimnis.

Von den beiden erstellten Folien kann man das eine auch als das verschlüsselte Originalbild betrachten (Chiffretext), das andere als den dazugehörigen Schlüssel. In der Praxis könnte sich ein Geschäftsmann auf Reisen den Chiffretext per Fax oder Post zusenden lassen, dann bräuchte er nur noch den passenden Schlüssel, den er als transparente Folie mit sich führt, darüber legen, um den Klartext zu erhalten. In diesem Sinne funktioniert visuelle Kryptografie ähnlich wie ein One-Time Pad, wenn jeder Klartext mit einem anderen Schlüssel verschlüsselt wird.

Ein Beispiel

In seinem Aufsatz „Eine Einführung in die visuelle Kryptografie“ beschreibt Andreas Klein ein mögliches Szenario, wie visuelle Kryptografie eingesetzt werden könnte, um Betrug zu verhindern:

Man stelle sich die folgende Situation vor: Nach einigen Einkäufen mit der Geldkarte stellt man überrascht fest, dass mehrere Hundert Euro zu viel von der Karte abgebucht wurden. Eine genauere Überprüfung zeigt, dass der Zigarettenautomat um die Ecke statt jeweils 5 EUR immer 50 EUR für eine Schachtel verlangt haben muss. Dummerweise ist die Zahlung mit einer Geldkarte anonym und da der Automatenbetreiber schlau genug war den manipulierten Automaten auszutauschen, bevor der Betrug entdeckt wurde, kann der Betrug nicht mehr nachgewiesen werden. Der Betrogene bleibt auf seinem Schaden sitzen.

Obwohl ein solcher Betrug bisher noch nicht vorgekommen ist, wäre er durchaus möglich. Das Problem liegt darin, dass die Bezahlung mit einer Geldkarte am Automaten ähnlich ist, als würde man dem Verkäufer an einer Kasse seinen Geldbeutel geben, damit er sich den fälligen Betrag selber nimmt. Die Unsicherheit dieses Vorgehens ist augenfällig. Was kann man also tun, um das Bezahlsystem sicherer zu gestalten?

Die Antwort, natürlich: Visuelle Kryptografie. Folgendes Verfahren ist denkbar:

1. Der Automat sendet an die Geldkarte eine Information, wie viel Geld abgebucht werden soll.

2. Die Geldkarte erstellt mit dieser Information ein Bild und sendet es an den Automaten zurück, der das Bild auf einem Display anzeigt:

   

3. Als Zubehör zur Geldkarte hat der Besitzer eine Folie, die über das auf dem Display des Automaten angezeigte Bild gelegt wird:

   

4. Zusammen ergibt sich das fertige Kontrollbild:

   

So, wie oben beschrieben, ist dieses Verfahren noch nicht wirklich praxistauglich. Benutzt man zum Beispiel in Schritt 3 immer dieselbe Folie, hat man dasselbe Problem wie auch bei einem One-Time-Pad: Wird derselbe Schlüssel mehrfach verwendet, hat es ein Angreifer leicht, an die verschlüsselte Information heranzukommen. Auf der anderen Seite kann der Automat nur aus dem Bild, dass er in Schritt 2 von der Geldkarte erhält, keine Rückschlüsse auf das fertige Kontrollbild erzielen, und es auch nicht gezielt manipulieren.

Das Prinzip

Zunächst soll die Funktionsweise der visuellen Kryptografie an Hand einer einfachen Variante eines schwarz-weiß Bildes als unserem Klartext erläutert werden. Dieses Originalbild, das zu teilende Geheimnis, besteht aus einer Ansammlung von weißen und schwarzen Pixeln, wie im Beispiel zu sehen:

Für die Erstellung der zwei einzelnen Folien betrachtet man nun jedes Pixel für sich, und jedes Pixel muss in die zwei Elemente aufgeteilt werden (im Original als „Share“ bezeichnet), die übereinandergelegt wieder das Originalpixel ergeben.

Für jedes Pixel wählt man dazu zuerst zufällig ein Element aus der gezeigten Liste aus, dieses stellt den ersten Teil dar. Handelt es sich um ein weißes Pixel, wählt man als zweiten Teil das gleiche Element. Bei einem schwarzen Pixel wählt man das dazugehörige Komplementärelement.

Somit wird jedes Pixel des Klartextes durch zwei Elemente dargestellt, die jedes für sich wiederum aus zwei weißen und zwei schwarzen Subpixeln bestehen. Die Gesamtheit aller Elemente auf einer einzelnen Folie wirkt dadurch alleine betrachtet grau. Legt man zwei gleiche Elemente übereinander, sieht man nun wiederum zwei weiße und zwei schwarze Suibpixel (steht für ein weißes Pixel des Klartextes), legt man zwei komplementäre Elemente übereinander, sind sie komplett schwarz (steht für ein schwarzes Pixel des Klartextes).

Dieses Vorgehen sei beispielhaft für je ein weißes und schwarzes Pixel des Originalbildes dargestellt, wobei ich der Einfachheit halber die Anzahl möglicher Elemente von sechs (siehe oben) auf zwei reduziere, und nur die horizontalen Elemente verwende.

Originalpixel	Zufällige Auswahl	Element 1	Element 2	Kombination beider Elemente
	50% Chance
	50% Chance
	50% Chance
	50% Chance

Hat man diese Aufteilung für jedes Pixel des ursprünglichen Bildes gemacht, hat man die zwei Teile des Geheimnisses generiert:

sowie

Legt man diese beiden Bilder übereinander, erhält man wieder den Klartext:

Eines ist beim zusammengesetzten Klartext zu erkennen - das vorher rein schwarz-weiße Bild erscheint jetzt in schwarz-grau. Und um es gleich vorweg zu nehmen: Mit zunehmender Anzahl Folien wird mehr Kontrast verloren gehen. Die Ursache ist einfach, dass das weiße Pixel hier in vier Subpixel zerlegt wurde, von denen zwei weiß und zwei schwarz sind. Da die Pixel naturgemäß klein sind, verschwimmt das zu Grau.

Verallgemeinerung

Mit einem relativ simplen manuellen Verfahren, das auch dem oben genannten Aufsatz von Andreas Klein entnommen ist, kann man nun für beliebige n eine Anzahl von n Folien erstellen, die alle übereinander gelegt das geheime Bild zeigen.

Im ersten Schritt unterteilt man jedes Pixel des zu verschlüsselnden Bildes in ein Element mit 2^n-1 Subpixeln. Möchte man also für ein Bild drei Folien erstellen, benutzt man Elemente mit 2² = 4 Subpixeln.

(Anmerkung: Beim Beispiel unter „Das Prinzip“ habe ich auch Elemente mit vier Subpixeln verwendet, obwohl bei zwei Folien jedes Element nur 2¹ = 2 Subpixel haben müsste. Tatsächlich ist es so, dass die Formel 2^n-1 die minimal benötigte Anzahl an Subpixeln pro Element ergibt. Wenn die Elemente allerdings nicht quadratisch sind, wird sich aber das Bildverhältnis ändern und das Bild verzerren.)

Im zweiten Schritt nummeriert man die Subpixel eines Elements. Um ein schwarzes Pixel zu verschlüsseln, beschriftet man die Subpixel des Elementes in beliebiger Reihenfolge mit den Teilmengen ungerader Mächtigkeit von {1 ... n}. Für ein weißes Pixel beschriftet man die Subpixel mit den Teilmengen gerader Mächtigkeit.

(Anmerkung: Die Mächtigkeit einer Teilmenge beschreibt in gewissem Sinne die Anzahl der Elemente pro Teilmenge. Ungerade Mächtigkeit heißt, die Teilmenge hat eine ungerade Anzahl Elemente. Gerade Mächtigkeit heißt, die Teilmenge hat eine gerade Anzahl Elemente (die leere Menge Ø zählt auch dazu).

Zum Schluss färbt man alle Subpixel der Folie i, in deren Beschriftung i vorkommt, schwarz:

	Folie 1		Folie 2		Folie 3		Gesamt
Schwarz		+		+		=
Weiß		+		+		=

Beim Aufeinanderlegen aller Folien sieht man entweder genau ein weißes Pixel (steht für Weiß) oder keines (steht für Schwarz). Fehlen Folien, bleiben Subpixel frei und das zu schützende Geheimnis bleibt geheim.

Es ist übrigens deutlich zu sehen, dass – wie oben angekündigt – der Kontrast zwischen den „schwarzen“ und „weißen“ Pixeln weiter abgenommen hat. Ein weißes Originalpixel wird bei drei Folien durch ein weißes und drei schwarze Subpixel dargestellt.

Zum Schluss...

Dieser Artikel sollte als Einführung in die visuelle Kryptographie dienen. Über das hinaus, was ich hier gezeigt habe, gibt es noch weitere Möglichkeiten, Nachrichten visuell zu verschlüsseln. Zum Beispiel kann man ein Geheimnis derart in n Folien aufteilen, dass man nur eine bestimmte Anzahl k kleiner n davon benötigt, um das Geheimnis zu rekonstruieren. Die Verschlüsselung von farbigen Bilder wäre auch möglich.

Wer sich eingehender mit diesem Thema beschäftigen möchte, findet unten und im Download-Bereich einige weitere Informationen und Anlaufstellen.

Weiterführende Literatur

Andreas Klein hat ein ganzes Buch über visuelle Kryptografie geschrieben:

• Andreas Klein, Visuelle Kryptographie (Springer-Lehrbuch), Springer-Verlag, 2007

Ich kenne das Buch (noch) nicht. Es ist aber bei Amazon.de erhältlich.

Links

• Doug Stinson's Visual Cryptography Page
• Visual Cryptography Applet bei der Uni Regensburg (Java Applet, mit dem man Bilder verschlüsseln kann)