Fachbeitrag «Kryptografie»

Von den klassischen Verschl├╝sselungsverfahren bis zur Public-Key-Kryptografie

Mit Kryptografie war ursprünglich die Wissenschaft der Verschlüsselung gemeint. Heute umfasst sie allgemein die  Informationssicherheit und die Widerstandsfähigkeit gegen Manipulation und unbefugtes Lesen.

  • Kryptologie: Wissenschaft vom Entwurf, der Anwendung und der Analyse von kryptografischen Verfahren
  • Kryptografie: Wie kann eine Nachricht ver- und entschlüsselt werden?
  • Kryptoanalyse: Wie sicher ist ein Verschlüsselungsverfahren?

1. Symmetrische Verschlüsselungsverfahren

1.1 ROT-13

Beim 26 Buchstaben zählenden Alphabet hat die ROT-13 Rotationschiffre den Vorteil, dass derselbe Algorithmus zum ver- bzw. entschlüsseln verwendet wedern kann.

1.2 Vigenèreverschlüsselung

Zur Verschlüsselung eines Klartextes wird ein Schlüssel benötigt. Idealerweise ist dieser gleich lang wie der Klartext. Ist der Schlüssel kürzer als der Klartext, wird dieser einfach wiederholt. Die chiffrierten Buchstaben ermittelt man mit dem Vigenère-Quadrat, einer quadratischen Anordnung von untereinander stehenden verschobenen Alphabeten. Dazu sucht man den Kreuzungspunkt der durch den jeweiligen Schlüsselbuchstaben gekennzeichneten Zeile und der Spalte des Quadrats, die oben durch den Klartextbuchstaben gekennzeichnet ist. Der Empfänger benutzt zum Entschlüsseln der Nachricht denselben Schlüssel wie der Absender. Er kann durch Umkehren des Verschlüsselungsverfahren den Klartext zurückgewinnen.

Das komplette Vigenère-Quadrat:

1.3 Die XOR-Stromchiffre

Bei der Stromchiffre werden Klartext Bit für Bit bzw. Zeichen für Zeichen XOR-ver- bzw. entschlüsselt. Sender und Empfänger benutzen denselben Schlüssel.

1.4 Vor- und Nachteile von symmetrischen Verschlüsselunsverfahren

  • Pro: Schlüssel sind «kürzer» als Nachricht
  • Pro: Sicherer Kanal für «kurzen» Schlüssel ist einfacher zu haben als sicherer Kanal für Nachricht
  • Kontra: Sender und Empfänger müssen gleichen Schlüssel haben
  • Kontra: Schlüsseltausch benötigt sicheren Kanal
  • Kontra: Falls sicheren Kanal vorhanden könnte ja die Nachricht selbst darüber übertragen werden
  • Kontra: Schlüsselmanagement aufwändig: S=N*(N-1)/2 wobei S=Schlüssel und  N=Teilnehmer - Die Schlüsselzahl wächst somit quadratisch

2. Asymmetrische Verschlüsselungsverfahren

Bei der Public/Privat-Key Kryptografie wird der Schlüssel auf zwei Teilschlüssel aufgeteilt. Das heisst, das jeder Teilnehmer folgendes Schlüsselpaar besitzt:

  • Private-Key bzw. Privater Schlüssel: Dieser dient dem Nachrichten-Empfänger zum Entschlüsseln der Nachricht. Der Private-Key kennt nur der Empfänger und bleibt geheim.
  • Public-Key bzw. Öffentlicher Schlüssel: Dieser dient zum Verschlüsseln einer Nachricht an die Person, die den Public-Key generiert bzw. ihn veröffentlicht hat. Der Public-Key ist jedermann zugänglich.

2.1 Das asymmetrische Verfahren «RSA»

RSA gemäss den Erfindern Ronald L. Rivest, Adi Shamir und Leonard Adleman (1977)

Die Rechenvorschrift für die Verschlüsselung der Nachricht: c=ke mod n
Die Rechenvorschrift für die Entschlüsselung der Nachricht: k=cd mod n
Wobei gilt:
c: Ciphertext
k: Klartext
e,n: Public Key des Empfängers
d,n: Secret Key des Empfängers


Die Mathematik ist bei Verschlüsselung und Entschlüsselung dieselbe, die Koeffizienten dagegen sind verschieden. Die Funktion xy mod z ist eine sogenannte Einwegfunktion. Damit ist eine Funktion gemeint, die sich ohne eine Zusatzinformation nur schwerlich umkehren lässt.

