# RSA.zip
Source:

from Crypto.Util.number import *
from secret import FLAG

FLAG = bytes_to_long(FLAG)

if __name__ == "__main__":
    p = getPrime(512)
    q = getPrime(512)
    N = p*q
    e = 65537
    d = inverse(e, (p-1)*(q-1))
    c = pow(FLAG, e, N)
    print(f"N = {N}")
    print(f"c = {c}")
    while True:
        try:
            c = int(input(">>> "))
            bit = pow(c,d,N) % 2
            print(bit)
        except:
            break

## Phân tích:
Chall trên sử dụng mã hóa RSA thông thường, với N được tạo từ 2 số nguyên tố 512bit được get ngẫu nhiên, sinh khóa và mã hóa rất bình thường. Điểm đặc biệt ở đây là challenge cung cấp một function gợi ý:

    while True:
        try:
            c = int(input(">>> "))
            bit = pow(c,d,N) % 2
            print(bit)
        except:
            break

Hàm này sử dụng khóa bí mật để giải mã c, rồi đem kết quả đi mod 2, rồi return bit nhận được (0 hoặc 1). Với thuật toán trả về 1 bit thì ta có thể sử dụng Least Significant Bit Attack ([LSB Attack](https://crypto.stackexchange.com/questions/11053/rsa-least-significant-bit-oracle-attack)).
Cụ thể thì, LSB Attack áp dụng với mã hóa RSA thông thường, với các thành phần p,q,N,e,d, khi mà hệ thống chịu cho ta biết rằng với ciphertext mà ta nhập vào thì bãn rõ cho ra sẽ là số chẵn hay số lẻ. Nếu attacker chặn được bản mã C được mã hóa từ hệ thống, tức là nhận được bản mã:
$$
C = P^e \mod N
$$
Tại đây, attacker lấy giá trị C có được nhân với $2^e \mod N$, ta sẽ được giá trị ciphertext của $2P$ (Bởi $C.(2^e \mod N) = (2P)^e \mod N$). Khi này, gửi giá trị đó lên sever, máy chủ sẽ tính giá trị $2P \mod N$, ta sẽ có được 2 trường hợp mà từ đó, có thể truy dần về giá trị của P:
* Nếu sever trả về rằng giá trị chẵn (trả về bit 0): Khi này thì ta sẽ có $2P < N$ (vì khi $2P<N$ thì $2P \mod N = 2P$ với N luôn là lẻ), tức $P < N/2$.
* Nếu sever trả về rằng giá trị lẻ (trả về bit 1): Khi này thì ta sẽ có $2P > N$ (vì khi $2P>N$ thì khi này $2P=k.N + r$ với N luôn là lẻ, r cũng sẽ lẻ bởi số nào nhân với số lẻ cũng sẽ tạo số lẻ), tức $P > N/2$.

Lợi dụng khả năng so sánh với $N/2$, cùng với việc là thường thì P sẽ luôn nhỏ hơn giá trị N, ta tạo hai giá trị `high`= N và `low` = 0 => ban đầu thì `high + low = N`.Mục tiêu của ta là thu hẹp dần hai giá trị này về sát nhất giá trị của $P$.
* Khi sever trả về bit chẵn => $P < N/2$ => giá trị trần `high` được cập nhật thành $N/2$
* Khi sever trả về bit lẻ => $P > N/2$ => giá trị đáy `low` được cập nhật thành $N/2$.
Mỗi lần cập nhật thì phạm vi giá trị của P lại giảm một nửa, sẽ tìm ra giá trị chính xác của P.
Code khai thác như sau:
## Code:

from pwn import *
from Crypto.Util.number import *
io = process(['python3' , 'chall.py'])


io.recvuntil(b"N = ")
N = int(io.recvline().strip())
io.recvuntil(b"c = ")
c = int(io.recvline().strip())

low, high = 0,N
e = 65537

for i in range(1024):  
    c = (c * pow(2, e, N)) % N  

    io.recvuntil(b">>> ")
    io.sendline(str(c).encode())

    bit = int(io.recvline().strip())

    mid = low + (high - low) // 2 #Nhằm tránh cho giá trị cuối cùng là số thập phân nên sử dụng phép //
    if bit == 0:
        high = mid
    else:
        low = mid

    print(f"Step {i+1}: M ≈ {high}")

FLAG = long_to_bytes(int(high))
print(f"Recovered FLAG: {FLAG}")


io.close()

>Sau nhiều lần thử nghiệm, nhận ra rằng do phép chia lấy phần nguyên // 2 mà có sai số xảy ra. Tuy nhiên, với các flag thường gặp thì sai số không đáng để, chỉ xảy ra sai lệch khi decode kí tự cuối (thường là kí tự "}"). Vì thế mà sai số trên không thực sự quá ảnh hưởng đối với các flag thường được sử dụng trong các giải CTF với format `name{put_your_flag_here}`.

# RSA_101

Source:

from Crypto.Util.number import *
from random import *
from secret import flag_1,flag_2,flag_3,flag_4,flag_5,flag_6,flag_7
import json

class Outer_tower(): #0
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.p=getPrime(1024)
        self.e=65537
    def encrypt_flag(self):
        return json.dumps({"encrypted_flag":pow(self.flag,self.e,self.p)})
    def encrypt(self,msg):
        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.p)})
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'sign':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

