PMG2022/RSA Aufgaben

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
== Aufgabe 1 ==

Alice wählt zwei verschiedene Primzahlen $p$ = 5 und $q$ = 11. 

Gib $N$ an:
<run id="600d58b962ab8">

</run>
''(wieder in " " schreiben)''


Ermittle $(p-1)*(q-1)$ und eine dazu teilerfremde Zahl $e$ des öffentlichen Schlüssels:

<run id="600d59a22e2b2">
</run>


Hier nun den öffentlichen Schlüssel $(e, N)$ angeben:

<run id="600d59a22e30f"></run>



<li>man wähle <u>zwei möglichst große Primzahlen</u> $p$ und $q$
<li>Verschlüsseln mit '''öffentlichem''' Schlüssel $(e, N)$, wobei $N = p * q$ und $e$ eine beliebige Zahl ist aber <u>teilerfremd</u> zu $(p - 1)*(q - 1)$</li>
<li>Entschlüsseln mit '''privatem''' Schlüssel $d$, den man aus $d*e = 1  mod  ((p - 1)*(q - 1))$ erhält</li>
<br>
'''<font color="green">Es gelten also die Formeln:

<ul>für das Verschlüsseln der Nachricht M zum chiffrierten Text C: $C = M^e(mod N)$ </ul>
<ul>sowie für das Dechiffrieren von C in die Ausgangsnachricht M: $M = C^d(mod N)$ </ul></font>'''
<br><br>
<font color="red">Ein Beispiel:</font>

Bob will an Alice eine Nachricht schicken.
Alice hat einen öffentlichen Schlüssel wie folgt gewählt:
Die Primzahlen seien $p$=17 und $q$=11.
Damit ist $N$=187, für $e$ wird 7 gewählt. Dieser Schlüssel wird ''veröffentlicht''.
<br>
Es soll die Nachricht ''XMAS'' gesendet werden. Dazu müssen die Buchstaben in ASCII-Code umgewandelt werden.<br>
<br>Betrachten wir zunächst das ''X'', so wird diese in ASCII durch $1011000$ dargestellt. Dies entspricht der Dezimalzahl 88, damit sei die (Teil-)Nachricht $M=88$.
<br>
''<font size="1">Ascii-Listen finden sich z.B. unter [http://www.torsten-horn.de/techdocs/ascii.htm] oder [http://www.asciitable.com/] </font>''
<br>
<br>

Für die Verschlüsselung ergibt sich nun $C = 88^7(mod 187)$
Dies ist 11 (nachprüfen!), damit schickt Bob die geheime Nachricht $C=11$ an Alice.
<br><br>
Nur wer die passenden Primzahlen kennt, mit denen der öffentliche Schlüssel erzeugt wurde, kann die Botschaft entschlüsseln. Das ist allein Alice. <br>Ihr privater Schlüssel folgt aus<br> 
$d*e = 1  mod  ((p - 1)*(q - 1))$<br>
$d*7 = 1  mod  (16*10)$<br>
$d*7 = 1  mod  (160))$<br>
$d = 23$, weil $23*7 = 161$(!?)
<br><br>
Nun braucht nur noch die Nachricht entschlüsselt werden:
$M = C^d(mod N)$<br>
$M = 11^{23}(mod 187)$<br>
$M = 88 =$  ''X''.