2.2 Zahlenbeispiel zum asymmetrischen Verfahren «RSA»

Im Folgenden soll eine Schlüsselberechnung anhand von einem Zahlenbeispiel gezeigt werden:

  1. Alice wählt zufällig zwei Primzahlen p ≠ q, die etwa gleich gross sein sollten und berechnet deren Produkt n=p·q
    Wahl p=11 und q=17; Somit wird n=11*17=187
  2. Danach berechnet Alice x = (p-1) · (q-1)
    x=(11-1)*(17-1)=160
  3. Alice berechnet nun x + 1
    x+1=160+1=161
  4. Der Wert e wird ausgewählt, wobei d ein Teiler aus x+1 sein muss
    Der zweite Teiler aus x+1 ist d. Es muss gelten: d*e=x+1
    Unzulässige Werte von d und e (z.B. d=e) werden als unsicher abgelehnt
    Da 161=7*23 sind 7 und 23 geeignete Kandidaten für e und d
  5. Alice hat nun ihr Schlüsselpaar berechnet:
    n und e sind Public-Key von Alice
    d und n sind Secret-Key von Alice
    n=187, e=7, d=23

Nun wird als Ver- und Entschlüsselungsbeispiel der Klartext in Form der Zahl k=12 gewählt.

  1. Die Verschlüsselung mit dem Public-Key von Alice (e=7, n=187) nach der Formel c=kemod n
    c=127mod 187=177
    Der chriffrierte Wert lautet somit c=177
  2. Die Entschlüsselung mit dem Private-Key von Alice (d=23, n=187) nach der Formel k=cdmod n
    k=17723mod 187=12
    Der erhaltene unverschlüsselte Wert lautet somit k=12
    , was zu beweisen war.

2.4 Bemerkung zur Sicherheit der RSA-Schlüssel

Wie in «2.2 Zahlenbeispiel zum asymmetrischen Verfahren» gezeigt, berechnet sich der Schlüssel unter anderem mit diesem Teilschritt: Alice wählt zufällig zwei Primzahlen p ≠ q, die etwa gleich lang sein sollten und berechnet deren Produkt N = p·q. In einigen Veröffentlichungen wird beschrieben, die Stärke des RSA-Algorithmus basiere auf der Tatsache, dass es schwierig sei, grosse Primzahlen zu faktorisieren. Dies ist ein Schreibfehler, denn Primzahlen allgemein, gross oder klein, haben nur zwei Faktoren. Gemeint ist, dass es schwierig ist, grosse Zahlen zu faktorisieren und der Modulus (p*q) ist eine solche grosse Zahl.
Gebräuchliche Schlüssellängen bei RSA sind: 1024 Bit, 2048 Bit, 3072 Bit, 4096 Bit

2.5 Hybride Verfahren

Symmetrische Verschlüsselungsverfahren haben das bereits besprochene Problem des Schlüsseltauschs und Schlüsselmanagements. das bei den asymmetrischen Verfahren so nicht besteht. Allerdings benötigen symmetrische Verfahren weniger Rechenzeit zur Erstellung des Chiffretexts als rein asymmetrische Verfahren. Darum liegt es auf der Hand, dass in einem hybriden Verfahren die Vorteile der beiden Verfahren genutzt werden:

  • Asymmetrisches oder Public-Key-Verfahren für Schlüsselmanagement, zB. RSA
  • Symmetrisches Verfahren zum Versenden der eigentlichen Nachricht, zB. RC4, DES

2.6 Das Verschlüsselungsverfahren in einer Übersicht

3. Digitale Signatur mit «RSA»

Ausgehend von seinem Grundprinzip ist das Internet nicht sicher:

  • Mitlesen von Daten (Sniffing)
  • Vortäuschen falscher Identitäten (Spoofing)
  • Angriffe auf die Verfügbarkeit (Denial-of-Service)
  • Übertragen von Programmen mit Schadfunktion (Viren, Würmer...)
  • Menschliches Fehlverhalten (Preisgabe von geheimen Daten)