class Flour_of_test(): #1
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.e=3
    def encrypt_flag(self):
        p=getPrime(512)
        q=getPrime(512)
        n=p*q
        return json.dumps({"encrypted_flag":pow(self.flag,self.e,n),"N":n,"e":3})
    def encrypt(self,msg):
        p=getPrime(512)
        q=getPrime(512)
        n=p*q
        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,n),"N":n})
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'sign':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

class The_Workshop_Battle(): #2
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=getPrime(512)
        self.phi=(self.p-1)*(self.q-1)

        self.n=self.p*self.q
        self.e=65537
        self.d=inverse(self.e,self.phi)
    def sign(self,msg):
        if b"admin" not in bytes.fromhex(msg):
            return json.dumps({"signature":hex(pow(int(msg,16),self.d,self.n)),"N":self.n,"e":self.e})
        else:
            return json.dumps({"signature":pow(31066278741462331364812614761,self.d,self.n),"N":self.n,"e":self.e})
    def verify(self,signature):
        signature=pow(int(signature,16),self.e,self.n)
        if long_to_bytes(signature)==b"admin":
            return long_to_bytes(self.flag)
        else:
            return "get out Regular !"
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'sign':
                msg = your_input['msg']
                print(self.sign(msg))

            elif your_input['option']=="verify":

                sig=your_input["signature"]
                print(self.verify(sig))

            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

class Hell_train(): #3
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=self.getsmoothprime(512)
        self.n=self.p*self.q
        self.e=65537
        self.check=0
    def getsmoothprime(self,size):
        f=eval(open('primes.txt','r').read())
        shuffle(f)
        p=2
        i=0
        while True:
            p=p*f[i]
            if isPrime(p+1) and len(bin(p))>size:
                return p+1
            i+1
            if len(bin(p))>2*size:
                shuffle(f)
                p=2
    def encrypt_flag(self):
        if self.check==0:
            self.check=1
            return json.dumps({"encrypted_flag":pow(self.flag,self.e,self.n),"N":self.n,"e":self.e})
    def encrypt(self,msg):
        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.n),"N":self.n,"e":self.e})

    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'encrypt':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

class FLOOR_OF_DEATH(): #4
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=(self.getsmoothprime(512)-1)
        self.n=self.p*self.q
        self.e=109480
    def getsmoothprime(self,size):
        f=eval(open('primes.txt','r').read())
        shuffle(f)
        p=2*23**2
        i=0
        while True:
            p=p*f[i]
            if isPrime(p+1) and len(bin(p))>size:
                return p+1
            i+=1
            if len(bin(p))>2*size:
                shuffle(f)
                p=2

    def encrypt_flag(self):
        return json.dumps({"encrypted_flag":pow(self.flag,self.e,self.n),"N":self.n,"e":self.e})
    def encrypt(self,msg):
        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.n),"N":self.n,"e":self.e})

    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'encrypt':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

class Mirror_World_1(): #5
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=getPrime(512)
        self.n=self.p*self.q
        self.e=3
        self.check=0
        
    def encrypt_flag(self):
        if self.check!=1:
            self.check+=1
            x=randint(0,self.n-1)
            y=randint(0,self.n-1)
            padded_flag=(x*self.flag+y)%self.n
            return json.dumps({"encrypted_flag":pow(self.flag,self.e,self.n),"N":self.n,"e":self.e,"X":x,"Y":y})
        else:
            return json.dumps({"ALERT":"You cant fool zahard 121 times regular"})
    def encrypt(self,msg):

        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.n),"N":self.n,"e":self.e})
    
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'sign':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

