Ergebnis 1 bis 4 von 4
  1. #1
    Swaggy Dude Avatar von mbeezy
    Registriert seit
    29.03.2007
    Beiträge
    2.112

    Standard Erweiterter Euklidischer Algorithmus (EEA)

    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:
    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ß
    Geändert von mbeezy (12.02.2010 um 03:53 Uhr)
    #ichwurdezurückgehaltendamals #sheesh #burrr #scurrr #nohomo #turnup #eaglegang #byrdcall #glogangornogang #duschkabinenposse #codeincobracrew

  2. #2
    Wicked Wonderland Avatar von aL1ien
    Registriert seit
    08.07.2007
    Beiträge
    434

    Standard

    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 ;/.
    Tu peut t'le mettre dans l'cul.

  3. #3
    Neuling
    Registriert seit
    02.03.2010
    Beiträge
    1

    Standard

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

    ITS oder AI? ;-)

  4. #4
    Swaggy Dude Avatar von mbeezy
    Registriert seit
    29.03.2007
    Beiträge
    2.112

    Standard

    Zitat Zitat von Darkscene Beitrag anzeigen
    ITS oder AI? ;-)
    IT-YES! Ehm, ITS. :o

    P.S. Java suckz0rt.
    #ichwurdezurückgehaltendamals #sheesh #burrr #scurrr #nohomo #turnup #eaglegang #byrdcall #glogangornogang #duschkabinenposse #codeincobracrew

Stichworte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •