Fach:AK Stundenlogs

Aus StudyWiki

Inhaltsverzeichnis

1 01.09.2008 - Begriffsbildung in der Kryptologie
2 07.09.2008 - Enigma
- 2.1 Aufgaben
- 2.2 Weblinks
3 Woche 3 - Zahlentheoretische Grundlagen: Basic Skills
- 3.1 Übungsserie
  - 3.1.1 Aufgabe 1
    - 3.1.1.1 a
    - 3.1.1.2 b
    - 3.1.1.3 c
    - 3.1.1.4 d
    - 3.1.1.5 e
    - 3.1.1.6 f
  - 3.1.2 Aufgabe 2
  - 3.1.3 Aufgabe 3
    - 3.1.3.1 a
    - 3.1.3.2 b
  - 3.1.4 Aufgabe 4
  - 3.1.5 Aufgabe 5
    - 3.1.5.1 a
    - 3.1.5.2 b
  - 3.1.6 Aufgabe 6
  - 3.1.7 Aufgabe 7
4 DES
5 10.11.08 - Hash functions
6 17.11.08 - RSA

[bearbeiten] 01.09.2008 - Begriffsbildung in der Kryptologie

Unterlagen: Sieben Wunder der Informatik, Kapitel 7

 Kryptologie ist die Lehre der Geheimsprachen

[bearbeiten] CAESAR

Das GTA (Geheimtextalphabet) wird unterhalb des KTA (Klartextalphabet) aufgeschrieben, wobei das GTA um KEY (Schlüssel) Positionen zum KTA verschoben ist.

Wenn man GTA und KTA von 0 bis 25 durchnummeriert, kann man mit folgenden Funktionen ver- und entschlüsseln

Verschlüsselungsfunktion:

 GTA.Wert = (KTA.Wert + KEY) mod 26

Entschlüsselungsfunktion:

 KTA.Wert = (GTA.Wert - KEY + 26) mod 26

Wobei .Wert der Buchstabe an der Jeweiligen Position ist.

[bearbeiten] Definition von Sicherheit

Kerckhoffs-Prinzip (Auguste Kerckhoffs, 19. Jahrhundert)

 Ein Kryptosystem ist sicher, 
 wenn man trotz öffentlich bekanntem Verschlüsselungsverfahren 
 ohne die Kenntnis des Schlüssels aus empfangenen Kryptotexten 
 die ursprünglichen Klartexte nicht ableiten kann.

[bearbeiten] Aufgaben

[bearbeiten] A7.1

[bearbeiten] a)

 i=5:  AJSNANINANHN
 i=17: MVEZMZUZMZTZ

[bearbeiten] B)

 i=7:  YVTH HLALYUH KVJLA
 i=13: UBZVARF FHZHF, ABA QRV!

i=13 ist ein Sonderfall der bei 2fachem Verschlüsseln wieder zum Klartext führt, auch bekannt unter ROT13

[bearbeiten] A7.2

 i=7: PRIMUMUTPROGICEAS

[bearbeiten] A7.3

[bearbeiten] a)

 DANTEALIGHIERI

[bearbeiten] b)

 GEDULDISTDERSCHLUESSELFUERFREUDE

[bearbeiten] A7.4

$\oplus$ bedeuted XOR

${{\oplus \begin{matrix} 0&0&0&1&1&1&0&0&1&1 \\ 0&1&0&1&1&0&1&0&0&1 \end{matrix}} \over {\quad \begin{matrix} 0&1&0&0&0&1&1&0&1&0 \end{matrix}}}$

[bearbeiten] A7.5

[bearbeiten] a)

$\perp$ ist unsere definierte Maskierungsoperation (in diesem beispiel ein logisches AND)

Encrypt: ${{\perp \begin{matrix} 0&0&1&1&0&0&1&1 \\ 0&0&1&0&1&1&0&1 \end{matrix}} \over {\quad \begin{matrix} 1&1&1&0&0&0&0&1 \end{matrix}}}$ Decrypt: ${{\perp \begin{matrix} 1&1&1&0&0&0&0&1 \\ 0&0&1&0&1&1&0&1 \end{matrix}} \over {\quad \begin{matrix} 0&0&1&1&0&0&1&1 \end{matrix}}}$

[bearbeiten] b)

