# Wanna Champion 2024
> Nhan_laptop |
> --

> Trong lúc rảnh rỗi thì mình có nhìn lại giải của UIT tổ chức năm vừa rồi và chọn những chall mình thấy hay để làm lại.

## RAS - tvdat2004

chall:

from Crypto.Util.number import *
# from secret import flag
import random
flag = b'crypto{????????????????????????????}'
# print(len(flag))
class RAS(object):
    def __init__(self, p, q):
        self.p = p
        self.q = q
        self.n = (p**3 - p)*(q**3 - q)
        """

        p ( p ** 2 - 1 ) q ( q ** 2 - 1 )
        p ( p - 1 ) ( p + 1  ) q ( q - 1 ) q ( q + 1 )

        """
    def generate_e(self):
        e = random.randint(self.p * self.q, (self.p * self.q)**2)
        return e
        
    def encrypt(self, pt):
        e = self.generate_e()
        assert pt < self.n
        c = pow(pt, e, self.n)
        return e, c

flag1, flag2, flag3 = bytes_to_long(flag[:len(flag)//3]), bytes_to_long(flag[len(flag)//3:2*len(flag)//3]), bytes_to_long(flag[2*len(flag)//3:])

# shuffle it
m1 = flag1*flag2*flag3
m2 = flag1 + flag2 + flag3 
m3 = flag1 * flag2 + flag2 * flag3 + flag3 * flag1 

nbit = 256 

menu = '''
Welcome to my RAS
1. Send primes
2. Get encrypted flag
'''

b = False
while True:
    try:
        choose = input(menu)
        if choose == '1':
            primes = input(f"Send me two {nbit}-bit strong primes, separated by comma: ")
            try:
                p, q = map(int, primes.strip().split(','))
            except: 
                raise Exception("Invalid input")  

            if (isPrime(p) and isPrime(q) and
                p != q and 
                p.bit_length() == q.bit_length() == nbit):
                b = True
                ras = RAS(p, q)
            else:
                print("Primes not strong enough!")
        elif choose == '2':
            if b:
                print(ras.encrypt(m1))
                print(ras.encrypt(m2))
                print(ras.encrypt(m3))
            else:
                raise Exception("You must send strong primes first!!!")
        else:
            raise Exception("Invalid choice!!!")
            
    except Exception as e:
        print(f"Error: {str(e)}")
        break

Tóm tắt là:
- Public key bài này là `n = (p ** 3 - p ) * ( q **3 -q )`
- Và cho mình không hạn lần để truy vấn

solve:

Và chú ý là mình kiểm soát được `p,q` nên chiến lược là mình sẽ lựa các p,q phù hợp rồi tìm `m_p, m_q` phù hợp với `phi_p, phi_q`.

### Part 1:

ps1 = []
ms1 = []
ps2 = []
ms2 = []
ps3 = []
ms3 = []
def decrypt(x,p):
    e,c = x 
    if GCD(e ,p-1)!=1:
        return None
    phi = p-1 
    d = inverse(e,phi)
    return pow(c,d,p)

while 1  : 
    p = getPrime(512)
    q = getPrime(512)

    resp = oracle(p,q)
    m1 = decrypt(resp[0],p)
    m2 = decrypt(resp[1],p)
    m3 = decrypt(resp[2],p)
    
    if m1 != None:
        ms1.append(m1)
        ps1.append(p)

    if m2 != None:
        ms2.append(m2)
        ps2.append(p)

    if m3 != None:
        ms3.append(m3)
        ps3.append(p)

    m1 = decrypt(resp[0],q)
    m2 = decrypt(resp[1],q)
    m3 = decrypt(resp[2],q)
    
    if m1 != None:
        ms1.append(m1)
        ps1.append(q)

    if m2 != None:
        ms2.append(m2)
        ps2.append(q)

    if m3 != None:
        ms3.append(m3)
        ps3.append(q)

    print(len(ms3))
    if len(ms3)> 80 and len(ms1) > 80 and len(ms2)> 80:
        break

m1 = flag1*flag2*flag3
m2 = flag1 + flag2 + flag3 
m3 = flag1 * flag2 + flag2 * flag3 + flag3 * flag1 

assert m1 == crt(ms1,ps1)
assert m2 == crt(ms2,ps2)
assert m3 == crt(ms3,ps3)

Mình tìm được 3 giá trị chuẩn - trong code này mình đang cho các bạn biết thuật này đúng - cần truy vấn một lượng lớn mẫu `message_prime`,.

### Part 2:

m = [m1,m2,m3]

flag1,flag2,flag3 = PolynomialRing(ZZ,'x',3,order = 'lex').gens()

m1 = flag1*flag2*flag3 - m[0]
m2 = flag1 + flag2 + flag3 -m[1]
m3 = flag1 * flag2 + flag2 * flag3 + flag3 * flag1 -m[2]

sol = ideal([m1,m2,m3]).groebner_basis()

và biểu thức cuối của sol là :

 x2^3 - 93081550437588504762415453164324824815512890448494127125481445*x2^2 + 105666576836626803617552219352359893258738438672438347484052785812492589634912853507595855810570916410282826314295714241368*x2 - 30113957810887199660425965901262837077808596976276277044244604618090976099024732025862764623637567079600132510545058461867624877630019579652029887142843302953305408592327770843664464

Và mình chỉ cần tìm trên này:

f = PolynomialRing(ZZ,'x2')

fi = f(sol[-1]).roots(multiplicities = False)
for i in fi[::-1]:
    print(long_to_bytes(int(i)).decode(),end='')
# W1{wi3rd_ch41!En9e_n33d_4_WlErD_s0O!luti0n_6f339749663eeb3508c3b00c15872e41}
print()