Fach:AK Lernziele

Aus StudyWiki

Inhaltsverzeichnis

1 Woche 1 - Grundlagen der Kryptografie
2 Woche 2 - Klassische Kryptografie und ihre Kryptoanalyse
3 Woche 3 - Zahlentheoretische Grundlagen: Basic Skills
4 Woche 4 - Moderne Blockch. und ihre Betriebsarten: DES
5 Woche 5 - Zahlentheoretische Grundlagen: Advanced Skills
6 Woche 7 - (Kryptografische) Hashfunktionen
7 Woche 8 - Exponentialchiffre und das RSA-Public-Key-Kryptosystem
8 Woche 9 - Diskreter Logarithmus und kryptografische Anwendungen
9 TI Funktionen

[bearbeiten] Woche 1 - Grundlagen der Kryptografie

[bearbeiten] Eine Definition von Kryptografie, Kryptoanalyse und Kryptologie kennen

Kryptografie = Kunst / Wissenschaft, und Methodik Daten zu ver- und entschlüsseln sowie zu hashen (schreiben, lesen)

Kryptanalyse = Kunst / Wissenschaft und Methodik des Knackens von kryptografischen Algorithmen (brechen, umgehen)

Kryptologie = Oberbegriff für Kryptografie und Kryptoanalyse

[bearbeiten] Die fünf Komponenten eines Kryptosystems (und Ihre Zusammenhänge) beschreiben können

Klartextraum
Chiffretextraum
Schlüsselraum
Chiffriertransformationen
Dechiffriertransformationen

[bearbeiten] Drei Anfangssituationen für Kryptoanalytiker beherrschen

Nur-Chiffretext-Angrif - Nur der Chiffretext ist bekannt
Bekannter Plaintext-Angriff - Klar- und Chiffretext-Paare sind bekannt
Gewählter Klartext-Angriff - ein zu chiffrierender Text kann gewählt werden
Replay-Attacke - Angriff auf Authentizität durch Wiedereinspielen

[bearbeiten] Angriffspunkte

kurze Schlüssellängen (Periodizität von Schlüsseln)
Häufigkeitsverteilung der Buchstaben
Digramm-Häufigkeitsverteilung

[bearbeiten] Die Sicherheitsanforderungen an einem Kryptosystem erklären können und wissen, wann ein Kryptosystem schwer zu knacken ist

Geheimhaltungsanforderungen
- Es sollte nicht möglich sein Die Dechiffriertransformation aus abgefangenem chiffretext zu bestimmen
- Es sollte nicht möglich sein den Klartext aus dem Chiffretext zu bestimmen
Authenzititätsanforderungen
- Es sollte nicht möglich sein Die Chiffriertransformation aus abgefangenem chiffretext zu bestimmen
- Es sollte nich möglich sein eine kollision herbeizuführen

[bearbeiten] Transpositions- und Substitutionschiffren verstehen

Transposition: Umstellen (verschieben) der Bits oder Zeichen eines Klartextes. Es werden nur die im Text vorhandenen Zeichen verwendet.

Substitution: Ersetzen der Bits, Zeichen oder Zeichenblöcke eines Klartextes durch beliebige Zeichen

[bearbeiten] Multiplikations- und Affine-Chiffre verwenden können

[bearbeiten] Multiplikationschiffre

1) Eine Multiplikationsfunktion bestimmen

 f(a) = (a * k) mod n

2) Buchstaben-Nummern substitutionstabelle erstellen

 z.B.
 A=1, B=2, ...

3) Buchstabe durch Zahl substituiren, funktion darauf anwenden und daaas Resultat wiedeer zurücksubstituieren

[bearbeiten] Affinechiffre

Das selbe wie Multiplikation aber mit einer anderen funktion

 f(a) = (a * k1 + k0) mod n
 k1 und k2 sind frei wählbar

[bearbeiten] Das berühmte Verschlüsselungsverfahren von Vigenère kennen

Eine Tabelle wird zur ver- und entschlüsselung verwendet, das Vigenere-Quadrat
Der Schlüssel muss gleich lang, wie der Klartext sein (oder sich so lange wiederholen, bis er das ist)
Verschlüsselung: die Spalte, welche das i-te zu verschlüsselnde Zeichen beinhaltet wird "gekreuzt" mit der Zeile, welche das i-te Zeichen des Schlüssels beinhaltet.

Vigenère-Quadrat
		Text
		`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`
S c h l ü s s e l	`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 26`	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 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 A C 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 I K 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	G e h e i m t e x t

Basiert auf Verschiebe-Chiffre. Jedes Zeichen im Klartext wird verschoben, wobei der Betrag der Verschiebung von der Position des Zeichens im Text und dem Schlüsselwort abhängt.

Ist der Schlüssel echt gleichlang, wie der Plaintext, sprechen wir von einer Vernam Chiffre oder einem OTP.

[bearbeiten] Mit der Hill-Chiffre, mit der Playfair-Chiffre und mit Chiffren mit homophoner Substitution arbeiten können

[bearbeiten] Hill-Chiffre

Blockbasierende Substitution, der Form

$C = E k (M) = M A$

Wobei A eine Matrix mit der Grösse der Blocksize des Systems (zB 2) ist und eine inverse Matrix modulo n existiert. Beispiel:

$A =\begin{vmatrix} 3 & 2\\3&5\end{vmatrix}, A^{-1} = \begin{vmatrix}15& 20\\ 17 &9\end{vmatrix}$

Die Matrix wird blockweise auf den Klartext angewandt.

Kryptanalyse am erfolgreichsten, wenn einzelne Text-Elemente (Plain und Cipher) bekannt sind, da somit Rückschlüsse auf die Schlüsselmatrix gezogen werden können.

[bearbeiten] Playfair-Chiffre

Erzeugen einer 5x5-Matrix durch horizontales einfüllen des Schlüsselwortes (ohne Umlaute, jedes Zeichen wird nur einmal erfasst). Anschliessend wird der Rest der Matrix mit den im Alphabet verbleibenden Zeichen aufgefüllt (alphabetisch sortiert).
Aufteilen des Klartextes in Digramme. Bei Doppelten Zeichen in einem Digramm wird der erste Buchstabe mit einem 'X' erweitert (escaped), fehlt am Schluss ein Zeichen, wird das letzte Digram ebenfalls mit einem 'X' aufgefüllt (zB. 'HALLO' => HA-LX-LO)
Verschlüsselung entsprechend einem der folgenden drei Fälle
1. Beide Buchstaben in derselben Zeile => Verwendung des jeweils rechten Nachbarn in derselben Zeile (modulo 5)
2. Beide Buchstaben in derselben Spalte => Verwendung des jeweils unteren Nachbarn in derselben Spalte
3. Alle andern Fälle => Die beiden Buchstaben spannen ein Viereck in der Matrix auf. Das erste Element des Digrammes wird durch die obere Ecke substituiert, das zweite durch die untere Ecke der Submatrix

Anders formuliert:

 pt = {A[x1,y1],B[x2,x2]}
 ct = {P1[x1, y2], P2[x2, y1]}

Das gleiche Verfahren wird für die Entschlüsselung verwendet.

[bearbeiten] homophobe Substitution

Das Ziel der homophonen Substitution ist die Gleichverteilung des Vorkommens aller Zeichen im Ciphertext.

Dazu wird zu jedem Zeichen des Plaintextes die relative Häufigkeit ermittelt. Anschliessend wird für jeden Buchstaben ein Set von Substitutions-Elementen (zB. durch Zufallsgenerator) generiert. Wichtig ist dabei, dass die Grösse des Sets proportional gleich gross ist, wie die Verteilung des Auftretens des Buchstabens im Plaintext.

Besteht zB. das set ‚E’ = {00 08 19 32 93 99}. Substituiert wird das erste Auftreten von E mit 00, das zweite mit 08, etc.

[bearbeiten] Eine beliebige klassische Verschlüsselungsmethode in einer frei wählbaren Programmiersprache umsetzen

[bearbeiten] Woche 2 - Klassische Kryptografie und ihre Kryptoanalyse

[bearbeiten] Sie kennen die grundsätzlichen Schwachstellen von Verschlüsselungsverfahren, zum Beispiel zu kurze Schlüssellängen

kurze Schlüssellängen
Häufigkeitsverteilung der Buchstaben
Digramm-Häufigkeit

[bearbeiten] Sie sind in der Lage den Unterschied zwischen monoalphabetischen und polyalphabetischen Verschlüsselungsverfahren zu erklären

Cäsar ist ein Beispiel der Monoalphabetischen verschlüsselung, da jeder Buchstabe immer mit dem gleichen substituiert wird.

Vigenere ist eine Polyalphabetische verschlüsselung, da der gleiche Buchstabe unter umständen mit einem anderen wert Substituiert werden kann.

[bearbeiten] Sie können die klassischen Verschlüsselungsverfahren Cäsar, Substitution und Vigenère selbst auf eine beliebige Textnachricht anwenden

[bearbeiten] Cäsar Verschlüsselung

Das Alphabet muss einfach zwei mal untereinander aufgeschrieben werden, das 2te mal mit einer verschiebung, der rest wird am anfang eingefügt.

Verschlüsselt wird der obere mit dem unteren und zum entschlüsseln wird der untere mit dem oberen codiert.

 Bsp mit der Original verschiebung von 3
 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
 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

Als sonderfall gilt der Schlüssel 13 (Entspricht der ROT13 codierung), da damit ein ver und entschlüsseln durcj die gleiche Funktion erfolgen kann.

[bearbeiten] Substitutions Verschlüsselung

Im Aufbau gleich wie Cäsar mit dem Unterschied, dass keine fixe verschiebung stattfindet.

Es wird einfach ein Blind durchmischte zweite Zeile generiert, die dan als Schlüssel gilt.

[bearbeiten] Vigenere Verschlüsselung

Im Aufbau gleich wie Cäsar aber eine Polyalphabetische substitution.

 Bsp.
 KEY: TEST
 KT: DINGDONG
 Funktion: c(X,Y) => Caesar verschiebung von Y um X buchstaben
 GT: c(D,T) c(I,E) c(N,S) c(G,T) c(D,T) c(O,E) c(N,S) c(G,T)

[bearbeiten] Sie kennen zwei Methoden der Kryptoanalyse (Brute-Force und Häufigkeitsanalyse) und können diese auf verschlüsselte Texte anwenden

[bearbeiten] Bruteforce

