Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
efinf:blc2016:krypto [2017/01/05 13:31] Ivo Blöchliger [Public-Private Key Encryption] |
efinf:blc2016:krypto [2017/01/26 09:30] (current) Ivo Blöchliger |
||
---|---|---|---|
Line 1: | Line 1: | ||
{{backlinks> | {{backlinks> | ||
===== Prinzipien moderner Kryptographie ===== | ===== Prinzipien moderner Kryptographie ===== | ||
+ | ==== Zusammenfassung ==== | ||
+ | |||
+ | * Slides: {{ : | ||
+ | |||
+ | |||
Begriffe: | Begriffe: | ||
* **{{https:// | * **{{https:// | ||
Line 35: | Line 40: | ||
* Ein Hashwert kann auch mit Ruby-Libraries berechnet werden, {{https:// | * Ein Hashwert kann auch mit Ruby-Libraries berechnet werden, {{https:// | ||
* Das Histogramm kann als csv-Datei exportiert werden, wobei jede Zeile so aussieht: ' | * Das Histogramm kann als csv-Datei exportiert werden, wobei jede Zeile so aussieht: ' | ||
+ | |||
+ | <hidden Lösungsansatz> | ||
+ | Hinweis: Code herunterladen, | ||
+ | <code ruby hashtest.rb> | ||
+ | require ' | ||
+ | |||
+ | # s: String, bit: nummer | ||
+ | def flipBit(s, bit) | ||
+ | # Kopie von s | ||
+ | s = String.new(s) | ||
+ | byte = bit/8; | ||
+ | bit = bit%8; | ||
+ | s.setbyte(byte, | ||
+ | s.getbyte(byte)^(1 << bit)) | ||
+ | return s | ||
+ | end | ||
+ | |||
+ | # s1,s2: Zwei gleich lange Strings | ||
+ | def count_bit_diff(s1, | ||
+ | diff = 0 | ||
+ | s1.size.times{|i| | ||
+ | xor = s1.getbyte(i)^s2.getbyte(i) | ||
+ | # Ganzzahl: 1 Byte | ||
+ | 8.times{|bit| | ||
+ | diff+=1 if (xor & (1<< | ||
+ | } | ||
+ | } | ||
+ | return diff | ||
+ | end | ||
+ | |||
+ | text = File.read(" | ||
+ | hash_orig = Digest:: | ||
+ | counters = Array.new(256, | ||
+ | (text.size*8).times{|bit| | ||
+ | modif = flipBit(text, | ||
+ | hash_modif = Digest:: | ||
+ | counters[count_bit_diff(hash_orig, | ||
+ | } | ||
+ | |||
+ | # Generate CSV-Output | ||
+ | counters.each_with_index{|c, | ||
+ | puts "# | ||
+ | } | ||
+ | </ | ||
+ | Das Historgramm kann wie folgt erzeugt werden: | ||
+ | <code bash> | ||
+ | ruby hashtest.rb > test.csv | ||
+ | libreoffice test.csv | ||
+ | </ | ||
+ | In LibreOffice ist der Strichpunkt (Semicolon) als Trennzeichen zu wählen. Das Histogramm kann als Balkendiagramm erzeugt werden, wobei die erste Spalte als Labels verwendet wird. | ||
+ | |||
+ | {{: | ||
+ | </ | ||
=== Anwendungen === | === Anwendungen === | ||
Line 41: | Line 99: | ||
* Forensik: Vor der Analyse eines Datenträgers werden Hashwerte davon hinterlegt. (Damit nachträglich Manipulation festgestellt werden könnte). | * Forensik: Vor der Analyse eines Datenträgers werden Hashwerte davon hinterlegt. (Damit nachträglich Manipulation festgestellt werden könnte). | ||
* Digitale Unterschrift: | * Digitale Unterschrift: | ||
+ | * Blockchain, für z.B. Bitcoins. | ||
+ | * Überprüfen von Plagiaten. Nicht die Inhalte sondern Hashes (wahrscheinlich von Sätzen, Abschnitten, | ||
=== Rainbow-Tables === | === Rainbow-Tables === | ||
Trade-Off: Speicherplatz/ | Trade-Off: Speicherplatz/ | ||
- | Zutaten: Bakannte Hash-Funktion $h(s)$, Spezielle Hash-ähnliche | + | Zutaten: Bakannte Hash-Funktion $h(s)$, Spezielle Hash-ähnliche |
+ | Diese Funktionen können einander sehr ähnlich sein. Z.B. fassen die Funktionen den Hash als Ganzzahl auf, rechnen i dazu und dann modulo die Anzahl Passwörter im betrachteten Passwortraum und liefern das entsprechende Passwort (z.B. 0 ist ' | ||
Generierung der Tabelle: | Generierung der Tabelle: | ||
- Starte mit einem Passwort $x$. | - Starte mit einem Passwort $x$. | ||
- Speichere das Passwort $x$ | - Speichere das Passwort $x$ | ||
- | - Wiederhole | + | - Für $i$ von 0 bis $(n-1)$ mal (so $10^4$ oder so): $x := p_i(h(x))$ |
- Speichere $h(x)$ | - Speichere $h(x)$ | ||
- Wiederhole ab Schritt 2. | - Wiederhole ab Schritt 2. | ||
Entschlüsseln eines Passworts, gegeben Hash $y$. | Entschlüsseln eines Passworts, gegeben Hash $y$. | ||
- | - Wiederhole bis $y$ in der Tabelle vorkommt (maximal | + | - Für $j$ von $n$ bis zu 0 hinunter: |
- | - Setzte | + | - Fasse $h$ als Eintrag in Spalte $j$ auf und rechne die Kette zu Ende (beginnend mit $p_j(h)$). |
- | - Wenn $y$ nicht in der Tabelle vorkommt, | + | - Wenn das Ende der Kette in der Tabelle vorkommt, |
- | - Wenn $y$ in der Rainbow-Table | + | |
+ | |||
+ | Ursprünglich hatte man diverse Tabellen mit unterschiedlichen Reduktionsfunktionen | ||
+ | |||
+ | Siehe http:// | ||
+ | |||
+ | |||
+ | === Spielzeug Beispiel === | ||
+ | <hidden Code zur Abschätzung des Rechenaufwands> | ||
+ | <code ruby rainbowtable.rb> | ||
+ | require ' | ||
+ | |||
+ | # Passwords are 7 lower case letters a-z | ||
+ | # Hash is SHA256 | ||
+ | |||
+ | # Makes a password out of a hex hash | ||
+ | def makePW(hash, n=7) | ||
+ | z = hash.to_i(16) | ||
+ | pw = "" | ||
+ | n.times{ | ||
+ | pw += (z % 26 + ' | ||
+ | z/=26 | ||
+ | } | ||
+ | return pw | ||
+ | end | ||
+ | |||
+ | #Random password (for starting a chain) | ||
+ | def randPass(n=7) | ||
+ | Array.new(n){(' | ||
+ | end | ||
+ | |||
+ | # Check, how many hashes per second/ | ||
+ | def speedTest(n=5) | ||
+ | text = " | ||
+ | n = 26**text.size | ||
+ | start = Time.now | ||
+ | n.times { | ||
+ | Digest:: | ||
+ | text.succ! | ||
+ | } | ||
+ | total = Time.now-start | ||
+ | puts "#{n} Hashes in #{total} secs." | ||
+ | puts "Makes # | ||
+ | puts "Makes # | ||
+ | puts "Makes # | ||
+ | end | ||
+ | |||
+ | |||
+ | </ | ||
+ | </ | ||
===== Public-Private Key Encryption ===== | ===== Public-Private Key Encryption ===== | ||
+ | |||
+ | {{ : | ||
==== Mathematische Grundlagen ==== | ==== Mathematische Grundlagen ==== | ||
- | * Rechnen in Restklassen | + | * Rechnen in Restklassen: Nach jeder Operation wird der Rest modulo n (der Modulus) gerechnet. |
- | * Potenzieren in $\mathbb{Z} / n\mathbb{Z}$ | + | * Potenzieren in $\mathbb{Z} / n\mathbb{Z}$ |
* Diskreter Logarithmus ist schwierig | * Diskreter Logarithmus ist schwierig | ||
+ | |||
+ | $b^e \mod n$ effizient ausrechnen. Annahme: $e$ liegt im Zweiersystem vor, z.B. 0b10001011. Dann ist | ||
+ | $$b^e = b^{1+2+8+128} = b^1 \cdot b^2 \cdot b^8 \cdot b^{128}$$ | ||
+ | |||
+ | Die Potenzen $b^2$, $b^4$, $b^8$, $b^{16}$, etc. können durch wiederholtes quadrieren erhalten werden. | ||
+ | |||
+ | === Pseudo-Code zum Potenzieren === | ||
+ | * **Input** $b$, $e$, $n$ | ||
+ | * **Output** $r=b^e \mod n$ | ||
+ | * $r=1$ | ||
+ | * Solange $e \neq 0$: | ||
+ | * Falls Bit 0 von $e$ gesetzt (d.h. wenn '' | ||
+ | * $r := r \cdot b \mod n$ | ||
+ | * $e := e/2$ (bzw. '' | ||
+ | * $b := b^2 \mod n$ | ||
+ | * Resultat ist $r$ | ||
+ | |||
+ | <hidden Ruby-Code> | ||
+ | <code ruby modpow.rb> | ||
+ | def modpow(b, | ||
+ | res = 1 | ||
+ | while (e>0) | ||
+ | if e & 1 == 1 | ||
+ | res = (res*b)%n | ||
+ | end | ||
+ | e = e >> 1 | ||
+ | b=(b*b)%n | ||
+ | end | ||
+ | return res | ||
+ | end | ||
+ | </ | ||
+ | </ | ||
+ | ==== Diffie-Hellmann Key-Exchange ==== | ||
+ | Achtung: Nicht jede Primzahl und nicht jede Basis ist dafür geeignet. Die sollten sorgfältig ausgewählt werden, was Rechenaufwand bedeutet. Das ist der Grund, warum viele Internetdienste gleiche Primzahlen und Basen verwenden. | ||
+ | |||
+ | Siehe z.B. https:// | ||
+ | |||
+ | ==== RSA-Schlüssel zum Spielen (hier 32 Bit, bietet keine Sicherheit) ==== | ||
+ | <code bash> | ||
+ | # 32 bit Schlüssel generieren | ||
+ | openssl genrsa 32 > key.pem | ||
+ | |||
+ | # Daten anzeigen (dezimal und hexadezimal) | ||
+ | openssl rsa -text -noout < key.pem | ||
+ | |||
+ | # Public key schreiben | ||
+ | openssl rsa -in key.pem -outform PEM -pubout > public.pem | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | Zutaten: Modulus $n$ (Produkt zweier Primzahlen), | ||
+ | |||
+ | Eigenschaft: | ||
+ | ==== Public/ | ||
Grundlage: Zwei Schlüssel, einer **privat**, einer **öffentlich**. Was mit dem einen verschlüsselt wird, kann **nur** mit dem **anderen** Schlüssel entschlüsselt werden. | Grundlage: Zwei Schlüssel, einer **privat**, einer **öffentlich**. Was mit dem einen verschlüsselt wird, kann **nur** mit dem **anderen** Schlüssel entschlüsselt werden. | ||
Line 77: | Line 244: | ||
Effektiv wird normalerweise nur ein Hash der Nachricht verschlüsselt. | Effektiv wird normalerweise nur ein Hash der Nachricht verschlüsselt. | ||
- | === Authetifizierung | + | === Authentifizierung |
Zuordnung Schlüssel-Person (oder Server) muss überprüft werden. Ansätze: | Zuordnung Schlüssel-Person (oder Server) muss überprüft werden. Ansätze: | ||
* Austausch über weiteren Kanal (z.B. in Person, Austausch auf Papier). | * Austausch über weiteren Kanal (z.B. in Person, Austausch auf Papier). | ||
* Zertifizierung über vertrauenswürdige Drittstelle. Diese signiert, dass der Schlüssel zur Person (oder Server) gehört. | * Zertifizierung über vertrauenswürdige Drittstelle. Diese signiert, dass der Schlüssel zur Person (oder Server) gehört. | ||
- | ==== Schlüsseltausch über unsicheren Kanal (Diffie-Hellman) ==== | ||
==== OTR, Deniability, | ==== OTR, Deniability, | ||
* https:// | * https:// | ||
- |