# Write-up Crypto UTCTF 2023
## Provably Insecure

- Đề cho 1 file server.py
`server.py`

from cryptography.hazmat.primitives.asymmetric import rsa
from secrets import randbits

if __name__ == '__main__':
    alice = rsa.generate_private_key(public_exponent=65537, key_size=2048)
    print("Alice's pk: ", alice.public_key().public_numbers().n, alice.public_key().public_numbers().e)
    m = randbits(256)
    s = pow(m, alice.private_numbers().d, alice.public_key().public_numbers().n)
    print(m, s)
    print("Your key: ")
    n_prime = abs(int(input("n': ")))
    e_prime = abs(int(input("e': ")))
    d_prime = abs(int(input("d': ")))

    # Checks
    x = randbits(256)
    assert alice.public_key().public_numbers().n != n_prime or alice.public_key().public_numbers().e != e_prime
    assert n_prime > s
    assert pow(x, e_prime * d_prime, n_prime) == x
    assert e_prime > 1
    assert pow(s, e_prime, n_prime) == m

    with open('flag.txt', 'r') as f:
        print("Flag: " + f.read().strip())

- Dựa vào source ta biết rằng mỗi phiên kết nối, server sẽ:

- Tạo key RSA $\text{(2048-bit n, e = 65537, d)}$
- Tạo một số random $\text{256-bit m}$
- Ký số $m$ đó bằng cặp key vừa tạo: $s \equiv m^{d} \pmod n$ và gửi cho chúng ta cặp $(m,s)$
- Tạo một số random $\text{256-bit x}$ khác
- Yêu cầu chúng ta tìm key RSA $(n',e',d')$ với $e'>1,n'\neq n,n'>s,e'\neq e$ sao cho:

- $x^{e'd'}\equiv x \pmod{n'}$
- $s^{e'}\equiv m \pmod{n'}$

- Lưu ý: $n'$ không nhất thiết phải là tích của 2 số nguyên tố $p,q$, có thể là $p$
- Do $\text{n.bit_length()=2048} \implies \text{s.bit_length()<2048}$, ta sẽ tạo ra số nguyên tố $\text{2048-bit p-smooth}$ để bỏ vào thuật toán Polig-Hellman(discrete log)

`gen_smooth_prime.sage`

def B_smooth(total_size, small_factors_size, big_factor_size):
    """ Just picking at random should be enough, there is a very small probability
    we will pick the same factors twice
    """
    smooth_prime = 2
    factors = [2]
    # large B-sized prime
    large_prime = random_prime(1<<(big_factor_size + 1), lbound=1<<(big_factor_size-3))
    factors.append(large_prime)
    smooth_prime *= large_prime
    # all the other small primes
    number_small_factors = (total_size - big_factor_size) // small_factors_size
    i = 0
    for i in range(number_small_factors - 1):
        small_prime = random_prime(1<<(small_factors_size + 1), lbound=1<<(small_factors_size-3))
        factors.append(small_prime)
        smooth_prime *= small_prime
    # we try to find the last factor so that the total number is a prime
    # (it should be faster than starting from scratch every time)
    prime_test = 0
    while not is_prime(prime_test):    
        last_prime = random_prime(1<<(small_factors_size + 1), lbound=1<<(small_factors_size-3))
        prime_test = smooth_prime * last_prime + 1

    factors.append(last_prime)
    smooth_prime = smooth_prime * last_prime + 1

    return smooth_prime, factors
def generate_pq(nbits):    
    p, factors = B_smooth(nbits+32, 15, 40)
    while True:
        if is_prime(p):            
            if 2**nbits < p:
                break
        p, factors = B_smooth(nbits+32, 15, 40)    

    q, factors = B_smooth(nbits+32, 15, 40)    
    while True:
        if is_prime(q):
            if 2**nbits < q:
                if gcd(p-1, q-1) == 2:
                    break
        q, factors = B_smooth(nbits+32, 15, 40)    
    return p,q  

a = generate_pq(2048)
print(a)

- Có được p-smooth rồi ta sẽ tìm ra được $\text{d' = discrete_log(p,s,m)}$ và kiểm tra $gcd(d',p-1)=1$ để có thể tìm được $e'$

- Ta sẽ gửi $(p,e',d')$ lên server và có flag

`sol.py`

from sympy.ntheory.residue_ntheory import discrete_log
from math import gcd
from pwn import *
context.log_level = 'debug'
p = 62143219619681917935136906151929253060951584255243199041636592977128737612765879211852580842443751889475293085575739308499043552527775924407768488072352361355356207305538727324510456921711248898153730337251113711043008330828602641385335360964498324586613712757151309916606721874486110551032007609570622431231166045980262507993234482716169704396228707671836774118010047676485506754490326300709395846944972467897527001865144040919990845270870839846582929305864636064876937300156034551928552824253432978686903375415481206108740585420665182847507515656746566694978845572597313612052932233290404317565105392882920239821327
while True:
    io = remote('puffer.utctf.live', 52548)
    io.recvuntil(b"\n")
    m = int(io.recvuntil(b' ',drop=True).decode())
    s = int(io.recvuntil(b'\n',drop=True).decode())
    dp = discrete_log(p,s,m)
    if gcd(dp,p-1) == 1:
        break

ep = pow(dp,-1,p-1)
io.sendlineafter(b"n': ", str(p).encode())
io.sendlineafter(b"e': ", str(ep).encode())
io.sendlineafter(b"d': ", str(dp).encode())
io.interactive()

- Flag: utflag{hey_wait_signature_forgery_is_illegal}