# UIUCTF 2023 writeup

- Giải UIUCTF 2023 vừa rồi được tổ chức từ 7:00AM 1/7 -> 7:00AM 3/7, mình đã đánh cho team ``m1cr0$oft 0ff1c3`` và kết thúc giải ở vị trí thứ 22.


- Thật may vì giải lần này crypto tương đối dễ ở mức **beginner-easy** (theo mình tự đánh giá 😁), nên mình đã clear được hết các challs 😎.


- Dưới đây là writeup cho các challenge mà mình đã giải được.

## writeup available for:
### Crypto:
1. [Three-Time Pad](#Three-Time-Pad)
2. [At Home](#At-Home)
3. [Group Project](#Group-Project)
4. [Morphing Time](#Morphing-Time)
5. [Group Projection](#Group-Projection)
6. [crack_the_safe](#crack_the_safe)

## Three-Time Pad

>"We've been monitoring our adversaries' communication channels, but they encrypt their data with XOR one-time pads! However, we hear rumors that they're reusing the pads...
>
>Enclosed are three encrypted messages. Our mole overheard the plaintext of message 2. Given this information, can you break the enemy's encryption and get the plaintext of the other messages?"
>
>Author: Pomona

Attachments:
[files](https://github.com/tranminhprvt01/CTF-writeups/tree/main/UIUCTF/2023/crypto/three-time-pad/public)

Nhận xét:
- Đề cho ta 4 file gồm 3 file ciphertext và 1 file plaintext, kèm theo đó ở description ta đã biết được rằng p2 ⊕ key = c2 và key được **tái sử dụng** cho các p_i và c_i
- Vì thế ở bài này ta chỉ việc đơn giản recover key = p2 ⊕ c2, và từ key này để recover lại các p_i.

script:

from pwn import *
c1 = open("c1", 'rb').read()
c2 = open("c2", 'rb').read()
c3 = open("c3", 'rb').read()
p2 = open("p2", 'rb').read()

key = xor(c2, p2)

print(key)

m1 = xor(key, c1)
m3 = xor(key, c3)

print(m1)
print(m3)


-> flag: ``uiuctf{burn_3ach_k3y_aft3r_us1ng_1t}``

## At Home

> Mom said we had food at home
>
>Author: Anakin

Attachments:
* chall.py

from Crypto.Util.number import getRandomNBitInteger

flag = int.from_bytes(b"uiuctf{******************}", "big")

a = getRandomNBitInteger(256)
b = getRandomNBitInteger(256)
a_ = getRandomNBitInteger(256)
b_ = getRandomNBitInteger(256)

M = a * b - 1
e = a_ * M + a
d = b_ * M + b

n = (e * d - 1) // M

c = (flag * e) % n

print(f"{e = }")
print(f"{n = }")
print(f"{c = }")

* chall.txt

e = 359050389152821553416139581503505347057925208560451864426634100333116560422313639260283981496824920089789497818520105189684311823250795520058111763310428202654439351922361722731557743640799254622423104811120692862884666323623693713
n = 26866112476805004406608209986673337296216833710860089901238432952384811714684404001885354052039112340209557226256650661186843726925958125334974412111471244462419577294051744141817411512295364953687829707132828973068538495834511391553765427956458757286710053986810998890293154443240352924460801124219510584689
c = 67743374462448582107440168513687520434594529331821740737396116407928111043815084665002104196754020530469360539253323738935708414363005373458782041955450278954348306401542374309788938720659206881893349940765268153223129964864641817170395527170138553388816095842842667443210645457879043383345869

Nhận xét:
- Thoạt đầu nhìn vào bài, ta thấy rất nhiều biến cùng các phép tính, tuy nhiên thứ thực sự quan trọng trong bài này chỉ là dòng ``c = (flag * e) % n``

- Do flag được tính toán trên mod n, ta có thể tính lại flag bằng cách sau:
$flag ≡ c*e^{-1} (mod \ n)$

script:

from Crypto.Util.number import *

e = 359050389152821553416139581503505347057925208560451864426634100333116560422313639260283981496824920089789497818520105189684311823250795520058111763310428202654439351922361722731557743640799254622423104811120692862884666323623693713
n = 26866112476805004406608209986673337296216833710860089901238432952384811714684404001885354052039112340209557226256650661186843726925958125334974412111471244462419577294051744141817411512295364953687829707132828973068538495834511391553765427956458757286710053986810998890293154443240352924460801124219510584689
c = 67743374462448582107440168513687520434594529331821740737396116407928111043815084665002104196754020530469360539253323738935708414363005373458782041955450278954348306401542374309788938720659206881893349940765268153223129964864641817170395527170138553388816095842842667443210645457879043383345869

e_ = inverse(e, n)

m = (c*e_) % n

print(m)

print(long_to_bytes(m))


-> flag: `uiuctf{W3_hav3_R5A_@_h0m3}`

## Group Project

>In any good project, you split the work into smaller tasks...
>
>nc group.chal.uiuc.tf 1337
>
>Author: Anakin

Attachments:
* chall.py

from Crypto.Util.number import getPrime, long_to_bytes
from random import randint
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


with open("/flag", "rb") as f:
    flag = f.read().strip()

def main():
    print("[$] Did no one ever tell you to mind your own business??")

    g, p = 2, getPrime(1024)
    a = randint(2, p - 1)
    A = pow(g, a, p)
    print("[$] Public:")
    print(f"[$]     {g = }")
    print(f"[$]     {p = }")
    print(f"[$]     {A = }")

    try:
        k = int(input("[$] Choose k = "))
    except:
        print("[$] I said a number...")

    if k == 1 or k == p - 1 or k == (p - 1) // 2:
        print("[$] I'm not that dumb...")

    Ak = pow(A, k, p)
    b = randint(2, p - 1) 
    B = pow(g, b, p)
    Bk = pow(B, k, p)
    S = pow(Bk, a, p)

    key = hashlib.md5(long_to_bytes(S)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    c = int.from_bytes(cipher.encrypt(pad(flag, 16)), "big")

    print("[$] Ciphertext using shared 'secret' ;)")
    print(f"[$]     {c = }")


if __name__ == "__main__":
    main()

Nhận xét:
- Nhìn sơ, ta có thể thấy rằng bài này tương đối giống với thuật toán trao đổi khóa Diffie-Hellman.
- Và bình thường ở các bài dạng này, ta cần kiểm soát được giá trị shared_secret để có thể decrypt ciphertext.
- Nhìn vào code trên, ta được cho phép biết các tham số g, p, A và được yêu cầu gửi tham số k. Để rồi shared_secret sẽ được tính bằng:
$$
a = randint(2, p-1) \\
b = randint(2, p-1) \\
B ≡ g^b \ (mod \ p) \\
Bk ≡ B^k \ (mod \ p) \\
S ≡ Bk^a \ (mod \ p) \\
$$
- Và ở bài này, trong server có 1 đoạn check k như sau

 if k == 1 or k == p - 1 or k == (p - 1) // 2:
        print("[$] I'm not that dumb...")

- Tuy nhiên, server lại không thoát ra nếu ta nhập k là các giá trị trên, mà vẫn tiếp tục encrypt message và trả cho chúng ta giá trị c.
- Ở đây, mình giả sử server đã chặn các giá trị như dòng trên, thì ta vẫn có thể gửi k = 0 và từ đó Bk = 1 và S cũng sẽ là 1.
- Và do đã kiểm soát được giá trị S, ta chỉ việc dùng S đó để lấy key và decrypt c.

script:

from pwn import *
from Crypto.Util.number import *
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


host, port = "group.chal.uiuc.tf", 1337

r = remote(host, port)



r.recvuntil(b"[$] Did no one ever tell you to mind your own business??\n")

r.recvuntil(b"[$] Public:\n")




g = int(r.recvline().rstrip()[12:])
p = int(r.recvline().rstrip()[12:])
A = int(r.recvline().rstrip()[12:])

r.recvuntil(b"[$] Choose k = ")
r.sendline(str((0)))

r.recvuntil(b"[$] Ciphertext using shared 'secret' ;)\n")

S = 1

c = int(r.recvline().rstrip()[12:])

key = hashlib.md5(long_to_bytes(S)).digest()
cipher = AES.new(key, AES.MODE_ECB)

flag = cipher.decrypt(long_to_bytes(c))

print(flag)

r.interactive()


-> flag: `uiuctf{brut3f0rc3_a1n't_s0_b4d_aft3r_all!!11!!}`

## Morphing Time

>The all revealing Oracle may be revealing a little too much...
>
>nc morphing.chal.uiuc.tf 1337
>
>Author: Anakin

Attachments:
* chall.py

#!/usr/bin/env python3
from Crypto.Util.number import getPrime
from random import randint

with open("/flag", "rb") as f:
    flag = int.from_bytes(f.read().strip(), "big")


def setup():
    # Get group prime + generator
    p = getPrime(512)
    g = 2

    return g, p


def key(g, p):
    # generate key info
    a = randint(2, p - 1)
    A = pow(g, a, p)

    return a, A


def encrypt_setup(p, g, A):
    def encrypt(m):
        k = randint(2, p - 1)
        c1 = pow(g, k, p)
        c2 = pow(A, k, p)
        c2 = (m * c2) % p

        return c1, c2

    return encrypt


def decrypt_setup(a, p):
    def decrypt(c1, c2):
        m = pow(c1, a, p)
        m = pow(m, -1, p)
        m = (c2 * m) % p

        return m

    return decrypt


def main():
    print("[$] Welcome to Morphing Time")

    g, p = 2, getPrime(512)
    a = randint(2, p - 1)
    A = pow(g, a, p)
    decrypt = decrypt_setup(a, p)
    encrypt = encrypt_setup(p, g, A)
    print("[$] Public:")
    print(f"[$]     {g = }")
    print(f"[$]     {p = }")
    print(f"[$]     {A = }")

    c1, c2 = encrypt(flag)
    print("[$] Eavesdropped Message:")
    print(f"[$]     {c1 = }")
    print(f"[$]     {c2 = }")

    print("[$] Give A Ciphertext (c1_, c2_) to the Oracle:")
    try:
        c1_ = input("[$]     c1_ = ")
        c1_ = int(c1_)
        assert 1 < c1_ < p - 1

        c2_ = input("[$]     c2_ = ")
        c2_ = int(c2_)
        assert 1 < c2_ < p - 1
    except:
        print("!! You've Lost Your Chance !!")
        exit(1)

    print("[$] Decryption of You-Know-What:")
    m = decrypt((c1 * c1_) % p, (c2 * c2_) % p)
    print(f"[$]     {m = }")

    # !! NOTE !!
    # Convert your final result to plaintext using
    # long_to_bytes

    exit(0)


if __name__ == "__main__":
    main()

Nhận xét:
- Nhìn sơ, ta thấy bài này có vẻ có khá nhiều toán 😅
- Tóm tắt sơ qua flow của bài:
+ Đề cho ta 3 tham số public g, p, A trong đó $A = g^a \ (mod \ p)$
+ Tiếp theo, ta được biết giá trị c1, c2 = ecnrypt(flag)
+ Nói sơ về hàm encrypt(m):
$$
k = randint(2, p-1) \\
c1 ≡ g^k \ (mod \ p) \\
c2 ≡ m * A^k \ (mod \ p)
$$
+ Sau đó, ta được yêu cầu gửi tham số c1_, c2_ thỏa điều kiện (1 < c1_, c2_ < p-1)
+ Khi này, server sẽ cho ta biết giá trị decrypt của (c1\*c1_ %p, c2\*c2_ %p)
+ Nói sơ về hàm decrypt(c1, c2):
$$
m ≡ c1^a \ (mod \ p) \\
m ≡ m^{-1} \ (mod \ p) ≡ c1^{-a} \ (mod \ p) \\
m ≡ c2 * m \ (mod \ p) ≡ c2 * c1^{-a} \ (mod \ p) \\
$$
+ Mối liên hệ giữa encrypt và decrypt, như ta có thể thấy rằng việc tính toán được thực hiện trên mod p, nên ngay từ dòng $c2 ≡ m * A^k \ (mod \ p)$ ta đã biết rằng $m ≡ c2 * A^{-k} \ (mod \ p) ≡ c2 * g^{-ak} \ (mod \ p) ≡ c2 * c1^{-a} \ (mod \ p)$
+ Như vậy, nếu ta có thể gọi decrypt(c1, c2) thì m thu được của chúng ta sẽ là flag.
+ Tuy nhiên, đời không như mơ khi bài này đã chặn việc chúng ta gửi c1_ = 1, c2_ = 1 hoặc c1_ = p, c2_ = p.
+ Vì thế, parameter injection không thể hoạt động trong bài này. Mà thay vào đó, ta sẽ cần sử dụng toán để giải quyết.
- Hãy giả sử rằng ta gửi vào server giá trị c1_ = 2, c2_ = 2, vậy m mà ta thu được là cái gì.
$$
m ≡ ({2*c1})^a \ (mod \ p) \\
m ≡ m^{-1} \ (mod \ p) ≡ 2^{-a} * c1^{-a} \ (mod \ p) ≡ A^{-1} * c1^{-a} \ (mod \ p) \ \text{ Do thật vô tình g ở trong bài này luôn bằng 2}\\
m ≡ 2*c2 * m \ (mod \ p) ≡ 2*c2 * A^{-1} * c1^{-a} \ (mod \ p) \\
$$
- Do flag ban đầu chỉ thực sự cần giá trị $c2 * c1^{-a} \ (mod \ p)$ nên sau khi thu được m ta có thể tính lại flag ban đầu bằng
$$
flag ≡ m*2^{-1}*A \ (mod \ p)
$$

script:

from pwn import *

host, port = "morphing.chal.uiuc.tf", 1337

r = remote(host, port)

r.recvuntil(b"[$] Public:\n")

g = int(r.recvline().rstrip()[12:])
p = int(r.recvline().rstrip()[12:])
A = int(r.recvline().rstrip()[12:])

r.recvuntil(b"[$] Eavesdropped Message:\n")
c1 = int(r.recvline().rstrip()[13:])
c2 = int(r.recvline().rstrip()[13:])



r.recvuntil(b"[$] Give A Ciphertext (c1_, c2_) to the Oracle:\n")

c1_ = 2
c2_ = 2


from Crypto.Util.number import *

r.sendline(str(c1_))
r.sendline(str(c2_))

r.recvuntil(b"[$] Decryption of You-Know-What:\n")

m = int(r.recvline().rstrip()[12:])



print(m)

flag = m*inverse(2, p) * A % p

print(flag)
print(long_to_bytes(flag))

r.interactive()


-> flag: `uiuctf{h0m0m0rpi5sms_ar3_v3ry_fun!!11!!11!!}`

## Group Projection

>I gave you an easier project last time. This one is sure to break your grade!
>
>nc group-projection.chal.uiuc.tf 1337
>
>Author: Anakin

Attachments:
* chall.py

from Crypto.Util.number import getPrime, long_to_bytes
from random import randint
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


with open("/flag", "rb") as f:
    flag = f.read().strip()

def main():
    print("[$] Did no one ever tell you to mind your own business??")

    g, p = 2, getPrime(1024)
    a = randint(2, p - 1)
    A = pow(g, a, p)
    print("[$] Public:")
    print(f"[$]     {g = }")
    print(f"[$]     {p = }")
    print(f"[$]     {A = }")

    try:
        k = int(input("[$] Choose k = "))
    except:
        print("[$] I said a number...")
        return
    if k == 1 or k == p - 1 or k == (p - 1) // 2 or k <= 0 or k >= p:
        print("[$] I'm not that dumb...")
        return

    Ak = pow(A, k, p)
    b = randint(2, p - 1)
    B = pow(g, b, p)
    Bk = pow(B, k, p)
    S = pow(Bk, a, p)

    key = hashlib.md5(long_to_bytes(S)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    c = int.from_bytes(cipher.encrypt(pad(flag, 16)), "big")

    print("[$] Ciphertext using shared 'secret' ;)")
    print(f"[$]     {c = }")
    return

if __name__ == "__main__":
    main()

Nhận xét:
- Bài này là phiên bản nâng cấp của bài Group Project ở trên khi lần này giới hạn của k đã không còn rộng như trước và server sẽ out ra khi ta nhập k không thỏa mãn

if k == 1 or k == p - 1 or k == (p - 1) // 2 or k <= 0 or k >= p:
        print("[$] I'm not that dumb...")
        return

- Ở bài này, nhìn vào giá trị `k = (p-1)//2` (sao nhìn cái format này quen quen nhở 🤔).
- Nếu bạn đã luyện tập trên [CryptoHack](https://cryptohack.org), bạn sẽ thấy được rằng đây là format của Legendre Symbol, tuy nhiên Legendre Symbol sẽ không giúp ta giải quyết bài toán này =)))
- Mà thay vào đó, ta nhìn nhận lại bài toán theo hướng khác
$$
Bk ≡ B^k \ (mod \ p) ≡ 2^{bk} \ (mod \ p) \\
S ≡ Bk^{a} \ (mod \ p) ≡ 2^{abk} \ (mod \ p)
$$
- Nếu ta để ý tại dòng $Bk ≡ 2^{bk} \ (mod \ p)$ giả sử rằng ta gửi `k = (p-1)//2` và b là số chẵn, khi này $Bk ≡ 2^{bk} \ (mod \ p) ≡ 2^{(p-1)*x} \ (mod \ p)$
- Mà dựa vào định lý fermat nhỏ, ta có thể biết ngay được rằng giá trị Bk ở trên luôn là 1.
- Áp dụng mindset tương tự, bài toán lần này sẽ là giải quyết với $S ≡ 2^{abk} \ (mod \ p)$, giả sử rằng trong lần connect tới server đó a, b cùng là số chẵn như vậy nếu ta gửi `k = (p-1)//4` ta sẽ thu được $S ≡ 2^{abk} \ (mod \ p) ≡ 2^{(p-1)*x} \ (mod \ p) ≡ 1 \ (mod \ p)$
- Như vậy, bài toán đã được giải quyết với một chút kĩ năng và nhiều chút nhân phẩm 😆.

Script:

from pwn import *
from Crypto.Util.number import *
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


host, port = "group-projection.chal.uiuc.tf", 1337

cnt = 0
while True:
    print(f"Attempt {cnt}")
    r = remote(host, port)



    r.recvuntil(b"[$] Did no one ever tell you to mind your own business??\n")

    r.recvuntil(b"[$] Public:\n")




    g = int(r.recvline().rstrip()[12:])
    p = int(r.recvline().rstrip()[12:])
    A = int(r.recvline().rstrip()[12:])

    r.recvuntil(b"[$] Choose k = ")
    r.sendline(str((p-1)//4))

    r.recvuntil(b"[$] Ciphertext using shared 'secret' ;)\n")

    S = 1

    c = int(r.recvline().rstrip()[12:])

    key = hashlib.md5(long_to_bytes(S)).digest()
    cipher = AES.new(key, AES.MODE_ECB)

    flag = cipher.decrypt(long_to_bytes(c))

    if b"uiuctf{" in flag:
        print(flag)
        break
        r.interactive()
    print("~"*40)
    cnt+=1


-> flag: `uiuctf{brut3f0rc3_w0rk3d_b3f0r3_but_n0t_n0w!!11!!!}`

## crack_the_safe

>"I found this safe, but something about it seems a bit off - can you crack it?"
>
>Author: Anakin

Attachments:
* chall.py

from Crypto.Cipher import AES
from secret import key, FLAG

p = 4170887899225220949299992515778389605737976266979828742347
ct = bytes.fromhex("ae7d2e82a804a5a2dcbc5d5622c94b3e14f8c5a752a51326e42cda6d8efa4696")

def crack_safe(key):
    return pow(7, int.from_bytes(key, 'big'), p) == 0x49545b7d5204bd639e299bc265ca987fb4b949c461b33759

assert crack_safe(key) and AES.new(key,AES.MODE_ECB).decrypt(ct) == FLAG

Nhận xét:
- Một challenge có code rất ngắn tuy nhiên lại có mức độ khó nhất so với các challenge trên.
- Trong bài này ta cần tính được giá trị key để decrypt ct, và key chỉ xuất hiện trong hàm crack_safe.
- Qua hàm crack_safe, ta đã có thể thấy được rằng đây là 1 bài toán dạng DLP (Discrete Logarithm Problem)
- Kinh nghiệm của mình trong bài toán dạng này là đầu tiên ta sẽ check order của group được sử dụng để tính toán (nói 1 cách khác ta cần check factor của p-1 do p là số nguyên tố)


- Mình sử dụng factordb để tách factor từ p-1 và thấy được rằng trong các factor của nó có xuất hiện 1 factor cuối 25 chữ số ~ 83 bits.
- Độ phức tạp tốt nhất của thuật toán để giải quyết bài toán DLP là khoảng $O(\sqrt{p})$. Vì thế ngoại trừ factor cuối cùng 25 chữ số lấy căn ~ 12 chữ số là khá to để có giải quyết DLP với factor này, còn các factor còn lại khá nhỏ và có thể giải quyết dễ dàng. Nên ta có thể áp dụng giải thuật [Pohlig-Hellman](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm) cho bài toán này.
- Ý tưởng cơ bản của Pohlig-Hellman là từ việc giải bài toán DLP trên 1 group, ta sẽ giải quyết bài toán DLP trên các subgroup và sau đó sử dụng [CRT](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) để kết hợp các giá trị mũ trong các bài toán con lại và trả về giá trị mũ đúng trong bài toán cha.
- Nếu ta áp dụng ý tưởng Pohlig-Hellman vào bài toán này, ta sẽ xem subgroup của chúng ta không có factor cuối, và đương nhiên order của subgroup này sẽ là tích các factor trừ factor cuối.
- Khi này, khi mà giải quyết bài toán DLP trên subgroup của chúng ta, ta sẽ thu được x ~ 109 bits
- Và sự thiếu hụt bits này là do ta cần giải quyết thêm bài toán DLP với subgroup là factor cuối sau đó kết hợp lại bằng CRT nhưng việc này là không thể (hoặc [có thể????](https://hackmd.io/5U3davrQSU-sJRC3E9t44w?view#Another-Approach) 😳).
- Vậy hiện tại ta đã có 1 phương trình $key ≡ x1 \ (mod \ \text{subgroup1_order})$
- Nhưng quan sát lại challenge, ta thấy key được sử dụng trong encrypt AES => key phải có 16 bytes ~ 128 bits
- Do x ta thu được đã ~ 109 bits tương đối nhiều nên ta sẽ thử bruteforce k trong phương trình $key ≡ x1 \ (mod \ \text{subgroup1_order}) => key = x1+k*\text{subgroup1_order}$ cho đến khi nào tính được key thỏa mãn hàm crack_safe thì ta đã thành công tìm lại key

Script:

from Crypto.Cipher import AES
from Crypto.Util.number import *

p = 4170887899225220949299992515778389605737976266979828742347
c = 0x49545b7d5204bd639e299bc265ca987fb4b949c461b33759
g = 7
ct = bytes.fromhex("ae7d2e82a804a5a2dcbc5d5622c94b3e14f8c5a752a51326e42cda6d8efa4696")


primes = [2, 19, 151, 577, 67061, 18279232319, 111543376699, 9213409941746658353293481]

exp = [1, 1, 1, 1, 1, 1, 1, 1]
print(primes)
print(exp)

order = (p-1) // primes[-1]


from sympy.ntheory import discrete_log

g_ = pow(g, primes[-1], p)
c_ = pow(c, primes[-1], p)

print(g)
print(c)

x = discrete_log(p, c_, g_)

print(x, x.bit_length())
print(order)

"""
key only 16*8 = 128 bits and we already have 109 bits
just brute force res

key = x mod (order) => key = x+k*order
"""

k=0
while True:
	candidate = x+k*order
	if k%10000 == 0: 
		print("current variable")
		print("k", k)
		print("candidate", candidate)
		print("~"*40)
	if pow(g, candidate, p) == c:
		print("Found key", candidate)
		print("k", k)
		key = candidate
		break
	k+=1	


print(key)
key = long_to_bytes(key)

flag = AES.new(key,AES.MODE_ECB).decrypt(ct)
print(flag)


- Như vậy sau khi bruteforce k, ta đã thành công recover key và sử dụng key đó để decrypt ct.

-> flag: `uiuctf{Dl0g_w/__UnS4F3__pR1Me5_}`

### Another Approach:

- Well, với việc mình đề cập rằng ta có thể giải quyết bài toán DLP với factor 25 chữ số kia là không thể. Trên thực tế, sau giải mình có xem wu của người khác và biết đến sự tồn tại của 1 cái tool có tên là **cado-nfs**.
- Mình không thể hiểu được hết bản chất của cado-nfs, tuy nhiên mình biết sơ sơ về cách sử dụng nó.
- Vì thế ở phần này mình sẽ viết thiên hướng sharing knowledge hơn.
- Nói sơ qua về [cách hoạt động](https://crypto.stackexchange.com/questions/74867/how-do-i-interpret-the-cado-nfs-output-for-discrete-logarithm-calculation-in-gf) của cado-nfs.
- Đại loại rằng, sau khi down tool, ta chạy file cado-nfs.py với các tham số ell, target, modulus (ell tượng trưng cho factor lớn mà không thể giải quyết với các thuật toán DLP thường, hoặc có thể hiểu là order của subgroup còn lại mà ta chưa giải quyết; target là 1 giá trị chúng ta đưa vào), và cado-nfs sẽ trả cho ta giá trị $log_{base}(target)$ (có thể bạn sẽ thắc mắc base này ở đâu nhưng bạn chỉ cần hiểu đơn giản rằng base này có thể là bất cứ giá trị nào).
- Nói 1 cách dễ hiểu hơn, đầu tiên mình sẽ giả sử bài toán DLP chúng ta cần giải có dạng.
$g^x ≡ h \ (mod \ p)$
- Và chúng ta tới hiện tại đã xác định với giá trị p đã cho sẽ chia thành 2 subgroup, với subgroup1 là tích các factor ngoại trừ factor cuối và subgroup2 là factor cuối. Cùng lúc đó như đã tính toán ở trên ta đã có 1 phương trình:
$key ≡ x1 \ (mod \ \text{subgroup1_order})$

- Khi này ta sẽ sử dụng cado-nfs để tìm x2 trong phương trình: $key ≡ x2 \ (mod \ \text{subgroup2_order})$

- Việc này có thể được thực hiện bằng cách cho tham số ell = factor cuối, $target ≡ h^{\text{subgroup1_order}} \ (mod \ p)$ và modulus = p.
- Khi này, cado-nfs sẽ cho ta biết giá trị log(h'). Tương tự, ta sẽ xài cado-nfs để tính giá trị log(g').
- Khi này nhắc lại kiến thức về tính chất của logarit, ta có $\frac{log(h')}{log(g')} = x2$ và vì phép chia xét trong group là phép nhân nghịch đảo nên ta có $x2 ≡ log(h') * log(g')^{-1} \ (mod \ ell)$, như vậy ta hoàn toàn có thể tính được x2 xét trên mod subgroup2_order
- Tức là ta đã thành công thu được 2 phương trình:
$$
key ≡ x1 \ (mod \ \text{subgroup1_order})\\
key ≡ x2 \ (mod \ \text{subgroup2_order})
$$
- Công đoạn còn lại, ta chỉ cần xài crt để combine 2 phương trình trên lại và win 😎.

Script:

from Crypto.Cipher import AES
from Crypto.Util.number import *
from sympy.ntheory import discrete_log
from sympy.ntheory.modular import crt


p = 4170887899225220949299992515778389605737976266979828742347
c = 0x49545b7d5204bd639e299bc265ca987fb4b949c461b33759
g = 7
ct = bytes.fromhex("ae7d2e82a804a5a2dcbc5d5622c94b3e14f8c5a752a51326e42cda6d8efa4696")



primes = [2, 19, 151, 577, 67061, 18279232319, 111543376699, 9213409941746658353293481]

exp = [1, 1, 1, 1, 1, 1, 1, 1]

order1 = (p-1) // primes[-1]
order2 = (p-1) // order1

g1 = pow(g, order2, p)
c1 = pow(c, order2, p)

print("g1", g1)
print("c1", c1)

x1 = discrete_log(p, c1, g1)


print(x1, x1.bit_length())


print("~"*40)
print("this is ell", order2)

g2 = pow(g, order1, p)
c2 = pow(c, order1, p)

print("g2", g1)
print("c2", c1)

#using cado-nfs
log_c = 1607529382666405025125600
log_g = 8483029440103488262728827

x2 = log_c * inverse(log_g, order2) % order2
print(x2, x2.bit_length())
print("~"*40)

#now we use crt to recover key

res = crt([order1, order2], [x1, x2])
key = res[0]

print(key)
key = long_to_bytes(key)

flag = AES.new(key,AES.MODE_ECB).decrypt(ct)
print(flag)


- Wow, chúng ta đã mở khóa 1 thành tựu mới cho ngày hôm nay 🤯

- Sau một hồi nói lan man, mình nhận ra mình chưa đưa các bạn [link tool](https://c.ur4ndom.dev/cado-nfs.git.tar.gz) =)))

## Kết luận
- Ở trên là danh sách 6 bài mảng crypto mình solve được trong giải UIUCTF 2023.
- Mọi thắc mắc của các bạn xin vui lòng liên hệ với mình qua discord: ``tranminhprvt01#7535``
- Cuối cùng, cảm ơn các bạn đã đọc. Have a good day! 🥰