Skripte DHBW

Vorlesungsskripte aus dem DHBW-Studium

Kryptographie 22.01.2018

Inhalte

Literatur

Grundbegriffe

Was ist Kryptologie?

Kryptologie ist eine Wissenschaft, die sich mit Methoden der Verschlüsselung und damit verwandte Verfahren befasst.

Kryptographie bezeichnet den Zweig der Kryptologie, der sich mit der Erstellung und dem Design kryptologischer Algorithmen befasst. In der Kryptoanalyse geht es um das nicht-autorisierte Brechen von Verschlüsselungen.

Der Kryptologie liegt ein einfaches Kommunikationsmodell zugrunde:

Bei der Kryptographie geht es um folgendene Punkte:

Weiter Begriffe:

Definition: Der Klartext ist die Nachricht, die durch ein geeinetes Verfahren in eine Form transformiert wird, dass eine Informationsentanhme durch eine 3. Partei nicht möglich ist.

Klartext zu…

Es gibt zwei grundlegende Verfahren, eine Nachricht vor Informationsentanhme zu schützen:

Das Verfahren, einen Klartext in eine Form zu transformieren, dass die Informationsentnahme nicht möglich ist, heisst Verschllüsselung, oder Chiffrieren, eine verschlüsselte Nachricht heißt Chiffretext. Codieren, hat eine andere Bedeutung, nämlich Umwandlung in eine andere Form, damit sie geeignet verarbeitet werden können.

Die Umkehrung heißt Entschlüsselung oder Dechffrierung. Ein Kryptographischer Algorithmus (oder auch Chiffre) ist das mathematische Verfahren, welches den Klartext im Chiffretext umwandelt. Üblicherweise verwenden heutige krypto. Verfahren einen Schlüssel K. Das ist ein bestimmer Wert aus einem Schlüsselraum.
z.B. K = 128Bit Schlüsselraum

Daumenregel: 10^3 = 1024 ~= 10^3

Grundlegenes Szenario (Symmetrische Verschlüsselung)

Symmetrische Verfahren haben (alle) drei grundsätzliche Probleme

  1. Key Exchange Probleme
  1. Key Management Problem
  1. Mit symmetrischen Verfahren ist es nicht möglich, digitale Signatur zu realisieren. Es gibt kein eindeutiges Indentifikationsmerkmal für den Sender einer Nachricht.

Grundlegenes Szenario (Asymmetrische Verschlüsselung)

1976 Whitfield Diffie + Martin Hellman: “New Directions in Cryptography” => Public Key Kryptographie oder Asymmetrische Verschlüsselung

Key Exchange-Problem gelöst, da Alice und Bob keinen Schlüssel über einen sicheren Kanal austauschen müssen!

Key Management-Problem gelöst, da ein Schlüssel ausreicht (K_pub), so dass beliebig viele Parteien vertraulich mit Bob kommunizieren können.

In der Praxis: Public-Key-Verfahren sind etwa 1000x langsamer als symmetrische Verfahren -> man verwendet daher sog. Hybridverfahren

Es gibt Dutzende symmetrische Verfahren, z.B.

Public-Key-Verfahren:

Sowohl symmetrische als auch asymmetrische Verfahren können in Form von Block-Chiffren oder Strom-Chiffren eningesetzt werden. Bei Blockchiffren werden Bitblöcke (z.B. 64 Bit) in einem Vorgang verschlüsselt in einem 64 Bit Chiffreblock. Klartext -> aufteilen in n 64 Bit Blöcken. Bei Stromchiffren (bzw. bei WLAN) wird Zeichen für Zeichen verschlüsselt (bitweise/byteweise).

Es gibt in den meisten Kryptografischen Systemen zwei grundlegende Operationen wie Klartext in Chiffretext transformiert wird.

Moderne Verfahren benutzen eine Vielzahl von Substitutions- bzw. Transpositiosoperationen.

Definition: (Claude Shannan 1948): Ein Kryptosystem ist ein Fünf-Tupel K = (P,C,K,E,D).