Dabei wird jede mögliche kombination ausprobiert und verglichen.

 Bsp:
 Bei der Cäsar verschlüsselung wird der GT mit allen 25 möglichen Kombinationen entschlüsselt,
 einer der 25 Texte sollte sinn machen und lesbar sein.

Durch BF ist jeder algorithmus angreifbar, die Sicherheit bestimmt sich dadurch, ob es in einer vernünftigen Zeit möglich ist einen Text mithilfe von Bruteforce entschlüsseln (siehe DES, nicht gecknackt aber denoch wegen BF unsicher).

[bearbeiten] Häufigkeitsanalyse (frequency distribution)

Dabei wird auf die Häufigkeitsverteilung der einzelnen Buchstaben, Digrammen, Trigrammen usw... in der Sprache gesetzt.

Die Häufigkeitstabelle muss von einem möglichst grossen Text aus der jeweiligen Sprache erstellt werden, wobei am Schluss zu jedem Buchstaben eine Relative Häufigkeit (vorkommen im Text) in Prozent zugewiesen werden kann.

Wird das gleiche auf den GT angewendet (vorausgesetzt er ist genügend lang), kann durch vergleich der Häufigkeit ein Rückschluss auf die substitution gemacht werden.

[bearbeiten] Algorithmus I zum Knacken monoalphabetischer Chiffren

Construct initial key guess k, based upon symbol frequencies of the expected language
let v = f(dk(c))
let k’ = k
change k’ by swapping two elements a and b
if v’ < v let v = v’ and k = k’
goto step 3

für f könnte zB. die Funktion $f(t)=\sum_{i,j}\left|D_{ij}(t)-E_{ij}\right|$ verwendet werden.

[bearbeiten] Sie beherrschen die Begriffe „One-Time-Pad“ und „Nur-Chiffretext-Angriff“

[bearbeiten] One-Time-Pad

Der schlüssel is gleich lang wie der KT, somit ist er auch gegen Bruteforce geschützt.

Die Fragestellung ist nur, dass der Schlüssel sicher Transportiert werden muss und daher ist diese Verschlüsselung nur bedingt von nutzen.

[bearbeiten] ciphertext-only-attack

Dabei hat Mallory (Der Angreifer) nur den Verschlüsselten Text sowie die Methoden zur Ver- und Entschlüsselung zur verfügung.

[bearbeiten] Sie können Kryptoanalyse-Szenarien als Matrizenrechung darstellen und damit eine monoalphabetische Chiffre schnell und systematisch knacken

[bearbeiten] Sie können das „One-Time-Pad“ in einer beliebigen Programmiersprache umsetzen

[bearbeiten] Woche 3 - Zahlentheoretische Grundlagen: Basic Skills

[bearbeiten] Sie können den Unterschied zwischen einem Ring und einer Gruppe erklären

Eine Gruppe hat eine binäre $\oplus$ Operation und erfüllt die Axiome

Abgeschlossenheit: $a\oplus b \in g$
Assoziativität: $a\oplus (b \oplus c) = (a \oplus b) \oplus c$
Neutrales Element: $e\oplus e' = e$
Inverses Element: $e\oplus e' = 1$

Für kommutative Gruppen muss zudem noch gelten: $a\oplus b = b \oplus a$

Ein Ring hat 2 binäre Operationen ( $\oplus$ und $\otimes$ ) und erfüllt die Axiome kommutative Gruppe für $\oplus$ , Abgeschlossenheit, Assoziativität und Neutrales Element für $\otimes$ sowie das Distributivgesetz für $\oplus$ und $\otimes$ .

[bearbeiten] Sie sind in der Lage nachzuvollziehen, dass ein algebraischer Objekt ein Ring (oder eben nicht) ist

Durch Prüfen ob die entsprechenden Axiome zutreffen oder nicht.

[bearbeiten] Sie wissen, dass die Menge der ganzen Zahlen mod n u.U.einen Ring bildet

[bearbeiten] Sie können eine Addition und eine Multiplikation auf Elementen in diesem für Sie neuen Ring definieren und verwenden

Man kann die Normalen +, -, * Operationen verwenden aber jede Zahl muss immer modulo n gerechnet werden.

[bearbeiten] Sie kennen den Begriff der „Schnellen Exponentiation“

Exponent wird durch Zerlegung (üblicherweise in Quadrate) schrittweises abgebaut:

Die resultierenden Exponenten sind kleiner und können einfacher modular behandelt werden.

[bearbeiten] Sie können den Unterschied zwischen der herkömmlichen und der „schnellen“ Exponentiation aufführen

Herkömliche:

kann sehr grosse Zahlen geben
rechenintensiv

Schnelle:

die Zahlen bleiben kleiner
Weniger Operationen
Integer können nicht überlaufen wegen modularer Multiplikationen

[bearbeiten] Sie können die Schnelle Exponentiation anwenden

 Bsp:

[bearbeiten] Woche 4 - Moderne Blockch. und ihre Betriebsarten: DES

[bearbeiten] Sie kennen den Begriff DES und die wichtigsten Meilensteinen in seiner Geschichte (Entstehung, Verwendung und Angriffe)

[bearbeiten] History

Wurde Anfang der 70er jahre bei IBM in den USA Entwickelt
Am 15 Januar 1977 wurde deer DES vom NIST zum Standart für Datenverschlüsselung annerkant
Am 18 Juni 1997 wurde die eeerste erfolgreiche Known-Plaintext-Attacke durchgeführt
Heute gilt der DES als nicht mehr Sicher

