RSA Verstehen?
In einem guten Buch verstehe ich die Erklärung nicht ganz für den RSA Algorithmus(rot markiert):
Es muss doch auf jeden Fall nach den Potenzgesetzen `e*d = 1` gelten falls `(N^e)^d = N` sein soll..
Warum ist dann ed = 1 + etwas?? Etwas müsste doch dann 0 sein
2 Antworten
Mir ist nicht ganz klar, wo dein Problem wirklich liegt. Jedenfalls wird e so gewählt, dass
Warum? Weil dadurch das Inverse zu e modulo Φ(n) existiert - das ist ja der private Schlüssel!
Aufgrund des erweiterten Euklidischen Algorithmus kann man schreiben
(der größte gemeinsame Teiler zweier Zahlen ist immer eine Linearkombination dieer Zahlen)
Daraus folgt:
und so ist
also das Inverse zu e
Genau, d ist das Multiplikativ-Inverse zu e und somit: d * e = 1
... natürlich im entsprechenden Restklassenring und nicht in der Menge der rationalen (oder reellen) Zahlen.
Der Entschlüsselungsexponent d ist der Kehrwert von e (mod phi(N)).
N = p * q mit p, q prim.
phi(x) ist die Anzahl der zu x teilerfremden natürlichen Zahlen <= x.
Falls x prim ist, ist phi(x) = x - 1, denn x kann nur durch 1 und sich selbst geteilt werden.
Beispiel: phi(5) = 4, da die Zahlen 1, 2, 3, 4 teilerfremd zu 5 sind.
(Die 1 ist ein Sonderfall, da Teilerfremdheit dadurch definiert ist, dass es keine Zahl außer der eins gibt, die beide Zahlen teilt.)
Da die Euler'sche Phi-Funktion multiplikativ ist, gilt:
phi(N) = phi(p) * phi(q) = phi(p * q)
Für p, q prim: phi(N) = phi(p) * phi(q) = phi(p * q) = (p - 1) * (q - 1)
e * d = 1 (mod phi(N))
Das heißt: e * d = 1 + "irgendein Vielfaches von phi(N)" (Genau das bedeutet ja Kongruenz.)
Oder mathematisch sauber: e * d = 1 + k * phi(N)
(Mit k eine beliebige ganze Zahl.)
Nunja und phi(N) = (p - 1) * (q - 1), für p, q prim also ...
e * d = 1 + k * (p - 1) * (q - 1)
Warum schreibt er dann ed = 1 + X