Es ist ein Logisches AND und somit bei 2 facher Anwendung wieder wirkungslos.

[bearbeiten] c)

Es sind beides Logische Operationen und wie ROT13 bei 2facher Anwendung wirkungslos.

[bearbeiten] A7.6

 KT: 1010 (Kryptotext)
 Key: 10010101 wobei er in K1: 1001 und K2: 0101 Aufgeteilt werden kann

Verschlüsselungsverfahren:

 Es gibt 2 Runden mit XOR, 1. Runde mit K1 danach das Resultat in der 2ten Runde mit K2

[bearbeiten] A7.7

B gibt (durch den Boten) A ein offenes Schloss
A schliesst den Kasten mit diesem Schloss und gibt ihn zurück

Der Bote braucht nur 2 * 3 Laüfe anstelle von 3 * 3

[bearbeiten] A7.8

 KT: 01001101
 A: 01010101
 E: 10101010

1) A: ${{\oplus \begin{matrix} 0&1&0&0&1&1&0&1 \\ 0&1&0&1&0&1&0&1 \end{matrix}} \over {\quad \begin{matrix} 0&0&0&1&1&0&0&0 \end{matrix}}}$ 2) E: ${{\oplus \begin{matrix} 0&0&0&1&1&0&0&0 \\ 1&0&1&0&1&0&1&0 \end{matrix}} \over {\quad \begin{matrix} 1&0&1&1&0&0&1&0 \end{matrix}}}$ 3) A: ${{\oplus \begin{matrix} 1&0&1&1&0&0&1&0 \\ 0&1&0&0&1&1&0&1 \end{matrix}} \over {\quad \begin{matrix} 1&1&1&0&0&1&1&1 \end{matrix}}}$ 4) E: ${{\oplus \begin{matrix} 1&1&1&0&0&1&1&1 \\ 1&0&1&0&1&0&1&0 \end{matrix}} \over {\quad \begin{matrix} 0&1&0&0&1&1&0&1 \end{matrix}}}$

[bearbeiten] A7.9

Ja, da es eine Logische Funktion ist die bei 2facher Anwendung wieder zum ursprung kommt.

[bearbeiten] A7.10

 p=13
 q=17
 n=13*17=221

$f_n(100)=100^2 \quad mod \quad 221 = 166$

$y^2 \quad mod \quad 221 = 166$

 Ich verzichte auf die Lösung von allen Y ;-)

[bearbeiten] A7.11

K generiert einen Hash des Dokuments und verschlüsselt diesen mit seinem Private key
B entschlüsselt den Hash mit dem Public key von K und vergleicht die 2 Hash werte

[bearbeiten] A7.12

K generiert einen Hash des Dokuments und verschlüsselt es mit seinem Private key, danach verschlüsselt er beides mit dem Public key von B
B entschlüsselt das Dokument mit seinem Private key und entschlüsselt den Hash mit dem Public key von K, danach erstellt er einen Hash des Dokuments und vergleicht ihn

[bearbeiten] A7.13

K nimmt B's Public key und verschlüsselt ihn mit seinem Private key
B entschlüsselt die Nachricht mit dem Public key von K und vergleicht den inhalt mit dem eigenen Public key

Durch die verwendung von B's Public key als verschlüsselter text kann B zwar bestätigen das K ihm das gesendet hat (da mit K's Public key entschlüsselt werden konnte), kann ihn aber nicht an jemand anders weitersenden und sich als K ausgeben

[bearbeiten] 07.09.2008 - Enigma

[bearbeiten] Aufgaben

[bearbeiten] A1 Vorteil und grobe Funktionsweise der Enigma

Rollentrennung zwischen Funker und Offizier
Grösstenteils automatische Verschlüsselung
Beim Anschlag einer Taste wird ein elektrischer Impuls ausgelöst, welcher sich über verschiedene Rollen mit Kontaktbürsten fortpflanzt und, der Rollenstellung entsprechend, ein Licht ein Licht auslöst, welches für den zu verwendenden Cyphertext-Character steht. Die Position der Rollen ändert sich dabei laufend.
Rotoren können gewechselt werden und haben konfigurierbare Anfangspositionen (welche vom Offizier dem Code Book entnommen werden)

[bearbeiten] A2 Rolle des Reflektors

