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:
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}
```
