====== Einführung in die Kryptographie ====== ===== Allgemeines ===== * 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 ===== 27.10.2005 ===== ==== Einleitung ==== IT-Sicherheit <-> Kryptographie: * Verschlüsseln * Signieren * Identifizieren * Authentifizieren Wofür braucht man das? * Online Banking (http/ssl/tls) * TUD-Card * Mobiltelefone * Betriebssystemupdates * ... ==== Ziele ==== * Vertraulichkeit (Confidentiality)\\ Nur der Berechtigte hat Zugang zu einer Information/Daten. Die anderen nicht. War lange das Hauptziel kryptographischer Mechanismen: Verschlüsselung. * Identifikation (Identification)\\ {{uni:mitschriften:krypto:krypto20051027-01.png}}\\ 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, ... ==== Verschlüsseln ==== Beispiel: | ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 | ^ 1 | A | B | C | D | E | ^ 2 | F | G | H | I/J | K | ^ 3 | L | M | N | O | P | ^ 4 | Q | R | S | T | U | ^ 5 | V | W | X | Y | Z | 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. ==== Division mit Rest ==== 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} ==== Caesar-Chiffre ==== ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ L ^ M ^ N ^ O ^ P ^ Q ^ R ^ S ^ T ^ U ^ V ^ W ^ X ^ Y ^ Z | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 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 ==== Permutationschiffre ==== Permutationen: | 0 | 1 | 2 | 3 | 4 | 5 | | 1 | 2 | 4 | 3 | 5 | 0 | 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 ===== 31.10.2005 (ab ~17:10) ===== ==== Known plaintext Attacke ==== Angreifer kennt ein paar (Klartext <-> Schlüsseltext) Paare => Schlüssel {{uni:mitschriften:krypto:krypto-20051031-01.png}} * Flugzeug der Aliierten wirft Bombe daneben -> Known Plaintext! * "Wasserbombe bei xx.yy" -> Enigma -> Chiffretext -> Funksendung -> Abfangen durch Flugzeug * Provozierter Klartext ==== Chosen plaintext Attacke ==== Der Angreifer kann Nachrichten seiner Wahl entschlüsseln. - Secret Key Verschlüsselung - Public Key Verschlüsselung Bei Secret Key: {{uni:mitschriften:krypto:krypto-20051031-02.png}} 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: ^ A ^ B | | Verschlüsselungsschlüssel | Entschlüsselungsschlüssel | | kann veröffentlicht werden \\ kein Schlüsselaustausch nötig | - | Ö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. ==== Chosen Ciphertext Attacke ==== Angreifer kann sich Chiffretexte seiner Wahl entschlüsseln lassen. ==== Identifikationsverfahren ==== Ich schicke verschlüsselte Nachricht an Bob. Bob entschlüsselt. Wenn das stimmt, dann war es auch Bob. Typen von Angriffen: ^ aktiv ^ passiv | | chosen plaintext \\ Veränderungen im Chiffretext | Chiphertext only | ==== Blockchiffren ==== ==== Stromchiffren ==== Schlüsselstrom | 0100100011110 | Klartext | | 1000111110010 | Schlüsselstrom: Den können Sender und Empfänger aus einem gemeinsamen Schlüssel erzeugen | | 1100011101100 | Chiffretext: XOR | 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 ===== 3.11.2005 ===== ==== Stromchiffren ==== (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 = | **1** | **0** | **0** | **0** | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | **1** | **0** | **0** | **0** | 1 | 0 | 0 | ... | | s_0 | s_1 | s_2 | s_3 | s_4 | s_5 | s_6 | s_7 | s_8 | s_9 | s_10 | s_11 | s_12 | s_13 | s_14 | s_15 | s_16 | s_17 | s_18 | s_19 | s_20 | s_21 | ... | s ist also periodisch, mit der Persiode 2^n. Periodik bei einem Schlüssel -> Problematisch. Ziel der Stromchiffre: Verschlüsselung beliebig langer Dokumente. \\ Idee: ^ d | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | Klartext | ^ s | **1** | **0** | **0** | **0** | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | **1** | **0** | **0** | **0** | 1 | 0 | 0 | Schlüsselstrom (__effizient__ generierbar) | ^ c | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | Klartext xor Schlüsselstrom | 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(c) = d_s_0(c_0)d_s_1(c_1)... ==== Blockchiffren ==== 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 - Effizient notiert - Effizient ausgewertet werden können! ==== Modi ==== Verwende Blockchiffren zur Verschlüsselung beliebig langer Texte. === Electronic Codebook Mode (ECB) === 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 = 10110001010010//10// (//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! === Cipher Block Chaining Mode (CBC) === 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}, ... ===== 07.11.2005 (ab ~16:50) ===== //(erster Teil der Vorlesung siehe http://www.datenzone.de/space/Krypto/Krypto+4.+Vorlesung, Inhalt war CFB und OFB, siehe auch [[wp>Block cipher modes of operation]])// ==== Kongruenzen ==== 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 ===== 10.11.2005 ===== ==== Kongruenzen ==== 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 ==== Euklidischer Algorithmus ==== 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 ==== Erweiterter Euklidscher Algorithmus ==== 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 ^ i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ^ r_i | 140 | 37 | 29 | 8 | 5 | 3 | 2 | 1 | 0 | ^ q_i | - | 3 | 1 | 3 | 1 | 1 | 1 | 2 | - | ^ x_i | 1 | 0 | 1 | 1 | 4 | 5 | 9 | 14 | 37 | ^ y_k | 0 | 1 | 3 | 4 | 15 | 19 | 34 | 53 | 140 | 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 ===== 14.11.2005 (ab ~16:50) ===== ==== Matrizen über Ringen ==== 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 = (aij), i = 1, ... , k, j = 1, ... , n geschrieben als rechteckiges Schema {{uni:mitschriften:krypto:krypto20051114-01.png}} Wir bezeichnen mit R(k,n) bzw Rk x n die Menge aller k x n Matrizen über R * aij Koeffizienten von A * (a1j a2j ... akj)T ist die j-te Spalte von A * (ai1 ai2 ... ain) ist die i-te Spalte von A Zeilenvektoren sind 1 x n Matrizen, Spaltenvektoren sind k x 1 Matrizen. ==== Summe und Produkt von Matrizen ==== Seien k, n element N und A, B element Rk x n A = (aij), B = (bij), i = 1, ... , k, j = 1, ... , n Die Summe von A und B ist A + B = (aij + bij), i = 1, ... , k, j = 1, ... , n Das Produkt von A und C element Rn x m ist A * C = (dij), 1 <= i <= k, 1 <= k <= n \\ dij = Summe von v = 1 bis n über aivcvj \\ A * C element Rk x m ==== Der Matrizenring ==== Sei R ein kommutativer Ring mit Einselement 1 und n element N, dann ist (Rn x n, +, *) ein Ring.\\ Einselement in Rn x n ist die identität oder Einheitsmatrix (eij) = 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. ==== Determinante und Inverse von Matrizen ==== Sei A element Rn x n, dann ist Aij 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 aij det Aij ) Bsp: A = ( (a11 a12) (a21 a22) ). A11 = a22, A21 = a12, A12 = a21, A22 = a11.\\ det A = (-1)2a11a22 + (-1)3a12a21 = a11a22 - a12a21 ==== Eigenschaften der Determinante (ohne Beweis) ==== A, B element Rn x n * det(AB) = det A * det B * det( (eij) ) = 1 * c element R, c * A = (c * aij ), det(cA) = cndet A Die transponierte Matrix von A = (aij) ist die Matrix AT = (aji). Es gilt det(AT) = det(A) a element Zn, dann ist ax kongruent 1 mod n lösbar falls gcd(a, n) = 1. Eine Matrix A element Rn x n hat genau ein multiplikatives Inverses. Wir definieren dazu die Adjunkte von A: adj(A) = ( (-1)i+j det(Aji) ) Es gilt A-1 = (det A)-1 * adj(A) Beispiel: A = ( (a11 a12) (a21 a22) ) \\ adj(A) = ( (+a22 -a12) (-a21 +a11) ) Sei R = Zm für m element N und A = Znn x n mit n element N, dann ist A genau dann invertierbar, wenn gcd(det A, m) = 1 Beispiel: Z42 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__ ===== 17.11.2005 ===== ==== Affin lineare Blockchiffren ==== Klartextraum, Schlüsseltextraum => Zmn, n, m element N, n = Blocklänge E : Zmn -> Zmn \\ p = (p1, p2, ... , pn) -> Ap + b mod m \\ A element Zmnxn, b element Zmn __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 Zmnxn x Zmn, A invertierbar mod m D : Zmn -> Zmn \\ 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 \\ c0 = (1 1)T, m0 = (3 1)T \\ c1 = (2 3)T, m1 = (2 5)T \\ c2 = (8 2)T, m2 = (4 8)T \\ c3 = (7 7)T, m3 = (? ?)T \\ c1 - c0 kongruent (Am1 + b) - (Am0 + b) kongruent Am1 - Am0 kongruent A(m1 - m0) mod m \\ c2 - c0 kongruent A(m2 - m0) ... | c1 - c0 | c2 - c0 | m1 - m0 | m2 - m0 | | (1 2)T | (7 1)T | (-1 4)T | (1 7)T | ( (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 Am0 kongruent ( (1 8) (0 3) )(3 1)T kongruent (11 3)T kongruent (1 3)T mod 10 (1 1)T = c0 kongruent Am0 + b kongruent (1 3)T + b mod 10 \\ <=> b kongruent (0 -2)T mod 10 c3 = (7 7)T m3 kongruent A-1(c3 - 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 ==== Known Plaintext Angriff aud die affin lineare Blockchiffre ==== * Blocklänge n * Klar- und Schlüsseltextraum Zmn * Gegeben Paare von Klar- und Schlüsseltexten (mi, ci), ci = Ami + b, i = 0, ... * Berechne ~ci = ci - c0, ~mi = mi - m0 \\ ~ci kongruent A~mi mod m * Bilde * ~C element Zmnxn, wobei die i-te Spalte ~ci ist * ~M element Zmnxn, wobei die i-te Spalte ~mi ist * ~C kongruent A~M mod m * Falls ~M invertierbar ist, berechne ~C~M-1 kongruent A mod m, b kongruent ci - Ami 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, p1 = (1 0 1 0)T, p2 = (1 0 0 1)T \\ Ap1 kongruent (1 0 0 1)T mod 2, Ap2 kongruent (0 0 1 1)T mod 2 => Bitpermutation! ==== Was ist linear, was affin linear? ==== f : Zmn -> Zmn * linear, falls eine Matrix existiert A element Zmkxn so dass f(x) = Ax mod m <=> a, b element Zm, x, y element Zmn, f(ax + by) kongruent af(x) + bf(y) mod m * affin linear, falls eine Matrix existiert A element Zmkxn so dass f(x) = Ax + b mod m <=> ~f : Zmn -> Zmk, x -> f(x) - f(0) mod m, ~f linear Hill: 3-fach Verschlüsselung: - nicht-linearer Schritt - linearer Schritt - nicht-linearer Schritt (geheim) nicht linear: \\ p1 -> pi(p1) \\ p2 -> pi(p2) \\ ... \\ pn -> pi(pn) => **Feistelchiffre** : Kombination linearer und nicht-linearer Schritte Feistel: IBM (1915 - 1990), + Don Coppersmith => Lucipher Cipher. Siehe auch DES, RC5, Blowfish... AES ===== 21.11.2005 ===== //(Keine Mitschrift von meiner Seite, siehe [[http://www.datenzone.de/space/Krypto/Krypto+8.+Vorlesung]])// ===== 24.11.2005 ===== ==== Time memory tradeoff ==== Situation: Wir kennen Klartext x und zugehörigen Chriffretext c. Wir wollen ein Schlüssel K mit EK(x) = c Vollständige Suche: * Zeit: ~ |K| (K = Schlüsselraum) * Platz: konstant M = ceil( |K|1/3 ) gk : Sigman -> K , 1 kleinergleich k kleinergleich m, K = Schlüssel, Sigman = Klar-/Chiffretexte ki, 1 kleinergleich i kleinergleich m Kk (i, j) = { Ki für j=0 ; gk( EK_k (i, j-1)(x) ) sonst } ((k Nr der Tabelle, (i,j) Koordinate, gk zufällig)) Kk(1,0) -> Kk(1,1) -> ... -> Kk(1,m) \\ Kk(2,0) -> ... \\ ... \\ Kk(m,0) ~ m2 Schlüssel, m Tabellen, insgesamt m3 Schlüssel Bei richtiger Wahl von gk, Ki 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) = gk( c ), 1 kleinergleich k kleinergleich m. Suche den in einer Tabelle. Wenn man den findet, dann gk( EK_k (i,j-1)(x) ) = gk( C ) = Kk(i,j) Prüfe, ob EK_k (i,j-1)(x) = C Analyse: Alle Tabellen werden gebraucht (Platz |K|) \\ Zeit: O(|K|1/3) Modifikation K(1,k) = gk( C ) \\ K(j,k) = gk( EK(j-1,k)(x) ), 1 kleinergleich k kleinergleich m, 1 kleiner j kleinergleich m Wenn K(j,k) = Kk(i,m) , dann ist Kk(i,m-j) der Kandidate. Konstruiere die i-te Zeile der k-ten Tabelle. Teste, ob Kk(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 ==== Endliche Körper ==== 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} ^ + ^ 0 ^ 1 ^ 2 | ^ 0 | 0 | 1 | 2 | ^ 1 | 1 | 2 | 0 | ^ 2 | 2 | 0 | 1 | ^ * ^ 0 ^ 1 ^ 2 | ^ 0 | 0 | 0 | 0 | ^ 1 | 0 | 1 | 2 | ^ 2 | 0 | 2 | 1 | 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 pn Elemente konstruieren. Restklassen von Polynomen mit Koeffizienten in Fp modulo eines irreduziblen Polynoms Z/pZ = Fp \\ F2 = {0, 1} Konstruktion von F4 Irreduzibles Polynom mit Koeffizienten in F2 von Grad 2. X2 = X * X => reduzibel \\ X2 + 1 = (X+1)(X+1) => reduzibel \\ X2 + X + 1 => irreduzibel => p(x) = X2 + X + 1 F4 besteht aus allen Restklassen von Polynomen in F2[x] modulo p(x). ^ + ^ 0 ^ 1 ^ X ^ X+1 | ^ 0 | 0 | 1 | X | X+1 | ^ 1 | 1 | 0 | X+1 | X | ^ X | X | X+1 | 0 | 1 | ^ X+1 | X+1 | X | 1 | 0 | ^ * ^ 0 ^ 1 ^ X ^ X+1 | ^ 0 | 0 | 0 | 0 | 0 | ^ 1 | 0 | 1 | X | X+1 | ^ X | 0 | X | X+1 | 1 | ^ X+1 | 0 | X+1 | 1 | X | Konstruktion von Fpn * Finde irreduzibles Polynom von Grad n in Fp[x], nenne es g(x) * Dann ist Fp[x] / g(x)Fp[x] ein endlicher Körper mit pn Elementen. ===== 28.11.2005 (ab ~17:15) ===== ==== Geburtstagsparadoxon ==== __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/(3652) * (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 = 216 = 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? === Allgemeine Formel === Gegenwahrscheinlichkeit q = 1/nn * 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 ex 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 ==== Perfekte Sicherheit ==== 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 Ek : P -> C, Entschlüsselungsfunktionen Dk : C -> P Ansatz: Der Schlüsseltext soll keine Informationen über den Klartext verraten, solange der Schlüssel unbekannt ist. ===== 1.12.2005 ===== //Ausgefallen.// ===== 5.12.2005 (ab ~17:20) ===== __Beispiel__ Vernan One-Time-Pad P = C = K = {o, 1}n ^ p | 01000110000111 | ^ k | 10100010110101 | ^ xor | 11100100110010 | 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. ===== 15.12.2005 ===== 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 ai mod mi, i=1,..,n \\ m = Produkt für i=1 bis n von mi \\ Mi = m / mi \\ xgcd : yiMi kongurent 1 mod mi \\ x = Summe für i=1 bis n von (aiyiMi Bsp: M1=35, M2=21, M3=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) = 2t'k' für ein t' element N und ein k' element N so dass k' ungerade \\ s := max{ t element N : 2t teilt ed-1 } \\ k=(ed - 1) / 2s Abbildung: psi : Zn -> Zp x Zq, x -> (x mod p, x mod q). Invertierbar wegen CRT __Theorem__: Sei a element Zn und die Ordnung von ak in Zp und Zq sei verschieden. Dann gcd(a2^t*k - 1, n) < n und > 1 für ein t element {1, ..., s-1}. __Beweis__: gcd( ed-1, phi(n) ) = 2t'k' => t' kleinergleich s \\ (ak)2^t' kongruent 1 mod n \\ 2t'k' | 2t'k \\ => Ordnung ak in Zp und Zq ist in { 2i | 1 kleinergleich i kleinergleich s } \\ 2t = Ordnung von ak in Zp und in Zq \\ (ak)2^{t-1} nicht kongruent 1 mod p \\ (ak)2^t kongruent 1 mod q \\ => gcd( (ak)2^t - 1; n) = q Fortsetzung folgt.. ===== 19.12.2005 ===== DHP, einzige bekannte Lösung via DLP. p ungefähr 21024. 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} ==== Verschlüsselungsverfahren nach ElGamal ==== Schlüsselerzeugung: p, g element {2, ... , p-1}, hat hohe Ordnung. a element_R {0, ..., p-2} A = ga 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 = gb mod p \\ K = Ab 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...)// ~~DISCUSSION~~