Äquivalenz zwischen Faktorisierung von n und Berechnung von φ(n)

 aufwärts

Die Sicherheit der RSA-Ver­schlüsselung beruht darauf, dass nur n bekannt ist, nicht aber φ(n). Ein Angreifer, dem es gelingt, φ(n) ausfindig zu machen, kann aus dem öffentlichen Schlüssel e den privaten Schlüssel d als das multi­plikativ inverse Element modulo φ(n) berechnen.

Beim RSA-Verfahren ist die Zahl n das Produkt aus zwei ver­schiedenen Primzahlen p und q. Öffentlich bekannt ist aber nur die Zahl n, jedoch nicht die beiden Faktoren p und q, aus denen sich n zusammensetzt. Bei kleinen Zahlen, etwa n = 77, lassen sich die Faktoren leicht ermitteln, bei sehr großen Zahlen, etwa Zahlen der Länge 1024 Bit, jedoch nicht. Nach heutigem Stand ist die Faktorisierung von großen Zahlen undurch­führ­bar, weil zu rechen­aufwendig.

Jeder, der p und q ausfindig machen kann, ist in der Lage, φ(n) zu berechnen, mittels der Formel

φ(n)  =  (p-1)·(q-1)

Die Berechnung von φ(n) ist also höchstens so schwer wie die Faktorisierung von n, also die Zerlegung von n in die Faktoren p und q.

Aber vielleicht lässt sich ja φ(n) auf andere Art und Weise sehr viel leichter bestimmen, ohne die Zahl n vorher zu faktorisieren? Die Antwort ist nein. Im Folgenden wird gezeigt, dass die Berechnung von φ(n) mindestens so schwer ist wie die Faktorisierung von n.

Denn jeder, der φ(n) bestimmen kann, ist auch in der Lage, p und q zu berechnen. Dies wird im Folgenden gezeigt.

Berechnung von p und q aus n und φ(n)

Es seien n und φ(n) gegeben; wir berechnen daraus p und q.

 

Als erstes berechnen wir den Wert von p + q aus n und φ(n):

φ(n) = (p-1)·(q-1)
 = pq – p – q + 1
 = n – (p+q) + 1

 folgt    p + q   =   n – φ(n) + 1

 

Wir erzeugen nun eine quadratische Gleichung, deren Lösungen p und q sind:

(x – p)·(x – q)ausmultiplizieren  =  x2 – p·x – q·x + p·q zusammenfassen  =  x2 – (p+qx + p·qfür p+q und für pq einsetzen  =  x2 – (n – φ(n) + 1)·x + n

Diese quadratische Gleichung lässt sich mit der Formel von Vieta lösen (die auch als p-q-Formel bezeichnet wird, wobei jedoch p und q dort eine andere Bedeutung haben als die hier vorkommenden Faktoren p und q). Die beiden Lösungen der quadratischen Gleichung sind die gesuchten Faktoren p und q.

 

Insgesamt ist damit gezeigt, dass die Berechnung von φ(n) genauso schwer ist wie die Faktorisierung von n.

 

Zahlenbeispiel

Gegeben seien n = 77 und φ(n) = 60; gesucht ist die Faktorisierung n = p·q.

Es ist zunächst

n – φ(n) + 1   =   77 – 60 + 1   =   18

Die quadratische Gleichung lautet somit

x2 – 18·x + 77

Die Formel von Vieta liefert die Lösungen

x1,2p-q-Formel anwenden  =  9   ±  Wurzel81 – 77ausrechnen  =  9  ± Wurzel4ausrechnen  =  9 ± 2

Die beiden Lösungen lauten also x1 = 9 + 2 = 11 und x2 = 9 – 2 = 7.

Wir haben also aus n = 77 und φ(n) = 60 die Faktorisierung 77 = 11 · 7 berechnet.

 

Übung

Aufgabe 1:  

Gegeben sind n = 2911 und φ(n) = 2800. Zerlegen Sie n in die Primfaktoren p und q.

Hinweis: Wenn Sie es sich einfach machen wollen, berechnen Sie n – φ(n) + 1  =  2911 – 2800 + 1  =  112 und tragen dann -112 und 2911 in das Formular zur Lösung einer quadratischen Gleichung ein. Die beiden Lösungen sind die gesuchten Faktoren von n.

Aufgabe 2:  

Gegeben sind n = 293141 und φ(n) = 292032. Zerlegen Sie n in die Primfaktoren p und q.

 

Literatur

[RSA 78]R.L. Rivest, A. Shamir, L.M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21, 2, 120-126 (1978)
[KK 10]C. Karpfinger, H. Kiechle: Kryptologie. Vieweg+Teubner (2010)
[Lan 18]H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[Weitere Informationen]

Buch  

 

 

Zurück zu:   [RSA-Verschlüsselung]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 07.12.2017   Updated: 13.03.2019
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik