# PearlCTF
### Baby Message Out

#!/usr/bin/env python3
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from flag import flag
from math import log
import sys

n = pow(10, 5)
sys.setrecursionlimit(n)

def nextPrime(p):
    if isPrime(p):
        return p
    else:
        return nextPrime(p + 61)

p = getPrime(256)
q = nextPrime(nextPrime(17*p + 1) + 3)
r = nextPrime(29*p*q)
s = nextPrime(q*r + p)
t = nextPrime(r*s*q)

print(f"{p = }")
print(f"{q = }")
print(f"{r = }")
print(f"{s = }")
print(f"{t = }")
n = p*q*r*s*t
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f"c: {c}")
print(f"n: {n}")

c: 1838979268925267202615818395622122484893202706167722156383681963142079180161531237936585341507802530813847301831886857107840552940103096671213346624172927405178565892385733216702672851783423891229382579221604596673156151519463795808010572632138076246765227545034269340790242411584582692558549837221897037971538915332866933837117883228953143242965510280921618063635225603250391037969273250144174802927111408106890496901519737395485115788436384012937788617630381389196078818501905993385084557887716148781944416313908553565974546239241287340505018036547080504009483360838747251073440799502791555942879229132369697126614944991347408598924472158561247485575276852356316968119522601927483600978106155875300324966339458896992260918634629607740522754923275555209240690069838566642421234035117257380757518902549668151860260985363114235340791362277047923494577018035035653075155240898800910887230020812289524262582877697129108304758256250595391379019020972909027192107727799235384374670082518555887502478560056865020860127002
n: 485889862688353809145356849681869098056742135790325154633816315764783289109350404808839464043297429168130293002483316664607770068196944445394490388957147529192164743228508084885030734914365245916125607677185307000076761646830755541107131137865984020648243428286711853728051263128076845261298240617545417811431124904304446607845470628505361436115651109768237103000946120781642652665829238385087624612205525857191218811570122228639908283598707567056620352822139985271817003262919597858495812801663331842855143930997258260164422858382713240717739568744168349527025412634588705503126870149875268600539407786323924132037483972529603572727892740460450963315253482630345996561505957763886776070413535287129043703855880444326909520084249767518737040222995586717034060176093473694948961503759770499124924886087468497100053775745634680192678426965540847613838559522315570932873854027804486662281273550134766570419630624914801192395060568099367828616501877701994364906741451132770474154689411119296104818089636891131318495955929

Ta thấy rằng, có một hàm sinh số nguyên tố như sau:

def nextPrime(p):
    if isPrime(p):
        return p
    else:
        return nextPrime(p + 61)

Và có 5 số nguyên tố được sinh ra

p = getPrime(256)
q = nextPrime(nextPrime(17*p + 1) + 3)
r = nextPrime(29*p*q)
s = nextPrime(q*r + p)
t = nextPrime(r*s*q)

Ta thử chạy một code mới và thu được như sau (mình tự chạy với số p khác bài)

p =               (p)
q =        (3 + 17*p + 1037*k1)
r = (29*p*(3 + 17*p + 1037*k1) + 61*k2)
s = ((29*p*(3 + 17*p + 1037*k1) + 61*k2)*(3 + 17*p + 1037*k1) + p + 61*k3)
t = ((29*p*(3 + 17*p + 1037*k1) + 61*k2)*(3 + 17*p + 1037*k1)*((29*p*(3 + 17*p + 1037*k1) + 61*k2)*(3 + 17*p + 1037*k1) + p + 61*k3) + 61*k4)

Từ việc khai triển trên, ta thấy được rằng
$$q \approx 17p$$
$$r \approx 29pq \approx 29 \cdot 17p^2$$
$$s \approx qr \approx 17p \cdot 29 \cdot17 p^2 \approx 29 \cdot17^2 p^3 $$
$$t\approx rsq \approx 29 \cdot 17p^2 \cdot 29 \cdot 17^2 p^3 \cdot 17p = 29^2\cdot17^4p^6$$
$$n = pqrst \approx 29^4\cdot17^8p^{13}$$

Từ đó, ta có thể tìm được giá trị sấp xỉ của p bằng cách
$$p \approx \sqrt[13]{\dfrac{n}{29^4\cdot17^8}}$$

Sau đó ta sẽ bruteforce p, sao cho giá trị p là nghiệm của N.

from Crypto.Util.number import isPrime, long_to_bytes
from gmpy2 import next_prime, iroot
import sys

n = pow(10, 5)
sys.setrecursionlimit(n)

def nextPrime(p):
    if isPrime(p):
        return p
    else:
        return nextPrime(p+61)

n = 485889862688353809145356849681869098056742135790325154633816315764783289109350404808839464043297429168130293002483316664607770068196944445394490388957147529192164743228508084885030734914365245916125607677185307000076761646830755541107131137865984020648243428286711853728051263128076845261298240617545417811431124904304446607845470628505361436115651109768237103000946120781642652665829238385087624612205525857191218811570122228639908283598707567056620352822139985271817003262919597858495812801663331842855143930997258260164422858382713240717739568744168349527025412634588705503126870149875268600539407786323924132037483972529603572727892740460450963315253482630345996561505957763886776070413535287129043703855880444326909520084249767518737040222995586717034060176093473694948961503759770499124924886087468497100053775745634680192678426965540847613838559522315570932873854027804486662281273550134766570419630624914801192395060568099367828616501877701994364906741451132770474154689411119296104818089636891131318495955929
p_approx = iroot(n//(pow(17,8)*pow(29,4)),13)[0]
print(p_approx)
for i in range(p_approx - 10000, p_approx + 10000):
    if n % i == 0:
        p = i
        break
print(p)
q = nextPrime(nextPrime(17*p+1)+3)
r = nextPrime(29*p*q)
s = nextPrime(q*r+p)
t = nextPrime(r*s*q)

phi = (p-1)*(q-1)*(r-1)*(s-1)*(t-1)
e = 65537
d = pow(e,-1,phi)
c = 1838979268925267202615818395622122484893202706167722156383681963142079180161531237936585341507802530813847301831886857107840552940103096671213346624172927405178565892385733216702672851783423891229382579221604596673156151519463795808010572632138076246765227545034269340790242411584582692558549837221897037971538915332866933837117883228953143242965510280921618063635225603250391037969273250144174802927111408106890496901519737395485115788436384012937788617630381389196078818501905993385084557887716148781944416313908553565974546239241287340505018036547080504009483360838747251073440799502791555942879229132369697126614944991347408598924472158561247485575276852356316968119522601927483600978106155875300324966339458896992260918634629607740522754923275555209240690069838566642421234035117257380757518902549668151860260985363114235340791362277047923494577018035035653075155240898800910887230020812289524262582877697129108304758256250595391379019020972909027192107727799235384374670082518555887502478560056865020860127002
m = pow(c,d,n)

print(long_to_bytes(m))

**Flag: pearl{7h1s_0n3_w4s_f0r_7h3_k1ds}**

### Security ++
Secure.py

flag = b'PearlCTF{day-la-flag}'
key = b'a'*8 + b'b'*8 + b'c'*8 + b'd'*8
from base64 import b64encode
from enc import encrypt_block, pad


def encrypt(data: bytes):
    pt = data + flag
    pt = pad(pt)
    block_count = len(pt) // 16
    encText = b''
    for i in range(block_count):
        if i % 2 == 0:
            encText += encrypt_block(pt[i * 16:i * 16 + 16], key[0:16])
        else:
            encText += encrypt_block(pt[i * 16:i * 16 + 16], key[16:])
    return encText


def main():
    while 1:
        msg = input("\nEnter plaintext: ").strip()
        res = encrypt(msg.encode())
        print(b64encode(res).decode())


if __name__ == '__main__':
    main()

enc.py

from copy import copy

s_box = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)


