Kryptologie Klaus Becker (2002). KB Kryptologie 2 E-mail an K. Becker An: [email protected] Von: [email protected] Betrifft: Kontoeröffnung

KryptologieKryptologie

Klaus Becker(2002)

2

KB

Kry

pto

log

ieE-mail an K. BeckerE-mail an K. Becker

An: [email protected]: [email protected]: Kontoeröffnung

Sehr geehrte Herr Becker,

Sie haben mit Ihrer Mail vom 1.8.2002 ein Konto bei unserer Bank beantragt. Wir danken Ihnen für das Vertrauen in unsere Bank. Selbstverständlich können wir Ihnen ein Konto einrichten. Die Kontonummer lautet: 314 216. Sie erhalten demnächst per Post eine Kreditkarte (PIN 9138). Für die Einrichtung des Kontos sind wir leider gezwungen, Ihnen einen Unkostenbetrag von 50 Euro in Rechnung zu stellen. Wir haben diesen Betrag bereits von Ihrem Konto abgebucht. Bitte zahlen Sie diesen Betrag schnellstmöglich auf Ihr Konto ein.

Mit freundlichen Grüßen

P. Theuerkauf(Leiter der Service-Abteilung)

3

KB

Kry

pto

log

ieSicherheitsproblemeSicherheitsprobleme

Authentizität: Stammt die Nachricht wirklich von der billigen Bank, oder erlaubt sich hier jemand einen Scherz?

Integrität: Hat jemand die Nachricht manipuliert (PIN geändert)?

Verbindlichkeit: Die Bank behauptet, die Nachricht so nicht verschickt zu haben. Stimmt das?

Vertraulichkeit: Wurde die Nachricht abgefangen und von einer unbekannten Person gelesen?

4

KB

Kry

pto

log

ieSicherheitsanforderungenSicherheitsanforderungen

Authentizität: Die Nachricht, die man erhält, stammt wirklich von der Person, die als Absender angegeben ist.

Integrität: Die Nachricht, die man erhält, ist von keiner dritten Person manipuliert worden.

Verbindlichkeit: Der Urheber kann nachträglich nicht bestreiten, die Nachricht verfasst zu haben.

Vertraulichkeit: Die Nachricht kann nicht von dritten Personen gelesen werden.

5

KB

Kry

pto

log

ieTeil 1Teil 1

Verschlüsselung

6

KB

Kry

pto

log

ieKommunikationssituationKommunikationssituation

Liebe ...

Angreifer

Sender Empfänger

Nachricht

7

KB

Kry

pto

log

ieChiffriersystemeChiffriersysteme

xKlartext

yGeheimtext

Schlüssel

f

Verschlüsselungs-funktion

xKlartext

Schlüssel

f*

Entschlüsselungs-funktion

Beachte: Chiffriersysteme dienen der Ver- und Entschlüsselung von Nachrichten. Sie sollen Vertraulichkeit gewähren.

8

KB

Kry

pto

log

ieSicherheit bei ChiffriersystemenSicherheit bei Chiffriersystemen

Prinzip von Kerckhoff: Die Sicherheit eines Chiffriersystems darf nicht von der Geheimhaltung der Ver- und Entschlüsselungsalgorithmen abhängen. Sie darf sich nur auf die Geheimhaltung der Schlüssel gründen.D.h.: Es sollte praktisch nicht möglich sein, Schlüssel aus Klartext-Geheimtext-Paaren (x,y) zu erschließen.

9

KB

Kry

pto

log

ieSymmetrische ChiffriersystemeSymmetrische Chiffriersysteme

xKlartext

Beispiele: • Caesar-Chiffriersystem• Vigenere-Chiffriersystem

s

yGeheimtext

Schlüssel

f


s

xKlartext

Schlüssel

f*


10

KB

Kry

pto

log

ieSymmetrische ChiffriersystemeSymmetrische Chiffriersysteme

Aufgabe:

Beurteile symmetrische Chiffriersysteme hinsichtlich des Aufwands

für die Erzeugung von Schlüsseln,

für den Austausch von Schlüsseln.

Betrachte den Fall, dass bereits n Teilnehmer sich auf das Chiffriersystem geeinigt haben und dass ein neuer Teilnehmer hinzukommt.

11

KB

Kry

pto

log

ie

Asymmetrische Asymmetrische ChiffriersystemeChiffriersysteme

cB

f f*

dB

x xyKlartext



KlartextGeheimtext

c: öffentlicher Schlüsseld: privater Schlüssel

BA

Jeder Teilnehmer verfügt über zwei Schlüssel:

12

KB

