# TAMU CTF
## Truncated 1


Ta nhận được 2 file pem chứa publickey và privatekey. Không may thay file privatekey.pem bị cắt cụt phần đầu.

ZXPI0zfM5EJkeooRvNr3RKQEoQKBgQD0WrYbxhBveSRYvkOV0+omfutwS6wIoCme
CYCq5MboHdZn8NDCHy+Y66b+G/GMZJewqEKQSLwHcAjKHxouneFXp6AxV0rkBWtO
RNnjXfthsWXvOgBJzGm8CJQS+xVtUpYc4l1QnYaQpc0/SClSTPG775H5DnJ8t4rK
oNQur+/pcwKBgD1BU0AjW6x+GYPXUzA0/tXQpu5XaAMxkinhiiOJWT/AExzJU8Jt
eQULJ3EDENG6acSuwMhm0WMLhQ0JG6gIejRyOBZSIqjESWGHPmkU1XbUDz0iLb1h
HTqJMAWYKWJs4RnJbx6NGJAhd2Ni4CyOGmujYpqNnp1qfZNhmcj/VOeBAoGBAJgD
stU2c9UVlTIMM7mLG1kVjlzPBtha42ko2j32k3Ol1FPXcdfCVPcaa0ockjnX/rJt
CvP9+9PYs+8iSESF/cFtS/BGMRYH9Qi9NpwHRLMzDIo2GCXRIFpVL+FbCKp5PV/8
xza2uRdVvolG2EYWDjDvym0Zusmx2YtTYI0m8ObXAoGAZ6T8aF6GAZ0s814ZfEcy
zZGrZZQ/MJ7W8ZGdU1/y+204LzfGsW+d+sTPfQPYhn03/qU3SFhP095sYzELeOOZ
3yITOftHEdMP3XffnAudgn3tBHrtu0EsVFL44H7CWe4hx3M49M0lfERD60lPwUG1
8hY5qcthSko1f1WkTgN7Rrs=
-----END PRIVATE KEY-----

Mình nghĩ chỉ cần thêm `-----BEGIN PRIVATE KEY-----
` thì mình sẽ lấy được thông tin gì đó nhưng không, nó không hề đọc thông tin của khóa.