[bearbeiten] Chronologie

Datum		Ereignis
15. Mai	1973	Das NBS veröffentlicht eine erste Ausschreibung für ein standardisiertes Verschlüsselungsverfahren
27. August	1974	Das NBS veröffentlicht eine zweite Ausschreibung für ein standardisiertes Verschlüsselungsverfahren
17. März	1975	DES wird im „Federal Register“ veröffentlicht
August	1976	Erster Workshop zu DES
September	1976	Zweiter Workshop, welcher die mathematischen Grundlagen von DES behandelt
November	1976	DES wird als Standard zugelassen
15. Januar	1977	DES wird als FIPS-Standard „FIPS PUB 46“ veröffentlicht
	1983	DES wird das erste mal neu bestätigt
	1986	Videocipher II, ein auf DES basierendes Verschlüsselungssystem für Fernsehsatelliten wird von der HBO verwendet
22. Januar	1988	DES wird als „FIPS 46-1“ revalidiert, welches FIPS PUB 46 ersetzt
	1992	Biham und Shamir publizieren den ersten theoretischen Angriff mit gegenüber der Brute-Force-Methode verminderter Komplexität: die differentielle Kryptanalyse. Dieser Angriff erfordert jedoch unrealistische 2⁴⁷ frei gewählte Klartexte.
30. Dezember	1993	DES wird ein drittes Mal bestätigt, diesmal als „FIPS 46-2“
	1994	Die erste experimentelle Kryptoanalyse von DES wird mittels linearer Kryptoanalyse durchgeführt (Matsui, 1994)
Juni	1997	Das DESCHALL-Projekt bricht erstmals öffentlich eine mit DES verschlüsselte Nachricht
Juli	1998	Der DES-Knacker „Deep Crack“ der EFF bricht einen DES-Schlüssel binnen 56 Stunden
Januar	1999	Deep Crack und distributed.net brechen in einer Kooperation einen DES-Schlüssel in 22 Stunden und 15 Minuten
25. Oktober	1999	DES wird ein viertes Mal in Gestalt des „FIPS 46-3“ bestätigt. Dieser gibt als bevorzugte Anwendung 3DES an und erlaubt DES selbst nur für den Einsatz in veralteten Systemen
26. November	2001	Der Advanced Encryption Standard wird als „FIPS 197“ publiziert
26. Mai	2002	Der AES tritt in Kraft
26. Juli	2004	Im „Federal Register“ wird die Absetzung des FIPS 46-3 und verwandter Standards empfohlen
19. Mai	2005	NIST setzt den FIPS 46-3 außer Kraft
März	2006	Der FPGA-basierte Parallelrechner COPACOBANA kostet weniger als 10.000 Dollar (Materialkosten) und bricht DES in weniger als 9 Tagen

[bearbeiten] Verwendung

Blockchiffre
64-Bit Blöcke
56-Bit Schlüssel
16 Runden

[bearbeiten] Angriffe

Known-Plaintext-Attacke (Vollständige Schlüsselsuche)
Differenzielle Kryptoanalyse (gehört zu den Choosen-Plaintext-Attacken)
Lineare Kryptoanalyse (gehört zu den Choosen-Plaintext-Attacken)

[bearbeiten] Sie kennen die Anatomie vom DES: Aufbau, Anzahl Runden, Verschlüsselungs- und Entschlüsselungsprozess, Schlüsselgenerierung, Begriff der Diffusion sowie all die wichtigsten Grössen (z.B. Block- und Schlüsselgrösse und Grösse des Schlüsselraums)

Die Nachricht wird in 64-Bit-Blöcke zerlegt. Beim ECB und CBC wird der letzte Block auf volle 64 Bits ergänzt bzw. ein weiterer Block angefügt. Zum Auffüllen wird die Bitfolge 1000… verwendet.

Diese Paddingvorschrift ist eindeutig umkehrbar, das heißt, die Füllbits können nach dem Entschlüsseln wieder entfernt werden.

[bearbeiten] Sie wissen, dass der DES nie gebrochen wurde und dass er nicht desto trotz die heutigen Sicherheitsansprüche nicht erfüllt

Da er in "nützlicher" Zeit durch Bruteforce umgangen werden kann.

[bearbeiten] Sie beherrschen jedes Detail der so genannten S-Boxes

[bearbeiten] Sie können erklären, was mit dem Begriff „Betriebsart“ gemeint wird

Die Nachricht wird in 64-Bit-Blöcke zerlegt. Beim ECB und CBC wird der letzte Block auf volle 64 Bits ergänzt bzw. ein weiterer Block angefügt. Zum Auffüllen wird die Bitfolge 1000… verwendet. Diese Paddingvorschrift ist eindeutig umkehrbar, das heißt, die Füllbits können nach dem Entschlüsseln wieder entfernt werden.

[bearbeiten] ECB

Electronic Code Book. Die Blöcke werden jeweils mit dem gleichen Schlüssel unabhängig von einander verschlüsselt. Hierdurch entstehen bei Chiffrierung gleicher Klartextblöcke auch gleiche Chiffretextblöcke. Übertragungsfehler in einem Block wirken sich nur dann auf andere Blöcke aus, wenn hierbei fälschlich die Anzahl der Bits verändert wird.

