Problem des Monats Mai 2004

Die geheime Botschaft in der Kassette.
Dazu die Analogie für Rechnernetzwerke. Genial! Aber ...

A und B möchten vertrauliche Nachrichten auf dem Postweg austauschen. Sie wohnen zu weit auseinander, um sich zu treffen. Sie möchten sicherheitshalber keine Nachrichten über das Telefon oder über unverschlüsselte E-Mails senden. Sie vertrauen aber - etwas altmodisch - darauf, dass Briefe und Pakete zuverlässig beim Adressaten ausgeliefert werden. Allerdings befürchten sie eine heimliche Öffnung der Poststücke, die einem "Lauscher" den Inhalt zugänglich machen würde, ohne dass A oder B dies bemerken. Sie einigen sich deshalb auf stabile Stahlkassetten, die mit Vorhängeschlössern gesichert werden können.

Würde A eine solche Kassette mit einer vertraulichen Nachricht an B schicken, könnte B die Kassette nicht öffnen, da er keinen Schlüssel für das Schloss hat. Zweitschlüssel per Post zu schicken, kommt natürlich nicht in Frage, denn ein Lauscher könnte davon ein Duplikat herstellen. Aber A und B kennen einen anderen Weg!

Wir halten einen Moment inne. Es wird also eine Fragestellung aus der Kryptographie behandelt. Die Versendung von Botschaften in Kassetten ist ein klarer Fall eines symmetrischen Verschlüsselungsverfahrens, wenn auch der Empfänger das Schloss mit einem eigenen Schlüssel öffnen kann. Bevor wir uns wieder dem Problem von A und B zuwenden, bei dem es ja keine identischen Schlüssel gibt, sollen diese symmetrischen Verfahren kurz erläutert werden.

Der Autor einer Nachricht verwendet einen Schlüssel, um diese Nachricht nicht im Klartext, sondern in einer geheimen Form an den Empfänger versenden zu können; dieser kennt den Schlüssel und entschlüsselt die übermittelte Botschaft wieder, um den Klartext lesen zu können. Die Symmetrie des Verfahrens liegt in zwei Punkten begründet: Absender und Empfänger müssen sich vorab über den Schlüssel verständigt haben, und die Algorithmen für die Ver- und Entschlüsselung sind identisch oder voneinander ableitbar.

Formaler Ablauf symmetrischer Verschlüsselungsverfahren:

Die Verschlüsselungsfunktion  f  ist dabei nicht eindeutig. Für jedes symmetrische Verschlüsselungsverfahren gibt es eine große Familie dieser Funktionen, die zwar alle die gleiche charakteristische Struktur haben, sich aber unterscheiden durch den in  f  eingebundenen Schlüssel.

Beispiel 1
A steckt seine Nachricht  M  in eine Kassette und verschließt diese mit einem Schloss oder mehreren Schlössern (Verschlüsselung  f ). Kassette mit Inhalt entspricht dann  f(M) . A versendet die Kassette an B. Die Entschlüsselung  f^-1  ist das Öffnen der Kassette und die Entnahme der Nachricht  M . Die Symmetrie des Verfahrens liegt auf der Hand: A und B haben vorab sichergestellt, dass sie beide (identische) Schlüssel für die Kassette besitzen.

Beispiel 2
Nachrichten lassen sich in der Regel leicht als Folge von Nullen und Einsen darstellen, und der Einfachheit halber wollen wir voraussetzen, dass   M  in dieser Form geschrieben ist. Eine einfache und weit verbreitete Verschlüsselung arbeitet mit der binären Addition ohne Übertrag, die wir hier &-Addition nennen wollen. & ist kommutativ und assoziativ, und  M & M  besteht nur aus Nullen.
Zur Verschlüsselung seiner Nachricht  M  &-addiert A zu  M  eine feste binäre Zahl  M_A  von der gleichen Länge wie  M . M_A  ist der Schlüssel. Ein Vorteil dieses Verfahrens liegt darin, dass Ver- und Entschlüsselung vollkommen identisch sind, d.h.  f = f^-1  und  f(M) = f^-1(M) = M & M_A .
Aus praktischen Gründen, vor allem für einen einfachen Schlüsselaustausch, wird man Nachrichten blockweise verschlüsseln, d.h.  M_A  besteht dann aus identischen Blöcken einer festen Länge  n  (der letzte Block darf natürlich weniger als  n  Ziffern haben und wird dann einfach abgeschnitten). Besteht z.B.  M_A  aus den Blöcken  01101010 , so ist  n = 8 , und aus der Nachricht  M = 11110100 00110000 01  wird  f(M) = M & M_A = 10011110 01011010 00 .

Ein Nachteil symmetrischer Verschlüsselungsverfahren ist die Notwendigkeit des Schlüsselaustauschs zwischen A und B. Oft kommt ein Treffen der beiden wegen der Entfernung nicht in Frage, also muss die Vereinbarung über den zu verwendenden Schlüssel über einen Kommunikationskanal erfolgen. Diese Kommunikation ist aber nicht sicher, sie könnte "belauscht" werden. Außerdem ist es lästig und höchst unsicher, wenn die Mitglieder von Netzwerken untereinander vertraulich kommunizieren wollen und dann jeweils alle über einen gemeinsamen Schlüssel (oder eine Schlüsseländerung) informiert werden müssen bzw. wenn die Mitglieder sich paarweise über eigene Schlüssel zu verständigen haben. Eine moderne (und mathematisch sehr interessante) Lösung dieses Problems bieten asymmetrische Verschlüsselungsmethoden, aber um diese soll es hier nicht gehen.

Es gibt für die beiden beschriebenen Beispiele eine "Erweiterung", die die Nachteile symmetrischer Verschlüsselungen vermeidet. Damit kommen wir zum anfangs gestellten Problem zurück. Ein kleiner Tipp vorweg: Der Kommunikationsweg wird dadurch länger. Gesucht sind also zwei kryptographische Methoden, die sich der "Kassettenmethode" bzw. der &-Addition bedienen, aber bei denen A und B keinen Schlüsselaustausch vornehmen müssen.

Frage 1
Wie lässt sich das vertrauliche Versenden von Nachrichten in abschließbaren Kassetten (Beispiel 1) so organisieren, dass Absender und Empfänger nicht wegen der verwendeten Schlüssel in Kontakt treten müssen?

Frage 2
Wie lässt sich das kryptographische Verfahren aus Beispiel 2 so anwenden, dass Absender und Empfänger nicht wegen der verwendeten Schlüssel in Kontakt treten müssen?

Ausnahmsweise ist es bei diesem Monatsproblem möglich, sich einen Teil der Lösung sofort anzusehen. Es soll eine Antwort auf Frage 1 angegeben werden, die eine ganz analoge Antwort auf Frage 2 nahe legt. Diese analogen Lösungen liegen der Frage 3 zugrunde.

Falls Sie die Fragen 1 und 2 beantworten konnten, können Sie diesen Hinweis überspringen: Lösung zu Frage 1

Frage 3
Diese Lösung zu Frage 1 ermöglicht eine weitgehend sichere Geheimhaltung. Aber leider, leider: Die analoge Lösung zu Frage 2 schützt die Vertraulichkeit nicht. Sie ermöglicht es Lauschern, die die Kommunikation abhören, sowohl die Nachrichten als auch die verwendeten Schlüssel zu berechnen, ohne dass A oder B dies bemerken. Warum?

Lösung