RSA im CAS - Invers-Modulo ExtEuklid, LCM, s ϕ(n)+1
RSA
- p, q Primfaktoren im CAS festlegen
- e auswählen → Slider grün → phi, e teilerfremd) - public key
- Extended Euklid einstellen → nd Slider grün → Iterationstiefe OK bei ExtGDC(0) - private key
- Alternative Berechnung d: Suchtiefe k nd (ggf. erhöhen von k (10), wenn kein d gefunden wird)
- Im CAS stößt man nicht so schnell an ein Zahlenlimit (10000 Stellen siehe Bild unten). Den ExtGCD zur Berechnung der Modulo-Inversen (zu e) hab ich trotzdem in der AlgebraView versteckt - er benötigt 3 Arrays und würde die Übersichtlichkeit im CAS stören.
- Berechnung ExtGCD in einer Matrix, weicht jedoch von dem bekannten a,b,q,r,x,y Muster ab. Iextgcd=IterationList({ Element(X, 2), Element(X, 1)-floor(Element(X, 1)/Element(X, 2)) Element(X, 2) , Element(X, 5), Element(X, 6), Element(X, 3)-floor(Element(X, 1)/Element(X, 2))*Element(X, 5), Element(X, 4)-floor(Element(X, 1)/Element(X, 2))*Element(X, 6) } ,X, {{a,b,1,0,0,1}}, nn) Mit nn Iterationstiefe angeben - Ergebnis in letzter Zeile Spalte 1,3,4! (siehe Aufgabe 2)
Auswahl public key
Aufgabe 1
Alice sendet an Bob die Nachricht (C1,C2) = (204,8), bestehend aus zwei Einzelnachrichten, welche sie beide zuvor mit Bobs öffentlichem RSA-Schlüssel (e,N) = (47,221) chiffriert hat. Wie lautet die entschlüsselte Nachricht, wenn Alice eine ASCII-Tabelle verwendet hat. Begründen Sie Ihr Vorgehen!
Aufgabe 2
Ein RSA-Verfahren mit privatem Schlüssel (d,n) = (21191,47053) Berechnen Sie den öffentlichen Schlüssel e und codieren Sie damit die zu übertragende Nachricht msg=1061.
Wie funktioniert die Idee hinter RSA
e encrypt - d decrypt - N msg
Es gibt also ein mit:
Fall 1: gilt (Fermat) und:
Fall 2: , also in und damit natürlich auch .
Wir haben somit und ebenso .
Da und teilerfremd sind, folgt .
entnommen E.Weitz Das RSA-Kryptosystem