You do not have permission to view link please Anmelden or Registrieren
Durch einen Fehler bei der Erzeugung von zufälligen Primzahlen lassen sich die RSA-Schlüssel der
You do not have permission to view link please Anmelden or Registrieren
von
You do not have permission to view link please Anmelden or Registrieren
erraten. Dadurch ist die Sicherheit von Millionen Ausweisen, Computern und Passwortspeichern gefährdet. Der genaue Fehler soll erst in zwei Wochen auf einer
You do not have permission to view link please Anmelden or Registrieren
veröffentlicht werden, doch es gibt schon jetzt
You do not have permission to view link please Anmelden or Registrieren
.Von „RSA“ haben wohl die wenigsten Internetnutzer etwas gehört. Dabei hängt davon in großem Maße die Sicherheit des Internetverkehrs ab. Jeder der heute Onlinebanking betreibt, Mails verschickt, in Internetshops kauft oder nur eine https-Webseite aufruft, muss sich auf RSA verlassen können.
[h=3]RSA-Verschlüsselung verstehen[/h]Jede Verschlüsselung steht vor der Schwierigkeit, zwischen den Kommunikationspartnern einen gemeinsamen Schlüssel auszutauschen, ohne dass er von Dritten abgefangen und mißbraucht werden kann. Dieses Problem wurde in den 1970ern gelöst. Die Trick besteht darin, dass man nicht mehr heimlich, sondern offen einen Teilschlüssel tauscht, mit dem andere die Kommunikation nicht belauschen können. Der Schlüssel wird dazu in einen öffentlichen und einen privaten Teil aufgespalten und als Schlüsselpaar bezeichnet. Verteilt wird nur der öffentliche Schlüssel, der die Nachricht nur verschlüsselt. Den Inhalt wieder lesbar machen kann nur der private Schlüssel. Dieser Schlüssel muss unbedingt geheim gehalten werden.
You do not have permission to view link please Anmelden or Registrieren
Das Verfahren wird als asymmetrische Verschlüsselung bezeichnet und ist die Grundlage des RSA-Schlüsselsystems. RSA steht für die Anfangsbuchstaben der Namen der Erfinder Rivest, Shamir und Adleman.
[h=3]Aufbau des RSA-Schlüssels[/h]Zur Erzeugung einen RSA-Schlüssels benötigt man drei Primzahlen. Die ersten beiden Zahlen p und q sollten möglichst groß und von ähnlicher Länge sein, aber nicht zu dicht beieinander liegen. Die dritte Primzahl hat meistens einen festen Wert von 65537 und wird Verschlüsselungs-Exponent e genannt.
Zur Erzeugung des öffentlichen Schlüssels werden die beiden großen Primzahlen p und v miteinander multipliziert und ergeben den RSA-Modulus n.
n = p · v
e = 65537
Modulus und Exponent findet man in allen öffentlichen RSA-Schlüsseln (siehe
You do not have permission to view link please Anmelden or Registrieren
).Die Sicherheit des öffentliche Schlüssel beruht darauf, dass es einem Angreifer in absehbarer Zeit nicht gelingt die beiden Komponenten p und v zu erraten oder aus dem Modulus n durch Faktorisierung zu berechnen.
Der private Schlüssel d wird erzeugt, indem zunächst die Eulersche Phi-Funktion φ() des Produktes der beiden Primzahlen berechnet wird. Das ist eine einfache Multiplikation.
φ👎 = φ(p·v) = (p-1)·(q-1)
Daraus wird der private Schlüssel d erstellt, der als Entschlüsselungs-Exponent bezeichnet wird, weil er verschlüsselte Nachrichten wieder lesbar macht. d ist das multiplikativ Inverse von e bezüglich des Moduls der Funktion φ👎. Das klingt komplizierter als es ist.
d = e⁻¹ mod φ👎 = 1/e mod (p-1)·(q-1)
d muss unbedingt geheim gehalten werden, während n und e öffentlich zugänglich sind.
[h=3]RSA-Schlüsselbeispiel[/h]Ein praktisches Beispiel mittels des freien Mathematikprogramms
You do not have permission to view link please Anmelden or Registrieren
erläutert die Verwendung des Schlüsselpaars. Das Beispiel lässt sich mit diesem
You do not have permission to view link please Anmelden or Registrieren
nachvollziehen:e = 65537
\\ Es werden zwei ähnlich große Primzahlen berechnet.
p = nextprime(2^64) \\ 8446744073709551629
q = nextprime(2^65) \\ 36893488147419103363
\\ Multiplikation der Primzahlen ergibt den RSA-Modulus n.
n = p*q \\ 680564733841876929822888034435936028327
m = (p-1)*(q-1) \\ Eulersche Phi Funktion von n: m = φ👎
\\ Aus e und m ergibt sich der private Schlüssel d.
d = 1/e % m \\ 287534628001704843192908297534611003865
\\ Ein Text wird verschlüsselt und wieder lesbar gemacht.
text = "tarnkappe.info"
\\ Der Text wird in ASCII-Buchstabencode umgewandelt.
chars = Vec(Vecsmall(text)) \\ [116, 97, 114, 110, 107, 97, 112, 112, ...
\\ Der Buchstabencode wird in das Zahlensystem zur Basis 256 umgewandelt
code = fromdigits(chars, 256) \\ 2360480060567527850800680270718575
\\ Der Code wird mit dem öffentlichen Schlüssel vom Absenders verschlüsselt.
geheim = lift(Mod(code, n) ^ e) \\ 204950903863101360211085884671147980080
\\ Der Empfänger entschlüsselt die Nachricht mit dem privaten Schlüssel.
code = lift(Mod(geheim, n) ^ d) \\ 2360480060567527850800680270718575
\\ Der entschlüsselte Code wird wieder lesbar gemacht.
text = Strchr(digits(code, 256)) \\ "tarnkappe.info"Was die jeweiligen Funktionen genau bewirken, lässt in der
You do not have permission to view link please Anmelden or Registrieren
nachschlagen.[h=3]Öffentlichen RSA-Schlüssel knacken[/h]Wer die Primzahlen p und v zu klein wählt (zu kurzer Schlüssel!) bekommt ein Problem, weil sich dann der private Schlüssel aus dem öffentlich berechnen lässt. Infinion verkauft seit 5 Jahre Chips, deren Firmware
You do not have permission to view link please Anmelden or Registrieren
ist und keine zufälligen Primzahlen p und q erzeugt. Deren Primzahlen lassen sich erraten.Hacker verwenden spezielle Verfahren, um den verschlüsselten Code eines schlechten Schlüssels mittels n und e zu knacken. Die Berechnung eines keys kann einige Zeit dauern. Hier sind es nur Bruchteile einer Sekunde:
\\ Faktorisierung von n: z = [p, q]z = factor👎~[1,] \\ [18446744073709551629, 36893488147419103363]key = lift(Mod(1,(z[1]-1)*(z[2]-1)) / e)
Der verschlüsselte Text kann mit key lesbar gemacht werden.
text txt = Strchr(digits(lift(Mod(geheim, n) ^ key), 256)) \\ "tarnkappe.info"
Es geht sogar noch kürzer nur mit n und e.
text = Strchr(digits(lift(Mod(geheim, n) ^ (1/e % eulerphi👎)), 256))
Der RSA-Schlüssel hat im Beispiel eine Länge von 129 Bit. Das ist mehr als das Doppelte dessen was dem Internet Explorer 5/6 von der US-Regierung für sicheres Bezahlen im Internet erlaubt wurde: 56-bit. Später gab es dann Microsofts High Encryption Pack mit 128 Bit. Solche geringe Verschlüsselung stellt sicher, dass die NSA mitlesen kann…
Hinweis: Längere Texte müssen in Code-Blöcke block aufgebrochen werden, die man separat verarbeitet muss. Die Zahl des Buchstabencodes in code muss kleiner sein als die nächste Zweierpotenz lim unterhalb von n: code lim = 2^x n
block = code % lim ; code = code / lim
You do not have permission to view link please Anmelden or Registrieren
You do not have permission to view link please Anmelden or Registrieren
Autor: Kati Mueller
You do not have permission to view link please Anmelden or Registrieren
