Differences

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

--- kurse:ef05a-2021:crypto-crash-course [2022/05/16 09:07]
Ivo Blöchliger [Public/Private-Key Cryptography]
+++ kurse:ef05a-2021:crypto-crash-course [2022/05/16 10:34] (current)
Ivo Blöchliger [NFT]
@@ Line 28: / Line 28: @@
     * Super schnell (bis zu 15GiB/s auf modernen Prozessoren) -> Verschlüsselung ist tranparent (Harddisk, aber auch RAM!)
+===== Zufallszahlen =====
+«Echter Zufall» ist schwierig. Zufallsgeneratoren z.B. in Python sind **nicht zufällig** und kryptographische Zwecke ungeeignet!
-===== Public/Private-Key Cryptography =====
+Moderne Betriebsysteme «ernten Entropie» aus diversen Quellen, wie z.B. Temperatur, Netzwerkverkehr, Tastatur, Maus etc. Damit wird dann «guter» Zufall erzeugt, der für kryptographische Zwecke geeignet ist.
-  * Schlüsselpaar, einer ist öffentlich (public), einer ist privat (private) und streng geheim!
-  * Was mit dem einen Schlüssel verschlüsselt wird, kann nur mit dem anderen entschlüsselt werden.
-  * Es ist praktisch unmöglich, aus dem einen Schlüssel den anderen zu berechnen.
-    * Aber ist selbstverständlich möglich, ein Schlüsselpaar zu erzeugen!
-  *
-==== Praktische Umsetzung ====
-  * Nur ein **zufälliger** AES-Key wird verschlüsselt mitgesendet.
-  * Die Nachricht wird mit AES verschlüsselt.
-  * Vorteile
-    * Mehrere Empfänger für eine verschlüsselte Nachricht (Nur AES-Schlüssel wird mehrfach verschlüsselt).
-    * Geringer Rechenaufwand
-==== Diffie-Hellman Vefahren ====
+===== Diffie-Hellman Vefahren =====
-=== Klassisches Verfahren ===
+==== Klassisches Verfahren ====
   * Grundprinzip: der diskrete Logarithmus kann nicht effizient berechnet werden (d.h. nicht viel besser als alles ausprobieren).
 $$
 b^e = x \mod n \qquad \text{Aus $b$ und $x$ kann $e$ nicht berechnet werden.}
 $$
   * Schlüsseltausch über unsicheren Kanal von $A$ und $B$:
     * $A$ wählt zufällige Basis $b$, zufällige Primzahl $n$ und geheime Zufallszahl $x$. $A$ berechnet $p = b^x \mod n$.
@@ Line 59: / Line 51: @@
     * Woher weiss $A$, dass es sich wirklich um $B$ handelt? $E$ könnte sich dazwischen hängen und den Austausch mit $A$ und $B$ machen, hat dann zwei Schlüssel und kann sich so einklinken.
     * Authenzität von $A$ und $B$ muss überprüft werden!
+=== Weitere Varianten und Bemerkungen ===
+  * Dieses Verfahren gibt es u.a. auch basierend auf «elliptischen Kurven».
+  * Es ist keine gute Idee, immer die gleiche Primzahl zu verwenden. Mit einigen Monaten Vorberechnung kann das Verfahren dann geknackt werden (bei Primzahlen in der Grössenordnung von 1000 Bits).
+===== Public/Private-Key Cryptography =====
+  * Schlüsselpaar, einer ist öffentlich (public), einer ist privat (private) und streng geheim!
+  * Was mit dem einen Schlüssel verschlüsselt wird, kann nur mit dem anderen entschlüsselt werden.
+  * Es ist praktisch unmöglich, aus dem einen Schlüssel den anderen zu berechnen.
+    * Aber ist selbstverständlich möglich, ein Schlüsselpaar zu erzeugen!
+==== Aktuelle Verfahren ====
+Elliptische Kurven sind heute das Mittel der Wahl. RSA wird zwar immer noch weitläufig verwendet, sollten aus verschiedenen Gründen aber nicht mehr verwendet werden. Beide Verfahren werden mit grossen Quantencomputern hinfällig.
+Verfahren, die auch von Quantencomputern nicht ausgehebelt werden können werden aktuell getestet.
+=== RSA ===
+Für einen Modulus $n=pq$ mit $p,q$ prim können zwei Exponenten $e$ und $d$ bestimmt werden, so dass für alle $m<n$ gilt:
+$$
+\left(m^d\right)^e = m \mod n \qquad \text{und damit} \qquad \left(m^d\right)^e = m^{de} = \left(m^e\right)^d = m
+$$
+Ohne Kenntnis von $p$ und $q$ ist es, **für sorgfältig gewählte Parameter** praktisch unmöglich aus dem öffentlichen Schlüssel ($n$, $e$) den privaten
+Schlüssel $d$ zu errechnen.
+D.h. wenn man effizient faktorisieren kann, fällt RSA.
+=== RSA «knacken» ===
+  * Unsorgfältig gewählte Parameter $p$ und $q$.
+  * Zu kleine Entropie bei Zufallszahlerzeugung.
+    * ggT berechnen ist einfach!
+    * Existieren z.B. nur $2^{16}$ verschiedene $p$, haben aus ca. $2^8=256$ unterschiedlichen $n$ zwei einen gemeinsamen Teiler mit Wahrscheinlichkeit ca. 50%.
+==== Praktische Umsetzung ====
+  * Nur ein **zufälliger** AES-Key wird verschlüsselt mitgesendet.
+  * Die Nachricht wird mit AES verschlüsselt.
+  * Vorteile
+    * Mehrere Empfänger für eine verschlüsselte Nachricht (Nur AES-Schlüssel wird mehrfach verschlüsselt).
+    * Geringer Rechenaufwand
 ==== Challenge/Response ====
   * Besitznachweis eines privaten Schlüssels, ohne den Schlüssel zu zeigen.
+    * Server: Verschlüssle mal diese Zufallszahl!
+    * Client: Bitte sehr.
+    * Server entschlüsselt mit öffentlichem Schlüssel. Das kann nur der Besitzer vom privaten Schlüssel sein.
 ==== Bemerkung zu RSA vs. Elliptic Curves ====
@@ Line 75: / Line 110: @@
   * Integrität der Nachricht.
 ==== Prinzipien ====
+  * Mit privatem Schlüssel verschlüsseln.
+  * Kann nur mit öffentlichem Schlüssel entschlüsselt werden.
+  * Kommt dabei was sinnvolles heraus, kann das nur der Besitzer des privaten Schlüssels verschlüsselt haben.
 ==== Effektive Umsetzung ====
 Nur der Hash der Nachricht wird verschlüsselt, nicht die Nachricht selbst.
@@ Line 81: / Line 119: @@
 ==== Anwendung bei https ====
+  * Zentrale Stellen
+    * deren öffentliche Schlüssel sind im Browser hinterlegt.
+  * Zentrale stelle unterschreibt, öffentlichen Schlüssel vom Server.
+  * Client überprüft unterschrift auf vom Server präsentierten Zertifikat.
+    * wenn Zertifikat OK (d.h. der unterschreibenden Stelle wird vertraut), wird dem Server vertraut
+    * Schlüsseltausch (z.B. Diffie-Hellman oder ähnliches Verfahren).
+=== Pre-Snowden ===
+  * Kaum https, Passwörter im Klartext übers Netz.
+  * Wenn https, dann oft Schlüssel-Tausch via privatem Server-Schlüssel. Problem: nachträgliche Entschlüsselung möglich, wenn Zugriff auf privaten Server-Schlüssel.
+  * Zertifikate waren schweineteuer. Heute gratis dank Letsencrypt (Spenden von Bürgerrechtsorganisationen).
 ===== POW-Blockchain =====
-Proof of work, z.B. Bitcoin.
+  * Öffentliche Buchhaltung
+  * Transaktionen sind vom Sender unterschrieben.
+  * Block:
+    * Hashwert vom letzen Block
+    * Liste von Transaktionen
+      * inkl. Transaktionsgebühren und Belohnung für den Erzeuger vom Block
+    * Zu findende Zufallszahl
+    * ergibt einen Hashwert mit $x$ führenden Nullen (binär). Schwierigkeit $2^x$
+  * Konsens: Längste Kette ist massgebend.
+  * Transaktion erst «sicher», wenn ein paar Blöcke angehängt
+  * Transaktion wieder «löschen» nur mit enormer Rechenpower möglich (z.B. wenn man mehr als 50% der Power hat, kann man eine parallele Kette ohne die eigene Transaktion rechnen).
+==== Aufwand/Ertrag ====
+  * Bitcoin Stromverbrauch: Wie Irland.
+  * Anzahl Transaktionen: ca. 4/s (zum Vergleich: Visa: 65'000/s).
+==== Alternativen ====
+  * Proof of Stake (anstatt Proof of work).
+    * Bieterrunde, wer den nächsten Block signieren darf.
+    * Pseudozufälliges aber deterministisch nachvollziehbares Auswahlverfahren, mit Wahrscheinlichkeit proportional zum Einsatz.
+    * Ausgewählter signiert Block, bekommt Transaktionsgebühren.
+    * Wer beim Verfahren «falsch» agiert, verliert den gebotenen Einsatz.
 ==== Welches «Problem» löst eine Blockchain? ====
+  * Kein Vertrauen in zentrale Stelle.
+  * Kein Vertrauen in Marktzteilnehmer.
+Meine Meinung: Vertrauen ist das höchste Wirtschaftsgut, ein wichtiger Grund für das wirtschaftliche Wohlergehen der Schweiz. Vertrauen ist verdammt effizient.
 ==== Braucht es für $xy$ eine Blockchain? ====
-Antwort: Nein.
+Kurze Antwort: Nein.
+Lange Antwort: Meist reicht eine digitale Unterschrift einer vertrauenswürdigen Stelle (worauf fast alle Blockchains in öffentlichen Projekten basieren).
 ==== NFT ====
-Vergleichbar mit Autogramm. Wertvoll für den Fan, sonst Altpapier.
+Vergleichbar mit Autogramm. Wertvoll für den Fan, sonst Altpapier. Siehe auch Steve Moulds Video dazu: https://www.youtube.com/watch?v=IZaTd0hDtkI
+===== Weitere Buildingblocks =====
+  * https://en.wikipedia.org/wiki/Zero-knowledge_proof
+  * https://en.wikipedia.org/wiki/Group_signature
+  * https://en.wikipedia.org/wiki/Ring_signature
+  * Unlesbare Transaktionen: https://en.wikipedia.org/wiki/Monero