Der REflektor schickt den Output der "rechten Seite" der Enigma nochmals gegen links durch die Rotoren um so vermeindlich die Entropie des Cyphertextes zu erhöhen. Möglicherweise wurde davon ausgegangen, dass so eine Verschlüsselung erzielt wird, welche der Verwendung von 6 Rollen entspricht. Ein negativer Seiteneffekt war jedoch, dass somit ein Zeichen vom Plaintext nicht mehr sich selber im Cyphertext zugeordnet werden konnte (plain(A) konnte nie cypher(A) sein), was von gegnerischen Kryptanalsten ausgenutzt werden konnte.

[bearbeiten] A3 Definition einer Periode

Ein endlicher Schlüsselraum, der gleichmässig traversiert wird, wiederholt sich nach einer Periode von maximal der Länge des Schlüsselraumes wieder. Im Falle der Enigma mit drei Rollen, wäre dies nach 25^3 = 17'576 Schlüsselwechseln (unter Verwendung dreier fixer Rollen).
Da allerdings noch ein Reflektor verwendet wurde, reduziert sich diese Zahl nochmals um 25^2 = 676, da die letzte Rolle nur 25 Zustände einnehmen kann. Somit erstreckt sich der effektive Schlüsselraum über 26*26*25 = 26^3-26^2 = 16'900

[bearbeiten] A4 Grösse eines Schlüsselraumes

Grundsätzlich z^n, wobei z die Anzahl möglicher Zustände und n die Schlüssellängedarstellt
Im Falle der Enigma 26^3
Zusätzlich erweitert um Faktor 10 durch die Verwendung von 3 aus 5 Rollen
Zusätzlich erweitert um 3! Möglichkeiten, die Rotoren einzubauen
Zusätzlich Permutation (allerdings invariant) auf dem Steckbrett: 26!/(13!*2^13)
Macht total ca. 8e18 Schlüssel

[bearbeiten] A5 Tatsächliche Grösse des Schlüsselraumes

Durch (menschliche) Auswahl schwacher Schlüssel wurde der Schlüsselraum faktisch erheblich reduziert, da
Spruchschlüssel sehr schwach gewählt
Unter Sysadmins als "Sonne3"-Effekt bekannt :)

[bearbeiten] A6 Max. Anz. Versuche für Brute Force

Noch immer 26e3-25e2 = 16'900

[bearbeiten] A7 Was ist eine polyalphabetische Substitution

Jedes Zeichen wird durch ein anderes ausgetauscht (substituiert), wobei für die Substitution für jeden Buchstaben (innerhalb einer vollen Periode) ein anderes Alphabet verwendet wird.
Entspricht etwa Ci = f1(f2(Pi)), wenn f2 der i-ten Position eines Buchstabens ein Alphabet zuweist und f1 die Substition durchführt.

[bearbeiten] Weblinks

[bearbeiten] Woche 3 - Zahlentheoretische Grundlagen: Basic Skills

[bearbeiten] Übungsserie

[bearbeiten] Aufgabe 1

Berechnen Sie die folgenden Werte:

 TI: mod(a,b)

[bearbeiten] a

$413 \mod 51$

[bearbeiten] b

$64 \mod 14$

[bearbeiten] c

$55 \mod 7$

[bearbeiten] d

$1400 \mod 23$

[bearbeiten] e

$-7 \mod 22$

 
 Vereinfachter fall da abs(-7) < 22 und negativ ist (aus der Ring Definition)

[bearbeiten] f

$-413 \mod 11$

[bearbeiten] Aufgabe 2

Bestimmen Sie den jeweiligen grössten gemeinsamen Teiler (den so genannten ggT) der Werte $a$ und $b$ ; dabei verwenden Sie den euklidischen Algorithmus; führen Sie alle Schritte an:

 TI: gcd(a,b)

[bearbeiten] a

$a = 45; b = 22$

 
  $22 = 22 * 1 + 0$

[bearbeiten] b

$a = 64; b = 12$

 
  $12 = 3 * 4 + 0$

[bearbeiten] c

$a = 53; b = 37$

  $53 = 1 * 37 + 16$ 
  $37 = 2 * 16 + 5$ 
 
  $5 = 5 * 1 + 0$

