Einführung in die Kryptographie

• Homepage: http://www.cdc.informatik.tu-darmstadt.de/lehre/WS05_06/vorlesung/Kryptographie_I.html
• Übungen: http://www.cdc.informatik.tu-darmstadt.de/lehre/WS05_06/vorlesung/Krypto_I/WS05_06_Uebungen.html
• Weitere Mitschriften:
  • http://www.datenzone.de/space/Krypto

• Klausur: 21.02.2006, 10.00 - 12.00 Uhr, Erlaubt nur Taschenrechner
• Benotete Hausübung:
  • Verfügbar ab 05.12.
  • Abgabe bis 13.12., 17:00 Uhr
  • Abgabe entweder bei Übungsleiter oder am 13.12. von 09:30-13:30h und 16:15-17:00h in S202/B206

IT-Sicherheit ↔ Kryptographie:

• Verschlüsseln
• Signieren
• Identifizieren
• Authentifizieren

Wofür braucht man das?

• Online Banking (http/ssl/tls)
• TUD-Card
• Mobiltelefone
• Betriebssystemupdates
• …

• Vertraulichkeit (Confidentiality)
  Nur der Berechtigte hat Zugang zu einer Information/Daten. Die anderen nicht. War lange das Hauptziel kryptographischer Mechanismen: Verschlüsselung.
• Identifikation (Identification)
  
  Homebanking, www.bahn.de
• Integrität (Data Integrity)
  Sind Daten unverändert?
• Message (Data) Authentication
  Ich weiß, wer die Nachricht geschickt hat und dass sie unverändert ist.
• Nichtabstreitbarkeit (Nonrepudiation)
  Für Verträge, Monitoring-Systeme, …
• Secret-Sharing
  Verteilen eines Geheimnisses an viele (n). Wenn sich t kleinergleich n zusammentun, so können sie das Geheimnis rekonstruieren

Fortgeschrittene Ziele: Wahlen, …

Beispiel:

ICH BIN MUEDE. ⇒ 241323 122433 3245151415.

Klartexte (plaintexts) → Chiffretexte (ciphertext)

Klartexte Teilmenge von Klartextraum (Beispiel: {A, … , Z}^*)
Chiffretexte Teilmenge von Chiffretextraum (Beispiel: {{1, 2, 3, 4, 5}^2}}^*

Schlüssel entspricht Tabelle

Schlüssel Teilmenge von Schlüsselraum (= alle möglichen Tabellen) → Keyspace K

Verschlüsselungsfunktionen

E_k: P → C, k element K

Entschlüsselungsfunktionen

D_k: C → P, k element K

Zu jeder Verschlüsselungsfunktion gibt es eine passende Entschlüsselungsfunktion.

133 = 6 * 21 + 7
a = q * b + r

a,q element Z, b element Z>0, 0 kleinergleich r kleiner b, q,r eindeutig

-50 = (-7) * 8 + 6
r = (a mod b)
6 = (-50 mod 8)

Z_8 = {0, 1, 2, 3, 4, 5, 6, 7}
Z_b = {0, … , b-1}

P = {0, … , 25} = Z_26
C = {0, … , 25} = Z_26
K = {0, … , 25} = Z_26

E: Z_26 → Z_26, x → (x + e) mod 26

Permutationen:

Z_6 → Z_6, Tabelle = Zuordnungsvorschrift

phi: x → x (Bijektion)
Für alle y element X existiert ein x element X so dass gilt phi(x) = y

X = {1}: 1 → 1 einzige Permutation

X = {1, 2}: 1 → 1, 2 → 2, 1 → 2, 2 → 1

Endliche Menge X: Wieviele Permutationen? Antwort: |X|!

(Z_2)^n = P = C

z.B. (Z_2)^24 (0, 1, 1, 0, 1, … , 1, 0)

S(X) Menge aller Permutationen von X.
S_n Menge aller Permutationen von Z_n.

K = S_n teilemenge von Pi
E_Pi(b_o, … , b_{n-1}) = (b_{Pi(b_0)}, … , b_{Pi(b_{n-1})})

n=3, Pi = (0 1 2) ⇒ (1 2 0)
E_Pi(1 1 0) = 1 0 1

Angreifer kennt ein paar (Klartext ↔ Schlüsseltext) Paare ⇒ Schlüssel

• Flugzeug der Aliierten wirft Bombe daneben → Known Plaintext!
• “Wasserbombe bei xx.yy” → Enigma → Chiffretext → Funksendung → Abfangen durch Flugzeug
• Provozierter Klartext

Der Angreifer kann Nachrichten seiner Wahl entschlüsseln.

1. Secret Key Verschlüsselung
2. Public Key Verschlüsselung

Bei Secret Key:

