Karsten Fischer, Sven Kauer

Public Key Kryptographie mit dem RSA Schema

2

Gliederung

I. Historischer HintergrundII. Public Key KryptographieIII. BeispielszenarioIV. Einweg-FunktionV. RSA VerfahrenVI. AlgorithmusVII. BeispielVIII.Signieren von NachrichtenIX. Schwächen des RSAX. Angriffe auf den RSAXI. EinsatzgebieteXII. Zusammenfassung XIII.Quellen

3

Historischer Hintergrund

• Bis in die 70er symmetrische Verfahren→ Problem der Schlüsselverteilung

• 1976 Theorie über asymmetrische Verschlüsselung

• 1977 RSA am MIT (Rivest, Shamir, Adleman)

• 1980 durch RSA Data Security Inc. patentiert

• 1991 implemetiert in PGP durch Phil Zimmermann

• 2000 US-Patent läuft aus→ RSA weltweit einsetzbar

4

Public Key Kryptographie

Theorie von W. Diffie und M. Hellman, 1976

Asymmetrisches Verfahren:

• zwei verschiedene Schlüssel:1. Kodierung einer Nachricht2. Dekodierung einer Nachricht

• Kodierungsschlüssel soll keine Schlüsse auf den Dekodierungsschlüssel zulassen

5

Public Key Kryptographie

Public Key-Prinzip:

• (wichtige) asymmetrischen Variante

• Kodierungsschlüssel öffentlich (public key)

• Dekodierungsschlüssel geheim (private key)

6

Public Key Kryptographie

Public Key-Prinzip:

jeder Teilnehmer T hat folgende Schlüssel:• Public Key E = ET (Encryption)• Private Key D = DT (Decryption)

Eigenschaften der Schlüssel:1. für jede Nachricht m gilt:

D(E(m)) = m und E(D(m)) = m

2. privater Schlüssel D (praktisch) nicht aus Schlüssel E zu erschließen.

7

Beispielszenario

Vorbereitungen:

• Kommunikationsgruppe

• Jeder Teilnehmer T bekommt Schlüsselpaar (ET, DT)

• Schlüsselpaare der Teilnehmer sind verschieden

• Schlüssel E wird verteilt (Publikationsorgan/Zertifizierungsstelle)

• Schlüssel D bleibt geheim

8

Beispielszenario

Senden und Empfang:

• A will B die Nachricht m Schicken

• A sucht Schlüssel EB von B heraus

• A verschlüsselt m mittels EB

• A verschickt EB(m) an B

• B entschlüsselt mit DB(m): DB(EB(m)) = m

9

Beispielszenario

Sicherheit:

• Kein anderer Teilnehmer kann EB(m) entschlüsseln, weil ihm DB von B fehlt

Analogie: Briefkasten:

• jeder kann Post in den Briefkasten einwerfen• nur Briefkastenbesitzer kann sie herausholen

• Public Key E → Namensschild

• Private Key D → Briefkastenschlüssel

10

Einweg-Funktionen

Kodierungsschlüssel soll keine Schlüsse auf den Dekodierungsschlüssel zulassen

↓

Suche eine bijektive Funktion f(x) = y, die folgende Anforderungen erfüllt:

1. einfache Berechnung von y bei bekanntem x2. schwere Berechnung von x bei bekanntem y

↓

„Einweg-Funktionen“ (Trapdoor-functions)

11

Einweg-Funktionen

Def: Eine umkehrbar eindeutige ("bijektive") Funktion

f : A → B mit x → y = f (x)

heißt Einweg-Funktion, wenn der Funktionswert y relativ leicht aus dem Argument x berechnet werden kann, wenn es aber andererseits bei Kenntnis von y nur mit sehr großem Aufwand möglich ist, das Argument x zu ermitteln, das zum Funktionswert y gehört.

12

Einweg-Funktionen

Analogie: Telefonbuch (einer großen Stadt)

• Funktion f ermittelt Telefonnummer x aus Namen y→ Nachschlagen (TB ist alphabetisch sortiert)

• Umkehrfunktion f -1 nur sehr aufwendig(„ermittele Name y zur Telefonnummer x“)→ nach Nummern sortiertes TB?

13

Einweg-Funktionen

Einige Einwegfunktionen:

• Faktorisierung:y = x1 ∙ x2

• Diskreter Logarithmus:y = bx mod n

