Moderne Verfahren

der

Kryptographie

RSA – Algorithmus

und

Digitale Signaturen

Einleitung

Dieser Vortrag beschäftigt sich mit dem Verschlüsselungsalgorithmus RSA und seiner Anwendung als Signaturverfahren. Ich werde die mathematischen Grundlagen erläutern und erklären wie man das RSA - Verfahren verwendet. Das RSA – Verfahren wurde im Jahre 1978 von den Mathematikern R.Rivest, A.Shamir und L.Adleman erfunden. Sie versuchten damals zu beweisen, das es nicht möglich wäre in der Public Key Kryptographie ein sicheres Verschlüsselungs- und Entschlüsselungsverfahren zu entwickeln.

1. Mathematische Grundlagen

Dem RSA Algorithmus liegt eine einfache mathematische Tatsache zu Grunde, die von Euler formuliert wurde.

Sei ü_n ¬ 1, 2, ..., n-1 ¡ und ü_n^* ¬ a i ü_n : ggT(a,n) = 1¡, die Teilmenge derjenigen Elemente die teilerfremd zu n sind. Dann bildet ü_n^* eine multiplikative Menge. Das multiplikative Inverse eines Elementes a i ü_n^* kann mit Hilfe der Vielfachsummendarstellung berechnet werden. Dann gilt:

Ist ggT(a,n) = 1= sa + tn, so ist a” ¬ s mod n die multiplikative Inverse ü_n^* aus von a

Die Anzahl der Elemente dieser Menge ist gerade î(n). î(n) ist die Eulersche î-Funktion, d.h. die Anzahl der zu n teilerfremden natürlichen Zahlen, die kleiner oder höchstens gleich n sind. Man kann für î(n) eine Formel angeben, wenn die Faktorisierung von n bekannt ist.

z.B.

Seien p und q zwei verschiedene Primzahlen

î(p) = p-1 oder î(pq) = (p-1)(q-1) usw.

î(n) zu berechnen mit der Kenntnis von p und q ist nicht schwer î(n) = (p-1)(q-1). Andererseits gilt aber auch p+q = n-î(n)+1, woraus sich durch Auflösen nach p und Einsetzen dieses Ausdrucks in die Formel pq = n die quadratische Gleichung q²–(n-î(n)+1+n ergibt , die man leicht lösen kann. Aber ohne die Kenntnis von p und q, lässt sich î(n) genauso schwer berechnen, als wenn man n faktorisieren müsste, wobei dies nicht bewiesen ist. Um diese Eigenschaften für die Kryptographie zu nutzen, insbesondere für den RSA-Algorithmus ist der

Satz von Euler-Fermat wichtig:

Für alle Zahlen a i ü_n^* gilt a^î(n) \ 1 (mod n)

Beweis : Sei ü_n^* = u₁,u₂, ... ,u_î(n)¡ Aus au_i @ au_j (mod n) für i @ j folgt, daß man ü_n^* auch als ü_n^* = au₁,au₂, ... ,au_î(n)¡ schreiben kann. Es gilt dann auch

und somit die Aussage a^î(n) \ 1 (mod n).

Aus diesen Kenntnissen kann man nun einen wichtigen Satz formulieren

Sei n = pq das Produkt zweier verschiedener Primzahlen p und q. Dann gilt für jede natürliche Zahl m R n und jede natürliche Zahl k die Gleichung

m^{k(p-1)(q-1)+1} mod n = m

Wie man sieht gilt: m^{k(p-1)(q-1)+1} = m (mod n) 3 m^kî(n)+1 = m (mod n). Da gilt: m^î(n) \ 1

(mod n), gilt auch m^kî(n) \ 1 (mod n): k g û, daraus folgt dann m^kî(n)Em \ m (mod n),also

m^kî(n)+1 \ m (mod n)

Anmerkung: Viefachsummendarstellung des ggT und erweiterter euklidischer Algorithmus

Sei d = ggT(a,b). Dann gibt es ganze Zahlen s und t mit d = sa+tb

Dann berechnet man s und t mit dem erweiterter euklidischer Algorithmus,

indem man den ggT(a,b) = d bestimmt und danach den Wed den man geangen ist

umformt und das Ergebnis einsetzt.

Bsp.: gesucht ggT(12,7) und die dazugehörige Linearkombination d = sa + tb

1) EUKLIDISCHER Algorithmus:

