3 Asymmetrische Algorithmen

3.1 RSA

Beim RSA-Algorithmus handelt es sich um das bekannteste asymmetrische Kryptoverfahren, benannt nach seinen Erfindern RIVEST-SHAMIR-ADLEMAN [56, 1].²⁰ Die mathematische Grundlage bilden Restklassenkörper, verbunden mit der Schwierigkeit große Zahlen zu faktorisieren.

3.1.1 Schlüsselgenerierung

Betrachten wir in der Voraussetzung zuerst die Schlüsselerzeugung, welche im Wesen folgendermaßen abläuft:²¹

1. Wähle zwei große Primzahlen 𝑝,𝑞 > 2, mit 𝑝 ≠ 𝑞, welche das öffentliche Modul 𝑛 = 𝑝𝑞 bestimmen.

   Zahlentheoretische Erläuterungen:

   • Bei der Restklasse Z_𝑛 := {0,1,…,𝑛 − 1} handelt es sich um einen Ring, nicht um einen Körper.²²
   • Im Gegensatz dazu bilden Z_𝑝 und Z_𝑞 jeweils einen Primzahlenkörper.
   • Läßt man aus Z_𝑛 nur solche Elemente zu, die keinen gemeinsamen Teiler mit dem Modul 𝑛 haben, wird ein Körper konstruierbar. Die Anzahl der Elemente 𝑟 in dessen multiplikativer Gruppe Z_𝑛^∗ := {𝑟 ∈ Z|0 < 𝑟 < 𝑛,gcd(𝑟,𝑛) = 1} ergibt sich mit Hilfe von EULER’s Totient-Funktion zu 𝜑 = 𝜙(𝑛) = (𝑝−1)(𝑞−1).

2. Nun wird eine Zufallszahl 1 < 𝑒 < 𝜑 erzeugt, die keinen gemeinsamen Faktor mit 𝜑 hat. Diese (auch als öffentlicher Exponent bezeichnete) Zahl bildet die Basis des öffentlichen Schlüssels (𝑛,𝑒).

   Zahlentheoretische Erläuterungen:

   • Wegen gcd(𝑒,𝜑) = 1 gehört 𝑒 zum endlichen Körper Z_𝜑.
   • Aus gcd[𝑒,(𝑝−1)(𝑞−1)] = 1 läßt sich als notwendige Voraussetzungen gcd(𝑒,𝑝− 1) = 1 und gcd(𝑒,𝑞−1) = 1 ableiten.
   • Da 𝑝−1 und 𝑞−1 gerade Zahlen sind, muß 𝑒 wegen des vorangegangenen Punktes auf jeden Fall ungerade sein.

3. Für den privaten Schlüssel (𝑛,𝑑) wird jetzt eine weitere Zahl 𝑑 so berechnet,²³ daß 𝑑𝑒−1 ohne Rest durch 𝜑 teilbar ist.

   Zahlentheoretische Erläuterungen:

   • Ausgehend von

     

     kann man 𝑑 auch als Inverse des öffentlichen Exponents 𝑒 im Körper Z_𝜑 ansehen.

     

3.1.2 Algorithmus

Für die Verschlüsselung wird folgende Operation auf dem Plaintext-Block 𝑚 ausgeführt, wobei dieser als Zahl 𝑚 ∈ Z_𝑛 interpretiert wird:

Die inverse Operation der Entschlüsselung wird in gleicher Art und Weise vorgenommen:

Für den Beweis 𝑚′ = 𝑚 wendet man zuerst Gleichung 6 an und bezieht dann die Restklassendarstellung 𝑑𝑒 = 1 +𝑘𝜑 (𝑘 ∈ N) ein.

Die weitere Argumentation beruht darauf, daß 𝑚^𝜑 mod 𝑛 = 1 gilt und so:

