Kryptologie

 

Kryptologie ist die Wissenschaft vom Geheimhalten von Geheimnissen. Sie bietet Methoden an, sogenannte Geheimschriften, um die Vertraulichkeit von Daten sicherzustellen. Wir unterscheiden zwischen den folgenden Teilgebieten der Kryptologie:

1. Kryptografie (Verschlüsselung von Daten)
2. Kryptoanalyse (Analyse von verschlüsselten Daten)

Die Anfänge der Kryptologie verlieren sich in der Geschichte, aber nachweislich wurde bereits im 5. Jahrhundert vor Christi die Skytala von den Spartanern eingesetzt. Bei der Skytala handelt es sich um einen Stab (Zylinder) eines bestimmten Durchmessers, um den ein schmaler Papyrusstreifen gewickelt wird. Die Nachricht wird längs des Stabes auf den aufgewickelten Papyrusstreifen geschrieben. Auf dem abgewickelten Streifen stehen die Zeichen dann in permutierter Anordnung, und der Klartext ist nicht ohne weiteres abzulesen.


1. Klassische Kryptologie

Hierunter versteht man Verfahren, welche weitestgehend manuell oder nur mit einfacher maschineller Unterstützung durchgeführt wurden. Es kommen ausschließlich symmetrische Verfahren mit nur einem Schlüssel zum Einsatz.

Beispiele:

 

 

2. Moderne Kryptologie

Mit dem Aufkommen des Computers eröffneten sich der Kryptologie andere Möglichkeiten und Einsatzbereiche. Es zeigte sich, dass auch die Vigenere-Verschlüsselung nicht sicher war. Mit dem Computer konnten auch ganz andere Verfahren zur Verschlüsselung eingesetzt werden, die manuell nicht nutzbar wären.

2.1 Symmetrische Verfahren


Bei den symmetrischen Verfahren gibt es nur einen Schlüssel, der zum Ver- und Entschlüsseln verwendet wird. Es gibt grundsätzlich zwei Probleme:

Die heutigen Algorithmen verschlüsseln nur Zahlen. Daher müssen Buchstaben zunächst in Zahlen umgewandelt werden, was aber kein Problem darstellt. Meist wird ein Block von 64 Binärziffern verschlüsselt. Die Ziffern (0 oder 1) werden dabei nach komplizierten Regeln mehrfach ersetzt und durcheinander gewirbelt.
Bekannte Algorithmen sind:

Die Inhalte von Nachrichten lassen sich durch moderne symmetrische Verschlüsselungsverfahren wie DES und BLOWFISH sehr gut geheim halten, aber die Übermittlung der Schlüssel ist umständlich und riskant.

2.2 Public-Key-Verfahren

Vor mehr als einem Vierteljahrhundert wurde die Kryptographie durch ein revolutionär neues Konzept total verändert. Im Jahr 1976 präsentierten Whiteld Diffe und Martin E. Hellman in ihrer berühmten Arbeit " New Directions in Cryptography" das Konzept der asymmetrischen oder Public-Key-Verschlüsselung.

Dabei werden zwei verschiedene Schlüssel benutzt. Der so genannte "öffentliche Schlüssel" kann auch über unsichere Wege zum Versender der Nachrichten gelangen. Ein Entschlüsseln der Nachricht ist aber allein mit dem - beim Empfänger verbliebenen - "privaten Schlüssel" möglich.


Das Konzept: Alice möchte Bob eine verschlüsselte Nachricht schicken. Diesmal verschlüsselt sie die Daten jedoch nicht wie gewohnt mit einem bereits festgelegten Schlüssel, sondern mit Bobs öffentlichem Schlüssel. Bob selbst hat seinen eigenen, nichtöffentlichen (privaten) Schlüssel. Nur mit diesem gelingt es ihm, die verschlüsselten Daten zu lesen. Bob hat also zwei Schlüssel: einen öffentlichen (public key) und einen privaten, geheimen (private key). Aufgrund dieses Konzepts bezeichnet man asymmetrische Kryptographie häufig auch als Public-Key-Kryptographie.

2.3 Das RSA-Verfahren

Das RSA Kryptosystem ist das erste praktisch einsetzbare Public-Key-Verfahren, welches realisiert wurde. Es wurde 1977 entwickelt und ist nach den Initialen seiner Erfinder, Rivest, Shamir und Adleman, benannt. kann. Die Sicherheit von RSA liegt in der Schwierigkeit begründet, (sehr) große Zahlen zu faktorisieren. Diese großen Zahlen sind Produkte zweier Primzahlen p und q, d. h. m = pq. Man geht davon aus, dass es schwer ist, aus einem gegebenem Produkt m die Primfaktoren p und q zu ermitteln.
In diesem Zusammenhang wird oft der Begriff "Einwegfunktion" verwendet. Die eine Richtung, hier das Multiplizieren zweier Zahlen, ist einfach möglich. Die umgekehrte Richtung, also das Zerlegen eines Produktes in seine Faktoren, ist sehr viel schwieriger und erfordert viel mehr Zeit.

Die Schlüsselerzeugung

Zur Anwendung wählt man zufällig zwei Primzahlen p und q, von denen nur das Produkt m=pq bekannt gegeben wird. Mit den Zahlen p und q konstruiert man zwei spezielle Exponenten, einen "öffentlichen" Schlüssel e und einen "privaten" d. Für den öffentlichen Schlüssel e muss gelten:

ggT(e, (p-1)(q-1)) = 1

Die Zahl e muss also teilerfremd zum Produkt (p-1)(q-1) sein. Meist wählt man für e einen eher kleineren Wert. Das Paar (m,e) bildet dann den öffentlichen Schlüssel.