Das möchten wir erreichen:

  • Authentisierung - Sicherstellung der Identität eines Kommunikationspartners
  • Vertraulichkeit - Zugänglichkeit der Nachricht nur für bestimmten Empfängerkreis
  • Integrität - Schutz vor Verfälschung von Nachrichten bei der Übermittlung
  • Autorisierung - Prüfung der Zugriffsberechtigung auf Ressourcen
  • Verfügbarkeit - Schutz vor Datenverlust, Sicherstellung des laufenden Betriebs
  • Verbindlichkeit - Sicherer Nachweis der Absendung bzw. des Empfangs

Wozu soll die digitale Signatur dienen?

  • Sichere Identifizierung des Absenders eines Dokumentes
  • Sicherheit vor nachträglichen Manipulationen des Dokumentes
  • Elektronisch signierte Dokumente sind mit unterschriebenen Papierdokumenten gleich gesetzt
  • Ist ein Prüfwert einer Information
  • Die Digitale Signatur hat die Aufgabe einer Unterschrift und eines Siegels

3.1 Die digitale Signatur mit «RSA» in einer Übersicht

Wesentlicher Ablauf:

  • Der Inhalt der Nachricht wird auf eine eindeutige Kenngrösse abgebildet. Dazu bedient man sich eines Hash-Algorithmus
  • Der Hash-Wert wird mit dem privatem Schlüssel verschlüsselt und zur Nachricht hinzugefügt
  • Der Empfänger kann mit Hilfe des öffentlichen Schlüssel des Senders prüfen, ob die Information wirklich vom Absender stammt und nicht verändert wurde

3.2 Der Hash-Wert

  • Der Hashwert bildet einen beliebig langen Nachrichtentext auf einen Wert vorgegebener, kurzer Länge an (Hashwert, Prüfsumme)
  • Aus dem Hashwert kann die ursprüngliche Nachricht nicht errechnet werden (Irreversibilität)
  • Die Konstruktion von Nachrichten mit identischem Hashwert muss praktisch unmöglich sein
  • Die zufällige Übereinstimmung von Hashwerten beliebiger Nachrichten ist sehr unwahrscheinlich (Kollisionsresistenz, Integrität prüfbar)

4. Public Key Infrastruktur

  • OpenPGP - Ein dezentraler Standard, der anfangs der 90er Jahre durch Phil Zimmermann entwickelt wurde: Jeder Teilnehmer am Verschlüsselungssystem, der ein gültiges Schlüsselpaar besitzt, kann die Echtheit anderer Schlüssel durch seine Unterschrift bestätigen.
  • X.509 - Zentral und hierarchisch organisiert. Der Besitzer hat seine Identität bzw. Glaubwürdigkeit durch ein X-509 Zertifikat von einer CA (=Certification Authority) bescheinigen lassen. Das heisst: Personenangaben werden mit dem Schlüsselpaar gekoppelt (Elektronischer Ausweis), ausgestellt von einer vertrauenswürdigen Instanz TC (=Trust Center) oder CA

4.1 Aufgaben von TC’s bzw. CA's (X.509)

  • Zertifikate ausstellen - Korrekte Identifikation des Teilnehmers,  Zertifizieren von User, Server, Sub CA's. Erstellung des Zertifikates durch digitale Signatur über Identifikationsdaten  und öffentlichen Schlüssel eines Teilnehmers.  Bei Ausgabe eines Zertifikates an einen Teilnehmer ist dieser über Funktionalität  und Gefahren von zertifizierten Signaturschlüsseln zu unterrichten.
  • Veröffentlichen der Public-Keys der User und Publizieren eigenes Zertifikat
  • Verwalten bzw. Archivierung angelaufener Zertifikate
    Zertifikate zurückziehen oder für ungültig erklären
    Festlegung der Gültigkeitsdauer von Zertifikaten
  • Zeitstempeldienst - Absicherung im Falle des Diebstahls des geheimen Schlüssels. Nachweis einer zeitpunktsbezogenen Willensbekundung. Nachweis und Sicherheit, dass die digitale Signatur nicht nach Ablauf der Gültigkeit des Zertifikates erstellt wurde.

5. Schwachstellen von «RSA» (Auswahl)

5.1 Der Geburtstagsangriff

Eigentlich sollte ein Dokument und der dazugehörige Hashwert einmalig sein. Dem ist leider nicht ganz so. Nach langem PC-unterstützten Suchen ist es möglich, zwei unterschiedliche Dokumente mit gleichem Hashwert zu finden.