Besitzen 𝑚 und 𝑛 keinen gemeinsamen Teiler (gcd(𝑚,𝑛) = 1, 𝑚 ∈ Z_𝑛^∗), dann kann man auf 𝑚^𝜑 mod 𝑛 einfach EULER’s Satz (nach Formel ??) anwenden und ist fertig.

Hat 𝑚 allerdings gemeinsame Teiler mit 𝑛, dann gilt gcd(𝑚,𝑛) ≠ 1 und deshalb 𝑚 ∉ Z_𝑛^∗. Betrachtet man aber die Faktorisierung von 𝑛, dann muß 𝑚 ein Vielfaches von 𝑝 oder 𝑞 sein (wegen 𝑚 < 𝑛 jedoch nicht von 𝑝𝑞). Unter dieser Voraussetzung wäre die Zerlegung 𝑚 = 𝑚𝑝 oder 𝑚 = 𝑚𝑞 möglich, wobei jeweils gcd(𝑚,𝑛) = 1 gilt. Im Fall 𝑚 = 𝑚𝑝 (für 𝑚 = 𝑚𝑞 ganz genauso) läßt sich die Modulo-Division 𝑚^𝜑 mod 𝑛 durch Kürzen von 𝑝 und unter Berücksichtigung von 𝑚 < 𝑞 folgendermaßen vereinfachen:

Wegen 𝑚 ∈ Z_𝑞^∗ kann nun wieder der Satz von EULER zur Anwendung kommen, was den Beweis vervollständigt.

3.1.3 Optimierung

Eine Beschleunigung des Verfahrens läßt sich (algorithmisch) vor allem beim Entschlüsseln erzielen.²⁴ Geht man dazu von

aus, dann lassen sich (durch Modulo-Division nach 𝑝 und 𝑞) die folgenden zwei Kongruenzen formulieren:

Diese legen eine Anwendung des Chinesischen Restsatzes entsprechend Anhang ?? nahe [20, 62].²⁵

Als Voraussetzung benötigt man die Koeffizienten 𝛼 und 𝛽 in der BéZOUT-Darstellung des größten gemeinsamen Teilers (vgl. Formel ?? in Anhang ??)

welche z. B. mit Hilfe des erweiterten euklidischen Algorithmus berechnet werden können.²⁶ Sie stellen, wenn man vorangegangene Gleichung nach 𝑝 und 𝑞 modulo-dividiert, gleichzeitig die Inversen

im Körper Z_𝑞 und Z_𝑝 dar. Durch Anwendung des Chinesischen Restsatzes für zwei Kongruenzen kann man nun 𝑚′ berechnen:

(8)

Der Vorteil liegt darin, daß die modulare Exponentiation modulo 𝑛, welche die Komplexität O(log ³𝑛) hat,²⁷ auf zwei Operationen gleicher Art, aber mit verringerter Anzahl von Stellen verteilt.

Die weitere Optimierung kann in drei Schritten erfolgen:

1. Wendet man den Chinesischen Restsatz in der Variante nach H. L. GARNER an, so werden weitere Vereinfachungen möglich [19]. Denn aus der Restklassendarstellung

   

   läßt sich eine lineare diophantische Gleichung ableiten (siehe auch Anhang ??):

   

   welche die Lösungsmenge

   

   besitzt. Üblicherweise benutzt man zur Berechnung von 𝑚′ die Lösungen für 𝑥_𝑘 und erhält in geschlossener Darstellung:²⁸

   

   Unter der Voraussetzung 𝑚′ = 𝑚′ mod 𝑛 kann man vorangegangene Gleichung noch weiter reduzieren, wenn die allgemeingültige Beziehung (𝑟𝑞) mod (𝑝𝑞) = 𝑞(𝑟 mod 𝑝) berücksichtigt wird.

   

   Die Vorteile dieser Darstellung liegen vor allem darin, daß

   • eine finale Modulo-Division durch 𝑛 nicht mehr nötig ist;
   • nur ein BéZOUT-Kofaktor überhaupt benötigt wird;
   • wegen der Zwischenreduktion modulo 𝑝 die Speicherplatzanforderungen reduziert sind.

