Extended Euclidean Algorithm

I’ve started a cryp­tog­ra­phy class at DePaul and dur­ing the first lec­ture we first reviewed the Extended Euclid­ean Algo­rithm.  It pro­vides a method, using only a table, pen­cil, and paper, to eas­ily find not just the gcd of two inte­gers, but the s and t val­ues as well. Aca­d­e­m­i­cally: Let a and b be two inte­gers, at least one of which is nonzero, and let d = gcd(a,b). There exists some val­ues s,t such that d = sa + tb.

When it was cov­ered in class, the table didn’t have the k col­umn as it does in Wikipedia so I didn’t quite grasp it the first time through.  When I’m unsure of some­thing I attempt to write imple­ment it in code. So below is my quick Python imple­men­ta­tion of the Extended Euclid­ean Algo­rithm for find­ing d, s, and t, given a and b in d = gcd(a,b) = sa + tb . Not quite sure what we’ll use it for, but I have no doubt that I will learn that soon enough!

# Uses the Extended Euclid­ean Algo­rithm (Table Method) to find the gcd, s, and t
def gcd(a,b,dis­play=False):
    # Setup the first two rows of the table
    s2 = 1; t2 = 0; d2 = a; k2 = 1;
    s1 = 0; t1 = 1; d1 = b; k1 = d2/d1;
   
    # Com­pute Rows until the GCD is found
    while True:
        # Cal­cu­late a Table Row
        s0 = s2 — k1*s1
        t0 = t2 — k1*t1
        d0 = d2 — k1*d1
        k0 = d1/d0
       
        # Shift all the Row Vari­ables
        d2 = d1;    d1 = d0;
        s2 = s1;    s1 = s0;
        t2 = t1;    t1 = t0;
        k2 = k1;    k1 = k0;
       
        # We’ve found the GCD
        if d2%d1 == 0:
            break
           
    # Print the Results
    if dis­play == True:
        print “gcd(a,b)=sa+tb: gcd(“+‘a‘+”,”+‘b‘+”)=(“+‘s1‘+”)(“+‘a‘+”)+(“+‘t1‘+”)(“+‘b‘+”) = “+‘d1‘
   
    # Return the results
    return d1, s1, t1

New Section, New Start?

I’ve recently cre­ated a new sec­tion above called “Aca­d­e­mics” that I plan on using for host­ing var­i­ous projects/papers from my grad­u­ate stud­ies. I posted two papers from my last two terms and will hope­fully have more to post this term.

I’ve also upgraded the site to Word­Press 2.7 so I’ll have to check­out the new fea­tures and see what’s what. So far so good.

Bomb #1

My cur­rent class assign­ment con­sists of reverse engi­neer­ing a piece of code writ­ten by the pro­fes­sor. Basi­cally the pro­gram reads in one line from STDIN at a time and checks to see if it’s the right phrase. If it is, that bomb is defused and it con­tin­ues to the next one. If the phrase is incor­rect that the bomb blows up and I’ll have to try again.

Below is my method­ol­ogy for Phase 1.

** Note that as a stu­dent we were given access to the source code of the “shell” pro­gram that calls the other func­tions that actu­ally do the com­pare. So I know that the func­tions are called phase_1() through phase_6(). The func­tion names could also be guessed by using obj­dump –t bomb.exe and look­ing at the func­tion names.

** Also, solutions.txt con­tains a sin­gle line with con­tent: test­ing

$ gdb bomb
(gdb) b phase_1
(gdb) dis­play /i $pc
(gdb) r solutions.txt

That runs the pro­gram until the break­point is hit. Once it’s hit I run disas to dis­play the assem­bly of the cur­rent func­tion. I notice that there is a call to strings_not_equal and fig­ure that the two val­ues pushed onto %esp are likely the argu­ments, and based on the func­tions name, are likely strings. I then use dis­play /a $eax to take a look at the address con­tained in %eax. Finally, I use x /s 0x405040 and x /s 0x404140 to look at the strings located at those addresses. One is the string I passed in, and the other is the win­ing string. I change my solutions.txt file to have the new string in it and test it to val­i­date. It works! Bomb 1 defused!

Bomb - Phase 1