class Mirror_World_2(): #6
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=getPrime(512)
        self.n=self.p*self.q
        self.e=3
        self.check=0
        
    def encrypt_flag(self):
        if self.check!=1:
            self.check+=1
            x=randint(0,self.n-1)
            y=randint(0,self.n-1)
            padded_flag=(x*self.flag+y)%self.n
            return {"encrypted_flag":pow(padded_flag,self.e,self.n),"N":self.n,"e":self.e,"X":x,"Y":y}
        else:
            return json.dumps({"ALERT":"You cant fool zahard 2 times regular"})
    def encrypt(self,msg):

        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.n),"N":self.n,"e":self.e})
    
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'sign':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

if __name__ == "__main__":
    idx = input("Choose the challenge: ")
    try:
        match(int(idx)):
            case 0:
                The_irregular_test=Outer_tower(flag_1)
                The_irregular_test.start_floor_test()
            case 1:
                Rak_the_ragnarok=Flour_of_test(flag_2)
                Rak_the_ragnarok.start_floor_test()
            case 2:
                Fugitive=The_Workshop_Battle(flag_3)
                Fugitive.start_floor_test()
            case 3:
                Zahard=Hell_train(flag_4)
                Zahard.start_floor_test()
            case 4:
                Khun=FLOOR_OF_DEATH(flag_5)
                Khun.start_floor_test()
            case 5:
                Arlen_Grace_1=Mirror_World_1(flag_6)
                Arlen_Grace_1.start_floor_test()
            case 6:
                Arlen_Grace_2=Mirror_World_2(flag_7)
                Arlen_Grace_2.start_floor_test()
    except:
        quit()

Nhận thấy đây không chỉ là một challenge, đây là một chương trình với 7 challenges, mỗi challenges là một flag khác nhau với tên riêng:

if __name__ == "__main__":
    idx = input("Choose the challenge: ")
    try:
        match(int(idx)):
            case 0:
                The_irregular_test=Outer_tower(flag_1)
                The_irregular_test.start_floor_test()
            case 1:
                Rak_the_ragnarok=Flour_of_test(flag_2)
                Rak_the_ragnarok.start_floor_test()
            case 2:
                Fugitive=The_Workshop_Battle(flag_3)
                Fugitive.start_floor_test()
            case 3:
                Zahard=Hell_train(flag_4)
                Zahard.start_floor_test()
            case 4:
                Khun=FLOOR_OF_DEATH(flag_5)
                Khun.start_floor_test()
            case 5:
                Arlen_Grace_1=Mirror_World_1(flag_6)
                Arlen_Grace_1.start_floor_test()
            case 6:
                Arlen_Grace_2=Mirror_World_2(flag_7)
                Arlen_Grace_2.start_floor_test()
    except:
        quit()

Để thuật tiện thì mình sẽ tách lẻ từng chall một để tiện cho giải quyết.
## Chall0: Irregular Test(Outer Tower)

class Outer_tower(): #0
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.p=getPrime(1024)
        self.e=65537
    def encrypt_flag(self):
        return json.dumps({"encrypted_flag":pow(self.flag,self.e,self.p)})
    def encrypt(self,msg):
        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.p)})
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'sign':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

### Phân tích:
Sơ qua thì thấy chương trình mã hóa với giá trị `self.e = 65537`. Các hàm `encrypt_flag()` dùng mã hóa flag, `encrypt` mã hóa msg với độ dài 16bit khi option là 'sign'. Điều đặc biệt ở đây là ở hai hàm encrypt đều cùng sử dụng mod p.
Ta có phương trình:
\begin{align*}
ct = pt^e \mod p \\
\rightarrow ct - pt^e=k_1.p
\end{align*}
Từ phương trình trên, ta có thể khôi phục p bằng cách gửi đi 2 msg để nhận về 2 ct, và vì p là ước chung thì có thể tìm được p bằng GCD.
### Code:

from Crypto.Util.number import *
import json
import pwn
from math import gcd
conn = pwn.process(["python3","challenges.py"])

server_msg = conn.recv().decode()
if "Choose the challenge:" in server_msg:
    conn.sendline("0")

conn.sendline(json.dumps({"option": "get_flag"}))
response = json.loads(conn.recv().decode())
encrypted_flag = response["encrypted_flag"]

e = 65537
msgs = ["2", "3"] 
resp = []

for msg in msgs:
    msg_int = int(msg, 16)
    conn.sendline(json.dumps({"option": "sign", "msg": msg}))
    sign_response = json.loads(conn.recv().decode())
    resp.append(sign_response["encrypted_msg"])

