Euclid's Algorithm

-
Introduction

I was recently going through the cryptohack challenges when I came across the Greatest Common Divisor (GCD) challenge, this challenge is a novice level challenge where you are expected to code up a function to compute the GCD of two numbers, a link to Euclid's Algorithm was provided as a hint to solve the problem. Normally, as expected I followed the link just to brush up on my understanding, considering that it's something I already knew. Soon after I proceeded to code up the function and then realized I was missing a great deal of what was supposed to be intuitive, that is, I did not properly understand the algorithm as I thought, hence this post.
So what is Euclid's Algorithm? It's an algorithm attributed to 300 B.C. Greek mathematician Euclid, for efficiently computing the greatest common divisor of two numbers, this algorithm has a wide array of uses especially in the field of cryptography. The GCD of any two numbers, for example, 5 and 12, is the largest number that divides both numbers without any remainder. So what Euclid did is come up with a set of steps to solves this problem for any two given numbers.

Naive Euclid's Algorithm

The set of steps proposed by Euclid is as follows:
  1. Given a set of two numbers, e.g 5 and 12
  2. Subtract the smaller number i.e 5 from the bigger number i.e 12
  3. Assign the result of step two (12 - 5 = 7) as the bigger number, overwriting the previous value (i.e 12 will now be replaced by 7, leaving us with 5 and 7 as the new set of numbers)
  4. Repeat the process all over again from step one with the new  set of numbers (i.e 5 and 7) until you reach a point where both numbers are equal, when that happens, the number is the GCD of the two initial numbers
The figure below shows this process:

Fig. 1 - Computing the GCD of 12 and 5 which is 1

From Fig. 1 we can see that the GCD of 12 and 5 is 1 i.e is the only number that divides both 12 and 5 without any remainder. Using the above steps you can find the GCD of any two numbers.

The Intuition

Why does this algorithm work? first, remember that every Natural number (i.e {1, 2, 3...}) is divisible by 1, and that's because every natural number from 1 is just a successive increment of 1 as can be seen in Fig. 2

Fig. 2 - Successive increment of two numbers

Also, we know that every number is divisible by itself but not divisible by any number greater than itself i.e 5 is divisible by 5 but not 6 or 7 e.t.c, therefore we can say that the Greatest Divisor (GD) of any given single natural number is itself i.e the GD of 5 is 5, the GD of 7 is 7. So far, we've established the following:
  1. Every natural number is divisible by 1
  2. A divisor of any natural number must be less than or equal to the natural number
  3. The Greatest Divisor of any single Natural number must be itself
Now, given two numbers, if both numbers are equal then they must be the same number i.e if a = 7 and b = 7, then a == b, and from rule 3 above, the greatest divisor of 7 is 7, the easy part. But if both numbers are not equal e.g a = 12 and b = 5, now since the number we seek is a common divisor between the two numbers, then we know from rule 2 that the divisor must be less than or equal to the smaller number, in this case, 5, therefore it is safe to subtract the smaller number from the bigger number since we already know the GCD cannot be found in the larger part of that bigger number, after the subtraction, we are now left with a new set of numbers and we repeat the above process eventually we get to a point where the numbers are equal which in the worst case is 1 and when that happens we use rule 3 to conclude that the number is the GCD of the two given numbers.

Code Implementation

Naive Euclid's Algorithm


Efficient Euclid's Algorithm

But why do we refer to the above algorithm as naive? Well, because if given two numbers where one is significantly greater than the other e.g a = 724 and b = 8032523, then the subtraction will take a long time to converge to the smaller number. So a more efficient version was developed and it works by replacing the greater of the two numbers by the remainder when the greater number is divided by the lesser number and when the remainder of the numbers becomes zero the algorithm terminate and we return the other number

Efficient Euclid's Algorithm

Now, I think I fairly understand Euclid's Algorithm. In the next part of this post, we will dive into the Extended Euclidean Algorithm and probably look at its usefulness in practical cryptography.





Comments

Post a Comment

Popular posts from this blog

Before You Dive In...

-
I have always wanted to write, partly to improve my writing skills but also to document my research in reverse code engineering, software exploitation and computer programming in general, my current goal is to have at least a post a week, but since am just starting out I do not know how feasible that will be considering school and my need for quality over quantity. In the coming weeks, I will post on varying topics from software reverse engineering to exploitation and basically anything that interest me. My primary aim is just to cement my knowledge in my fields of interest by giving back to the community as I learn and hopefully along the way help someone trying to learn. A quick disclaimer though is that I am no professional at either writing or the subject on which I will be writing (at least for now),  am just trying to navigate through the vast ocean of knowledge hoping to pick one or two things along the way, so corrections, constructive criticism, and even unconstructive ones
Read more

OverTheWire: Bandit Lab

-
Image
Bismillahirrahmanirrahim (In the name of Allah the most gracious, the most merciful) So recently I and @electro decided to solve wargames and CTFs in the spirit of honing the skills and because we are preparing for something really important (another post for another day). We decided to start with the labs at overthewire  and the first on the list was Bandit Lab. Bandit Lab was a fun experience, mostly easy, except for one or two tricky levels, level 26 and level 33 in particular. This Labs weren't so difficult but required a bit of thinking outside the box, hence why am documenting them. NB : this writeup doesn't include our thought process while solving the levels Level 26 Level Description When we attempt to login to this level using the private key obtained from the previous level we get automatically logged out and since the level goal already informed us that we are dealing with a different shell, we need to figure out what it is and how to break out of it. Above is the
Read more

SSRF Notes: PortSwigger Labs Continued

-
Image
  Lab 3: SSRF with blacklist-based input filter Task :  This lab has a stock check feature which fetches data from an internal system.  To solve the lab, change the stock check URL to access the admin interface at http://localhost/admin and delete the user carlos.  The developer has deployed two weak anti-SSRF defenses that you will need to bypass. This Lab is just like the previous ones except that we need to bypass blacklist filters. This is what a normal request to the stock check feature looks like: Passing http://localhost/admin to the stockApi parameter does not work this time. we get this response: That's the filter blocking us. It turned out 127.0.0.1, localhost, admin are all blacklisted so cannot be used. So after trying a couple things the following was able to bypass the filter: We get the following response: So to complete the Lab we just proceed to delete carlos. And that's it Lab solved.
Read more