[bearbeiten] CBC

Cipher Block Chaining Mode. Vor der Verschlüsselung wird der Klartextblock mit dem zuvor verschlüsselten Block verknüpft (XOR-Verknüpfung). Der erste Klartextblock wird mit dem Initialisierungsvektor IV verknüpft. Der IV wird zur Entschlüsselung benötigt, muss jedoch nicht geheim gehalten werden. Dadurch entsteht eine Verkettung (englisch chain) der Blöcke. Trotz dieser Verkettung wird bei einem Übertragungsfehler in einem Chiffrenblock nur der betroffene Block und der nachfolgende falsch entschlüsselt. Fehler/Manipulationen in einem Block wirken sich also bei der Entschlüsselung nur auf den fehlerhaften/manipulierten und den nächsten Block aus. Trotzdem gilt, dass durch eine einzige Änderung im Klartext sich alle nachfolgenden Blöcke in der Folge stark verändern. Ein Angreifer kann daher die Chiffre kaum unbemerkt verändern, ohne dass danach zwei Blöcke erkennbar manipuliert sind. In keinem Fall sind gezielte Veränderungen ohne Kenntnis des Schlüssels möglich. Durch Verwendung eines verschlüsselten Prüfwerts (zum Beispiel CRC) wird dies mit höchster Sicherheit ausgeschlossen.

[bearbeiten] OFB

Output Feedback Mode. In diesem Modus wird eine Zufallsfolge erzeugt. Dazu wird ein Initialisierungsvektor IV verschlüsselt, das Ergebnis erneut verschlüsselt etc. Die Verschlüsselung erfolgt durch XOR-Verknüpfung der Zufallsfolge mit dem Klartext. Der IV darf nur einmalig verwendet werden. Diese Verfahren entspricht einer Stromchiffre vergleichbar zu RC4. Übertragungsfehler führen beim OFB lediglich zur falschen Dechiffrierung einzelner Zeichen, eine Veränderung der Bitanzahl kann jedoch ohne explizite Resynchronisierung nicht korrigiert werden.

[bearbeiten] CFB

Cipher Feedback Mode. Hier wird wie beim OFB eine Zufallsfolge erzeugt und zur Verschlüsselung per XOR-Verknüpfung genutzt. Jedoch wird die Chiffre zur Berechnung der Zufallsfolge verwendet (daher die Bezeichnung Cipher Feedback). Gegen Übertragungsfehler ist CFB ähnlich wie CBC resistent.

[bearbeiten] Sie haben verstanden, was ein Replay-Angriff ist

Ein Replay-Angriff (Angriff durch Wiedereinspielung) ist eine kryptoanalytische Angriffsform auf die Authentizität von Daten in einem Kommunikationsprotokoll. Hierbei sendet der Angreifer zuvor aufgezeichnete Daten, um etwa eine fremde Identität vorzutäuschen. [Wikipedia]

[bearbeiten] Sie kennen vier Betriebsarten (und können detailliert die jeweilige Funktionsweise angeben) und den Begriff Stromchiffre

[bearbeiten] stream cipher

Jeder Buchstabe bzw. jedes Bit des KT wird mit einem Buchstaben bzw. Bit des Schlüssels verknüpft (meistens durch XOR).

Stromchiffren werden unsicher, wenn der Schlüssel mehrmalig verwendet wird.

[bearbeiten] Feistel Funktion

Die F-Funktion von DES arbeitet auf Halbblöcken zu je 32 Bits und besteht aus vier Phasen:

Die Halbblöcke werden mittels einer geeigneten Permutation E auf 48 Bits Länge expandiert, indem einzelne Bits mehrfach verwendet werden.
Das Ergebnis wird mit einem Teilschlüssel XOR-verknüpft. Für jede Runde wird hierzu nach einer festen Vorschrift ein anderer 48-Bit Teilschlüssel aus dem Hauptschlüssel generiert.
Die resultierenden Blöcke werden in acht 6-Bit-Stücke zerteilt und diese mittels Substitution durch S-Boxen auf eine Länge von 4 Bits komprimiert. Diese nicht-lineare Transformierung in den S-Boxen stellt das Herzstück der Sicherheit von DES dar, ohne sie wäre DES linear und trivial zu brechen.
Die 32 Bits Ausgabe der S-Boxen werden mittels einer festen Permutation P rearrangiert.

[bearbeiten] Woche 5 - Zahlentheoretische Grundlagen: Advanced Skills

[bearbeiten] Sie wissen, unter welchen Umständen zwei Zahlen a und b teilerfremd sind

Wenn der ggt(a,b) = 1 ist, sind die Zahlen a und b Teilerfremd (relativ prim)

[bearbeiten] Sie wissen, was mit dem Begriff des „multiplikativen Inversen“ in dem Ring (Zn,+,*) gemeint wird

Es existiert ein $\exists X (x=a^{-1} \mod n)$

x ist invers zu a, wenn $x*a \equiv_{n} 1$ .

Inverse werden mit dem Erweiterten Euklidschen Algorithmus oder der schnellen Exponentiation von $x \equiv_n a^{-1} \equiv_n a^{\varphi(n)-1}$ berechnet.

Für prime n heisst das: $a^{-1} = a^{n-2} \mod n$

minv.jar ist eine kleine Demo Applikation, die zeigt wie man das Multiplikative Inverse berechnet.