Unpraktisch im Internet ⇒ 10^9 Benutzer, jeder will mit jedem eine Nachricht austauschen: (10^9 * (10^9 - 1)) / 2 = etwa 0.5 * 10^8 Schlüssel

Bei Public Key:

Öffentlicher Schlüssel muss aber vor Veränderung geschützt werden!

Beispiel für Chosen Plaintext:

Frage: “Haben Sie InfC bestanden?” - Antwort entweder “Ja” oder “Nein”.
Angreifer verschlüsselt nun mit bekanntem PublicKey des Empfängers “Ja” und “Nein” und vergleich jeweils - somit ist der Inhalt der Nachricht dennoch bekannt. Lösung: Randomisierung, Sender versendet nicht “Ja” oder “Nein”, sonder z.B. “Ja1788763”. Empfänger weiß, dass die letzten 7 Byte random sind und verwirft sie.

Angreifer kann sich Chiffretexte seiner Wahl entschlüsseln lassen.

Ich schicke verschlüsselte Nachricht an Bob. Bob entschlüsselt. Wenn das stimmt, dann war es auch Bob.

Typen von Angriffen:

Schlüsselstrom

Synchrone Stromchiffre, denn Sender und Empfänger erzeugen den Schlüsselstrom synchron.

Beispiel:

n element N, k element Z_2 ^ n, k = (k_1, …, k_n)
Strom: s_1, s_2, s_3, …
s_i = k_i, 1 kleinergleich k kleinergleich n
s_i = Summe für j=1 bis n von c_j * s_{i-j} mod 2, i größer n
Dabei sind c_1, …, c_n feste Koeffizienten.
Lineare Rekursion vom Grad n
n = 4 : s_{i+4} = s_i + s_{i+1} mod 2 ⇒ c_1 = 0, c_2 = 0, c_3 = 1, c_4 = 1
k = (1,0,0,0)

Im Allgemeinen wird eine Keystrom-Generatorfunktion benutzt:
k_1k_2k_3…k_n → Schlüsselstrom in Z_2^*

Lineare Rekursion leicht in Hardware realisierbar → Schieberegister

(k_0, … , k_{n-1}) element K teilmenge von Z_2^n
s_i = k_i, 0 kleinergleich i kleinergleich n-1
s_{i+n} = Summe von j = 0 bis n-1 über c_j * s_{i+j} mod 2, i größergleich 0
s_{i+4} = s_i + s_{i+1} mod 2, i größergleich 0
c_0 = 1, c_1 = 1, c_2 = c_3 = 0

k = (1, 0, 0, 0)
Dann ist s =

s ist also periodisch, mit der Persiode 2^n. Periodik bei einem Schlüssel → Problematisch.

Ziel der Stromchiffre: Verschlüsselung beliebig langer Dokumente.
Idee:

Simultan von Sender und Empfänger generierbar.

Im Allgemeinen:

• g : K → Z_2^*
• e_s : Z_2 → Z_2 (im Beispiel: e_s : p_i xor s_i)
• p = p_0p_1p_2…p_{m-1}
• E_k(p) = E_s_0(p_0)E_s_1(p_1)…
• D_k© = d_s_0(c_0)d_s_1(c_1)…

E_k : Z_2^n → Z_2^n, n ist die Blocklänge

Feststellung: Verschlüsselungsfunktionen von Blockchiffren sind immer Permutationen.

Entschlüsselbar:

• ⇒ injektiv
• ⇒ bijektiv (da Urbildmenge = Bildmenge, beides endlich)

Bijektive Funktionen sind immer Permutationen.

Allgemeinste Blockchiffre:

• Blocklänge n
• K = S(Z_2^n)
• |S(Z_2^n)| = (2^n)!

Man kann nur Permutationen gebrauchen die

1. Effizient notiert
2. Effizient ausgewertet

werden können!

Verwende Blockchiffren zur Verschlüsselung beliebig langer Texte.

P = C = Z_2^n, K Schlüsselraum
Gegeben p = p_1p_2p_3…

Ergänze so, dass Länge durch n teilbar.

n = 4, k = s_4
E_pi : b_1b_2b_3b_4 → b_{pi(1)}b_{pi(2)}b_{pi(3)}b_{pi(4)}
pi = { (1 2 3 4) ⇒ (2 3 4 1) }
m = 1011000101001010 (Ergänzung)

Teile auf in Blöcke der Länge n

m = 1011 0001 0100 1010

Verschlüssele jeden Block

c = 0111 0010 10000 0101

Zum Entschlüsseln verfährt man analog.

Nachteil:

• Gleich Blöcke im Klartext werden zu gleichen Blöcken im Chiffretext
• ⇒ statistische Eigenschaften des Klartextes bleiben erhalten
• ⇒ Blöcke lassen sich ersetzen

