p:=numlib::prevprime(floor(sqrt(5*10^150)));
ElGamal-Verfahren, Public-Key-Verschlüsselung
Kryptographie mit MuPAD,
Prof. Dr. Dörte Haftendorn, Mathematik mit MuPAD 4.02, (es ex. Vorlesungs-Version)
(ex. in 2.5 Okt 99 , vom Nov.02 und in 3.11 Sept. 05) Feb.07
http://haftendorn.uni-lueneburg.de www.mathematik-verstehen.de
####################################################################
Verabredungsphase
Anton, Berta und Tobi wollen gemeinsam kommunizieren und eine gemeinsame
Schlüsselliste vereinbaren. Tobi bereitet als Grundlage p und g vor.
p:=numlib::prevprime(floor(sqrt(5*10^150)));
//p:=113:g:=987:
r:= random((p div 2)..p-1): g:=r();
Sie vereinbaren eine Verschlüsselungsfunktion
unassign(f,f_inv,kk,cc): f:=(kk,cc)->(kk*cc):f(kk,cc);
f_inv:=(kk,cc)->(cc div kk):f_inv(kk,cc);
Er teilt dieses allen mit, jeder darf das wissen.
Jeder wählt sich eine beliebige Zahl t als geheimen Schlüssel und
berechnet einen öffentlichenTeil seines Schlüssels:
r:= random((p div 2)..p-1): ta:=r();tAnton:=powermod(g,ta,p);
r:= random((p div 2)..p-1): tb:=r();tBerta:=powermod(g,tb,p);
r:= random((p div 2)..p-1): tt:=r();tTobi:=powermod(g,tt,p);
schluessel:=matrix([tAnton,tBerta,tTobi]);//Öffentliche Schlüsselliste
Vorbereitungsphase für eine Sendung
Anton will an Berta und Tobi etwas senden. Er wählt sich eine beliebige Zahl a und berechnet:
r:= random((p div 2)..p-1): a:=r();antonOffen:=powermod(g,a,p);
k_AB:=powermod(tBerta,a,p);k_AT:=powermod(tTobi,a,p);
Dieses Antons Kommunikationsschlüssel für Berta und Tobi.
Nun will Anton an die anderen beiden einen Text senden, den nur die beiden lesen können.
txToZoo:=proc(w)
local i,le,ur,wz;
begin
wz:=0:le:=length(w);ur:=numlib::toAscii(w);
print(ur);
(wz:=wz+(ur[i]-28)*100^(le-i)) $ i=1..le:
return(wz);
end_proc:
zooToTx:=proc(wz)
local ur,le,i;
begin
ur:=[]:
repeat ur:=[wz mod 100].ur;
wz:=floor(wz/100);
until wz<=0 end_repeat;
print(ur); le:=nops(ur);
//erstmal aus der Zahl eine Liste machen
//dann die Listenzahlen in ASCII
for i from 1 to le do ur[i]:=ur[i]+28 end_for:
print(ur);
return(numlib::fromAscii(ur));
end_proc:
m:=txToZoo("Montag im Medley");
//m:=10;
[77, 111, 110, 116, 97, 103, 32, 105, 109, 32, 77, 101, 100, 108, 101, 121]
Sendung
A_an_Berta:=f(k_AB,m);
A_an_Tobi:=f(k_AT,m);
Berta erhält antonOffen und A_an_Berta,
Tobi erhält antonOffen und A_an_Tobi.
Entschlüsselungsphase
Berta berechnet:
k_AB:=powermod(antonOffen,tb,p); vonAntonB:=f_inv(k_AB,A_an_Berta);
Tobi berechnet:
k_AT:=powermod(antonOffen,tt,p);vonAntonT:=f_inv(k_AT,A_an_Tobi);
bool(vonAntonB=vonAntonT)
Beide haben also dasselbe erhalten.
Die Message-Zahl muss noch in Klartext verwandelt werden.
klar:=zooToTx(vonAntonB);
[49, 83, 82, 88, 69, 75, 4, 77, 81, 4, 49, 73, 72, 80, 73, 93]
[77, 111, 110, 116, 97, 103, 32, 105, 109, 32, 77, 101, 100, 108, 101, 121]
##############################################
Signatur mit dem ElGamal-Verfahren= DSS
= Digital Signature Standard
Anton will seine Nachricht signieren, bekannt sind g, p und sein öffentlicher Schlüssel tAnton:
Er wählt ra teilerfremd zu p-1
repeat
r:= random((p div 2)..p-1): ra:=r():
until gcd(p-1,ra)=1 end_repeat:ra;
kra:=powermod(g,ra,p);
matrix([igcdex(p-1,ra)]);
ra_inv:=op(igcdex(p-1,ra),3); // letztes Element euklid. Algorithmus
if (ra_inv<0) then ra_inv:=ra_inv+p-1: end_if:ra_inv; //Korrektur bei negativem ra_inv
//m:=77;
sa:=modp((m-ta*kra)*ra_inv,p-1);
Anton sendet m und die digitale Unterschrift zu m also [m, sa,kra];
Prüfung der Unterschrift
Tobi will prüfen, ob die Nachricht wirklich von Anton kommt.
Er berechnet
test1:=powermod(g,m,p);
test2:=modp(powermod(tAnton,kra,p)*powermod(kra,sa,p),p);
if (test1=test2) then print("Das hat Anton geschrieben: m=".m)
else print("Vorsicht, das ist nicht von Anton Original!") end_if;
"Das hat Anton geschrieben: m=49838288697504778104497372807393"
Die von Anton gesendete Signatur ist mit der Nachrricht "verwoben". Sie läßt sich für keine andere
Nachricht verwenden. Wenn die Nachricht verändert wurde, gelingt der Test ebenfalls nicht.
m:=m+7;
test1:=powermod(g,m,p);
test2:=modp(powermod(tAnton,kra,p)*powermod(kra,sa,p),p);
if (test1=test2) then print("Das hat Anton geschrieben: m=".m)
else print("Vorsicht, das ist nicht von Anton Original!") end_if;
"Vorsicht, das ist nicht von Anton Original!"