12 = 7 + 5

7 = 5 + 2

5 = 2E2 + 1 3) Einsetzen:

2 = 2E1 1 ggT(12,7) = 1 1 = 5 - 2E2

2) Umformen: 1 = 12 – 7 - 2E(7 – 5)

5 = 12 – 7 1 = 12 – 7 - 2E(7 – 12 + 7)

2 = 7 – 5 1 = 3E12 - 5E7 1 s = 3, t = 7

1 = 5 – 2E2 also haben wir die Linearkombination

gefunden.

2. RSA Verfahren

Um die Schlüssel zu erzeugen, die man später verwendet, geht man wie folgt vor:

Man wählt zufällig zwei Primzahlen p und q, für jeden Teilnehmer eine. p und q sind Primzahlen, die z.B. 150 Dezimalstellen (ca. 500 Bit) haben. Dabei gilt dann

m^{k(p-1)(q-1)+1} mod n = m. Um sicher zu gehen, das p und q Primzahlen sind,werden sie einem Primzahltest unterzogen. Ein Primzahltest ist der Spezialfall des

Satzes von Euler-Fermat und wird kleiner Fermat Satz genannt. Formuliert lautet er:

Für jede Primzahl p und jede Zahl a mit 1 R a < p gilt a^p-1 \ 1 (mod p)

Beweis : Mit p, ist p-1 die Ordnung der zyklischen Gruppe und für ein beliebiges a aus {1,2,3,...,p-1} gilt:

Wenn a, a², a³, ... a^r-1 verschieden ergibt sich nach r-Schritten das bereits vorhandene Element a^s a^r=a^s mit s < r (Da es nur maximal p-1 Elemente als Ergebnisse gibt, muß sich spätestens nach p Schritten ein Element wiederholen) so gilt nach Multiplikation mit a^-s a^r-s=1. Damit gibt es ein q = r-s mit a, a²,...,a^q=1. Damit bilden a, a², a³, ... a^q=1 eine Untergruppe, womit q ein Teiler von p-1 ist. also q*c=p-1 für eine natürliche Zahl c. Da a^q=1 gilt: (a^q)^c=1 also a^q*c=a^p-1 = 1 also gilt der kleine Fermat Satz.¿

Dann berechnet man die Zahl î(n) = (p-1)(q-1) und das Produkt n = pq. Als nächstes wählt man sich eine natürliche Zahl e, für die gilt: e ist teilerfremd zu î(x), d.h ggT(e, î(x)) = 1, und berechnet mit zum Beispiel dem erweiterten euklidischen Algorithmus die Zahl d, mit ed mod î(x) = 1. ed mod î(n) = 1 3 ed – k(p-1)(q-1) = 1 3 ed = 1+k(p-1)(q-1) für k g û.

Man berechnet d wie folgt: e und d mit d·e mod j(n) = 1. Die Zahl e wird beliebig gewählt, es muss jedoch gelten 1 < e < n-1 und ggT(j(n), e) = 1. s, t Î dann setzt setzt man a = j(n) und b = e, so ergibt sich ggT(j(n), e) = 1 = s·j(n) + t·e Modulo j(n) gerechnet ergibt sich (s·j(n) + t·e) mod j(n) = t·e mod j(n) = 1 Die gesuchte Zahl d ist also der Wert von t, der durch den erweiterten Euklidischen Algorithmus berechnet wird.

Nun kann man die gewonnenen Schlüssel verteilen. e zusammen mit n bilden den öffentlichen Schlüssel und d ist der geheime Schlüssel den nur derjenige besitzt, der verschlüsselte Nachrichten empfangen will. Die Zahlen p, q, sowie î(n) sind geheim zuhalten oder zu vernichten, da sie nicht mehr benötigt werden und man mithilfe dieser Zahlen die Schlüssel rekonstruieren kann.