2. Man kann aber noch weitergehen, indem die Berechnung von 𝑚_𝑝 und 𝑚_𝑞 vereinfacht wird. Eine wesentliche Zeitersparnis kommt zustande, wenn man 𝑐 vor dessen Potenzierung in der Länge reduziert.

   

3. Eine letzte Optimierung bezieht sich auf den Exponenten 𝑑, welcher ebenfalls reduziert werden kann. Dazu muß man sich nur klarmachen, daß durch die Reduktion von 𝑐 in Punkt 2 das Ergebnis der Potenzierung jeweils in Z_𝑝 oder Z_𝑞 und insbesondere in der zugehörigen multiplikativen Gruppe liegt. Da diese zyklisch ist, wiederholen sich beim Potenzieren die Werte mit der Gruppenordnung |Z_𝑝^∗| = 𝑝−1 bzw. |Z_𝑞^∗| = 𝑞−1. Aus diesem Grund kann man 𝑑 auf die Gruppenordnung reduzieren (vgl. auch Anhang ??).

   

Zu der privaten Schlüsseldarstellung (𝑛,𝑑) gibt es deshalb zwei Optionen:

• ein Tripel (𝑝,𝑞,𝑑), was wegen 𝑛 = 𝑝𝑞 trivial erscheint;
• oder die Darstellung als Quintupel (𝑝,𝑞,𝑑_𝑝,𝑑_𝑞,𝑞_inv), mit 𝑑_𝑝 = 𝑑 mod (𝑝 − 1), 𝑑_𝑞 = 𝑑 mod (𝑞−1) und 𝑞_inv = 𝑞⁻¹ (mod 𝑝).

Wegen der signifikanten Geschwindigkeitsvorteile wird fast immer die Quintupel-Variante verwendet [23, 28, 58].²⁹

3.1.4 Verschlüsselung nach PKCS #1

Um den RSA-Algorithmus praktisch auf die Verschlüsselung von Daten anzuwenden, müssen diese zuerst geeignet aufbereitet werden. Der Prozeß dieser Formatierung wird in [23, 58] als Message Encoding Operation bezeichnet, in [59] hingegen als Encryption Block Formatting.

PKCS #1 v1.5 Mit der Methode nach [59, 35] gestaltet sich die Formatierung noch relativ einfach.³⁰ Der Datenblock D wird entsprechend Abbildung 15 in die Struktur des sogenannten Encryption Block EB eingebunden. Auf den Encryption Block EB wird letztlich der RSA-Algorithmus nach Formel 6 angewendet.³¹

Die weiteren Elemente im Encryption Block haben folgende Bedeutung:

BT

Der Block Type zeigt die Verwendung des privaten oder öffentlichen Schlüssels (im anschließenden RSA-Algorithmus) an.

00H

Signieren (Verwendung des privaten Schlüssels);

01H

genauso wie 00H (der Unterschied liegt im Element PS);

02H

Verschlüsseln (Verwendung des öffentlichen Schlüssels).

PS

Ein Padding String dient der Anpassung an die Länge des Moduls 𝑘 = so, daß ++3 = 𝑘 gewährleistet ist. Die Länge von PS soll mindestens 8 Byte sein, was im Umkehrschluß die von D auf 𝑘−11 Bytes beschränkt. Das Padding selbst hängt vom Typ des Blocks (BT) ab:

00H

alle Bytes sind 00H;

01H

alle Bytes sind FFH;

02H

alle Bytes sind zufällig, aber ungleich 00H.