A = 2**e - resp[0]
B = 3**e - resp[1]
p = gcd(A, B)


d = inverse(e, p-1)
decrypted_flag = pow(encrypted_flag, d, p)


print("Recovered Flag:", long_to_bytes(decrypted_flag).decode())

conn.close()

Flag: `Secruinets{u_M4D3_I7_insid4_7he_7ower_u_4r3_4_CHO53N_onE}`

## Chall1 (FLour of test):

class Flour_of_test(): #1
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.e=3
    def encrypt_flag(self):
        p=getPrime(512)
        q=getPrime(512)
        n=p*q
        return json.dumps({"encrypted_flag":pow(self.flag,self.e,n),"N":n,"e":3})
    def encrypt(self,msg):
        p=getPrime(512)
        q=getPrime(512)
        n=p*q
        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,n),"N":n})
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'sign':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

Chall này thì phức tạp hơn kha khá so với chall trước, nhưng lại thấy `e=3` cố định nên lóe lên tia sáng với Small Exponent Attack. Nhưng mà ở đây thì giá trị m lớn, nên ta dùng **Hastad’s Broadcast Attack**.
### Code:

from Crypto.Util.number import *
import json
import pwn
import gmpy2
from math import gcd
from sympy import integer_nthroot

def hastad_broadcast_attack(ciphertexts, n_val, e=3):
    N = 1
    for n in n_val:
        N *= n
    
    result = 0
    for c, n in zip(ciphertexts, n_val):
        Ni = N // n
        inv_Ni = gmpy2.invert(Ni, n)
        result += c * Ni * inv_Ni
    
    result = result % N
    plaintext, exact = integer_nthroot(result, e)
    if exact:
        return long_to_bytes(plaintext).decode()
    else:
        return "Hastad's Attack Failed"

conn = pwn.process(["python3","challenges.py"])
server_msg = conn.recv().decode()
if "Choose the challenge:" in server_msg:
    conn.sendline("1")

ciphertexts, n_val = [], []
e = 3
for _ in range(e): 
    conn.sendline(json.dumps({"option": "get_flag"}))
    response = json.loads(conn.recv().decode())
    ciphertexts.append(response["encrypted_flag"])
    n_val.append(response["N"])
    

recovered_flag = hastad_broadcast_attack(ciphertexts, n_val)
print("Recovered Flag:", recovered_flag)

conn.close()

Flag: `Securinets{F4CiNG_Ev4nkhell'S_Hell_Is_N07_ThAT_e4sy}`
## Chall2 (TheWorkshopBattle):

class The_Workshop_Battle(): #2
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=getPrime(512)
        self.phi=(self.p-1)*(self.q-1)

        self.n=self.p*self.q
        self.e=65537
        self.d=inverse(self.e,self.phi)
    def sign(self,msg):
        if b"admin" not in bytes.fromhex(msg):
            return json.dumps({"signature":hex(pow(int(msg,16),self.d,self.n)),"N":self.n,"e":self.e})
        else:
            return json.dumps({"signature":pow(31066278741462331364812614761,self.d,self.n),"N":self.n,"e":self.e})
    def verify(self,signature):
        signature=pow(int(signature,16),self.e,self.n)
        if long_to_bytes(signature)==b"admin":
            return long_to_bytes(self.flag)
        else:
            return "get out Regular !"
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'sign':
                msg = your_input['msg']
                print(self.sign(msg))

            elif your_input['option']=="verify":

                sig=your_input["signature"]
                print(self.verify(sig))

            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