[bearbeiten] Sie wissen was die reduzierte Menge der Reste modulo n ist und wissen, wann ein multiplikatives Invers zu a modulo n existiert

Die reduzierte Menge ist die Untermenge einer Menge, welche teilerfremd zum Modulus der Übermenge ist. $\Z^*_n = \{a \in \Z_n | \operatorname{ggT}(a,n) = 1\}$

[bearbeiten] Sie kennen die Bedeutung der Euler’sche φ-Funktion, und können ihr Wert für einige Spezialfälle von n berechnen

Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen $a \le n$ zu ihr teilerfremd sind und bildet eine kommutative multiplikative Gruppe

$\varphi(n) \; := \; \Big| \{ 1 \le a \le n \, |\, \operatorname{ggT}(a,n) = 1 \} \Big|$

Berechnung der Funktion für p = Primzahl:

[bearbeiten] Sie kennen die Sätze von Fermat und Euler sowie ihre Bedeutung bei der Berechung eines multiplikativen Inverses im Ring (Zn,+,*) beschreiben

[bearbeiten] Satz von Fermat

Für p = Primzahl und ggt(a,p)=1 gilt

[bearbeiten] Satz von Euler

Für ggt(a,n) gilt

Für $r_1 \equiv_n \varphi(n) = r_2 \equiv_n \varphi(n)$ gilt

Für $a*x\equiv_n 1$ gilt

 
 Falls n = prim gilt weiter
  $x = a n - 2$

[bearbeiten] Zusammenhang im Ring

Für $a \in \Z, n \in \N^*, ggt(a_n)=1$ gilt

Vorraussetzung für inverses Element

[bearbeiten] Sie können die Sätze von Fermat und Euler anwenden, um ein multiplikatives Invers im Ring (Zn,+,*) für die dazugehörigen Spezialszenarien zu berechnen

[bearbeiten] Sie kennen einen Algorithmus, um systematisch ein multiplikatives Invers modulo n zu berechnen

Erweiterter Eukli'dscher Algotithmus:

Bestimme ggt(a,n)
Rückwärtseinsetzung (Siehe Bsp)
Alles modulo n

 Bsp:
 11 mod 26  a=11, n=26
 1) ggt(11,26)
    26 = 2 * 11 + 4
    11 = 2 * 4  + 3
    4  = 1 * 3  + 1  ggt(11,26) = 1
 2) 1 = 4 - 1 * 3 = 4 - 1 * (11 - 2 * 4) = 3 * 4 - 1 * 11 = 3 * (26 - 2 * 11) - 1 * 11 = 3 * 26 - 7 * 11
 3) 1 = 3 * 26 - 7 * 11  1 mod 26 = -7 * 11 mod 26
 
 x = -7 mod 26 = 19
 (19 * 11 mod 26 = 209 mod 26 = 1)

[bearbeiten] Sie wissen, was eine modulare Gleichung ist

 Bsp: 
  $g g t (6,15)$ 
    $15 = 2 * 6 + 3$ 
   
   
     note:

[bearbeiten] Sie sind in der Lage ein Vorgehen anwenden und interpretieren zu können, um modulare Gleichungen zu lösen

Lösung modularer Gleichungen a * x mod n = b

Falls $g g T (a, n) = 1$ -> erweiterter Euklidischer Algorithmus, 1 Lösung: $x=a^{-1}*b \mod n$
Falls
1. ggT kein Teiler von b ->keine Lösung
2. sonst g Lösungen...

Formeln:

[bearbeiten] Woche 7 - (Kryptografische) Hashfunktionen

[bearbeiten] Sie kennen eine informale Definition einer „Hashfunktion“ sowie die wichtigsten (z.T. äquivalenten) darin vorkommenden Begriffe

Eine Hashfunktion ist eine Funktion $h$ , welche die folgenden beiden Eigenschaften erfüllt

Die Funktion $h$ bildet Eingaben $x$ einer belieebigen bitlänge auf Ausgaben $h (x)$ (auch Fingeeerabdruck gennant) einer festen Länge ab.
Wenn $x$ und $h$ gegeben sind, ist $h (x)$ leicht zu berechnen.

  $h (x)$  = Hashwert = Message Digest = Fingerprint

[bearbeiten] Sie wissen, dass eine Hashfunktion leicht zu berechnen sein muss und wissen, dass diese so ausgewählt werden muss, dass sie nicht fälschbar ist

[bearbeiten] Sie beherrschen die Begriffe „Kollision“ und „Kollisionsresistenz“

Eine Kollision ist, wenn gilt $h (x) = h (y)$
Kollisionsresistent bedeutet, dass es keinen Effizienten Algorithmus gibt um eine Kollision zu finden (Suche nach y zu gegebenem x)

[bearbeiten] Sie kennen die Bedingungen, welche Hashfunktionen erfüllen müssen, damit sie als „schwach“ bzw. „stark Kollisionsresistent“ gelten und kennen die Definition von „kryptografischer Hashfunktion“

[bearbeiten] Starke Kollisionsresistenz

Es existiert kein effizienter Algorithmus zum Finden eines $M 1$ zu einem gegebenen $M 2$ , für welches $h (M 1) = h (M 2)$ gilt.

[bearbeiten] Starke Kollisionsresistenz (= kryptografische Hashfunktion)