Der Inhalt von PS ist beim Entschlüsseln (Byte für Byte) auf konforme Kodierung zu prüfen [59, S. 9.4]. Für die Blocktypen 01H und 02H kann der Anfang (und damit auch die Länge) des Datenblocks D ermittelt werden, indem das 00H-Byte zwischen PS und D gesucht wird. Für den Blocktyp 00H ist dieses Verfahren nur geeignet, wenn das erste Byte in D immer ungleich 00H ist. Kann dies nicht vorausgesetzt werden, dann muß die Länge a priori bekannt sein.³²

PKCS #1 v2.1 Nicht zuletzt wegen des sehr erfolgreiche Angriffs nach [11] wird die PKCS #1 v1.5 Formatierung heute nicht mehr empfohlen. Statt dessen sollte grundsätzlich Version 2.1 nach [58, 34, 23, 28] zum Einsatz kommen, welche Optimal Asymmetric Encryption Padding (OAEP) verwendet [9].³³

Den Kern der Blockformatierung nach Abbildung 16 macht eine sogenannte Mask Generation Function (MGF, in Abbildung 16 mit F bezeichnet) aus, welche selbst wiederum eine Hash-Funktion H verwendet. Die MGF kann dasselbe leisten wie die Hash-Funktion, nämlich eine große Eingangsmenge auf eine kleine Ausgangsmenge abbilden (mit soll im folgenden die Breite eines Hash-Wertes bezeichnet sein). Sie kann aber auch das Umgekehrte – eine kleine Eingangsmenge auf eine größere Ausgangsmenge „zerstreuen”. PKCS #1 v2.1 legt sich zwar in der Hash-Funktion nicht fest, definiert aber in [58, B.2.1] eine konkrete Mask Generation Function, genannt MGF1.³⁴

Die einzelnen Kodierungsschritte können folgendermaßen beschrieben werden:

1. Ergänze die Nachricht M zuerst (und grundsätzlich) durch ein vorangestelltes Byte mit Wert 01H.
2. Füge weitere 00H-Byte’s hinzu (Padding), so daß ein Datenblock DB der Länge 𝑘−−1 entsteht.³⁵
3. Bilde den Hash über ein vereinbartes, konstantes Label 𝐿 und stelle das Ergebnis als lHash = H(𝐿) an den Anfang des Datenblocks.³⁶
4. Erzeuge einen Zufallsstrom Seed der Länge .
5. Berechne maskedDB = DB ⊕ MGF(Seed) als Teil der Encoded Message (EM).
6. Berechne maskedSeed = Seed ⊕ MGF(maskedDB), als höherwertigen Teil von EM.
7. Stelle ein führendes 00H-Byte an den Anfang von EM (gewährleistet auch hier wieder EM < 𝑛).

Im Gegensatz zu PKCS #1 v1.5 geht in die RSA-Verschlüsselung 𝑐 = EM^𝑒 mod 𝑛 hier nun ein Wert EM ein, der keinerlei Rückschlüsse auf den Datenblock DB zuläßt.³⁷

3.2 Diffie-Hellmann Schlüsselaustausch

Das Verfahren von DIffiE und HELLMANN [15] nutzt das Problem des diskreten Logarithmus’³⁸ um einen Schlüsselaustausch zu realisieren [23, 30, 7, 54, 48, 13, 53]. Voraussetzung dafür ist eine große Primzahl 𝑝 (öffentliches Modul) und ein Generator 𝑔 mit 0 < 𝑔 < 𝑝, welche beiden Kommunikationspartnern bekannt sind. Der Austausch der Session Keys erfolgt folgendermaßen:

1. Zuerst erzeugt der Initiator des Protokolls ein (geheimes) Element 𝑎 mit 0 < 𝑎 < 𝑝 − 1 und berechnet damit seine öffentlichen Schlüssel 𝐴 = 𝑔^𝑎 mod 𝑝.
2. Dieser Schlüssel 𝐴 wird im Klartext zum Empfänger (Responder) übertragen.³⁹
3. Der Empfänger erzeugt ebenfalls eine Zufallszahl 𝑏 und berechnet 𝐵 = 𝑔^𝑏 mod 𝑝.
4. Anschließend überträgt er 𝐵 = 𝑔^𝑏 mod 𝑝 als (unverschlüsselte) Antwort zum Initiator.