### Phân tích:
Mã hóa RSA lần này có sử dụng thêm các hàm `sign` và `verify` để tạo và xác thực digisign. Đi sâu vào từng hàm, thì tại `sign` ta thấy rằng khi trong msg không có `b"admin"` thì mới thực sự tạo digisign cho `msg` nhập vào, nếu không thì sẽ thay `msg` thành `31066278741462331364812614761`. Sang hàm `verify` chỉ khi `b"admin"` có trong `signature`, flag mới được trả về.
Mục tiêu cần làm là tạo chữ kí hợp lệ cho `b"admin"`.
Đến đây thì mình chọn phương án [Chosen Message Attack](https://crypto.stackexchange.com/questions/35644/chosen-message-attack-rsa-signature). Với `m = bytes_to_long(pt)` (`pt` chính là b"admin"), ta sẽ phân tích ra 2 thừa số m1 và m2. Cách tấn công cụ thể như sau:
\begin{align*}
s_1 = m_1^d \mod N \\
s_2 = m_2^d \mod N \\
\rightarrow s = s_1.s_2 = (m_1.m_2)^d \mod N \\
\rightarrow s = m^d \mod N
\end{align*}
Gửi sig `s` có được, chắc chắn sever sẽ nhả flag.
### Code:

from json import dumps, loads
from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes

m1 = 2603647
m = bytes_to_long(b"admin") 
m2 = m // m1
def evenhex(n):
    h = format(n, 'x')
    return h if len(h) % 2 == 0 else "0" + h

def sign(msg_hex):
    req = dumps({"option": "sign", "msg": msg_hex})
    io.sendline(req)
    res = io.recvline().decode().strip()
    data = loads(res)
    return int(data["signature"], 16), data["N"], data["e"]


io = process(["python3", "challenges.py"])
print(io.recv().decode()) 
io.sendline(b'2')  

m1_hex = evenhex(m1)
m2_hex = evenhex(m2)


s1, N, e = sign(m1_hex)
s2, N2, e2 = sign(m2_hex)

assert N == N2 and e == e2, "Error: N or e"
s = (s1 * s2) % N


option = dumps({"option": "verify", "signature": hex(s)})
io.sendline(option)

flag = io.recvline().decode().strip()
print("Flag:", flag)

io.close()

Flag:`Securinets{u_9o7_ur_SE1f_THe_7horN_7HAt_caN_K1l1_a_GoD}`
## Chall3 (Helltrain):

class Hell_train(): #3
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=self.getsmoothprime(512)
        self.n=self.p*self.q
        self.e=65537
        self.check=0
    def getsmoothprime(self,size):
        f=eval(open('primes.txt','r').read())
        shuffle(f)
        p=2
        i=0
        while True:
            p=p*f[i]
            if isPrime(p+1) and len(bin(p))>size:
                return p+1
            i+1
            if len(bin(p))>2*size:
                shuffle(f)
                p=2
    def encrypt_flag(self):
        if self.check==0:
            self.check=1
            return json.dumps({"encrypted_flag":pow(self.flag,self.e,self.n),"N":self.n,"e":self.e})
    def encrypt(self,msg):
        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.n),"N":self.n,"e":self.e})

    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'encrypt':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

### Phân tích
Điểm đáng chú ý ở đây chính là hàm `getsmoothprime`. Hàm này tạo ra số nguyên tố p sao cho `p-1` là tích của nhiều số nguyên tố nhỏ hơn, ở đây là các số nguyên tố từ file `prime.txt`. Nhắc `p-1` thì mình nhớ về [Pollard's p-1 Algorithm](https://hackmd.io/@quanda/rJD-3qZLC).
Với giá trị e và n có được, mình sẽ dùng thuật toán trên để tìm được p và q, từ đó giải mã.
### Code:

from json import *
from pwn import *
from Crypto.Util.number import *
from gmpy2 import fac
from math import gcd
from sympy import true, isprime
import tqdm
def pollard(n, B=100000):
    a = 2
    for p in primes(B):
        pp = 1
        while pp*p <= B:
            pp *= p
        a = pow(a, pp, n)  
        g = gcd(a-1, n)
        if 1 < g < n:
            return g
    return None

io = process(["python3", "challenges.py"])
print(io.recv().decode()) 
io.sendline(b'3')  

io.sendline(dumps({"option": "get_flag"}))
response = loads(io.recv().decode())
ct = response["encrypted_flag"]
n = response["N"]
e = response["e"]
io.close()

p = pollard(n)
q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(ct, d, n)
print(long_to_bytes(m))

Flag: `Securinets{hI9H_w4y_t0_7HE_fl0or_oF_DE47h_ain7_that_Easy}`
## Chall4:

class FLOOR_OF_DEATH(): #4
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=(self.getsmoothprime(512)-1)
        self.n=self.p*self.q
        self.e=109480
    def getsmoothprime(self,size):
        f=eval(open('primes.txt','r').read())
        shuffle(f)
        p=2*23**2
        i=0
        while True:
            p=p*f[i]
            if isPrime(p+1) and len(bin(p))>size:
                return p+1
            i+=1
            if len(bin(p))>2*size:
                shuffle(f)
                p=2

    def encrypt_flag(self):
        return json.dumps({"encrypted_flag":pow(self.flag,self.e,self.n),"N":self.n,"e":self.e})
    def encrypt(self,msg):
        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.n),"N":self.n,"e":self.e})

    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'encrypt':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