Kry

pto

log

ie


cB

f f*

dB

x xyKlartext KlartextGeheimtext

BA

Kommunikationsprotokoll:

A verschlüsselt x mit dem öffentlichen Schlüssel von B: y = f(cB,x).

A sendet y an B.

B entschlüsselt y mit seinem privaten Schlüssel: x = f*(dB,y).

13

KB

Kry

pto

log

ie


(c,d)

A: dA

A: cA

Die Schlüssel werden von einer Schlüsselvergabestelle erzeugt.

Die öffentlichen Schlüssel werden in einer öffentlichen Datenbank bereitgestellt.

Die Übermittlung des privaten Schlüssels an den Teilnehmer muss sicher sein.

Die privaten Schlüssel werden von den Teilnehmern geheim gehalten.

B: cB

...

dA A

14

KB

Kry

pto

log

ie


Sicherheitsanforderungen:

Es ist praktisch unmöglich, aus dem öffentlichen Schlüssel cT den privaten Schlüssel dT zu erschließen.

Es ist praktisch unmöglich, den privaten Schlüssel dT aus Klartext-Geheimtextpaaren (x,y) zu erschließen.

15

KB

Kry

pto

log

ieRSA-VerfahrenRSA-Verfahren

RSA: Rivest, Shamir, Adleman (1977)

Schlüsselerzeugung:

Wähle zwei Primzahlen p und q.Bsp.: p = 7; q = 11

Berechne n = pq und = (p-1)(q-1).Bsp.: n = 77; = 60

Bestimme c < mit ggT(c,) = 1. Günstig: c Primzahl mit p,q < c <

Bsp.: c = 13

Bestimme d mit mod(cd,) = 1. Bsp.: d = 37 (1337 = 481 = 860 + 1)

Öffentl. Schlüssel: (c,n) Bsp.: (13,77)

Privater Schlüssel: (d,n) Bsp.: (37,77)

16

KB

Kry

pto

log

ieRSA-VerfahrenRSA-Verfahren

Schlüssel:

Öffentl. Schlüssel: (c,n) Bsp.: (13,77)

Privater Schlüssel: (d,n) Bsp.: (37,77)

Verschlüsselung:

y = mod(xc,n) Bsp.: x = 6; y = mod(613,77) =

62Entschlüsselung:

x = mod(yd,n) Bsp.: y = 62; x = mod(6237,77) =

6

Bedingung: x < p,q

17

KB

Kry

pto

log

ie

RSA - mathematische RSA - mathematische GrundlagenGrundlagen

Mathematische Grundlage: Satz von Euler

Für zwei teilerfremde natürliche Zahlen a und m gilt:

a (m) mod m = 1 bzw. mod(a(m), m) = 1Eulersche -Funktion:

(m): Anzahl der zu m teilerfremden Zahlen, die < m sindBsp. für die Aussage des Satzes von Euler:

m = 5: (5) = 4, da 1, 2, 3, 4 zu 5 teilerfremd sind.

mögliche Werte für a: 1, 2, 3, 4, 6, ... (alle teilerfremd zu m = 5)

Satz liefert: 14 mod 5 = 1 bzw. 5 | 14 1 24 mod 5 = 1 bzw. 5 | 24 144 mod 5 = 1 bzw. 5 | 34 1 44 mod 5 = 1 bzw. 5 | 44 164 mod 5 = 1 bzw. 5 | 64 1 74 mod 5 = 1 bzw. 5 | 74 1...

18

KB

Kry

pto

log

ieRSA - KorrektheitRSA - Korrektheit

Zu zeigen: mod(mod(xc ,n)d ,n) = x bzw. mod(xc)d ,n) = x Es gilt: x und n sind teilerfremd, da x < p, q und n = pq.

Setze: = (p-1)(q-1). Dann ist = (n).

Satz von Euler liefert: mod(x, n) = 1 (*)

Konstruktion von c und d liefert: mod(cd,) = 1

Also: Es gibt k mit cd = k + 1

Folglich: (xc)d = xcd = xk + 1 = xxk

Mit (*) gilt: mod(xc)d ,n) = mod(x(x)k ,n) = mod(x,n) = x

19

KB

Kry

pto

log

ieRSA-Verfahren mit DERIVERSA-Verfahren mit DERIVE

Hilfsfunktionen:

MODINV

MODPOT

dient zur Bestimmung von d mit mod(cd,) = 1

Aufruf:

MODINV(c, )

dient zur Bestimmung der modularen Potenz

Aufrufe:

mod(xc,n): MODPOT(x, c, n)

mod(yd,n): MODPOT(y, d, n)

