1. Frage Extended GCD(),
richtig D = Ax + By = Au + Bv, dabei sollte der GCD Algorithmus bestimmte Regeln beachten. Er swapt A,B wenn A > B ist. Wenn es den einfachen GCD von A,B gibt und dieser dann D <> 1 zurückliefert, so heisst das das beim Erweiterten GCD von A,B ebenfalls D <> 1 sein wird. Mathematisch gesehen heist dies dann das es kein eindeutiges Multiplikatives Inverses von A,B gibt. D.h. man berechnet D = GDCExt(A,B, x,y) und wenn D <> 1 dann gibt es kein A^-1 mod B. Somit heisst dies das A und B zueinander NICHT teilerfremd sind (relativ prime zueinander), was aber eine Vorraussetzung dafür ist das A im modularen Ring B invertiert werden kann. Natürlich kann X,U < 0 sein aber dies spielt keine Rolle, den in modularen Ringen -> mod M, wird aus dem negativen U sehr leicht ein positives und korrektes U indem man U' = U + M rechnet.
2. multiplikatives Inverse, A^-1 mod M
Richtig es würden negative Zahlen entstehen. Aber beachte das wir im Modularen Ring arbeiten. Z.b. 2 mod 3 == -1 mod 3. Somit ist es durchaus möglich neagtive Zahlen zu beschreiben, über 3 + -1 == 2 mod 3.
Wir haben hier aber einen negative Exponenten, was nicht gleichbedeutend mit negativem A ist. Ein Negativer Exponent wird bei Ganzzahlen diese Zahl A zu einer gebrochenen Zahl mit Nachkommmastellen machen. Aber wir arbeiten in modularen Ringen ! und dort kann man sehr wohl mit negativem Exponenten arbeiten und das Resultat wird denoch eine Zahl im Bereich -M < 0 < M sein. Vorausgesetzt A ist relativ teilerfremd zu M. Deshalb wird bei allen Kryptoverfahren meistens M als Primzahl oder Produkt zweier großer Primzahlen definiert. Da M nun eine Primzahl ist ist jede Zahl kleiner M automatisch teilerfremd zu M. Logisch, da die erste Zahl die nicht teilerfremd zu M ist eben 1*M bzw. 2*M ist.
So, was macht nun das multiplikative Inverse ?
Am besten ist hier ein Vergleich zu den Gebrochenen Zahlen. Wir haben eine Zahl R = 4 und benötigen das Reziproke, den Kehrwert. Dieser ist 1/R = R^-1 = 0.25. Jetzt wollen wir eine Zahl X = 12 durch 4 dividieren. Es gibt zwei Wege dazu 1.) X / R = Y oder eben X * R^-1 = Y.
Nun in Modularen Ringen wird X / R == Y mod M über X * R^-1 == Y mod M gerechnet. Es gibt nur eine Lösung wenn R relativ teilerfremd zu M ist.
Also, wie der Name "multiplikatives Inverse" besagt ist das nichts anderes als der Kehrwert einer Zahl in mpdularen Ringen.
Oben benutze ich zwei verschiedene Gleichheitszeichen. 1.) = -> ist gleiche und 2.) == -> ist kongruent. In modularen Ringen wird immer == benutzt. Da 3 mod 4 == -1 mod 4 == -5 mod 4 == 7 mod 4 == 11 mod 4 usw. usw. ist. D.h. in modularen Ringen zu M einer Primzahl wird jede Zahl in das Set der Zahlen S = {0 <= E < M} mod M gemappt. Die Anzahl der teilerfremenden Elemente E in S ist M -1 = Phi(M). Sollte M = P * Q sein, also zwei Primzahlen P * Q, dann ist die Anzahl der Elemente E in S mod M = Phi(P, Q) = LCM(P -1, Q -1). D.h. der Ring M = PQ enthält nun die Menge aller teilerfremden Elemente der Subringe Sp = {0 <= Ep < P} mod P und Sq = {0 <= Eq < Q} mod Q mit Sp || Sq = Phi(P, Q) = LCM(P -1, Q -1).
Das || steht für die Vereinigungsmenge. Ich habe absichtlich diese Schreibweise genommen das normalerweise das + dafür richtig wäre. Aber man verwechselt dann die Addition zweier Sets mit der Addition zweier Zahlen. Denn wenn wie zB. zwei Sets haben {1,2,3,4} und {3,4,5,6} dann ist {1,2,3,4} + {3,4,5,6} = {1,2,3,4,5,6}, und somit die Anzahl der Element der Sets 4 + 4 = 6 -> 4 || 4 = 6.
3.) Empfehlung von mir
Kaufe dir das Buch
"Einführung in die Kryptographie" von Johannes Buchmann ISBN 3-540-66059-3. Buchmann geht in diesem Buch sehr ausführlich und einfach verständlich in die nötige Mathematik ein. Das Buch ist leicht mißverständlich benamt und sollte heissen
"Einführungn in die Mathematik der Kryptographie". Denn Buchmann konzentriert sich vor allem auf z.B. obige Fragen, statt auf symmetrische Verfahren.
4.) Fragen
Wenn der erweiterete GCD zweier Zahlen A,B ein D <> 1 zuckrückgibt und somit A,B nicht teilerfremd zueinander sind, WIE wird dann PHI(A, B) berechnet ??
Bei RSA ist N = P*Q, warum muß man nun überprüfen ob GCD(E, N) = GCD(D, N) = 1 ist ??
Gruß Hagen