Zu diesem Schlüssel e wird das "modular Inverse" d berechnet, so dass gilt:

(e * d) mod ((p-1)*(q-1)) = 1

Das Paar (m,d) bildet dann den privaten Schlüssel.

Zahlenbeispiel: p = 7, q = 13 Þ m = 91, e = 5, d = 29.


Man beachte, dass e teilerfremd zum Produkt 72 = 6 · 12 ist.


Das Verschlüsseln


Das RSA-Verfahren verschlüsselt und entschlüsselt nur Zahlen; daher muss der Klartext mit einem öffentlich bekannten Alphabet in eine Zahlenfolge übersetzt werden. Ist M die Klartextzahl, so erhält man die verschlüsselte Zahl C durch die modulares Potenzieren:

C = M e mod m.

Soll mit dem öffentlichen Schlüsselpaar m = 91 und e = 5 beispielsweise die Zahl 65 verschlüsselt werden, so berechnet man C = 65 5 mod 91 = 39.

Das Entschlüsseln

Hierzu wird das private Schlüsselpaar m = 91 und d = 29 benötigt. Die Klartextzahl erhält man wieder durch modulares Potenzieren:

M = C d mod m.

Mit den obigen Zahlen ergibt sich M = 39 29 mod 91 = 65.

In der Praxis werden sehr große Primzahlen mit mehr als 100 Stellen gewählt. Außerdem wird ein Text in größere Blöcke zerlegt, die jeweils in eine relativ große Klartextzahl M umgewandelt werden, damit keine monoalphabetische Verschlüsselung entsteht.

Digitale Signatur

Was geschieht, wenn ich als Besitzer des privaten Schlüssels d diesen zum Verschlüsseln benutzt? Im Zahlenbeispiel: C = 65 29 mod 91 = 39.
Nun, dann kann jeder mit meinem öffentlichen Schlüssel e die Nachricht entschlüsseln. M = 39 5 mod 91 = 65.
Macht dies Sinn? Ja, denn wenn der Empfänger mit meinem öffentlichen Schlüssel eine Nachricht entschlüsseln kann, so kann er sicher sein, dass die nur von mir mit meinem privaten Schlüssel verschlüsselt werden konnte. So lässt sich das asymmetrische RSA-Verfahren zu einer digitalen Unterschrift nutzen!

2.4 Schlüsseltausch nach Diffie-Hellmann

Diffie-Hellman ist ein Algorithmus zum sicheren Schlüsselaustausch über einen unsicheren Kanal. Mit diesem Algorithmus wird bei zwei Partnern ein gemeinsamer Schlüssel erzeugt, den die Partner zur symmetrischen Verschlüsselung benutzen können. Es handelt sich also nicht um ein Verfahren zur Verschlüsselung von Nachrichten. Der 1976 vorgestellte Algorithmus ist ein Meilenstein für die Kryptologie, war es doch der erste Public-Key Algorithmus.

Für zwei Parteien A und B läuft die Schlüsselerzeugung wie folgt ab:

Die Partner A und B einigen sich gemeinsam auf eine große Primzahl p, für die zusätzlich gelten soll, dass (p-1)/2 ebenfalls eine Primzahl ist. Weiter einigt man sich auf eine Zahl g die kleiner p ist. Beide Zahlen können über den unsicheren Kanal ausgetauscht werden.

Jeder Partner überlegt sich einen großen, ganzzahligen Wert x, welche jeweils den geheimen, privaten Teil des Schlüssels darstellen. Hieraus berechnet jeder Partner sein Y, welches er dem anderen Partner zusenden kann. Y berechnet sich wie folgt:

Y = g x mod p

Mit dem eigenen x und dem Y des Partners kann nun jeder den gemeinsamen Schlüssel K berechnen, der aufgrund der Kommutativität der Potenz in beiden Fällen gleich ist:


K = Y x mod p

Der Angreifer kann nun g und p und die beiden Y kennen, ohne ein x ist ihm die Berechnung des Schlüssels aber nicht möglich, es sei denn es gelingt ihm, die Zahl x, den diskreten Logarithmus aus Y zu ermitteln.

Zahlenbeispiel: p = 59, g = 43

Geheimzahlen xA = 17 Þ YA = 43 17 mod 59 = 38
xB = 28 Þ YB = 43 28 mod 59 = 48

Mit den öffentlich übermittelten Y-Werten berechnet jeder den gemeinsamen Schlüssel k.

A: k = 48 17 mod 59 = 45
B: k = 38 28 mod 59 = 45.

In der Praxis werden Zahlen mit etwa 200 Stellen verwendet. Das modulare Potenzieren ist eine Einwegfunktion: Das Potenzieren ist ziemlich einfach, umgekehrt lässt sich der Exponent x aber nur durch Probieren finden, was bei großen Zahlen äußerst zeitraubend ist.
Durch dieses Verfahren ist es also nicht mehr erforderlich, für ein symmetrisches Verschlüsselungsverfahren einen gemeinsamen Schlüssel auf einem sicheren Weg zu übertragen. Vielmehr kann in aller Öffentlichkeit ein gemeinsamer Schlüssel erzeugt werden!

W. Steffen, März 2004


Quellen:

Hans-G. Mekelburg: Verschlüsselte Botschaften, Kryptologie: Eine Einführung, 2002 (sehr gute Einführung!)

Rudolf Kippenhahn: Verschlüsselte Botschaften: Geheimschrift, Enigma und Chipkarte; 2. Auflage (Reinbek: Rowohlt, 1998) 362 S.

Simon Singh: Geheime Botschaften, Die Kunst der Verschlüsselung von der Antike bis in die Zeiten des Internet. (dtv, 2001) 458 S.

zurück  home