I’ve started a cryptography class at DePaul and during the first lecture we first reviewed the Extended Euclidean Algorithm. It provides a method, using only a table, pencil, and paper, to easily find not just the gcd of two integers, but the s and t values as well. Academically: Let a and b be two integers, at least one of which is nonzero, and let d = gcd(a,b). There exists some values s,t such that d = sa + tb.
When it was covered in class, the table didn’t have the k column as it does in Wikipedia so I didn’t quite grasp it the first time through. When I’m unsure of something I attempt to write implement it in code. So below is my quick Python implementation of the Extended Euclidean Algorithm for finding 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 Euclidean Algorithm (Table Method) to find the gcd, s, and t
# 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;
# Compute Rows until the GCD is found
# Calculate a Table Row
s0 = s2 — k1*s1
t0 = t2 — k1*t1
d0 = d2 — k1*d1
k0 = d1/d0
# Shift all the Row Variables
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:
# Print the Results
if display == True:
print “gcd(a,b)=sa+tb: gcd(“+‘a‘+”,”+‘b‘+”)=(“+‘s1‘+”)(“+‘a‘+”)+(“+‘t1‘+”)(“+‘b‘+”) = “+‘d1‘
# Return the results
return d1, s1, t1
I’ve recently created a new section above called “Academics” that I plan on using for hosting various projects/papers from my graduate studies. I posted two papers from my last two terms and will hopefully have more to post this term.
I’ve also upgraded the site to WordPress 2.7 so I’ll have to checkout the new features and see what’s what. So far so good.
My current class assignment consists of reverse engineering a piece of code written by the professor. Basically the program 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 continues to the next one. If the phrase is incorrect that the bomb blows up and I’ll have to try again.
Below is my methodology for Phase 1.
** Note that as a student we were given access to the source code of the “shell” program that calls the other functions that actually do the compare. So I know that the functions are called phase_1() through phase_6(). The function names could also be guessed by using objdump –t bomb.exe and looking at the function names.
** Also, solutions.txt contains a single line with content: testing
$ gdb bomb
(gdb) b phase_1
(gdb) display /i $pc
(gdb) r solutions.txt
That runs the program until the breakpoint is hit. Once it’s hit I run disas to display the assembly of the current function. I notice that there is a call to strings_not_equal and figure that the two values pushed onto %esp are likely the arguments, and based on the functions name, are likely strings. I then use display /a $eax to take a look at the address contained 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 wining string. I change my solutions.txt file to have the new string in it and test it to validate. It works! Bomb 1 defused!