Bài này cũng có hàm `getsmoothprime`, tuy nhiên đã có một chút sự đổi khác. Thay vì giá trị p khởi đầu `p=2`, lần này là một giá trị p khác lớn hơn rất nhiều với `p=2*32**2`.
## Chall5:

class Mirror_World_1(): #5
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=getPrime(512)
        self.n=self.p*self.q
        self.e=3
        self.check=0
        
    def encrypt_flag(self):
        if self.check!=1:
            self.check+=1
            x=randint(0,self.n-1)
            y=randint(0,self.n-1)
            padded_flag=(x*self.flag+y)%self.n
            return json.dumps({"encrypted_flag":pow(self.flag,self.e,self.n),"N":self.n,"e":self.e,"X":x,"Y":y})
        else:
            return json.dumps({"ALERT":"You cant fool zahard 121 times regular"})
    def encrypt(self,msg):

        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.n),"N":self.n,"e":self.e})
    
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'sign':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

### Phân tích:
Somehow bài này có thêm function padding ở trong hàm `encrypt_flag` sử dụng 2 giá trị x và y, tuy nhiên hàm lại chỉ trả về flag được mã hóa bằng RSA thông thường mà không có padding. Cùng với đó là bổ sung thêm giá trị `self.check` để đảm bảm mỗi lần kết nối chỉ request `encrypt_flag` 1 lần duy nhất. Tuy nhiên, vì e nhỏ, ta vẫn có thể áp dụng `Hastad Broadcast Attack`, lặp lại 3 lần kết nối đến sever và thu thập giá trị.
### Code:

from Crypto.Util.number import *
import json
import pwn
import gmpy2
from math import gcd
from sympy import integer_nthroot

def hastad_broadcast_attack(ciphertexts, n_val, e=3):
    N = 1
    for n in n_val:
        N *= n
    
    result = 0
    for c, n in zip(ciphertexts, n_val):
        Ni = N // n
        inv_Ni = gmpy2.invert(Ni, n)
        result += c * Ni * inv_Ni
    
    result = result % N
    plaintext, exact = integer_nthroot(result, e)
    if exact:
        return long_to_bytes(plaintext).decode()
    else:
        return "Hastad's Attack Failed"

ciphertexts, n_val = [], []
e = 3
for _ in range(e):
    conn = pwn.process(["python3","challenges.py"])
    server_msg = conn.recv().decode()
    if "Choose the challenge:" in server_msg:
        conn.sendline("5")
    conn.sendline(json.dumps({"option": "get_flag"}))
    response = json.loads(conn.recv().decode())
    ciphertexts.append(response["encrypted_flag"])
    n_val.append(response["N"])
    print(ciphertexts)
    print(n_val)
    conn.close()
a = hastad_broadcast_attack(ciphertexts, n_val)
print(a)

Flag: `Secruinets{u_D0dg3D_the_wrA7H_oF_zah4rD_5OM3how}`
## Chall6:

class Mirror_World_2(): #6
    def __init__(self,flag):
        self.flag=bytes_to_long(flag)
        self.q=getPrime(512)
        self.p=getPrime(512)
        self.n=self.p*self.q
        self.e=3
        self.check=0
        
    def encrypt_flag(self):
        if self.check!=1:
            self.check+=1
            x=randint(0,self.n-1)
            y=randint(0,self.n-1)
            padded_flag=(x*self.flag+y)%self.n
            return {"encrypted_flag":pow(padded_flag,self.e,self.n),"N":self.n,"e":self.e,"X":x,"Y":y}
        else:
            return json.dumps({"ALERT":"You cant fool zahard 2 times regular"})
    def encrypt(self,msg):

        return json.dumps({"encrypted_msg":pow(int(msg,16),self.e,self.n),"N":self.n,"e":self.e})
    
    def start_floor_test(self):
        while True:
            your_input=json.loads(input())
            if not 'option' in your_input:
                    return {"error": "U better choose something or die alone"}
            elif your_input['option'] == 'get_flag':
                print(self.encrypt_flag())

            elif your_input['option'] == 'sign':
                try :
                    msg = your_input['msg']
                    print(self.encrypt(msg))
                except:
                    pass
            elif your_input['option']=='return to tower':
                break
            else:
                return {"error": "Invalid option"}

### Phân tích:
Chall6 này chính là chall5 nhưng lần này thì mã hóa RSA đã sử dụng padding.