Fast alle der folgenden Fragen hat sich meine Studentin Elena Tsianaka ausgedacht, vielen Dank!
Wer an Hintergrundwissen interessiert ist, möge zum Lehrbuch Diskrete Mathematik für Einsteiger von A. Beutelspacher und M.-A. Zschiegner (Vieweg 2002) greifen.
Gesucht sind die Eulerschen φ-Funktionen von 6 und von 11, wir bieten jeweils drei Antworten an, bitte die richtige(n) ankreuzen:
a) φ(6) = 3
b) φ(6) = 2
c) φ(11) = 10
d) φ(11) = 2
e) Keine der Zahlen ist richtig
Wir bieten wieder einige Lösungen an, bitte die richtige(n) ankreuzen:
a) φ(5) = 4
b) φ(6) = 4
c) φ(8) = 4
d) φ(10 ) = 4
Gesucht sind Primzahlen p < q mit φ(n) = (p - 1) · (q - 1) = 20
Die kleinere Primzahl ist
Die größere Primzahl ist
Kommen wir zum RSA-Algorithmus (Einzelheiten zu diesem Algorithmus findet man hier )
Jemand will mit Hilfe der Primzahlen 7 und 13 den RSA - Algorithmus benutzen.
Gesucht sind die zugehörigen Zahl n und φ(n):
Die Zahl n ist und die Zahl φ(n) ist
Die nächsten Fragen behandeln den RSA-Algorithmus zu den Primzahlen p=3 und q=11. (Nochmal zu Infos zum RSA-Algorithmus hier )
Person A möchte Person B eine Nachricht schicken, Person B hat die Primzahlen p=3 und q=11 gewählt.
Gesucht ist der geheime Schlüssel d , wenn e=7 gewählt wird!
Die Zahl d ist .
Wir bleiben bei den Primzahlen p=3 und q=11 sowie bei e=7.
Der öffentlichen Schlüssel des verwendeten RSA-Algorithmus lautet (20,7) .
Wahr Falsch
Es geht weiterhin um den RSA-Algorithmus mit dem öffentlichen Schlüssel (33,7) und dem geheimen Schlüssel (3,11,3) .
In welche verschlüsselte Nachricht c muss Person A die zu übermittelnde Nachricht m=5 umwandeln?
Die verschlüsselte Nachricht besteht aus der Zahl c = .
Es geht ein letztes Mal um den RSA-Algorithmus mit p=3, q=11, n=33, &phi(n)=20, e=7, d=3 .
Person A schickt nun Person B die verschlüsselte Nachricht c=14.
Auf welche Art und Weise entschlüsselt Person B die erhaltene Nachricht c=14 zur Originalnachricht m=5?
Bitte das Kreuz an die richtige Stelle!
a) m = c · d mod 37 = 42 mod 37 = 5
b) m = cd mod 33 = 2744 mod 33 = 5
c) m = n / (c - d) + 2 = 33 / (14 - 3 ) + 2 = 5
Person X arbeitet mit dem RSA-Algorithmus. Sie hat den öffentlichen Schlüssel (n,e) = (35,11).
Person A möchte an Person X die Nachricht m=6 schicken. Wie lautet die verschlüsselte Nachricht c?
Die verschlüsselte Nachricht c lautet
Eine letzte Frage zum RSA-Algorithmus von Frage 9:
Auf Grund des öffentlichen Schlüssels (n,e) = (35,11) hat A an X die Nachricht 6 unverändert als 6 übertragen.
Folglich kann der geheime Schlüssel d ebenfalls 11 lauten.
b) und c) sind richtig:
b) φ(6) = 2 , denn nur die beiden Zahlen 1 und 5 (zwischen 1 und 6) sind teilerfremd zu 6
c) φ(11) = 10 , denn 11 ist eine Primzahl und alle zehn Zahlen von 1 bis 11 - 1 = 10 sind teilerfremd zu 11
Richtig ist d=3:
Das gesuchte d für den geheimen Schlüssel lautet 3.
Gegeben ist p=3 und q=11. Damit ist der erste Teil des öffentlichen Schlüssels von B die Zahl n=33, wegen φ(n)=2·10=20 bestimmt er als zweite Zahl seines öffentlichen Schlüssels e=7.
Gesucht ist d mit 7·d mod 20 = 1.
Wir bestimmen den geheimen Schlüssel d mit Hilfe des Euklidischen Algorithmus:
20 = 2 · 7 + 6, 7 = 1 · 6 + 1, also 1 = 7 - 1 · 6 = 7 - 1 · (20 - 2 · 7) = 3 · 7 - 20 .
Die gesuchte Zahl ist damt d = 3 .
a) φ(5) = 4 , die vier teilerfremden Zahlen sind 1,2,3,4 (Beachte auch: 5 ist eine Primzahl)
b) φ(6) = 4 ist falsch (siehe Antwort zu Frage 1)
c) φ(8) = 4 , die vier teilerfremden Zahlen sind 1,3,5,7
d) φ(10 ) = 4 , denn 10 = 2 · 5 (Produkt zweier Primzahlen), die vier teilerfremden Zahlen sind 1,3,7,9
A rechnet 611 mod 35 = [(62) 5 · 6 ] mod 35 = [(62) mod 35] 5 · [6 mod 35] = 15 · 6 = 6 .
n = p · q = 7 · 13 = 91 , die zugehörige Eulersche φ-Funktion φ(91) = φ(7·13) = (7 - 1 ) · (13 - 1) = 72
Zu a): Was soll die Zahl 37 in der Rechnung?
Zu b): Die einzige richtige Methode: m = cd mod 33 = 2744 mod 33 = 5
Zu c): Reinste Fantasie, die absolut nichts mit dem RSA-Algorithmus zu tun hat.
Wir berechnen c= me mod n = 57 mod 33 = 78125 mod 33 = 14 .
Wahr:
Der geheime Schlüssel kann d = e = 11 lauten, verfolgen wir noch einmal die Verschlüsselung:
A rechnet mit dem öffentlichen Schlüssel von X: me mod n = 611 mod 35 = ... = 6 = c
Jetzt entschlüsselt X mit seinem uns unbekannten geheimen Schlüssel d :
X rechnet cd mod n = 6d mod 35 und erhält die unverschlüsselte Nachricht m = 6
Wegen (wie oben gesehen) 611 mod 35 = 6 , gilt, kann der geheime Schlüssel ebenfalls 11 lauten.
Falsch:
Der öffentliche Schlüssel lautet (n,e) = (p · q , e) = (3 · 11 , 7) = (33,7).
Die gesuchten Primzahlen sind 3 und 11:
20 = 2 · 2 · 5 = 2 · 10 = ( 3 - 1) · (11 - 1)
Die Eulersche φ-Funktion einer Zahl n zählt alle Zahlen zwischen 1 und n, die teilerfremd zu n sind,
Beispiel: φ(4) = 2, denn ggT(1,4) = 1 = ggT(3,4), aber ggT(2,4) = 2 und ggT(4,4) = 4 .
Einfache Frage: Was ist die Eulersche φ-Funktion einer Primzahl?
Ferner kennt man die Eulersche φ-Funktion des Produkts zweier verschiedener Primzahlen p und q, nämlich
φ(p · q) = (p -1 ) · (q - 1)
zurück zur ersten Frage
Zum RSA-Algorithmus:
Der RSA-Algorithmus wurde 1987 von R. Rivest, A. Shamir und L. Adleman veröffentlicht. Er ist ein Public Key Verschlüsselungssystem, das auf dem Satz von Euler aufgebaut ist.
Wenn eine Nachricht mittels des RSA-Algorithmus versandt werden soll, muss die Nachricht in Form einer natürlichen Zahl sein. Zunächst wählt der Empfänger zwei verschieden große Primzahlen p und q, bildet das Produkt n = p · q und die zugehörige Eulersche φ-Funktion φ(n) = (p - 1 ) · (q - 1). Anschließend legt er eine natürliche Zahl e mit ggT( e, φ(n) ) = 1 fest. Abschließend bestimmt er eine natürliche Zahl e mit ( e · d ) mod φ(n) = 1 , zum Beispiel mit dem Euklidischen Algorithmus.
Der öffentliche Schlüssel ist nun das Zahlenpaar (n,e), der private das Zahlentripel (p,q,d). Die Primfaktorzerlegung von n ist so gut wie unmöglich, wenn die Primzahlen p und q genügend groß sind.
Möchte ein Sender nun eine Nachricht m senden mit ( m eine Zahl zwischen 1 und p·q - 1 ), so berechnet er mittels des öffentlichen Schlüssels (n,e) die Zahl c = me mod n , sendet die verschlüsselte Nachricht c dem Empfänger, der diese dann mit d potenziert und modulo n rechnet. Es ergibt sich nach dem Satz von Euler wieder die Nachricht m, da cd mod n = m .
zurück zur vierten Frage
zurück zur fünften Frage
© H. J. Samaga, 18.04.06