Darum: Besser nicht verwenden!

IV element Z_2^n, Initialisierungsvektor, öffentlich
c_0 = IV
c_j = E_e(c_{j-1} xor m_j)
c = c_0c_1c_2…c_t

Entschlüsseler bekommt d (Entschlüsselungsschlüssel zu e), IV, c und berechnet dann:
c_0 = IV
m_j = c_{j-1} xor D_d(c_j) = c_{j-1} xor c_{j-1} xor m_j = 0 xor m_j = m_j stimmt.

Beispiel:

• IV = 1010, m = 1011000101001010, E_pi, pi wie zuvor
• c_0 = 1010
• c_1 = E_pi(1010 xor 1011) = E_pi(0001) = 0010
• c_2 = E_pi(0010 xor 0001) = E_pi(0011) = 0110
• c_3 = E_pi(0110 xor 0100) = E_pi(0010) = 0100
• c_4 = E_pi(0100 xor 1010) = E_pi(1110) = 1101
• ⇒ c = 0010011001001101

Entschlüsseler muss warten, bis c_1 vollständig übertragen ist.

m_1 = c_0 xor D_d(c_1) = c_0 xor 0001 = 1011 stimmt.

Eigenschaft CBC: Kontextabhängig → Gleiche Blöcke in unterschiedlichen Kontext ergeben verschiedene Chiffretextblöcke! Insbesondere verschiedene IV führen zu verschiedenen Chiffretexten.

Was ist der Effekt von Übertragungsfehlern? → c_i wird falsch übertragen, welche m_j sind dann noch garantiert richtig? ⇒ m_{i+2}, m_{i+3}, m_{i+4}, … und m_{i-1}, m_{i-2}, m_{i-3}, …

(erster Teil der Vorlesung siehe http://www.datenzone.de/space/Krypto/Krypto+4.+Vorlesung, Inhalt war CFB und OFB, siehe auch Block cipher modes of operation)

Kleine lateinische Buchstaben sind ganze Zahlen

a kongruent b mod m

m | b - a (m ist ein Teiler/teilt b - a)

-2 kongruent 19 mod 21
weil 19 - (-2) = 19 + 2 = 21 und 21 | 21
-2 kongruent 19 mod 7
weil 19 - (-2) = 19 + 2 = 21 und 7 | 21
-2 kongruent 19 mod 3
weil 3 | 21

a kongruent b mod m ⇔ a = b + k*m ⇔ a und b lassen bei Division durch m den selben Rest.

a kongruent b mod m, c kongruent d mod m ⇒ a + c = b + d mod m

Begründung:

m | a - b, m | c - d
(a+c) - (b+d) = (a-b) + (c-d)
m | a-b, m | c-d ⇒ m | (a-b) + (c-d) !

a * c kongruent b * d mod m
Wir müssen nachrechnen, dass a * c - b * d von m geteilt wird. Das ist get nicht so einfach. Da nehmen wir doch lieber mal eine neue Idee.

a = b + k*m
c = d + l*m
a * c = (b + km)(d + lm) = bd + blm + kdm + klm^2 = bd + (bl + kd + klm) * m

Fermat, 17Jhd., Jurist + Mathematiker

F_n = 2^(2^n) + 1 → Fermatzahlen
F_0 = 3, F_1 = 5, F_2 = 17, F_3 = 257, F_4 = 65537, F_5 = 2^2^5 + 1

641 | 2^2^5 + 1
641 = 640 + 1 = 5 * 2^7 + 1 ⇒ 5 * 2^7 = -1 mod 641
hoch 4! (Erlaubt, weil Kongruenzen multipliziert werden dürften):
5^4 * 2^28 kongruent 1 mod 641
641 = 625 + 16 = 5^4 + 2^4
5^4 = -2^4 mod 641
-2^32 kongruent 1 mod 641
2^32 + 1 kongruent 0 mod 641
⇒ 641 | 2^32 + 1

641 | 2^2^5 + 1
a kongruent b mod m, c kongruent d mod m ⇒ a + c kongruent b+d mod m → Auch für -, *

Dividieren? Invertieren?

17 * x kongruent 1 mod 23

ggT(a, b)
ggT(24, 32) = 8
ggT(-144, -64) :
12 | -144 → -144 = 12 * (-12)
m | a ⇔ Es existiert ein k . a = k * m

Ideen des euklidischen Algorithmus

b ungleich 0
ggT(a, b) = ggT(b, a mod |b|) (→ 0 kleinergleich a kleiner |b|) (1)
ggt(a, 0) = a (2)
Wende (1) solange an, bis b = 0 ist. Wende dann (2) an.

Beispiel: ggT(140, 37) = ggT(37, 140 mod 37) = ggT(37, 29) = ggT(29, 37 mod 29) = ggT(29, 8) = ggT(8, 29 mod 8) = ggT(8, 5) = ggT(5, 8 mod 5) = ggT(5, 3) = ggT(3, 5 mod 3) = ggT(3, 2) = ggT(2, 3 mod 2) = ggT(2, 1) = ggT(1, 2 mod 1) = ggT(1, 0) = 1

Wie lange können diese Schritte dauern, wieviele Iterationen gibt es?

Anzahl der Iterationen bei der Berechnung von ggT(a, b) mit a größer b größer 0.

Letzter Schritt: r_{n-1} = q_n * r_n + 0 (0 ist der letzte Divisionsrest)

Wir beweisen

• r_k größer gleich theta^(n-k)
• theta = ( 1 + sqrt(5) )/2

dann ist

• b = r_1 größergleich theta^(n-1) = e^( (log theta)(n-1) )
• log b größer gleich (n-1) log theta
• (log b) / (log theta) größer gleich n-1
• n kleinergleich (log b) / (log theta) - 1 kleiner 1.441 log_a(b)

Sehr effizient: Anzahl Iterationen kleiner 1.5 (Anzahl Bits in b)

Beweis von r_k größergleich theta^(n-k)
oBdA ggT(a, b) = 1.
r_n = 1 größergleich theta^0 = 1
r_{n-1} = q_n*r_n = q_n größergleich 2 (weil r_n kleiner r_{n-1})

Sei n-2 größergleich k größergleich 0 und gelte Behauptung für k' größer k
r_k = q_{k+1}r_{k+1} + r_{k+2}
größergleich r_{k+1} + r_{k+2}
größergleich theta^(n-k-1) + theta^(n-k-2)
= theta^(n-k-1)(1+1/theta)

1+1/theta = 1 + 1/( ( 1+sqrt(5) )/2 ) = 1 + 2/(1 + sqrt(5)) = (1 + sqrt(5) + 2)/(1 + sqrt(5)) = (3 + sqrt(5))/(1 + sqrt(5)) = ( (3 + sqrt(5)) * (1 - sqrt(5)) ) / (-4) = (3 - 5 - 2sqrt(5)) / -4 = (-2 - 2sqrt(5)) / -4 = (1 + sqrt(5)) / 2 ) theta
⇒ theta = 1 + 1/theta

Berechnet x, y: a*x + b*y = ggT(a, b)

Dazu:
x_i, y_i
r_i = (-1)^(i)x_ia + (-1)^(i+1)y_ib
x = (-1)^nx_n, y = (-1)^(n+1)y_n

Wie löst man damit ax kongruent 1 mod m?

a = r_0 = 1 * a + 0 * b
b = r_1 = 0 * a + 1 * b
⇒ x_0 = 1, x_1 = 0, y_0 = 0, y_1 = 1

Anmerkung: Alle x_i, y_i bestimmt für i kleiner k, k größergleich 2.

Was ist x_k, y_k?

r_{k-2} = q_{k-1}r_{k-1} + r_k
r_k = r_{k-2} mod r_{k-1}
= (-1)^(k-2) * x_{k-2} * a + (-1)^(k-1) * y_{k-1} * b - q_k( (-1)^(k-1) * x_{k-1} * a + (-1)^k * y_{k-1} * b)
= a * ( (-1)^(k-2) * x_{k-2} + (-1)^k * q_k * x_{k-1}) + b * ( (-1)^(k-1) * y_{k-2} + (-1)^(k+1) * q_{k-1} * y_{k-1} )
= (-1)^k * a * (x_{k-2} + q_{k-1} * x_{k-1}) + (-1)^(k+1) * b * (y_{k-2} + q_{k-1} * y_{k-1})

(x_{k-2} + q_{k-1} * x_{k-1}) = x_k, (y_{k-2} + q_{k-1} * y_{k-1}) = y_k

r_7 = (-1)^7 * x_7 * a + (-1)^8 * y_7 * b
140 * x + 37 * y = 1, x = -14, y = 53
140 * (-14) kongruent 1 mod 37
-14 ist also das Inverse von 140 in Z/37Z

Es sei R ein kommutativer Ring mit Eins.

Definition: eine k x n Matrix über R ist eine doppelt indizierte Familie von Elementen aus R

h = (a_ij), i = 1, … , k, j = 1, … , n

geschrieben als rechteckiges Schema

Wir bezeichnen mit R^(k,n) bzw R^{k x n} die Menge aller k x n Matrizen über R

• a_ij Koeffizienten von A
• (a_1j a_2j … a_kj)^T ist die j-te Spalte von A
• (a_i1 a_i2 … a_in) ist die i-te Spalte von A

Zeilenvektoren sind 1 x n Matrizen, Spaltenvektoren sind k x 1 Matrizen.

Seien k, n element N und A, B element R^{k x n}

A = (a_ij), B = (b_ij), i = 1, … , k, j = 1, … , n

Die Summe von A und B ist

A + B = (a_ij + b_ij), i = 1, … , k, j = 1, … , n

Das Produkt von A und C element R^{n x m} ist

A * C = (d_ij), 1 ⇐ i ⇐ k, 1 ⇐ k ⇐ n
d_ij = Summe von v = 1 bis n über a_ivc_vj
A * C element R^{k x m}

Sei R ein kommutativer Ring mit Einselement 1 und n element N, dann ist (R^{n x n}, +, *) ein Ring.
Einselement in R^{n x n} ist die identität oder Einheitsmatrix

(e_ij) = 1 falls i = j, 0 sonst

Die n x n Nullmatrix (über R) ist die n x n Matrix, deren sämtliche Einträge Null sind. “Null” ist hier das neutrale Element in R bezüglich der Addition. Die Nullmatrix ist das neutrale Element bezüglich ”+” in R.

Sei A element R^{n x n}, dann ist A_ij die Matrix, die man erhält, wenn man in A die i-te Zeile und die j-te Spalte streicht.

Für alle i element {1, … , n} ist die Determinante von A

det A = Summe für j = 1 bis n von ( (-1)^i+j a_ij det A_ij )

Bsp: A = ( (a₁₁ a₁₂) (a₂₁ a₂₂) ). A₁₁ = a₂₂, A₂₁ = a₁₂, A₁₂ = a₂₁, A₂₂ = a₁₁.
det A = (-1)²a₁₁a₂₂ + (-1)³a₁₂a₂₁ = a₁₁a₂₂ - a₁₂a₂₁

A, B element R^{n x n}

• det(AB) = det A * det B
• det( (e_ij) ) = 1
• c element R, c * A = (c * a_ij ), det(cA) = cⁿdet A

Die transponierte Matrix von A = (a_ij) ist die Matrix A^T = (a_ji). Es gilt det(A^T) = det(A)

a element Z_n, dann ist ax kongruent 1 mod n lösbar falls gcd(a, n) = 1.

Eine Matrix A element R^{n x n} hat genau ein multiplikatives Inverses. Wir definieren dazu die Adjunkte von A:

adj(A) = ( (-1)^i+j det(A_ji) )

Es gilt

A^-1 = (det A)^-1 * adj(A)

Beispiel: A = ( (a₁₁ a₁₂) (a₂₁ a₂₂) )
adj(A) = ( (+a₂₂ -a₁₂) (-a₂₁ +a₁₁) )

Sei R = Z_m für m element N und A = Z_n^{n x n} mit n element N, dann ist A genau dann invertierbar, wenn gcd(det A, m) = 1

Beispiel: Z₄^{2 x 2}

• A = ( (1 1) (3 1) ), det(A) = 1*1 - 1*3 = -2
  gcd(detA, 4) = gcd(-2, 4) = 2 != 1
  ⇒ A ist nicht invertierbar
• A = ( (1 3) (0 3) ), det(A) = 1*3 - 0*3 = 3
  gcd(detA, 4) = 1
  ⇒ A ist invertierbar

Klartextraum, Schlüsseltextraum ⇒ Z_mⁿ, n, m element N, n = Blocklänge

E : Z_mⁿ → Z_mⁿ
p = (p₁, p₂, … , p_n) → Ap + b mod m
A element Z_m^nxn, b element Z_mⁿ

Bsp: m = 10, n = 2, A = ( (1 7) (2 1) ), b = (2 5)^T, p = (3 7)^T
c kongruent A*p + b mod m
kongruent ( (1 7) (2 1) ) * (3 7)^T + (2 5)^T mod m
kongruent (52 13)^T + (2 5)^T kongruent (4 8)^T mod m

Schlüssel? (A, b) element Z_m^nxn x Z_mⁿ, A invertierbar mod m

D : Z_mⁿ → Z_mⁿ
c → A^-1(c - b) mod m
D( c ) kongruent A^-1(Ap + b - b) mod m kongruent A^-1Ap kongruent p mod m

Bsp: detA kongruent -13 mod m kongruent -3 mod m
A^-1 kongruent (-3)^-1( (1 -7) (-2 1) ) kongruent 3 ( (1 -7) (-2 1) ) kongruent ( (3 9) (4 3) ) mod 10
c = (4 8)^T
D( c ) kongruent ( (3 9) (4 3) ) ( (4 8)^T - (2 5)^T )
kongruent ( (3 -1) (4 3) ) (2 3)^T
kongruent (3 -3)^T
kongruent (3 7)^T mod m

1929 Hill-Chiffre: b=0, m=26, n=6, Matrix A fest eingebaut