5. Beide Partner berechnen dann mit Hilfe von 𝐴 bzw. 𝐵 den Sitzungsschlüssel 𝑔^𝑎𝑏 mod 𝑝.

   • Der Initiator berechnet 𝐵^𝑎 = (𝑔^𝑏 mod 𝑝)^𝑎 mod 𝑝 = 𝑔^𝑎𝑏 mod 𝑝.
   • Auf der anderen Seite wird äquivalent 𝐴^𝑏 = (𝑔^𝑎 mod 𝑝)^𝑏 mod 𝑝 = 𝑔^𝑎𝑏 mod 𝑝.

3.3 Elliptische Kurven (EC)

3.3.1 Elliptische Kurven über reellen Zahlen R

Elliptische Kurven E(R) werden in der Normalform nach WEIERSTRASS durch Gleichungen der Form

(10)

beschrieben. Wegen der (nur) zwei freien Parameter 𝑎 und 𝑏 ist jede elliptische Kurve durch zwei Punkte 𝑃₁,𝑃₂ eindeutig definiert. Insofern ist jeder weitere Punkt durch die Kenntnis von 𝑃₁ und 𝑃₂ festgelegt.

Für 𝑎 ergibt die Differenz beider Gleichungen

was dann zur Berechnung von 𝑏 verwendet werden kann.

Zieht man entsprechend Abbildung 17) durch 𝑃₁ und 𝑃₂ eine Gerade, so berechnet sich ein dritter (Schnitt-) Punkt 𝑃₃′ = (𝑥₃,𝑦₃′) nach der Geradengleichung:

mit dem Anstieg:

(11)

Den Schnittpunkt 𝑃₃′ mit der elliptischen Kurve

findet man (unter Zuhilfenahme von 𝛼³ −𝛽³ = (𝛼 −𝛽)(𝛼² +𝛼𝛽 +𝛽²)) durch Gleichsetzen:

Aus der Geradengleichung ist nun 𝑦₃′ berechenbar:

und so für den Kurvenpunkt 𝑃₃ = (𝑥₃,𝑦₃) = (𝑥₃,−𝑦₃′):

(14)

3.3.2 Elliptische Kurven über endlichen Körpern F_𝑞

Der kryptographische Anwendungsfall sind elliptische Kurven über endlichen (Restklassen-) Körpern F_𝑞, welche selbst entweder Primzahlenkörper F_𝑝 oder auch Binärkörper F_2^𝑚 sind [22, 57, 52, 13].⁴⁰ Dafür definiert man die Addition zweier Punkte 𝑃₁,𝑃₂ zu 𝑃₃ = 𝑃₁ +𝑃₂ so, daß 𝑃₃ (wie in Abbildung  17 dargestellt) wieder auf der elliptischen Kurve liegt. Die Menge aller dieser Punkte 𝑃₃ soll eine ABELsche Gruppe (𝐺,+) bilden, d. h. es müssen folgende Bedingungen erfüllt sein:

1. Die Addition von 𝑃₁,𝑃₂ ∈ 𝐺 führt zu 𝑃₃ ∈ 𝐺. Für die Kurve E(F_𝑝) ergeben sich folgende Formeln:⁴¹

   1. Punktaddition:

      (15)

   2. Punktverdoppelung:

      Für 𝑃₁ = 𝑃₂ = 𝑃 = (𝑥,𝑦) wird die Tangente angelegt (denn 𝜆 kann nicht nach Formel 11 berechnet werden), d. h. der Anstieg 𝜆 entspricht der ersten Ableitung im Punkt 𝑃.

      

      Mit 𝑥 = 𝑥₁ = 𝑥₂ ergibt sich aus Additionsformel 15 direkt das Ergebnis:

      (16)

   3. Im Fall 𝑥₁ = 𝑥₂ und 𝑦₂ = −𝑦₁ wird 𝑃₃ = (0,0) definiert.
