RSA-Verschlüsselung/Chinesischer Restsatz
Brauche ich für die RSA-Verschlüsselung den Chinesischen Restsatz?
2 Antworten
Es ist ja n = p * q.
damit lässt sich ja phi(n) = (p-1) * (q-1) berechnen und damit auch der geheime Schlüssel d. Um also einen Text zu entschlüsseln, braucht man lediglich eine Exponentation modulo n.
Mit dem chinesischen Restsatz lässt sich dies aber in zwei Teile aufteilen, nämlich in modulo p und modulo q. Dies sind zwar mehr Rechnungen, weil aber p und q wesentlich kleiner als n sind, ist das Verfahren effizienter. Beachte aber, dass dies nur für die Dechiffrierung möglich ist, denn beim Chiffrieren kennt derjenige ja nur n, nicht aber p und q.
So weit ich weiß, brauchst du den chinesischen Restsatz nicht für RSA, es geht komplett ohne. Mithilfe des chinesischen Restsatzen, lässt sich aber effizienter rechnen. Schau z.B. mal hier:
http://de.wikipedia.org/wiki/RSA-Kryptosystem#RSA_mit_dem_Chinesischen_Restsatz