Zum Inhalt springen

Beweisarchiv: Kryptografie: Kryptosysteme: Korrektheit des RSA-Kryptosystems

Aus Wikibooks

Beweisarchiv: Kryptografie

Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit
Kryptosysteme: Korrektheit des RSA-Kryptosystems · Sicherheit des GMR-Signatursystems
Pseudozufall: Sicherheit des s²-mod-n-Generators


Korrektheit des RSA-Kryptosystems

[Bearbeiten]

Einleitung

[Bearbeiten]

Das RSA-Kryptosystem verschlüsselt einen Klartext , indem dieser mit dem öffentlichen Schlüssel exponentiert wird. Der Schlüsseltext kann durch Exponentieren mit dem geheimen Schlüssel wieder entschlüsselt werden. Es gelten dabei folgende Voraussetzungen:

Für die Wahl der Schlüssel gilt:

bezeichnet die eulersche φ-Funktion.

Behauptung

[Bearbeiten]

RSA entschlüsselt korrekt:

Beweis

[Bearbeiten]

Laut Voraussetzung gilt:


Der Satz von Euler-Fermat besagt:

Also gilt und :

Der Satz von Euler-Fermat gilt nur für die Einheiten in . Deshalb muss noch gezeigt werden, dass (**) auch für die teilerfremden Elemente in und gilt. Das einzige teilerfremde Element in beiden Ringen ist die Null.

Da

gilt (**) für alle Elemente aus und

Nach dem Chinesischen Restsatz folgt daraus:

Nun erhält man durch Einsetzen von :

Wikipedia-Verweise

[Bearbeiten]

 RSA-Kryptosystem
 Eulersche Phi-Funktion
 Satz von Euler-Fermat
 Chinesischer Restsatz


Beweisarchiv: Kryptografie

Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit
Kryptosysteme: Korrektheit des RSA-Kryptosystems · Sicherheit des GMR-Signatursystems
Pseudozufall: Sicherheit des s²-mod-n-Generators