[bearbeiten] d

$a = - 5; b = 33$

 
 
 
 
  $2 = 2 * 1 + 0$

[bearbeiten] Aufgabe 3

[bearbeiten] a

Schreiben Sie ein Programm (egal in welcher Programmiersprache), das den ggT zweier Zahlen a und b berechnet.

[bearbeiten] b

Erweitern Sie Ihr Programm so, dass nicht nur die Lösung, sondern auch alle Zwischenschritte ausgegeben werden.

[bearbeiten] Aufgabe 4

Berechnen Sie jeweils das Resultat des folgenden Ausdrucks dank der schnellen Exponentiation. Führen Sie alle Schritte der Berechnung an.

[bearbeiten] a

$7^{12} \mod 15$

$7^{12} \equiv_{15} 7^8*7^4 \equiv_{15} ((7^2)^2)^2 * (7^2)^2 \equiv_{15} (4^2)^2*4^2 \equiv_{15} 1^2*1 \equiv_{15} 1$

[bearbeiten] b

$25^{20} \mod 7$

$25^{20} \equiv_{7} 4^{16} * 4^4 \equiv_{7} (((4^2)^2)^2)^2*(4^2)^2 \equiv_{7} ((2^2)^2)^2*2^2 \equiv_{7} (4^2)^2*4 \equiv_{7} 2^2*4 \equiv_{7} 4*4 \equiv_{7} 16 \equiv_{7} 2$

[bearbeiten] c

$10^{10} \mod 11$

$10^{10} \equiv_{11} 10^8*10^2 \equiv_{11} ((10^2)^2)^2*101^2 \equiv_{11} (1^2)^2*1 \equiv_{11} 1$

[bearbeiten] d

$8^{31} \mod 20$

$8^{31} \equiv_{20} 8^{16}*8^8*8^4*8^2*8 \equiv_{20} (((8^2)^2)^2)^2 * ((8^2)^2)^2 *(8^2)^2*8^2*8 \equiv_{20} ((4^2)^2)^2*(4^2)^2*4*8 \equiv_{20} (16^2)^2*16^2*4*8 \equiv_{20} \cdots$

$\cdots \equiv_{20} 16^2*16*4*8 \equiv_{20} 16*16*4*8 \equiv_{20} 16^2*4*8 \equiv_{20} 16*4*8 \equiv_{20} 512 \equiv_{20} 12$

[bearbeiten] Aufgabe 5

[bearbeiten] a

Entwickeln Sie ein Programm (egal in welcher Programmiersprache), das die schnelle Exponentiation a b mod c für die drei Eingaben a, b und c berechnet. Überprüfen Sie mit Ihrem Programm die von Ihnen berechneten Ergebnisse der Aufgabe 4.

[bearbeiten] b

Erweitern Sie Ihr Programm so, dass nicht nur die Lösung, sondern auch alle Zwischenschritte ausgegeben werden.

[bearbeiten] Aufgabe 6

Johann studiert gerade die Exponentiation in dem Ring Zn. Er beobachtet, dass um ${25 + 37} \mod 13$ zu berechnen er wie folgt vorgehen kann:

${25 + 37} \mod 13 = {(25 \mod 13) + (37 \mod 13)} \mod 13 = {12 + 11} \mod 13 = 23 \mod 13 = 10 \mod 13 = 10$

Jeder Summterm, der grösser als das Modulo ist, kann selber einer Modulo-Operation unterzogen werden.

Da er nun $3^{17} \mod 5$ berechnen möchte, fragt sich Johann ob er auch den Exponent zuerst einer Modulo-Operation unterziehen kann. Er möchte etwas in diesem Stil machen:

$3^{17} \mod 5 = 3^{(17 \mod 5)} \mod 5 = 32 \mod 5$

Darf er es machen? Versuchen Sie es selber...

[bearbeiten] a

Berechnen Sie $3^{17} \mod 5$ mit der schnellen Exponentiation.

$3^{17} \equiv_{5} 3^{16}*3 \equiv_{5} (((3^2)^2)^2)^2*3 \equiv_{5} ((4^2)^2)^2*3 \equiv_{5} (1^2)^2*3 \equiv_{5} 3$

[bearbeiten] b

Berechnen Sie nun $3^{17} \mod 5 = 3^{(17 \mod 5)} \mod 5 = ...$