Es existiert kein effizienter Algorithmus zum Finden eines $M 1$ zu einem beliebigen $M 2$ , für welches $h (M 1) = h (M 2)$ gilt

[bearbeiten] Sie können die Hashfunktionen MD4, MD5, SHA-1 und RIPEMD-160 nennen und kennen die Grösse der entsprechenden Fingerabdrücken

[bearbeiten] MD4 (RFC 1320)

 Fingerprint: 128-Bit (16-Byte)
 Kollisionswarscheinlichkeit P nach:  $264$

[bearbeiten] MD5 (RFC 1321)

 Fingerprint: 128-Bit (16-Byte)
 Kollisionswarscheinlichkeit P nach:  $264$

[bearbeiten] SHA-1 (RFC 3174)

 Fingerprint: 160-Bit
 Kollisionswarscheinlichkeit P nach:  $280$

[bearbeiten] RIPEMD-160

 Fingerprint: 160-Bit
 Kollisionswarscheinlichkeit P nach:  $280$

[bearbeiten] Sie sind in der Lage, das Geburtstagsproblem zu lösen und kennen dessen Ergebnisse (samt Formel) auswendig

Allgemein ausgedrückt ist die Wahrscheinlichkeit $P$ , mit der mindestens eine Person von $n$ anwesenden Personen an einem bestimmten Tag Geburtstag hat:

Wahrscheinlichkeit, dass mindestens zwei Personen an einem Tag Geburtstag haben:

Anders ausgedrückt:

[bearbeiten] Sie beherrschen den Geburtstagsangriff und sind in der Lage anhand dieser Methode Kollisionen einer Hashfunktion zu finden; sie wissen mit welcher Wahrscheinlichkeit und wie schnell es passiert

Anz. Operationen zum finden einer beliebigen (nicht ausgewählten) Kollision für eine Schlüssellänge von m Bits:

[bearbeiten] Woche 8 - Exponentialchiffre und das RSA-Public-Key-Kryptosystem

[bearbeiten] Sie kennen die Definition von Exponentiationschiffre

Blockweise Chiffrierung mit dem Schlüssel {m,e} und Blocklänge ld(n)+1

  $C = E (M) = M e m o d (n)$ 
  $M = D (C) = C d m o d (n)$

Dechiffrierung mit dem Schlüssel {d,n} $ed mod(\varphi(n))=1$

funktioniert wegen dem Satz $(M e m o d (n)) m o d (n) = M$ Wegen Kommutativität der Exponenten gilt daher auch E(D(M))=D(E(M)).

[bearbeiten] Sie können Pohlig-Hellman charaktierisieren anwenden und wissen, dass es eine symmetrische Chiffre ist

[bearbeiten] Key generation

Schlüsselpaare {p,e},{p,d} erzeugen

p := grosse Primzahl
Wähle e mit $1 \le e\le p-2$ und $g g t (e, p) = 1$
$d=e^{-1} mod(\varphi(p))$
Chiffrierschlüssel = {p,e}
Dechiffrierschlüssel = {p,d}
e und d sind geheim zu halten

[bearbeiten] Verschlüsselung

$C = M e m o d (p)$

[bearbeiten] Enschlüsselung

$M = C d m o d (p)$

[bearbeiten] Beispiel

 Geg: p=23, e = 9, M = 16
 (23) = 22, da 23 prim
  $d = e - 1 m o d (22)$  => ggt(22,9)
   22 = 2*9+4
   9  = 2*8+1 => 1 = 9-2*(22-2*9) mod(22)
                 1 = 9-2*22+4*9   mod(22)
                 1 = 5*9 =>  $e - 1 = d = 5$ 
 
 M = 16

[bearbeiten] Sie können erklären, was mit „Schlüsselaustauschproblem“ gemeint wird

Wie kann ein gemeinsamer Schlüssel zwischen 2 parteien "sicher" über einen "unsicheren" Kanal ausgetauscht werden?

[bearbeiten] Sie kennen den Begriff „Public Key Kryptosystem“ (und die Synonyme)

[bearbeiten] Sie kennen Schlüsselpaare und können sie beschreiben

[bearbeiten] Sie wissen wie PKK die Authentizität und Geheimhaltung gewährleisten können

[bearbeiten] Sie können den Begriff der digitale Signatur beschreiben

[bearbeiten] Sie können das RSA-Verfahren charaktierisieren und verwenden

Beruht auf der Schwierigkeit n in p und q zu faktorisieren. p sollte etwa gleich gross wie q sein (ca. 512 bit)

[bearbeiten] Key Generation

Erzeugen von Primzahlen p,q
$n = p * q$ und $\varphi(n) = (p-1)*(q-1)$
Wahl von e mit $1 < e < \varphi(n)$ , mit $ggT(e,\varphi(n)) = 1$
$d = e^{-1} mod(\varphi(n))$

 Public Key  = (e,n)
 Private Key = (d,n)

[bearbeiten] Verschlüsselung

  $C = E (M) = M e m o d (n)$

[bearbeiten] Entschlüsselung

  $M = D (C) = M d m o d (n)$

[bearbeiten] Signatur

  $S = D (M) = M d m o d (n)$ , {M|S} wird übermittelt

[bearbeiten] Signatur-Verifikation

  $M' = E (S) = S e m o d (n)$  muss = M sein

