« vorheriger Beitrag  · nächster Beitrag »

14.02.08 · 11:03 Uhr

Kryptographie I

Kategorie: Technik

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.

 

Autor: Thilo Kuessner· 0 Kommentare· Permalink· Trackback-URL

Tags: Cäsar-Chiffre· Entschlüsselung· Kryptographie· Verschlüsselung