Post on 05-Apr-2015
transcript
Kapitel 4
Kryptographie
Kapitel 4
Kryptographie
Kapitel 4 © Beutelspacher
November 2004Seite 2
InhaltInhalt
4.1 Was ist Kryptographie?
4.2 Monoalphabetische Verfahren: Cäsar, ...
4.3 Polyalphabetische Verfahren: Vignère, ...
4.4 Modernste Kryptographie: Das Problem des Schlüssels
4.1 Was ist Kryptographie?
4.2 Monoalphabetische Verfahren: Cäsar, ...
4.3 Polyalphabetische Verfahren: Vignère, ...
4.4 Modernste Kryptographie: Das Problem des Schlüssels
Kapitel 4 © Beutelspacher
November 2004Seite 3
4.1 Kryptologie = Kryptographie4.1 Kryptologie = Kryptographie
• Geheimhaltung: Garantie, dass eine Nachricht
von nicht autorisierten Personen nicht gelesen werden kann.
• Authentifikation: Garantie, dass eine Nachricht
von nicht autorisierten Personen nicht verändert werden kann.
• Geheimhaltung: Garantie, dass eine Nachricht
von nicht autorisierten Personen nicht gelesen werden kann.
• Authentifikation: Garantie, dass eine Nachricht
von nicht autorisierten Personen nicht verändert werden kann.
Kapitel 4 © Beutelspacher
November 2004Seite 4
Kryptologie bietet SicherheitKryptologie bietet Sicherheit
• Verschlüsselung
diplomatischer Dienst, Militär, Mobilfunk, Pay-TV, ...
• Authentifikation von Daten
e-commerce, Homebanking, electronic cash, Computerviren, ...
• Authentifikation von Personen
Geldautomat, Rechnerzugang, Telefonkarten, Wegfahrsperre bei
Kfzs, ...
• Verschlüsselung
diplomatischer Dienst, Militär, Mobilfunk, Pay-TV, ...
• Authentifikation von Daten
e-commerce, Homebanking, electronic cash, Computerviren, ...
• Authentifikation von Personen
Geldautomat, Rechnerzugang, Telefonkarten, Wegfahrsperre bei
Kfzs, ...
Kapitel 4 © Beutelspacher
November 2004Seite 5
Sicherheit ja ! Aber wozu Kryptologie?Sicherheit ja ! Aber wozu Kryptologie?
Kryptologie bietet Verfahren,
die (im Prinzip) beweisbar sicher sind.
Kryptologie bietet Verfahren,
die (im Prinzip) beweisbar sicher sind.
Kryptologische Mechanismen
können (im Prinzip)
beliebig sicher gemacht werden.
Kryptologische Mechanismen
können (im Prinzip)
beliebig sicher gemacht werden.
Kapitel 4 © Beutelspacher
November 2004Seite 6
Der AngreiferDer Angreifer
Kann man verhindern, dass ein Angreifer die Nachricht versteht?Kann man verhindern, dass ein Angreifer die Nachricht versteht?
Kapitel 4 © Beutelspacher
November 2004Seite 7
Drei GeheimtexteDrei Geheimtexte
Dodasos isostot unonkoknonackokbobaror
U R J Z J K L E B E R T A S R I
T X N P U T G Q W M S L O D B P
Dodasos isostot unonkoknonackokbobaror
U R J Z J K L E B E R T A S R I
T X N P U T G Q W M S L O D B P
Kapitel 4 © Beutelspacher
November 2004Seite 8
Geschichte Geschichte
Antike: die spartanische Skytala, der Cäsar-Code
Mittelalter: Leon Battista Alberti, Trithemius, Vigenère
Das Zeitalter der Chiffriermaschinen: Wheatstone, Jefferson,
Kasiski, Friedman, Scherbius, Hagelin, ...
Die mathematische Ära: Shannon, Diffie, Hellman, Shamir
Antike: die spartanische Skytala, der Cäsar-Code
Mittelalter: Leon Battista Alberti, Trithemius, Vigenère
Das Zeitalter der Chiffriermaschinen: Wheatstone, Jefferson,
Kasiski, Friedman, Scherbius, Hagelin, ...
Die mathematische Ära: Shannon, Diffie, Hellman, Shamir
Kapitel 4 © Beutelspacher
November 2004Seite 9
4.2 Die Cäsar-Verschlüsselung4.2 Die Cäsar-Verschlüsselung
Man schreibt das normale Alphabet (Klartextalphabet = KT) auf und
darunter nochmals das normale Alphabet (Geheimtextalphabet = GT),
aber um einige Stellen verschoben.
Beispiel:
KT: 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
GT: W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
Verschlüsselung: Ein Klartextbuchstabe wird durch den darunter-
stehenden Geheimtextbuchstaben ersetzt.
Beispiel: Aus MATHE wird IWPDA.
Man schreibt das normale Alphabet (Klartextalphabet = KT) auf und
darunter nochmals das normale Alphabet (Geheimtextalphabet = GT),
aber um einige Stellen verschoben.
Beispiel:
KT: 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
GT: W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
Verschlüsselung: Ein Klartextbuchstabe wird durch den darunter-
stehenden Geheimtextbuchstaben ersetzt.
Beispiel: Aus MATHE wird IWPDA.
Kapitel 4 © Beutelspacher
November 2004Seite 10
Cäsar-ScheibenCäsar-Scheiben
Etwa um 1500 wurden “Verschlüsselungsmaschinen” erfunden, z.B.
die Cäsar-Scheiben:
Zwei runde Scheiben sind in ihrem
Mittelpunkt drehbar gegeneinander
befestigt. Auf jeder der Scheiben ist
das Alphabet in normaler Reihenfolge
zu sehen.
Verschlüsselt wird, indem von außen nach innen gelesen wird.
Entschlüsselt wird, indem man von innen nach außen liest.
Etwa um 1500 wurden “Verschlüsselungsmaschinen” erfunden, z.B.
die Cäsar-Scheiben:
Zwei runde Scheiben sind in ihrem
Mittelpunkt drehbar gegeneinander
befestigt. Auf jeder der Scheiben ist
das Alphabet in normaler Reihenfolge
zu sehen.
Verschlüsselt wird, indem von außen nach innen gelesen wird.
Entschlüsselt wird, indem man von innen nach außen liest.
Kapitel 4 © Beutelspacher
November 2004Seite 11
VerschlüsselungsschemaVerschlüsselungsschema
Sender und Empfänger brauchen einen geheimen Schlüssel.Sender und Empfänger brauchen einen geheimen Schlüssel.
Klartext:Lieber Herr ...
Klartext:Lieber Herr ...
Geheimtext:XYRTRE WREE...
Geheimtext:XYRTRE WREE...
Klartext:Lieber Herr ...
Klartext:Lieber Herr ...wird
verschlüsseltwird
entschlüsselt
Der Angreifer will den Geheimtext ohne Schlüssel entschlüsseln!Der Angreifer will den Geheimtext ohne Schlüssel entschlüsseln!
Kapitel 4 © Beutelspacher
November 2004Seite 13
Mechanismus “Verschlüsselung”Mechanismus “Verschlüsselung”
Der Schlüssel K ist das gemeinsame Geheimnis
von Sender und Empfänger.
Der Schlüssel K ist das gemeinsame Geheimnis
von Sender und Empfänger.
Verschlüsselungc = fK(m)
c
Menge vonSchlüs seln
Menge vonNachrichten m
K K
Entschlüsselungm = fK
-1(c)Klartext
Geheimtext
m
Klartext
Kapitel 4 © Beutelspacher
November 2004Seite 14
Kryptoanalyse der Cäsar-VerschlüsselungKryptoanalyse der Cäsar-Verschlüsselung
• Ausprobieren aller Möglichkeiten
Da nur 26 Schlüssel zu testen sind, ist dies möglich.
• Statistische Analyse
Im Deutschen ist E der mit Abstand häufigste Buchstabe (ca. 20%).
Zähle die Buchstaben im Geheimtext.
Der häufigste entspricht dem Klartext-E.
Damit liegt der Schlüssel fest, und man kann entschlüsseln.
• Ausprobieren aller Möglichkeiten
Da nur 26 Schlüssel zu testen sind, ist dies möglich.
• Statistische Analyse
Im Deutschen ist E der mit Abstand häufigste Buchstabe (ca. 20%).
Zähle die Buchstaben im Geheimtext.
Der häufigste entspricht dem Klartext-E.
Damit liegt der Schlüssel fest, und man kann entschlüsseln.
Kapitel 4 © Beutelspacher
November 2004Seite 15
Cäsar knackenCäsar knacken
U R J Z J K L E B E R T A S R IV S K A K L M F C F S U B T S JW T L B L M N G D G T V C U T KX U M C M N O J E H UWD V U LY V N D N O P I F I V X EWV MZ WO E O P Q J G J WY F XWNA X P F P Q R K H K X Z G Y X OB Y Q G Q R S L I L Y A H Z Y PC Z R H R S T M J M Z B I A Z QD A S I S T U N K N A C K B A RE B T J T U V O L O B D L C B SF CU K U VWP M P C E M D C TG DV L VWX Q N Q D F N E D U
U R J Z J K L E B E R T A S R IV S K A K L M F C F S U B T S JW T L B L M N G D G T V C U T KX U M C M N O J E H UWD V U LY V N D N O P I F I V X EWV MZ WO E O P Q J G J WY F XWNA X P F P Q R K H K X Z G Y X OB Y Q G Q R S L I L Y A H Z Y PC Z R H R S T M J M Z B I A Z QD A S I S T U N K N A C K B A RE B T J T U V O L O B D L C B SF CU K U VWP M P C E M D C TG DV L VWX Q N Q D F N E D U
H EWMWX Y R O R E G N F E VI F X N X Y T S P S F H O G F WJ G Y O Y Z A T Q T G I P ‘HG XK H Z P Z A B U R U H J Q I H YL I A Q A B C V S V I K R J I ZM J B R B C DW T W J L S K J AN K C S C D E X U X K M T L K BO L D T D E F Y V Y L N U M L CP M E U E F G Z W Z MO V N M DQ N F V F G H A X A N PWO N ER O GWG H I B Y B O Q X P O FS P H X H I J C Z C P R Y Q P GT Q I Y I J K D A D Q S Z R Q H
H EWMWX Y R O R E G N F E VI F X N X Y T S P S F H O G F WJ G Y O Y Z A T Q T G I P ‘HG XK H Z P Z A B U R U H J Q I H YL I A Q A B C V S V I K R J I ZM J B R B C DW T W J L S K J AN K C S C D E X U X K M T L K BO L D T D E F Y V Y L N U M L CP M E U E F G Z W Z MO V N M DQ N F V F G H A X A N PWO N ER O GWG H I B Y B O Q X P O FS P H X H I J C Z C P R Y Q P GT Q I Y I J K D A D Q S Z R Q H
Kapitel 4 © Beutelspacher
November 2004Seite 16
Kardinal, Pastor und Admiral, als Führungstrio null und
nichtig und darum völlig abhängig vom Ami-Trust, tat durch
Radionachricht und Anschlag kund, dass Nahrungsnot und
damit Tod aufs Volk zukommt. Zunächst tat man das als
Falschinformation ab. Das ist Propagandagift, sagt man. Doch
bald schon ward spürbar, was man ursprünglich nicht glaubt.
Das Volk griff zum Stock, zum Dolch. “Gib uns das täglich
Brot”, hallts durch Land und “pfui auf das Patronat, auf
Ordnung, Macht und Staat.” ...
(Georges Perec, Anton Voyls Fortgang. Zweitausendeins 1986.)
Kardinal, Pastor und Admiral, als Führungstrio null und
nichtig und darum völlig abhängig vom Ami-Trust, tat durch
Radionachricht und Anschlag kund, dass Nahrungsnot und
damit Tod aufs Volk zukommt. Zunächst tat man das als
Falschinformation ab. Das ist Propagandagift, sagt man. Doch
bald schon ward spürbar, was man ursprünglich nicht glaubt.
Das Volk griff zum Stock, zum Dolch. “Gib uns das täglich
Brot”, hallts durch Land und “pfui auf das Patronat, auf
Ordnung, Macht und Staat.” ...
(Georges Perec, Anton Voyls Fortgang. Zweitausendeins 1986.)
Kapitel 4 © Beutelspacher
November 2004Seite 17
Monoalphabetische VerschlüsselungenMonoalphabetische Verschlüsselungen
Ein Verschlüsselungsalgorithmus heisst monoalphabetisch (griech:
nur ein Alphabet), falls jeder Klartextbuchstabe immer in den gleichen
Geheimtextbuchstaben verschlüsselt wird.
Unter das Klartextalphabet schreibt man ein beliebig durcheinander-
gewürfeltes Geheimtextalphabet.
Beispiel:
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
F G W E V H D I C U A J T B S Q R K Z L M Y N O P X
Verschlüsselung: Von oben nach unten, aus MATHE wird TFLIV.
Ein Verschlüsselungsalgorithmus heisst monoalphabetisch (griech:
nur ein Alphabet), falls jeder Klartextbuchstabe immer in den gleichen
Geheimtextbuchstaben verschlüsselt wird.
Unter das Klartextalphabet schreibt man ein beliebig durcheinander-
gewürfeltes Geheimtextalphabet.
Beispiel:
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
F G W E V H D I C U A J T B S Q R K Z L M Y N O P X
Verschlüsselung: Von oben nach unten, aus MATHE wird TFLIV.
Kapitel 4 © Beutelspacher
November 2004Seite 18
Schlüsselwort-ChiffrierungSchlüsselwort-Chiffrierung
Unter das Klartextalphabet schreibt man das Geheimtextalphabet;
dieses wird wie folgt gebildet:
Sender und Empfänger wählen ein Wort (Beispiel: MATHEMATIK).
Dieses bildet den Anfang des Geheimtextalphabets (wobei doppelt
auftretende Buchstaben beim zweiten Mal usw. entfallen). Dann
werden die restlichen Buchstaben des Alphabets aufgefüllt:
Beispiel:
KT: 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
GT: M A T H E I K B C D F G J L N O P Q R S U V W X Y Z
Unter das Klartextalphabet schreibt man das Geheimtextalphabet;
dieses wird wie folgt gebildet:
Sender und Empfänger wählen ein Wort (Beispiel: MATHEMATIK).
Dieses bildet den Anfang des Geheimtextalphabets (wobei doppelt
auftretende Buchstaben beim zweiten Mal usw. entfallen). Dann
werden die restlichen Buchstaben des Alphabets aufgefüllt:
Beispiel:
KT: 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
GT: M A T H E I K B C D F G J L N O P Q R S U V W X Y Z
Kapitel 4 © Beutelspacher
November 2004Seite 19
Wie sicher sind monoalphabetische Verschlüsselungen?Wie sicher sind monoalphabetische Verschlüsselungen?
Es gibt genau 26! Permutationen, also 26! Möglichkeiten für ein
Geheimtextalphabet. Da
26! = 403 291 461 126 605 635 584 000 000
ist, gibt es eine riesige Zahl von Schlüsseln.
Trotzdem haben monoalphabetischen Verschlüsselungen Nachteile:
1. Der Schlüssel ist die Folge der 26 Buchstaben des Geheimtext-
alphabets. Eine solche Folge ist schwer zu merken.
2. Sie sind relativ leicht zu knacken (trotz der großen Schlüsselzahl).‘
Statistische Analyse: Der Angreifer entschlüsselt die häufigsten
Buchstaben (E, N, ...) und rät die restlichen.
Es gibt genau 26! Permutationen, also 26! Möglichkeiten für ein
Geheimtextalphabet. Da
26! = 403 291 461 126 605 635 584 000 000
ist, gibt es eine riesige Zahl von Schlüsseln.
Trotzdem haben monoalphabetischen Verschlüsselungen Nachteile:
1. Der Schlüssel ist die Folge der 26 Buchstaben des Geheimtext-
alphabets. Eine solche Folge ist schwer zu merken.
2. Sie sind relativ leicht zu knacken (trotz der großen Schlüsselzahl).‘
Statistische Analyse: Der Angreifer entschlüsselt die häufigsten
Buchstaben (E, N, ...) und rät die restlichen.
Kapitel 4 © Beutelspacher
November 2004Seite 20
4.3 Polyalphabetische Verschlüsselungen4.3 Polyalphabetische Verschlüsselungen
• Man müsste ...
so verschlüsseln können,
... dass die Häufigkeiten der Buchstaben vertuscht werden.
• Also müsste man ...
so verschlüsseln,
... dass sich das Geheimtextalphabet von Buchstabe zu
Buchstabe ändert.
• Aber da alles müsste so gehen, ...
dass der Empfänger des Geheimtexts
diesen wieder entschlüsseln kann.
• Man müsste ...
so verschlüsseln können,
... dass die Häufigkeiten der Buchstaben vertuscht werden.
• Also müsste man ...
so verschlüsseln,
... dass sich das Geheimtextalphabet von Buchstabe zu
Buchstabe ändert.
• Aber da alles müsste so gehen, ...
dass der Empfänger des Geheimtexts
diesen wieder entschlüsseln kann.
Kapitel 4 © Beutelspacher
November 2004Seite 21
Polyalphabetische VerschlüsselungenPolyalphabetische Verschlüsselungen
Idee der polyalphabetischen Verschlüsselung:
Verwende bei jedem Buchstaben ein neues Alphabet! D.h.: Verwende
einen Cäsar-Code, aber wechsle nach jedem Buchstaben die
Einstellung der Scheiben.
Diese Idee entstand um 1500 und wurde u.a. von Alberti, Porta,
Trithemius und Vigenère weiterentwickelt.
Idee der polyalphabetischen Verschlüsselung:
Verwende bei jedem Buchstaben ein neues Alphabet! D.h.: Verwende
einen Cäsar-Code, aber wechsle nach jedem Buchstaben die
Einstellung der Scheiben.
Diese Idee entstand um 1500 und wurde u.a. von Alberti, Porta,
Trithemius und Vigenère weiterentwickelt.
Kapitel 4 © Beutelspacher
November 2004Seite 22
Algorithmus und SchlüsselAlgorithmus und Schlüssel
Der Algorithmus ist die allgemeine Vorschrift, wie man ver- und
entschlüsselt. Der Algorithmus ist i.a. öffentlich bekannt (auch dem
Angreifer).
Beispiel: Beim Cäsar-Code repräsentieren die Cäsar-Scheiben den
Algorithmus.
Der Schlüssel gibt die konkrete Verschlüsselungsvorschrift an. Der
Schlüssel ist das exklusive Geheimnis von Sender und Empfänger.
Beispiel: Beim Cäsar-Code ist der Schlüssel die Einstellung der
Scheiben (oder der Buchstabe, in den A verschlüsselt wird, oder der
Buchstabe, in den E verschlüsselt wird, oder ...).
Der Algorithmus ist die allgemeine Vorschrift, wie man ver- und
entschlüsselt. Der Algorithmus ist i.a. öffentlich bekannt (auch dem
Angreifer).
Beispiel: Beim Cäsar-Code repräsentieren die Cäsar-Scheiben den
Algorithmus.
Der Schlüssel gibt die konkrete Verschlüsselungsvorschrift an. Der
Schlüssel ist das exklusive Geheimnis von Sender und Empfänger.
Beispiel: Beim Cäsar-Code ist der Schlüssel die Einstellung der
Scheiben (oder der Buchstabe, in den A verschlüsselt wird, oder der
Buchstabe, in den E verschlüsselt wird, oder ...).
Kapitel 4 © Beutelspacher
November 2004Seite 23
Vigenère-QuadratVigenère-Quadrat
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 ZB C D E F G H I J K L M N O P Q R S T U V W X Y Z AC 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 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 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 D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J K L M N O P Q R S T U V W X Y Z A B C D E F G H IK L M N O P Q R S T U V W X Y Z A B C D E F G H I J L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z 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
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 ZB C D E F G H I J K L M N O P Q R S T U V W X Y Z AC 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 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 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 D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J K L M N O P Q R S T U V W X Y Z A B C D E F G H IK L M N O P Q R S T U V W X Y Z A B C D E F G H I J L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z 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
Kapitel 4 © Beutelspacher
November 2004Seite 24
Vigenère-VerschlüsselungVigenère-Verschlüsselung
Schlüsselwort: M A T H E M A T H E M A T H E M
Klartext: D A S I S T U N K N A C K B A R
Geheimtext: P A L P W F U G R R M C D I E Y
Schlüsselwort: M A T H E M A T H E M A T H E M
Klartext: D A S I S T U N K N A C K B A R
Geheimtext: P A L P W F U G R R M C D I E Y
Anders ausgedrückt:
Jeder Buchstabe wird in eine Zahl übersetzt: A = 0, B = 1, ..., Z = 25.
Dann wird Klartext- und Schlüsselbuchstabe modulo 26 addiert.
Das Ergebnis ist der Geheimtextbuchstabe.
Anders ausgedrückt:
Jeder Buchstabe wird in eine Zahl übersetzt: A = 0, B = 1, ..., Z = 25.
Dann wird Klartext- und Schlüsselbuchstabe modulo 26 addiert.
Das Ergebnis ist der Geheimtextbuchstabe.
Kapitel 4 © Beutelspacher
November 2004Seite 25
RotormaschinenRotormaschinen
• Idee: Durch Kopplung verschiedener „Rotoren“ entsteht ein
guter Algorithmus
• Komplexe Permutationen (Enigma)
• Große Periode (M-209)
• Idee: Durch Kopplung verschiedener „Rotoren“ entsteht ein
guter Algorithmus
• Komplexe Permutationen (Enigma)
• Große Periode (M-209)
Kapitel 4 © Beutelspacher
November 2004Seite 26
Die EnigmaDie Enigma
Die deutsche Wehrmacht benutzt im 2. Weltkrieg
die Chiffriermaschine Enigma (griech.: Rätsel).
Funktionsweise:
Nach einem Tastendruck fließt Strom durch eine
komplizierte Verdrahtung mehrerer gekoppelter
Rotoren und ein Lämpchen zeigt den Geheim-
textbuchstaben an. Die Rotoren drehen sich bei
jedem Anschlag um eine Einheit weiter.
Die deutsche Wehrmacht benutzt im 2. Weltkrieg
die Chiffriermaschine Enigma (griech.: Rätsel).
Funktionsweise:
Nach einem Tastendruck fließt Strom durch eine
komplizierte Verdrahtung mehrerer gekoppelter
Rotoren und ein Lämpchen zeigt den Geheim-
textbuchstaben an. Die Rotoren drehen sich bei
jedem Anschlag um eine Einheit weiter.
Kapitel 4 © Beutelspacher
November 2004Seite 27
Besser = unknackbar? Besser = unknackbar?
• Der Vigenère-Code wurde 350 Jahre lang nicht geknackt.
• Kann man den Code noch sicherer machen?
• Man muss das Schlüsselwort so lang wie möglich machen und
die Buchstaben zufällig wählen.
So erhält man einen unknackbare Code!
• Der Vigenère-Code wurde 350 Jahre lang nicht geknackt.
• Kann man den Code noch sicherer machen?
• Man muss das Schlüsselwort so lang wie möglich machen und
die Buchstaben zufällig wählen.
So erhält man einen unknackbare Code!
Kapitel 4 © Beutelspacher
November 2004Seite 28
Erfolg des Vigenère-VerfahrensErfolg des Vigenère-Verfahrens
Im allgemeinen werden gleiche Klartextbuchstaben in verschiedene
Geheimtextbuchstaben verschlüsselt. Daher sind die Häufigkeiten der
Buchstaben des Geheimtexts sehr ausgeglichen.
Also kann man mit einer herkömmlichen statistischen Analyse (die
häufigsten Buchstaben suchen und zu E, N, ... entschlüsseln) einen
Vigenère-Code nicht knacken.
Dieses Verfahren blieb über 300 Jahre lang ungeknackt!
Erst 1863 fand der preußische Infanteriemajor Friedrich Wilhelm
Kasiski eine Möglichkeit der Kryptoanalyse. Sie besteht aus 2 Teilen.
Im allgemeinen werden gleiche Klartextbuchstaben in verschiedene
Geheimtextbuchstaben verschlüsselt. Daher sind die Häufigkeiten der
Buchstaben des Geheimtexts sehr ausgeglichen.
Also kann man mit einer herkömmlichen statistischen Analyse (die
häufigsten Buchstaben suchen und zu E, N, ... entschlüsseln) einen
Vigenère-Code nicht knacken.
Dieses Verfahren blieb über 300 Jahre lang ungeknackt!
Erst 1863 fand der preußische Infanteriemajor Friedrich Wilhelm
Kasiski eine Möglichkeit der Kryptoanalyse. Sie besteht aus 2 Teilen.
Kapitel 4 © Beutelspacher
November 2004Seite 29
Kryptoanalyse, 1.Teil: Bei bekannter SchlüsselwortlängeKryptoanalyse, 1.Teil: Bei bekannter Schlüsselwortlänge
Angenommen, das Schlüsselwort hat 5 Buchstaben, dann wurden
die Buchstaben Nr. 1, 6, 11, 16, ... alle mit dem ersten Schlüssel-
wortbuchstaben verschlüsselt. Dann könnten wir diesen bestimmen:
Wir suchen den häufigsten Buchstaben unter den Buchstaben Nr. 1, 6,
11, 16, ... Dieser muss dem Klartext-E entsprechen.
Erster Schlüsselwortbuchstabe: Anfangsbuchstabe des Alphabets, bei
dem E in diesen häufigsten Buchstaben verschlüsselt wird.
Beispiel: Wenn der häufigste Buchstabe Q ist, dann sucht man in der
Spalte, die oben mit E beginnt, den Buchstaben Q. Dann geht man in
dieser Zeile nach vorne – und findet M.
Durch Betrachten der Buchstaben Nr. 2, 7, 12, 17, ... findet man den
zweiten Schlüsselwortbuchstaben. Usw.
Angenommen, das Schlüsselwort hat 5 Buchstaben, dann wurden
die Buchstaben Nr. 1, 6, 11, 16, ... alle mit dem ersten Schlüssel-
wortbuchstaben verschlüsselt. Dann könnten wir diesen bestimmen:
Wir suchen den häufigsten Buchstaben unter den Buchstaben Nr. 1, 6,
11, 16, ... Dieser muss dem Klartext-E entsprechen.
Erster Schlüsselwortbuchstabe: Anfangsbuchstabe des Alphabets, bei
dem E in diesen häufigsten Buchstaben verschlüsselt wird.
Beispiel: Wenn der häufigste Buchstabe Q ist, dann sucht man in der
Spalte, die oben mit E beginnt, den Buchstaben Q. Dann geht man in
dieser Zeile nach vorne – und findet M.
Durch Betrachten der Buchstaben Nr. 2, 7, 12, 17, ... findet man den
zweiten Schlüsselwortbuchstaben. Usw.
Kapitel 4 © Beutelspacher
November 2004Seite 30
Kryptoanalyse, 2.Teil: Schlüsselwortlänge bestimmen (I)Kryptoanalyse, 2.Teil: Schlüsselwortlänge bestimmen (I)
Wenn die ersten Buchstaben (z.B. E) einer Folge, die an zwei Stellen
im Klartext vorkommt (z.B. EIN), zufällig unter dem gleichen Schlüssel-
wortbuchstaben (z.B. C) stehen, dann ergeben sich an diesen Stellen
auch zwei gleiche Geheimtextfolgen (z.B. GPQ).
Beispiel:
SW: D A C H D A C H D A C H D A C H D A C H D A C H
KT: : : E I N : : : : : : : : : : : : : E I N : : :
GT: : : G P Q : : : : : : : : : : : : : G P Q : : :
Dieses Phänomen tritt dann auf, wenn der Abstand der Folgen (hier:
16) ein Vielfaches der Schlüsselwortlänge (hier: 4) ist.
Wenn die ersten Buchstaben (z.B. E) einer Folge, die an zwei Stellen
im Klartext vorkommt (z.B. EIN), zufällig unter dem gleichen Schlüssel-
wortbuchstaben (z.B. C) stehen, dann ergeben sich an diesen Stellen
auch zwei gleiche Geheimtextfolgen (z.B. GPQ).
Beispiel:
SW: D A C H D A C H D A C H D A C H D A C H D A C H
KT: : : E I N : : : : : : : : : : : : : E I N : : :
GT: : : G P Q : : : : : : : : : : : : : G P Q : : :
Dieses Phänomen tritt dann auf, wenn der Abstand der Folgen (hier:
16) ein Vielfaches der Schlüsselwortlänge (hier: 4) ist.
Kapitel 4 © Beutelspacher
November 2004Seite 31
Bestimmung der Schlüsselwortlänge (II)Bestimmung der Schlüsselwortlänge (II)
Die Länge des Schlüsselworts kann man also wie folgt bestimmen:
1. Man sucht gleiche Folgen im Geheimtext.
2. Man bestimmt den Abstand dieser Folgen.
3. Der ggT (größte gemeinsame Teiler) dieser Abstände ist ein
Kandidat für die Länge des Schlüsselworts.
Beispiel: Findet man in einem Geheimtext mehrfach vorkommende
Folgen mit den Abständen 30 (= 235), 84 (= 2237) und 18 (=
233), kommt man zur Vermutung, dass die Schlüsselwortlänge 6
ist.
Fazit: Auch der Vigenère-Code ist knackbar (wenn auch raffiniert)!
Die Länge des Schlüsselworts kann man also wie folgt bestimmen:
1. Man sucht gleiche Folgen im Geheimtext.
2. Man bestimmt den Abstand dieser Folgen.
3. Der ggT (größte gemeinsame Teiler) dieser Abstände ist ein
Kandidat für die Länge des Schlüsselworts.
Beispiel: Findet man in einem Geheimtext mehrfach vorkommende
Folgen mit den Abständen 30 (= 235), 84 (= 2237) und 18 (=
233), kommt man zur Vermutung, dass die Schlüsselwortlänge 6
ist.
Fazit: Auch der Vigenère-Code ist knackbar (wenn auch raffiniert)!
Kapitel 4 © Beutelspacher
November 2004Seite 32
Vigenère knackenVigenère knacken
E Y R Y C F W L J H F H S I U B H M J O U C S E GT N E E R F L J L V S X M V Y S S T K C M I K Z S J H Z V B F X M X K P M M V W O Z S I A F C R V F T N E R H M C G Y S O V Y V F P N E V H J A O V WU U Y J U F O I S H X O V U S F M K R P T W L C I F M W V Z T Y O I S U U I I S E C I Z V Z V Y V F P C Q U C H Y R G O M U W K V B N X V B V H H W I F L M Y F F N E V H J A O V W U L Y E R A Y L E RV E E K S O C Q D C O U X S S L U Q V B F M A L F E Y H R T V Y V X S T I V X H E U W J G J Y A R S I L I E R J B V V F B L F V W U H M T V U A I J H P Y V K K V L H V B T C I U I S Z X V B J B V V P V Y V F G B V I I O V W L E W D B X M S S F E J G F H F V J P L W Z S F C R V U F M X V Z M N I R I G A E S S H Y P F S T N L R H U Y R
E Y R Y C F W L J H F H S I U B H M J O U C S E GT N E E R F L J L V S X M V Y S S T K C M I K Z S J H Z V B F X M X K P M M V W O Z S I A F C R V F T N E R H M C G Y S O V Y V F P N E V H J A O V WU U Y J U F O I S H X O V U S F M K R P T W L C I F M W V Z T Y O I S U U I I S E C I Z V Z V Y V F P C Q U C H Y R G O M U W K V B N X V B V H H W I F L M Y F F N E V H J A O V W U L Y E R A Y L E RV E E K S O C Q D C O U X S S L U Q V B F M A L F E Y H R T V Y V X S T I V X H E U W J G J Y A R S I L I E R J B V V F B L F V W U H M T V U A I J H P Y V K K V L H V B T C I U I S Z X V B J B V V P V Y V F G B V I I O V W L E W D B X M S S F E J G F H F V J P L W Z S F C R V U F M X V Z M N I R I G A E S S H Y P F S T N L R H U Y R
Kapitel 4 © Beutelspacher
November 2004Seite 33
Ein unknackbarer CodeEin unknackbarer Code
Schlüsselwort: Q X V H C A M D M Z S J E C B Y
Klartext: D A S I S T U N K N A C K B A R
Geheimtext: T X N P U T G Q W M S L O D B P
Schlüsselwort: Q X V H C A M D M Z S J E C B Y
Klartext: D A S I S T U N K N A C K B A R
Geheimtext: T X N P U T G Q W M S L O D B P
Kapitel 4 © Beutelspacher
November 2004Seite 34
Was heisst “unknackbar”? Was heisst “unknackbar”?
T X N P U T G Q W M S L O D B P
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A B
. . . . . . . . . . . . . . . .
D A S I S T U N K N A C K B A R
. . . . . . . . . . . . . . . .
M A T H E M A T I K I S T G U T
. . . . . . . . . . . . . . . .
Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z
T X N P U T G Q W M S L O D B P
A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A B
. . . . . . . . . . . . . . . .
D A S I S T U N K N A C K B A R
. . . . . . . . . . . . . . . .
M A T H E M A T I K I S T G U T
. . . . . . . . . . . . . . . .
Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z
Kapitel 4 © Beutelspacher
November 2004Seite 35
One-time pad („Einmalblock“)One-time pad („Einmalblock“)
• Algorithmus: Addition „modulo 2“
• Entschlüsseln = Verschlüsseln
• Die Vernam-Chiffre ist absolut sicher (“perfekt”), falls die Schlüsselfolge wirklich zufällig ist (Shannon 1949)
• Problem: Länge der Schlüsselfolge = Länge des Klartexts
• Algorithmus: Addition „modulo 2“
• Entschlüsseln = Verschlüsseln
• Die Vernam-Chiffre ist absolut sicher (“perfekt”), falls die Schlüsselfolge wirklich zufällig ist (Shannon 1949)
• Problem: Länge der Schlüsselfolge = Länge des Klartexts
Zufallsfolge (one-time pad )
Klartext
Geheimtext01101 01000 11100 ...
01001 10001 11000 ...
00100 11001 00100 ...
Kapitel 4 © Beutelspacher
November 2004Seite 36
PseudozufallsfolgenPseudozufallsfolgen
• Praktischer Kompromiss: Pseudozufallsfolgen
• Sender und Empfänger müssen nur einen Schlüssel (= Initialisierung
des Generators) konstanter Länge austauschen.
• Anwendung: Verschlüsselung beim Handy
• Praktischer Kompromiss: Pseudozufallsfolgen
• Sender und Empfänger müssen nur einen Schlüssel (= Initialisierung
des Generators) konstanter Länge austauschen.
• Anwendung: Verschlüsselung beim Handy
Pseudozufallsfolge
Klartext
Geheimtext01101 01000 11100 ...
01001 10001 11000 ...
00100 11001 00100 ...
Pseudo-
zufallsbit-
generator
Kapitel 4 © Beutelspacher
November 2004Seite 37
4.4 Geht das mit rechten Dingen zu?4.4 Geht das mit rechten Dingen zu?
• Zwei Personen, die sich noch nie getroffen haben,
unterhalten sich öffentlich ...
... und am Ende des Gesprächs haben sie
ein gemeinsames Geheimnis,
während alle anderen keine Ahnung davon haben ???
• Das wäre die Lösung des Schlüsselproblems! Man müsste die
Übertragung des Schlüssels nicht mehr organisatorisch (o.ä.) regeln,
sondern könnte mathematische Methoden anwenden!
• Zwei Personen, die sich noch nie getroffen haben,
unterhalten sich öffentlich ...
... und am Ende des Gesprächs haben sie
ein gemeinsames Geheimnis,
während alle anderen keine Ahnung davon haben ???
• Das wäre die Lösung des Schlüsselproblems! Man müsste die
Übertragung des Schlüssels nicht mehr organisatorisch (o.ä.) regeln,
sondern könnte mathematische Methoden anwenden!
Kapitel 4 © Beutelspacher
November 2004Seite 38
Die Kunst, öffentlich geheime Süppchen zu kochenDie Kunst, öffentlich geheime Süppchen zu kochen
gemeinsame Suppe
öffentlich:öffentlich:
Kapitel 4 © Beutelspacher
November 2004Seite 39
Diffie-Hellman Key-Exchange (1976)Verfahren zur „symmetrischen“ Erzeugung eines gemeinsamen
Schlüssels
Diffie-Hellman Key-Exchange (1976)Verfahren zur „symmetrischen“ Erzeugung eines gemeinsamen
Schlüssels
Wählt Zahl a < p.
Berechnet = ga mod p.
Berechnet a mod p( = g ba mod p).
Wählt Zahl b < p.
Berechnet = gb mod p.
Berechnet b mod p( = g ab mod p).
g ba mod p = K = g ab mod pgemeinsamer Schlüssel
öffentlich: p Primzahl (100 Stellen), g natürliche Zahl (100 Stellen)
öffentlich: p Primzahl (100 Stellen), g natürliche Zahl (100 Stellen)
Kapitel 4 © Beutelspacher
November 2004Seite 40
“Systematische” Angriffe“Systematische” Angriffe
• Systematisches Ausprobieren aller Schlüssel
symmetrisch Schlüsselaust. Bewertung
40 Bit 256 Bit völlig unsicher
56 Bit 512 Bit heute knackbar
128 Bit 1024 Bit nicht knackbar
256 Bit 2048 Bit nie knackbar
• Bezüglich dieser Angriffe ist die Sicherheit von Algorithmen
unbeschränkt! Die einzige Gefahr droht von der Mathematik!
• Systematisches Ausprobieren aller Schlüssel
symmetrisch Schlüsselaust. Bewertung
40 Bit 256 Bit völlig unsicher
56 Bit 512 Bit heute knackbar
128 Bit 1024 Bit nicht knackbar
256 Bit 2048 Bit nie knackbar
• Bezüglich dieser Angriffe ist die Sicherheit von Algorithmen
unbeschränkt! Die einzige Gefahr droht von der Mathematik!