c

d

xcn

y

MODPOT

ydn

x

20

KB

Kry

pto

log


Erzeugung der Schlüssel:

DERIVE-Protokoll:p := NEXT_PRIME(1000)1009q := NEXT_PRIME(2000)2003n := p·q2021027 := (p - 1)·(q - 1)2018016c := NEXT_PRIME(2500)2503d := MODINV(c, )1454455

Ergebnis:

Öffentl. Schlüssel: (c,n) Bsp.: (2503, 2021027)

Privater Schlüssel: (d,n) Bsp.: (1454455, 2021027)

21

KB

Kry

pto

log


Verschlüsselung der Nachricht „HALLO“:

Vorbereitung: KodierungHALLO 08.01.12.12.15 801|121|215beachte: benutzte Zahlen < p,q

DERIVE-ProtokollMODPOT(801, c, n)234247MODPOT(121, c, n)1436140MODPOT(215, c, n)697452

Ergebnis:verschlüsselte Nachricht: 234247|1436140|697452

Öffentl. Schlüssel: (c,n) = (2503, 2021027)

Privater Schlüssel: (d,n) = (1454455, 2021027)

22

KB

Kry

pto

log


Entschlüsselung:

Nachbereitung: Dekodierung801|121|215 08.01.12.12.15 HALLO

DERIVE-ProtokollMODPOT(234247, d, n)801MODPOT(1436140, d, n)121MODPOT(697452, d, n)215

Ergebnis:entschlüsselte Nachricht: HALLO

Öffentl. Schlüssel: (c,n) = (2503, 2021027)

Privater Schlüssel: (d,n) = (1454455, 2021027)

23

KB

Kry

pto

log

ieÜbungÜbung

Erzeugen Sie sich mit Derive zunächst ein Schlüsselpaar. Verschlüsseln Sie anschließend mit Derive eine (nicht zu lange) Nachricht. Testen Sie, ob beim Entschlüsseln die ursprüngliche Nachricht wieder entsteht.

(Sie können auch eine Nachricht mit ihrem Nachbarn verschlüsselt austauschen.)

24

KB

Kry

pto

log

ieRSA-Verfahren knackenRSA-Verfahren knacken

RSA knacken:

1. Mögl.: (c,n) (d,n)

2. Mögl.: (x,y), (c,n) (d,n)

Strategie 1. Mögl.: Strategie 2. Mögl.:

n (p,q) x = mod(yd,n)

(p,q) (x,y,n) d

(c,) d

Schwierigkeit:

Primfaktorzerlegung von n diskreter Logarithmus

25

KB

Kry

pto

log

ieEinwegfunktionenEinwegfunktionen

Einwegfunktion:

f ist eine umkehrbare Funktion mit Umkehrfunktion f*.

f kann mit geringem Aufwand berechnet werden.

f* kann nur mit sehr hohem Aufwand (praktisch nicht)

berechnet werden.Beispiel 1: Telefonbuch

f : Name Telefonnummerf*: Telefonnummer Name

f

f*

Beispiel 2: RSA

f : (p,q) n = pq Produkt von zwei Primzahlenf*: n (p,q) Primfaktorzerlegung

Bed.: n hat mehr als 155 Stell. (512 Bit)

26

KB

Kry

pto

log

ieÜbungÜbung

NEXT_PRIME(10^10)

10000000019

NEXT_PRIME(10^11)

100000000003

10000000019·100000000003

1000000001930000000057

FACTOR(1000000001930000000057)

10000000019·100000000003

Untersuchen Sie mit Derive, wie lang eine Produktberechnung und die zugehörige Berechnung der Primfaktorzerlegung dauert. Gehen Sie hierzu wie im unten abgebildeten Derive-Protokoll vor. Vergrößern Sie schrittweise die benutzten Primzahlen. Was fällt auf?

27

KB

Kry

pto

log

ieTeil 2Teil 2

Digitale Signatur

28

KB

Kry

pto

log

ieProbleme mit der UrheberschaftProbleme mit der Urheberschaft

Nachrichtenauthentisierung:

Gewährleistung der Integrität (Nachricht wurde nicht von Dritten verändert).

Gewährleistung der Authentizität (Nachricht stammt vom Absender)

Probleme:

Empfänger ändert die Nachricht ab (z. B.: erhöht den Überweisungsbetrag).

Absender streitet ab, die Nachricht verschickt zu haben (z. B.: streitet Börsentransaktion ab)

29

KB

Kry

pto

log

ieDigitale SignaturDigitale Signatur

Anforderungen an eine digitale Signatur

