DiffieHellmann-Verfahren, Schlüsselvereinbarung
Kryptographie mit MuPAD,
Prof. Dr. Dörte Haftendorn, Mathematik mit MuPAD 4.02, (Buch-Version)
(ex. in 2.5 Okt 99 , vom Nov.02 und in 3.11 Sept. 05) Juni 07 (Dieses ist noch nicht optimal erläutert)
http://haftendorn.uni-lueneburg.de www.mathematik-verstehen.de
####################################################################
---------------------------------------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------------------------------------------------------------------------------------------------------
Anton will mit Berta einen gemeinsamen Schlüssel vereinbaren.
Er bereitet als Grundlage p und g vor.
saat:=random(10000..99999):
p:=numlib::prevprime(floor(sqrt(saat()*10^600)));
//Exponent auch 150
saat:=random(10000..99999):
p:=numlib::prevprime(floor(sqrt(saat()*10^600)));
//Exponent auch 150
g:=numlib::prevprime(floor(sqrt(saat()*10^150)));271224998847820073135738623156171637606953120506159511566380116462087182321927746858315952427086405306358802150733393346183507811451548522523688895522279711916868494191992548150024033374293460705016424340328571004520197904436495142023416254956803247075571981571877654612113372885322748643898592366911511
g:=numlib::prevprime(floor(sqrt(saat()*10^150)));
//p:=29:g:=23:
Er teilt dieses Berta mit, jeder darf das wissen.
Anton wählt sich eine beliebige Zahl a und berechnet:
r:= random(2..p-2): a:=r();
anton:=powermod(g,a,p);
Berta wählt sich eine beliebige Zahl b und berechnet:
r:= random(2..p-2): b:=r(); berta:=powermod(g,b,p);
/*a:=16: b:=19: // gutes Beispiel
anton:=powermod(g,a,p);
berta:=powermod(g,b,p);*/
Anton und Berta senden sich gegenseitig öffentlich ihre Ergebnisse.
Anton berechnet:
ka:=powermod(berta,a,p);
Berta berechnet:
kb:=powermod(anton,b,p);
Das ist der gemeinsame Schlüssel.
//kb:=kb-1://Störung einbauen
if (ka=kb) then k:=ka;
print("Der gemeinsame geheime Schlüssel für Anton und Berta ist") ;
print("k = ".k) ;
else print("Vorsicht, Protokoll ist gestört") end_if;
"Der gemeinsame geheime Schlüssel für Anton und Berta ist"
"k = 11700550534702836579727487724305589908856127937348940944503438257093707946\
1908"
Diesen Vergleich kann beim Ablauf niemand machen. Die Manipulation wird dadurch gemerkt, dass man
später nicht entschlüsseln kann.
Anwendungsphase
Berta will Anton einen Text senden, den nur Anton lesen kann.
mText:="Montag im Medley":
---------------------------------------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(mText);
[77, 111, 110, 116, 97, 103, 32, 105, 109, 32, 77, 101, 100, 108, 101, 121]
delete f,kk,x: f:=(kk,x)->(kk*x): f(kk,x);
c:=f(kb,m);
Sie teilt Anton den Algorithmus von f(k,c) und c mit. f muss invertierbar sein.
f ist hier einfach, in der Praxis "verrührt" f die Nachricht heftig.
Anton will das lesen
Den gemeinsamen Schlüssel k weiß Anton schon, k bleibt geheim.
delete f_inv,kk,x: f_inv:=(kk,x)->(x/kk): f_inv(kk,x);
m_vonBerta:=f_inv(kb,c);
Der Ascii-Text muss noch in Klartext verwandelt werden.
klar:=zooToTx(m_vonBerta);
[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]
Anton will Berta antworten:
mAntwort:="ja, um 8":
m:=txToZoo(mAntwort);
[106, 97, 44, 32, 117, 109, 32, 56]
c:=f(ka,m);
Berta liest
m_vonAnton:=f_inv(kb,c); klar:=zooToTx(m_vonAnton);
[78, 69, 16, 4, 89, 81, 4, 28]
[106, 97, 44, 32, 117, 109, 32, 56]
Anton und Berta können nun beliebig oft mit dem einmal berechneten
Schlüssel k Nachrichten austauschen.
Angriff auf Diffie-Hellman
g;p;anton;berta
Das kann Mister X abfangen
matrix([[i,powermod(g,i,p),anton,bool(powermod(g,i,p)=anton)] $ i=1..30])
versuch:=powermod(berta,16,p):
zooToTx(f_inv(versuch,c))
[11, 49, 13, 27, 42, 66, 24, 66, 36]
[39, 77, 41, 55, 70, 94, 52, 94, 64]
c;
f_inv(kkk,x)
f_inv(i,c) $ i=1..4;
zooToTx(f_inv(i,c)) $ i=1..4
[9, 20, 73, 50, 99, 76, 71, 38, 38, 73, 81, 53, 59, 52, 30, 97, 34, 61, 49, 40,
41, 28, 37, 68, 76, 98, 7, 53, 84, 90, 62, 55, 69, 14, 48, 63, 0, 4, 89, 92,
9, 58, 71, 67, 17, 66, 24]
[37, 48, 101, 78, 127, 104, 99, 66, 66, 101, 109, 81, 87, 80, 58, 125, 62, 89,
77, 68, 69, 56, 65, 96, 104, 126, 35, 81, 112, 118, 90, 83, 97, 42, 76, 91,
28, 32, 117, 120, 37, 86, 99, 95, 45, 94, 52]
[4, 60, 36, 75, 49, 88, 35, 69, 19, 36, 90, 76, 79, 76, 15, 48, 67, 30, 74, 70,
20, 64, 18, 84, 38, 49, 3, 76, 92, 45, 31, 27, 84, 57, 24, 31, 50, 2, 44,
96, 4, 79, 35, 83, 58, 83, 12]
[32, 88, 64, 103, 77, 116, 63, 97, 47, 64, 118, 104, 107, 104, 43, 76, 95, 58,
102, 98, 48, 92, 46, 112, 66, 77, 31, 104, 120, 73, 59, 55, 112, 85, 52, 59,
78, 30, 72, 124, 32, 107, 63, 111, 86, 111, 40]
[3, 6, 91, 16, 99, 92, 23, 79, 46, 24, 60, 51, 19, 84, 10, 32, 44, 87, 16, 46,
80, 42, 79, 22, 92, 32, 69, 17, 94, 96, 87, 51, 89, 71, 49, 54, 33, 34, 96,
64, 3, 19, 57, 22, 39, 22, 8]
[31, 34, 119, 44, 127, 120, 51, 107, 74, 52, 88, 79, 47, 112, 38, 60, 72, 115,
44, 74, 108, 70, 107, 50, 120, 60, 97, 45, 122, 124, 115, 79, 117, 99, 77,
82, 61, 62, 124, 92, 31, 47, 85, 50, 67, 50, 36]
[2, 30, 18, 37, 74, 94, 17, 84, 59, 68, 45, 38, 39, 88, 7, 74, 33, 65, 37, 35,
10, 32, 9, 42, 19, 24, 51, 88, 46, 22, 65, 63, 92, 28, 62, 15, 75, 1, 22,
48, 2, 39, 67, 91, 79, 41, 56]
[30, 58, 46, 65, 102, 122, 45, 112, 87, 96, 73, 66, 67, 116, 35, 102, 61, 93,
65, 63, 38, 60, 37, 70, 47, 52, 79, 116, 74, 50, 93, 91, 120, 56, 90, 43,
103, 29, 50, 76, 30, 67, 95, 119, 107, 69, 84]