Anzahl möglicher öffentlicher Schlüssel im RSA-Verfahren

Question

Aufgabe:

Es seien p und q verschiedene Primzahlen.

a)  Wie viele mögliche  öffentliche Schlüssel gibt es für das RSA-Verfahren mit Modul N= p·q ?

b)  Zeige zusätzlich zu a), dass die Anzahl der möglichen  öffentlichen Schlüsselegerade ist.

c)  Kann man p und q so wählen, dass es einen geraden öffentlichen Schlüssel gibt?

Begründe jeweils deine Aussagen. Ohne Begründung werden grundsätzlich 0 Punkte vergeben

Problem/Ansatz:

Ein öffentlicher Schlüssel ist ja einfach ein e ∈ℤφ(N), welcher teilerfremd zu φ(N) ist, also zum Bleistift:

p = 7 und q = 13, dann ist N = 7*13 = 91

und φ(N) = (7-1) * (13 - 1) 72

Dann ist z.B. e = 5 ein öffentlicher Schlüssel,, weil 5 ∈ℤ_φ(72) denn 5 ist teilerfremd zu φ(91), also teilerfremd zu 72.

Also wäre die Antwort "alle möglichen öffentlichen Schlüssel, die teilerfremd zu φ(N) sind. Jetzt steht in der Aufgabenstellung aber "wie viele", außerdem gibt uns die Teilaufgabe b) den Hinweis, dass die gesuchte Anzahl gerade ist, was ebenfalls zu zeigen ist. Es ist also eine konkrete Zahl gesucht. Wie soll das gehen, wenn p und q beliebige Variablen sind?

Comments

Hi Marceline,

die Eulersche-Phi-Funktion gibt dir doch genau die Anzahl der teilerfremden Zahlen zu einer Zahl N, die kleiner als N sind. Also ist bei a) \(\varphi(\varphi(N))\) gesucht.

Gruß

---

Danke Yakyu,

aber ich hab ja gar kein p und q gegeben, um N = p*q und folglich auch φ(N) und φ(φ(N)) als exakte Zahl zu berechnen, die gerade ist.

---

Du sollst bei dieser Aufgabe keine exakte Zahl bestimmen, wenn du keine Zahlen gegeben hast.

Die Lösung zu a) ist also \(\varphi((p-1)(q-1))\). Damit kann man die Anzahl berechnen sofern \(p\) und \(q\) gegeben sind.

Tipp zu b): \(p\) und \(q\) sind jeweils ungerade

Tipp zu c): nein

---

Ach sooooooooooo..das geht ja voll..Ok, vielen Dank für die nachvollziehbare Erklärung, Yaku.

---

zu b)

p und q sind ungerade

dann sind p-1 und q-1 wieder gerade

Wenn jetzt φ((p-1)(q-1) berechnet werden soll, ist das umgeschrieben ja

(p-1)-1 und (q-1)-1.

Das wären wieder ungerade Zahlen.

Ich muss ja zeigen, dass die Anzahl der möglichen öffentlichen Schlüssel gerade ist, also dass die Anzahl der Zahlen, die teilerfremd zu φ((p-1)(q-1)), also teilerfremd zu (p-1)-1 und (q-1)-1 sind, gerade ist. Aber ich weiß ja immer noch was genau e ist. Die Teilmengen einer ungeraden Zahl sind selbst immer ungerade Zahlen, falls das weiterhilft.

Oder ist die Lösung einfach, dass die Lösung der eulerschen Phi-Fkt für zwei gerade Zahlen stets gerade ist?.

---

Die Formel die du anwendest gilt nur für Primzahlen. p-1 und q-1 sind aber keine Primzahlen. Du musst über die Primfaktorzerlegung argumentieren und dir zunutzen machen dass 4 ein Teiler von (p-1)(q-1) ist.