Also: Das Design eines Kryptosystems erforder die Spezifikation von fünf Größen

  1. Klartextalphabet
  2. Chiffretextalphabet
  3. Schlüsselraum
  4. Verschlüsselungsverfahren
  5. Entschlüsselungsverfahren

In der heutigen Kryptographie wird in der Regel streng auf das KERCKHOFFS-Prinzip geachtet (1883). “Die Sicherheit eines Kryptosystems darf niemals von der Geheimhaltung des Verschlüsselungsalgorithmus abhängen, sondern ausschließlich von dem Geheimhalten des Schlüssels.”

kurz: Who is who in der Kryptografie (keinesfalls vollständig)

Klassische Symmetrische Verschlüsselungsverfahren

  1. Klartext wird in Kleinbuchstaben geschrieben
  2. CHIFFRETEXT WIRD IN GROßBUCHSTABEN geschrieben
  3. Im Klartext werden Leerzeichen und Interpunktionszeichen weggelassen
  4. Die Klartext- und Chiffretextzeichen werden durch die Zahlen von 0 bis 25 dargestellt

Die Shift-Chiffre (oder Cäsar-Chiffre)

Das Shift-Chiffre ist eine sog. monoalphabetische Chiffre, d.h. das Klartextalphabet wird genau auf ein Chiffretextalphabet abgebildet. Dies hat zur Folge, dass die statistische Struktur des Klartexts erhalten bleibt.

Andere Frage: Hilft es, wenn man ein Klartext 2x hintereinander und 2 verschiedenen Schlüsseln verschlüsselt, also, erhöht sich dadurch die Sicherheit? Hier nicht, da das Hintereinanderausführen von zwei Shift-Chiffren mit den Schlüsseln K_1,K_2 wie einer Verschlüsselung mit K_1+K_2.

Die Affine Chiffre

Beispiel, Klartext: Wirtschaftsinformatik

(α,β)=(5,12)(\alpha, \beta) = (5, 12)

ggT(5,26)=1ggT(5,26) = 1

w↦22↦122w \mapsto 22 \mapsto 122

Vorlesung 2

Die Vigenère-Chiffre

Die Shift- und die affine Chiffre sind Beispiele von monoalphabetischen Chiffren, d.h. mit der Wahl eines Schlüssels wird jedes Klartextzeichen auf genau ein Chiffretextzeichen abgebildet (Eigenschaft, dass die statistische Eigenschaft des Klartexts auf dem Chiffretext übertragen wird)

Vigenère-Chiffre (1586) veröffentlicht, galt langge als nicht brechbar bis zu den 1860ern, Friedrich Kasiski, Charles Babbage.

Definition:
Sei eine positive ganze Zahl und
M=C=K=(Z26)mM = C = K = (\mathbb{Z}_{26})^m
=Z26⋅Z26⋅⋯⋅Z26= \mathbb{Z}_{26} \cdot \mathbb{Z}_{26} \cdot \dots \cdot \mathbb{Z}_{26}

Für einen festen Schlüsselwert K⃗=K....\vec{K} = K....
…\dots

Beispiel:

Alice und Bob vereinbaren ein Schlüsselwort jamesbond .
Nun ist m = 9 wegen 9 unterschiedlichen Zeichen.

jamesbond --> 9 0 12 4 18 1 13 13 3 = k⃗\vec{k}.

Klartext: treffenummitternacht

t r e f f e n u m m i t t e r n a c h t
19

t r e f f e n u m m i t t e r n a c h t
19 17 4 5 5 4 13 20 12 12 8 19 19 4 17 13 0 2 27 19
9 0 12 4 18 1 14 13 3 9 0 12 4 18 1 13 13 3 9 0
2 17 16 9 23 5 1 7 15 21 8 5 23 22 18 1 13 5 16 19
C R Q J X F B H P V I F X W S B N F Q T

In fett: Effekt von polyalphabetischen Verfahren. Ein Zeichen kann auf verschiedene Zeichen abgebildet werden.
In kursiv: n wird auf B abgebildet. Das Alphabet wiederholt sich. Der erste Schritt zum knacken wäre also die Schlüssellänge (Auch benannt Periode, wann es sich wiederholt) rauszufinden.

