Unterkapitel

• 1. IDEA
• 2. RSA
• 3. ElGamal
  • 1. Unterschriften
  • 2. Verschlüsselung

25. Kurz vorgestellt: Die Verschlüsselungsalgorithmen

 1. IDEA

IDEA™ soll hier stellvertretend für die symmetrischen Verschlüsselungsalgorithmen behandelt werden. Weitere Algorithmen finden Sie in [Sti95,Sch95]. IDEA basiert auf der Kombination einfacher Rechenoperationen. Verwendet werden:

1.

Bitweise Addition zweier Zahlen ohne Übertrag (XOR)

2.

Addition zweier Zahlen ohne Berücksichtigung des Übertrags über 2¹⁶ hinaus

3.

Multiplikation zweier Zahlen und Bildung des Restes nach Division durch 2¹⁶+1. Hierbei werden 0 und 2¹⁶ besonders behandelt: Vor Beginn der Multiplikation wird eine 0 durch 2¹⁶ersetzt, das Ergebnis 2¹⁶ wiederum wird als 0 interpretiert. Daraus folgt: $0 \text{\glqq{}mal\grqq{}} 0 = 1$.

  

Abbildung E.1: IDEA™

Diese drei Operationen wurden nicht absolut willkürlich gewählt, sondern aufgrund einer ganz speziellen mathematischen Eigenschaft: Sie bilden zwei 16-Bit-Zahlen a,b auf eine 16-Bit-Zahl c ab und sind sowohl in b invertierbar. Das heißt: Zu jedem b gibt es ein b', so daß $(a\cdot b)\cdot b'=a$ für alle a gilt. Das ist die entscheidende Eigenschaft, die das Entschlüsseln (bei bekanntem Schlüssel) erlaubt. Nebenbei sind die Operationen auch in ainvertierbar (und überhaupt kommutativ), was nahelegt, daß ihr Ausgabewert wünschenswert stark vom Schlüssel abhängt.

Aus dem 128-Bit-Schlüssel werden Teilschlüssel berechnet, und zwar S_1,1 bis S_8,6 und S_9,1 bis S_9,4. Hierfür wird der Schlüssel in acht 16 Bit große Teile geteilt, diese ergeben S_1,1 bis S_1,6, S_2,1 und S_2,2. Anschließend wird der gesamte 128-Bit-Schlüssel um 25 Bit nach links rotiert und wieder in acht Blöcke zu je 16 Bit unterteilt, die dann S_2,3bis S_2,6 und S_3,1 bis S_3,4 werden. Dann wird wieder rotiert und so weiter.

Die eigentliche Verschlüsselung läuft so ab, daß ein Klartextblock von 64 Bit Länge in vier Blöcke zu je 16 Bit eingeteilt wird, die anschließend dem Verfahren in Abb. E.1 unterworfen werden. Dargestellt ist nur der erste Durchlauf, das Verfahren wird achtmal angewendet.

Zum Entschlüsseln kann dasselbe Verfahren verwendet werden. Damit dabei der ursprüngliche Klartext erhalten bleibt, müssen leicht andere Teilschlüssel verwendet werden.

  2. RSA

         

RSA, das wohl berühmteste asymmetrische Verschlüsselungsverfahren, ist benannt worden nach Rivest, Shamir und Adleman, seinen Entwicklern. Als sie es 1977 veröffentlichten, war es das einzige öffentlich bekannte Verfahren, daß die 1976 von Diffie und Hellman publizierte Idee öffentlicher Schlüssel tatsächlich einsetzen konnte.

Das System basiert auf Rechnungen im Ring der ganzen Zahlen modulo pq, wobei p und q zwei verschiedene Primzahlen sind. In diesem System zu rechnen, geht ebenso vor sich wie gewohnt, nur, daß vom Ergebnis nur der Rest bei Division durch pq behalten wird. Als Zeichen, daß wir diese Art der Rechnung durchführen, verwenden wir das $\equiv$ anstelle des üblichen = und schreiben den "Modulus", also das pq, hinter die Rechnung. Wenn wir als Beispiel pq = 15 setzen, dann sind folgende Rechnungen korrekt:
$$\begin{align*}2 + 5 &\equiv 7 \pmod{15}\\ 2 * 5 &\equiv 10\pmod{15}\\ 4 * 5 &\... ...,4 &\equiv 4\pmod{15}\text{, denn $x=1/y$\space bedeutet $x*y=1$ .} \end{align*}$$

Von besonderem Interesse sind hier die Exponentialfunktionen:
$$\begin{align*}5 ^ 2 &\equiv 10\pmod{15}\\ 4 ^ 7 &\equiv 4\pmod{15}, \end{align*}$$
denn es ist kein effizientes Verfahren bekannt, diese Rechnung umzukehren, d.h. es ist keine Möglichkeit bekannt, in annehmbarer Zeit Probleme wie $x^5\equiv 12$ zu lösen. (Auf der Schwierigkeit des diskreten Logarithmus, also der Lösung von $6 ^ x\equiv 8$ etc., beruhen andere Verfahren, beispielsweise ElGamal.) Weiterhin interessant ist eine Beziehung, die schon Euler bekannt war:

$$a^{\phi (x)} \equiv 1 \pmod x$$

Hier sind a und x beliebig, davon abgesehen, daß sie keinen gemeinsamen Teiler größer als 1 haben. $\equiv$ ist das Zeichen für das oben erwähnte Modulo-Rechnen, und zwar modulo x. Ein weiteres neues Zeichen steht in dieser Formel: $\phi(x)$ ist die "Eulersche Phi-Funktion". Für uns wichtig ist nur, daß $\phi (pq) = (p - 1)(q - 1)$ gilt, wiederum für die Primzahlen p und q. Eine kurze Rechnung ergibt für eine beliebige ganze Zahl k:
$$\begin{align*}a ^ {\phi (pq)} &\equiv 1 \pmod{pq}\\ a ^ {(k * \phi (pq))} &\equiv 1 \pmod{pq}\\ a ^ {(k * \phi (pq) + 1)} &\equiv a \pmod{pq} \end{align*}$$