Sau khi stuck quá lâu thì mình đi xin hint của một người anh đẹp trai, và mình nhận được cái blog này [twitter-secrets](https://blog.cryptohack.org/twitter-secrets).

Private key được mã hóa trong file PEM sẽ bao gồm các thành phần như sau: $n, e, d, p, q, d \mod (p - 1), d \mod (q-1)$ có format như sau:

PrivateKeyInfo ::= SEQUENCE {
   version Version,
   privateKeyAlgorithm AlgorithmIdentifier ,
   privateKey PrivateKey,
   attributes [0] Attributes OPTIONAL
}

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

File PEM được mã hóa theo format DER và sau đó được encode bằng base64. Thử decode base64 để có cái nhìn trực quan.
Các thành phần được phân tách tại các bytes đặc biệt. Nhưng ở đây ta thấy được có đến 2 bộ bytes đặc biệt.
là `02 81 80` và `02 81 81`
- `02` là kiểu dữ liệu, ở đây là integer
- `81` là độ dài của giá trị số nguyên sẽ được mã hóa theo 2 byte sau.
- `81` hoặc `80` là độ dài thực tế của thành phần đó.



Sau khi check tất cả các trường hợp thì mình nhân được một số nguyên tố và nó chính là `p`. Giờ chỉ việc đi lấy flag thôi.

from Crypto.PublicKey import RSA 
from Crypto.Util.number import long_to_bytes, bytes_to_long

pubkey = RSA.import_key(open("public.pem").read())
#privkey = RSA.import_key(open("private.pem").read())

n = pubkey.n
e = pubkey.e
p = 171591453807815360055383432361744738571408045745496169801430992882142401100861734451639082772737244851844544019866927162589906672848777094551880156673924037027502474510855110537773122402652662824704382923888088092543963549151216084489617389710494396822238199408480117071568865534432933911118270203872402205043
q = n // p
print(n)
print(p)
print(q)
c = open("flag.txt.enc", 'rb').read()
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(bytes_to_long(c), d, n)

print((long_to_bytes(m)))

Flag: `gigem{Q_Fr0M_Pr1V473_K3Y_89JD54}`

## Truncated 2


Ta tiếp tục nhận được file privatekey bị cắt phần đầu.
Decode base64:


Ta nhận được 3 phần, theo như format thì phần cuối của file là:

  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p

Vậy là ta nhận được 3 phần chính là dp, dq và invQ.
Từ $dp, dq$ ta có thể dễ dàng tìm ra được p và q.

$dp = d \mod (p-1)$

$ed = 1 \mod (p-1)(q-1)$
$\to ed = 1 + k*(p-1)(q-1)$

lấy modul p-1 cho 2 vế:

suy ra: $e*dp = 1 \mod (p-1)$
Ta có thể viết như sau: $e * dp = 1 + k*(p-1)$

Từ với $k < e$ việc tìm p trở nên khá dễ dàng.

**script:**

from Crypto.PublicKey import RSA 
from sympy import isprime
from Crypto.Util.number import long_to_bytes, bytes_to_long
pubkey = RSA.import_key(open("public.pem").read())
#privkey = RSA.import_key(open("private.pem").read())

n = pubkey.n
e = pubkey.e
data_hex = '5971f6b5e70281804894e9fa2c26b0e1c631ced2f86be0207a82751d707b018839565e93f551df596e9d16f05599a2bfb0bbb300064139f383de85c793e058da2cce41a9a0398e40be05bb9b82703fe804164f5ff4d76623d0e4c720fd705ce6eface979489a8b3a2bd6630077699c0aa8da6250c1de8840d3e5afc34db865e0650ce08f828b49ad02818054d4d1981870d799334e5ae5174526d2979e14c6ecc74d7b59600fbf7db4c060481c3d38c83aa4048e4c6ad483a416d43aecc58db7fe8b9e3d114187538c02b22c9197fe3afd23a83f6e9ac33fab55c84776b1de23a6057e91c47e36ab2ac7600adbbfeb4159d8b09d81898f9a04e47b679cbe690daf6a60551f2b8227863377028180676ab6ccf3e15bdbfbe61abc7f056f2c68cfc834f8806233d7af1d9c204b2cc1ec36ff32d2dc0a40c63c527a8a04120891a0be8facdd08cfbd094dd21060bf4f041ce624ce1e692715fbaf45837a58a3976d3419248c766831da473e0c665a4739515e1eb998f7fb3ecb6e14da7386f64002cc1cf25ca2393f14f8d1bfe6206b'
data_hex = data_hex.split('028180')
print(data_hex)

##find p and q
# for dp in data_hex[1:]:
#     dp = int(dp, 16)
#     for kp in range(3, e):
#         p_mul = dp * e - 1
#         if p_mul % kp == 0:
#             p = (p_mul // kp) + 1
#             if isprime(p) and n % p == 0:
#                 print(f"Possible p: {p}")
#                 break

p = 175686589048371524987437716214231436544952421988758977028512309898670634575798354986395679131909077133458646058850182514737865035891817435157438827258054551419621190227752633841294595721590533491316564587316052552895454011463277500314590143225393639686181953221172969420780838402312402869662496440462358754237
q = 146499949876031596595119473544158492278112465965128296098554215599527541093216463269448197726258519438043835011477106576649738579124758942019192335365960513430943680607378942906030476700381704046104806602324753526654817790452245515616252739559328483440653497757953778117237609624419671326102551735126101243367

assert p*q == n

c = open("flag.txt.enc", 'rb').read()
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(bytes_to_long(c), d, n)

print((long_to_bytes(m)))

Flag: `gigem{DP_DQ_r54_7rUNC473D_SDA79}`

Mình méo hiểu sao câu Truncated 1 lại ra được một số nguyên tố rõ ràng nó là phần cuối của file pem thì làm gì có được cái đấy.

## Criminal

**server.py**

from base64 import b64encode
from Crypto.Random import get_random_bytes
from Crypto.Cipher import ChaCha20_Poly1305
from pathlib import Path
from zlib import compress

flag = Path("flag.txt").read_bytes()
key = get_random_bytes(32)

try:  
    while True:
        append = input("Append whatever you want to the flag: ").encode()
        # gotta save on bandwidth!
        m = compress(flag + append)
        cipher = ChaCha20_Poly1305.new(key=key)
        cipher.update(m)
        c, tag = cipher.encrypt_and_digest(m)
        res = cipher.nonce + tag + c
        print(b64encode(res).decode())
except (KeyboardInterrupt, EOFError):
    pass

Chall này sử dụng mã hóa ChaCha20_Poly1305 như bug của bài này không phải ở mã hóa ChaCha20 nhưng mà hàm compress. Nó được nhắc đến ở đây [CRIME vuln](https://en.wikipedia.org/wiki/CRIME).

Cùng xem qua lib `zlib` và hàm `compress`.


Với các ký tự dùng để compress khác nhau có có thể dẫn đến sự thay đội độ dài của ouput.
Ở đây ta dùng `flag{a` khi compress với `flag{b` thì cái len của nó lớn hơn so với khi compress với `flag{a`.


Từ hình ảnh trên nếu ta compress `bytes1` và `bytes2` nếu `bytes2` là một phần của `bytes1` thì nó sẽ cho ra một cái len nào đó, còn nếu không phải là một phần của `bytes1` thì nó cho ra một cái len lớn hơn.

**script:**

from pwn import *
import base64 
import string

#context.log_level = "debug"
io = remote("tamuctf.com", 443, ssl=True, sni="criminal")

alphabet = [chr(ord('a')+ i) for i in range(26)]
alphabet.append('_')

flag = 'gigem{'
io.recvuntil(b'Append whatever you want to the flag: ')
io.sendline((flag+';').encode())
# vì ';' không thuộc FLAG nên mình sẽ dùng nó để lấy một cái leng chuẩn để so sánh.
leng = len(base64.b64decode(io.recvuntil(b'\n', drop = True).decode()))

print(leng)
while True:
    for char in alphabet:
        io.recvuntil(b'Append whatever you want to the flag: ')
        io.sendline((flag + char).encode())
        data = base64.b64decode(io.recvuntil(b'\n', drop = True).decode())
        print(len(data))
        if len(data) < leng:
            flag += char
            break
        
    print(flag)

Chạy đến đây thì không nhận được thêm ký tự nào phù hợp nữa.


Flag: `gigem{foiled_again}`

## Smooth Criminal

Chall này có source như sau:

from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from math import lcm,gcd
from secrets import randbelow
from hashlib import sha256

NUM_BITS = 2048

def getModulus(bits):
    n = 1
    primes = []
    while n.bit_length() < bits:
        p = getPrime(24)
        if p not in primes:
            n *= p
            primes.append(p)
    return n, primes

def sign(n,msg,d):
    h = bytes_to_long(sha256(msg).digest())
    k = randbelow(q-2)+1
    x = pow(h,k,n)
    r = pow(x,d,n)
    s = pow(h+x,d,n)
    return r,s

def verify(n,msg,e,r,s):
    h = bytes_to_long(sha256(msg).digest())
    v1 = pow(r,e,n)
    v2 = pow(s,e,n)
    return v2 == (v1 + h) % n

n,primes = getModulus(NUM_BITS)
q = 1
for p in primes:
    q = lcm(q,p-1)
msgs = []
e = 65537
d = pow(e,-1,q)

print(f"The modulus is ... a mystery left for you to unfold.")
print(f"Your verification exponent {e = }")
msg = input("Give the oracle a message to sign: ").encode()
msgs.append(msg)
r,s = sign(n,msg,d)
print(f"Your verification signature is ({r}, {s})")

msg = input("Give the oracle another message to sign: ").encode()
msgs.append(msg)
r,s = sign(n,msg,d)
print(f"Your second verification signature is ({r}, {s})")

comm = input("Ask the oracle a question: ").encode()
r,s = input("Give the verification signature: ").split(",")
r,s = int(r),int(s)

if comm in msgs:
    print("Hey, no cheating")
    exit()
if verify(n,comm,e,r,s):
    if comm == b"What is the flag?":
        print("The flag is: ",end="")
        with open("flag.txt","r") as flag:
            print(flag.read())
    else:
        print("Not the right question.")
else:
    print("Invalid signature")

Ta chỉ có 2 lần gửi đến msg để nhận `r, s` và lần cuối ta cần gửi `comm = b"What is the flag?"` và giá trị chính xác của `r` và `s` sau khi thực hiện hàm `sign` với `comm`.

Bài này ta đang không có thông tin của `N`, với 2 lần gửi ta có thể lấy lại N bằng `gcd` thông qua dữ kiện sau đây:
`v2 == (v1 + h) % n`

Tức là: $s^e = r^e +h \mod n$
suy ra: $s^e - r^e - h = m*n$
Với 2 lần gửi ta có được 2 bội của $n$. Nhưng ban đầu mình thử `gcd` nhưng không được vì bội đó quá lớn. Nên mình bỏ sài cách này.

Vì N là một smooth number được tạo từ các số nguyên tố có 24 bit. Ta có thể bruteforce được những số nguyên tố này, trông có vẻ khá cơ bắp một tí 💪.

Vì $(s^e - r^e - h) \mod n = 0$ suy ra: $(s^e - r^e - h) \mod p_i = 0$

**script:**

from pwn import remote
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from secrets import randbelow
from math import lcm,gcd
from hashlib import sha256
from sympy import nextprime
from tqdm import tqdm

io = remote("localhost", 1337)
io.recvuntil(b'Give the oracle a message to sign: ')
io.sendline(b'Obito')
io.recvuntil(b'Your verification signature is ')
r, s = eval(io.recvuntil(b'\n', drop=True).decode())

io.recvuntil(b'Give the oracle another message to sign: ')
h = bytes_to_long(sha256(b'Obito').digest())
io.sendline(b'hahaha')

print("Factoring N ...", end=" ")
e = 65537
factors = []
p = 2**23
q = 1
n = 1
max = 2**24
while p < max:
    p = nextprime(p)
    v1 = pow(r,e,p)
    v2 = pow(s,e,p)
    if (v2 - v1 - h) % p == 0:
        q = lcm(q, p-1)
        n*=p
        factors.append(p)
        
print('Done')
print(factors)


def sign(n,msg,d):
    h = bytes_to_long(sha256(msg).digest())
    k = randbelow(q-2)+1
    x = pow(h,k,n)
    r = pow(x,d,n)
    s = pow(h+x,d,n)
    return r,s

io.recvuntil(b'Ask the oracle a question: ')
io.sendline(b"What is the flag?")

io.recvuntil(b'Give the verification signature: ')
r, s = sign(n,b"What is the flag?", pow(e, -1, q))

io.sendline(str(r).encode() + b','  + str(s).encode())
io.interactive()


Flag: `gigem{sm00th_numb3rs_4r3_345y_70_f4c70r}`

## Jumbled

Mô tả:
`The RSA Public and Private keys are provided. However, the private key seems to be jumbled in a block size of 10 hex characters. Can you get the flag?`

Đề cho ta file flag.enc, public và private

**public**

2d 2d 2d 2d 2d 42 45 47 49 4e 20 50 55 42 4c 49 43 20 4b 45 59 2d 2d 2d 2d 2d 0d 0a 4d 49 49 42 49 6a 41 4e 42 67 6b 71 68 6b 69 47 39 77 30 42 41 51 45 46 41 41 4f 43 41 51 38 41 4d 49 49 42 43 67 4b 43 41 51 45 41 71 6d 54 59 68 59 54 37 2b 4e 42 7a 5a 44 72 73 66 4b 44 34 0d 0a 34 4b 2b 39 72 74 4c 63 5a 4c 54 2b 56 61 57 48 59 76 6e 38 42 70 39 58 2f 66 67 37 54 6d 4b 35 6c 35 44 36 4d 73 46 38 39 72 5a 38 74 61 45 47 46 4a 50 79 2b 6b 78 2b 71 55 71 4f 4f 39 35 47 0d 0a 51 68 4d 32 53 58 41 77 6e 30 44 31 54 4a 4b 64 61 53 5a 75 6e 47 30 36 70 63 51 33 62 2b 70 62 35 47 44 59 59 70 34 33 50 37 61 67 55 73 67 48 53 43 77 32 4f 46 43 74 55 2f 4d 73 35 33 45 77 0d 0a 69 32 6a 35 31 64 45 76 2b 38 4b 62 75 71 49 70 32 49 4f 47 7a 4c 79 33 4d 7a 78 34 72 31 54 6a 54 49 6d 31 38 44 6e 70 56 56 65 6f 79 38 73 4e 74 57 62 56 64 6e 43 43 74 49 59 36 4c 6e 50 50 0d 0a 73 6d 61 4f 4a 31 2b 6a 57 72 57 67 76 39 44 6e 64 70 5a 49 65 44 4f 75 6f 7a 64 31 62 4b 6c 74 4c 42 65 49 4b 32 6b 66 46 6e 6f 78 6f 6d 54 67 57 2b 53 41 53 4c 34 72 6e 2f 6f 6a 71 4e 63 30 0d 0a 36 43 5a 35 4c 2b 4b 6e 44 43 42 79 62 68 47 33 73 67 54 69 6d 7a 77 30 51 4d 72 53 35 47 33 35 6b 46 76 32 6c 33 4d 37 2f 38 57 48 4f 69 58 57 70 53 53 5a 4b 6d 4b 71 31 54 73 62 65 76 2b 72 0d 0a 6c 77 49 44 41 51 41 42 0d 0a 2d 2d 2d 2d 2d 45 4e 44 20 50 55 42 4c 49 43 20 4b 45 59 2d 2d 2d 2d 2d

**private**

49 45 4e 42 47 2d 2d 2d 2d 2d 20 54 4b 41 45 49 50 56 20 52 0a 2d 4d 2d 0d 2d 59 2d 45 2d 44 42 41 49 41 76 49 41 49 45 47 6b 39 68 69 6b 42 71 4e 67 41 46 53 45 41 41 30 51 77 42 69 67 41 67 53 59 42 77 43 4b 51 42 43 49 41 41 45 6f 67 41 34 50 30 68 76 69 5a 46 71 4e 38 75 6f 4f 78 0d 4e 0a 48 6b 74 75 78 32 30 72 6a 37 50 67 69 59 2b 70 64 35 74 56 6b 50 44 39 74 66 2b 6e 77 31 66 47 79 50 77 6b 6f 6d 59 58 4f 72 51 31 59 79 6f 74 7a 6e 58 32 70 48 0d 54 36 4c 6b 36 55 2f 43 6b 45 33 5a 34 53 37 0a 6f 50 66 56 43 51 63 5a 44 7a 4a 63 6d 62 4a 36 31 6b 70 4d 70 6c 76 76 64 36 78 71 44 54 6c 2f 6a 74 6e 63 68 59 69 6b 4e 44 49 59 64 4c 79 42 41 71 53 79 0a 7a 0d 38 31 55 54 34 4b 56 50 30 61 6e 43 63 4c 6e 54 69 36 6e 75 6f 77 2f 70 53 37 7a 4c 50 76 63 62 67 4d 59 34 62 4d 58 4e 69 56 69 4f 48 76 4c 36 79 56 6a 6c 4f 56 77 65 49 32 4b 56 63 5a 32 74 77 31 38 75 2b 6f 63 68 0d 6a 30 0a 61 36 74 58 4e 34 5a 6e 79 6f 6b 32 68 64 6c 30 43 4f 61 2f 73 33 71 4e 56 36 4d 6a 34 36 52 72 38 67 61 46 30 34 57 73 62 4f 35 5a 42 47 65 69 57 6a 0a 66 2b 75 0d 76 42 69 49 49 6e 6f 6b 54 4a 31 4f 7a 69 6f 75 48 45 49 4a 63 34 4d 76 71 44 62 52 4b 50 42 65 4f 62 79 51 66 57 62 6d 4c 79 6b 41 74 59 2f 63 76 78 63 61 7a 2f 58 71 4a 59 4a 6b 61 4a 6c 36 64 36 78 2f 4f 74 0d 72 0a 71 56 41 42 45 4d 41 41 75 67 36 58 67 55 43 41 38 45 67 41 43 67 57 4b 69 47 2b 55 71 77 4c 53 47 74 79 49 72 61 65 6a 6f 33 78 6b 56 73 44 37 71 65 73 4d 2b 2f 0d 52 36 4d 2b 77 6a 6d 45 77 49 35 6e 47 5a 61 0a 74 64 77 5a 39 37 59 46 70 6b 33 2b 6b 72 4f 38 6b 45 6d 4f 2f 52 6e 63 47 6f 54 53 6f 53 63 33 4f 51 75 53 42 6c 67 65 42 64 42 5a 37 33 57 6e 48 75 31 58 0a 42 0d 75 74 51 6f 78 42 33 52 59 74 6a 71 2b 69 4e 72 42 41 49 52 6e 6a 36 78 4a 56 73 6f 49 31 6a 34 57 61 30 42 70 6d 4e 68 78 7a 70 46 2f 34 78 44 42 2b 71 57 59 6b 71 2f 61 39 47 48 37 57 69 4d 70 4c 32 68 43 51 52 55 0d 63 38 0a 56 2f 38 4f 45 30 4c 39 74 50 68 43 45 4e 74 49 44 31 46 43 43 6b 73 76 57 58 52 39 30 59 68 45 78 51 74 4e 45 39 44 62 55 4a 4b 79 4b 67 38 51 71 6c 0a 71 76 34 0d 59 4b 6c 61 33 73 4b 41 50 67 6a 62 34 32 61 41 4b 59 39 4a 78 48 39 4a 74 74 6b 73 30 59 58 44 70 6b 34 75 45 5a 6a 44 54 4b 4f 57 30 4a 31 78 31 51 68 53 42 50 63 7a 47 2b 52 39 68 71 5a 69 75 65 55 45 54 34 0d 65 0a 67 6f 2b 51 39 37 33 71 50 6a 47 58 58 49 46 71 4d 6a 4b 49 64 48 43 54 58 4a 2b 46 30 4b 45 2f 42 51 67 35 4b 32 5a 33 6e 55 42 74 64 2b 6a 6d 44 63 51 46 53 63 0d 2f 6a 66 77 62 55 4c 46 64 4b 6f 30 51 4d 38 0a 33 55 64 6c 34 42 49 56 45 52 34 7a 46 55 68 4c 4e 52 6a 79 50 46 52 41 68 44 53 7a 63 76 75 66 4d 2b 37 41 55 63 7a 52 4e 39 50 70 4d 2f 4d 42 63 45 41 63 0a 58 0d 4b 79 4b 50 6a 58 42 45 68 4b 49 71 61 6d 43 53 73 42 61 2f 69 55 4e 52 6a 4e 38 42 43 78 75 6f 4e 6b 62 6c 2b 67 66 6c 58 45 73 39 6f 75 33 4b 46 63 44 70 6d 35 38 62 4b 51 6d 31 57 68 6a 38 6e 71 48 4e 56 67 64 4c 0d 74 36 0a 6d 49 49 32 67 6e 6a 7a 48 37 77 70 4b 67 67 58 32 63 61 68 45 4a 68 77 6e 44 67 63 42 51 46 49 63 37 55 72 65 69 69 71 32 4b 78 7a 36 70 66 6e 34 45 0a 79 68 31 0d 36 54 43 74 67 69 4c 53 42 4b 71 55 74 43 6f 6e 36 52 34 74 5a 45 49 65 5a 2f 37 59 59 35 42 45 78 67 5a 62 68 50 4d 50 77 2b 76 71 6e 37 45 57 47 61 48 58 52 73 37 30 72 68 64 34 59 56 39 79 63 69 4e 4e 54 54 0d 4b 0a 31 73 54 6e 6c 34 30 75 77 65 72 66 5a 69 70 2f 38 75 64 76 69 47 30 51 42 64 44 30 78 69 36 53 2b 76 4a 70 49 58 36 72 4c 58 70 7a 69 53 31 56 6f 4b 44 55 39 4e 0d 75 76 4a 6f 39 64 52 64 72 58 45 78 53 75 72 0a 50 33 41 72 78 59 67 4b 42 51 42 50 6e 6b 65 51 74 6e 56 79 70 74 63 62 47 75 31 6a 6f 74 4b 4c 71 6a 42 63 66 43 45 30 73 4e 76 53 42 65 2b 61 51 48 7a 42 0a 73 0d 34 68 4e 79 6c 74 57 35 36 74 37 51 59 38 47 61 7a 69 73 59 5a 69 6b 7a 4a 70 43 59 64 44 63 37 58 79 77 32 45 32 6d 30 4d 7a 33 32 2b 56 63 51 36 74 69 59 67 37 37 44 72 75 42 73 74 4e 78 76 4d 6b 6a 4c 64 42 41 36 0d 59 70 0a 77 4e 42 6b 36 48 50 55 50 77 76 66 47 65 4e 47 4f 50 62 4f 69 69 56 2b 4c 78 32 73 58 35 74 4f 68 53 7a 6d 70 46 61 48 31 6b 41 43 41 68 31 51 30 44 0a 31 45 62 0d 62 47 69 6f 41 4a 41 66 65 74 6c 6c 63 36 56 62 58 4a 4f 42 39 54 48 53 65 4b 71 41 7a 63 4d 30 47 66 6c 36 74 6d 64 67 55 34 4a 62 71 36 4d 57 48 76 50 31 6b 56 78 5a 2f 54 72 76 6f 32 38 67 70 49 72 54 56 65 0d 7a 0a 43 64 37 31 78 50 54 31 69 66 50 50 77 67 62 46 35 75 56 52 6e 2b 2b 56 4f 5a 65 71 6d 53 73 76 41 38 39 56 6b 79 44 35 51 38 56 52 32 39 70 5a 33 6c 32 63 71 62 0d 45 7a 67 6b 6f 54 57 70 72 56 54 35 61 65 75 0a 6e 39 57 37 2b 46 66 54 6d 6a 42 74 30 42 46 37 44 48 4a 58 4b 6b 55 6b 76 37 62 67 6d 7a 4a 62 46 42 2b 64 41 67 7a 43 59 32 50 4a 4b 74 6a 5a 39 63 45 4c 0a 37 0d 68 72 4f 6c 31 38 4a 70 53 69 31 55 36 75 4a 65 65 37 74 32 79 6c 4c 67 6b 63 77 4c 76 71 53 41 46 50 78 6c 2f 52 2b 52 36 67 47 64 35 54 6b 2b 6d 74 4a 69 54 6c 74 2f 33 35 62 49 70 41 50 62 59 54 67 77 59 62 6a 77 0d 46 44 0a 58 2f 49 4c 4b 2b 69 44 68 77 68 71 68 73 71 73 62 35 45 52 4d 7a 54 36 46 42 7a 2b 41 67 2b 79 50 74 77 79 52 50 4b 38 72 59 76 6e 56 37 36 43 43 57 0a 65 70 56 0d 33 32 65 4e 61 46 6a 61 6b 53 44 6c 54 61 49 4f 52 74 77 37 37 79 6f 64 6a 2d 2d 2d 2d 2d 0d 3d 0a 51 3d 41 49 54 52 56 20 4e 50 45 44 2d 2d 2d 2d 2d 45 20 59 45 4b

Với `public` mình decode hex thì nó là định dạng file PEM chứa, còn private theo như đề bài mô tả thì nó đã bị `shuffled` nhưng trong phạm vi 10 bytes. Ta cần tìm ra quy luật và đưa nó về nguyên trạng.

Với tất cả các file pem chứa private key thì phần mở đầu của nó chính là `-----BEGIN PRIVATE KEY-----`. Từ dữ kiện nãy ta có thể so sánh với các bytes đầu tiên bị xáo trộn để xem quy luật của nó.

Bytes đúng:

2d 2d 2d 2d 2d 42 45 47 49 4e 20 50 52 49 56 41 54 45 20 4b 45 59 2d 2d 2d 2d 2d

Đã bị trộn:

49 45 4e 42 47 2d 2d 2d 2d 2d 20 54 4b 41 45 49 50 56 20 52 0a 2d 4d 2d 0d 2d 59 2d 45 2d 44 42 41 49 41 76 49 41 49 45 47 6b 39 68 69 6b 42 71 4e 67 41 46 53 45 41 41 30 


Với 10 bytes đầu ta tìm chỉ tìm được 1 phần quy luật:
`8, 6, 9, 5, 7, ...`
Tiếp tục thử với 10 bytes sau xem thế nào:


Và thế là ta đã có được quy luật:
`8, 6, 9, 5, 7, 3, 1, 4, 0, 2`

Các số này có nghĩa là vị trí chính xác của các bytes.
Giờ chỉ cần đưa tất cả về đúng vị trí thôi.

from Crypto.PublicKey import RSA 
from Crypto.Util.number import long_to_bytes, bytes_to_long

public = open("public", 'r').read().replace(" ", "")
public = RSA.import_key(bytes.fromhex(public))
n = public.n
e = public.e

private_jumb = open("private", 'r').read().split(' ')

private_jumb = [private_jumb[i:i+10] for i in range(0, len(private_jumb), 10)]
private_hex = []
qui_luat = [8, 6, 9, 5, 7, 3, 1, 4, 0, 2]
for i in private_jumb:
    for idx in qui_luat:
        private_hex.append(i[idx])

private = bytes.fromhex(''.join(private_hex)).decode()
private = RSA.import_key(private)
d = private.d

c = bytes_to_long(open('flag.txt.enc', 'rb').read())
print(long_to_bytes(pow(c, d, n)))

FLAG: `gigem{jumbl3d_r54_pr1v473_k3y_z93kd74lx}`

## Emoji group
Ta có source code:

from secrets import multiply, g, identity, inverse, valid
from random import getrandbits

def power(p,x):
    out = identity
    while x:
        if x & 1:
            out = multiply(out,p)
        p = multiply(p,p)
        x >>= 1
    return out

def encrypt(msg,e):
    generator = power(g,e)
    out = generator
    for c in msg:
        out += power(generator,ord(c))
    return out

def decrypt(ct,d):
    chars = [power(g,i) for i in range(256)]
    plaintext = ""
    pt = power(ct[0],d)
    if pt != g:
        raise Exception("Invalid ciphertext")
    for c in ct[1:]:
        pt = power(c,d)
        plaintext += chr(chars.index(pt))
    return plaintext

print("Give me a message to encrypt:")
msg = input()
e = 0
while not valid(e):
    e = getrandbits(32)
ct = encrypt(msg,e)
print(f"Your cipher text is:",ct)
d = inverse(e)
print(f"The original message was:",decrypt(ct,d))

with open("flag.txt","r") as flag:
    e = 0
    while not valid(e):
        e = getrandbits(32)
    print("The flag is:",encrypt(flag.read(),e))

Khi ta gửi đến server ta nhận được những thứ như sau:

Phần tử đầu tiên của ciphertext là `genarator = g**e`, nhận thấy với mỗi ký tự sẽ ứng với một emoji. Nó có vẻ giống như mã hóa casaer, mỗi ký tự sau khi được mã hóa được ánh xạ đến một emoji tương ứng.

Với `msg` mà ta gửi tới ta có thể biết được các ký tự đó ánh xạ như thế nào. Vì `encrypt(msg, e)`, `encrypt(msg, e)` có 2 `e` khác nhau nên ta không thể biết được `flag` được mã hóa như thế nào. Nhưng nếu chúng cùng `generation` thì dễ dàng lấy được FLAG.

Mình sẽ gửi tới server là lưu lại tất cả `generation` và ciphertext tương tương ứng với msg mà mình đã gửi. Nếu `generation` của flag_enc có trong những `generation` mà mình đã lưu thì chỉ cần mã hóa ngược lại để lấy FLAG.

**script:**

import string
from pwn import remote

characters = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~"

dict = {}
flag = ''
while 1:
    io = remote("localhost", 1337)
    io.recvuntil(b'Give me a message to encrypt:\n')
    io.sendline(characters)
    io.recvuntil(b'Your cipher text is: ')
    c = io.recvuntil(b'\n', drop=True).decode()
    dict[c[0]] = c[1:]
    print(c[0])
    
    io.recvuntil(b'The flag is: ')
    flag_enc = io.recvuntil(b'\n', drop=True).decode()
    print(flag_enc)
    
    if flag_enc[0] in dict:
        for i in flag_enc[1:]:
            # print(i)
            flag += characters[dict[flag_enc[0]].index(i)]
        print(flag)
        break   


FLAG: `gigem{h0p3_y0u_d1dn7_s0lv3_by_h4nd}`

## PCG

Ta có source code như sau:

from secrets import randbelow
from Crypto.Util.number import getPrime
import sys

SIZE = 256
class PCG: # Polynomial Congruential Generator
    def __init__(self):
        self.m = getPrime(256)
        self.coeff = [randbelow(self.m-1) for _ in range(SIZE)]
        self.x = randbelow(self.m-1)
    def __call__(self):
        newx = 0
        for c in self.coeff:
            newx *= self.x
            newx += c
            newx %= self.m
        self.x = newx
        return self.x
    def printm(self):
        print(self.m)
        return
pcg = PCG()

print(pcg.m)
for i in range(SIZE*3):
    print(pcg())

sys.stdout.flush()
correct = True
for i in range(SIZE // 2):
    guess = int(input())
    if guess != pcg():
        correct = False

if correct:
    print(open('flag.txt','r').read())
else:
    print("you failed")
sys.stdout.flush()

Để lấy được flag ta cần predict được (256/2) giá trị tiếp theo của hàm `pcg` sau khi đã nhận được (256*3) giá trị từ hàm `pcg`.

Ta có:
$x_{i+1} = a_{0}*x_{i}^{255} + \dots + a_{254}*x_{i} ^ 1 + a_{255} \mod (m)$
Với `m` đã có, ta chỉ cần khôi phục lại hệ số và gen thêm các giá trị tiếp theo để lấy Flag thôi.

Gọi:
$A = \begin{bmatrix}
a_0 & a_1 & a_2 & a_3 & .. & a_{255} \\
\end{bmatrix}$

$B = \begin{bmatrix}
x_0^{255} & x_1^{255} & .. & x_{255}^{255} \\
... & ... & .. & ... \\
x_0 & x_1 & .. & x_{255} \\
1 & 1 & .. & 1 \\
\end{bmatrix}$

Ta có: $X_i*A = \begin{bmatrix}
x_0 & x_1 & x_2 & .. & x_{255} \\
\end{bmatrix}$ với $i \in N$
Giải nghiệm phương trình trên ta sẽ tìm được các hệ số. Và tiếp tục gen tiếp hàm `pcg()` và gửi đến server và nhận lại flag.

from pwn import remote
from sage.all import *

io = remote("localhost", 1337)
SIZE = 256
data = io.recvlines(SIZE*3 + 1)
X = list(map(int, data))
print(X)

m = X[0]  
X = X[1:]
print(len(X))
F = GF(m)
A = Matrix(F,[[x**(SIZE-1-i) for i in range(SIZE)] for x in X[:-1]])
y = vector(F,X[1:])
arr = A.solve_right(y)
coeff = [int(x) for x in arr]

print(coeff)
class PCG: # Polynomial Congruential Generator
    def __init__(self):
        self.m = getPrime(256)
        self.coeff = [randbelow(self.m-1) for _ in range(SIZE)]
        self.x = randbelow(self.m-1)
    def __call__(self):
        newx = 0
        for c in self.coeff:
            newx *= self.x
            newx += c
            newx %= self.m
        self.x = newx
        return self.x
    def printm(self):
        print(self.m)
        return
pcg = PCG()
pcg.m = m

pcg.coeff = coeff
pcg.x = X[-1]
for i in range(SIZE // 2):
    io.sendline(str(pcg()).encode())
io.interactive()

FLAG: `gigem{p0lyn0m1al5_4r3_funny}`