0 Daumen
2k Aufrufe

Aufgabe: RSA- Verschlüsselung

7 * 11 ergibt das RSA-Modul N ==> 77

Finde die Ordnung von \(\varphi(77)\) der Einheitengruppe von \(\mathbb{Z}_{77}\).

Meine Gedanken:

Es muss \(\varphi(77)\) so oft mit sich multipliziert werden, bis es in \(\mathbb{Z}_{77}\) die eigene Identität ergibt...?

Ich hole hier nur etwas aus den Untiefen meines Hirns hervor.

Wäre über einen gedanklichen Anstoß dankbar.

Avatar von

Hallo

Überschrift und Aufgabe sind verschieden?

 Dein Lösungsansatz ist richtig.

Gruß lul

hallo

sorry nur bis das Produkt 1 ergibt nicht wieder 77.

\(  phi(77) = 60  \)

Das bedeutet: \(  60^{30} mod 77 = 1  \)

D.h. in \(\mathbb{Z}_{77} hat phi(77) die Ordnung 30\) ?

Da probiert man sich ja zu tode, bis man das ohne Taschenrechner ausgerechnet hat.

Ist das tatsächlich die richtige Vorgehensweise?

Was genau möchtest Du berechnen? φ(77) ist die Ordnung der Gruppe (ℤ/77ℤ,)* das heißt diese Gruppe hat φ(77)=60 Elemente. φ(77) ist eine natürliche Zahl, also kein Element der Einheitengruppe. Möchtest du die Ordnung der Restklasse von 60 bestimmen?

Die Aufgabe besagt:

"Berechne die Ordnung von φ(77)  der Einheitengruppe von ℤ77." 

Meine Vermutung, wie die Ordnung berechnet wird, habe ich im ersten Post oben formuliert. Danach würde der Exponent, durch den phi(77) in Z77 1 ergibt, 30 sein:

phi(77) = 60
Das bedeutet: \(60^{30} = 1 mod 77\)

Die Ordnung wäre also 30... ?!

lul hat kommentiert, dass mein Grundgedanke richtig sei. Diesen habe ich verfolgt. Ergo das Ergebnis. Ob ich damit auf dem völlig falschen Dampfer bin oder nicht... keine Ahnung.

Schon 60^15 ist kongruent 1 mod 77. Die Ordnung ist also ≤15.

Meines Wissens gibt es keine effizienten Weg die Ordnung von Elementen zu berechnen, wenn man sonst keine Anhaltspunkte hat. Beim ausprobieren kannst du dir die meisten Fälle aber sparen, da die Ordnung eines Elements die Gruppenordnung teilt. Du musst also nur 60^x für x∈{2,3,4,5,6,10,12,15,20,30} ausprobieren

Aber ich denke die Aufgabe ist es nicht die Ordnung von 60 zu berechnen. Vor allem da die Aufgabe ja etwas mit dem RSA Verfahren zu tun hat:

1. Wahl zweier Primzahlen p,q und n:=pq

2. Berechnung der Gruppenordnung von (Z/pqZ)*, also Berechnung von φ(n)=(p-1)(q-1) <<< ich glaube das sollst du hier machen.

3. Wahl von 1<e<φ(n) mit ggT(e,φ(n))=1

4. Bestimmung von d mit ed Ξ 1 mod φ(n)

===> Öffentlicher Schlüssel (n,e), privater Schlüssel (n,d)

Es geht in der Tat um's RSA-Verfahren. Das was du mit den Rechenschritten beschreibst ist exakt die nachfolgende Aufgabe.

Die erste Aufgabe lautet wie gesagt... Zitat:

"Der RSA-Modul N ist das Produkt der Primzahlen 7 und 11. Berechne die Ordnung phi(77) der Einheitengruppe von Z77."

Es wird nach der Ordnung von phi(77) gefragt. Da muss ich dann wohl alle Möglichkeiten durchprobieren.



Wie kommst du auf {2,3,4,5,6,10,12,15,20,30}?

Hallo

 die Ordnung eines Elementes muss Teiler der Gruppenordnung, hier 60 sein.

Gruß lul

Also ich verstehe das so:

"Berechne die Ordnung phi(77) der Einheitengruppe von Z77."

===> du sollst die Ordnung von (Z/77Z)* bestimmen, also nur phi(77) berechnen, denn das ist die Gruppenordnung. Mehr ist da meiner Meinung nach nicht zu tun ;)

Wenn das wirklich der Fall ist, dann hat sich meine Frage erledigt. :-D

Da p = 7 und q = 11

ergibt sich phi(77) = (p - 1( * (q - 1) = 60

tadaaaa

Danke in jedem Fall für Deine Hilfe!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community