Entschlüsselung: Mit gleichem Schlüsselwort einfach abziehen (xi−ki) mod26(x_i - k_i)\ mod26
Schlüsselraum: ∣K∣=26⋅26⋅…⋅26=26m|K| = 26 \cdot 26 \cdot \ldots \cdot 26 = 26^m
k⃗=(k1,k2,…,km)\vec{k} = (k_1, k_2, \ldots, k_m)
z.B. m = 5 --> 26526^5 Schlüssel ~ 1.2⋅1071.2 \cdot 10^7 Schlüssel.

Die Vigènere-Chiffre ist eine polyalphabetische Chiffre, weil durch die Wahl des Schlüssels k⃗\vec{k} (ohne Buchstabenwiederholung) eine Klartextzeichen auf m mögliche Chiffrezeichen abgebildet wird.

  1. Auswahl eines Schlüssels:
    Wähle eine Zahl, z.B. n = 3; der Schlüssel ist eine n×\timesn-Matrix MM, deren Einträge Zahlen mod 26 sind. MM:
    enter image description here

Hier: n = 3
berlin
Als Zahl: (1,4,17)⋅(11,8,13)(1, 4, 17) \cdot (11, 8, 13)

(1,4,17)=Block 1(1, 4, 17) = \text{Block 1}

(11,8,13)=Block 2(11, 8, 13) = \text{Block 2}
(1,4,17)⋅M=(204,175,163) mod 26(1, 4, 17) \cdot M = (204, 175, 163)\ mod\ 26

=(22,19,7)=Chiffretext= (22, 19, 7) = \text{Chiffretext}
(11,8,13)⋅M=(4,23,3)(11, 8, 13) \cdot M = (4, 23, 3)
berlin=22,19,7,4,23,3\text{berlin} = 22, 19, 7, 4, 23, 3

Dechiffrierung

Dazu benötigt man die zu MM inverse Matrix M−1M^{-1}, die wir NN nennen, diese erfüllt:
M⋅N=I3x3mod 26M \cdot N = I_{3x3} \text{mod 26}
II = Identitätsmatrix, Hauptdiagonale alle Werte 1

detM=40+132+108−54−64−165=−3=23 mod 26det M = 40 + 132 + 108 - 54 - 64 - 165 = -3 = 23 \text{ mod 26}
M−1=1detM⋅(inverse matrix berechnen, Laplace auf M)M^{-1} = \frac{1}{detM} \cdot (\text{inverse matrix berechnen, Laplace auf M})

WTH = 22, 19, 7

(22,19,7)⋅M−1=(1,4,17)=b e r(22, 19, 7) \cdot M^{-1} = (1, 4, 17) = \text{b e r}

Eine wichtige Eigenschaft von Blockchiffren ist die Diffusion (Shamron); d.h. die Änderung eines Klartextzeichens hat zur Folge, dass sich mehrere Chiffretextzeichen ändern.

Beispiel: a a b – 0 0 1
–> (0,0,1)⋅M(0, 0, 1) \cdot M
–> (11,9,8)(11, 9, 8) --> L, J, I

a b b – 0 1 1
–> (0,1,1)⋅M(0, 1, 1) \cdot M
–> (15,14,14)(15, 14, 14) --> P, O, O

Diese Eigenschaft müssen heutige Block-Chiffren (DES, AES) aufweisen. Dadurch wird die statistische Struktur von Klartextblöcken verschleiert.

Rotor-Maschinen
Das Ende der Fahnenstange polyalphabetischer Chiffren sind Rotormaschinen.
Abschtzung des Schlüsselraums:
Drei Walzen à 26 Positionen: 26326^3 Positionen = 17576 Möglichkeiten.

Set besteht aus 5 Walzen. 35\overset{5}{3} = 10 Möglichkeiten

3! Möglichkeiten, die drei Walzen in den Slots einzugeben = 6

–> 60 Möglichkeiten --> 1.054.560 Konfigurationen.

Steckbrett: Möglich z.B. 5 Buchstabenpaare zu tauschen
A⟷F,C⟷L,K⟷MA \longleftrightarrow F , C \longleftrightarrow L, K\longleftrightarrow M

