I participated corCTF with H0j3n last weekened, it was a nice CTF. Here are some of the writeups

# Challenges

## Attachments

Look at the python source code:

from Crypto.Util.number import bytes_to_long, isPrime
from secrets import randbelow

p = bytes_to_long(open("flag.txt", "rb").read())
assert isPrime(p)

a = randbelow(p)
b = randbelow(p)

def f(s):
return (a * s + b) % p

print("a = ", a)
print("b = ", b)
print("f(31337) = ", f(31337))
print("f(f(31337)) = ", f(f(31337)))


As you can see, we are given $$a$$, $$b$$, $$f(31337)$$ and $$f(f(31337))$$

And we need to find $$p$$ which is the flag!

## Modular arithmetic

If you familar with PRNG, you know this is using LCG https://en.wikipedia.org/wiki/Linear_congruential_generator

We need some math in order to find $$p$$

According to modular arithmetic, we know that $$f(s) \equiv as+b \mod p$$, therefore $$f(s) = kp+as+b$$

So to find $$kp$$, we just need to calculate $$f(s)-(as+b)$$

We got value of $$f(31337)$$ and $$f(f(31337))$$, we just need to calculate the $$kp$$ of both value then calculate the GCD (Greatest Common Divisor) of both $$kp$$, then we found $$p$$ !!

$k_1p=f(31337)-a(31337)+b$ $k_2p=f(f(31337))-a(f(31337))+b$ $p=gcd(k_1p,k_2p)$

Calculate the flag using python script:

import gmpy2
from Crypto.Util.number import long_to_bytes
a =  7904681699700731398014734140051852539595806699214201704996640156917030632322659247608208994194840235514587046537148300460058962186080655943804500265088604049870276334033409850015651340974377752209566343260236095126079946537115705967909011471361527517536608234561184232228641232031445095605905800675590040729
b =  16276123569406561065481657801212560821090379741833362117064628294630146690975007397274564762071994252430611109538448562330994891595998956302505598671868738461167036849263008183930906881997588494441620076078667417828837239330797541019054284027314592321358909551790371565447129285494856611848340083448507929914
x1 =  52926479498929750044944450970022719277159248911867759992013481774911823190312079157541825423250020665153531167070545276398175787563829542933394906173782217836783565154742242903537987641141610732290449825336292689379131350316072955262065808081711030055841841406454441280215520187695501682433223390854051207100
x2 =  65547980822717919074991147621216627925232640728803041128894527143789172030203362875900831296779973655308791371486165705460914922484808659375299900737148358509883361622225046840011907835671004704947767016613458301891561318029714351016012481309583866288472491239769813776978841785764693181622804797533665463949

k1 = x1-(a*31337+b)
k2 = x2-(a*x1+b)

flag = gmpy2.gcd(k1,k2)
print(long_to_bytes(flag))
# b'corctf{1n_m4th3m4t1c5,_th3_3ucl1d14n_4lg0r1thm_1s_4n_3ff1c13nt_m3th0d_f0r_c0mput1ng_th3_GCD_0f_tw0_1nt3g3rs} <- this is flag adm'


Thats the flag! Simple math to calculate the flag

## Flag

corctf{1n_m4th3m4t1c5,_th3_3ucl1d14n_4lg0r1thm_1s_4n_3ff1c13nt_m3th0d_f0r_c0mput1ng_th3_GCD_0f_tw0_1nt3g3rs}


# luckyguess

Look at the python source code:

#!/usr/local/bin/python
from random import getrandbits

p = 2**521 - 1
a = getrandbits(521)
b = getrandbits(521)
print("a =", a)
print("b =", b)

try:
x = int(input("enter your starting point: "))
y = int(input("alright, what's your guess? "))
except:
print("?")
exit(-1)

r = getrandbits(20)
for _ in range(r):
x = (x * a + b) % p

if x == y:
print("wow, you are truly psychic! here, have a flag:", open("flag.txt").read())
else:
print("sorry, you are not a true psychic... better luck next time")


Seems like another LCG again? Now we’re given $$a$$, $$b$$ and $$p$$ and we can input the seed value $$x$$ then guess correctly the final output to get the flag

## Math again

$$r$$ is 20bits long which is nearly impossible to guess, therefore it must have a value that $$x=f(x)$$, so no matter what is $$r$$ we can guess correctly the output

Searching for lcg bad seed found this slides stated the bad seed value is:

$-(a-1)^{-1} \cdot b \mod p$

We just need to solve the equation:

$x=ax+b$ $x-ax=b$ $(1-a)x=b$ $x=\frac{b}{1-a}$

So if we input $$\frac{b}{1-a}$$ as $$x$$ we will get the same value! To calculate that we need to calculate the modular inverse of $$1-a$$ then times $$b$$ (Because of modular arithmetic)

