RSA-Verschlüsselung/Chinesischer Restsatz

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

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.

Was möchtest Du wissen?