Wenn wir nun zwei ganze Zahlen d und e einführen, von denen wir verlangen, daß $de = k * \phi (pq) + 1$ gelten soll, dann erhalten wir:
$$\begin{align*}a^{de} &\equiv a\pmod{pq}\\ [1.2ex] a^d &\equiv b\pmod{pq}\\ b^e &\equiv a\pmod{pq} \end{align*}$$

Wobei die Kenntnis von b und d nicht ausreicht, um a zu berechnen. RSA funktioniert nun so, daß als öffentlicher Schlüssel d und das Produkt pq veröffentlicht werden und die Nachrichten adamit wie eben beschrieben verschlüsselt werden. Die verschlüsselten Nachrichten (b) können dann bedenkenlos versandt werden, da sie ohne e nicht entschlüsselt werden können.

Angriffsmöglichkeiten auf RSA

Aus a und b e berechnen

Dies nennt sich in der Sprache der Mathematiker "diskreter Logarithmus" und gilt derzeit als praktisch (d.h. in "kurzer" Zeit) unlösbar.

Aus pq und d das geheime e berechnen

Hierzu muß nach derzeitigem Wissensstand pq in seine Faktoren zerlegt werden, was ebenfalls für nicht in sinnvoller Zeit lösbar gehalten wird. Als Anhaltspunkt: Ron Rivest hat 1995 geschätzt, daß es im Jahre 2010 möglich sein dürfte, eine 1689-Bit-Zahl zu faktorisieren - zu Kosten von 25 Milliarden Euro. Bei einer Investitionssumme von 25 Millionen Euro schätzte er die Grenze auf 705 Bit.

Ein spezieller Angriff auf Nachrichten mit mehreren Empfängern

Wenn dasselbe a an mehrere Empfänger verschlüsselt wird, wobei dasselbe d verwendet wird, ist es mit einem kleinen mathematischen Kunstgriff möglich, die Nachricht zu entschlüsseln. Dies betrifft PGP nicht, da hier beim Verschlüsseln an mehrere Empfänger der IDEA-Schlüssel stets mit Zufallszahlen aufgefüllt wird, die für jeden Empfänger verschieden sind.

  3. ElGamal

Die Sicherheit ElGamals beruht auf der Schwierigkeit, diskrete Logarithmen zu finden, also der Schwierigkeit, eine Gleichung der Form

$$y \equiv g^{x}\pmod{n}$$

zu gegebenen y,g und p nach xaufzulösen. (Zur Notation siehe Abschnitt E.2.) Dieses Problem ist in vielen Spezialfällen (d.h. für n einer bestimmten allgemeinen Form) gelöst, der allgemeine Fall ist aber nach wie vor ein hartes Problem. Übrigens würde ein erfolgreicher Angriff auf das Problem des diskreten Logarithmus auch die Sicherheit des RSA-Verfahrens zunichte machen, da jeder den privaten Schlüssel ausrechnen könnte.

Um einen ElGamal-Schlüssel zu berechnen, wählt man zufällig eine Primzahl p (diese Zahl sollte recht groß sein, z.B. 1024 Bit) und zwei Zahlen g und x, die kleiner als p-1 sind. Dann berechnet man

$$y = g^{x}\pmod{p}.$$

Der öffentliche Schlüssel ist (y,g,p), der private Schlüssel (x,g,p). g und p können ohne Probleme für viele Teilnehmer identisch sein. p-1 ist immer gerade, (p-1)/2 sollte keine kleinen Faktoren haben, weil sonst ein Algorithmus von  Pohlig und Hellman verwendet werden kann, um den diskreten Logarithmus etwas schneller zu berechnen. PGP wählt für jeden Benutzer ein eigenes p; um diese Bedingung an (p-1)/2 zu erfüllen, wählt es dazu Primzahlen $p_{1},\dots,p_{n}$ und probiert, ob $p=1+2\prod_{i=1}^{n}p_{i}$ eine Primzahl ist. Wenn nicht, werden andere $p_{1},\dots,p_{n'}$ gewählt.

1. Unterschriften

ElGamal-Unterschriften werden wie folgt erzeugt: Zunächst wähle ein zufälliges k, das keinen gemeinsamen Teiler mit p-1 hat und berechne h, den Hash-Wert der Nachricht. Dann berechne man a und b, so daß
$$\begin{align*}a &\equiv g^{k}\pmod{p}\\ h &\equiv xa + bk\pmod{p-1}.\\ \inte... ...quiv g^{xa}g^{kb}\\ & \equiv g^{xa+kb}\\ & \equiv g^{h}\pmod{p} \end{align*}$$

2. Verschlüsselung

Eine Nachricht M mit ElGamal zu verschlüsseln, funktioniert so: Zunächst wähle man wiederum ein zufälliges k ohne gemeinsame Teiler mit p-1. Dann berechne man
$$\begin{align*}a&\equiv g^{k}\pmod{p}\\ b&\equiv y^{k}M\pmod{p}. \end{align*}$$
Das Paar (a,b) ist die verschlüsselte Nachricht. Man beachte, daß die Länge der Nachricht hierbei mindestens verdoppelt wird. Zum Dekodieren braucht der Empfänger nur

$$\frac{b}{a^{x}}\equiv\frac{y^{k}M}{(g^{k})^{x}} \equiv\frac{y^{k}M}{y^{k}}\equiv M\pmod{p}$$

zu berechnen.