Bei 5 Vertauschungen sind das
15!⋅⟮226⟯⋅224⋅…=295.269.975 Möglichkeiten\frac{1}{5!} \cdot \lgroup \overset{26}{2}\rgroup \cdot \overset{24}{2} \cdot \ldots = \text{295.269.975 Möglichkeiten}

1 x 2 x 3 insgesamt 3.113.799.048.360.000 Möglichkeiten!!

Mathematische Grundlagen

Algebraische Strukturen

N\mathbb{N} = Menge der natürlichen Zahlen = {0, 1, 2, …}
Z\mathbb{Z} = Menge der ganzen Zahlen = {-2, -1, 0, 1, 2}

Eine binäre Operation o auf einer Menge ist eine Abbildung

o:A⋅A→Ao: A \cdot A \rightarrow A

(a,b)↦a o b (a, b) \mapsto a \text{ o } b

Da a o b ∈A\in A heißt A abgeschlossen unter o

Halbgruppen

Eine Halbgruppe ist ein Paar (A,o)(A, o), AA ist eine Menge, o bingäre Abbilgund, und es gilt:
a o (b o c)=(a o b) o c Assoziativgesetza \text{ o } (b \text{ o } c) = (a \text{ o } b) \text{ o } c \text{ Assoziativgesetz}

Bsp:(N,+),(N,×)\text{Bsp:} (\mathbb{N}, +), (\mathbb{N}, \times)

…\ldots

Eine Halbgruppe mit einem neutralem Element heißt Monoid.

Gruppen

Eine Gruppe ist eine Halbgruppe (A,o)(A, \text{o}) mit:

  1. Es existiert ein neutrales Element IA∈A\mathbb{I}_A \in A mit a o a−1=a    ∀a∈Aa \text{ o } a^{-1} = a \ \ \ \ \forall{} a \in A
  2. ∀ a∈A\forall \ a \in A existiert ein Element a o a−1=IA⋅Inversesa \text{ o } a^{-1} = \mathbb{I}_A \cdot \text{Inverses}
    Falls (A,o)(A, o) eine Gruppe ist und o ist Kommutativ, d.h.
    a o b=b o aa \text{ o } b = b \text{ o } a

dann heißt (A,o)(A, o) ABELsche Gruppe.

Beispiele:
(Z,+)(\mathbb{Z}, +) ist eine ABELsche Gruppe.
Zu jedem a∈Z gibt es ein a−1=−a∈Za \in \mathbb{Z} \text{ gibt es ein } a^{-1} = -a \in \mathbb Z
mit a+(−a)=0   neutrales Elementa + (-a) = 0 \ \ \text{ neutrales Element}

Z,x\mathbb{Z}, x ist keine Gruppe, warum?
assoziativ erfüllt, aber …\ldots

(Q∖{0},×)(\mathbb{Q}\setminus \{0\}, \times) ist eine ABELsche Gruppe
Die Menge der Shift-Chiffren bilden unter den Operationen “Hintereinanderausführung” eine ABELsche Gruppe.

Auf der Menge Z\mathbb{Z} sind zwei binäre Operatoren definiert, nämlich Addition und Multiplikation.
Das Tripel (Z,+,×)(\mathbb{Z}, +, \times)

Ein Ring ist ein Tripel (A,+,X)(A, +, X) mit

  1. (A,+)(A, +) bildet eine Gruppe
  2. (A,×)(A, \times) --> ×\times ist assoziativ, ×\times hat ein neutrales Element, aber kein Inverses.
  3. Es gilt das Distributivgesetz

a×(b+c)=a×b+a×ca \times (b + c) = a \times b + a \times c

(a+b)×c=a×c+b×c    ∀a,b,c,∈A(a+b)\times c = a \times c + b \times c \ \ \ \ \forall a,b,c, \in A

Bsp: (Z,+,×)(\mathbb{Z}, +, \times) bildet ein Ring.
Die Menge aller Polynome in x mit Koeffizienten in einem Körper bildet einen Ring, den Polynomring.

