Das RSA-Verfahren -Einsatz von
Standardalgorithmen in der Kryptologie
Klaus Becker
2007
2
Verschlüsseln durch modulares Rechnen
Zielsetzung: Am Beispiel kryptologischer Verfahren Relevanz von Algorithmen erkennen Bedeutung schneller Algorithmen erleben Standardalgorithmen kennen lernen
modulares Addieren
Verschlüsselung mit öffentl. Schlüssel (d, m)
z → (z * d) % m
z → (z * e) % m
modulares Multiplizieren
Entschlüsselung mit privat. Schlüssel (e, m)
Verschlüsselung mit öffentl. Schlüssel (d, m)
z → (z + d) % m
z → (z + e) % m
Entschlüsselung mit privat. Schlüssel (e, m)
Verschlüsselung mit öffentl. Schlüssel (d, m)
z → (z ** d) % m
z → (z ** e) % m
Entschlüsselung mit privat. Schlüssel (e, m)
modulares Potenzieren
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
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: DQuelltext:
SALVECAESAR
Geheimtext:VDOYHFDHVDU
PYLZFOWBNQCYBUVNCBLGYCHYAYBYCGMWBLCZNYH
NTCZYLN
VDOYHFDHVD
U
9 Caesar-Verfahren mit Zahlen
A → 00B → 01
...Z → 25
A#S#T#E#R#I#X
00#18#19#04#17#08#23
(0 + 3) % 26 = 3(18 + 3) % 26 = 21...(23 + 3) % 26 = 0
00#18#19#04#17#08#23
03#21#22#07#20#11#00
(3 + 23) % 26 = 0(21 + 23) % 26 = 18...(0 + 23) % 26 = 23
03#21#22#07#20#11#00
00#18#19#04#17#08#23
A → 00B → 01
...Z → 25
00#18#19#04#17#08#23
A#S#T#E#R#I#X
Codierung:
Umwandlung von Zeichen in Zahlen
Verschlüsselung:
Verarbeitung von Zahlen
Entschlüsselung:
Verarbeitung von Zahlen
Decodierung:
Umwandlung von Zahlen in Zeichen
10 Modulares Rechnen - Addition
Uhrenaddition: (14 + 22) % 24 = 36 % 24 = 12
%: Rest bei der ganzzahligen Division
Bsp.: 12 % 4 = 0; 12 % 5 = 2; 12 % 17 = 12Verschlüsselung:
Verarbeitung von Zahlen
(0 + 3) % 26 = 3(18 + 3) % 26 = 21...(23 + 3) % 26 = 0
00#18#19#04#17#08#23
03#21#22#07#20#11#00
Entschlüsselung:
Verarbeitung von Zahlen
(3 + 23) % 26 = 0(21 + 23) % 26 = 18...(0 + 23) % 26 = 23
03#21#22#07#20#11#00
00#18#19#04#17#08#23
„Es ist jetzt 14 Uhr. In 22 Stunden gibt es
wieder Mittagessen.“ 14 + 22 = 12
11 Caesar-Variationen
Codierung:
Umwandlung von Zeichen in Zahlen
A → 01B → 02
...Z → 26
A#S#T#E#R#I#X
01#19#20#05#18#09#24
Verschlüsselung:
Verarbeitung von Zahlen(e, m) = (9, 30)
(1 + 9) % 30 = 10(19 + 9) % 30 = 28...(24 + 9) % 30 = 3
01#19#20#05#18#09#24
10#28#29#14#27#18#03
Entschlüsselung:
Verarbeitung von Zahlen(d, m) = (21, 30)
(10 + 21) % 30 = 1(28 + 21) % 30 = 19...(3 + 21) % 30 = 24
10#28#29#14#27#18#03
01#19#20#05#18#09#24
Decodierung:
Umwandlung von Zahlen in Zeichen
A → 01B → 02
...Z → 26
01#19#20#05#18#09#24
A#S#T#E#R#I#X
12 Caesar-Variationen
Codierung:
Code: A → 1Blocklänge: 2
AA → 0101AB → 0102
...ZZ → 2626
AS#TE#RI#X
0119#2005#1809#24
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (2102, 3000)
(119 + 2102) % 3000 = 2221(2005 + 2102) % 3000 = 1107 ...
0119#2005#1809#24
2221#1107#911#2126
Entschlüsselung:
privater Schlüssel(d, m) = (898, 3000)
(2221 + 898) % 3000 = 119(1107 + 898) % 3000 = 2005 ...
2221#1107#911#2126
0119#2005#1809#24
Decodierung:
Code: A → 1Blocklänge: 2
AA → 0101AB → 0102
...ZZ → 2626
0119#2005#1809#24
AS#TE#RI#X
13 Aufgabe
Codierung:
Code: A → 1Blocklänge: 2
DO#MS#PE#YE#R
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (567, 2911)
Entschlüsselung:
privater Schlüssel(d, m) = (2344, 2911)
Decodierung
Code: A → 1Blocklänge: 2
AA → 0101AB → 0102
...ZZ → 2626
AA → 0101AB → 0102
...ZZ → 2626
14 Aufgabe
Codierung:
Code: A → 1Blocklänge: 1
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (99, 411)
Entschlüsselung:
privater Schlüssel(d, m) =
103#114#112#107#114#105
Decodierung
Code: A → 1Blocklänge: 1
A → 01B → 02
...Z → 26
A → 01B → 02
...Z → 26
15 Additives Chiffrierverfahren
Codierung:
Code: A → 1Blocklänge: 2
AA → 0101AB → 0102
...ZZ → 2626
AS#TE#RI#X
0119#2005#1809#24
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (2102, 3000)
z → (z + e) % m 0119#2005#1809#24
2221#1107#1010#2126
Entschlüsselung:
privater Schlüssel(d, m) = (898, 3000)
z → (z + d) % m 2221#1107#1010#2126
0119#2005#1809#24
Decodierung:
Code: A → 1Blocklänge: 2
AA → 0101AB → 0102
...ZZ → 2626
0119#2005#1809#24
AS#TE#RI#X
Bed.: z < mm > maxCode
Bed.: (e + d) % m = 0
16 Additives Chiffrierverfahren
Codierung:
Code: A → 1Blocklänge: 2
b → z AS#TE#RI#X
0119#2005#1809#24
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (2102, 3000)
z → (z + e) % m 0119#2005#1809#24
2221#1107#1010#2126
Entschlüsselung:
privater Schlüssel(d, m) = (898, 3000)
z → (z + d) % m 2221#1107#1010#2126
0119#2005#1809#24
Decodierung
Code: A → 1Blocklänge: 2
0119#2005#1809#24
AS#TE#RI#X
eindeutige Codierung von Zeichenblöcken
Bed.: z < mm > maxCode
Bed.: (e + d) % m = 0
z → b
Decodierung als Um-kehrung der Codierung
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:
öffentlicher Schlüssel(e, m) = (2102, 3000)
z → (z + e) % m 0119#2005#1809#24
2221#1107#1010#2126
Entschlüsselung:
privater Schlüssel(d, m) = (898, 3000)
z → (z + d) % m 2221#1107#1010#2126
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.
Bed.: m ist größer als die maximale Codezahl
Bed.: e + d = m
18 Prinzip von Kerckhoff
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).
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.
Sicherheit:
Das "additive" Chiffrierverfahren erfüllt nicht das Prinzip von Kerckhoff.
19 Implementierung
Codierung:
Code: A → 1Blocklänge: 2
AA → 0101AB → 0102
...ZZ → 2626
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (2102, 3000)
(119 + 2102) % 3000 = 2221(2005 + 2102) % 3000 = 1107 ...
Entschlüsselung:
privater Schlüssel(d, m) = (898, 3000)
(2221 + 898) % 3000 = 119(1107 + 898) % 3000 = 2005 ...
Decodierung:
Code: A → 1Blocklänge: 2
AA → 0101AB → 0102
...ZZ → 2626
Zur Implementierung des vorgestellten Chiffrier-verfahrens (in Python) werden die einzelnen Operationen mit Hilfe von Funktionen dargestellt.
def zahl(c):def zeichen(z):def zerlegen(wort, blocklaenge):def codierenBlock(wort):def codierenBlockListe(blockListe):def codieren(wort, blocklaenge):def decodierenZahl(zahl):def decodierenZahlListe(zahlenListe):def zusammenfuegen(liste):def decodieren(zahlenListe):def verschluesselnZahl(zahl, schluessel):def 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:
Code: A → 1Blocklänge: 1
b → z A#S#T#E#R#I#X
01#19#20#05#18#09#24
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (7, 30)
z → (z * e) % m 01#19#20#05#18#09#24
07#13#20#05#06#03#18
Entschlüsselung:
privater Schlüssel(d, m) = (13, 30)
z → (z * d) % m 07#13#20#05#06#03#18
01#19#20#05#18#09#24
Decodierung
Code: A → 1Blocklänge: 1
01#19#20#05#18#09#24
A#S#T#E#R#I#X
eindeutige Codierung von Zeichenblöcken
Bed.: z < m
Bed.: (e * d) % m = 1
z → b
Decodierung als Um-kehrung der Codierung
23 Aufgabe
Codierung:
Code: A → 1Blocklänge: 1
b → z C#A#E#S#A#R
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (7, 30)
z → (z * e) % m
Entschlüsselung:
privater Schlüssel(d, m) = (13, 30)
z → (z * d) % m
Decodierung
Code: A → 1Blocklänge: 1
eindeutige Codierung von Zeichenblöcken
Bed.: z < m
Bed.: (e * d) % m = 1
z → b
Decodierung als Um-kehrung der Codierung
24 Aufgabe
Codierung:
Code: A → 1Blocklänge: 1
b → z
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (12, 35)
z → (z * e) % m
Entschlüsselung:
privater Schlüssel(d, m) =
z → (z * d) % m 27#5#6#2#7
Decodierung
Code: A → 1Blocklänge: 1
eindeutige Codierung von Zeichenblöcken
Bed.: z < m
Bed.: (e * d) % m = 1
z → b
Decodierung als Um-kehrung der Codierung
25 Implementierung
Zur Implementierung des vorgestellten Chiffrier-verfahrens (in Python) werden die einzelnen Operationen mit Hilfe von Funktionen dargestellt.
def zahl(c):def zeichen(z):def zerlegen(wort, blocklaenge):def codierenBlock(wort):def codierenBlockListe(blockListe):def codieren(wort, blocklaenge):def decodierenZahl(zahl):def decodierenZahlListe(zahlenListe):def zusammenfuegen(liste):def decodieren(zahlenListe):def verschluesselnZahl(zahl, schluessel):def verschluesseln(zahlenListe,
b → z
z → (z * e) % m
z → (z * d) % m
eindeutige Codierung von Zeichenblöcken
Bed.: z < m
Bed.: (e * d) % m = 1
z → b
Decodierung als Um-kehrung der Codierung
Codierung:
Code: A → 1Blocklänge: 1
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (7, 30)
Entschlüsselung:
privater Schlüssel(d, m) = (13, 30)
Decodierung
Code: A → 1Blocklänge: 1
26 Aufgabe
Ändern Sie die Implementierung des Chiffriersystems mit modularem Addieren geeignet ab und testen Sie das neue Chiffriersystem, das auf modularem Multiplizieren basiert.
27 Modulares Inverses
Zwei Zahlen a, b heißen modular invers zueinander bzgl. des Moduls m genau dann, wenn gilt: (a * b) % m = 1.
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (7, 30)
z → (z * e) % m 01#19#20#05#18#09#24
07#13#20#05#06#03#18
Entschlüsselung:
privater Schlüssel(d, m) = (13, 30)
z → (z * d) % m 07#13#20#05#06#03#18
01#19#20#05#18#09#24
Bed.: z < m; ggT(d, m) = 1
Bed.: (e * d) % m = 1
Bsp.: (7 * 13) % 30 = 1. Also: 13 ist das modulare Inverse zu 7 bzgl. des Moduls m = 30.Beachte: Wenn a und m teilerfremd sind, dann existiert das modulare Inverse von a bzgl. m.
Das multiplikative Chiffrierverfahren funktioniert nur, wenn man zwei Zahlen e und d findet mit (e * d) % m = 1.
28 Aufgabe
Untersuchen Sie, zu welchen der folgenden Zahlen e es ein modulares Inverses d bzgl. des Moduls 12 gibt:
e = 2
e = 3
e = 4
e = 5
e = 6
e = 7
e = 8
e = 9
e = 10
e = 11
29 Korrektheit
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 * 1) % m = z
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (7, 30)
z → (z * e) % m 01#19#20#05#18#09#24
07#13#20#05#06#03#18
Entschlüsselung:
privater Schlüssel(d, m) = (13, 30)
z → (z * d) % m 07#13#20#05#06#03#18
01#19#20#05#18#09#24
Bed.: z < m; ggT(e, m) = 1
Bed.: (e * d) % m = 1
Beispiel:
Verschlüsseln: 9 → (9 * 7) % 30 Entschlüsseln: (9 * 7) % 30 → ([(9 * 7) % 30] * 13) % 30 = [(9 * 7) * 13)] % 30 = [9 * (7 * 13)] % 30 = (9 * [(7 * 13) % 30]) % 30 = (9 * 1) % 30 = 9
30 Aufgabe
Der Korrektheitsnachweis nutzt einige Regeln zum Rechnen mit modularer Multiplikation aus, u. a.:
((a % m) * (b % m)) % m = ((a % m) * b) % m = (a * b) % m
Überprüfen Sie diese Regeln anhand von Beispielen. Sie können sich die Ergebnisse auch von Python (im interaktiven Modus) berechnen lassen.
31 Sicherheit
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (7, 30)
z → (z * e) % m 01#19#20#05#18#09#24
07#13#20#05#06#03#18
Entschlüsselung:
privater Schlüssel(d, m) = (13, 30)
z → (z * d) % m 07#13#20#05#06#03#18
01#19#20#05#18#09#24
Bed.: z < m; ggT(e, m) = 1
Bed.: (e * d) % m = 1
Sicherheit:Die Sicherheit des multiplikativen Chiffrierverfahrens hängt davon ab, ob man zur Zahl e aus dem öffentlichen Schlüssel das modulare Inverse d bzgl. m bestimmen kann.
32
Bestimmung des modularen Inversen
Ein naiver Ansatz besteht darin, der Reihe nach alle Zahlen durchzuprobieren, bis man das gewünschte Ergebnis gefunden hat. def modInvNaiv(e, m): gefunden = False d = 1 while not gefunden: if (e*d)%m == 1: gefunden = True else: d = d + 1 return d
33 Aufgabe
Implementieren und testen Sie den Algorithmus in Python.
Testen Sie insbesondere den Algorithmus auch mit großen Zahlen.
Bsp.:
Bestimmen Sie das modulare Inverse vone = 775517959261225265313877628572204089387832653836742449bzgl. m = 1000010000100001000010000100001000010000100001000010000Als Ergebnis sollten Sied = 49erhalten.
Bestimmen Sie jetzt das modulare Inverse vond = 49bzgl.m = 1000010000100001000010000100001000010000100001000010000Als Ergebnis sollten Siee = 775517959261225265313877628572204089387832653836742449erhalten.
Was fällt hier auf?
34 Aufgabe
Benutzen Sie ein Programm mit zusätzlichen Ausgaben, um abzuschätzen, wie lange es wohl dauern wird, bis das Ergebnis der folgenden Berechnung feststeht:
e = 49m = 1000010000100001000010000100001000010000100001000010000modInvNaiv(e, m)
Messen sie hierzu (grob) die Zeit, die das Programm benötigt, um 10000000 Zahlen durchzuprobieren. Rechnen Sie dann hoch.
def modInvNaiv(e, m): gefunden = False d = 1 while not gefunden: if d % 10000000 == 0: print "Anzahl der Versuche: ", d if (e*d)%m == 1: gefunden = True else: d = d + 1 return d
35
Praktisch unbrauchbarer Algorithmus
Beispiel:
e = 49m = 1000010000100001000010000100001000010000100001000010000modInvNaiv(d, m)
Um 10 000 000 (= 107) Zahlen durchzuprobieren, benötigt ein Rechner derzeit etwas 10s.
Da das erwartete Ergebnis 775517959261225265313877628572204089387832653836742449 eine 54-stellige Zahl ist, wird der Rechner eine Zeit benötigen, die in der Größenordnung von 1047s liegt. Dies sind mehr als 1039 Jahre. Bedenkt man, dass das Universum ein Alter von etwa 1010 Jahre hat, dann zeigt sich, wie ungeeignet das naive Vorgehen ist.
Für größere Zahlen ist der naive Algorithmus unbrauchbar. Für die unten gezeigten Zahlen benötigt ein Rechner länger, als das Universum alt ist.
36 Vielfachsummensatz
Ein besseres Verfahren zur Bestimmung des modularen Inversen basiert auf folgendem Zusammenhang ("Vielfachsummensatz", "Lemma von Bézout", "Lemma von Bachet"):
Für je zwei natürliche Zahlen a und b gibt es ganze Zahlen x und y mit ggT(a,b)=x*a+y*b.
Beispiele:
a = 3; b = 4: ggT(3, 4) = 1 = (-1)*3 + 1*4
a = 6; b = 9: ggT(6, 9) = 3 = (-1)*6 + 1 * 9
a = 41; b = 192: ggT(41, 192) = 1 = 89*41 + (-19)*192
37
Erweiterter euklidischer Algorithmus
(1) 884 = 2*320 + 244 → 244 = 884 - 2*320 = (1*884 + 0*320) - 2*(1*320 + 0*884) = 1*884 - 2*320
(2) 320 = 1*244 + 76→ 76 = 320 - 1*244 = (0*884 + 1*320) - 1*(1*884 - 2*320)) = 3*320 - 1*884
(3) 244 = 3*76 + 16 → 16 = 244 - 3*76 = (1*884 - 2*320) - 3*(3*320 - 1*884) = 4*884 - 11*320
(4) 76 = 4*16 + 12→ 12 = 76 - 4*16 = (3*320 - 1*884) - 4*(4*884 - 11*320) = 47*320 - 17*884
(5) 16 = 1*12 + 4→ 4 = 16 - 1*12 = (4*884 - 11*320) - 1*(47*320 - 17*884) = 21*884 - 58*320
(6) 12 = 3*4 + 0
Gegeben: a = 884; b = 320Gesucht: ggT(a, b) = x*a + y*b
Ergebnis:
ggT(884, 320) = 4 = 21*884 + (- 58)*320
38 Aufgabe
Bestimmen Sie analog die Darstellung für a = 30 und b = 7.
Gegeben: a = 30; b = 7Gesucht: ggT(a, b) = x*a + y*b
39 Aufgabe
Das Struktogramm zeigt, wie der erweiterte euklidische Algorithmus mit Variablen und Kontrollstrukturen beschrieben werden kann. Im Folgenden ist ein Ablaufprotokoll für die Eingaben a = 884 und b = 320 skizziert. Machen Sie sich anhand dieses Ablauf-protokolls die Arbeitsweise des Algorithmus klar. Die unten gezeigten Berechnungsschritte sollten sich im Ablaufprotokoll widerspiegeln.
Bachet
Eingabe: a, b
aalt := a
amitte := b
xalt := 1
xmitte := 0
yalt := 0
ymitte := 1
SOLANGE amitte <> 0
q := aalt div amitte
aneu := aalt mod amitte
xneu := xalt - q*xmitte
yneu := yalt - q*ymitte
xalt := xmitte
xmitte := xneu
yalt := ymitte
ymitte := yneu
aalt := amitte
amitte := aneu
Ausgabe: aalt, xalt, yalt
(1) 884 = 2*320 + 244 → 244 = 884 - 2*320 = (1*884 + 0*320) - 2*(1*320 + 0*884) = 1*884 - 2*320
(2) 320 = 1*244 + 76→ 76 = 320 - 1*244 = (0*884 + 1*320) - 1*(1*884 - 2*320)) = 3*320 - 1*884
(3) 244 = 3*76 + 16 → 16 = 244 - 3*76 = (1*884 - 2*320) - 3*(3*320 - 1*884) = 4*884 - 11*320
(4) 76 = 4*16 + 12→ 12 = 76 - 4*16 = (3*320 - 1*884) - 4*(4*884 - 11*320) = 47*320 - 17*884
(5) 16 = 1*12 + 4→ 4 = 16 - 1*12 = (4*884 - 11*320) - 1*(47*320 - 17*884) = 21*884 - 58*320
(6) 12 = 3*4 + 0
40
Erweiterter euklidischer Algorithmus
Geg.: a = 884; b = 320; Ges.: ggT(a, b) = x*a + y*baalt:884 = a:884 amitte:320 = b:320xalt:1 = 1xmitte:0 = 0yalt:0 = 0ymitte:1 = 1 {aalt:884 = xalt:1 * a: 884 + yalt:0 * b:320; amitte:320 = xmitte:0 * a:884 + ymitte:1 * b:320}
(1) 884 = 2*320 + 244 → 244 = 884 - 2*320 = (1*884 + 0*320) - 2*(1*320 + 0*884) = 1*884 - 2*320
q: 2 = aalt: 884 / amitte: 320 aneu:244 = aalt:884 % amitte:320xneu:1 = xalt:1 - xmitte:0 * q:2yneu:-2 = yalt:0 - ymitte:1 * q:2xalt:0 = xmitte:0xmitte:1 = xneu:1yalt:1 = ymitte:1ymitte:-2 = yneu:-2aalt:320 = amitte:320amitte:244 = aneu:244{aalt:320 = xalt:0 * a:884 + yalt:1 * b:320; amitte:244 = xmitte:1 * a:884 + ymitte:-2 * b:320}
Bachet
Eingabe: a, b
aalt := a
amitte := b
xalt := 1
xmitte := 0
yalt := 0
ymitte := 1
SOLANGE amitte <> 0
q := aalt div amitte
aneu := aalt mod amitte
xneu := xalt - q*xmitte
yneu := yalt - q*ymitte
xalt := xmitte
xmitte := xneu
yalt := ymitte
ymitte := yneu
aalt := amitte
amitte := aneu
Ausgabe: aalt, xalt, yalt
41
Erweiterter euklidischer Algorithmus
{aalt:320 = xalt:0 * a:884 + yalt:1 * b:320; amitte:244 = xmitte:1 * a:884 + ymitte:-2 * b:320}
(2) 320 = 1*244 + 76 → 76 = 320 - 1*244 = (0*884 + 1*320) - 1*(1*884 - 2*320)) = 3*320 - 1*884
q: 1 = aalt: 320 / amitte: 244 aneu:76 = aalt:320 % amitte:244xneu:-1 = xalt:0 - xmitte:1 * q:1yneu:3 = yalt:1 - ymitte:-2 * q:1xalt:1 = xmitte:1xmitte:-1 = xneu:-1yalt:-2 = ymitte:-2ymitte:3 = yneu:3aalt:244 = amitte:244amitte:76 = aneu:76{aalt:244 = xalt:1 * a:884 + yalt:-2 * b:320; amitte:76 = xmitte:-1 * a:884 + ymitte:3 * b:320}
Bachet
Eingabe: a, b
aalt := a
amitte := b
xalt := 1
xmitte := 0
yalt := 0
ymitte := 1
SOLANGE amitte <> 0
q := aalt div amitte
aneu := aalt mod amitte
xneu := xalt - q*xmitte
yneu := yalt - q*ymitte
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)*192Also: (89*41) % 192 = (1 - (-19)*192) % 192 = (1 + 19*192) % 192 = 1Also: 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*192Also: 1 + 192*17 = (-79+192)*17 + 7*192Also: 1 + 192*17 - 7*192 = 113*17Also: (113*17) % 192 = (1 + 10*192) % 192 = 1Also: modInv(17, 192) = 113
Beispiel 3: modInv(320, 884)Beachte: ggT(320, 884) = 4 > 1. Es gibt kein modulares Inverses von 320 bzg. 884.
44 Aufgabe
Die Datei "ModularesInverses.py" zeigt u. a., wie man aus den Ergebnissen des erweiterten euklidischen Algorithmus das modulare Inverse bestimmen kann.
Testen Sie die Implementierung insbesondere für große Zahlen:
e = 49m = 1000010000100001000010000100001000010000100001000010000modInv(d, m)
Welche Konsequenzen ergeben sich hieraus für die Sicherheit des Chiffrierverfahrens mit modularer Multiplikation?
45 Sicherheit
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (7, 30)
z → (z * e) % m 01#19#20#05#18#09#24
07#13#20#05#06#03#18
Entschlüsselung:
privater Schlüssel(d, m) = (13, 30)
z → (z * d) % m 07#13#20#05#06#03#18
01#19#20#05#18#09#24
Bed.: z < m; ggT(e, m) = 1
Bed.: (e * d) % m = 1
Sicherheit: Das "multiplikative" Chiffrierverfahren ist nicht sicher, da man aus dem öffentlichen Schlüssel mit Hilfe des erweiterten euklidischen Algorithmus den privaten Schlüssel recht schnell bestimmen kann.
46 Sicherheit
Sicherheit: Das "multiplikative" Chiffrierverfahren ist nicht sicher, da man aus dem öffentlichen Schlüssel mit Hilfe des erweiterten euklidischen Algorithmus den privaten Schlüssel recht schnell bestimmen kann.
Die "Unsicherheit" basiert hier also darauf, dass man ein schnelles Verfahren gefunden hat, um das modulare Inverse einer Zahl zu bestimmen.
47 Teil 4
Verschlüsseln mit modularem Potenzieren
48
Verschlüsseln d. modulares Rechnen
modulares Addieren
Verschlüsselung mit öffentl. Schlüssel (e, m)
z → (z * e) % m
z → (z * d) % m
modulares Multiplizieren
Entschlüsselung mit privat. Schlüssel (d, m)
Verschlüsselung mit öffentl. Schlüssel (e, m)
z → (z + e) % m
z → (z + d) % m
Entschlüsselung mit privat. Schlüssel (d, m)
Verschlüsselung mit öffentl. Schlüssel (e, m)
z → (z ** e) % m
z → (z ** d) % m
Entschlüsselung mit privat. Schlüssel (d, m)
modulares Potenzieren
49
Verschlüsseln d. modulares Potenzieren
Codierung:
Code: A → 1Blocklänge: 1
b → z A#S#T#E#R#I#X
01#19#20#05#18#09#24
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (13, 77)
z → (z ** e) % m 01#19#20#05#18#09#24
01#61#69#26#46#58#52
Entschlüsselung:
privater Schlüssel(d, m) = (37, 77)
z → (z ** d) % m 01#61#69#26#46#58#52
01#19#20#05#18#09#24
Decodierung
Code: A → 1Blocklänge: 1
01#19#20#05#18#09#24
A#S#T#E#R#I#X
eindeutige Codierung von Zeichenblöcken
Bed.: z < m
Bed.: (e * d) % φ(m) = 1
z → b
Decodierung als Um-kehrung der Codierung
50 Schlüsselerzeugung
Vorbereitung:
Wähle zwei verschiedene Primzahlen p und q.
Berechne m = p*q.
Berechne φ(m) = (p-1)*(q-1).
Wähle eine Zahl e, die teilerfremd zu φ(m) ist.
Berechne d so, dass (e*d) % φ(m) = 1 ist.
("Vernichte p, q, φ(m).")
Schlüssel:
Der öffentliche Schlüssel ist (e, m).
Der private Schlüssel ist (d, m).
Beispiel:
p = 7; q = 11
m = 77
φ(m) = 60
z. B. e = 13
d = 37
(13, 77)
(37, 77)
51 Aufgabe
Codierung:
Code: A → 1Blocklänge: 1
b → z A#S#T#E#R#I#X
01#19#20#05#18#09#24
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (13, 77)
z → (z ** e) % m 01#19#20#05#18#09#24
Entschlüsselung:
privater Schlüssel(d, m) = (37, 77)
z → (z ** d) % m
Decodierung
Code: A → 1Blocklänge: 1
eindeutige Codierung von Zeichenblöcken
Bed.: z < m
Bed.: (e * d) % φ(m) = 1
z → b
Decodierung als Um-kehrung der Codierung
52 Aufgabe
Codierung:
Code: A → 1Blocklänge: 1
b → z
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (7, 55)
z → (z ** e) % m
Entschlüsselung:
privater Schlüssel(d, m) =
z → (z ** d) % m 28#25#02#25#04#07
Decodierung
Code: A → 1Blocklänge: 1
eindeutige Codierung von Zeichenblöcken
Bed.: z < m
Bed.: (e * d) % φ(m) = 1
z → b
Decodierung als Um-kehrung der Codierung
53 Implementierung
Zur Implementierung des vorgestellten Chiffrier-verfahrens (in Python) werden die einzelnen Operationen mit Hilfe von Funktionen dargestellt.
def zahl(c):def zeichen(z):def zerlegen(wort, blocklaenge):def codierenBlock(wort):def codierenBlockListe(blockListe):def codieren(wort, blocklaenge):def decodierenZahl(zahl):def decodierenZahlListe(zahlenListe):def zusammenfuegen(liste):def decodieren(zahlenListe):def verschluesselnZahl(zahl, schluessel):def verschluesseln(zahlenListe,
Codierung:
Code: A → 1Blocklänge: 1
b → z
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (13, 77)
z → (z ** e) % m
Entschlüsselung:
privater Schlüssel(d, m) = (37, 77)
z → (z ** d) % m
Decodierung
Code: A → 1Blocklänge: 1
eindeutige Codierung von Zeichenblöcken
Bed.: z < m
Bed.: (e * d) % φ(m) = 1
z → b
Decodierung als Um-kehrung der Codierung
54 Aufgabe
Ändern Sie die Implementierung des Chiffriersystems mit modularem Addieren / Multiplizieren geeignet ab und testen Sie das neue Chiffriersystem, das auf modularem Potenzieren basiert.
Hinweis: Benutzen Sie zum schnellen modularen Potenzieren die folgende Funktion modpot:
def modpot(x, y, n): pot = 1 while y > 0: if y % 2 == 1: pot = (pot * x) % n y = y - 1 else: x = (x * x) % n y = y / 2 return pot
55 Korrektheit des RSA-Verfahrens
Behauptung: Seien (e, m) und (d, m) ein öffentlicher und privater Schlüssel zum RSA-Verfahren. Sei z eine natürliche Zahl mit z < m. Dann gilt: (ze % m)d % m = z
Verschlüsselung:
öffentlicher Schlüssel(e, m) = (13, 77)
z → (z ** e) % m 01#19#20#05#18#09#24
01#61#69#26#46#58#52
Entschlüsselung:
privater Schlüssel(d, m) = (37, 77)
z → (z ** d) % m 01#61#69#26#46#58#52
01#19#20#05#18#09#24
Bed.: z < m
Bed.: (e * d) % φ(m) = 1
56 Korrektheit des RSA-Verfahrens
Beweis: Nach den Vorgaben zur Schlüsselerzeugung gilt:m = pq; (m) = (p-1)(q-1); (ed) % (m) = 1.
Da (ed) % (m) = 1, gibt es eine natürliche Zahl k mit ed = k(m) + 1.
Nach dem Satz (s. u.) gilt dann (zk(m) + 1) % m = z.
Hiermit folgt jetzt:
(ze % m)d % m = (ze)d % m = (zed) % m = (zk(m) + 1) % m = z
Behauptung: Seien (e, m) und (d, m) ein öffentlicher und privater Schlüssel zum RSA-Verfahren. Sei z eine natürliche Zahl mit z < m. Dann gilt: (ze % m)d % m = z
SatzSeien p und q Primzahlen. Dann gilt für alle natürlichen Zahlen z und alle natürlichen Zahlen k: zk(p-1)(q-1)+1 % (pq) = z
57 Aufgabe
Überprüfen Sie die Aussage des Satzes: Seien p und q Primzahlen. Dann gilt für alle natürlichen Zahlen z und alle natürlichen Zahlen k: zk(p-1)(q-1)+1 % (pq) = z
Setzen Sie hierzu für die p, q, z und k konkrete Werte einsetzen und berechnen Sie (mit Python) den Ausdruck zk(p-1)(q-1)+1 % (pq).
58 Aufgabe
Die Verschlüsselung durch modulares Potenzieren ist nur dann geeignet, wenn man schnell modulare Potenzen bestimmen kann. Testen und analysieren Sie den folgenden Algorithmus:
def modpot(x, y, n): pot = 1 while y > 0: if y % 2 == 1: pot = (pot * x) % n y = y - 1 else: x = (x * x) % n y = y / 2 return pot
59 Sicherheit des RSA-Verfahrens
Bedingung:Die Sicherheit hängt davon ab, ob man in angemessener Zeit den Bestand-teil m des öffentlichen Schlüssels in seine Primfaktoren zerlegen kann.Vorbereitung:
Wähle zwei verschiedene Primzahlen p und q.
Berechne m = p*q.
Berechne φ(m) = (p-1)*(q-1).
Wähle eine Zahl e, die teilerfremd zu φ(m) ist.
Berechne d so, dass (e*d) % φ(m) = 1 ist.
("Vernichte p, q, φ(m).")
Schlüssel:
Der öffentliche Schlüssel ist (e, m).
Der private Schlüssel ist (d, m).
Beispiel:
p = 7; q = 11
m = 77
φ(m) = 60
z. B. e = 13
d = 37
(13, 77)
(37, 77)
60 Sicherheit des RSA-Verfahrens
Sicherheit:Bis heute gibt es keine schnellen Algorithmen, um eine Zahl in ihre Primfaktoren zu zerlegen. Das RSA-Verfahren ist bei groß gewählten Primzahlen recht sicher, da man aus dem öffentlichen Schlüssel den privaten Schlüssel bisher nicht in angemessener Zeit bestimmen kann.
61 Aufgabe
Mit dem folgenden Programm kann man eine Primfaktorzerlegung bei natürlichen Zahlen durchführen.
def primfaktoren(n): from math import sqrt liste = [] for t in [2, 3]: while n % t == 0: liste.append(t) n = n / t t = 5 d = 2 w = round(sqrt(n)) while t <= w: while n % t == 0: liste.append(t) n = n / t t = t + d d = 6 - d if n > 1: liste.append(n) return liste
Testen Sie das Programm.
Testen Sie auch das Verhalten bei großen Eingabezahlen.
62 Aufgabe
Multiplizieren Sie zwei Primzahlen p und q und zerlegen Sie anschließend das Produkt m = p*q wieder in seine Primfaktoren. Erhöhen Sie schrittweise die Größe von p und q. Zur Erzeugung von Primzahlen können Sie die sehr naiv implementierte Funktion "naechstgroesserePrimzahl(n)" (oder auch "naechstKleinerePrimzahl(n)") benutzen (siehe "SystematischePrimzahlZerlegung.py"). Protokollieren Sie die Messergebnisse und versuchen Sie herauszufinden, wie die Rechenzeit in Abhängigkeit der Größe der Ausgangsprimzahlen wächst. Gehen Sie bei der Erhöhung von p und q systematisch vor. Erzeugen Sie z. B. Primzahlen, die in der Nähe von 30..0 bzw 40..0 liegen. Die Zahlen 30..0 sollen beginnend bei 30 jeweils um eine Stelle wachsen, analog 40..0 = 40, 400, 4000, .. . Die Zahlen n wachsen dann jeweils um zwei Stellen (siehe nächste Folie).
63 Aufgabe
p q n StellenZeit
31 41 1271 4
307 401 123107 6
3001 4001 12007001 8
64 Aufgabe
Gibt es eigentlich genug Primzahlen in der gewünschten Größenordnung? Untersuchen Sie, wie viele Primzahlen es bis zu einer gegebenen Zahl x gibt.
65 Informationen
Gibt es genug Primzahlen in der gewünschten Größenordnung?
Für eine gegebene Zahl x gibt es ungefähr x/ln(x) Primzahlen, die kleiner als x sind.
Man wählt heute Primzahlen, die mit mindestens 512 Bit dargestellt werden. Das sind Zahlen in der Größenordnung 2512. Da 2512/ln(2512) etwa die Größenordnung 2500 hat (das ist eine Zahl mit 150 Dezimalstellen), sollten genügend Primzahlen für die Verschlüsselung zur Verfügung stehen.
Wie bestimmt man große Primzahlen?
Zur Bestimmung großer Primzahlen geht man wie folgt vor. Man erzeugt eine Zufallszahl im gewünschten Größenbereich und testet, ob es sich um eine Primzahl handelt. Solche Primzahltests kann man sehr schnell mit geeigneten Verfahren durchführen. Da es sehr viele Primzahlen im gewünschten Bereich gibt (s. o.), muss man nicht in der Regel allzu viele Zahlen testen.
66 Fazit
Algorithmen spielen bei der Entwicklung von Chiffriersystemen eine große Rolle.
Im Fall des RSA-Verfahrens benötigt man einerseits gute Algorithmen, um das Verfahren überhaupt effizient durchführen zu können (z. B. schnell ein modulares Inverses bestimmen; schnell eine modulare Potenz bestimmen).
Andererseits ist das Verfahren so angelegt, dass bestimmte Operation mit den bisher bekannten Algorithmen mit vertretbarem Rechenaufwand nicht durchgeführt werden können.
67 Literaturhinweise
Folgende Materialien wurden hier benutzt:
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
K. Merkert: http://www.hsg-kl.de/faecher/inf/krypto/rsa/index.php