Der Recherchekompass
[ home | anleitungen | recherchen | hilfe | sitemap | index | suchen ]

Verschlüsselte Botschaften Moderne asymmetrische Verfahren

Als asymmetrische Verschlüsselungsverfahren bezeichnet man Verfahren, bei denen zwischen dem Schlüssel zur Chiffrierung und dem zur Dechiffrierung kein einfacher Zusammenhang besteht, so dass es nicht möglich ist - ohne zusätzliches Wissen - aus dem einen Schlüssel auf den Anderen zu schließen. Es kann also aus einem einmal erzeugten Chiffretext der Klartext nicht wieder zurückgewonnen werden, wenn man nicht im Besitz des Schlüssels für die Dechiffrierung ist. Vielmehr ist der hierzu erforderliche Aufwand, so hoch, dass ein Angriff auf diesem Weg nicht praktikabel ist. Bei asymmetrischen Verfahren wird also nicht mit nur einem Schlüssel, sondern immer mit einem geeigneten Schlüsselpaar gearbeitet.

Abbildung: Kryptografisches System (asymmetrisch)

Die verbreiteten asymmetrischen Verfahren basieren auf der Schwierigkeit folgender zahlentheoretischer Probleme:

• Die Bestimmung des diskreten Logarithmus.
• Die Faktorisierung eines Produktes großer Primzahlen.

Der Vorteil asymmetrischer Verfahren liegt auf der Hand: Es muss kein sicherer Kanal für den Schlüsseltausch vorhanden sein, der Austausch kann öffentlich stattfinden. Außerdem wird für die Kommunikation eine geringere Anzahl von Schlüsseln benötigt: Bei der symmetrischen Verschlüsselung ist pro "Kommunikationspärchen" ein Schlüssel erforderlich, was bei n Teilnehmern (n*(n-1))/2 Schlüssel bedeutet. Bei der asymmetrischen hingegen braucht jeder sein Schlüsselpaar sowie die öffentlichen Schlüssel der Kommunikationspartner: 2+(n-1).

Als Nachteil ist insbesondere der sehr hohe Aufwand für Ver- und Entschlüsselung zu sehen. So muss bereits der Schlüssel - bei gleicher Sicherheit - erheblich länger sein als bei einem symmetrischen Verfahren, was denn auch zum höheren Aufwand beiträgt. Des weiteren entstehen Chiffretexte die länger sind als die originären Klartexte und die Algorithmen sind in der Regel nur schwer hardwareseitig umzusetzen. Als weiteren Nachteil ist gewiss die Unsicherheit zu sehen, dass das zugrundeliegende mathematische Problem eben doch einer einfachen Lösung zugeführt werden kann.

 

• Diffie-Hellmann

  Diffie-Hellman ist ein Algorithmus zum sicheren Schlüsselaustausch über einen unsicheren Kanal. Mit diesem Algorithmus wird bei zwei oder mehr 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 läuft die Schlüsselerzeugung wie folgt ab:

  1. 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 und eine Zahl g die kleiner p ist. Beide Zahlen können über den unsicheren Kanal ausgetauscht werden.

  2. 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

  3. 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 den diskreten Logarithmus aus Y zu ermitteln.

  Die Schlüsselerzeugung funktioniert bei mehreren Parteien:

  1. Die Partner 1 bis n einigen sich auf ein gemeinsames g und p, mit (p-1)/2 ebenfalls prim. Zudem wird eine zyklische Reihenfolge unter den Partnern festgelegt.

  2. Jeder der Partner legt sein x fest. Hieraus berechnet der erste in der Reihe sein Y wie oben und sendet es an seinen Nachfolger. Dieser berechnet sein Y und sendet es wiederum seinem Nachfolger, der ebenso verfährt. Die Berechnung von Y lautet dabei:
     Y_i = Y_i-1^x mod p

  3. Der (n-1)-Partner kann nun den gemeinsamen Schlüssel nach obiger Formel (Schritt 3) berechnen. Zudem berechnet er sein Y nach der Formel aus Schritt 2 oben zur Basis g und sendet dies an seinen Nachfolger, den ersten der Reihe. Dieser berechnet wiederum sein Y, wie in Schritt 2 hier, behält dabei natürlich sein bisheriges x bei.

     In dieser Form wird weiterverfahren, bis jeder Partner den gemeinsamen Schlüssel berechnen kann.

  Dem Angreifer bleibt hierbei für jedes Y mindestens ein x verborgen, so dass ihm auch hierbei die Berechnung des Schlüssels unmöglich gemacht ist.

  Die Sicherheit des Verfahrens beruht auf dem Problem des diskreten Logarithmus, zwar ist es einfach, a^x mod n zu berechnen, die Umkehrung ist jedoch ein schwieriges Problem, welches äquivalent zum Faktorisierungsproblem von ganzen Zahlen anzusehen ist. Da Diffie-Hellmann keine Authentifizierung der Partner beinhaltet, ist das Verfahren aber durch einen Man-in-the-Middle Angriff auszuhebeln, wobei der Angreifer die Rolle eines der Partner übernimmt.

  [seitenanfang] [verweise]

   

• El Gamal

  Das ElGamal-Verschlüsselungsverfahren wurde 1985 von Taher ElGamal veröffentlicht und stellt eine Abänderung und Erweiterung des Verfahrens zum Schlüsselaustausch von Diffie und Hellman dar. Die zugrundeliegende Mathematik ist dieselbe. Zur Erzeugung der Schlüssel wird wie folgt vorgegangen:

  • Zunächst wird eine große Primzahl p und eine Basis g mit 1 < g < p benötigt bestimmt.

  • Den privaten und geheimzuhaltenden Schlüssel bildet eine beliebige natürliche Zahl d, die zu p-1 relativ prim und kleiner ist.

  • Für den öffentlichen Schlüssel wird zudem ein (e) folgendermaßen berechnet:
    e = g^d mod p

  • Die Werte für e, p und g können öffentlich verfügbar gemacht werden.

  Hat der Sender einer Botschaft den öffentlichen Schlüssel des Empfängers, so gestaltet sich die Chiffrierung und Dechiffrierung einer Nachricht wie folgt:

  • Wie bei RSA werden auch bei ElGamal nur Zahlen in Zahlen ver- bzw. entschlüsselt, daher muss der Klartext mit einem öffentlich bekannten Alphabet in eine Zahlenfolge (numerical Encoding) übertragen werden. Dann wird die Nachricht M in gleichlange Blöcke zerlegt, die kleiner als p sein müssen.

  • Chiffrierung:
    Unter Verwendung des öffentlichen Schlüssels des Empfängers wählt der Versender zufällig eine natürliche Zahl x die kleiner ist als p-1. Damit wird ein Y berechnet:
    Y = g^x mod p

    Diese Y wird zusammen mit dem Chiffretext C an den Empfänger versendet. Das Chiffre wird gebildet indem der Klartext M folgendermaßen umgerechnet wird:

    C = M * e^x mod p

  • Dechiffrierung:
    Der Empfänger kann die Nachricht (Y, C) wieder in den Klartext umsetzen, indem er M auf die folgende Art berechnet:
    M = C * Y^p-1-d mod p

    Der Nachweis das die dechiffrierte Nachricht gleich der ursprünglichen ist, lässt sich allgemein führen und soll hier nicht dargestellt werden.

  • Abschließend werden die Blöcke zusammengesetzt und die erhaltenen Zahlenfolge wird anhand des öffentlich bekannten Alphabetes wieder in den Klartext übertragen.

  Die Sicherheit des Verfahrens beruht, wie bei Diffie-Hellmann auf dem Problem des diskreten Logarithmus. Da auch ElGamal keine Authentifizierung der Partner beinhaltet, ist es ebenfalls durch einen Man-in-the-Middle Angriff gefährdet.

  [seitenanfang] [verweise]

   