2. Die Addition sei assoziativ: 𝑃₁ +(𝑃₂ +𝑃₃) = (𝑃₁ +𝑃₂) +𝑃₃ für 𝑃₁,𝑃₂,𝑃₃ ∈ 𝐺.
3. Es gibt das neutrale Element 𝑂 ∈ 𝐺 mit 𝑃+𝑂 = 𝑂+𝑃 = 𝑃 für 𝑃 ∈ 𝐺 . Nimmt man an, daß 𝑂 = (𝑥₁,𝑦₁) ist, dann muß die Forderung 𝑃₃ = 𝑃₂ gestellt werden, um (𝑥₁,𝑦₁) zu ermitteln. Dazu verwendet man 𝑥₃ = 𝜆² −𝑥₂ −𝑥₁ mit 𝜆 → ∞, was zu 𝑥₁ = lim _𝜆→∞𝜆² −2𝑥₂ = ∞ und 𝑦₁ = lim _{𝜆,𝑥1→∞}𝜆(𝑥₁ −𝑥₂)−𝑦₂ = ∞ führt. Das neutrale Element ist somit 𝑂 = (∞,∞), was auch geometrisch einleuchtet.
4. Zu jedem beliebigen Element 𝑃 ∈ 𝐺 findet man −𝑃 ∈ 𝐺, so daß wieder (−𝑃)+𝑃 = 𝑂 gilt. Als Folge der Betrachtungen zum neutralen Element (siehe voriger Punkt) ergibt sich: −𝑃 = (𝑥,−𝑦)

Elliptische Kurven über F_2^𝑚 verwenden die Form 𝑦² + 𝑥𝑦 = 𝑥³ + 𝑎𝑥² + 𝑏, funktionieren aber grundsätzlich nach demselben Prinzip. Ohne weiteren Beweis sei hier angegeben (vgl. zum Beispiel [22, S. 3.1.2], zu den Algorithmen siehe auch [21, 12, 17, 4]):

• Punktaddition: 𝑃₃ = 𝑃₁ +𝑃₂ = (𝜆² +𝜆+𝑥₁ +𝑥₂ +𝑎,𝜆[𝑥₁ +𝑥₃]+𝑥₃ +𝑦₁)
• Punktverdoppelung: 𝑃₃ = 2𝑃 = (𝜆² +𝜆+𝑎,𝑥² +𝑥₃[𝜆+1]), mit 𝜆 = 𝑥 +𝑦/𝑥
• negativer Punkt: −𝑃 = (𝑥,𝑥 +𝑦)

Zur Verifikation eines Kurvenpunktes substituiert man 𝑧 = 𝑦/𝑥 und erhält eine quadratische Gleichung in F_2^𝑚 .⁴²

Die beiden Lösungen sind wegen 𝑧² +𝑧 = 𝑧(𝑧+1) dann 𝑧 und 𝑧+1, unterscheiden sich also nur im niederwertigsten Bit [23, A.12.9].

Für die kryptographische Anwendung, insbesondere für Verfahren, die auf dem diskreten Algorithmus basieren, wird zuerst die Gruppenpotenz definiert zu 𝑦 = 𝑥^𝑛 = 𝑥 ⋄𝑥 ⋄𝑥𝑥 ⋄𝑥. Das diskrete Logarithmus Problem besteht nun bekanntermaßen darin die Zahl 𝑛 zu finden, was bei einer Gruppenaddition per elliptischer Kurve ziemlich schwierig ist. Eines der bekanntesten Beispiele ist die Umsetzung des Diffie-Hellman Schlüsselaustausches (vgl. Abschnitt 3.2) auf elliptische Kurven [6, 57]. Aber auch Signatur- und Public-Key Verfahren können damit realisiert werden [8, 24].