Erweiterter Euklidischer Algorithmus (EEA)

[mbeezy]

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, Seiten 160ff
- Einführung in die Kryptografie und Datensicherheit, Christof Paar, WS0809, Vorlesung 10: Euklidischer Algorithmus, Ruhr-Universität Bochum
- http://everything2.com/title/Extende...dean+algorithm

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



Der EEA berechnet für die gegeben Werte den größten gemeinsamen Teiler:


Wozu braucht man das alles? Man braucht den EEA zum Beispiel, wenn man in der Kryptografie bei einer Affinen Chiffre die modulare Inverse berechnen muss.
Die Grundidee sagt aus, dass man in jeder Iteration des normalen Euklidischen Algorithmus berechnet:
mit
letzte Iteration




Es folgt:

Euklidischer Algorithmus | Erweiterter Euklidischer Algorithmus
| wobei und
|
|

und so weiter, bis gilt:

|

wobei die anzeigt, dass der Algorithmus fertig ist und aus dem Schritt zuvor entspricht.


Für die Praxis gibt es folgende Iterationsformeln:
als Startwert und



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

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: mit
gesucht:







Also: Der Wert des EEA ist die Inverse von



Eine Beispielrechnung:
gegeben:

Euklidischer Algorithmus | Erweiterter Euklidischer Algorithmus
|
|
|
|
|




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


Gruß

[aL1ien]

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]

Die Welt ist klein, da trifft man doch tatsächlich auf einen Kommilitonen....

ITS oder AI? ;-)

[mbeezy]

ITS oder AI? ;-)

IT-YES! Ehm, ITS. :o

P.S. Java suckz0rt.