Powerpoint-Präsentation

 Documents

 8 views
of 67
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Das RSA-Verfahren - Einsatz von Standardalgorithmen in der Kryptologie Klaus Becker 2007 2 Verschlüsseln durch modulares Rechnen modulares modulares modulares…
Share
Transcript
Das RSA-Verfahren - Einsatz von Standardalgorithmen in der Kryptologie Klaus Becker 2007 2 Verschlüsseln durch modulares Rechnen modulares modulares modulares Addieren Multiplizieren Potenzieren Verschlüsselung mit Verschlüsselung mit Verschlüsselung mit öffentl. Schlüssel (d, m) öffentl. Schlüssel (d, m) öffentl. Schlüssel (d, m) z → (z + d) % m z → (z * d) % m z → (z ** d) % m Entschlüsselung mit Entschlüsselung mit Entschlüsselung mit privat. Schlüssel (e, m) privat. Schlüssel (e, m) privat. Schlüssel (e, m) z → (z + e) % m z → (z * e) % m z → (z ** e) % m Zielsetzung: Am Beispiel kryptologischer Verfahren  Relevanz von Algorithmen erkennen  Bedeutung schneller Algorithmen erleben  Standardalgorithmen kennen lernen 3 Teil 1 Das RSA-Verfahren 4 RSA-Verfahren 5 Aufgabe Experimentieren Sie mit dem Werkzeug "CrypTool", um einen ersten Eindruck von der Arbeitsweise des RSA-Verfahrens zu gewinnen. Starten Sie CrypTool. Rufen Sie [Einzelverfahren] [RSA-Kryptosystem] [RSA-Demo] auf. Nutzen Sie jetzt CrypTool, um einfache Texte zu verschlüsseln und wieder entschlüsseln. 6 Orientierung Im folgenden soll das RSA-Verfahren genauer untersucht werden. Dabei sollen insbesondere die algorithmischen Grundlagen analysiert werden. Die mathematischen Aspekte werden kurz angesprochen, aber nicht weiter vertieft. Die Vorgehensweise folgt einem Vorschlag von Witten und Schulz, der in den folgenden Artikeln beschrieben wird: H. Witten, R.-H. Schulz: RSA & Co. in der Schule, Teil1. LOG IN 140 S. 45 ff. H. Witten, R.-H. Schulz: RSA & Co. in der Schule, Teil2. LOG IN 143 S. 50 ff. 7 Teil 2 Verschlüsseln mit modularer Addition 8 Den Anfang macht Caesar PYLZFOWBNQCYBUVNCBLGYC HYAYBYCGMWBLCZNYHNTCZY LN VDOYH FDHVDU 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 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C Schlüssel: D Quelltext: Geheimtext: SALVECAESAR VDOYHFDHVDU 9 Caesar-Verfahren mit Zahlen Codierung: A → 00 A#S#T#E#R#I#X B → 01 Umwandlung von ... Zeichen in Zahlen Z → 25 00#18#19#04#17#08#23 Verschlüsselung: (0 + 3) % 26 = 3 00#18#19#04#17#08#23 (18 + 3) % 26 = 21 Verarbeitung von Zahlen ... (23 + 3) % 26 = 0 03#21#22#07#20#11#00 Entschlüsselung: (3 + 23) % 26 = 0 03#21#22#07#20#11#00 (21 + 23) % 26 = 18 Verarbeitung von Zahlen ... (0 + 23) % 26 = 23 00#18#19#04#17#08#23 Decodierung: A → 00 00#18#19#04#17#08#23 B → 01 Umwandlung von ... Zahlen in Zeichen Z → 25 A#S#T#E#R#I#X 10 Modulares Rechnen - Addition „Es ist jetzt 14 Uhr. In 22 Stunden gibt es wieder 14 + 22 = 12 Mittagessen.“ Uhrenaddition: (14 + 22) % 24 = 36 % 24 = 12 %: Rest bei der ganzzahligen Division Bsp.: 12 % 4 = 0; 12 % 5 = 2; 12 % 17 = 12 Verschlüsselung: (0 + 3) % 26 = 3 00#18#19#04#17#08#23 (18 + 3) % 26 = 21 Verarbeitung von Zahlen ... (23 + 3) % 26 = 0 03#21#22#07#20#11#00 Entschlüsselung: (3 + 23) % 26 = 0 03#21#22#07#20#11#00 (21 + 23) % 26 = 18 Verarbeitung von Zahlen ... (0 + 23) % 26 = 23 00#18#19#04#17#08#23 11 Caesar-Variationen Codierung: A → 01 A#S#T#E#R#I#X B → 02 Umwandlung von ... Zeichen in Zahlen Z → 26 01#19#20#05#18#09#24 Verschlüsselung: (1 + 9) % 30 = 10 01#19#20#05#18#09#24 (19 + 9) % 30 = 28 Verarbeitung von Zahlen ... (e, m) = (9, 30) (24 + 9) % 30 = 3 10#28#29#14#27#18#03 Entschlüsselung: (10 + 21) % 30 = 1 10#28#29#14#27#18#03 (28 + 21) % 30 = 19 Verarbeitung von Zahlen ... (d, m) = (21, 30) (3 + 21) % 30 = 24 01#19#20#05#18#09#24 Decodierung: A → 01 01#19#20#05#18#09#24 B → 02 Umwandlung von ... Zahlen in Zeichen Z → 26 A#S#T#E#R#I#X 12 Caesar-Variationen Codierung: AA → 0101 AS#TE#RI#X AB → 0102 Code: A → 1 ... Blocklänge: 2 ZZ → 2626 0119#2005#1809#24 Verschlüsselung: (119 + 2102) % 3000 0119#2005#1809#24 = 2221 öffentlicher Schlüssel (2005 + 2102) % 3000 (e, m) = (2102, 3000) = 1107 ... 2221#1107#911#2126 Entschlüsselung: (2221 + 898) % 3000 2221#1107#911#2126 = 119 privater Schlüssel (1107 + 898) % 3000 (d, m) = (898, 3000) = 2005 ... 0119#2005#1809#24 Decodierung: AA → 0101 0119#2005#1809#24 AB → 0102 Code: A → 1 ... Blocklänge: 2 ZZ → 2626 AS#TE#RI#X 13 Aufgabe Codierung: AA → 0101 DO#MS#PE#YE#R AB → 0102 Code: A → 1 ... Blocklänge: 2 ZZ → 2626 Verschlüsselung: öffentlicher Schlüssel (e, m) = (567, 2911) Entschlüsselung: privater Schlüssel (d, m) = (2344, 2911) Decodierung AA → 0101 AB → 0102 Code: A → 1 ... Blocklänge: 2 ZZ → 2626 14 Aufgabe Codierung: A → 01 B → 02 Code: A → 1 ... Blocklänge: 1 Z → 26 Verschlüsselung: öffentlicher Schlüssel (e, m) = (99, 411) Entschlüsselung: 103#114#112#107#114#105 privater Schlüssel (d, m) = Decodierung A → 01 B → 02 Code: A → 1 ... Blocklänge: 1 Z → 26 15 Additives Chiffrierverfahren Codierung: AA → 0101 AS#TE#RI#X AB → 0102 Code: A → 1 ... Blocklänge: 2 ZZ → 2626 0119#2005#1809#24 Verschlüsselung: z → (z + e) % m 0119#2005#1809#24 öffentlicher Schlüssel Bed.: z < m (e, m) = (2102, 3000) m > maxCode 2221#1107#1010#2126 Entschlüsselung: z → (z + d) % m 2221#1107#1010#2126 privater Schlüssel Bed.: (d, m) = (898, 3000) (e + d) % m = 0 0119#2005#1809#24 Decodierung: AA → 0101 0119#2005#1809#24 AB → 0102 Code: A → 1 ... Blocklänge: 2 ZZ → 2626 AS#TE#RI#X 16 Additives Chiffrierverfahren Codierung: b→z AS#TE#RI#X Code: A → 1 eindeutige Codierung Blocklänge: 2 von Zeichenblöcken 0119#2005#1809#24 Verschlüsselung: z → (z + e) % m 0119#2005#1809#24 öffentlicher Schlüssel Bed.: z < m (e, m) = (2102, 3000) m > maxCode 2221#1107#1010#2126 Entschlüsselung: z → (z + d) % m 2221#1107#1010#2126 privater Schlüssel Bed.: (d, m) = (898, 3000) (e + d) % m = 0 0119#2005#1809#24 Decodierung z→b 0119#2005#1809#24 Code: A → 1 Decodierung als Um- Blocklänge: 2 kehrung der Codierung AS#TE#RI#X 17 Additives Chiffrierverfahren Korrektheit: Die Entschlüsselung macht die Verschlüsselung rückgängig: z → (z + e) % m → ((z + e) % m + d) % m = (z + (e + d) % m) % m = z % m = z Verschlüsselung: z → (z + e) % m 0119#2005#1809#24 öffentlicher Schlüssel Bed.: m ist größer als (e, m) = (2102, 3000) die maximale Codezahl 2221#1107#1010#2126 Entschlüsselung: z → (z + d) % m 2221#1107#1010#2126 privater Schlüssel Bed.: (d, m) = (898, 3000) e+d=m 0119#2005#1809#24 Sicherheit: Das "additive" Chiffrierverfahren ist nicht sicher, da man aus dem öffentlichen Schlüssel sofort den privaten Schlüssel bestimmen kann. 18 Prinzip von Kerckhoff Die Sicherheit eines Kryptosystems darf nicht von der Geheimhaltung des Algorithmus abhängen. Die Sicherheit darf sich nur auf die Geheimhaltung des Schlüssels gründen. Vgl. A. Beutelspacher: Kryptologie. Vieweg 1996 Das Prinzip wurde erstmals formuliert im Buch "La cryptographie militaire" von Jean Guillaume Hubert Victor Francois Alexandre Auguste Kerckhoffs van Nieuwenhof (1835 bis 1903). Sicherheit: Das "additive" Chiffrierverfahren erfüllt nicht das Prinzip von Kerckhoff. 19 Implementierung Codierung: AA → 0101 Zur Implementierung des AB → 0102 vorgestellten Chiffrier- Code: A → 1 ... verfahrens (in Python) Blocklänge: 2 ZZ → 2626 werden die einzelnen Operationen mit Hilfe von Verschlüsselung: (119 + 2102) % 3000 Funktionen dargestellt. = 2221 öffentlicher Schlüssel (2005 + 2102) % 3000 (e, m) = (2102, 3000) = 1107 ... Entschlüsselung: (2221 + 898) % 3000 = 119 privater Schlüssel (1107 + 898) % 3000 def zahl(c): (d, m) = (898, 3000) = 2005 ... def def zeichen(z): zerlegen(wort, blocklaenge): def codierenBlock(wort): def codierenBlockListe(blockListe): Decodierung: AA → 0101 def def codieren(wort, blocklaenge): decodierenZahl(zahl): AB → 0102 def decodierenZahlListe(zahlenListe): Code: A → 1 ... def def zusammenfuegen(liste): decodieren(zahlenListe): Blocklänge: 2 ZZ → 2626 def def verschluesselnZahl(zahl, schluessel): verschluesseln(zahlenListe, 20 Aufgabe In der Datei "ChiffriersystemModularesAddieren.py" finden Sie eine Implementierung des vorgestellten Chiffrierverfahrens. Analysieren Sie die einzelnen Funktionsdeklarationen und ergänzen Sie geeignete Testfälle. 21 Teil 3 Verschlüsseln mit modularer Multiplikation 22 Multiplikatives Chiffrierverfahren Codierung: b→z A#S#T#E#R#I#X Code: A → 1 eindeutige Codierung Blocklänge: 1 von Zeichenblöcken 01#19#20#05#18#09#24 Verschlüsselung: z → (z * e) % m 01#19#20#05#18#09#24 öffentlicher Schlüssel Bed.: (e, m) = (7, 30) z 0 q := aalt div amitte (1) 884 = 2*320 + 244 aneu := aalt mod amitte → 244 = 884 - 2*320 = (1*884 + 0*320) - 2*(1*320 + 0*884) = 1*884 - 2*320 xneu := xalt - q*xmitte (2) 320 = 1*244 + 76 yneu := yalt - q*ymitte → 76 = 320 - 1*244 = (0*884 + 1*320) - 1*(1*884 - 2*320)) = 3*320 - 1*884 xalt := xmitte (3) 244 = 3*76 + 16 xmitte := xneu → 16 = 244 - 3*76 = (1*884 - 2*320) - 3*(3*320 - 1*884) = 4*884 - 11*320 yalt := ymitte (4) 76 = 4*16 + 12 → 12 = 76 - 4*16 = (3*320 - 1*884) - 4*(4*884 - 11*320) = 47*320 - 17*884 ymitte := yneu aalt := amitte (5) 16 = 1*12 + 4 → 4 = 16 - 1*12 = (4*884 - 11*320) - 1*(47*320 - 17*884) = 21*884 - 58*320 amitte := aneu Ausgabe: aalt, xalt, yalt (6) 12 = 3*4 + 0 40 Erweiterter euklidischer Algorithmus Geg.: a = 884; b = 320; Ges.: ggT(a, b) = x*a + y*b Bachet aalt:884 = a:884 Eingabe: a, b amitte:320 = b:320 aalt := a xalt:1 = 1 amitte := b xmitte:0 = 0 xalt := 1 yalt:0 = 0 ymitte:1 = 1 xmitte := 0 {aalt:884 = xalt:1 * a: 884 + yalt:0 * b:320; yalt := 0 amitte:320 = xmitte:0 * a:884 + ymitte:1 * b:320} ymitte := 1 (1) 884 = 2*320 + 244 → 244 = 884 - 2*320 = SOLANGE amitte <> 0 (1*884 + 0*320) - 2*(1*320 + 0*884) = q := aalt div amitte 1*884 - 2*320 aneu := aalt mod amitte q: 2 = aalt: 884 / amitte: 320 xneu := xalt - q*xmitte aneu:244 = aalt:884 % amitte:320 yneu := yalt - q*ymitte xneu:1 = xalt:1 - xmitte:0 * q:2 yneu:-2 = yalt:0 - ymitte:1 * q:2 xalt := xmitte xalt:0 = xmitte:0 xmitte := xneu xmitte:1 = xneu:1 yalt := ymitte yalt:1 = ymitte:1 ymitte := yneu ymitte:-2 = yneu:-2 aalt:320 = amitte:320 aalt := amitte amitte:244 = aneu:244 amitte := aneu {aalt:320 = xalt:0 * a:884 + yalt:1 * b:320; Ausgabe: aalt, xalt, yalt amitte:244 = xmitte:1 * a:884 + ymitte:-2 * b:320} 41 Erweiterter euklidischer Algorithmus {aalt:320 = xalt:0 * a:884 + yalt:1 * b:320; Bachet amitte:244 = xmitte:1 * a:884 + ymitte:-2 * b:320} Eingabe: a, b (2) 320 = 1*244 + 76 → 76 = 320 - 1*244 = aalt := a (0*884 + 1*320) - 1*(1*884 - 2*320)) = amitte := b 3*320 - 1*884 xalt := 1 q: 1 = aalt: 320 / amitte: 244 aneu:76 = aalt:320 % amitte:244 xmitte := 0 xneu:-1 = xalt:0 - xmitte:1 * q:1 yalt := 0 yneu:3 = yalt:1 - ymitte:-2 * q:1 ymitte := 1 xalt:1 = xmitte:1 xmitte:-1 = xneu:-1 SOLANGE amitte <> 0 yalt:-2 = ymitte:-2 q := aalt div amitte ymitte:3 = yneu:3 aneu := aalt mod amitte aalt:244 = amitte:244 xneu := xalt - q*xmitte amitte:76 = aneu:76 {aalt:244 = xalt:1 * a:884 + yalt:-2 * b:320; yneu := yalt - q*ymitte amitte:76 = xmitte:-1 * a:884 + ymitte:3 * b:320} xalt := xmitte xmitte := xneu yalt := ymitte ymitte := yneu aalt := amitte amitte := aneu Ausgabe: aalt, xalt, yalt 42 Aufgabe Die Datei "ErweiterterEuklidischerAlgorithmus.py" enthält eine Implementierung des erweiterten euklidischen Algorithmus. Testen Sie diese Implementierung. Fügen Sie insbesondere Ausgabeanweisungen ein und überprüfen Sie das gezeigte Ablaufprotokoll. 43 Bestimmung des modularen Inversen Mit Hilfe der Ausgaben des erweiterten euklidischen Algorithmus lässt sich das modulare Inverse bestimmen: Beispiel 1: modInv(41, 192) Beachte: ggT(41, 192) = 1. Das modulare Inverse von 41 bzgl. 192 kann bestimmt werden. Der Algorithmus von Bachet liefert zu den Eingaben (41, 192) die Ausgabe (1, 89, -19). Also: 1 = 89*41 + (-19)*192 Also: (89*41) % 192 = (1 - (-19)*192) % 192 = (1 + 19*192) % 192 = 1 Also: modInv(41, 192) = 89 Beispiel 2: modInv(17, 192) Beachte: ggT(17, 192) = 1. Das modulare Inverse von 17 bzgl. 192 kann bestimmt werden. Der Algorithmus von Bachet liefert zu den Eingaben (17, 192) die Ausgabe (1, -79, 7). Also: 1 = (-79)*17 + 7*192 Also: 1 + 192*17 = (-79+192)*17 + 7*192 Also: 1 + 192*17 - 7*192 = 113*17 Also: (113*17) % 192 = (1 + 10*192) % 192 = 1 Also: modInv(17, 192) = 113 Beispiel 3: modInv(32
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks