RSA-Verfahren, Public-Key-Verschlüsselung
Kryptographie mit MuPAD, Buch-Version
Prof. Dr. Dörte Haftendorn, Mathematik mit MuPAD 4.02,
(ex. in 2.5 vom Sept 99 Nov.02 und in 3.11 Sept. 05) Feb.07, Juni 07
http://haftendorn.uni-lueneburg.de www.mathematik-verstehen.de
www.mathematik-sehen-und-verstehen.de
Buch: Mathematik sehen und verstehen Seite 36ff (mit Angriff Seite 38)
####################################################################
---------------------------------------eigene Zahlentheorie Ergänzungen-----------------------------------------------------------------------------------------------------
Im Dateimenu bei "Eigenschaften" sehen die beien Prozeduren zur Umwandlung von Text in Zahl und Zahl in Text, ebenso zstern(n),
daher können sie hier ausgeführt werden.
---------------------------------------eigene Zahlentheorie Ergänzungen------------------------------------------------------------------------------------------------------
Vorbereitungsphase
Anton bereitet seine Schlüssel vor.
saat:=random(100001..999999): saat():
p:=numlib::prevprime(floor(sqrt(saat()*10^50)));
10^27
//Exponent 50 z.B.auch 300
q:=numlib::prevprime(floor(sqrt(27*10^50)));
//p:=19;q:=23; //für kleine Beispiele
n:=p*q;
ph:=(p-1)*(q-1);
Wahl einer beliebigen, aber zu ph teilerfremden Zahl e
repeat
r:= random(2..ph): e:=r():
until gcd(ph,e)=1 end_repeat:e;
Bestimmung des modularen Inversen zu dieser Zahl
igcdex(ph,e);
d:=op(igcdex(ph,e),3); // letztes Element euklid. Algorithmus
if (d<0) then d:=d+ph: end_if:d; //Korrektur bei negativem d
d*e mod ph
d ist Antons geheimer Schlüssel.
Der Öffentlichkeit gibt er e und n bekannt.
e;n;
##################################################################
Anwendungsphase Berta schreibt an Anton
-------------------------------------------------------------------
Berta will Anton einen Text senden, den nur Anton lesen kann.
---------------------------------------eigene Zahlentheorie Ergänzungen-----------------------------------------------------------------------------------------------------
Im Dateimenu bei "Eigenschaften" sehen die beien Prozeduren zur Umwandlung von Text in Zahl und Zahl in Text, daher können sie hier ausgeführt werden.
---------------------------------------eigene Zahlentheorie Ergänzungen------------------------------------------------------------------------------------------------------
m:=txToZoo("Dienstag im Medley");
// ASCII, ASCII-28->zweistellig
[68, 105, 101, 110, 115, 116, 97, 103, 32, 105, 109, 32, 77, 101, 100, 108,
101, 121]
gcd(m,n); // soll 1 sein, Probe
c:=powermod(m,e,n);
###############################################################
Anwendungsphase Anton liest, was Berta schrieb
-----------------------------------------------------------------------------------------------------------------
Anton empfängt diesen verschlüsselten Text
und wandelt ihn in Klartext um.
m2:=powermod(c,d,n);
zooToTx(m2)//Zweierpakete +28->ASCII
[40, 77, 73, 82, 87, 88, 69, 75, 4, 77, 81, 4, 49, 73, 72, 80, 73, 93]
[68, 105, 101, 110, 115, 116, 97, 103, 32, 105, 109, 32, 77, 101, 100, 108,
101, 121]
###################################################################################
Signatur Erstellung
Anton signiert einen der Öffentlichkeit präsentierten Text
M:=txToZoo("Vertraut Emil nicht");
[86, 101, 114, 116, 114, 97, 117, 116, 32, 69, 109, 105, 108, 32, 110, 105, 99,
104, 116]
sig:=powermod(M,d,n);
Anton stellt den Text und sig öffentlich aus.
Eigentlich wendet er auf M vorher noch eine Hashfunktion an,
die öffentlich bekannt ist und M auf 128 Bit reduziert. Hier ist h(M)=M.
############################################################
Signatur Verifizierung
-----------------------------------------------------------------------------------------------------------
Berta will prüfen, ob das wirklich Antons unveränderter Text ist.
MB:=M: //Berta berechnet ebenfalls aus dem erhaltenen MB das h(M),
//hier ist h(MB)=MB. Und sie bildet ein Mtest aus der Signatur.
Mtest:=powermod(sig,e,n);
if (modp(MB,n)=modp(Mtest,n)) then print("Anton hat wirklich unterschrieben")
else print("Vorsicht, das ist nicht Antons Original!") end_if;
"Anton hat wirklich unterschrieben"
Wenn aber nun MisterX verändert hat
//MB:=txToZoo("Vertraut Emil ");
//MB:=M+1234567890
MB:=M+1;
Mtest:=powermod(sig,e,n);
if (modp(MB,n)=modp(Mtest,n)) then print("Anton hat wirklich unterschrieben")
else print("Vorsicht, das ist nicht Antons Original!") end_if;
"Vorsicht, das ist nicht Antons Original!"
######################## Angriff auf das RSA-Verfahren#########
Stetige Potenzfunktion und Umkehrfrage:
Für wWelches x wird der Wert 224 erreicht?
plotfunc2d(224,x^(281), x=1..1.03, ViewingBoxYRange=0..300,
LegendVisible=FALSE, LineWidth=1, GridVisible=TRUE)
Diskrete Potenzfunktion und Umkehrfrage:
Für welches x wird der Wert 224 erreicht?
li:=zstern(437);
pli:=[[k,powermod(k,281,437)] $ k in li];
plot(plot::Listplot(pli, LinesVisible=FALSE),plot::Polygon2d([[1,224], [436,224]]) );