In einer weiteren Serie wollen wir in ca. 14-tägigem Rhythmus die mathematischen Hintergründe einiger aktueller kryptographischer Verfahren erläutern, mit einem Schwerpunkt auf Public-Key-Verfahren.
Zur Bedeutung der Kryptographie im Internet-Zeitalter braucht man
wohl nicht viele Worte zu verlieren. Verschlüsselte, abhörsichere Übertragung ist beim Bezahlen im
Internet, bei der ‘elektronischen Unterschrift’, im Kreditkartenwesen, bei Zugangskontrolle und Copyright oder natürlich auch einfach bei der üblichen Kommunikation per Handy und e-Mail von eminenter Bedeutung.
Was ist das mathematische Setup bei der Kryptographie? Zunächst
fassen wir die zu kodierenden Botschaften als Elemente einer
mathematischen Menge auf, zum Beispiel identifizieren wir die 29
Buchstaben des Alphabets auf die naheliegende Weise mit den Zahlen
0,1,…,28. Diese Zuordnung fassen wir als gegeben auf, arbeiten von
jetzt ab also nur mit den Elementen dieser mathematischen Menge.
(Das ist jetzt noch nicht die Verschlüsselung, sondern nur eine
‘Mathematisierung’ des Textes.) Um diese Botschaft jetzt so zu
verschicken, daß ein eventueller Mitleser (der weiß, auf welche
Weise die Buchstaben den Zahlen 0,1,…,28 entsprechen) eine
abgefangene Botschaft nicht lesen kann, brauchen wir noch ein
Verschlüsselungsverfahren. Dieses ist eine Funktion f, die jedem
Element unserer Menge (etwa der Zahlen 0,1,…28) ein anderes
Element derselben Menge (also im Beispiel wieder eine Zahl zwischen
0 und 28) zuordnet.
(In Wirklichkeit verschlüsselt man heute nicht mehr die Buchstaben bzw. Zahlen, sondern ihre
einzelnen Bits. Aus mathematischer Sicht ändert das aber nichts an der Problemstellung.)
Die Entschlüsselung eines Textes besteht dann in der Berechnung der
Umkehrfunktion zu f. Wir brauchen also eine Funktion f, die sich
leicht berechnen läßt, für die aber die Umkehrfunktion nur schwer
berechenbar ist. (In Wirklichkeit ist es etwas komplizierter, weil
die Umkehrfunktion ja nur für einen zufälligen Mithörer schwer zu
berechnen sein soll, nicht für den Empfänger der Nachricht. Wie man
dieses Problem umgeht, erklären wir in Teil III dieser Serie.)
Das naheliegendste Verschlüsselungsverfahren wäre wohl folgendes:
wir wählen eine feste Zahl n, zum Beispiel n=3. Dann legen wir
unsere Verschlüsselungsfunktion fest als f(x)=x+n modulo 29, für n=3
also f(x)=x+3 modulo 29. Die Schreibweise ‘modulo 29’ bedeutet dabei
folgendes: falls der Wert von x+n die Zahl 29 überschreitet, ziehen
wir 29 vom Ergebnis ab. Also 26+3=0 modulo 29, 27+3=1 modulo 29,
28+3=2 modulo 29, und für alle kleineren x ist der Funktionswert
einfach x+3. Wenn wir das in das ursprüngliche Alphabet übersetzen,
ist also f(A)=D,f(B)=E,…,f(W)=Z,f(X)=A,f(Y)=B,f(Z)=C.
Dieses Verschlüsselungsverfahren ist natürlich leicht zu
entschlüsseln. (Es war übrigens schon den Römern bekannt und wird
wohl deshalb in der Fachliteratur als Cäsar-Chiffre
bezeichnet.) Die Umkehrfunktion ist einfach x-n modulo 29, in
unserem Fall also x-3 modulo 29. (Dies ist ähnlich zu verstehen wie
im vorigen Abschnitt, also etwa 2-3=28 modulo 29.)
Nicht nur, daß bei gegebenem f die Umkehrfunktion leicht berechnet
werden kann, schlimmer noch: selbst wenn ein Mithörer nicht weiß,
welche Zahl n in der Definition von f(x)=x+n modulo 29 verwendet
wurde, kann er dies anhand des Textes leicht herausbekommen.
Bekanntlich ist ja E der am häufigsten vorkommende Buchstabe in
deutsch- oder englisch-sprachigen Texten. Man muß also nur zählen,
welcher Buchstabe im verschlüsselten Text am häufigsten vorkommt,
und kann dann davon ausgehen, daß dieser Buchstabe f(E) ist. Wenn
etwa im verschlüsselten Text H am häufigsten vorkommt, wird wohl
f(E)=H bzw. f(5)=8 sein, woraus man sofort sieht, daß n=3 ist. Und
damit kann man dann den gesamten Text entschlüsseln. Natürlich muß
die aufgefangene Botschaft lang genug sein, damit wirklich mit hoher
Wahrscheinlichkeit der Buchstabe E im Originaltext am häufigsten
vorkam. (Schwieriger wäre es schon bei spanisch- oder italienisch-sprachigen Texten.
Auch dort ist zwar das E der häufigste Buchstabe. Aber das A, und im Italienischen auch das I, kommen mit fast derselben Häufigkeit vor. Hier müßte man also mehrere Möglichkeiten ausprobieren.)
Die Cäsar-Chiffre ist also kein sicheres Verschlüsselungsverfahren und wird
deshalb natürlich auch nicht verwendet. Verschlüsselungsverfahren,
die heute tatsächlich verwendet werden und schwierige Mathematik
(z.B. die Theorie der elliptischen Kurven) benutzen, werden in
weiteren Teilen dieser Serie besprochen werden.
Letzte Kommentare