Authentizität: Nur der Urheber des Dokuments kann die Signatur erzeugen.

Nichtübertragbarkeit: Die Signatur kann nicht auf andere Dokumente übertragen werden.

Verbindlichkeit: Der Absender kann die Urheberschaft nicht abstreiten.

Verifizierbarkeit: Der Empfänger kann die Signatur zweifelsfrei prüfen.

30

KB

Kry

pto

log

ie

Erzeugung einer digitalen Erzeugung einer digitalen SignaturSignatur

dA

f f*

cA


BA

Grundidee

A verschlüsselt x mit seinem privaten Schlüssel.

31

KB

Kry

pto

log


dA

f f*

cA


BA

Zu den Anforderungen an eine digitale Signatur:

Authentizität: nur A verfügt über dA.

Nichtübertragbarkeit: anderes x, anderes y

Verbindlichkeit: nur A kann x in y umgewandelt haben

Verifizierbarkeit: B kann y nur mit cA in ein sinnv. x umwandeln

32

KB

Kry

pto

log


dA

f f*

cA


BA

Nachteile

Das signierte Dok. ist erst nach dem Entschlüsseln lesbar.

Es ist sehr aufwendig, das gesamte Dok. zu verschlüsseln.Ausweg

Erzeugung eines „digitalen Fingerabdrucks“

33

KB

Kry

pto

log

ieDigitaler FingerabdruckDigitaler Fingerabdruck

Grundidee:

Es wird eine geeignet komprimierte Form des Klartextes x ermittelt.

Beispiel: vereinfachte XOR-Kompression

Vorbereitung: binäre Kodierung gemäß ASCII-CodeUTA 85 | 84 | 65 01010101 | 01010100 | 01000001 = X1 | X2 | X3XOR-Kompression:Y1 = 00000000Y2 = Y1 XOR X1 = 00000000 XOR 01010101 = 01010101Y3 = Y2 XOR X2 = 01010101 XOR 01010100 = 00000001Y4 = Y3 XOR X3 = 00000001 XOR 01000001 = 01000000Nachbereitung: 01000000 0*1+0*2+0*4+0*8+0*16+0*32+1*64+0*128 = 64Ergebnis:85 | 84 | 65 64

34

KB

Kry

pto

log

ieHash-FunktionHash-Funktion

Hash-Funktionen

Funktion h, die jeder Nachricht x einen Prüfwert h(x) zuordnet (digitaler Fingerabdruck).

Beispiel:

x: UTA 85 | 84 | 65 h(x): 64

Einweg-Hash-Funktionen

Hashfunktion mit folgender Eigenschaft:Es gibt einen effizienten Algorithmus zur Berechnung von h(x) aus x, aber keinen effizienten Algorithmus zur Berechnung von x aus h(x) (d. h.: es ist praktisch unmöglich zu einem Hashwert eine passende Nachricht zu konstruieren).

35

KB

Kry

pto

log


Signierprotokoll:

A bestimmt zur Nachricht x den Hash-Wert h(x) mit der vereinbarten Hash-Funktion h.

A erzeugt die digitale Signatur für x: u = f(dA,h(x)).

A sendet (x,u) an B.

B entschlüsselt u mit dem öffentlichen Schlüssel von A: v = f*(dB,u).

B erzeugt den Hash-Wert h(x) und prüft, ob h(x) = v.

36

KB

Kry

pto

log

ie

Anforderungen an Hash-Anforderungen an Hash-FunktionenFunktionen

Anforderungen an gute Hash-Funktionen

Es ist praktisch unmöglich, aus dem Hashwert h(x) die Nachricht x zu erschließen. (Einweg-Hash-Funktion)

Es ist praktisch unmöglich, eine von x verschiedene Nachricht z mit h(x) = h(z) zu erzeugen. (Kollisionsresistenz)

Kollisionen

Eine Einweg-Hash-Funktion heißt kollisionsresistent, wenn es keinen effizienten Algorithmus gibt, um ein Paar (x, z) mit der Eigenschaft h(x) = h(z) zu finden.

37

KB

Kry

pto

log

ieRechtslageRechtslage

Gesetz über Rahmenbedingungen für elektronische Signaturen (Signaturgesetz – SigG) (16.05.2001)

„Zweck des Gesetzes ist es, Rahmenbedingungen für elektronische Signaturen zu schaffen.“

38

KB

Kry

pto

log

ieÜbungÜbung

Eine verbesserte Hash-Funktion arbeitet wie folgt:

Vorbereitung: binäre Kodierung gemäß ASCII-Code

