1.3. Grundlegende Terminologie#
Das allgemeine Verständnis von Kryptographie bezieht sich vor allem auf das klassische Anwendungsfeld dieser Wissenschaft, nämlich die Geheimhaltung von Informationen durch Verschlüsselung. Dies entspricht dem allgemeinen Ziel der Vertraulichkeit in Beispiel 1.1. Das Wort Kryptographie leitet sich aus dem altgriechischen Wörtern \(\kappa\rho\upsilon\pi\tau o\varsigma\) (kryptós), zu deutsch geheim, und \(\gamma\rho\alpha\varphi\epsilon\iota\nu\) (gráphein), zu deutsch schreiben, ab - und steht somit für die Wissenschaft von Geheimschriften.
Das Problem bei der Übermittlung von geheimen Daten lässt sich wie folgt abstrakt darstellen. Ein Sender \(A\) will eine Nachricht \(m\) (als Abkürzung für das englische Wort message) an einen Empfänger \(B\) übermitteln. Hierbei spielt es zunächst keine Rolle, ob es sich bei der Nachricht beispielsweise um einen Text, ein Bild, oder eine Datei handelt. Die Übermittlung der Nachricht soll jedoch so geschehen, dass ein Unbefugter \(O\) nichts damit anfangen kann, auch wenn er die übermittelte Nachricht \(m\) unterwegs abfangen kann.
Die grundlegende Idee der Kryptographie ist es, die Ausgangsnachricht \(m\) nicht direkt zu übertragen, sondern sie mit Hilfe einer Transformation \(f\) zu einer Nachricht \(c=f(m)\) (als Abkürzung für das englische Wort ciphertext) zu transformieren, d.h. zu verändern. Anschließend übermittelt \(A\) die transformierte Nachricht \(c\) an \(B\). Der Empfänger \(B\) muss die Umkehrtransformation \(f^{-1}\) kennen, um damit die ursprüngliche Nachricht \(m=f^{-1}(c)\) zu bestimmen.
Der entscheidende Punkt ist es nun, dass ein Unbefugter \(O\) nichts mit der verschlüsselten Nachricht \(c\) anfangen können soll, auch wenn er auf dem Übertragungsweg an die übermittelte Nachricht \(c\) kommt. Dies bedeutet die Transformation \(f\) muss so beschaffen sein, dass ein Unbefugter von \(c\) nicht auf \(m\) schließen kann. Insbesondere muss die Umkehrtransformation \(f^{-1}\) geheimgehalten werden.
Bemerkung 1.3 (Alice, Bob und Oscar)
In englischsprachiger Literatur werden häufig für den Sender \(A\) und den Empfänger \(B\) fiktive Charaktere mit Namen Alice und Bob verwendet. Eine fiktive dritte Person \(O\), die versucht den Inhalt der übermittelten Nachricht abzufangen wird häufig als Oscar bezeichnet. Diese Nomenklatur hat vermutlich seinen Ursprung in der ersten Verwendung dieser Namen in einem Paper von Rivest, Shamir und Adleman [RSA78], den Erfindern des RSA Kryptosystems.
Definition 1.3 (Terminologie in der Verschlüsselung)
Folgende Begriffe werden häufig verwendet, um das grundlegende Vorgehen in der Kryptographie zu beschreiben.
Die Ausgangsnachricht \(m\) wird in der Regel Klartext (im Englischen: plaintext) genannt.
Die Transformation \(f\) bezeichnet man als Verschlüsselungsfunktion oder auch Chiffrierfunktion. Das Anwenden der Funktion \(f\) bezeichnet man als verschlüsseln oder chiffrieren.
Die transformierte Nachricht \(c=f(m)\) wird verschlüsselte Nachricht, verschlüsselter Text, Geheimtext oder Chiffretext (im Englischen: ciphertext) genannt.
Das Anwenden der inversen Transformation \(f^{-1}\) nennt man entsprechend entschlüsseln.
Es ist klar, dass die Verschlüsselungsfunktion \(f\) nicht beliebig gewählt wird und diese insbesondere zwei grundlegende Eigenschaften erfüllen sollte:
\(f\) sei injektiv,
\(f\) sei parametrisierbar
Die Forderung nach Injektivität garantiert, dass jeder zulässige Chiffretext \(c\) einen eindeutigen Klartext \(m = f^{-1}(c)\) als Urbild haben muss. Dies garantiert, dass es bei der Entschlüsselung von Chiffretexten nicht zu Uneindeutigkeiten kommen kann und die inverse Transformation \(f^{-1}\) überhaupt wohldefiniert ist. Wollen zwei Personen sicher Nachrichten übermitteln, können sie sich eine gemeinsame Verschlüsselungsfunktion \(f\) ausdenken, die dann geheim gehalten werden muss. Hat man jedoch viele Personen, die paarweise geheim Informationen austauschen wollen, liegt gewöhnlich ein fest gewähltes Verschlüsselungsverfahren zugrunde, das nun allgemein bekannt sein kann, jedoch von einem geheimen Schlüssel \(K\) abhängt, d.h. die Verschlüsselungsfunktion \(f_K\) und die Umkehrfunktion \(f_K^{-1}\) werden parametrisiert. Die Sicherheit der Verschlüsselungsmethode hängt dann von der Geheimhaltung des Schlüssels \(K\) ab.
Eine Zusammenstellung von Regeln, wie man einen Text verschlüsselt und wieder entschlüsselt, bezeichnet man allgemein als Kryptosystem (zur Verschlüsselung).
Definition 1.4 (Kryptosystem)
Ein Kryptosystem (oder auch Verschlüsselungssystem) ist ein Tupel \((\mathcal{P}, \mathcal{C}, \mathcal{K}, \mathcal{E}, \mathcal{D})\), dass die folgenden Eigenschaften besitzt:
\(\mathcal{P}\) bezeichnet man als Klartextraum und ist eine Menge von möglichen Klartexten.
\(\mathcal{C}\) bezeichnet man als Chiffretextraum und ist eine Menge von möglichen Chiffretexten.
\(\mathcal{K}\) bezeichnet man als Schlüsselraum. Er enhält alle möglichen Schlüssel des Verschlüsselungssystems.
\(\mathcal{E}\) bezeichnet eine Familie von Verschlüsselungsfunktionen
\[\lbrace E_k \colon \mathcal{P} \rightarrow \mathcal{C}, \ k \in \mathcal{K}\rbrace.\]\(\mathcal{D}\) bezeichnet eine Familie von Entschlüsselungsfunktionen
\[\lbrace D_k \colon \mathcal{C} \rightarrow \mathcal{P}, \ k \in \mathcal{K}\rbrace.\]Für jeden Schlüssel \(e \in \mathcal{K}\) existiert ein Schlüssel \(d \in \mathcal{K}\), so dass für jeden Klartext \(m \in \mathcal{P}\) die folgende Gleichung gilt:
\[D_d(E_e(m)) \ = \ m.\]
Die in Definition 1.4 verwendeten Symbole leiten sich aus den entsprechenden englischen Bezeichnungen ab: \(\mathcal{P}\) wie plaintext, \(\mathcal{C}\) wie ciphertext, \(\mathcal{K}\) wie key, \(\mathcal{E}\) wie encryption und \(\mathcal{D}\) wie decryption.
In der Regel lassen sich Kryptosysteme nach Ihren inhärenten Eigenschaften und Charakteristiken klassifizieren. Ein Unterscheidungskriterium bezieht sich auf die Verwendung von Schlüsseln durch ein Kryptosystem.
Definition 1.5 (Symmetrische und asymmetrische Kryptosysteme)
Sei \((\mathcal{P}, \mathcal{C}, \mathcal{K}, \mathcal{E}, \mathcal{D})\) ein Kryptosystem. Wir nennen das Kryptosystem symmetrisch wenn sowohl Sender als auch Empfänger einer durch das Kryptosystem verschlüsselten Nachricht den gleichen Schlüssel \(k \in \mathcal{K}\) verwenden, d.h. zum Verschlüsseln und Entschlüsseln wird der selbe Schlüssel verwendet. Formal bedeutet dies, dass für alle Klartexte \(m \in \mathcal{P}\) und alle Schlüssel \(k \in \mathcal{K}\) gelten muss:
Sind die Schlüssel für die Ver- und Entschlüsselung jedoch verschieden, so sprechen wir von einem asymmetrischen Kryptosystem.
Wir werden uns innerhalb dieser Vorlesung zunächst mit klassischen Chiffrierverfahren beschäftigen, die alle durch symmetrische Kryptosysteme beschrieben werden. Anschließend werden wir dann ein modernes, asymmetrisches Kryptosystem kennenlernen und näher diskutieren.
Es stellt sich heraus, dass unterschiedliche Kryptosysteme unterschiedliche Sicherheitsgarantien geben und diese Sicherheit maßgeblich durch die zu Grunde liegenden mathematischen Eigenschaften des Kryptosystems bestimmt ist. Wir werden diese Eigenschaften in den folgenden Kapiteln näher untersuchen und versuchen unterschiedliche Kryptosysteme zu verstehen und deren Sicherheit zu bewerten.