Das RSA-Verfahren

Einführung

Das RSA-Verfahren ist eine asymmetrische Verschlüsselungsmethode, die bereits 1978 erstmals vorgestellt wurde. Der nach den Nachnamen seiner Erfinder Ron Rivest, Adi Shamir und Leonard Adelman benannte Kodierungs­algorithmus gehört derzeit zu den sichersten und auch bekanntesten.

p Primzahl I q Primzahl II N Hauptmodul k Nebenmodul E Verschlüsselungsexponent D Entschlüsselungsexponent "x relativ prim zu y" bedeutet, dass der kleinste gemeinsame Teiler von x und y das Produkt beider Zahlen ist. "a ≡ b (mod c)" gesprochen: a ist kongruent                    zu b modulo c bedeutet: b = a modulo c (N,E) Privater Schlüssel (N,D) Öffentlicher Schlüssel M Message; Klartext C Chiffrat; Codierter Text

Seine Si­cher­heit be­ruht auf der Tat­sa­che, dass es ein­fach ist aus zwei gro­ßen Prim­zah­len (>150 Stel­len) eine na­türli­che Zahl zu er­zeu­gen, aber schwie­rig ist um­ge­kehrt die­se Zahl zu fak­to­ri­sie­ren. Ein weit­er­er Si­cher­heits­as­pekt liegt dar­in, dass es fak­tisch un­end­lich vie­le Prim­zah­len gibt. Da­raus lässt sich ab­lei­ten, das es auch un­end­lich vie­le Schlüssel­kom­bi­natio­nen gibt.

Das RSA-Verfahren findet in vielerlei Verschlüsse­lungs­software seinen Einsatz. Die wohl berühmteste RSA Implementierung ist in Phil Zimmermanns PGP (Pretty Good Privacy) zu finden. PGP ist für fast alle Betriebsysteme erhältlich und arbeitet derzeit mit einer Schlüssellänge von bis zu 1024 bit (ca. 1,8e308 Kombinationen). Weiterhin verwendet die Deutsche Telekom das RSA-Verfahren. Und auch Novell arbeitet mit diesem Verschlüsselungsalgorithmus.

Nachfolgend sehen Sie nun die Vorgehensweise für die Erzeugung des privaten und des öffentlichen Schlüssels. Außerdem wird die Ver- und Entschlüsselung anhand eines Beispiels gezeigt.

Schlüsselerzeugung 1. Man suche sich zwei große Primzahlen, nenne sie p und q.       p = 13      q = 37 2. Man multipliziere p und q miteinander und nenne diese Zahl N.       N = p * q = 13 * 37 = 481 3. Man multipliziere p-1 und q-1 miteinander und nenne diese Zahl k.       k = (p – 1) * (q – 1) = (13 – 1) * (37 – 1) = 432 4. Man suche sich eine Zahl E und berechne dann D, so dass      D * E ≡ 1 (mod k), wobei E relativ prim zu k ist.       D * E ≡ 1 (mod 432)       also D * E ist z.B. 1, 433, 865, 1297, 1729, ...       E = 5       => D = 173      D * E = 865  OK! Verschlüsselung 1. Mit dem Privaten Schlüssel N = 481 ∧ E = 5   ⇒ (N,E) Verschl. wird der Wert 17 ME  ≡ C (mod N) ⇔   175  ≡ C (mod 481) ⇔   1419857  ≡ 426 (mod 481) 2. Mit dem Öffentlichen Schlüssel N = 481 ∧ D = 173   ⇒ (N,D) Verschl. wird der Wert 17 MD  ≡ C (mod N) ⇔   17173  ≡ 153 (mod 481) Entschlüsselung 1. Mit dem Öffentlichen Schlüssel N = 481 ∧ D = 173   ⇒ (N,D) Entschl. wird der Wert 426 CD  ≡ M (mod N) ⇔   426173  ≡ 17 (mod 481) 2. Mit dem Privaten Schlüssel N = 481 ∧ E = 5   ⇒ (N,E) Entschl. wird der Wert 153 CE  ≡ M (mod N) ⇔   1535  ≡ 17 (mod 481)

Sicherheitsaspekte

1. Das „Knacken“ eines RSA-Codes ist direkt nur möglich, indem man N in seine Primfaktoren p und q zerlegt. Dies stellt aber bisher bei großen Primzahlen (> 150 Stellen) ein schweres mathematisches Problem dar.
   
   Zur Erinnerung:
   N = p * q           im Bsp:          481 = 13 * 37
   
   Den bisher größte Erfolg bei einem Angriff auf einen RSA Schlüssel erziehlten vier Wissenschaftler 1994. Es gelang ihnen eine 129-stellige RSA Zahl zu faktorisieren, indem sie das Problem in kleinere Teilprobleme zerlegten, diese weiterreichten und sich die Ergebnisse per E-Mail zuschicken ließen. Insgesamt arbeiteten 600 Menschen aus über 20 Länder circa 8 Monate lang daran.
   Mathematiker nehmen heute an, dass bei Verlängerung des Schlüssels auf 250 Stellen mit einer Zerlegung nicht einmal in einer Million von Jahren zu rechnen ist - aber wer weiß schon, was morgen ist ;)
   
   Die 129-stellige Zahl,die faktorisiert wurde lautete:
   114 381 625 757 888 867 669 235 779 976 146 612 010 128 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541
   
   
2. Durch eine schlechte Implementierung des RSA-Verfahrens ist die Sicherheit dieses Systems sehr gefährdet.
   
   Beispiele:
   
   • bei der Definition der Primzahlen werden diese nicht wirklich zufällig ausgewählt
   • Ein öffentlicher Schlüssel kann mit dem zugehörigen privaten unterzeichnet werden