Wie verschlüsselt und entschlüsselt man nun Texte. Sei m ein beliebiger Text. Sei f_e(m) ¬ m^e mod n, die Funktion mit der man den Text verschlüsselt. Und f_d(c) ¬ c^d mod n ist die Funktion zum Entschlüsseln des verschlüsselten Textes. Dann gilt f_d(f_e(m)) = (m^e)^d mod n = m. Eine Eigenschaft des RSA-Algorithmus die ihn so wertvoll für die Public Key Kryptographie macht ist, dass man aus der Kenntnis von n nicht auf die Zahlen e und d schließen kann, wenn man nicht die Faktoren p und q oder die Zahl î(n) = (p-1)(q-1) besitzt.

Beispiel 1:

Nehmen wir an, dass der öffentliche Schlüssel von Thomas 11 und
sein geheimer Schlüssel 3 sei und alle Rechnungen Modulo 15 durchgeführt werden. Wenn nun Werner die Zahl 2 verschlüsselt per mail an Thomas senden möchte, so muß er die Zahl 2 mit dem öffentlichen Schlüssel 11 von Thomas potenzieren und den Rest bei Modulo 15 an Thomas senden. Heraus kommt:

2¹¹ mod (15) = 2048 mod (15) = 8, da 2048/15 = 136 Rest 8.

D.h. Werner übermittelt Thomas die Zahl 8 und den "Modulus" 15. Zum Dechiffrieren potenziert Thomas die Zahl 8 mit seinem geheimen Schlüssel 3 und erhält:

8*8*8=512 aber mit der Verabredung alles Modulo 15 zu rechnen:
8 ³mod(15) = 512 mod(15) = 2, da 512 - gE15 = 2, mit g = 34

also erhält Thomas wieder die ursprüngliche Zahl 2.

3. Der RSA-Algorithmus als Signaturverfahren

Eine Signatur wird verwandt um ein digitales Schriftstück praktisch digital zu „unterschreiben“. Eine Signatur besitzt praktisch alle wichtigen Eigenschaften einer Unterschrift.

1. Echtheitseigenschaft

Diese Eigenschaft stellt sicher, dass das Dokument wirklich vom Unterschreibenden stammt. Es wird gefordert, dass die Unterschrift auf dem Dokument, der Unterschrift auf einem Vergleichsmedium entspricht. Diese Eigenschaft ist bei einer digitalen Signatur offensichtlich gegeben.

2. Identitätseigenschaft

Jede digitale Signatur ist persönlich. Man weiß immer von wem die Signatur stammt, das entspricht der Eigenschaft, dass man eine Unterschrift nur schwer fälschen kann.

3. Abschlusseigenschaft

Diese Eigenschaft signalisiert die Vollendung einer Erklärung. Das wird angezeigt, indem sie am Ende einer Erklärung steht.

4. Verifikationseigenschaft

Jeder Empfänger einer unterschriebenen Erklärung kann sich durch eine Unterschriftenvergleich absichern.

5. Warneigenschaft

Diese Eigenschaft soll den Unterschreibenden vor einer Übereilung bewahren. Dies ist gewährleistet durch die Komplexität einer Unterschrift. Diese Eigenschaft überträgt sich nicht auf die digitale Signatur.

Um einen Text zu signieren, verwendet man den RSA-Algorithmus und verschlüsselt das zu unterschreibende Dokument wie oben beschrieben. In der Praxis stellen sich allerdings einige Probleme. Die heutigen Signaturverfahren wendet man nicht auf lange Dokumente an, da die Verschlüsselungszeit nicht angemessen ist. Vor dem Verschlüsseln eines Dokumentes wendet man auf das Dokument eine Hash-Funktion h an. Mit dieser sogenannten öffentlichen Hash-Funktion berechnet man den Wert h(m), wobei m der zu verschlüsselnde Text ist. Damit bringt man das Dokument auf eine feste Länge, dass heißt man komprimiert ihn. Dieser Hash-Wert wird dann der Signaturfunktion unterworfen.