• Diskrete Wurzel: y = xa mod n (n nicht

prim)

14

RSA-Verfahren

• 1977 entdeckt von Rivest, Shamir und Adleman

• Verfahren zum Erzeugen von Einweg-Funktionen

• basiert insbesondere auf:

• Euklidischer Algorithmus

• (kleinen) Satz von Fermat

• kein Algorithmus zur schnellen Primfaktorzerlegung bekannt

15

RSA-Verfahren

Euklidischer Algorithmus:

While (a>0) And (b>0)

If a > b

Then a = a Mod b

Else b = b Mod a

End If

Wend

ggT = a + b

16

RSA-Verfahren

Erweiterter Euklidischer Algorithmus:

Satz: Zu je zwei natürlichen Zahlen a und b (b ≠ 0) gibt es ganze Zahlen x und y mit der

EigenschaftGGT(a, b)= a ∙ x + b ∙ y.

D.h. für teilerfremde a,b (GGT(a,b)=1): a ∙ x = 1 - b ∙ y bzw. a ∙ x ≡ 1 (mod b)

↓

x ist das Inverse zu a mod b

17

RSA-Verfahren

Beispiel: Erweiterter Euklidischer Algorithmus

• Zwei teilerfremde Zahlen: a = 14, b = 51 (GGT(14, 51)=1)

• mögliche Werte: x = 11, y = -3

↓

11 ist das Inverse zu 14 mod 51

a ∙ x - b ∙ y = 1

(a ∙ x) mod b ≡ 1

14 ∙ 11 - 51 ∙ -3 = 1

(14 ∙ 11) mod 51 ≡ 1

18

RSA-Verfahren

Satz von Fermat:

Satz: Ist p eine Primzahl und a eine zu p teilerfremde natürliche Zahl, so ist ap-1 ≡ 1 (mod p).

• Findet man auch als: ap ≡ a (mod p)

19

RSA-Verfahren

Satz von Fermat:

2 2mod7 3 3mod7 5 5mod7

0 1 1 1 1 1 1

1 2 2 3 3 5 5

2 4 4 9 2 25 4

3 8 1 27 6 125 6

4 2 2 81 4 625 2

5 4 4 243 5 3125 3

6 8 1 729 1 15625 1

7 2 2 2187 3 78125 5

20

RSA-Verfahren

Beweis: Satz von Fermat• Sind a, b inkongruent modulo einer festen Zahl n ,

dann sind auch x ∙ a und x ∙ b inkongruent (mod n) f.a. x > 0 mit GGT(x,n )=1

↓1 ∙ 2 ∙ … ∙ (p-1) = (1 ∙ a) ∙ (2 ∙ a) ∙ … ∙ ((p-1) ∙ a) (mod p)

↓W = W ∙ ap-1 (mod p)

↓1 = ap-1 (mod p)

qed.

21

RSA-Verfahren

Anwendungen des Satzes

• Primzahlerzeugung?

• Wenn p Primzahl, dann gilt ap ≡ a (mod p)

• Gilt auch:„Wenn ap ≡ a (mod p), dann ist p Primzahl“?

• Nein → Fermatsche Pseudoprimzahlen

22

RSA-Verfahren

Anwendungen des Satzes

• Primzahltest?

• Fermatscher Primzahltest:• Berechne b = an-1 (mod n)• Prüfe b = 1, bei erfolg: b Primzahlkandidat

• Langsam und Aufwendig

23

Algorithmus Kodierung

• Wähle Zufällig zwei Primzahlen p und q, welche „nahe“ beieinander liegen.

• Bestimmt deren Produkt N.• Ermittle .• Bestimme ein e , s. d. e > 1 und teilerfremd

zu .• Berechne aus den geheimen

Schlüssel d.

• Somit ist der öffentliche Schlüssel: N, eund der geheime Schlüssel: d