• RSA: Rivest-Shamir-Adleman

  Dieses Verfahren ist wohl das verbreitetste Public-Key-Verfahren. Es wurde 1977/78 von Ron Rivest, Adi Shamir und Len Adleman am MIT entwickelt, woher das Verfahren aus den Namen bekommen hat. RSA wurde 1983 bis ins Jahr 2000 für die USA patentiert. Das Patent wurde nicht verlängert.

  Bei diesen Verfahren benutzt man bekannte Probleme aus der Numerik. Die Sicherheit von RSA basiert auf dem Problem, eine große ganze Zahl in ihre Primfaktoren zu zerlegen. Daher darf die Schlüssellänge auch nicht zu klein gewählt werden. Die beiden Schlüssel werden wie folgt erzeugt:

  P = 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Q = 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 m     (p-1)*(q-1)   e   d
  Tabelle: Erzeugung von Schlüsselpaaren für RSA.	[quelltext]

  • Es werden zwei verschieden, große Primzahlen p und q zufällig gewählt, wobei die Differenz nicht zu klein sein sollte, und das Produkt der beiden berechnet: m = p * q

  • Dann wird ein zufälliger Wert e ermittelt, der kleiner m und teilerfremd (relativ prim) zu (p-1) * (q-1) ist. Zu diesem wird das modular Inverse d berechnet, so dass gilt: (e * d) mod ((p-1)*(q-1)) = 1 [1]

  • Als öffentlicher Schlüssel gilt dann: e und m und der private Schlüssel ist: d und m. Die Primzahlen p und q können vergessen werden, aber sie sollten niemals bekannt werden.

  Die Stärke dieses Verfahrens liegt im Schlüssel, bzw. dessen Erzeugung. Die Chiffrierung und Dechiffrierung der Nachrichten ist vergleichsweise einfach und gestaltet sich wie folgt:

  • Das RSA-Verfahren verschlüsselt und entschlüsselt nur Zahlen in Zahlen, daher muss der Klartext mit einem öffentlich bekannten Alphabet in eine Zahlenfolge (numerical Encoding) übersetzt werden.

  • Zunächst wird die Nachricht in numerische Blöcke zerlegt, die kleiner als m sein müssen, orientiert an der Bitlänge bedeutet dies: Bitlänge(Block) <= Bitlänge(m) - 1. [2]

  • Zur Verschlüsselung benutzt man die Funktion:
    
    C = M ^e mod m

  • Die Entschlüsselung erreicht man mit:
    
    M = C ^d mod m

  Öffentlich zugänglich ist natürlich das Verfahren zur Ver- und Entschlüsselung, was eine Forderung für alle kryptografisch starken Verfahren ist. Unbedingt öffentlich muss der öffentliche Schlüssel e und das Primzahlprodukt (n) sein. Der Chiffretext kann nun bekannt werden oder nicht, der Sicherheit der Übermittlung tut dies keinen Abbruch. Der verschlüsselte Text kann nur vom Empfänger entschlüsselt werden, da dieser als einziger den geheimen, privaten Schlüssel hat.

  RSA kann nur so lange als sicheres Verfahren gelten, wie es nicht möglich ist eine Faktorisierung von n in p und q zu erreichen, um dann den geheimen Schlüssel zu berechen. Noch 1993 schätzte man, dass die Zerlegung einer 130-stelligen Zahl in ihre zwei Primzahlen Millionen von Jahren benötigen würden. Tatsächlich gelang bereits ein Jahr später die Auflösung. Shamir selbst entwarf einen Computer, der einen 512-Bit-Schlüssel in 3 Tagen knacken kann.

  Ständig wird die Grenze der faktorierbaren Zahlen höher gesetzt, sei es durch verbesserte Berechnungstechniken oder durch bessere Rechner. Eine RSA-codierte Nachricht kann nur für eine begrenzte Zeit sicher sein, nämlich solange, bis diese Grenze die Höhe erreicht, die das n ihrer Verschlüsselung hatte.

  Public Key:  Secret Key:
  Klartext: Dies ist ein Klartext.	Geheimtext:
  [quelltext] Tabelle: RSA Chiffrierung

  Die Beispielverschlüsselung der Tabelle macht deutlich, dass die Sicherheit des RSA-Verfahrens von der Blocklänge abhängt. Da gleiche Blöcke auch gleich verschlüsselt werden, muss die Länge eines Blockes derart sein, dass die Wahrscheinlichkeit für die Wiederholung eines solchen Blockes sehr gering ist. Dies ist im obigen Beispiel nicht immer der Fall, bei einer Blocklänge von einem oder zwei Byte (m > 65536) ist das Verfahren kaum besser als die Cäsar-Chiffre.
  [seitenanfang] [verweise]