Modular Inverses in Python 3 (PicoCTF 2022 #03 basic-mod2)

Help the channel grow with a Like, Comment, & Subscribe!
Check out the affiliates below for more free or discounted learning!

📧Contact me! (I may be very slow to respond or completely unable to)

[georgebitounis]

For the sake of learning, RSA uses the multiplicative inverse in order to generate the private key (For extra info you know what to do ). John you are a beast, Greetings from Greece !

[hackvlix]

The "Extended Euclidean Algorithm" is well worth a look, since it is one of the most fundamental algorithms in computer algebra and cryptography, and in particular it is the key to understanding and computing modular inverses.

### Since the gcd of two numbers a, b (suppose a>=b, otherwise swap) is computed step-by-step via the ordinary Euclidean algorithm,

a_0 = a, b_0 = b

for n = 0, 1, 2... until r_n = 0:
(1) q_n = a_n div b_n
(2) r_n = a_n - b_n * q_n (which implies 0 <= r_n < b_n <= a_n)
(3) a_(n+1) = b_n
(4) b_(n+1) = r_n

This ends when r_n = 0 (meaning b_n properly divides a_n without remainder),
and then b_n = gcd(a, b) holds
(you can verify this by inductively checking the loop invariant that every divisor of a, b also divides r_n, so in particular once the loop terminates, every divisor of a, b divides b_n = r_(n-1)).

### An important consequence of this is that we can write gcd(a, b) as a linear combination of a and b,
gcd(a, b) = s*a + t*b.

To see this, observe that you can write the steps (1)-(4) in the ordinary Euclidean algorithm as a matrix equation,

x_(n+1) = Q_n * x_n

where

Q_n = [ 0 1 ]
[ 1 --q_n ]

and x_0 = [ a ]
[ b ]

Then, after the last step, we have

x_(n+1) = [ gcd(a, b) ] = Q_n * x_n = Q_n Q_(n-1) * ... * Q_0 * [ a ]
[ 0 ] [ b ]

The numbers s, t with gcd(a, b) = s*a + t*b are now just the two entries in the first row of the matrix

Q = Q_n * Q_(n-1) * ... * Q_0,

which can be computed step-by-step while iterating through the Euclidean algorithm.
This constitutes the Extended Euclidean Algorithm.

### Now, what does this have to do with modular inverses?

Fact: A number x has an inverse modulo m precisely if gcd(x, m) = 1.

If gcd(x, m) = 1, the Extended Euclidean Algorithm above allows us to compute two numbers s, t such that

s*x + t*m = 1.

But if we take this modulo m, then t*m becomes 0, so that

s*x = 1 (mod m).

This means s is the modular inverse of x modulo m, and we can compute it using the Extended Euclidean Algorithm, as shown above.

[marcusvsilverio]

Hello from Brazil, thank you so much. Awesome video!

[Feathla]

Thanks John. It’s good to see you’re still learning too. I think it’s helps us feel that it’s ok to always be learning and you can’t know everything. Thanks again for the time and energy you put in.

[sorav]

Another golden video from John. He makes looks thing easy and interesting. But the video doesn't show thousand of hours spent learning these skills, approach and thought process.

[twistedrisers]

I like what you did here. I just imported mod_invers from smypy then used modulasinv = mod_inverse(number, 41)

[chriskaprys]

John Hammond's channel: come for the infosec lessons & news; stay for the word "shenanigans". 😊

[dennismuller]

since 41 is a prime number, you could use Fermats little theorem to compute the modular inverse of x by calling pow(x, 39, 41), which works for older python versions as well.

[gymtraining]

Nice Nazaré Tedesco Brazil dude!! hahahahahaha love u John...

[asbestinuS]

Yeah...I love the math...I do the math all the time, I'm the best at math. Thank you for your video, kind sir.

[sayChristIsKing]

Dude it such a relief to see that I was not alone crossing my eyes when reading about reverse modulo. I though I was ultra dumb to not getting it right away

[ramlayassine]

def modular_inverse(a, c):
for n in range(c):
if (a * n) % c == 1:
return n
return -1

[poprivest]

Best example of understanding a modular inverse i could find (that actually was my google answer, i just did the search a bit differently lol):
The multiplicative inverse of “a modulo m” exists if and only if a and m are relatively prime (i.e., if gcd(a, m) = 1).
Input: a = 3, m = 11     Output("pow(3, -1, 11)"): 4        Since (4*3) mod 11 = 1, 4 is modulo inverse of 3(under 11)
And not to be confused with 1/3 mod11 (or "(3 to the power of -1) mod11"). I think python did it this way just to simplify it for us. I tried to get a calculator to reproduce the result, to no avail.

[mossdem]

Thank you so much for doing this. I massively over thought this challenge as simple and straightforward as it turned out to be! I got so frustrated when I couldn't do it but I knew trusty Hohn Jammond would save the day!

[rajeshsagar]

hoping that you solve all that pico ctf challenges...thanq

[magnoelmagnifico]

When you encrypt a file, does the algorithm apply to the binary directly or other values are used (as shown in the challenge)?

[Unstable_dio]

seeing the Extended Euclidean Algorithm brought back trauma from a few months ago when i first learned about rsa encryption and tried to compute my own keys, it still not working btw

[sergeant]

It boggles my mind how hackers of yesteryear plied their trade without internet search engines. The accumulative knowledge they had to seek (and remember) wasn't a mouse click away!

[davsyl]

I just want to know how to execute the code and the result shows on the right side of the screen and not the bottom!

[TheDenysabner]

What about @John Hammond using Nazare Tedesco's meme. lol