def bytes2matrix(text):
    return [list(text[i:i + 4]) for i in range(0, len(text), 4)]


def matrix2bytes(m):
    plaintext = b''
    for row in range(4):
        for j in range(4):
            plaintext += chr(m[row][j]).encode('latin-1')
    return plaintext


def pad(text: bytes):
    if len(text) % 16 != 0:
        pad_len = ((len(text) // 16) + 1) * 16 - len(text)
    else:
        pad_len = 0
    text = text.ljust(len(text) + pad_len, b'.')
    return text


def sub_bytes(state, sbox):
    for i in range(len(state)):
        for j in range(4):
            state[i][j] = sbox[state[i][j]]
    return state


def shift_rows(s):
    s[1][0], s[1][1], s[1][2], s[1][3] = s[1][1], s[1][2], s[1][3], s[1][0]
    s[2][0], s[2][1], s[2][2], s[2][3] = s[2][2], s[2][3], s[2][0], s[2][1]
    s[3][0], s[3][1], s[3][2], s[3][3] = s[3][3], s[3][0], s[3][1], s[3][2]
    return s


def gmul(a, b):
    if b == 1:
        return a
    tmp = (a << 1) & 0xff
    if b == 2:
        return tmp if a < 128 else tmp ^ 0x1b
    if b == 3:
        return gmul(a, 2) ^ a


def mix_col(col):
    temp = copy(col)
    col[0] = gmul(temp[0], 2) ^ gmul(temp[1], 3) ^ gmul(
        temp[2], 1) ^ gmul(temp[3], 1)
    col[1] = gmul(temp[0], 1) ^ gmul(temp[1], 2) ^ gmul(
        temp[2], 3) ^ gmul(temp[3], 1)
    col[2] = gmul(temp[0], 1) ^ gmul(temp[1], 1) ^ gmul(
        temp[2], 2) ^ gmul(temp[3], 3)
    col[3] = gmul(temp[0], 3) ^ gmul(temp[1], 1) ^ gmul(
        temp[2], 1) ^ gmul(temp[3], 2)
    return col


def add_round_key(state, round_key):
    for i in range(len(state)):
        for j in range(len(state[0])):
            state[i][j] = state[i][j] ^ round_key[i][j]
    return state


def encrypt_block(ptext: bytes, key):
    cipher = ptext
    rkey = bytes2matrix(key)

    for i in range(10):
        ctext = bytes2matrix(cipher)
        ctext = sub_bytes(ctext, s_box)
        ctext = shift_rows(ctext)
        temp = copy(ctext)
        for j in range(4):
            column = [temp[0][j], temp[1][j], temp[2][j], temp[3][j]]
            column = mix_col(column)
            for k in range(4):
                ctext[k][j] = column[k]
        ctext = add_round_key(ctext, rkey)
        cipher = matrix2bytes(ctext)
    return cipher

Solve.py

#!/usr/bin/python3 
from pwn import*
from base64 import*
from string import printable

io = process(["python3", "secure.py"])
brt_char = b''
payload_1 = b'a'*16
flag = b''
for i in range(40):
    payload_1 = payload_1[1:] + brt_char
    for j in printable:
        payload = payload_1 + j.encode() + b'a'*(31-i)
        io.recvuntil(b'Enter plaintext: ')
        io.sendline(payload)
        data = io.recvuntil(b'\n',drop=True).decode()
        data = b64decode(data)
        if data[:16] == data[32:48]:
            flag += j.encode()
            brt_char = j.encode()
            print(flag)
            break

### 3 spies

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long

with open('flag.txt', 'rb') as f:
    flag = f.read()


n1 = getPrime(512)*getPrime(512)
n2 = getPrime(512)*getPrime(512)
n3 = getPrime(512)*getPrime(512)

e=3

m = bytes_to_long(flag)

c1 = pow(m,e,n1)
c2 = pow(m,e,n2)
c3 = pow(m,e,n3)
    
with open('encrypted-messages.txt', 'w') as f:
    f.write(f'n1: {n1}\n')
    f.write(f'e: {e}\n')
    f.write(f'c1: {c1}\n\n')
    f.write(f'n2: {n2}\n')
    f.write(f'e: {e}\n')
    f.write(f'c2: {c2}\n\n')
    f.write(f'n3: {n3}\n')
    f.write(f'e: {e}\n')
    f.write(f'c3: {c3}\n')

n1: 125267411676839013904356880992044234494446196964982422223130579882047339346910691451497681975351838034684254305738613386927222900898672184001345811471784343779083336010063097729870079645284178978512325038316112509718505547104307526489798594871208559607331790920412305711830820739308995357441030646151241475357
e: 3
c1: 53377681151597930200174280269480737905892580547675095951568028531545776989476273786562435486230550919422086944133253611872983670236114054374565938184593173194919064517779661178744278071496565181181705071524501841159717567250259220092464925447795412484629687708208662079791459184303259833667333882817260906165

n2: 101985110329687359982214188967281711679876126442294375297547334583432698756724057183438691227371260175904715854057793173086301783390154807726779286131084537704721881438398569476214173211311977143694032174701007005033830070482491565424683664984059187439768982994371382763048098663670188786016786612348042190633
e: 3
c2: 86370003324603283962938004647941072863866893771153362222202759619566185050496089684606274416415418388916028237984708280964054009059814813483639010674182298294505525549842057730933691736372086557397211586739691237738757897947336698446258197604918828646265244195686107866422922575275382813594250335044143485624

n3: 83259448903366278561128205003734328779222118906091604625605804813528274055482582431201682767294594942491788720967344243567819654813240542076250030802111361571504667752481579915864184180358691091092122509649590043074189547962292835856503625214027405901620103615424259796442446412031011575671410630232956892267
e: 3
c3: 25601241268900087228853235319569275926328919786631787991019848828558430219449358810095537362492238844266084660904521793373698736119824512458196492049138821633273765102576368573691391116632126183996786969554104441242376959688329346567745607825277943462236901478944551669406261301309719409165457168678763092118

from Crypto.Util.number import long_to_bytes
from functools import reduce
from gmpy2 import iroot

n1 = 125267411676839013904356880992044234494446196964982422223130579882047339346910691451497681975351838034684254305738613386927222900898672184001345811471784343779083336010063097729870079645284178978512325038316112509718505547104307526489798594871208559607331790920412305711830820739308995357441030646151241475357
e = 3
c1 = 53377681151597930200174280269480737905892580547675095951568028531545776989476273786562435486230550919422086944133253611872983670236114054374565938184593173194919064517779661178744278071496565181181705071524501841159717567250259220092464925447795412484629687708208662079791459184303259833667333882817260906165

n2= 101985110329687359982214188967281711679876126442294375297547334583432698756724057183438691227371260175904715854057793173086301783390154807726779286131084537704721881438398569476214173211311977143694032174701007005033830070482491565424683664984059187439768982994371382763048098663670188786016786612348042190633
e=  3
c2= 86370003324603283962938004647941072863866893771153362222202759619566185050496089684606274416415418388916028237984708280964054009059814813483639010674182298294505525549842057730933691736372086557397211586739691237738757897947336698446258197604918828646265244195686107866422922575275382813594250335044143485624

n3 = 83259448903366278561128205003734328779222118906091604625605804813528274055482582431201682767294594942491788720967344243567819654813240542076250030802111361571504667752481579915864184180358691091092122509649590043074189547962292835856503625214027405901620103615424259796442446412031011575671410630232956892267
e =  3
c3 =  25601241268900087228853235319569275926328919786631787991019848828558430219449358810095537362492238844266084660904521793373698736119824512458196492049138821633273765102576368573691391116632126183996786969554104441242376959688329346567745607825277943462236901478944551669406261301309719409165457168678763092118

def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod

def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a // b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1

m=chinese_remainder([n1,n2,n3],[c1,c2,c3])
flag = iroot(m,3)
print(flag)