Prinzipien moderner Kryptographie

Es geht hier nicht um die mathematischen Details, sondern um de Prinzipien und grundlegenden Eigenschaften moderner kryptographischer «Bauteile».

• Input: Irgendeine Anzahl an Bytes
• Output: Konstante Anzahl an Bytes, z.B. 32 Bytes bei SHA-256
• Deterministisch (gleicher Input liefert immer gleichen Output)
• Kollisionssicher
  • D.h. für $x\neq y$ gilt $P(H(x)=H(y)) \approx \frac{1}{2^{0.5l}} \qquad \text{mit $l$ der Länge des Hashes in Bits}$
• Zu einem gegeben Hash-Wert $h$ ist es praktisch unmöglich $x$ zu bestimmen mit $H(x)=h$.
• Zu einem gegebenen $x$ ist es praktisch unmöglich, ein $y$ zu bestimmen mit $H(x)=H(y)$.
• Daraus folgt, dass der Output einer Hashfunktion von Zufall nicht zu unterscheiden ist. Oder anders ausgedrückt: Ändert man ein einziges Bit im Input, ändern sich in etwas die Hälfte aller Bits im Output.

Zur Zeit empfohlene Hashfunktionen sind

• SHA-2 (vor allem SHA-256 und SHA-512)
• SHA-3 («Backup», sollte ein Problem mit SHA-2 auftauchen).

Veraltete Hashfunktionen (nicht mehr brauchen!) sind:

• SHA-1 (noch halbwegs sicher, erste Kollisionen wurden aber berechnet).
• MD5 (komplett kaputt). Kann aber noch zur Detektion von zufälligen Übertragungsfehlern dienen (aber nicht gegen Attacken schützen).

• Ver- und Entschlüsseln brauchen den gleichen Schlüssel.
• Problem: Schlüsselaustausch!
• Standard heute: AES (128, 192 oder 256 Bits für Schlüssel)
  • Super schnell (bis zu 15GiB/s auf modernen Prozessoren) → Verschlüsselung ist tranparent (Harddisk, aber auch RAM!)

«Echter Zufall» ist schwierig. Zufallsgeneratoren z.B. in Python sind nicht zufällig und kryptographische Zwecke ungeeignet!

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.

• 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$.
• $A$ übermittelt (einsehbar) $b$, $n$ und $p$ and $B$.
• $B$ wählt eine geheime Zufallszahl $y$ und berechnet $q=b^y \mod n$ und $s=p^y \mod n = \left(b^x\right)^y = b^{xy}$.
• $B$ übermittelt $q$ and $A$.
• $A$ berechnet $s=q^x \mod n = \left(b^y\right)^x \mod n = b^{xy} \mod n$.
• Beide haben nun die gleiche Geheimzahl $s$, die zur Erzeugung eines Schlüssel für die geheime Kommunikation gebraucht werden kann.

• Probleme:
  • 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!

• 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).

• 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!

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.

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.

• 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%.

• 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

• 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.

• Don't do RSA anymore
  • Schwierig das korrekt hinzukriegen
  • Rechenaufwendiger, grössere Schlüssellänge (min 2048 Bits)

• Authentifizierung.
• Integrität der Nachricht.

• 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.

Nur der Hash der Nachricht wird verschlüsselt, nicht die Nachricht selbst.

• Effizienter (nur eine kleine Datenmenge wird mit aufwendiger Krypto verschlüsselt).
• Nachricht bleibt im Klartext lesbar (auch ohne Software für die Bestätigung der Unterschrift).

• 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).

• 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).

• Ö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).

• Bitcoin Stromverbrauch: Wie Irland.
• Anzahl Transaktionen: ca. 4/s (zum Vergleich: Visa: 65'000/s).

• 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.

• 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.

Kurze Antwort: Nein.

Lange Antwort: Meist reicht eine digitale Unterschrift einer vertrauenswürdigen Stelle (worauf fast alle Blockchains in öffentlichen Projekten basieren).

Vergleichbar mit Autogramm. Wertvoll für den Fan, sonst Altpapier. Siehe auch Steve Moulds Video dazu: https://www.youtube.com/watch?v=IZaTd0hDtkI

• 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