UTA 85 | 84 | 65 01010101 | 01010100 | 01000001 = X1 | X2 | X3

XOR-Kompression:

Y1 = 00000000Y2 = Y1 XOR X1 = 00000000 XOR 01010101 = 01010101 10101010Y3 = Y2 XOR X2 = 10101010 XOR 01010100 = 11111110 11111101 Y4 = Y3 XOR X3 = 11111101 XOR 01000001 = 10111010 01110101

Nachbereitung: 01110101 1 + 4 + 16 + 32 + 64 = 117

Ergebnis:

85 | 84 | 65 117

Erzeugen Sie analog den Hash-Wert von ‚HALLO‘.

39

KB

Kry

pto

log

ieTeil 3Teil 3

Sicherheitsinfrastruktur

40

KB

Kry

pto

log

iePGPPGP

PGP - Pretty Good Privacy

Hybridverfahren: PGP kombiniert

symmetrisches Verfahren (z. B. IDEA – Intern. Data Encryption Algorithm)

asymmetrisches Verfahren (z. B. RSA)

Lit.: www.sicherheit-im-internet.de

41

KB

Kry

pto

log

iePGPPGP

Vorbereitung

PGP erzeugt mit RSA das Schlüsselpaar (c,d) des Teilnehmes T und speichert es in einer Datei (auf Diskette) ab. Um an (c,d) heranzukommen, muss T ein vorher festgelegtes Password eingeben.

T verschickt seinen öffentlichen Schlüssel an alle Personen, mit denen er korrespondieren will / legt ihn auf einen Schlüsselserver.

Verschlüsselung: A will x an B schicken.

PGP (von A) erzeugt einen Sessionkey s.

PGP (von A) verschlüsselt die Nachricht x mit IDEA: y = g(s,x)

PGP (von A) verschlüsselt den Sessionkey s mit RSA: u = f(cB,s)

A sendet (y,u) an B.

PGP (von B) entschlüsselt u: s = f*(dB,u)

PGP (von B) entschlüsselt y: x = g*(s,y)

42

KB

Kry

pto

log

ieVertauen zu SchlüsselnVertauen zu Schlüsseln

Situation:

A sendet seinen öffentlichen Schlüssel cA an B.

X fängt die Nachricht ab, erzeugt ein neues Schlüsselpaar (cX, dX), ersetzt cA durch cx und schickt die Nachricht an B.

B glaubt nun, der öffentliche Schlüssel von A sei cx. Grundproblem:

Wie kann gewährleistet werden, dass ein öffentlicher Schlüssel authentisch ist, also demjenigen gehört, der sich als Eigentümer ausgibt?

43

KB

Kry

pto

log

ieZertifizierungZertifizierung

Zertifizierungsstelle (Trusted Third Party; kurz TTP):

A erzeugt ein neues Schlüsselpaar (cA, dA).

A weist sich gegenüber TTP aus (ID-Nachweis).

A hinterlegt eine Kopie seines öffentlichen Schlüssels cA bei TTP.

TTP erstellt ein Zertifikat Z mit (u. a.) ID und cA. D.h.: TTP verschlüsselt (ID, cA) mit seinem geheimen Schlüssel Z.

Signieren:

A signiert Nachricht mit dA und schickt sie an B.

B testet, ob cA wirklich A gehört. D.h.: B entschlüsselt Z mit dem öffentl. Schlüssel von TTP / entnimmt ID und cA dem Zertifikat Z.

B entschlüsselt die Signatur mit cA.

B erzeugt den Hash-Wert der Nachricht und testet die Signatur.

44

KB

Kry

pto

log

ieLiteraturLiteratur

A. Beutelspacher: Kryptologie. Vieweg 1995.

S. Singh: Codes. Hanser 2002.

LOG IN 5/6 1996: Themenheft Kryptologie.

R. Baumann: Digitale Unterschrift. In: LOG IN 2/99 und 3-4/99.

H. Witten, I. Letzner, R.-H. Schulz: RSA & Co in der Schule. Serie in LOG IN ab 3-4/99.

45

KB

Kry

pto

log

ieLiteraturLiteratur

www.foebud.org/pgp/html/node36.htmlGlossar mit zentralen Begriffen der Kryptologie

www.sicherheit-im-internet.de/home.htmlInitiative des Bundes

www.educeth.ch/informatik/lernaufg/twokeys/docUnterrichtseinheit zur Einführung asymmetrischer Verfahren

...

Documents

Kryptologie Klaus Becker (2002). KB Kryptologie 2 E-mail an K. Becker An: [email protected] Von: [email protected] Betrifft: Kontoeröffnung