• Die Kodierung erfolgt mit:

)1)(1()( qpN)(N

))(mod(1 Nde

)mod(NKC e

24

Beispiel Schlüsselerstellung

• Primzahlen: p = 463 und q = 467

215292)1)(1()( qpN• ermitteln:)(N• ermitteln:N 216221pqN

• bestimmen: , teilerfremd zu , e Ne 1 277e)(N• ermitteln:d ))(mod(1 Nde

1)( kNde 1)(0 dekN

12772152920 dkmögliche Lösung: ,22k 17099d

• öffentliche Schlüssel: N = 216221 und e = 277• geheimer Schlüssel: d = 17099

25

Beispiel Verschlüsselung

• öffentliche Schlüssel: N = 216221 und e = 277• Klartext K = 174• C ermitteln: )mod(NKC e

)216221mod(174277C• gerechnet mit modularer Exponentiation

Quad := b, Halb := e, Erg := 1 while Halb > 0

if Halb mod 2 > 0 then Erg := (Erg * Quad) mod m Quad = (Quad * Quad) mod m Halb = Halb div 2

end while return Erg

• Geheimtext C = 206690

26

Beispiel Dekodierung

• öffentliche Schlüssel: N = 216221• geheimer Schlüssel: d = 17099• Geheimtext C = 206690• K ermitteln: )mod(NCK d

)216221mod(20669017099K

• gerechnet mit modularer Exponentiation• Klartext K = 174

)mod(NCK d• Dekodierung mit .

27

Signieren von Nachrichten

• Idee: Dokumente mit einer digitalen „Unterschrift“ versehen.

• 1. Vorteil: Integrität, d. h. es wird die Unversehrtheit der übermittelten Nachricht sichergestellt

• 2. Vorteil: Authentizität, d. h. die Nachricht wurde vom richtigen Absender versandt

28

Signieren von Nachrichten

• Absender besitzt eigenen Schlüsselsatz.

• Absender kodiert seine Nachricht mit d,sprich:

• Absender versendet signierte und unsignierte Nachricht an Empfänger.

• Empfänger dekodiert die Nachricht mit e,sprich:

• Empfänger vergleicht unsignierte und dekodierte Nachricht miteinander und prüft auf Gleichheit.

)mod(NKC d

)mod(NCK e

29

Schwächen des RSA

• asymmetrisches Verfahren, welches für das Ver- und Entschlüsseln große K viel Zeit benötigt

• Wahl der Primzahlen kann nicht einfach zufällig erfolgen

• „Sicherheit“ beruht auf der Annahme das die Zerlegung von N in seine Primfaktoren in polynomieller Zeit nicht gelingen kann.

• Beweis steht aus• Shor-Algorithmus löst das Problem auf

Quantencomputern in P

30

Angriffe auf den RSA

• Verfahren substituiert Klartext zu Geheimtext, weshalb Angriffe mit der Known-Plaintext-Angriffe und Wahrscheinlichkeitsanalyse möglich sind.

• Bei schlecht gewählten Primzahlen, kann aus N auf wenige mögliche Paare geschlossen werden.

• Zerlegung in Primfaktoren ist bedingt schon gelungen: RSA-567 mit 174 Ziffern

Mersenne-Zahl mit 228 Ziffern

• Timing Attacks

12757

31

Timing Attacks auf den RSA

• Idee: Geheimtexte mit dem öffentlichen Schlüssel so erstellen, das die Dechiffrierung lange benötigt, um fehl zu schlagen.

• Vorgehen• Festlegen eines großen Startwertes• Schleife

• Messen der Laufzeit der einzelnen Anfragen wird gemessen.

• Aus auffälligen Messwerten wird auf Werte geschlossen, welche ausprobiert werden.

• Ausgabe des geheimen Schlüssels

32

Einsatzgebiet

• Internet- u. Telefonie-Infrastruktur: X.509-Zertifikate

• Übertragungs-Protokolle: IPSec SSL TLS SSH WASTE

• E-Mail-Verschlüsselung: PGP S/MIME

• Authentifizierung französischer Telefonkarten

33

Zusammenfassung RSA

• asymmetrisches Verschlüsselungsverfahren

• benutzt öffentliche und geheime Schlüssel

• Nachrichten können nur von einem Empfänger gelesen, aber vielen Absendern versandt werden

• Algorithmus beruht auf der scheinbaren Unmöglichkeit der Zerlegung von großen Produkten in Primfaktoren

• Verschlüsselung und Entschlüsselung erfolgt nach einfachen Formeln

34

Quellen

• „Handbook of Applied Cryptography“A. Menezes, P. C. van Oorschot, S. A. Vanstone

• „Remote Timing Attacks are Practical“D. Brumley, D. Boneh

• „Pulic Key Cryptographie“J. Ziegenbalg

• http://de.wikipedia.org/wiki/RSA-Kryptosystem

• http://www.heise.de/newsticker/meldung/42719