Blatt 3

Institut für
Theoretische Informatik
ITI
Dr. Jürgen Koslowski
Cryptologie 1+2
Aufgabenblatt 3, 2016-11-08
Übungsaufgabe 1
Bestimmen Sie unter Verwendung des erweiterten Euklidischen Algoritmus die Inversen modulo
2175 von
203 und 124 ,
falls sie existieren. Beschreiben Sie das Verfahren und führen Sie die notwendigen einzelnen
Rechnungen explizit aus (ggf. durch Angabe einer geeigneten Tabelle).
Lösungsvorschlag:
Der zweite Teil des erweiterten Euklidischen Algorithmus ist nur durchzuführen, wenn bei der
Bestimmung des größten gemeinsamen Teilers im ersten Teil der Wert 1 auftritt:
2175
203
145
58
= 10 · 203 + 145
= 1 · 145 + 58
= 2 · 58 + 29
= 2 · 29 +
0
Also folgt ggT(2175, 203) = 29 und das gesuchte Inverse existiert nicht.
Im zweiten Fall liefert der Euklidische Algorithmus
2175
124
67
57
10
7
= 17 · 124 + 67
= 1 · 67 + 57
= 1 · 57 + 10
= 5 · 10 + 7
= 1 ·
7 + 3
= 2 ·
3 + 1
und somit
0
1
(−17)
18
(−35)
193
= 17 ·
1
= 1 · (−17)
= 1 ·
18
= 5 · (−35)
= 1 ·
193
= 2 · (−228)
+ (−17)
+
18
+ (−35)
+
193
+ (−228)
+
649
Dies liefert 124−1 mod 2175 = 649 mod 2175 .
Übungsaufgabe 2
Bestimmen Sie die letzten beiden Ziffern von 19961996 ohne Zuhilfenahme eines Rechners.
Lösungsvorschlag:
Gesucht ist der Wert von x = 19961996 mod 100 . Um eine handhabbarere Basis zu erhalten,
wenden wir den Modulus an und erhalten
x = 961996 mod 100 = (−4)1996 mod 100 = 41996 mod 100
(∗)
wobei im letzten Schritt berücksichtigt wurde, dass der Exponent gerade ist.
Wegen ggT(4, 100) = 4 können wir den Satz von Euler und die daraus folgenden Rechenregeln
nicht anwenden. Andererseits erwarten wir schon, dass fortgesetztes Potenzieren von 4 modulo
100 irgendwann regelmäßiges Verhalten zeitigt. In der Tat gilt
41 mod 100 = 4
42 mod 100 = 16
43 mod 100 = 64
44 mod 100 = 56
45 mod 100 = 24
46 mod 100 = 96 = (−4) mod 100
woraus wir 411 mod 100 = 4 folgern. Damit ist 11 der kleinste Exponent mit der Eigenschaft,
dass ein früherer Wert wieder angenommen wird, und zwar der von 41 mod 100 . In diesem
“Orbit” der Größe 10 tritt 1 = 40 mod 100 allerdings nicht auf. Damit folgt
41996 mod 100 = 46 mod 100 = 212 mod 100 = 4096 mod 100 = 96
(In Gleichung (∗) hätte man evtl. gleich (−4) mod 100 mit 4096 mod 100 identifizieren und
so die Rechnung etwas abkürzen können.)
Alternativ kann man auch den Chinesischen Restsatz anwenden: 100 = 4 · 25 und ggT(4, 25) =
1 , sowie ϕ(4) = 2 und ϕ(25) = 20 .
Einerseits gilt 19961996 mod 4 = 0 , weil 1996 mod 4 = 0 . Andererseits erhält man 1996 mod
25 = (−4) mod 25 = 21 , und damit
19961996 mod 25 = (−4)1996 mod 25 = 416 mod 25 = 4 · 45
3
mod 25 = 4 · (−1)3 mod 25 = 21
Gemäß dem Chinesischen Restsatz wird h0, 21i ∈ Z4 × Z25 in Z100 abgebildet auf
4 · 4−1 mod 25 · 21 mod 100 = 4 · 19 · 21 mod 100 = 4 · 399 mod 100 = −4 mod 100 = 96
Übungsaufgabe 3
Zeigen oder widerlegen Sie: ist n =
torzerlegung von n , so gilt
Q
i<k
pri i mit pi prim für i < k die eindeutige Primfak-
ϕ(n) = n ·
Y
1
.
1−
pi
i<k
[Hinweis: Sie können die Formel oben auf Seite 41 des Buchs hier nicht anwenden; diese Formel
soll gerade überprüft werden.]
Lösungsvorschlag:
P
Erste Variante: Induktion über die Anzahl der Primfaktoren, d.h., über
i<k ri , und Verwendung der ursprünglichen Definition von ϕ : für n = 1 und n prim ist die Behauptung klar, da
sich das Produkt über keinen bzw. genau einen Faktor erstreckt.
Wir nehmen an, die Behauptung sei für n erfüllt. Für eine
Primzahl p ist sie nun für n · p zu testen. Offenbar gilt für a < np
ggT(a, np) = 1 ⇐⇒ ggT(a, n) = 1 ∧ ggT(a, p) = 1
Damit ergibt sich
ϕ(np) = |{ a ∈ Znp : ggT(a, np) = 1 }|
= |Znp |
− |{ a ∈ Znp : ggT(a, n) 6= 1 }|
− |{ a ∈ Znp : ggT(a, p) 6= 1 }|
+ |{ a ∈ Znp : ggT(a, p) 6= 1 ∧ ggT(a, n) 6= 1 }|
= np
− p(n − ϕ(n))
−n
(
+
n,
falls ggT(n, p) = p
n − ϕ(n), falls ggT(n, p) = 1
(
pϕ(n),
falls ggT(n, p) = p
=
(p − 1)ϕ(n), falls ggT(n, p) = 1

Q
1
p · n ·
1
−
i<k
p
i
=
Q
Q
1
(p − 1) · n ·
i<k 1 − pi = p · n ·
i<k 1 −
falls ggT(n, p) = p
1
1
pi · 1 − p
falls ggT(n, p) = 1
Zweite, viel kürzere, Variante: Anwendung des Satzes von Folie 56:
!
Y
Y
Y
Y
Y
1
ri
ri
ri −1
ri
ri −1
ϕ
pi
=
ϕ (pi ) =
(pi − 1)pi
=
pi − pi
=n·
1−
pi
i<k
i<k
i<k
i<k
i<k
Übungsaufgabe 4
Es sei C = DES(M, K) die Verschlüsselung eines binären Klartextes M mit Hilfe des
Schlüssels K bei Verwendung des Data Encryption Standard. Mit c(M ) bzw. c(K) bezeichnen wir das bitweise Komplement von M und K . Weiterhin sei C 0 = DES(c(M ), c(K)) der
zugehörige Chiffretext.
Beweisen Sie, dass C 0 = c(C) gilt. Was folgt daraus für einen Klartextangriff?
Lösungsvorschlag:
Wir nennen eine Abbildung Zn2
tierung kommutiert, d.h.,
p
Zm
2 komlementär , falls sie mit der bitweisen KomplemenZn2
p
c
Zn2
Zm
2
c
p
(1)
Zm
2
Komplementäre Funktionen sind offenbarr unter Komposition abgeschlossen und jede Projekπi
tion Zm
Z2 , i < m , ist komplementär. Außerdem ist Zn2 f Zm
2 genau dann kom2
plementär, wenn alle Kompositionen πi ◦ f mit i < m diese Eigenschaft haben. Folglich ist
0
1
das cartesische Produkt Zn2 0 × Zn2 1 f0 × f1 Zm
× Zm
zweier komplementärer Funktionen
2
2
wieder komplementär. Gleiches gilt für alle Funktionen, die durch Vervielfachen, Löschen oder
Vertauschen von Projektionen gebildet werden können.
Damit folgt sofort, dass mit dem Schlüssel K 0 = c(K) für die Teilschlüssel gilt Ki0 = c(Ki ) ,
1 ≤ i ≤ 16 .
Eine wichtige nicht komplementäre Funktion ist ⊕ (exclusive or ), es gilt sogar
m
Zm
2 × Z2
c×c
m
Zm
2 × Z2
(2)
⊕
⊕
Zm
2
Aber dafür sind folgende Kompositionen komplementär, die genau eines der beiden Argumente
von ⊕ komplementieren:
m
Zm
2 × Z2
c × id
id × c
m
Zm
2 × Z2
⊕
Zm
2
(3)
Um nachzuweisen, dass DES komplementär ist, betrachten wir den Algorithmus auf Seite
52 im Buch (Folie 72) mit der Eingabe (M 0 , K 0 ) = (c(M ), c(K)) . Die initiale Permutation ist
komplementär, liefert also (L00 , R00 ) = (c(L0 ), c(R0 )) . Wir nehmen an, dass im Schritt i < 15
die Ergebnisse (L0i , Ri0 ) = (c(Li ), c(Ri )) geliefert werden. Dann erhalten wir im nächsten Schritt
0
0
(L0i+1 , Ri+1
) = (Ri0 , L0i ⊕ f (Ri0 , Ki+1
)) = (c(Ri ), c(Li ) ⊕ f (c(Ri ), c(Ki+1 )))
(4)
Der erste Schritt bei der Berechnung von f (c(Ri ), c(Ki+1 )) besteht darin, E(c(Ri )) ⊕ c(Ki+1 )
zu bilden. Aber da E nach der Vorüberlegung komplementär ist, erhalten wir wegen (2)
E(c(Ri )) ⊕ c(Ki+1 ) = c(E(Ri )) ⊕ c(Ki+1 ) = Ri ⊕ Ki+1
Somit entfällt erfreulicherweise die Untersuchung der S-Boxen darauf, wie sie komplementierte
Argumente verarbeiten und es gilt f (c(Ri ), c(Ki+1 )) = f (Ri , Ki+1 ) . Da die Funktionen in (3)
komplementär sind, können wir die Berechnung (4) wie folgt fortsetzen
0
(L0i+1 , Ri+1
) = (c(Ri ), c(Li ) ⊕ f (Ri , Ki+1 ))
= (c(Ri ), c(Li ⊕ f (Ri , Ki+1 )))
= c(Ri , Li ⊕ f (Ri , Ki+1 ))
Im 16. Schritt unterbleibt die Vertauschung der beiden Hälften, wir erhalten
0
(R16
, L016 ) = c(R16 , L16 )
Die finale Permutation ist wieder komplementr, damit folgt die Behauptung.
Der Aufwand bei einem Klartextangriff halbiert sich somit.
Übungsaufgabe 5
(a) Bestimmen Sie für den DES die zu P C1 inverse Schlüsselpermutation.
(b) Im DES gibt es vier Schlüssel K , so daä die Chiffrierung EK selbstinvers ist, d.h., es
gilt EK (EK (M )) = M für alle M ∈ Z64
2 . Bestimmen Sie diese Schlüssel.
Lösungsvorschlag:
(a) Aus dem Vergleich der Identitätstransformation und P C1 läßt sich
mation direkt ablesen:

−1
8 17 26 62
56 48 40 32 24 16 8 7
 0 57 49 41 33 25 17 15 
6 16 25 61



 9
5 14 24 60
1
58
50
42
34
26
23


 18 10

4 13 22 59
2
59
51
43
35
31


=
 62 54 46 38 30 22 14 39 
3 12 21 30


 6 61 53 45 37 29 21 47 
2 11 20 29


 13
5 60 52 44 36 28 55 
1 10 19 28
20 12
4 27 19 11 3 63
0 9 18 27
die inverse Transfor58
57
56
54
53
52
51
50
49
48
46
45
44
43
42
41
40
38
37
36
35
34
33
32
7
15
23
31
39
47
55
63
Die ursprüngliche Beschreibung von P C1 eliminiert die Paritätsbits des 64-Bit Schlüssels
(blau), was das Auffinden der inversen Permutation duch das Auszählen der Positionen
unnötig erschwert. Behält man die Paritätsbits bei (die in P C1 natürlich nicht mehr als
solche fungieren), erhält man (P C1 )−1 , indem man in Position k < 64 die Position der
Zahl k in P C1 einträgt.
Wie ist P C1 entstanden? Neben den invarianten Paritätsbits ergeben sich in (P C1 )−1
zwei dreieckige Bereiche, rot und grün markiert, die durch eine gewisse Regelmäßigkeit
gekennzeichet sind. Es stellt sich heraus, dass bestimmte geometrische Transformationen,
die diese farbigen Bereiche berücksichtigen, die initiale Permutation P C1 erzeugen. Wir
beginnen markieren die interessanten Bereiche in der Identitätstransformation:
0
8
16
24
32
40
48
56
1 2 3 4 5 6 7
9 10 11 12 13 14 15
17 18 19 20 21 22 23
25 26 27 28 29 30 31
33 34 35 36 37 38 39
41 42 43 44 45 46 47
49 50 51 52 53 54 55
57 58 59 60 61 62 63
Die letzte Spalte der Paritätsbits (blau) bleibt invariant. Wir fügen das rote bzw. grüne
Dreieck um eine Spalte nach rechts, bzw. links verschoben unterhalb der linken vier bzw.
der rechten drei schwarzen Spalten an. Dann fügt man die Spalten (bis auf die letzte der
Paritätsbits) in geometrisch absteigender Reihenfolge zu einer (7 × 8) -Matrix zusammen
(wobei die letzten vier Spalten von hinten nach vorne umsortiert werden). Nach Drehung
dieser (7 × 8) -Matrix um −π/2 erhält man P C1 .
8
16
24
32
40
48
56
17
25
33
41
49
57
0
26
34
42
50
58
1
9
35
43
51
59
2
3
10 11
18 19
27
4
12
20
28
36
44
52
60
5
13
7
15
23
31
14 39
21 22 47
29 30 55
37 38 63
45 46
53 54
61 62
6
7→
56 48 40 32 24 16 8 7
0 57 49 41 33 25 17 15
9 1 58 50 42 34 26 23
18 10 2 59 51 43 35 31
62 54 46 38 30 22 14 39
6 61 53 45 27 29 21 47
13 5 60 52 44 36 28 55
20 12 4 27 19 11 3 63
Führt man ausgehend von
0
8
16
24
32
40
48
56
1 2 3 4 5 6 7
9 10 11 12 13 14 15
17 18 19 20 21 22 23
25 26 27 28 29 30 31
33 34 35 36 37 38 39
41 42 43 44 45 46 47
49 50 51 52 53 54 55
57 58 59 60 61 62 63
diese Transformationen rückwärts durch, muß sich (P C1 )−1 ergeben. Wir starten mit
einer (8 × 8) -Matrix der Zahlen von 0 bis 63 (zeilenweise aufgelistet), drehen die ersten
7 Spalten um π/2 und invertieren die Reihenfolge der letzten vier Spalten. Vertikale
Verschiebung der Spalten gemää des obigen Schemas liefert dann
6
5
4
3
2
1
0
14
13 22
12 21 30
11 20 29
10 19 28
9 18 27
8 17 26 62
16 25 61
24 60
59
58
57
56
54
53
52
51
50
49
48
46
45
44
43
42
41
40
7
15
23
31
38 39
37 47
36 55
35 63
34
33
32
Fügt man die farbigen Dreiecke wieder oben ein, so erhält man (P C1 )−1 , wie oben
angegeben.
(b) Da die Dechiffrierung nur die Reihenfolge der Teilschlüssel umkehrt, sind Schlüssel K̄ =
hks : s ≤ 64i mit der folgenden Eigenschaft gesucht
Ki = K15−i
für i < 8
Dies ist sicherlich der Fall, wenn für C0 D0 ∈ 256 , was P C1 (K̄) ohne die alten Paritätsbits
entspricht, gilt
Ci = C15−i und Di = D15−i
für i < 8
Die Bedingung C0 = C15 impliziert, dass die ersten Bits dieser Wörter übereinstimmen
müssen; nach Vorgabe der Linksverschiebungen sind dies aber die ersten beiden Bits von
C0 Ebenso müssen das erste und das zweite Bit von C0 übereinstimmen, usw.. Folglich
müssen alle 28 Bits von C0 konstant denselben Wert haben. Entsprechendes gilt auch
für die 28 Bits von D0 .
Wir suchen nun Schlüssel K , so dass für den um Paritätsbits ergänzten Schlüssel K̄ nach
Anwendung von P C1 und Entfernen der Paritätsbits ein Wert in {028 , 128 } · {028 , 128 }
übrigbleibt.
Aber dazu ist einfach die inverse Permutation P C1−1 auf die vier möglichen um (bisher
unbekannte) Paritätsbits ergänzte Wörter anzuwenden, also auf
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
?
?
?
?
?
?
?
?
und
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
?
?
?
?
?
?
?
?
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
sowie auf die bitweisen Komplemente. Das liefert bei ungerader Parität
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
und
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
sowie die entsprechenden Komplemente. Platzsparender ist die Hex-Schreibweise:
K̄0 = 0101010101010101 = (01)8
K̄1 = FEFEFEFEFEFEFEFE = (FE)8
K̄2 = 1F1F1F1F0E0E0E0E = (1F)4 (0E)4
K̄3 = E0E0E0E0F1F1F1F1 = (E0)4 (F1)4
Verwendet man stattdessen die Paritätsbits zur Herstellung gerader Parität, so erhält
man
K̄0 = 0000000000000000 = (00)8
K̄1 = FFFFFFFFFFFFFFFF = (FF)8
K̄2 = 1E1E1E1E0F0F0F0F = (1E)4 (0F)4
K̄3 = E1E1E1E1F0F0F0F0 = (E1)4 (F0)4
Vermutlich will man aus technischen Gründen das Byte 00 vermeiden.

Download Report