Bsp: m = 10, n = 2
c₀ = (1 1)^T, m₀ = (3 1)^T
c₁ = (2 3)^T, m₁ = (2 5)^T
c₂ = (8 2)^T, m₂ = (4 8)^T
c₃ = (7 7)^T, m₃ = (? ?)^T
c₁ - c₀ kongruent (Am₁ + b) - (Am₀ + b) kongruent Am₁ - Am₀ kongruent A(m₁ - m₀) mod m
c₂ - c₀ kongruent A(m₂ - m₀) …

( (1 7) (2 1) ) kongruent A * ( (-1 1) (4 7) ) mod m
( (1 7) (2 1) )( (-1 1) (4 7) )^-1 kongruent A mod m
( (-1 1) (4 7) )^-1 kongruent -1 ( (7 -1) (-4 -1) ) kongruent ( (-7 1) (4 1) ) kongruent ( (3 1) (4 1) ) mod m
( (1 7) (2 1) )( (3 1) (4 1) ) kongruent ( (31 8) (10 3) ) mod 10

Am₀ kongruent ( (1 8) (0 3) )(3 1)^T kongruent (11 3)^T kongruent (1 3)^T mod 10

(1 1)^T = c₀ kongruent Am₀ + b kongruent (1 3)^T + b mod 10
⇔ b kongruent (0 -2)^T mod 10

c₃ = (7 7)^T m₃ kongruent A^-1(c₃ - b)
kongruent A^-1( (7 7)^T - (0 -2)^T )
kongruent A^-1(7 9)^T
kongruent -3 ( (3 -8) (0 1) )(7 9)^T
kongruent -3 (21+18 9)^T
kongruent (3 3)^T mod 10

• Blocklänge n
• Klar- und Schlüsseltextraum Z_mⁿ
• Gegeben Paare von Klar- und Schlüsseltexten (m_i, c_i), c_i = Am_i + b, i = 0, …
• Berechne ~c_i = c_i - c₀, ~m_i = m_i - m₀
  ~c_i kongruent A~m_i mod m
• Bilde
  • ~C element Z_m^nxn, wobei die i-te Spalte ~c_i ist
  • ~M element Z_m^nxn, wobei die i-te Spalte ~m_i ist
  • ~C kongruent A~M mod m
• Falls ~M invertierbar ist, berechne ~C~M^-1 kongruent A mod m, b kongruent c_i - Am_i mod m für ein i = 0, … , n

Bsp: m = 2, n = 4, A = ( (0 0 1 0) (0 1 0 0) (0 0 0 1) (1 0 0 0) ), b = (0 0 0 0)^T, p₁ = (1 0 1 0)^T, p₂ = (1 0 0 1)^T
Ap₁ kongruent (1 0 0 1)^T mod 2, Ap₂ kongruent (0 0 1 1)^T mod 2 ⇒ Bitpermutation!

f : Z_mⁿ → Z_mⁿ

• linear, falls eine Matrix existiert A element Z_m^kxn so dass f(x) = Ax mod m ⇔ a, b element Z_m, x, y element Z_mⁿ, f(ax + by) kongruent af(x) + bf(y) mod m
• affin linear, falls eine Matrix existiert A element Z_m^kxn so dass f(x) = Ax + b mod m ⇔ ~f : Z_mⁿ → Z_m^k, x → f(x) - f(0) mod m, ~f linear

Hill: 3-fach Verschlüsselung:

1. nicht-linearer Schritt
2. linearer Schritt
3. nicht-linearer Schritt (geheim)

nicht linear:
p₁ → pi(p₁)
p₂ → pi(p₂)
…
p_n → pi(p_n)

⇒ Feistelchiffre : Kombination linearer und nicht-linearer Schritte

Feistel: IBM (1915 - 1990), + Don Coppersmith ⇒ Lucipher Cipher. Siehe auch DES, RC5, Blowfish… AES