Um einen Text zu signieren, braucht man eine Signaturfunktion S_T und eine Verifikationsfunktion V_T um den signierten Text zu verifizieren. Wobei S_T geheim ist, also nur dem Teilnehmer T bekannt. V_T ist eine öffentlich zugängliche Funktion die jedem erlaubt die Herkunft eines des signierten Dokumentes zu überprüfen.

Zum signieren bildet man sig = S_T(h(m)). Dabei ist m das zu signierende Dokument, h(m) ist die Funktion mit der man das Dokument auf eine feste Länge komprimiert und S_T(h(m)) = sig, also das signierte Datenpaket des komprimierten Dokumentes. Um sig zu verifizieren wendet man auf sig, V_T an. Also V_T(sig) = h(m) und wendet h auf m an dann vergleicht man beide h(m) und kann T verfizieren.

Da nun S_T nur einem Teilnehmer bekannt ist weiß der Empfänger natürlich das der Teilnehmer das Dokument gesendet hat. Um mit dem RSA-Algorithmus zu signieren, wendet man S_T(m) ¬ m^d mod n an. Die Verifikationsfunktion ist dann V_T(sig) ¬ sig^e mod n = m, wobei m noch mit der Ursprungsnachricht verglichen werden muss.

Beispiel 2:

Thomas möchte die "Nachricht" 121 unterzeichnen und bildet zunächst den Hashwert der Nachricht: Hash = 1+2+1 = 4. Diesen Wert 4 unterschreibt er, indem er ihn mit seinem geheimen Schlüssel 3 verschlüsselt. Die Nachricht, der chiffrierte Hashwert der Nachricht und der Modulus wird als "unterzeichnetes Dokument" versendet.

Hashwert	verschlüsselt	Nachricht,Unterschrift,Modul
Thomas: 4 ->	4^3mod(15)= 64 mod(15) = 4 ->	121 , 4 , 15

Um die Nachricht zu überprüfen, wird Werner zunächst selbst aus der Nachricht den Hashwert ermitteln: 1+2+1 = 4. Dann wird Werner mit dem öffentlichen Schlüssel 11 von Thomas den mitgelieferten Hashcode dechiffrieren: 4¹¹ mod(15) = 4194304 mod(15) = 4 (Hierbei sind sowohl der verschlüsselte, als auch der unverschlüsselte Wert zufällig gleich 4 .) Stimmen diese Zahlen, wie in diesem Fall, überein, geht man davon aus ,daß die Nachricht unverfälscht ist, und vom Besitzer des zum öffentlichen Schlüssel gehörigen geheimen Schlüssel erstellt wurde.

eigener Hashwert	entschlüsselter Hashwert	Ergebnis
1 + 2 + 1 = 4	4^11mod(15)= 4194304 mod(15) = 4 ->	identisch

Bemerkung:

1) Die Sicherheit des RSA-Algorithmus hängt stark von der Schwierigkeit ab, große Zahlen faktorisieren zu können. Es ist allerdings nicht bewiesen, dass diese beiden Probleme gleichwertig sind.

2) Derzeit für n Zahlen zwischen 512 und 2048 Bit Länge benutzt. Nach den jüngsten Faktorisierungsergebnissen, bei denen die RSA 140-Challenge gebrochen, also eine 450 Bit-Zahl faktorisiert wurde, ist eine Schlüssellänge von mindesten 768 Bit zu empfehlen.

4. Attacken auf den RSA-Algorithmus

Ich möchte nun noch einige Angriffe auf den RSA-Algorithmus nennen, wobei ich erwähnen möchte, dass der RSA-Algorithmus noch ungebrochen ist und diese Angriffe nur auf Spezialfälle anwendbar sind. Aber aus der Kenntnis dieser Angriffe kann man Fehler beim erstellen von Schlüsseln vermeiden.