My solution code using python:

from pwn import *
from Crypto.Util.number import *
p = remote("be.ax",31800)
p.recvuntil("a = ")
a = int(p.recvuntil('\n')[:-1])
p.recvuntil("b = ")
b = int(p.recvuntil('\n')[:-1])

P = 2**521 - 1
x = inverse(1-a,P) * b
print(f"x={x}")
print(f"y={(x * a + b) % P}")
p.interactive()
# x=8157802442862108603218032583174746602223107830105214400988760572848074964652282496633630863529974747007475186870875400736430339942641753414979724185385288945897013204349648892711500237449393089807499954866150814334827186976415763962970310451225314299120689307545333928967256604082498152596192970917628246788271253
# y=2878357714346482341059412386794527457065632409440137333123405194141516437425787096997746957221822320071627316690087461212467873121606718509524987871762938567
# [*] Switching to interactive mode
# enter your starting point: $8157802442862108603218032583174746602223107830105214400988760572848074964652282496633630863529974747007475186870875400736430339942641753414979724185385288945897013204349648892711500237449393089807499954866150814334827186976415763962970310451225314299120689307545333928967256604082498152596192970917628246788271253 # alright, what's your guess?$ 2878357714346482341059412386794527457065632409440137333123405194141516437425787096997746957221822320071627316690087461212467873121606718509524987871762938567
# wow, you are truly psychic! here, have a flag: corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}


## Flag

corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}


# hidE

Look at the source code, seems like a RSA question:

#!/usr/local/bin/python
import random
import time
import math
import binascii
from Crypto.Util.number import *

p, q = getPrime(512), getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)

random.seed(int(time.time()))

def encrypt(msg):
e = random.randint(1, n)
while math.gcd(e, phi) != 1:
e = random.randint(1, n)
pt = bytes_to_long(msg)
ct = pow(pt, e, n)
return binascii.hexlify(long_to_bytes(ct)).decode()

def main():
print('Secure Encryption Service')
print('Your modulus is:', n)
while True:
print('Options')
print('-------')
print('(1) Encrypt flag')
print('(2) Encrypt message')
print('(3) Quit')
x = input('Choose an option: ')
if x not in '123':
print('Unrecognized option.')
exit()
elif x == '1':
print('Here is your encrypted flag:', encrypt(flag))
elif x == '2':
msg = input('Enter your message in hex: ')
print('Here is your encrypted message:', encrypt(binascii.unhexlify(msg)))
elif x == '3':
print('Bye')
exit()

if __name__ == '__main__':
main()


As you can see, we can get encrypted flag and encrypted message but we only know $$n$$

How do we get the flag??

## Find $$e$$

Look at the code carefully, you will see the random seed is using current time

random.seed(int(time.time()))


So we can easily guess the seed and $$e$$ with random.randint()

Example python code:

# Generate 10 possible value of e
random.seed(start_time-i)
possible_e = []
for _ in range(10):
possible_e.append(random.randint(1, n))


## Find $$m$$

Now we got the $$e$$ but how we get the flag?? We can use the Common Modulus Attack!

We can generate 2 different ciphertext that encrypt with the same modulus, so it is applicable to this attack!

My solution code in python:

import random
import time
import gmpy2
from pwn import *
from Crypto.Util.number import *
from itertools import combinations

p = remote("be.ax" ,31124)
# Record start time
start_time = int(time.time())

# Get modulus
p.recvuntil("is: ")
n = int(p.recvuntil('\n')[:-1])
p.sendlineafter(": ","1")

# Get two different ciphertext of flag
p.recvuntil("encrypted flag: ")
c1 = int(p.recvuntil('\n')[:-1],16)
p.sendlineafter(": ","1")

p.recvuntil("encrypted flag: ")
c2 = int(p.recvuntil('\n')[:-1],16)

# Code get from https://infosecwriteups.com/rsa-attacks-common-modulus-7bdb34f331a5
def attack(c1, c2, e1, e2, N):
s1 = inverse(e1,e2)
s2 = int((gmpy2.gcd(e1,e2) - e1 * s1) // e2)
temp = inverse(c2, N)
m1 = pow(c1,s1,N)
m2 = pow(temp,-s2,N)
return long_to_bytes((m1 * m2) % N)

# Server time will delay abit so brute force the time
for i in range(5):
random.seed(start_time-i)
possible_e = []
# Generate 10 possible e
for _ in range(10):
possible_e.append(random.randint(1, n))

# Generate the combination of 2 possible e
comb = combinations(possible_e, 2)
for e1,e2 in list(comb):
if gmpy2.gcd(e1,e2):
m = attack(c1, c2, e1, e2, n)
# If flag format in message found the flag!
if b"corctf" in m:
print(m)
# b'corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}\n'


## Flag

corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}