Rating:

# NahamCon CTF 2020 Writeup

I found that this CTF had a few particularly interesting challenges, so I felt like a small writeup was due.

## Twinning


These numbers wore the same shirt! LOL, #TWINNING!

Connect with:
nc jh2i.com 50013


Netcatting to the server gives us this:


$nc jh2i.com 50013 Generating public and private key... Public Key in the format (e,n) is: (65537,7136206991423) The Encrypted PIN is 4647953841890 What is the PIN?  Looks like RSA but with wayyy too small numbers, but they also have another weakness... This challenge will definitely stick with me, as it is the first time ever that a small formula I came up with a while ago actually became useful: ![alt text](https://raw.githubusercontent.com/williamsolem/NahamCon-CTF-2020-Writeup/master/Twinning/formula.png "Reverse Conjugate") The essence of this formula is that it's able to factorize the factor of two primes p and q when p and q are consecutive (twin primes) or at least very close. The way I came up with this formula was when trying to find some way to apply the conjugate rule backwards in order to factorize n. I was somewhat successful, however it does diminish in accuracy quite gravely the futher away p and q are from eachother. Do note that m does NOT refer to the variable m in RSA, it is merely an intermediete variable to make the math a little more elegant. I guess you could say it's a very fancy way of doing the square root of n, and is pretty much useless in any practical contexts. (Though if any math geeks know a way to improve it to have accuracy across a wider range of primes, please let me know) Anyhow, we can write this formula as a python script: python def factor(n): sqrt=n**0.5 m=(int(sqrt+1)**2-n)**0.5 return [int(int(sqrt)-m+1),int(int(sqrt)+m+1)] while True: n = int(input("Enter n:")) print(factor(n))  Using this program we can factor n:  Enter n:7136206991423 [2671367, 2671369]  We can multiply p and q together to check, and sure enough, 2671367 * 2671369 = 7136206991423. Now let's get to decrypting. Here's a python script to do that: python def egcd(a, b): if a == 0: return (b, 0, 1) g, y, x = egcd(b%a,a) return (g, x - (b//a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('No modular inverse') return x%m p = 2671367 q = 2671369 ct = 4647953841890 e = 65537 phi = (p - 1) * (q - 1) d = modinv(e, phi) m = pow(ct, d, p * q) print(m)  Running the script gives us that the PIN is 4565, and sure enough, entering the PIN gives us the flag: $ nc jh2i.com 50013
Generating public and private key...
Public Key in the format (e,n) is: (65537,7136206991423)
The Encrypted PIN is 4647953841890
What is the PIN?
4565
Good job you won!
flag{thats_the_twinning_pin_to_win}


Original writeup (https://github.com/williamsolem/NahamCon-CTF-2020-Writeup/).