1. Einleitung
Das RSA – Verfahren ist heutzutage das wohl bekannteste und weitverbreiteste öffentliche asymmetrische Verschlüsselungsverfahren. Es wurde 1977 von Ron Rivest, Adi Shamir und Len Adleman entwickelt und wurde 1978 das erstemal veröffentlicht. Es war der erste vollständige Public - Key - Algorithmus, der sich sowohl für die Verschlüsselung, als auch für digitale Signaturen (Authentifizierung) eignet. Unter all den Public – Key – Algorithmen, die im Laufe der Jahre veröffentlich wurden, ist RSA bei weitem am einfachsten zu verstehen und zu implementieren. Die Sicherheit von RSA beruht auf der Schwierigkeit, große Zahlen zu faktorisieren. Im Gegensatz zu herkömmlichen Verfahren wie beispielsweise DES (Data Encryption Standard) wird bei RSA nicht mit einem geheimen Schlüssel gearbeitet, sondern mit einem öffentlichen Schlüssel für den Verschlüsselungsteil und einem geheimen für die Dechiffrierung. Beide Schlüssel sind zwar voneinander Abhängig, jedoch in einer Weise, daß es durch das Faktorisierungsproblem (fast) unmöglich ist aus dem öffentlichen Schlüssel den geheimen zu berechnen, vorausgesetzt die Schlüssel sind groß genug.
Das RSA- Verfahren ist in den USA patentiert, außerhalb aber frei benutzbar (Das Patent läuft am 20. September im Jahr 2000 ab).Der größte teil der gängigen Verschlüsselungssoftware basiert auf dem RSA-Verfahren. Das Verfahren ist aber nicht nur als Software implementiert, sondern auch auf dem frein Markt als Hardware erhältlich (Siemens, British Telecom, AT&T,....). RSA ist ein De-Facto-Standard in weiten Teilen der Welt. Die ISO definiert fast einen RSA- Standard für digitale Signaturen.
2.1 Primzahlen:
Eine Primzahl ist eine ganze Zahl größer als 1, die nur 1 und sich selbst als Teiler hat. Es gibt unendlich viele Primzahlen (Satz von Euklid). In der Kryptographie, speziell bei Verfahren mit öffentlichen Schlüsseln, benutzt man oft große Primzahlen (mit 512 Bit und mehr).
Kleine Primzahlen
Große Primzahlen
2.2 ggT(x,y):
Größter gemeinsamer Teiler der Zahlen x und y.
2.3 Relativ prim:
Zwei Zahlen sind relativ prim zueinander, wenn sie außer 1 keinen gemeinsamen Teiler haben. (ggT(x,y) = 1Þ
x und y sind relativ prim zueinander) Eine Primzahl ist zu allen anderen Zahlen mit Ausnahme ihrer Vielfachen relativ prim.
2.3. Modulare Arithmetik :
Die Modulo-Funktion gibt als Ergebnis den Rest einer Division zurück. Es gilt: a º
b (mod n) falls es eine ganze Zahl k gibt, mit a = b + k*n . b wird auch als Residuum von a modulo n bezeichnet.
Def. Die Vollständige Residuenmenge, ist die Menge der ganzen Zahlen, die als Ergebnis der Funktion (a mod n) in Frage kommen. [also 0.....n-1].
Bsp: Residuenmenge von (mod 12) : {0,1,2,3,4,5,6,7,8,9,10,11}
Def. Die Teilmenge der Residuen (a mod n), die relativ prim zueinander sind wird als reduzierte Residuenmenge bezeichnet.
Bsp: reduzierte Residuenmenge von (mod 12) : {1,5,7,11}
Modulare Arithmetik verhält sich wie normale Arithmetik: sie ist kommutativ, assoziativ und distributiv. Außerdem erhält man das gleiche Ergebnis, wenn man alle Zwischenresultate modulo n reduziert oder erst die ganze Rechnung durchführt und dann das Ergebnis modulo n reduziert :
(a+b) mod n = ((a mod n) + (b mod n)) mod n
(a-b) mod n = ((a mod n) – (b mod n)) mod n
(a*b) mod n = ((a mod n) * (b mod n)) mod n
(a*(b+c)) mod n = (((a*b) mod n)+((a*c) mod n)) mod n
Damit können auch Potenzen bestimmt werden, ohne riesige Zwischenergebnisse zu berechnen:
a8 mod n = ((a² mod n)² mod n)² mod n
a25 mod n = (a* a8* a16) mod n = ......... (((((((a² mod n)*a) mod n)² mod n)² mod n)² mod n) * a) mod n
2.3.1 Der Kehrwert modulo einer Zahl:
Das allgemeine Problem lautet, ein x zu ermitteln, das 1 = (a * x) mod n erfüllt oder anders: a-1 º
x (mod n).
Diese Funktion ist nur dann eindeutig lösbar, wenn a und n relativ prim zueinander sind!
Tip: der erweiterte Euklidsche Algorithmus kann auch den Kehrwert einer Zahl modulo n berechnen!(ein Beispiel!)
2.4 Der Kleine Satz von Fermat:
Ist m Primzahl und a kein vielfaches von m, dann gilt : am-1 º
1 (mod m)
2.5 Eulerische j–Funktion:
Die Eulerische j
-Funktion j
(n) beschreibt die Anzahl der Elemente in der reduzierten Residuenmenge.
Ist n eine Primzahl, so gilt: j (n) = n-1
Ist n = p*q wobei p und q Primzahlen sind, so gilt: j
(n) = (p-1) (q-1)
Falls der ggT(a,n) = 1 ,gilt nach der Eulerschen Verallgemeinerung des kleinen Satzes von Fermat aj
(n) mod n = 1 Damit läßt sich der Kehrwert einer Modulo-Operation leicht bestimmen:
x = aj (n) -1 mod n
Bsp: (5 mod 7) Kehrwert = 56-1 mod 7 = 55 mod 7 = 3
3.1 Schlüsselerzeugung:
Um die beiden Schlüssel zu erzeugen, wählt man zufällig zwei große Primzahlen p und q, die gleichlang sein sollten. In der Praxis nimmt man Primzahlen ab 100 Stellen. Die beiden Primzahlen müssen geheim bleiben, während das Produkt der beiden Primzahlen mit zum öffentlichen Schlüssel gehört. Es wird mit n bezeichnet (n=p*q)!
3.1.1 Öffentlicher Schlüssel:
Den öffentliche Schlüssel oder auch Chiffrierschlüssel e wählt man zufällig, aber so, daß er mit (p-1)*(q-1) relativ prim ist, also keine gemeinsamen Faktoren mit (p-1)*(q-1) hat. Gemeinsam mit n bildet e den öffentlichen Schlüssel.
Jetzt kann mit der Formel C = me mod n eine Zahl m die kleiner als n ist verschlüsseln.
3.1.2 Privater Schlüssel:
Mithilfe des erweiterten Euklidschen Algorithmus berechnet man schließlich den privaten Schlüssel oder auch Dechiffrierschlüssel d, so daß gilt: d = e-1 mod ((p-1)*(q-1)). d ist also der Kehrwert von e bezüglich der Modulo Operation ((p-1)*(q-1).
Mit M = cd mod n wird die chiffrierte Zahl wieder entschlüsselt.
3.2 Ein konkretes, einfach zu verstehendes und leicht nachzurechnendes Beispiel:
- Wahl der Primzahlen p = 11 und q = 7
- Damit ergibt sich n = p*q = 77
- Wahl des Chiffrierschlüssels e = 17 (keine gemeinsamen Faktoren mit ((p-1)* (q-1) = 60)
- Errechnen des Dechiffrierschlüssels d = 53 , denn (d*e) mod ((p-1)*(q-1)) = 1 denn: 53 * 17 mod 60 = 1
- Transformieren der Nachricht M= "Kryptographie" in Zahlen. (Schema: A=01, B=02,....Z=26)
Þ M= 11182516201507180116080905
- Zerlegen in gleichlange Blöcke, die kleiner als n sind
Þ M= 11 18 25 16 20 15 07 18 01 16 08 09 05
- Verschlüsseln jedes Blocks nach der Formel C = me mod n :
C1 = 1117 mod 77 = 5,054...*1017 mod 77 = 44
C2 = 1817 mod 77 = 72
C3 = 2517 mod 77 = 9
C4 = 16 17 mod 77 = 25
C5 = 2017 mod 77 = 48
C6 = 1517 mod 77 = 71
C7 = 7 17 mod 77 = 28
C8 = 1817 mod 77 = 72
C9 = 1 17 mod 77 = 1
C10 = 1617 mod 77 = 25
C11 = 8 17 mod 77 = 57
C12 = 9 17 mod 77 = 4
C13 = 5 17 mod 77 = 3
- Zusammensetzen der verschlüsselten Nachricht und übermitteln: 44 72 9 25 48 71 28 72 1 25 57 4 3
- Der Empfänger entschlüsselt die Nachricht mit seinem privatem Schlüssel nach M = cd mod n
M1 = 4453 mod 77 = 11
M2 = 7253 mod 77 = 18
M3 = 9 53 mod 77 = 25
M4 = 2553 mod 77 = 16
M5 = 4853 mod 77 = 20
M6 = 7153 mod 77 = 15
M7 = 2853 mod 77 = 7
M8 = 7253 mod 77 = 18
M9 = 1 53 mod 77 = 1
M10 = 2553 mod 77 = 16
M11 = 5753 mod 77 = 8
M12 = 4 53 mod 77 = 9
M13 = 3 53 mod 77 = 5
- Zusammensetzen der Nachricht und zurücktransformieren der Zahlen in Buchstaben !
Man Vermutet, daß die Sicherheit von RSA auf dem Problem der Faktorisierung großer Zahlen basiert.
D.h: Die Wiederherstellung des Klartextes aus dem öffentlichen Schlüssel und dem Chiffriertext äquivalent zur Faktorisierung des Produkts der beiden Primzahlen sind.
1977:
100$ Preisgeld für die Faktorisierung einer 129 Stellen langen RSA-Zahl (429 Bit).
-16 Jahre blieb das Problem trotz intensiver Bemühungen ungelöst.
1993:
Nicht ein Superrechner, sondern viele eigenständige Rechner des Internets wurden mit dem Problem konfrontiert. Bei den Freiwilligen, die dem Projekt beiwohnten, wurde eine Faktorisierungssoftware installiert die auf einer "Quadratischen Siebmethode mit Mehrfachpolynomen" basiert. So wird jeder Rechner mit einem kleinen Teil des Gesamtproblems belastet.
Þ Die ZAHL WURDE FAKTORISIERT!
Aufwand:
-8 Monate, 600 Freiwillige aus 20 Ländern mit einem geschätzen Rechenaufwand von 5000 MIPS-Jahren,
Endberechnung:
-Auf einer MasPar MP-1 (bestückt mit 16384 Prozessoren, wobei jeder einzelne Prozessor 200000 Integeroperationen pro Sekunde durchführen kann!).
Schätzungen: Die NSA (National Security Agency, USA) hätte für die Faktorisierung nur 4 Wochen benötigt
Þ
Die Sicherheit hängt von der Länge des Schlüssels ab:
Die RSA Laboratorien empfehlen:
768 bit für den privaten Gebrauch,
1024 bit für den geschäftlichen Gebrauch und
2048 bit für wirklich wichtige Schlüssel.
Ein 768-bit Schlüssel sollte bis ins Jahr 2004 benutzbar sein.
Durch einen längeren Schlüssel steigt natürlich auch die Ver- bzw. Entschlüsselungszeit der Nachricht, was aber in Zukunft durch höhere Rechenleistung wieder neutralisiert wird. So wird es auch in Zukunft so schwer wie heute sein einen Schlüssel zu knacken, vorausgesetzt man erweitert seinen Schlüssel proportional zur Rechenleistung und es wird kein einfacherer Algorithmus zur Faktorisierung von großen Zahlen erfunden!
Übersicht der Regelung von Kryptographie verschiedener Länder (Lokale Kopie der englischen Seiten)
Rechtliche Situation, politische Diskussion (Lokale Kopie der Seiten von Ulf Möller)
Zusammenstellung einiger Zitate aus dem Artikel von Ulf Nöller (s.o):
Anstoß:
Rede vom Bundesinnenminister Kanther zum 5. IT-Sicherheitskongresses "Gebrauch von Systemen mit zugriffsmöglichkeit für Straf- und Sicherheitsbehörden sollen vorgeschrieben werden."
Die Sicherheitsbehörden befürchten, daß ihnen durch solche Verfahren die Möglichkeit zum Abhören und Überwachen im Bereich der Telefon-,Fax- und Datenkommunikation verlorengingen.
Wirtschaftminister Rexrodt: "Es darf keine Nutzungsbeschränkung für Kryptographie geben!"
Reaktionen der Parteien 1996/1997:
CDU/ CSU:
-Verbot von "Krypto-Geräten", mit denen Straftäter sich einer angeordneten Überwachung entziehen
-Daß durch rechtlich zulässige Überwachungsmaßnahmen erlangte Daten von den Sicherheitsbehörden nicht "gelesen" werden können, könne nicht richtig sein.
-Im Kampf gegen Organisierte Kriminalität müsse Verschlüsselung "unverzüglich" europaweit unter Genehmigungsvorbehalt gestellt werden.
-Kryptographie müsse sicher sein, gleichzeitig müsse "ein Staat schon aus Staatsschutzgründen in der Lage sein, sich und seine Bürgerinnen und Bürger zu schützen, also gegebenenfalls Daten entschlüsseln önnen bzw. entschlüssen lassen können."
SPD:
"Wenn der Staat praktisch auf jede kommunikative Beziehung einen Zugriff hat, dann heißt das, daß man damit anonymen Instanzen, die ja häufig auch demokratisch nicht besonders streng kontrolliert sind, Informationsmaterial an die Hand gibt." Andererseits sei es wichtig, eine effiziente Kontrolle krimineller Kommunikation zu etablieren. Die dürfe jedoch nicht darauf hinauslaufen, daß die Regierung ihren Bürgern vorschreibe, in welcher Sprache sie kommunizieren, oder bei Bedarf eine Übersetzung fordere. Dem stehe Artikel 5 GG entgegen, der das Recht auf freie Meinungsäußerung in Wort, Schrift und Bild garantiert: "Bei einer Kryptographieregelung läge der Fall ähnlich." (Otto Schily)
"Die panische Furcht der Geheimdienste vor Mobiltelefonen, die sie nicht abhören können, ist genauso albern wie der betuliche Wunsch, das `anarchische' Internet so rasch als möglich von Pornographie oder fragwürdiger politischer Propaganda zu reinigen. Die Mafia stellt sich auf jede Regulation ein; in der Regel schneller als die Polizei"
B90:
"Die Möglichkeiten zur vertraulichen Kommunikation auf elektronischem Weg dürfen nicht durch Restriktionen bei deren Verschlüsselung (Kryptierung) eingeschränkt werden. Die Vorstellung, durch ein Verschlüsselungsverbot die Kriminalität im Netz bekämpfen zu können, ist angesichts der technischen Möglichkeiten, eine Kryptierung von Daten selbst wieder unsichtbar zu machen (z.B. Steganographie), unsinnig und dient allenfalls der Legitimierung undemokratischer Kontrollbefugnisse des Staates. Auch ein indirektes Kryptierverbot, wie es z.B. durch die Pflicht, den Verschlüsselungscode bei den Sicherheitsbehörden zu hinterlegen, lehnen wir aus den gleichen Gründen ab."
FDP:
"Es ist ein Angriff auf die Meinungsfreiheit und die Privatsphäre des mündigen Bürgers und auf die Selbstbestimmung und Vertraulichkeit seiner Daten." Den Kräften in unserem Staat, die dieses Verbot wollen, fehle Kompetenz, Übersicht und Weitblick, da sie die technischen Möglichkeiten der unerkennbaren Verschlüsselung verleugnen oder nicht kennen, die Konsequenzen der Internationalität moderner Kommunikation nicht erkennen und die Zukunftschancen des Informationsstandortes Deutschland nicht erwägen würden.
"....daß es ein Krypto-Gesetz, das zum Ziel hat, die Verschlüsselungsmöglichkeiten der Nutzer zu beschränken oder sogar zu verbieten, mit der F.D.P. nicht geben wird".Was man damit beabsichtige, sei erstens technologisch nie erreichbar, zweitens dürfe die Preisgabe von Schutzmöglichkeiten privater, wirtschaftlicher und wissenschaftlicher Daten vor unautorisierten, unlauteren oder sogar kriminellen Machenschaften nicht zugelassen werden.
Bundestagsvizepräsident Burkhard Hirsch fragt, wie hoch soll eine Strafdrohung sein solle, damit es ein wirklicher Straftäter vorzieht, unverschlüssselt über seine Tatpläne zu korrespondieren. Er nennt Fälle von unerkennbarer Verschlüsselung und betont, wegen der erkennbaren Sinnlosigkeit eines solchen Verbots sei es selbst im sogenannten "Dritten Reich" und in der DDR nicht strafbar gewesen, verschlüsselte Briefe zu schreiben. "Man könnte sich kaputtlachen, wenn man nicht wüßte, daß es tatsächlich so gemeint ist"
PDS:
"Das elektronische Briefgeheimnis ist zu gewährleisten" (Bundestags-Antrag)
"Die Bundestagsgruppe wird bei der anstehenden Beratung eines Gesetzes zum Verbot von kryptographischen Verfahren, in Umsetzung der Empfehlung des Europarates, gegen eine solche Restriktionspoltik stimmen"
Nach Ansicht des ZVEI wäre ein Krypto-Gesetz schädlich für Wirtschaft und Privatpersonen. Die Pläne ähnelten dem Versuch, Bankräuber durch eine Geschwindigkeitsbegrenzung zu behindern
BND:
"Es ist zwingend erforderlich, den Privat-, den Banken-, den Geschäftsverkehr verstärkt durch
Kryptierung gegen Angriffe von außen zu schützen. Gerade als Datenschützer sage ich das. Selbstverständlich aber muß es wie auf allen Gebieten, wo wir geschützte Bereiche haben, in besonderen Ausnahmefällen für staatliche Stellen möglich sein, gleichwohl an Informationen heranzukommen." Auch beim Post- und Fernmeldegeheimnis gebe es die Möglichkeit der Durchbrechung unter gesetzlich festgelegten Voraussetzungen.
LKA:
Werner Paul, Sachgebietsleiter Computerkriminalität beim Bayerischen LKA, behauptet: "Die ganz heißen Geschäfte wie Waffen- oder Rauschgifthandel laufen nicht mehr über Telefon, sondern werden verschlüsselt über die weltweiten Datennetze abgewickelt." Von einem Krypto-Verbot hält er dennoch nichts: Es sei wohl "irrelevant": Wenn jemand eine Straftat begehen wolle, werde er sich "davon auch nicht abhalten lassen, weil es ein Gesetz gibt, das die Verschlüsselung verbietet"
Quellenangabe:
- Angewandte Kryptographie (Bruce Schneider) , A&W
- Internetseite von Ulf Möller zum Thema Kryptographieverbot
- iX : 9/94