Lösungen zu Grundlagen der Kryptologie

Lo
¨sungen zu
Grundlagen der
Kryptologie
SS 2008
Hochschule Konstanz
Dr.-Ing. Harald Vater
Giesecke & Devrient GmbH
Prinzregentenstraße 159
D-81677 Mu¨nchen
Tel.: +49 89 4119-1989
E-Mail: [email protected]
L¨
osungen zu Kapitel 1
1.1
Der Vergleich von H A L L O und M F Q Q T ergibt eine zyklische Verschiebung von 5 Stellen im Alphabet.
K W J Z S I J um 5 Stellen zuru
¨ckgeschoben, ergibt F R E U N D E
1.2
Ciphertext:
M F Q Q T
K W J Z S I J
Plaintext:
H A L L O
F R E U N D E
Es werden soviele Zeichen ben¨otigt, um eine Sinnhaftigkeit bzw. Sinnlosigkeit eines Plaintextes (nach Ausprobieren aller Schlu
¨ssel) erkennen zu
ko¨nnen.
1.3
Es wird nur ein Ciphertextzeichen und das zugeh¨orige Plaintextzeichen
ben¨otigt. Die zyklische Verschiebung zwischen beiden Zeichen ist der C¨asarSchlu
¨ssel.
1.4
Betrachtung der Verschiebung der einzelnen Buchstaben:
Plaintext:
K R Y P T O L O G I E
Ciphertext:
L T B Q V R M Q J J G
Verschiebung:
1 2 3 1 2 3 1 2 3 1 2
Der sich wiederholende Schlu
¨ssel l¨aßt eine Vigen`ere-Chiffre mit dem
Schlu
¨sselwort A B C vermuten.
1.5
Man l¨aßt den Buchstaben A verschlu
¨sseln, bekommt das zugeh¨orige
Ciphertextzeichen, dann B , usw. bis Z . Hiermit kann dann die komplette Verschlu
¨sselungstabelle aufgestellt werden.
Notwendig: 26 Plaintextbuchstaben bei Alphabet mit 26 Zeichen (genaugenommen nur 25, denn der 26te Buchstabe ist dann der der u
¨brig bleibt).
1.6
Genau soviele Plain / Ciphertext-Zeichen, wie das Schlu
¨sselwort lang ist
(mu
¨ssen aber aufeinanderfolgende Plain / Ciphertext-Zeichen sein).
2
1.7
Plaintext:
K R Y P T O L O G I E
Schlu
¨sselwort:
G D M G D M G D M G D
Verschiebung:
7 4 13 7 4 13 7 4 13 7 4
Ciphertext:
R V L W X B S S T P I
1.8
50 Gruppen zu je 1 000 Buchstaben macht 50 000 Ciphertextzeichen
1.9
Dies ist nur unter der Bedingung m¨oglich, daß der Informationsgehalt (die
Entropie) des Plaintextes kleiner oder gleich dem des Schlu
¨ssels ist.
M¨ogliches Verfahren: Kompression des Plaintextes auf maximal 1 kByte,
dann One-Time-Pad Verschlu
¨sselung.
1.10
Plaintext:
K R Y P T O L O G I E
Schlu
¨sselwort:
G E H E I M N I S S E
Verschiebung:
7 5 8 5 9 13 14 9 19 19 5
Ciphertext:
R W G U C B Z X Z B J
Diese Vernam-Chiffre ist nicht perfekt (beweisbar) sicher. Der Schlu
¨ssel
wird zwar nur ein einziges mal verwendet, er stellt aber offensichtlich keine
echte Zufallszahl dar, sondern einen deutschen Text. Statistische Besonderheiten der deutschen Sprache k¨onnen fu
¨r einen Angriff ausgenutzt werden.
3
L¨
osungen zu Kapitel 2
2.1
Ja, gleicher Startwert und Schlu
¨ssel bedeutet gleiche Pseudozufallsfolge Z .
C1 = P1 +f Z
C2 = P2 +f Z
(Pi : Plaintext, Ci : Ciphertext)
Der Angreifer muß nur 2 Ciphertexte verEXORen und erh¨alt die verEXORten Plaintexte:
C1 +f C2
Beispiel:
=
P1 +f Z
f P +f Z
2
+
=
P1 :
C1 :
P2 :
C2 :
P1 +f P2
C1 +f C2 :
2.2
Es mu
¨ssen 2 Listen mit je 256 Eintr¨agen zu 8 Byte angelegt werden.
2 · 256 · 8 Byte = 260 Byte = 230 GByte = 1, 07 Mrd. GByte
2.3
Eine Woche hat 7 · 24 · 60 · 60 = 604 800 sec.
Ein DES-Chip schafft somit 6, 048 · 1011 Verschlu
¨sselungen pro Woche.
Insgesamt sind 256 = 7, 206 · 1016 Verschlu
¨sselungen notwendig.
Um dies in einer Woche zu schaffen, ben¨otigt man
DES-Chips. Diese kosten 595 715 DM.
4
7,206·1016
6,048·1011
= 119 143
2.4
Lange 000...0 Folgen zu Beginn des Plaintextes wu
¨rden einen periodischen
Ciphertext mit
DESk (ICV ) || ICV || DESk (ICV ) || ICV || . . .
C0 = DESk (ICV )
³
C1 = DESk DESk (ICV )
´
³
liefern, denn:
= DESk DES−1
k (ICV )
´
= ICV
Sind die 000...0 Folgen inmitten des Plaintextes, muß man nur den ICV
durch den vorhergehenden Ciphertextblock ersetzen.
Lange 111...1 Folgen liefern hingegen einen zuf¨alligen Ciphertext.
Deswegen wu
¨rde man gro¨ßere schwarze Bereiche (000...0 Folgen) des
Originalbildes durch regelm¨aßige Muster auch im verschlu
¨sselten Bild
wiedererkennen.
Beispiel:
Originalbild:
Bild verschlu
¨sselt mit
DES im CBC-Mode und
schwachem Schlu
¨ssel:
Bild verschlu
¨sselt mit
DES im CBC-Mode und
normalem Schlu
¨ssel:
2.5
a.) ECB-Mode: 1 Block im Plaintext falsch.
b.) CBC-Mode
1 Block im Plaintext falsch und
1 Bit im darauffolgenden Plaintextblock falsch.
c.)
1 Bit im Plaintext falsch
OFB-Mode
d.) CFB-Mode
1 Bit im zugeh¨origen m-Bit Plaintextblock falsch und
mehrere darauffolgende m-Bit Plaintextbl¨ocke falsch.
5
2.6
2.7
a.) 70 Byte mu
¨ssen um 2 Byte gepaddet werden
⇒
72 Byte
b.) 80 Byte mu
¨ssen um 8 (!) Byte gepaddet werden
⇒
88 Byte
a.) Nein, u
¨bliches Verfahren
b.) Ja, gleicher Schlu
¨ssel und gleicher ICV bedeuten gleiche Pseudozufallsfolge, siehe 2.1
2.8
2.9
ECB-Mode:
Blockchiffre, jeder Block wird mit der gleichen Operation
verschlu
¨sselt.
CBC-Mode:
Stromchiffre, Verschlu
¨sselungsoperation abh¨angig von vorangegangenen Daten.
OFB-Mode:
Additive Stromchiffre, Pseudozufallsfolge wird EXORverknu
¨pft (modulo 2 addiert)
CFB-Mode:
Additive Stromchiffre, Pseudozufallsfolge wird EXORverknu
¨pft (modulo 2 addiert)
Dieses Verfahren stellt ein Sicherheitsrisiko dar. Der MAC ist grunds¨atzlich
einer Known-Plaintext-Attack ausgesetzt, womit sich der Schlu
¨ssel durch
Exhaustive Key Search finden la¨ßt (einfacher DES). Hat der Angreifer den
Schlu
¨ssel gefunden, kennt er damit auch die linke H¨alfte des Triple-DES
Verschlu
¨sselungsschlu
¨ssels. Damit ist die Sicherheit der Datenverschlu
¨sselung nur noch die einer einfachen DES-Verschlu
¨sselung.
Der Kunde sollte fu
¨r den MAC auf jeden Fall einen separaten Schlu
¨ssel
verwenden.
2.10
Nein, bei der MAC-Berechnung darf es nicht m¨oglich sein (mit realistischem
Aufwand), zu manipulierten Daten den zugeh¨origen MAC zu finden. Bei
Padding mit '00'-Bytes ha¨tten beispielsweise die Daten 'AB' 'CD' 'EF' und
'AB' 'CD' 'EF' '00' den gleichen MAC.
2.11
Nein, wu
¨rde ein Angreifer beispielsweise zwei 8-Byte Bl¨ocke vertauschen,
erga¨be dies die gleiche EXOR-Summe und damit den gleichen MAC.
Ein 8 Byte langer CRC w¨are auch nicht sicherer, da es auch hier einfache
Verfahren gibt, die Daten so zu manipulieren, daß der gleiche CRC entsteht und damit der gleiche MAC (z.B. durch Addition von Vielfachen des
Generatorpolynoms).
6
2.12
Bekannt sind Pn , Cn und Cn−1 .
Pn−1
Pn
- +?
h
- +?
h
Diese h¨angen folgendermaßen zusammen:
K-
DESK ( Pn +f Cn−1 ) = Cn
Nun kann der Angreifer alle m¨ogli-
?
K-
DES
•
?
DES
?
?
Cn−1
che K in diese Gleichung einsetzen,
Cn
bis sie mit Gleichheit erfu
¨llt ist.
2.13
Nein, (lineare) Schieberegisterschaltungen liefern vorhersagbare Zufallszahlen. Mit einer Known-Plaintext-Attack kann ein Stu
¨ck Pseudozufallsfolge ermittelt werden.
Alle folgenden Pseudozufallszahlen ließen sich hieraus berechnen.
2.14
Zwei aufeinanderfolgende Zufallszahlenbl¨ocke sind ausreichend.
Zi = DESk ( IV + i )
Zi+1 = DESk ( IV + i + 1 )
= DES−1
k ( Zi )
=⇒
IV + i
=⇒
IV + i + 1 = DES−1
k ( Zi+1 )
nach IV + i aufgel¨ost und gleichgesetzt, ergibt:
−1
DES−1
k ( Zi ) = DESk ( Zi+1 ) − 1
Diese Gleichung kann fu
¨r alle m¨oglichen k u
¨berpru
¨ft werden.
2.15
G = 'A1' 'A2' 'A3' 'A4'
Z = '37' 'F2' 'AB' '4D'
Teilgeheimnisse:
Rekonstruktion:
⇒
T1 = Z
= '37' 'F2' 'AB' '4D'
⇒
T2 = G +f Z
= '96' '50' '08' 'E9'
⇒
G = T1 +f T2
= 'A1' 'A2' 'A3' 'A4'
7
L¨
osungen zu Kapitel 3
3.1
a.) Bei Verwendung symmetrischer Verfahren mu
¨ßten
³ ´
n
2
=
n·(n−1)
2
=
500 · 499
2
= 124 750
Schlu
¨ssel erzeugt werden.
b.) Bei Verwendung von Public-Key Verfahren mu
¨ßten nur 500 Schlu
¨ssel
(Paare) erzeugt werden.
3.2
a.)
7 + 9 mod 11
=
5
Probe : 5 − 9 mod 11 = 7
b.)
7 − 9 mod 11
=
9
Probe : 9 + 9 mod 11 = 7
c.)
7·9
mod 11
=
8
Probe :
d.)
7/9
mod 11
=
2
Probe : 2 · 9 mod 11 = 7
e.)
79
mod 11
=
8
Probe : 8 · 7 mod 11 = 1
8 mod 11 = 63 mod 11 = 7
9
9
(Fermat : 7 10 mod 11 = 1
3.3
⇒
a.)
13100 mod 101
=
b.)
21305 mod 101
= 25 mod 101 = 32
c.)
2199 mod 101
=
1
1
2
(Fermat)
· 2200 mod 101 =
=
3.4
d.)
47180 mod 77
=
e.)
2123 mod 77
=
1:
2:
3:
4:
5:
6:
Ordnung
Ordnung
Ordnung
Ordnung
Ordnung
Ordnung
1
3
6
3
6
2
7 9 · 7 mod 11 = 1)
1
1
2
102
2
mod 101
mod 101 = 51
(Euler) Φ(77) = (7−1)·(11−1) = 60
23 mod 77 = 8
(primitives Element)
(primitives Element)
3.5
Primitive Elemente aus GF(11): 2, 6, 7 und 8 , Suche durch Ausprobieren.
3.6
Die Ordnungen mu
¨ssen Teiler von p−1 = 100 sein. Folgende Ordnungen
treten auf (alle Teiler von 100):
1, 2, 4, 5, 10, 20, 25, 50, 100.
8
3.7
Der geheime Exponent d ist 1024 Bit lang, da d max. den Wert Φ(n)−1
annehmen kann (wegen d =
3.8
1
e
mod Φ(n)) und Φ(n) genauso lang ist wie n.
Public Key:
1024 Bit Modulus +
Secret Key:
1024 Bit Modulus + 1024 Bit Exponent = 2048 Bit
n = 3 · 11 = 33
17 Bit Exponent = 1041 Bit
Φ(n) = (3−1)·(11−1) = 20
d = 1 mod Φ(n) = 1 mod 20 = 21 mod 20 = 7
e
3
3
Schlu
¨sselpaar:
Public Key:
n = 33 , e = 3
Secret Key:
(n = 33), d = 7
Verschlu
¨sselung: y = 273 mod 33 = 19 683 mod 33 = 15
⇒ Ciphertext: y = 15
Entschlu
¨sselung: x = 157 mod 33 = 170 859 375 mod 33 = 27
⇒ Plaintext: x = 27
3.9
n = p·q = 5·7 = 35
Schlu
¨sselpaar:
Public Key:
n = 35
Secret Key:
p = 5, q = 7
Verschlu
¨sselung: y = 162 mod 35 = 256 mod 35 = 11
⇒ Ciphertext: y = 11
√
Entschlu
¨sselung: x = 11 mod 35 = 9, 16, 19 oder 26
⇒ Plaintext: x = 16
(daß es diese Wurzel ist, muß aus der Struktur des
Plaintextes hervorgehen)
3.10
¨
Offentliche
Schlu
¨ssel:
yA = 36 mod 17 = 15
yB = 37 mod 17 = 11
yC = 312 mod 17 = 4
gemeinsame symmetrische Schlu
¨ssel:
ZAB = 157 mod 17 = 116 mod 17 = 8
ZBC = 47 mod 17 = 1112 mod 17 = 13
ZAC = 46 mod 17 = 1512 mod 17 = 16
3.11
Eine digitale Signatur kann nur ein Teilnehmer berechnen (n¨amlich der
Besitzer des Secret Keys). Einen gu
¨ltigen MAC k¨onnen mindestens 2 Teilnehmer berechnen (n¨amlich beide Kommunikationspartner).
Somit leistet MAC nur Datenauthentisierung, w¨ahrend digitale Signaturen
sowohl Daten- als auch Benutzerauthentisierung gewa¨hrleisten.
9
3.12
Mit einer Hash-L¨ange von n Bit ergibt das Birthday-Paradoxon:
q
80
2
=
n = 2·
3.13
2·ln(2) · 2
³
n
2
1
log2 ( 1,177
)
≈ 1, 177 · 2
+ 80
´
n
2
≈ 159, 53 [Bit]
Nein, wenn als Schlu
¨ssel der Hash-Input verwendet werden wu
¨rde, w¨are bei
dem ersten Block der Schlu
¨ssel bekannt (der IV der Hashfunktion), und
man k¨onnte mit der Decrypt-Funktion des Chiffrieralgorithmus einfach die
Einwegfunktionalit¨at u
¨berwinden.
3.14
Das Rabin-Verfahren sollte u
¨berall dort eingesetzt werden, wo fu
¨r die
Signaturerzeugung ausreichend Rechenleistung in einer sicheren Umgebung
zur Verfu
¨gung steht (PC, Koprozessor), und fu
¨r die Signaturu
¨berpru
¨fung
nur sehr begrenzte Rechenleistung verfu
¨gbar ist (z.B. Chipkarte ohne Koprozessor).
3.15
Signaturerzeugung:
Signaturu
¨berpru
¨fung:
3.16
p : 1024 Bit
q:
160 Bit
α : 1024 Bit
x:
160 Bit
=⇒ insgesamt 2368 Bit
p : 1024 Bit
q:
160 Bit
α : 1024 Bit
y : 1024 Bit
=⇒ insgesamt 3232 Bit
Ja, das kann passieren. Mit ( s = H + x·r mod q ) wird s = 0 , falls
k
H = −x · r mod q .
Das ist sicherheitsrelevant, da sich ein Angreifer in diesem Fall den Secret
Key ausrechnen kann: x = − H mod q .
r
Wahrscheinlichkeit (H kann als zufa¨llig angenommen werden): 2−160 .
3.17
32 = 3 · 3 = 9
34 = 9 · 9 = 13
38 = 13 · 13 = 16
⇒
mod 17
mod 17
mod 17
310 mod 17 = 32 ·38 mod 17 = 9·16 mod 17 = 8
10
3.18
Beim DSA besteht der Exponent aus 160 Bit, davon sind durchschnittlich 80 Bit eine '1'. Somit mu
¨ssen 159 Quadrierungen und durchschnittlich
79 Multiplikationen berechnet werden.
3.19
ohne CRT:
mit CRT:
y = 127 mod 35 = 35 831 808 mod 35 = 33
mod 5 :
xp = 12 mod 5 = 2 ,
dp = 7 mod (5−1) = 3
→ yp = 23 mod 5 = 3
mod 7 :
xq = 12 mod 7 = 5 ,
dq = 7 mod (7−1) = 1
→ yq = 51 mod 7 = 5
Ru
¨cktransf.:
y=
³
( 17
mod 5)·7·yp +
( 51
´
mod 7)·5·yq mod 35
= (3·7·3 + 3·5·5)mod 35
= 138 mod 35 = 33
3.20
a.) RSA: Faktor 4
b.) DSA: keine Anwendung der CRT mo¨glich,
da modulo einer Primzahl gerechnet wird.
3.21
Bei n-stelligen Bina¨rzahlen ist durchschnittlich jede ( n·ln(2)) -te Zahl eine
Primzahl. Da gerade Zahlen keine Primzahlen sind (außer der 2), ist durchschnittlich jede ( 12 ·n·ln(2) )-te ungerade Zahl eine Primzahl.
⇒
3.22
1
·n·ln(2)
2
Wahl z.B. a = 2 :
= 640·ln(2) ≈ 443, 6 Versuche notwendig
220 mod 21 = 1 048 576 mod 21 = 4 6= 1
⇒ 21 ist keine Primzahl.
3.23
Wahl z.B. Z = 2 :
Probe:
3.24
951
952
953
954
955
mod
mod
mod
mod
mod
α = Z
101
101
101
101
101
=
=
=
=
=
p−1
q
mod p = 220 mod 101 = 95
95
36
87
84
1
Aus Zusammenstellung der ”Current Codebreaking Times”:
Modulusl¨ange fu
¨r Elliptische-Kurven Verfahren: ca. 160 Bit
Rechenaufwand, um diese Systeme zu brechen:
ca. 1011 MIPS-Years
Rechenzeit bei 1010 MIPS :
ca. 10 Jahre
11

Download Report