Homomorphie-Eigenschaft von RSA: Für den öffentlichen Schlüssel bestehend aus e,n eines RSA Systems gilt m₁^em₂^e mod n = (m₁m₂)^e mod n. Das sagt man kann eine Nachricht m₁m₂ verschlüsseln, ohne m₁ und m₂ zu kennen. Den gleichen Angriff kann man auf das RSA-Signaturverfahren starten. Und aus den Signaturen m₁^d mod n und m₂^d mod n kann man eine gültige Signatur (m₁m₂)^d mod n einer Nachricht m₁m₂ bilden, ohne den privaten Schlüssel d zu kennen. Das Problem, dass sich bei diesem Angriff stellt ist, dass die Nachrichten m₁ und m₂ einen Sinn ergeben, die Nachricht m₁m₂ allerdings nicht. Das liegt daran, dass die Redundanz der Nachrichten durch die Multiplikation zerstört werden. Hat man eine Nachricht die nicht redundante Werte beinhaltet, sollte man Redundanz einfügen um diesem Angriff zu entgehen.

Generieren eines gültigen Nachricht-Signatur-Paares: Man kann mit dem RSA-Verfahren leicht aus einer Signatur eine Nachricht erzeugen, die diese Signatur besitzt (siehe oben). Dazu wählt man sig aus und bildet dazu m ¬ sig^e mod n. Die Überprüfung der Signatur m^d = sig^ed = sig mod n ergibt dann das richtige Ergebnis. Aber auch diesem Angriff kann man entgehen wenn man verlangt, dass die Nachricht m redundant sein soll.

Verwendung kleiner Exponenten: Aus Gründen der Effizienz wird in einigen Fällen von e=3 als Exponent des öffentlichen Schlüssels vorgeschlagen. Wenn jedoch in einem solchen RSA-System drei Teilnehmer y₁, y₂ und y₃ die gleiche Nachricht verschlüsseln, so kann man aus den Kryptogrammen den Klartext berechnen. Seien

y₁ = m³ mod n₁

y₂ = m³ mod n₂

y₃ = m³ mod n₃

die von den Teilnehmern erzeugten Chiffre-Texte dann kann man mit Hilfe des chinesischen Restsatzes die eindeutige Lösung

y = m³ mod n₁n₂n₃

berechnen. Die Nachricht m muss dabei allerdings kleiner sein als jeder der drei Moduli n₁, n₂ und n₃. Daraus folgt m³ < n₁n₂n₃. Dies hat aber zur Folge, dass

y = m³ mod n₁n₂n₃ = m³

dass heißt man kann einfach die dritte Wurzel aus m bzw. y ziehen und erhält die ursprüngliche Nachricht.

Gleicher Modul für mehrere Benutzer: Verwenden zwei Benutzer A und B den gleichen RSA-Modul so kann jeder die Nachricht des anderen lesen. Der Benutzer B kennt beispielsweise die Exponenten e_A, e_B und d_B. Er berechnet

h = (e_Bd_B-1):ggT(e_A,e_Bd_B-1) = kgv(e_A,e_Bd_B-1):e_A

Die Zahl h ist ein Vielfaches von î(n) = (p-1)(q-1) und teilerfremd zu e_A. Nun kann man mit Hilfe des erweiterten Euklidischen Algorithmus die Vielfachsummendarstellung

cEh+dEe_A = 1

berechnen. Da cEh mod î(n) = 0 gilt, hat B so eine Zahl d gefunden, die dEe_A mod î(n) = 1 erfüllt. D.h. Benutzer B kann durch potenzieren mit d alle Nachrichten von A entschlüsseln.

Verschlüsselung von Nachrichten, die in einer algebraischen Beziehung zueinander stehen: Die wichtigsten aktuellen Angriffe auf das RSA-Verfahren stammen von oder sind unter Mitwirkung von Don Coppersmith entstanden. Als frappierendes Beispiel für diese neuen Attacken, zeige ich wie einfach man auf m schließen kann wenn man nur die Chiffre-Texte m und m+1 kennt und wenn zur Verschlüsslung der Exponent e=3 verwendet wird. Sei c₁ = m³ mod n und c₂ = (m+1)³ mod n

(c₂+2c₁-1) : (c₂-c₁+2) = ((m+1)³+2m³-1) : ((m+1)³-m³+2) = (3m³+3m²+3m) : (3m²+3m+3) = m