$3^{17} \equiv_{5} 3^{(17 \mod 5)} \equiv_{5} 3^2 \equiv_{5} 4$

[bearbeiten] c

Sind die Ergebnisse gleich? Was schliessen Sie daraus?

 Nein, die Modulofunktion darf nur auf Basiszahlen und nicht auf den exponenten angewendet werden

[bearbeiten] Aufgabe 7

In der Unterrichtseinheit über die Basic Skills der Zahlentheorie haben Sie gelernt, was ein Ring ist. Wichtig dabei ist zu wissen, dass ein Ring eine Basismenge umfasst, und dass auf dieser Basismenge zwei Operationen (eine Addition und eine Multiplikation) definiert sind. Beweisen (oder widerlegen) Sie, dass $(\Z, \oplus, \otimes)$ ein Ring ist. Die Ring-Operationen sind wie folgt definiert:

$a \oplus b = a + b - 1$

$a \otimes b = (a - 1) * b$

 Achtung:
  und  sind die Addition und die Multiplikation im Ring .
  $+$  und  $-$  sind die uns bekannte, herkömmliche Addition und Multiplikation der ganzen Zahlen (im Ring )

[bearbeiten] DES

NIST Document about DES

[bearbeiten] 10.11.08 - Hash functions

NIST Submissions for SHA-3

[bearbeiten] 17.11.08 - RSA

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

Kategorie: AK

Fach:AK Stundenlogs

Aus StudyWiki

Inhaltsverzeichnis

[bearbeiten] 01.09.2008 - Begriffsbildung in der Kryptologie

[bearbeiten] CAESAR

[bearbeiten] Definition von Sicherheit

[bearbeiten] Aufgaben

[bearbeiten] A7.1

[bearbeiten] a)

[bearbeiten] B)

[bearbeiten] A7.2

[bearbeiten] A7.3

[bearbeiten] a)

[bearbeiten] b)

[bearbeiten] A7.4

[bearbeiten] A7.5

[bearbeiten] a)

[bearbeiten] b)

[bearbeiten] c)

[bearbeiten] A7.6

[bearbeiten] A7.7

[bearbeiten] A7.8

[bearbeiten] A7.9

[bearbeiten] A7.10

[bearbeiten] A7.11

[bearbeiten] A7.12

[bearbeiten] A7.13

[bearbeiten] 07.09.2008 - Enigma

[bearbeiten] Aufgaben

[bearbeiten] A1 Vorteil und grobe Funktionsweise der Enigma

[bearbeiten] A2 Rolle des Reflektors

[bearbeiten] A3 Definition einer Periode

[bearbeiten] A4 Grösse eines Schlüsselraumes

[bearbeiten] A5 Tatsächliche Grösse des Schlüsselraumes

[bearbeiten] A6 Max. Anz. Versuche für Brute Force

[bearbeiten] A7 Was ist eine polyalphabetische Substitution

[bearbeiten] Weblinks

[bearbeiten] Woche 3 - Zahlentheoretische Grundlagen: Basic Skills

[bearbeiten] Übungsserie

[bearbeiten] Aufgabe 1

[bearbeiten] a

[bearbeiten] b

[bearbeiten] c

[bearbeiten] d

[bearbeiten] e

[bearbeiten] f

[bearbeiten] Aufgabe 2

[bearbeiten] a

[bearbeiten] b

[bearbeiten] c

[bearbeiten] d

[bearbeiten] Aufgabe 3

[bearbeiten] a

[bearbeiten] b

[bearbeiten] Aufgabe 4

[bearbeiten] a

[bearbeiten] b

[bearbeiten] c

[bearbeiten] d

[bearbeiten] Aufgabe 5

[bearbeiten] a

[bearbeiten] b

[bearbeiten] Aufgabe 6

[bearbeiten] a

[bearbeiten] b

[bearbeiten] c

[bearbeiten] Aufgabe 7

[bearbeiten] DES

[bearbeiten] 10.11.08 - Hash functions

[bearbeiten] 17.11.08 - RSA

Ansichten

Persönliche Werkzeuge

StudyPortal

Allgemein

Seminare

Fächer Fachstudium

Fächer Grundstudium

Suche

Werkzeuge