PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Erweiterter Euklidischer Algorithmus (EEA)



mbeezy
12.02.2010, 03:45
Hi,

im Zuge meiner Klausurvorbereitung möchte ich euch hier den Erweiterten Euklidischen Algorithmus (EEA) kurz vorstellen. Bitte habt Gnade mit mir, ich bin auch nur ein Boon. Solltet ihr einen Fehler finden, einfach sofort bescheid geben. ;)


##################################################


Thema: Erweiterter Euklidischer Algorithmus
Autor: soulstoned
Published: Free-Hack.com
Quelle(n):
- Christof Paar, Jan Pelzl: Understanding Cryptography: A Textbook for Students and Practitioners (http://www.amazon.de/Understanding-Cryptography-Textbook-Students-Practitioners/dp/3642041000), Seiten 160ff
- Einführung in die Kryptografie und Datensicherheit, Christof Paar, WS0809, Vorlesung 10: Euklidischer Algorithmus, Ruhr-Universität Bochum (http://www.rub.de)
- http://everything2.com/title/Extended+Euclidean+algorithm


##################################################



Der EEA berechnet für die gegeben Werte http://www.imagebanana.com/img/ixz898d1/1.gif den größten gemeinsamen Teiler:
http://www.imagebanana.com/img/lz493415/2.gif

Wozu braucht man das alles? Man braucht den EEA zum Beispiel, wenn man in der Kryptografie bei einer Affinen Chiffre die modulare Inverse http://www.imagebanana.com/img/b5wnfrd7/CodeCogsEqn.gif berechnen muss.
Die Grundidee sagt aus, dass man in jeder Iteration des normalen Euklidischen Algorithmus http://www.imagebanana.com/img/z04z9i3c/CodeCogsEqn2.gif berechnet:
http://www.imagebanana.com/img/7vy355g8/CodeCogsEqn3.gif mit
http://www.imagebanana.com/img/4jxjs9c/CodeCogsEqn4.gif letzte Iteration
http://www.imagebanana.com/img/tvm7mxo/CodeCogsEqn5.gif
http://www.imagebanana.com/img/n0ueh3au/CodeCogsEqn6.gif


Es folgt:

Euklidischer Algorithmus | Erweiterter Euklidischer Algorithmus
http://www.imagebanana.com/img/yqr4hnys/CodeCogsEqn7.gif | http://www.imagebanana.com/img/hjmyxq9/CodeCogsEqn8.gif wobei http://www.imagebanana.com/img/606fafc9/CodeCogsEqn9.gif und http://www.imagebanana.com/img/u0z7agzt/CodeCogsEqn10.gif
http://www.imagebanana.com/img/8w6057x1/CodeCogsEqn11.gif | http://www.imagebanana.com/img/jnnwzj85/CodeCogsEqn13.gif
http://www.imagebanana.com/img/0oixt8jn/CodeCogsEqn14.gif | http://www.imagebanana.com/img/fe7al9or/CodeCogsEqn15.gif

und so weiter, bis gilt:

http://www.imagebanana.com/img/n7cyclu/CodeCogsEqn16.gif | http://www.imagebanana.com/img/39vwr5q0/CodeCogsEqn17.gif
http://www.imagebanana.com/img/815timcs/CodeCogsEqn18.gif
wobei die http://www.imagebanana.com/img/r4bly1hi/CodeCogsEqn19.gif anzeigt, dass der Algorithmus fertig ist und aus dem Schritt zuvor http://www.imagebanana.com/img/kvkrbmz/CodeCogsEqn20.gif entspricht.


Für die Praxis gibt es folgende Iterationsformeln:
http://www.imagebanana.com/img/0zy9t5v/CodeCogsEqn21.gif als Startwert und
http://www.imagebanana.com/img/ugrir1sl/CodeCogsEqn23.gif
http://www.imagebanana.com/img/g42nawlz/CodeCogsEqn24.gif

Für die Informatiker unter euch kann folgender Pseudo-Code genommen werden:

http://www.imagebanana.com/img/6vrxysxv/1.png
Oder als Java-Source-Code:

public int[] extEuclid(int a, int b) {
if (b == 0) {
int result[] = {1, 0, a};
return result;
}

int u = a;
int v = b;
int x1, x2, x3, y1, y2, y3;

if (u < v) {
x1 = 0; x2 = 1; x3 = v;
y1 = 1; y2 = 0; y3 = u;
} else {
x1 = 1; x2 = 0; x3 = u;
y1 = 0; y2 = 1; y3 = v;
}

while (y3 > 1) {
int q = (int) (x3/y3);
int t1 = x1 - q*y1;
int t2 = x2 - q*y2;
int t3 = x3 - q*y3;

x1 = y1; x2 = y2; x3 = y3;
y1 = t1; y2 = t2; y3 = t3;
}
if (y3 == 0) {
int result[] = {x1, x2, x3};
return result;
} else {
int result[] = {y1, y2, y3};
return result;
}
}



Anwendung findet das ganze zum Beispiel in RSA:
gegeben: http://www.imagebanana.com/img/rbogxkyv/CodeCogsEqn26.gif mit http://www.imagebanana.com/img/m4awig67/CodeCogsEqn27.gif
gesucht: http://www.imagebanana.com/img/fiecczf8/CodeCogsEqn28.gif

http://www.imagebanana.com/img/g4fmzw14/CodeCogsEqn29.gif
http://www.imagebanana.com/img/7tfuuzo/CodeCogsEqn30.gif
http://www.imagebanana.com/img/znx8xr38/CodeCogsEqn31.gif
http://www.imagebanana.com/img/xffy1dd6/CodeCogsEqn32.gif
http://www.imagebanana.com/img/6obbrkh/CodeCogsEqn33.gif

Also: Der Wert http://www.imagebanana.com/img/b1l9q050/CodeCogsEqn34.gif des EEA ist die Inverse von http://www.imagebanana.com/img/30vy7z5/CodeCogsEqn35.gif



Eine Beispielrechnung:
gegeben: http://www.imagebanana.com/img/t5vwfsmt/CodeCogsEqn36.gif

Euklidischer Algorithmus | Erweiterter Euklidischer Algorithmus
http://www.imagebanana.com/img/6ndx3vnx/CodeCogsEqn37.gif | http://www.imagebanana.com/img/nbeh4ke0/CodeCogsEqn38.gif
http://www.imagebanana.com/img/5g0uvx8c/CodeCogsEqn39.gif | http://www.imagebanana.com/img/tjdr74zf/CodeCogsEqn40.gif
http://www.imagebanana.com/img/a71aod9t/CodeCogsEqn41.gif | http://www.imagebanana.com/img/tkfi2jkv/CodeCogsEqn42.gif
http://www.imagebanana.com/img/o51sx1q9/CodeCogsEqn48.gif | http://www.imagebanana.com/img/vmj3u1/CodeCogsEqn44.gif
http://www.imagebanana.com/img/dof8r7l0/CodeCogsEqn45.gif | http://www.imagebanana.com/img/mzfz52xs/CodeCogsEqn52.gif
http://www.imagebanana.com/img/ed6vyez9/CodeCogsEqn47.gif



Das wars dann soweit, hoffe es war einigermaßen verständlich. ;)


Gruß

aL1ien
12.02.2010, 07:08
Oh der...ich habe mal aus Spass einen RSA-Knacker geschrieben. Natürlich ist dies fast unmöglich im praktischen einsatz zu gebrauchen, da die Primzahlteilung zu lange geht. Es förderte aber immens das Verständis dahinter. (Siehe: http://free-hack.com/showthread.php?t=42305 )

Hatte dort einige probleme mit dem EEA ;/.

Darkscene
16.03.2010, 20:52
:D Die Welt ist klein, da trifft man doch tatsächlich auf einen Kommilitonen....

ITS oder AI? ;-)

mbeezy
19.03.2010, 15:30
ITS oder AI? ;-)
IT-YES! Ehm, ITS. :o

P.S. Java suckz0rt.