Der Ablauf:

  1. Mallory erstellt zwei Versionen eines Dokumentes «Guter Text: Alice an Bob» und «Böser Text: Alice an Mallory»
  2. Mallory erstellt von beiden Dokumenten (Gut und Böse) je verschiedene Varianten. Der jeweilige Inhalt wird dabei geringfügig, dh. von Auge kaum erkennbar, abgeändert (zB. Einfügen von Leerschläge etc.)
  3. Mallory sucht «Gut» und «Böse» Varianten mit demselben Hashwert (Die Chance, einen Treffer zu erzielen ist intakt)
  4. Mallory legt Alice die gefundene Variante von «Guter Text» zur Unterschrift vor.
  5. Alice unterschreibt die «Guter Text: Alice an Bob» Variante für Bob.
  6. Mallory trennt nun die Signatur von «Guter Text» ab und fügt sie «Böser Text: Alice an Mallory» an.
  7. «Böser Text: Alice an Mallory» ist nun ebenfalls gültig.

Was lernen wir daraus: Niemals ein fremdes Dokumment unterschreiben, auch wenn es im Klartext abgefasst ist, es sei denn, man nimmt vor der Unterzeichnung einige subtile Änderungen vor, wie z.B. Einfügen von Leerzeichen. Damit ändert sich der Haschwert und der Geburtstagsangriff ist gescheitert.

5.2 Chosen Ciphertext

Mallory fängt eine an Bob verschlüsselte Nachricht ab und besorgt sich auch Bob's Public-Key. Nun geht Mallory wie folgt vor:

  1. Mallory wählt eine Zufallszahl r, wobei gilt: r<n und r ist teilerfremd zu n
  2. Mallory berechnet RSA-mässig: s=re mod n (e und n sind Bob's Public-Key)
    Dementsprechend wird aber auch die RSA-Umkehrfunktion gelten: r=sd mod n (d und n wären dabei Bob's Private-Key)
  3. Im weiteren berechnet Mallory y=s*C mod n (C ist die an Bob verschlüsselte Nachricht)
  4. Zusätzlich berechnet Mallory t=r-1 mod n
  5. Nun überredet Mallory Bob, die von ihm errechnete Nachricht y digital zu signieren.
  6. Gutmütig wie er ist, signiert nun Bob wie folgt: u=yd mod n (d und n sind Bob's Private-Key)
  7. Nun wird Mallory wieder aktiv und berechnet folgendes:
    t*u mod n = Cd mod n
    Oder anders ausgedrückt:
    Mit t*u mod n erhält Mallory den Wert von Cd mod n, was exakt dem Klartext entspricht, den Bob verschlüsselt erhalten hat. Und dies erreicht er allein mit den ihm bekannten Werten t, u und n.
    Wie konnte dies passieren? Dazu ein paar Mathezeilen:
  8. In t*u mod n wird t durch r-1 mod n ersetzt (Siehe Schritt 4)
  9. Somit erhalten wir: t*u mod n = r-1 mod n * u mod n
  10. Wir ersetzten u durch yd mod n (Siehe Schritt 6)
  11. Somit erhalten wir: t*u mod n = r-1 mod n * (yd mod n) mod n
  12. Das mod n rechts aussen können wir uns auch sparen.
    Somit gilt: t*u mod n = r-1 mod n * yd mod n
  13. Nun kommt eine Modul-Rechenregel zum Einsatz: Nämlich die Homomorphieregel:
    Somit erhalten wir: t*u mod n = r-1 * yd mod n
  14. Wir ersetzen nun y durch s*C mod n (Siehe Schritt 3)
  15. Wir erhalten dadurch: t*u mod n = r-1 * (s*C mod n)d mod n
  16. Etwas umgeformt ergibt dies: t*u mod n = r-1 * sd mod n *Cd mod n
  17. Nun ersetzen wir sd mod n durch r (Siehe Schritt 2)
  18. Wir erhalten dadurch: t*u mod n = r-1 * r * Cd mod n
  19. Da r-1 * r=1 ergibt erhalten wir neu: t*u mod n = Cd mod n

Was lernen wir daraus: Niemals irgendwelche binären Dateien unbekannten Inhalts mit dem eigenen privaten Schlüssel unterschreiben. Es könnte sich um einen Chosen-Ciphertext-Angriff handeln. (Man in the middle-Attack)