[bearbeiten] Sie können die mathematische Grundlage von RSA aufführen

[bearbeiten] Sie können eine Erklärung für die Sicherheit von RSA aufführen

[bearbeiten] Sie können den chinesischen Restsatz verstehen und anwenden

[bearbeiten] Woche 9 - Diskreter Logarithmus und kryptografische Anwendungen

[bearbeiten] Sie können erklären, was eine zyklische Gruppe ist und wissen, was die Ordnung eines Elements in einer Gruppe ist

Zyklische Gruppe mit Generator G

[bearbeiten] Sie können die Ordnung eines Elements in einer Gruppe bestimmen

[bearbeiten] Sie kennen die Definition von primitiver Wurzeln modulo p und wissen, warum diese in der Kryptografie wichtig sind

Der kleinste Exponent i, welcher für welcher gilt $g^i\equiv_n 1$ bestimmt die Ordnung des Elementes g (zB. 3^7 mod 7 = 1 -> Ordnung = 6).

Ist die Ordnung = n-1, spricht man von primitiver Wurzel.

[bearbeiten] Anzahl primitiver Wurzeln in $\Z_p$

ACHTUNG: $\varphi(p-1)$ ist meist NICHT prim!

[bearbeiten] Sie kennen die Definition vom Begriff „diskreten Logarithmus“

Wie der normale Logarithmus, mit der besonderheit, das es nur Ganzzahlige werte modulo n sind

[bearbeiten] Sie kennen einen naiven Ansatz, um diskrete Logarithmen zu berechnen

[bearbeiten] Sie können das Zahlenkörpersieb als schnellste Methode nennen, um einen diskreten Logarithmus zu berechnen

[bearbeiten] Sie können das ElGamal-Public-Key-Kryptosystem als Verschlüsselungsund Signaturverfahren anwenden

Basiert auf Schwierigkeit, diskrete Logarithmen zu finden und dient der Verschlüsselung und Signatur (beinhaltet dazu zwei Verfahren).

[bearbeiten] Key Generation

Wähle p und berechne $q=2*p+1 |\{p,q\}\in P$
Wähle zufälliges $x\in \{1,...,q-2\}$
Berechne $y = g x m o d (p)$

 Public Key  = {p,g,y}
 Private Key = {x}

[bearbeiten] Chiffrierung

$M\in \Z_p$
Wähle zufälliges k mit $k\in \{1,...,p-2\}$
Berechne
1. $a = g k m o d (p)$
2. $b = M * y k m o d (p)$
C = {a,b}

[bearbeiten] Dechiffrierung

$z = (a x) - 1 m o d (p)$
$M = D (C) = z * b m o d (p)$

[bearbeiten] Signieren

Wähle zufällige Zahl k wobei gelten muss:
1. $k\in \{1,...,p-2\}$
2. ggt(k, p-1)=1
$r = g k m o d (p)$
$k - 1 m o d (p - 1)$
Es muss gelten: $M\in \Z^*_p$
$s = (M - x * r) * k - 1 m o d (p - 1)$

[bearbeiten] Signatur Prüfen

Bob holt public Key {p,g,y} mit $y = g x m o d (p)$
Wenn wird nicht abgebrochen
1. $v 1 = y r * r s m o d (p)$
2. $v 2 = g M m o d (p)$
3. Ist $v 1 = v 2$ , ist die Signatur gültig

[bearbeiten] Sie können den Schlüsselaustausch nach dem Protokoll von Diffie und Hellman durchführen

Löst das Problem des Schlüsselaustausches (Key Management Overhead).

Algorithmus zum Schlüsselaustausch, bekannt sind g und p

$\{x_a, x_b\}\in \{1,...,p-2\}$ , p ist eine grosse Primzahl
$Y_a=g^{x_a} mod(p)$ und $Y_b=g^{x_b} mod(p)$
$K_{ab}=Y^{x_a}_b mod(p) = Y^{x_b}_b mod(p)$

Knackbar mit subexponentieller Komplexität.

[bearbeiten] Sie wissen, worauf die Sicherheit des ElGamal-Public-Key-Kryptosystems bzw. des Schlüsselaustauschs nach Diffie und Hellmann beruht

[bearbeiten] TI Funktionen

Basic sourcen kommen noch...

[bearbeiten] Erweiterter Euclid

 euclid(x,m) => Programm Ausgabe mit Zwischenschritten
 egcd(x,m) => Funktion retourniert endresultat als string

[bearbeiten] Multiplikatives Invers

 minv(x,m) => Funktion retourniert endresultat

 minv(a_,m_)
 Func
 Local i_:a_->i_
 While mod(i_,m_) 1
   i_+a_->i_
 EndWhile
 Return i_/a_
 EndFunc

[bearbeiten] Euler'sche $φ(n) F u n k t i o n$

 phi(n) => Funktion retourniert endresultat

 phi(a_)
 Func
 Local i_,j_:1->i_:0->j_
 While i_<=a_
   if gcd(i_,a_)=1 Then
     j_+1->j_
   EndIf
   i_+1->i_
 EndWhile
 Return j_
 EndFunc

[bearbeiten] Primfaktoren zerlegung

 primes(x) => Programm Ausgabe der Primfaktoren

Von „http://study.2030.tk/wiki/Fach:AK_Lernziele“

Kategorie: AK