Ein Körper (englisch field) ist eine nichtleere Menge AA mit zwei binären Operationen, Addition (++) und Multiplikation (×\times) mit folgenden Axiomen:

  1. ∀ a,b∈A  gilt das Assoziativgesetz\forall \ a, b \in A \ \text{ gilt das Assoziativgesetz}
  2. ∀ a,b∈A  gilt das Kommunitativgesetz\forall \ a, b \in A \ \text{ gilt das Kommunitativgesetz}
  3. ∀ a,b∈A  gilt das Distributivgesetz\forall \ a, b \in A \ \text{ gilt das Distributivgesetz}
  4. Neutrale Elemente: ∀ a∈A\forall \ a \in A:
    Existiert ein Element 0A∈A0_A \in A mit a+0A=aa + 0_A = a
    Existiert ein Element 1A∈A1_A \in A mit a×1A=aa \times 1_A = a
  5. Inverse Elemente: ∀ a∈A\forall \ a \in A:
    Existiert ein Element −a-a mit a+(−a)=0Aa+(-a)=0_A, Additives Inverses
    Existiert ∀ a∈A∖{0A}\forall \ a \in A \setminus \{0_A\} ein Element a−1a^{-1} mit

a×a−1=1A. (multiplikatives Inverses)a \times a^{-1} = 1_A \text{. (multiplikatives Inverses)}

Lemma:

Für jeden Körper K gilt:

  1. a⋅0=0  ∀ a∈Ka \cdot 0 = 0 \ \ \forall \ a \in K
  2. Wenn a⋅b=0→a=0 oder b=0a \cdot b = 0 \rightarrow a = 0 \text{ oder } b = 0

…\ldots

Es gibt weiterhin sogenannte endliche Körper (Galois-Felder).

→(Zp,(a+b) mod p,(a×b) mod p)\rightarrow (\mathbb{Z}_p, (a+b) \text{ mod p}, (a\times b)\text{ mod p}) bildet einen Körper.

Zp={0,…,p−1}\mathbb{Z}_p=\{ 0, \ldots, p-1 \} , p Primzahl

Elementäre Eigenschaften von Zahlen

Eine Zahl b≠0b \neq 0 heißt Teiler von a∈Za \in \mathbb{Z}, (umgekehrt: a∈Za \in \mathbb{Z} heißt Vielfaches von b) falls
a=m⋅b,m∈Z.a = m \cdot b, m \in \mathbb{Z}.

Oder: bb teilt die Zahl aa ohne Rest:
b∣ab \vert a

Beispiel: a = 24, Teiler: 1, 2, 3, 4, 6, 8, 12, 24
Es gilt:

  1. Wenn a∣1→a=±1a \vert 1 \rightarrow a = \pm 1
  2. Wenn a∣ba\vert b wird b∣a→a=±bb \vert a \rightarrow a = \pm b
  3. Jedes b≠0b \neq 0 ist Teiler von 0
  4. Wenn b∣gb \vert g wird b∣h→b∣(m⋅g+n⋅h).b \vert h \rightarrow b\vert (m\cdot g + n\cdot h).

Anmerkung: Es gibt vollkommene Zahlen (perfect numbers).
aa heißt vollkommen, wenn sie als Summe ihrer echten Teiler geschrieben werden kann:
28=1+2+4+7+1428 = 1 + 2 + 4 + 7 + 14

Eine Zahl p∈Z,p>1p \in \mathbb{Z}, p > 1 heißt Primzahl genau dann, wenn die einzigen Teiler von p±1,±pp \pm 1, \pm p sind. Eine Zahl nn, die keine Primzahl ist, heißt zusammengesetzte Zahl.

Satz: Es gibt unendlich viele Primzahlen.
Beweis - der klassische Widerspruchsbeweis (Euclid):

q=2⋅3⋅5⋅7⋅…⋅Pnq = 2 \cdot 3 \cdot 5 \cdot 7 \cdot \ldots \cdot P_n

qq wird durch alle PiP_i geteilt, ohne Rest.

→\rightarrow Widerspruch zur Annahme →\rightarrow Es gibt unendlich viele Primzahlen.