Differences

This shows you the differences between two versions of the page.

--- efinf:blc2016:krypto [2017/01/17 08:24]
Ivo Blöchliger [Mathematische Grundlagen]
+++ efinf:blc2016:krypto [2017/01/26 09:30] (current)
Ivo Blöchliger
@@ Line 1: / Line 1: @@
 {{backlinks>.}}
 ===== Prinzipien moderner Kryptographie =====
+==== Zusammenfassung ====
+  * Slides: {{ :efinf:blc2016:26.01.17_0742.pdf |}}
 Begriffe:
   * **{{https://de.wikipedia.org/wiki/Kryptologie|Kryptologie}}** = {{https://de.wikipedia.org/wiki/Kryptographie|Kryptographie}} (Verschlüsseln) und {{https://de.wikipedia.org/wiki/Kryptoanalyse|Kryptoanalyse}} (gegnerisches Entschlüsseln)
@@ Line 47: / Line 52: @@
     byte = bit/8;
     bit = bit%8;
     s.setbyte(byte,
       s.getbyte(byte)^(1 << bit))
     return s
@@ Line 66: / Line 71: @@
 text = File.read("hashtest.rb")
-modif = flipBit(text, 30);
-puts "Veränderte Bits im text: #{count_bit_diff(text,modif)}"
 hash_orig = Digest::SHA256.digest(text)
-hash_modif = Digest::SHA256.digest(modif)
+counters = Array.new(256,0)
-puts "Anzahl bits: #{hash_orig.size*8}"
+(text.size*8).times{|bit|
-puts "Veränderte Bits: #{count_bit_diff(hash_orig, hash_modif)}"
+    modif = flipBit(text, bit);
+    hash_modif = Digest::SHA256.digest(modif)
-p hash_orig
+    counters[count_bit_diff(hash_orig, hash_modif)]+=1
-p hash_modif
+}
+# Generate CSV-Output
+counters.each_with_index{|c,i|
+        puts "#{i};#{c}"
+}
 </code>
+Das Historgramm kann wie folgt erzeugt werden:
+<code bash>
+ruby hashtest.rb > test.csv
+libreoffice test.csv
+</code>
+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.
+{{:efinf:blc2016:histogramm-sha256.png?direct&200|}}
 </hidden>
@@ Line 85: / Line 100: @@
   * Digitale Unterschrift: Anstatt das ganze Dokument zu signieren, wird der Hash davon signiert (ist erheblich schneller).
   * Blockchain, für z.B. Bitcoins.
+  * Überprüfen von Plagiaten. Nicht die Inhalte sondern Hashes (wahrscheinlich von Sätzen, Abschnitten, Seiten, ganzer Text) werden gespeichert. Beim Wiederfinden dieser Hashes kann auf die Original-Arbeit verwiesen werden.
 === Rainbow-Tables ===
 Trade-Off: Speicherplatz/Rechenpower.
-Zutaten: Bakannte Hash-Funktion $h(s)$, Spezielle Hash-ähnliche Funktion $p(h)$, die aus Hashes Passwörter generiert.
+Zutaten: Bakannte Hash-Funktion $h(s)$, Spezielle Hash-ähnliche Funktionen $p_i(h)$, die aus Hashes Passwörter generieren.
+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 'aaaaa').
 Generierung der Tabelle:
   - Starte mit einem Passwort $x$.
   - Speichere das Passwort $x$
-  - Wiederhole $n$ mal (so $10^6$ oder so): $x := p(h(x))$
+  - Für $i$ von 0 bis $(n-1)$ mal (so $10^4$ oder so): $x := p_i(h(x))$
   - Speichere $h(x)$
   - Wiederhole ab Schritt 2.
 Entschlüsseln eines Passworts, gegeben Hash $y$.
-  - Wiederhole bis $y$ in der Tabelle vorkommt (maximal $n$ mal ($n$ wie oben))
+  - Für $j$ von $n$ bis zu 0 hinunter:
-    - Setzte $y := h(p(y))$
+    - 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, Passwort ist nicht in der Rainbow-Table.
+    - Wenn das Ende der Kette in der Tabelle vorkommt, die ganze Kette neu rechnen. Hoffen, dass der gesuchte Hash in der Kette ist (es ist nicht unwahrscheinlich, dass zwei verschiedene Startpasswörter zum gleichen Hash am Ende führen).
-  - Wenn $y$ in der Rainbow-Table ist, vom Startpasswort starten, bis passendes Passwort gefunden.
-Naja, das ist nur mal die Grundidee. So wie oben beschrieben funktioniert die Sache nicht wirklich, weil die Passwortketten ineinander übergehen. 1. Lösungsansatz war, verschiedenste Funtionen zur Passwortgenerierung zu haben. Der Witz an Rainbow-Tables ist, dass die passwortgenerierende Funktion für jeden Schritt ändert. Kollisionen sind weiterhin möglich. Ein zusammenlaufen der Ketten ist viel unwahrscheinlicher.
+Ursprünglich hatte man diverse Tabellen mit unterschiedlichen Reduktionsfunktionen $p_i(h)$, um das Zusammenlaufen von Ketten zu vermeiden.
 Siehe http://lasec.epfl.ch/pub/lasec/doc/Oech03.pdf  (ist offenbar eine Erfindung aus Lausanne ;-))
@@ Line 111: / Line 127: @@
 === Spielzeug Beispiel ===
-<hidden Code zur Generierung der Rainbow-Table>
+<hidden Code zur Abschätzung des Rechenaufwands>
 <code ruby rainbowtable.rb>
 require 'digest'
@@ Line 132: / Line 148: @@
 def randPass(n=7)
   Array.new(n){('a'.ord+rand(26)).chr}.join
-end
-# Generate a row of the rainbow table
-def makeRow(pw, n=1_000_000)
-  h = ""
-  len = pw.size
-  n.times{
-    h = Digest::SHA256.hexdigest(pw)
-    pw = makePW(h,len)
-  }
-  return h
 end
@@ Line 161: / Line 166: @@
 end
-# Generate entries for the table
-while true
-  pw = randPass(7)
-  h = makeRow(pw)
-  puts "#{pw}:#{h}"
-end
 </code>
 </hidden>
 ===== Public-Private Key Encryption =====
+{{ :efinf:blc2016:17.01.17_1355.pdf |}}
 ==== 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}$ (d.h. modulo n).
   * 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 ''e & 1 == 1'')
