Digitale signaturen
Will man nachweisen, dass eine Nachricht im Internet von einem bestimmten Verfasser stammt, z. B. bei einer Transaktion die gemacht werden soll, dann ist es notwendig, sich zu authentifizieren. Im digitalen Bereich geschieht dies mit digitalen Signaturen, welche auf asymmetrischen Verschlüsselungsverfahren wie RSA basieren.
Was ist ein asymmetrisches Verschlüsselungsverfahren?
Bei anderen Verschlüsselungsverfahren hat man einen Geheimtext, den man mithilfe eines geheimen Schlüssels in einen verschlüsselten Text verwandelt. Möchte man diesen wieder lesbar machen, so braucht man genau diesen geheimen Schlüssel, um den Text wieder zurück zu entschlüsseln. Doch das erzeugt ein Problem: Wie kann der Nachrichtenempfänger den geheimen Schlüssel gesendet bekommen?
Die Lösung für dieses Problem sieht folgendermaßen aus:
Wenn eine Person wie Alice gerne Nachrichten mit Anderen austauschen möchte, dann generiert sie sich zuerst ein Schlüsselpaar. Dieses Paar besteht aus einem privaten Schlüssel, den sie geheim hält, und einem öffentlichen Schlüssel, den jeder kennen muss. Dieser kann beispielsweise einfach im Internet veröffentlicht werden. Die Schlüssel sind so konzipiert, dass sie immer nur in genau eine Richtung funktionieren, das bedeutet, selbst, wenn man den Schlüssel kennt, mit dem man den Text verschlüsselt hat, kann man diesen nicht einfach wieder benutzen, um den Text zu entschlüsseln, dafür braucht man den zweiten Schlüssel.
Wenn Bob nun Alice eine Nachricht senden möchte, nutzt er dafür diesen frei im Internet verfügbaren Public Key, um seine geheime Nachricht zu verschlüsseln. Den verschlüsselten Text sendet er nun öffentlich an Alice, welche diesen mit ihrem Private Key wieder entschlüsseln kann.
Für ein gutes Verschlüsselungsprogramm ist es hierfür also wichtig, dass man weder mit dem Public Key, noch mit der Kombination aus verschlüsselten Text und entschlüsseltem Text, den Private Key von Alice ausrechnen kann.
Derselbe Aufbau kann auch benutzt werden, wenn Alice eine Nachricht signieren möchte, indem sie nachweist, dass sie im Besitz des privaten Schlüssels ist.
Dafür verschlüsselt Alice einfach den zu signierenden Text mit ihrem Private Key und hängt diesen verschlüsselten Text der Nachricht als Unterschrift an. Jemand, der nun herausfinden möchte, ob der Text wirklich von Alice ist, kann jetzt den verschlüsselten Text mit dem Public Key entschlüsseln und so feststellen, ob die Nachrichten identisch sind oder nicht. Dies ist für Blockchain relevant, damit man feststellen kann, ob die Transaktionen wirklich von dem Kontoinhaber vorgenommen wurden.
Wie funktionert das technisch?
Der Algorithmus RSA, auf dem unter Anderem auch HTTPS basiert, welcher natürlich bei unserem Beispiel Bitcoin zum Einsatz kommt, benutzt clevere Mathematik, um ein Schlüsselpaar zu generieren und Nachrichten zu ver- und entschlüsseln.
Zur Generierung eines RSA-Schlüsselpaars wählt man zwei große Primzahlen p und q. Aus diesen Primzahlen wird die Zahl N = p*q berechnet. Nachrichten werden später immer modulo N betrachtet. Um eine Nachricht zu entschlüsseln, müsste man N, welches im Public Key enthalten ist, in seine Primfaktoren p und q zerlegen, was aufgrund der Größe der Zahlen praktisch unmöglich ist. Das macht RSA auch so sicher.
Man berechnet außerdem eine Zahl phi(N) = (p-1) * (q-1).
Die Funktion phi(N) gibt die Anzahl der positiven ganzen Zahlen an, die kleiner als N sind und keinen gemeinsamen Teiler mit N haben. Zum Beispiel hat die Zahl 7 die Zahlen 1, 2, 3, 4, 5 und 6 als teilerfremde Zahlen, also ist phi(7) = 6.
Als Nächstes wählt man eine Zahl e, den Verschlüsselungsexponenten.
Dabei gilt 1 < e < phi(N). Außerdem muss e teilerfremd zu phi(N) sein.
Nun kommt das multiplikative Inverse zum Einsatz, denn damit finden wir den Entschlüsselungsexponenten d; er ist das multiplikative Inverse zum Verschlüsselungsexponenten bezüglich phi(N).
Um das multiplikative Inverse zu bestimmen, verwendet man den erweiterten Euklidischen Algorithmus.
Jetzt können wir zwei Schlüsselpaare zusammensetzen, welcher dabei der öffentliche und welcher der private ist, ist austauschbar: Private Key= (e, N) Public Key= (d, N).
Die Verschlüsselung funktioniert folgendermaßen: Man hat einen Geheimtext T, den man in eine oder mehrere Abschnitte aus Zahlen unterteilt. Also hat man die Geheimzahl t.
Daraus generiert man eine verschlüsselte Nachricht mit den Informationen des Public Key:
v = t^d mod N
Die Nachricht v verschickt man über das Internet.
Entschlüsseln kann man dies nun mit t = v^e mod N und hat somit wieder den Geheimtext t in unverschlüsselter Form vorliegen.
Aber warum genau funktioniert das? Dafür müssen wir beweisen, dass t= (t^e)^d mod n gilt.
Das funktioniert, da e und d eben multiplikativ invers sind. Außerdem braucht man für den Beweis den Satz von Euler:
a^phi(m) ≡ 1 mod m
Außerdem wissen wir, da e invers zu d ist:
e * d ≡ 1 mod phi(N)
Was bedeutet, dass eine ganze Zahl r existiert, sodass gilt:
e * d = r * phi(N)+1
(t^e)^d lässt sich umformen zu:
≡ t^(e * d) wir setzen die Gleichung von oben ein:
≡ t^(r * phi(N)+1 ) +1 lässt sich aus dem Exponenten herausziehen
≡ t^(r * phi(N)) * t mit ein paar Potenzgesetzen
≡ (t^phi(N))^r * t hier kommt der Satz von Euler zur Anwendung
≡ 1^r * t * 1^x ist irrelevant
≡ t mod N