Manfred Börgens
Mathematische Probleme  # 41
Liste aller Probleme mit Lösungen
voriges Problem      nächstes Problem
zur Leitseite

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.

Kassette mit 1 Schloss

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:

Tabelle

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  MA  von der gleichen Länge wie  M . MA  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 & MA .
Aus praktischen Gründen, vor allem für einen einfachen Schlüsselaustausch, wird man Nachrichten blockweise verschlüsseln, d.h.  MA  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.  MA  aus den Blöcken  01101010 , so ist  n = 8 , und aus der Nachricht  M = 11110100 00110000 01  wird  f(M) = M & MA = 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



Zu Frage 1

A verschließt die Kassette mit einem Schloss, zu dem nur er einen Schlüssel hat, und verschickt sie an B. Dieser verschließt die Kassette mit einem weiteren Schloss, zu dem nur er einen Schlüssel besitzt, und schickt die Kassette zurück an A. A schließt sein eigenes Schloss auf und schickt die Kassette wieder an B. B kann nun die Nachricht lesen, nachdem er sein Schloss geöffnet hat.

3 Kassetten mit 1, 2, 3 Schloessern


Zu Frage 2

Das Verfahren aus 1 lässt sich leicht übertragen: A und B wählen unabhängig voneinander ihre (geheimen und privaten) Schlüssel  MA  und  MB . Der Ablauf der Kommunikation ist dann der folgende:

1. Botschaft: A versendet  M & MA an B.
2. Botschaft: B versendet  M & MA & MB  an A.
3. Botschaft: A versendet  M & MA & MB & MA = M & MB  an B. Dieser entschlüsselt diese Botschaft mit  M & MB & MB = M .


Zu Frage 3

Wenn es dem Lauscher gelingt, alle drei übermittelten Botschaften abzuhören, ist vor ihm nichts geheim zu halten. Denn die &-Addition der beiden ersten Botschaften gibt ihm den von B gewählten Schlüssel an die Hand und die &-Addition der beiden letzten Botschaften den Schlüssel von A:

(M & MA) & (M & MA & MB) = MB
(M & MA & MB) & (M & MB) = MA

Mit Hilfe dieser Schlüssel (einer würde schon reichen) kann der Lauscher aus der ersten oder dritten Botschaft  M  berechnen. Ist er nicht an den Schlüsseln, sondern nur an der Nachricht  M  interessiert, kann er auch gleich alle drei Botschaften &-addieren, denn deren &-Summe ist  M .

Die &-Addition ist also für diese Kommunikationsform ungeeignet. Dies liegt an einer prinzipiellen Schwäche dieser Verschlüsselungsoperation: Ein Lauscher, der eine Botschaft sowohl in ihrer ursprünglichen als auch in verschlüsselter Form kennt, kann daraus den Schlüssel errechnen, indem er die beiden &-addiert. (Setzt man  N = M & MA , so stehen dem Lauscher  N  und  N & MB  zur Verfügung, also kann er  MB  berechnen.) - Es gibt aber andere kryptographische Verfahren (u.a. das von Massey-Omura), die diese Schwäche nicht aufweisen und die "Kassettenmethode" erfolgreich imitieren.

Link zum Massey-Omura-Verfahren:   Uni Mainz



Stand 2005-12-04
voriges Problem   |    Liste aller Probleme mit Lösungen   |    nächstes Problem
Manfred Börgens   |    zur Leitseite