+      * $r := r \cdot b \mod n$
+    * $e := e/2$ (bzw. ''e= e >> 1'')
+    * $b := b^2 \mod n$
+  * Resultat ist $r$
+<hidden Ruby-Code>
+<code ruby modpow.rb>
+def modpow(b,e,n)
+  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
+</code>
+</hidden>
+==== 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://de.wikipedia.org/wiki/Diffie-Hellman-Schl%C3%BCsselaustausch
 ==== RSA-Schlüssel zum Spielen (hier 32 Bit, bietet keine Sicherheit) ====
@@ Line 190: / Line 227: @@
 </code>
+Zutaten: Modulus $n$ (Produkt zweier Primzahlen), öffentlicher Exponent $o$ (normalerweise 65537 = 0x10001), privater Exponent $p$.
+Eigenschaft: $$\left(x^o\right)^p \mod n= x \mod n = \left(x^p\right)^o \mod n$$
 ==== Public/private-Key Verschlüsselung ====
@@ Line 203: / Line 244: @@
 Effektiv wird normalerweise nur ein Hash der Nachricht verschlüsselt.
-=== Authetifizierung ===
+=== Authentifizierung ===
 Zuordnung Schlüssel-Person (oder Server) muss überprüft werden. Ansätze:
   * 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.
-==== Schlüsseltausch über unsicheren Kanal (Diffie-Hellman) ====
 ==== OTR, Deniability, Forward Secrecy ====
   * https://en.wikipedia.org/wiki/Off-the-Record_Messaging