RSA Aufgaben

Aus ProgrammingWiki
< PMG2022
Archivierte Version vom 2021-01-24T11:27:30+00:00. Aktuelle Version

Aufgabe 1

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

Gib N an:



(wieder in " " schreiben)

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



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



  • man wähle zwei möglichst große Primzahlen p und q

  • Verschlüsseln mit öffentlichem Schlüssel (e, N), wobei N = p * q und e eine beliebige Zahl ist aber teilerfremd zu (p - 1)*(q - 1)
    • 

  • Entschlüsseln mit privatem Schlüssel d, den man aus d*e = 1  mod  ((p - 1)*(q - 1)) erhält
    • 


    
'''Es gelten also die Formeln:
      für das Verschlüsseln der Nachricht M zum chiffrierten Text C: C = M^e(mod N) 
    

      sowie für das Dechiffrieren von C in die Ausgangsnachricht M: M = C^d(mod N) 
    '''



    
Ein Beispiel:
    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.

    
Es soll die Nachricht XMAS gesendet werden. Dazu müssen die Buchstaben in ASCII-Code umgewandelt werden.
    

    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.

    
Ascii-Listen finden sich z.B. unter http://www.torsten-horn.de/techdocs/ascii.htm oder http://www.asciitable.com/ 

    

    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.


    
Nur wer die passenden Primzahlen kennt, mit denen der öffentliche Schlüssel erzeugt wurde, kann die Botschaft entschlüsseln. Das ist allein Alice. 
    Ihr privater Schlüssel folgt aus
     
d*e = 1  mod  ((p - 1)*(q - 1))
    
d*7 = 1  mod  (16*10)
    
d*7 = 1  mod  (160))
    
d = 23, weil 23*7 = 161(!?)


    
Nun braucht nur noch die Nachricht entschlüsselt werden:
M = C^d(mod N)
    
M = 11^{23}(mod 187)
    
M = 88 =  X.