(Keine Mitschrift von meiner Seite, siehe http://www.datenzone.de/space/Krypto/Krypto+8.+Vorlesung)

Situation:

Wir kennen Klartext x und zugehörigen Chriffretext c. Wir wollen ein Schlüssel K mit E_K(x) = c

Vollständige Suche:

• Zeit: ~ |K| (K = Schlüsselraum)
• Platz: konstant

M = ceil( |K|^1/3 )

g_k : Sigmaⁿ → K , 1 kleinergleich k kleinergleich m, K = Schlüssel, Sigmaⁿ = Klar-/Chiffretexte

k_i, 1 kleinergleich i kleinergleich m

K_k (i, j) = { K_i für j=0 ; g_k( E_{K_k (i, j-1)}(x) ) sonst } ¹⁾

K_k(1,0) → K_k(1,1) → … → K_k(1,m)
K_k(2,0) → …
…
K_k(m,0)

~ m² Schlüssel, m Tabellen, insgesamt m³ Schlüssel

Bei richtiger Wahl von g_k, K_i sind das alle Schlüssel.

Das war die Vorberechnung. Jetzt sieht man Chiffretext C und möchte wissen E(x) = C.

Berechne K(1,k) = g_k( c ), 1 kleinergleich k kleinergleich m. Suche den in einer Tabelle. Wenn man den findet, dann

g_k( E_{K_k (i,j-1)}(x) ) = g_k( C ) = K_k(i,j)

Prüfe, ob E_{K_k (i,j-1)}(x) = C

Analyse: Alle Tabellen werden gebraucht (Platz |K|)
Zeit: O(|K|^1/3)

Modifikation

K(1,k) = g_k( C )
K(j,k) = g_k( E_K(j-1,k)(x) ), 1 kleinergleich k kleinergleich m, 1 kleiner j kleinergleich m

Wenn K(j,k) = K_k(i,m) , dann ist K_k(i,m-j) der Kandidate. Konstruiere die i-te Zeile der k-ten Tabelle. Teste, ob K_k(i,m-j) der nötige Schlüssel ist.

Wieviel Platz: ~ |K|^1/3 * |K|^1/3 = |K|^2/3
Wieviel Zeit: |K|^1/3 * |K|^1/3 = |K|^2/3

AES : Advanced Encryption Standard

Z/pZ = ( {0, … , p-1}, +, * )

Das ist ein endlicher Körper:

a quer = {a + pk : k element K}

Restklasse von a mod p

p=3, a=1,
a quer = {1, 1+-3, 1+-6, 1+-9, …} = {…, -5, -2, 1, 4, 7, …}, 1,7 Vertreter

Z/3Z = {0, 1, 2}

bei * ⇒ rechts unten jeweils in jeder Zeile/Spalte eine 1 ⇒ jedes Element hat ein Inverses ⇒ Körper!

Jeder Z/pZ ist ein endlicher Körper, der p Elemente hat. Zu jedem p element P, n element N kann man einen endlichen Körper mit pⁿ Elemente konstruieren.

Restklassen von Polynomen mit Koeffizienten in F_p modulo eines irreduziblen Polynoms

Z/pZ = F_p
F₂ = {0, 1}

Konstruktion von F₄

Irreduzibles Polynom mit Koeffizienten in F₂ von Grad 2.

X² = X * X ⇒ reduzibel
X² + 1 = (X+1)(X+1) ⇒ reduzibel
X² + X + 1 ⇒ irreduzibel ⇒ p(x) = X² + X + 1

F₄ besteht aus allen Restklassen von Polynomen in F₂[x] modulo p(x).

Konstruktion von F_pⁿ

• Finde irreduzibles Polynom von Grad n in F_p[x], nenne es g(x)
• Dann ist F_p[x] / g(x)F_p[x] ein endlicher Körper mit pⁿ Elementen.

Frage: Geburtstage über das Jahr gleichverteilt. Es sind k Leute im Raum. Mit welcher Wahrscheinlichkeit haben zwei von diesen am gleichen Tag Geburtstag?

(1 - 1/365) ist die Wahrscheinlichkeit, dass eine zweite Person am gleichen Tag Geburstag hat wie ich / Bundeskanzlerin.

• k = 2, Pr = (1 - 1/365) = 1/365 (365 - 1)
• k = 3, Pr = 1/365 * (365 - 1) * 1/365 * (365 - 2) = 1/(365²) * (365 - 1) * (365 - 2) = (1 - 1/365)(1 - 2/365)
• k = 4, Pr = (1 - 1/365)(1 - 2/365)(1 - 3/365)
• …
• k, Pr = Produkt für i = 1 bis k-1 von (1 - i/365)

Beispiel: Es gibt nur n = 2¹⁶ = 65636 verschieden Schlüssel für alle Autos in Deutschland. Wie hoch ist die Wahrscheinlichkeit, dass einer der Schlüssel von k Autos zu zweien passt?

Gegenwahrscheinlichkeit q = 1/nⁿ * Produkt für i=1 bis k-1 von (n - i) = Produkt für i=1 bis k-1 von ( (n-i)/n ) = Produkt für i=1 bis k-1 von (1 - i/n)

1 + x kleinergleich e^x für alle x element R

q kleinergleich Produkt für i=1 bis k-1 von (e^-i/n) = e^{- Summe für i=1 bis k-1 von (i/n)} = e^{-1/n * ( (k-1)k ) / 2}

Wahrscheinlichkeit p größergleich 1 - q größergleich 1 - e^{-1/n * ( (k-1)k ) / 2}

Bsp: Autos. k auf einem Parkplatz. k = 100 → p größergleich 0.072
Bsp: Geburtstag. K = 25 → p größergleich 0.56

Idee: Ein Verschlüsselungssystem soll so sicher sein, dass keiner der Angriffe funktioniert.

Frage: Welche Anforderungen?

Klartextraum P, Schlüsseltextraum C, Schlüsselraum K, Familie von Verschlüsselungsfunktionen E_k : P → C, Entschlüsselungsfunktionen D_k : C → P

Ansatz: Der Schlüsseltext soll keine Informationen über den Klartext verraten, solange der Schlüssel unbekannt ist.

Ausgefallen.

Beispiel Vernan One-Time-Pad

P = C = K = {o, 1}ⁿ

Praktisch? früher: nein. Heute: ja? Durch billigen Speicher.

Modell gut?

Überweisungsformular

|-------------------------|00000011111111|-----------------------------------|
                               Betrag

|----------------------------------------------------------------------------|
                             Schlüssel

                                XOR

|-------------------------|-Chiffretext--|-----------------------------------|
                     Ändere diese Bits zufällig

OTP nur sicher gegen passive Angriffe.

Kombination mit einer Authentifizierung nötig.

Perfekte Geheimhaltung bezieht sich nicht darauf.

Wie kommt man an die Zufallszahlen? Gibt es Zufall?

In der Praxis: Pseudozufall. Muss unvorhersagbar sein.

Bsp:

x kongruent 2 mod 3
x kongruent 3 mod 5
x kongruent 3 mod 7

Bedingung: Moduli müssen teilerfremd sein.

CRT: x kongruent a_i mod m_i, i=1,..,n
m = Produkt für i=1 bis n von m_i
M_i = m / m_i
xgcd : y_iM_i kongurent 1 mod m_i
x = Summe für i=1 bis n von (a_iy_iM_i

Bsp: M₁=35, M₂=21, M₃=15
2 * 35 kongruent 1 mod 3
1 * 21 kongruent 1 mod 5
1 * 15 kongruent 1 mod 7
Lösung: 2*2*35 + 3*1*21 + 3*1*15

Geheimer Schlüssel sicher falls Faktorisieren schwer.

Gegeben öffentlicher RSA-Schlüssel (n,e).
d bekannt, so dass ed kongruent 1 mod phi(n)
Geheim p,q → phi(n) = (p-1)(q-1) = 2^t'k' für ein t' element N und ein k' element N so dass k' ungerade
s := max{ t element N : 2^t teilt ed-1 }
k=(ed - 1) / 2^s

Abbildung: psi : Z_n → Z_p x Z_q, x → (x mod p, x mod q). Invertierbar wegen CRT

Theorem: Sei a element Z_n und die Ordnung von a^k in Z_p und Z_q sei verschieden. Dann gcd(a^{2^t*k} - 1, n) < n und > 1 für ein t element {1, …, s-1}.

Beweis: gcd( ed-1, phi(n) ) = 2^t'k' ⇒ t' kleinergleich s
(a^k)^{2^t'} kongruent 1 mod n
2^t'k' | 2^t'k
⇒ Ordnung a^k in Z_p und Z_q ist in { 2ⁱ | 1 kleinergleich i kleinergleich s }
2^t = Ordnung von a_k in Z_p und in Z_q
(a^k)^{2^{t-1}} nicht kongruent 1 mod p
(a^k)^{2^t} kongruent 1 mod q
⇒ gcd( (a^k)^{2^t} - 1; n) = q

Fortsetzung folgt..

DHP, einzige bekannte Lösung via DLP. p ungefähr 2¹⁰²⁴. Dann heute sicher zufällig

Bob                                  Alice
 b                                      A

B=g^b  <====== Austausch ========>    A=g^a

K=A^b                                 B°a=K
                  ^
                  |
          Person in the Middle 
B -> a'                             b' <- A
  => A' = g^a'               B' = g^b' <=

K_{Bob}=(A')^b             K_{Alice}=(B')^a
       =g^{a'b}                     =g^{b'a}

Schlüsselerzeugung: p, g element {2, … , p-1}, <g strich> hat hohe Ordnung.

a element_R {0, …, p-2}

A = g^a mod p

öffentlich: p, g, A
geheim: a = log_{g strich}(A strich)

Verschlüsselung: m element {0, …, p-1}
b element_R {0, …, p-2}, B = g^b mod p
K = A^b mod p
c = m * K mod p (Variante: m xor K - besser für andere Gruppen)
Schlüsseltext: (c, B), B ist die Diffie-Hellman Hälfte

Entschlüsselung: m = c*B^{-1} mod p ( B^{-a} = B^{p-1-a} )

(Durch Weihnachtsgeschichte des Dozenten zu beschäftigt mit Lachen zum Konzentrieren…)