 Die zwei gängigsten Verschlüsselungsverfahren sind RSA (Rivest/Shamir/Adleman, 1977) und ECC (Elliptic Curve Cryptography, 1985). Sicherheit ist eine Funktion der Länge des Public Keys (IBAN) und der Wahl des Verschlüsselungsverfahrens. Mit gleichem Zeitaufwand (Security Bits = 80 entspricht erraten einer 48-stelligen Zahl) kann bei RSA ein 1024-stelliger Code geknackt werden, bei ECC jedoch nur ein 160-stelliger (siehe Tabelle oben). Da der Speicheraufwand viel kleiner ist, verwendet die Blockchain ECC. Sowohl bei RSA also auch bei ECC sieht die mathematische Funktion etwa wie folgt aus: Public Key = Z x Private Key Die Umkehrfunktion ist: Private Key = Public Key / Z Für die Division durch Z gibt es aber (noch) keine effizienten Algorithmen, mit denen Computer den Private Key finden könnten. Wenn die Zahl Z sehr gross gewählt wird, ist es mit der heutigen Computertechnik praktisch unmöglich, den Private Key zu finden. ECC ist etwas kompliziert und es wird hier nur schematisch gezeigt, worum es geht. Zuerst sollen die Bestandteile der unten stehenden Grafik beschrieben werden, die wiederum nur eine spezielle stetige elliptische Kurve darstellt, die zur Veranschaulichung dient:  Rot: Elliptische Kurve, mathematisch y^2 = x^3 + 7 G (Generator Point): Ausgangspunkt auf der Kurve, x und y Koordinaten sind sehr gross Grün: Sprünge von einer Seite der Kurve auf die andere, Vorzeichenwechsel Blau: Tangente zur Kurve beim Ausgangspunkt, Differenzieren ECC-Multiplikation: Multiplikation bei ECC bedeutet im Unterschied zur herkömmlichen Mathematik, dass man die Tangente zum Ausgangspunkt G nimmt und schaut, wo sich diese mit der Kurve kreuzt (-2G). Dann springt man auf die andere Seite der Kurve und erhält 2G. Weitere Multiplikation ergibt 4G, 8G usw. ECC-Addition: Dabei wird durch zwei Punkte (z.B. 2G und 4G) eine Linie gelegt. Diese Linie ergibt einen neuen Punkt auf der Kurve. Es gilt: Public Key = Private Key x G oder K = kG Der Private Key gibt also an, wie oft ECC-Multiplikationen durchgeführt werden müssen, um den Public Key zu erhalten. Beispiele: Private Key = 2 führt zu Public Key = 4G Private Key = 3 = 8G Private Key = 10^77 = k = 2^kG Für die Multiplikation gibt es einen effizienten Algorithmus. Dies soll an einem Beispiel gezeigt werden:  Welche Schritte braucht es, um dies zu berechnen (von hinten nach vorne):  Im Endeffekt braucht es also nicht 151 Additionen, sondern nur 7 Multiplikationen und 4 Additionen. Es gibt heute noch keinen effizienten Algorithmus, der in umgekehrter Richtung wieder zu k führt. Dies wird in der Kryptografie "Problem des diskreten Logarithmus" genannt; analog zur Exponentialfunktion (siehe Anhang), obwohl die Umkehrfunktion hier eigentlich eine Division ist. Obige Kurve wurde nur zur Veranschaulichung herangezogen. In der Kryptografie werden nur ganzzahlige Werte (integers) benutzt und das Feld der möglichen Zahlen wird über eine Primzahl begrenzt. Dies nennt sich mod p. Diese Funktion kann am besten anhand einer Uhr erklärt werden. Eine Wanduhr ist mod 12. Wieso? Da die Stunde 13 als 1 Uhr dargestellt wird. 13 mod 12 = 1. Stunde 34 ist folglich 10 Uhr usw. Genau gleich verhält es sich mit dem kryptografischen Feld. Das Feld oben links ist durch die Primzahl 19 abgesteckt. x und y Werte ausserhalb des Feldes werden mod 19 dargestellt, 21 ist also 2. Die Null entspricht der 19 bzw. 19 mod 19. Die drei anderen Felder werden durch die Primzahlen 97, 127 und 487 abgegrenzt.   Über oben stehende Funktion sollen nun ein paar Punkte für das Feld F(p=19) berechnet werden:  Aufgrund der Wurzel, die genommen werden muss, um y zu berechnen, gibt es zu jedem x zwei y. Die Symmetrieachse entspricht y=p/2. Die meisten Blockchains, inklusive Bitcoin, verwenden folgende Kurve (ein paar wenige benutzen schon Edwards Curve):  Als Beispiel sollen Punkte für p = 17 berechnet werden. Dies ist etwas komplizierter. Nehmen wir x = 1. Die rechte Seite ergibt 8. Es gibt aber keine ganzzahlige Wurzel von 8. Darum muss solange 17 dazu addiert werden, bis eine ganzzahlige Wurzel innerhalb des Feldes resultiert. 8 + 17 = 25, Wurzel 25 = 5. Für x = 4 gibt es keine Lösung. Schliesslich ist x = 17 = 17 mod 17 = 0.  Das Feld sieht folgendermassen aus:  Und Feld F(p=19) sieht für diese Kurve so aus:  Für F(p=19) können 12 Punkte und für F(p=17) 18 Punkte berechnet werden. Für die anderen existiert die Wurzel nicht. Im Feld F(p=19) wurde ein Punkt G (x=12, y=14) eingezeichnet. Davon ausgehend werden nun erste Multiplikationen und damit Public Keys grafisch dargestellt (hier möchte ich speziell darauf hinweisen, dass das von Andrea Corbellini aufgestellte Programm einfach fantastisch ist. Spielen Sie damit herum und Sie bekommen ein gutes Gefühl, wie ECC funktioniert):  Bei weiteren Multiplikationen geschieht etwas Merkwürdiges:  Es herrscht Zyklizität vor. Von den 12 Punkten N kommen nur 6 als Key in Frage. Wird als Ausgangspunkt G (x = 0, y = 8) gewählt erhält man sogar nur 3 mögliche Keys. 6G entspricht dem Nullpunkt (im Programm wird dies mit inf = infinity angegeben). Erstaunlich ist auch, dass wenn p keine Primzahl ist, zwar Punkte, aber keine Public Keys berechnet werden können! Zum guten Glück gibt es effiziente Algorithmen, womit die Anzahl Punkte N (Schoff Algorithmus) und daraus die Anzahl Keys K (Lagrange Theorem) berechnet werden können. Auf den Schoff Algorithmus wird hier nicht eingegangen, sondern nur auf das Lagrange Theorem. Dieses besagt, dass K dem kleinsten ganzzahligen Divisor von N entspricht, der mit G multipliziert Null ergibt. Dies hört sich kompliziert an, daher sofort ein Beispiel: Oben hatten wir F(p=19) und N = 12. Divisoren von 12 sind: 1,2,3,6,12. Durch Anwendung der Formel für die Multiplikation zeigt sich, dass 6G = 0. Der gleiche Wert (k=6, 6G=0) wurde oben grafisch gefunden. Den geeigneten Ausgangspunkt G findet man wiederum über einen Algorithmus. Dazu muss der sogenannte Kofaktor (h) berechnet werden. Dieser entspricht N/K und ist in diesem Fall 2. Nun wählt man einen beliebigen Punkt (P) auf der Kurve. G=hP = 2P ist geeignet, falls er nicht dem Nullpunkt entspricht. Ansonsten muss mit einem anderen P ausprobiert werden. Hier soll noch erwähnt werden, dass in der Kryptografie K eine Primzahl sein muss, ansonsten die Verschlüsselung nicht sicher ist. Damit sollten für eine effiziente Public Key Verschlüsselung folgende Punkte erfüllt sein:
 Mit dieser Zahl erhält man aus 256 Bits das grösstmögliche Feld. Jedes F besteht aus 4 Bits (1111). 4x8x8=256. Dies ist jedoch keine Primzahl. Es muss also eine geeignete Primzahl gefunden werden, die möglichst nahe unter diesem Wert liegt. Bitcoin wählt folgende:  Das Ende sieht in binomialer Schreibweise so aus:  Wir müssen also von 2^256 folgende Terme abziehen (überall, wo eine Null steht):  Zum Beispiel entspricht eine 1 an der vierter Stelle von links: 2^32. Zuletzt muss noch 1 abgezogen werden, da das binomiale System bei 0 statt 1 beginnt. Ausgangspunkt G ist bei Bitcoin in komprimierter und dekomprimierter Form:  Anwendung: Signatur bei der Bitcoin BlockchainDie digitale Unterschrift wird gebraucht, um Transaktionen vornehmen zu können. Der Private Key kann als Ausgangspasswort und die Signatur als Hilfspasswort angesehen werden. Die Signatur beweist, dass jemand den Private Key hat, ohne diesen offen zu legen. Hier wurde beschrieben, wie bei Banken Passwörter als Hash auf einem zentralen Server gespeichert werden. Bei der Blockchain beteiligen sich aber viele unbekannte Server, weshalb die Sicherheit durch ECC nochmals erhöht wird. Zur Erstellung der Signatur werden folgende drei Koordinaten auf der elliptischen Kurve benötigt: zG = Zufalls-Koordinaten (x1, y1), z ist grosse Zufallszahl kG = Public Key-Koordinaten (x2, y2), k ist Private Key hG = Nachrichten-Koordinaten (x3, y3), h ist Hash der Transaktion Die digitale Unterschrift sieht wie folgt aus: s = (h + x1 k)/z wobei x1 mitgeliefert wird Schlaue Mathematiker haben herausgefunden, dass zG = s/s zG = (h + x1 k)/s G = (hG + x1 kG)/s zG = (hG + x1 Public Key)/s Die Zufalls-Koordinate hängt vom Hash (h) der Transaktion, dem Public Key, der digitalen Unterschrift (s) und x1 ab, jedoch wird der Private Key nicht mehr benötigt und muss daher zur Verifizierung nicht mehr offen gelegt werden. In den Transaktionsdaten stehen unter Scriptsig der Public Key sowie die digitale Unterschrift, der Hash kann aus der Transaktion berechnet werden und z (damit auch x1) steht in der Blockchain Datenbank. Miners überprüfen die Echtheit der Signatur, indem sie berechnen, ob die beiden Seiten gleich sind. Als Resultat liefert der Algorithmus true oder false bzw. richtig oder falsch. Da die digitale Unterschrift auch vom Hash abhängt, ist sie für jede Transaktion verschieden, was die Sicherheit zusätzlich erhöht. Niemand kann die Transaktion bis zur Verifizierung durch die Miner abändern, ansonsten die digitale Unterschrift nicht korrekt wäre. Jedoch beinhaltet der Hash (h) nicht das Scriptsig selber. Arglistige Miner haben darin minimale Manipulationen vorgenommen, so dass die digitale Signatur weiterhin stimmte, die Transaktions-ID aber komplett anders aussah, als vom Wallet prognostiziert. Diese Sicherheitslücke soll unter SegWit behoben werden. Die Zufalls-Koordinate muss bei jeder Transaktion neu berechnet werden und wirklich zufällig gewählt werden. Ansonsten kann aus zwei Transaktionen der Private Key herausgefunden werden! SONY hat früher eine statische Zufalls-Koordinate gewählt, womit die Playstation gehackt werden konnte. Wallet AufbauDie folgende Beziehung ist wichtig bei der Konstruktion von Wallets: (k + i)G = kG + iG = Public Key + iG i = ganze Zahl, k = Private Key Aus einem Public Key können somit beliebig viele zusätzliche Public Keys und damit Bitcoin Adressen mit Index i gebildet werden. Dafür braucht es den Private Key nicht. Dieser kann offline gespeichert werden und wird nur gebraucht, um kurz Überweisungen zu signieren. Zum Beispiel kann ein Online Webshop für jede Zahlung eine neue Bitcoin Adresse verwenden, um diese einzelnen Kunden zuweisen zu können.  Extended Keys Es würde jedoch keinen Sinn machen, wie hier einfach die Zahlen 1,2,3... zu nehmen. Gelangt trotz Vorsichtsmassnahmen ein Private Key in falsche Hände, können über den Index i sämtliche anderen Private Keys berechnet werden. Deshalb wird noch zusätzlich ein Passwort (Chain Code) verwendet, das nur dem Benutzer bekannt ist. Dieses setzt sich meistens aus 12-24 Wörtern zusammen und ist damit sehr sicher. Oft wird dieses daher gleichzeitig als Wallet Passwort gebraucht. Dann wird der folgende Hash berechnet: h = h (i, Chain Code, Public Key) Anstelle von i wird jetzt der dazugehörige Hash eingesetzt:  Kommt nun einer der Private Keys in falsche Hände, können die anderen Private Keys daraus nicht abgeleitet werden, weil der Chain Code fehlt. Hardened Keys Als zusätzliche Sicherheit kann auf der obersten Ebene im Hash der Private Key anstelle des Public Keys verwendet werden: h = h (i, Chain Code, Private Key) Anhang: Exponentialfunktion und Problem des diskreten LogarithmusExponentialfunktion  In der Kryptografie werden für k ganze Zahlen verwendet, womit die Funktion diskret (nicht stetig) ist. Beispiel:  Für die Exponentialfunktion gibt es einen effizienten Algorithmus, sprich Quadrieren. Dies soll an einem Beispiel gezeigt werden (k steht für Private Key und K für Public Key):  Um herauszufinden, wie viel Mal quadriert werden muss (y), kann die folgende Formel angewendet werden:  y für gerade ganze Zahl abrunden und für ungerade ganze Zahl aufrunden. Im Beispiel haben wir also:  Dies stimmt mit der Berechnung überein:  Um aus dem Public Key (K) den Private Key (k) zu erhalten, muss folgende Gleichung gelöst werden:  Für den Logarithmus einer diskreten Funktion gibt es zum heutigen Zeitpunkt keinen effizienten Algorithmus (für zukünftige Quantencomputer gäbe es einen). Die Differenz an Rechenschritten zwischen Funktion und Umkehrfunktion nimmt mit k exponentiell zu. Diese Differenz ist noch grösser für elliptische Kurve Kryptografie (ECC), weshalb dort kürzere Keys verwendet werden können. Quellen:
http://chimera.labs.oreilly.com/books/1234000001802/ch04.html#hd_wallets https://bitcoin.org/en/developer-guide#hierarchical-deterministic-key-creation http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/modk-mul.html https://en.wikipedia.org/wiki/Discrete_logarithm
2 Kommentare
|