# BITSCTF2025
## Baby Crypto

Connect at : **nc chals.bitskrieg.in 7000**

Ở đây, challenge không cho ta source code nên ta cũng chỉ có thể kết nối netcat xem nó cho ta cái gì.

Server trả về cho ta một cặp khóa công khai $(N, e)$ và Ciphertext, cùng với đó là một hàm giải mã Ciphertext.

Tất nhiên là khi nhìn vào đó thì ta sẽ nghĩ ngay đến việc chỉ cần quăng cái Ciphertext đề cho vào hàm giải mã là nó sẽ giải mã cho ta để lấy được Flag. Thế nhưng đây là kết quả khi ta làm điều đó :

Nó sẽ không hề giải mã Ciphertext của chúng ta. Điều đó sẽ có thể bị phá vỡ bằng cách tấn công **Decipher oracle**.

Nó có thể hiểu như là ta sẽ biến đổi một chút ở Ciphertext, có thể là nhân với một số nào đó. Khi này, server sẽ lầm tưởng rằng đó không phải là Ciphertext gốc nên sẽ giải mã ra một Plaintext khác.

Việc của chúng ta bây giờ là lấy Plaintext mới đó chia cho số mà ta vừa mới nhân ban nãy là đã có được Flag rồi =))

Code :

from Crypto.Util.number import *

n = 144340364993250854007978847312006646423533723277221509581526408686508070126529037428428272306944388831553157178310696833882009756821836638119725660640876169109045587137622881570080351241841262836399733034903350052753059642864615599553145860048479687627111711227232747542861246657620738469001376240053793222187
e = 65537
ct = 119637947199534313671247094142508486546567571210590476244252247603869862080209207741866150810935750441581262550398817567250940777105839519744545103353691802773631177845132642284088391423932501307241876818649014959325042906284818667857751818057214690286309749182381863774401871525369236551157833291411891638846
# lấy đại một giá trị r nào đó
r = 2

# lấy new_ct này đi giải mã
new_ct = (ct * pow(r, e, n)) % n
print(new_ct)

fake_plaintext = 39639837536156593072703000049994066086289431135207913625429785307924943603979635946981909260898213168370823268973219279443746657679296399190096606077830951260950823052936192667655676091351812437731066
print((long_to_bytes(fake_plaintext // r)).decode())

<details>
<summary> Flag</summary>
BITSCTF{r54_0r4acl3_h4s_g0t_t0_b3_0n3_0f_7h3_3as13st_crypt0_1n_my_0p1n10n_74b15203}
</details>

# LACTF2025
## crypto/big e

Source code :

from Crypto.Util.number import bytes_to_long, getPrime

flag = REDACTED

pt = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p*q

e_1 = getPrime(16)
e_2 = getPrime(16)


ct_1 = pow(pt, e_1, n)
ct_2 = pow(pt, e_2, n)
print("ct_1 = ", ct_1)
print("ct_2 = ", ct_2)

print("e_1 = ", e_1)
print("e_2 = ", e_2)

print("n = ", n)

# ct_1 =  7003427993343973209633604223157797389179484683813683779456722118278438552981580821629201099609635249903171901413187274301782131604125932440261436398792561279923201353644665062240232628983398769617870021735462687213315384230009597811708620803976743966567909514341685037497925118142192131350408768935124431331080433697691313467918865993755818981120044023483948250730200785386337033076398494691789842346973681951019033860698847693411061368646250415931744527789768875833220281187219666909459057523372182679170829387933194504283746668835390769531217602348382915358689492117524129757929202594190396696326156951763154356777
# ct_2 =  2995334251818636287120912468673386461522795145344535560487265325864722413686091982727438605788851631192187299910519824438553287094479216297828199976116043039048528458879462591368580247044838727287694258607151549844079706204392479194688578102781851646467977751150658542264776551648799517340378173131694653270749425410071080383488918100565955153958793977478719703463115004497213753735577027928062856483316183232075922059366731900291340025009516177568909257605255717594938087543899066756942042664781424833498278544829618874970165660669400140113047048269742309745649848573501494088032718459018143817236079173978684104782
# e_1 =  49043
# e_2 =  60737
# n =  9162219874876832806204248523866163938680921861751582550947065673035037752546476053774362284605943422397285024205866696280912237827227700515353007344062472274717294484810421409217463791112287997964358655519896402380272695026012981743782564008035342746214988154836484419372449523768063368280069515180570625408254410932129769708259508451185553774810385066789146531683973766796965747310893648672657945403825359068647151094841570404979930542270681833162424933411724266687320976217446032292107871449464575533610369244978941764470549091443086646932177141081314452355708815370388814214178980532690792441231698974328523197187

Nhìn qua Source code thì ta thấy được là Flag của chúng ta được mã hóa thành 2 Ciphertext bằng 2 cặp khóa công khai **(N, e)** khác nhau. (cùng $N$ khác $e$)

Ta có thể hoàn toàn giải mã được bằng cách sử dụng **thuật toán Euclid mở rộng (EGCD)**. Cách giải :
- Đầu tiên, ta tính $gcd(e_1, e_2)$, thường sẽ là $1$.
- Dựa vào lý thuyết, tồn tại 2 số $u, v$ sao cho :
$$
u.e_1 + v.e_2 = gcd(e_1, e_2) = 1
$$

- Biết rằng : $c_1 = m^{e_1} \Leftrightarrow (c_1)^{u} = (m^{e_1})^{u} \Leftrightarrow (c_1)^{u} = m^{{e_1}.{u}}$
> Tương tự : $c_2 = m^{e_2} \Leftrightarrow (c_2)^{v} = (m^{e_2})^{v} \Leftrightarrow (c_2)^{v} = m^{{e_2}.{v}}$

- Lấy $(c_1)^{u} \times (c_2)^{v}$ ta có :
$$
(c_1)^{u} \times (c_2)^{v} \Leftrightarrow m^{{e_1}.{u}} \times m^{{e_2}.{v}} = m^{{e_1}.{u} + {e_2}.{v}} = m^1 = m
$$

Như vậy, chỉ việc tìm ra được $u, v$ dựa trên thuật toán **Euclid mở rộng** là ta đã có được văn bản gốc $m$ mà chẳng cần phải cố gắng phân tích $N = p.q$.

Code :

from Crypto.Util.number import *
from sympy import *
import math

c1 = 
c2 = 
e1 =  
e2 =  
n = 

u, v, gcd = gcdex(e1, e2) # Tìm u,v
print(gcd, u, v)

u = -9136
v = 7377

flag = long_to_bytes((pow(c1, u, n) * pow(c2, v, n)) % n)
print(flag.decode())

<details>
<summary> Flag</summary>
lactf{b1g_3_but_sm4ll_d!!!_part2_since_i_trolled}
</details>

## crypto/Extremely Convenient Breaker

Connect at : **nc chall.lac.tf 31180**

Source code :

#!/usr/local/bin/python3

from Crypto.Cipher import AES
import os

key = os.urandom(16)
with open("flag.txt", "r") as f:
    flag = f.readline().strip()
cipher = AES.new(key, AES.MODE_ECB)

flag_enc = cipher.encrypt(flag.encode())
print("Here's the encrypted flag in hex: ")
print(flag_enc.hex())
print("Alright, lemme spin up my Extremely Convenient Breaker (trademark copyright all rights reserved). ")

while True:
    ecb = input("What ciphertext do you want me to break in an extremely convenient manner? Enter as hex: ")
    try:
        ecb = bytes.fromhex(ecb)
        if not len(ecb) == 64:
            print("Sorry, it's not *that* convenient. Make your ciphertext 64 bytes please. ")
        elif ecb == flag_enc:
            print("No, I'm not decrypting the flag. ")
        else:
            print(cipher.decrypt(ecb))
    except Exception:
        print("Uh something went wrong, please try again. ")

Nhìn vào Source code ta có thể thấy là FLAG của ta được mã hóa bằng **AES.MODE_ECB**, chế độ mã hóa rất là yếu của AES. Ở đây ta sẽ tương tác với Server như sau :

Server cho ta một Ciphertext và một hàm giải mã. Tất nhiên rồi, bạn nghĩ chỉ cần quăng cái Ciphertext vào hàm giải mã thì nó sẽ giải mã cho ta à??

Yeah, và tất nhiên là không rồi. Ý tưởng của bài này sẽ giống với ý tưởng của bài RSA ở giải BITSCTF ở trên, là ta sẽ thay đổi Ciphertext đi để khi quăng vào hàm giải mã nó sẽ giải cho chúng ta mà không nghi ngờ gì. Và khi đó ta nhận được một Plaintext giả. Việc còn lại là khôi phục về Plaintext gốc thôi.

Ở đây mình sẽ "chặt" khối Ciphertext ra làm 2 phần bằng nhau, sau đó sẽ Padding thêm byte bất kì vào 2 phần sao cho mỗi phần có đủ độ dài là 64 bytes (128 bytes hex) theo yêu cầu của đề. Rồi sau đó là giải mã 2 phần đó và ta sẽ có được Flag.

enc_flag = "lấy từ server"
a = enc_flag[0:64] + str(61) * 32
b = enc_flag[64:128] + str(61) * 32
print(a)
print(b)
#Có được a, b rồi thì giải mã thôi :>

<details>
<summary>Flag</summary>
lactf{seems_it_was_extremely_convenient_to_get_the_flag_too_heh}
</details>

## crypto/RSAaaS

Connect at : **nc chall.lac.tf 31176**

Source code :

#!/usr/local/bin/python3

from Crypto.Util.number import isPrime


def RSAaaS():
    try:
        print("Welcome to my RSA as a Service! ")
        print("Pass me two primes and I'll do the rest for you. ")
        print("Let's keep the primes at a 64 bit size, please. ")

        while True:
            p = input("Input p: ")
            q = input("Input q: ")
            try:
                p = int(p)
                q = int(q)
                assert isPrime(p)
                assert isPrime(q)
            except:
                print("Hm, looks like something's wrong with the primes you sent. ")
                print("Please try again. ")
                continue

            try:
                assert p != q
            except:
                print("You should probably make your primes different. ")
                continue

            try:
                assert (p > 2**63) and (p < 2**64)
                assert (q > 2**63) and (q < 2**64)
                break
            except:
                print("Please keep your primes in the requested size range. ")
                print("Please try again. ")
                continue

        n = p * q
        phi = (p - 1) * (q - 1)
        e = 65537
        d = pow(e, -1, phi)

        print("Alright! RSA is all set! ")
        while True:
            print("1. Encrypt 2. Decrypt 3. Exit ")
            choice = input("Pick an option: ")

            if choice == "1":
                msg = input("Input a message (as an int): ")
                try:
                    msg = int(msg)
                except:
                    print("Hm, looks like something's wrong with your message. ")
                    continue
                encrypted = pow(msg, e, n)
                print("Here's your ciphertext! ")
                print(encrypted)

            elif choice == "2":
                ct = input("Input a ciphertext (as an int): ")
                try:
                    ct = int(ct)
                except:
                    print("Hm, looks like something's wrong with your message. ")
                    continue
                decrypted = pow(ct, d, n)
                print("Here's your plaintext! ")
                print(decrypted)

            else:
                print("Thanks for using my service! ")
                print("Buh bye! ")
                break

    except Exception:
        print("Oh no! My service! Please don't give us a bad review! ")
        print("Here, have a complementary flag for your troubles. ")
        with open("flag.txt", "r") as f:
            print(f.read())


RSAaaS()

Nhìn vào source code thì ta sẽ gửi cho server 2 số nguyên tố $p, q$ dài **64 bits** để chúng tạo ra một hệ thống mã hóa RSA hoàn chỉnh (tất nhiên là không an toàn rồi).

Ở đây nếu muốn có được Flag thì hệ thống RSA này phải có sự cố nào đó thì mới trả Flag về cho ta. Và ta hoàn toàn có thể phá được nó.

Như ta đã biết thì nguyên lý của RSA là :
- Chọn 2 số nguyên tố lớn $p, q$ với $p \# q$, chọn hoàn toàn ngẫu nhiên.
- Tính $N = p.q$
- Tính hàm Euler $\phi(N) = N.(1-\frac{1}{p}).(1-\frac{1}{q})$
- Chọn một số tự nhiên $e$ sao cho $1 < e < \phi(N)$ và $gcd(e, \phi(N)) = 1$
- Tìm $d$ sao cho $e.d \equiv 1 \pmod{\phi(N)}$

Khi này ta có 2 cặp khóa bí mật và công khai :
- Khóa bí mật : $(N, d)$
- Khóa công khai : $(N, e)$

Ở đây $e = 65537$, còn $p, q$ là ta sẽ cho ngẫu nhiên. Bây giờ ta sẽ khai thác vào tính chất :
$$
gcd(e, \phi(N)) = 1
$$

Ta sẽ chọn $p, q$ sao cho $gcd(e, \phi(N)) \neq 1$, khi này $d$ sẽ không thể tính được và sẽ không thể giải mã Plaintext được. Cuối cùng là hệ thống RSA này sẽ sụp đổ.

import random
from sympy import isprime, gcd

e = 65537
while True:
    p = random.getrandbits(64) | 1
    if not isprime(p): continue
    q = random.getrandbits(64) | 1
    if not isprime(q) or p == q: continue
    if gcd(e, (p - 1) * (q - 1)) != 1:
        break

print(f"p = {p}")
print(f"q = {q}")

<details>
<summary>p, q</summary>
p = 17682932333998206323, q = 17638014904840959427
</details>

Khi này ta chỉ cần nhập 2 số này vào là xong.

<details>
<summary>Flag</summary>
lactf{actually_though_whens_the_last_time_someone_checked_for_that}
</details>

# EHAXCTF2025
## Dots & Dashes

Well, bài này cho ta một file âm thanh của mã morse. Đầu tiên mình sẽ down về rồi dùng tool để dịch thử mã này. Kết quả :

Đây là một chuỗi không có nghĩa, tuy nhiên ở phần mô tả của đề tác giả có cho mình một khóa là `kagi`. Điều đó làm mình nghĩ ngay đến **mật mã Vigenere**, còn không thì là **hệ mật khóa tự sinh.** Mình sẽ thử dùng tool để tra :

Cũng khá là hên khi mà nó đã cho ta được một chuỗi có nghĩa, giờ chỉ cần thêm dấu "_" và format flag `EHAX` vào là được.
<details>
<summary> Flag</summary>
EHAX{M0RS3_V1G3N3R3_0P3R4T10N}
</details>

# BroncoCTF
## Rahhh-SA

Trước khi thấy được như này thì ban tổ chức đã tạo ra một challenge cho tất cả mọi người là : **hãy tìm chỗ submit flag**. Vâng, các bạn không nghe nhầm đâu. Trang web ban đầu mình vào và đăng kí là `https://broncoctf.xyz/`. Lúc mà login acc thì nó báo là bạn bị cấm. Mình tưởng mình bị cấm thật :smile:

Nhưng bạn mình cũng bị thế, và nó phát hiện ra là đây chỉ là 1 challenge nhỏ của giải, mục đích là phải tìm ra trang web thật để submit flag. Ngồi quằn mãi tới lúc **8:05AM** thì ban tổ chức mới công bố domain mới. Kay!

Tuy nhiên thì họ cũng quăng cho mình một link drive chứa tất cả chall các mảng để cho ai rảnh thì ngồi làm trước.

Đó là câu chuyện khi mới bắt đầu giải này. Và bây giờ ta sẽ tập trung vào bài.

Khi nhìn vào dữ kiện mà đề cho thì ta sẽ thấy khá là bối rối : Một RSA mà ciphertext là số âm?? `p = -811`???, Modulo N thì bé và có khá nhiều Ciphertext.

Điều này cho mình một suy nghĩ là : Flag đã được encode sang mã ASCII rồi dùng cặp khóa **(N, e)** để mã hóa. Nhưng tại sao lại âm???

Khi ngồi mò chall trong link Drive thì mình có thấy được file Source code như sau :

import math

e = 65537

p = -811

q = 0#??????

n = p * q

phi_n = (p + 1) * (q + 1) 

# but first, a word from
# our sponsored function!
def extendedEuclideanAlgo(e, phi_n):
    A1, A2, A3 = 1, 0, phi_n # var "b"
    B1, B2, B3 = 0, 1, e # var "a

    while (True):
        if B3 == 0:
            return -1 
            # indicates no inverse!
        if B3 == 1:
            return B2 
            # B2: modular inverse

        Q = math.floor(A3 / B3)
        T1, T2, T3 = A1 - (Q * B1), A2 - (Q * B2), A3 - (Q * B3)
        A1, A2, A3 = B1, B2, B3
        B1, B2, B3 = T1, T2, T3

def encrypt(int, e, n):
    return pow(int, e, -n)

Vậy là Flag của chúng ta được mã hóa theo phương trình :
$$
ct = int^{e} \mod(-N)
$$

Chưa kể hàm $\phi(N)$ được cho bởi :
$$
\phi(N) = (p+1).(q+1)
$$

Vậy là mình đã có được cách mã hóa Plaintext và hàm $\phi(N)$. Việc còn lại là giải mã thôi :

e = 65537
n = 3429719
c = [-53102, -3390264, -2864697, -3111409, -2002688, -2864697, -1695722, -1957072, -1821648, -1268305, -3362005, -712024, -1957072, -1821648, -1268305, -732380, -2002688, -967579, -271768, -3390264, -712024, -1821648, -3069724, -732380, -892709, -271768, -732380, -2062187, -271768, -292609, -1599740, -732380, -1268305, -712024, -271768, -1957072, -1821648, -3418677, -732380, -2002688, -1821648, -3069724, -271768, -3390264, -1847282, -2267004, -3362005, -1764589, -293906, -1607693]
p = -811
q = n // p 

phi = p*q + p + q + 1
d = pow(e, -1, phi)

msg = ""
for i in range(len(c)):
    m = pow(c[i], d, n)
    msg += chr(m)  # Chuyển đổi mỗi số thành ký tự ASCII

print(msg)

<details>
<summary>Flag</summary>
bronco{m4th3m4t1c5_r34l1y_1s_qu1t3_m4g1c4l_raAhH!}
</details>

# KashiCTF 2025
## Lost Frequencies

Đề cho ta một chuỗi : `111 0000 10 111 1000 00 10 01 010 1011 11 111 010 000 0`
Khi sử dụng tool **[dCode](https://www.dcode.fr/cipher-identifier)** để xác định loại mã thì đó chính là mã Morse.

Decode chuỗi này và ta sẽ có được flag.
<details>
<summary> Flag</summary>
KashiCTF{OHNOBINARYMORSE}
</details>

## MMDLX

Challenge cho ta một file mã base64 dài tới `3.848.466` kí tự :smiley:. Mình đoán khá chắc là flag của chúng ta đã bị encode rất rất nhiều lần thì mới có thể cho ra được một file output nhiều bytes base64 tới vậy (chứ bình thường flag không thể nào dài tới mức đó được)

Khi dùng **[tools](https://www.base64decode.org)** để decode lại file đề cho thì ta có kết quả như sau :

Kết quả nhận được là một chuỗi kí tự không có nghĩa gì hết, và nếu tiếp tục decode chuỗi mới này thì cũng sẽ chẳng ra gì cả nên ta cần phải thay đổi hướng đi khác.

Ở phần mô tả của đề bài có đề cập tới `Romans`. Điều đó làm mình liên tưởng sự hiện diện của mã `Caesar Cipher` trong challenge này.

Bây giờ chúng ta chỉ có một file base64 đề cho, mà cái file này khi decode ra một chuỗi kí tự khá là xấu, nên mình nghĩ file base64 đề cho đã được mã hóa theo mã `Caesar`. Và bây giờ ta cần phải giải mã lại mật mã `Caesar` để có lại được file base64 nguyên bản.

Quy trình mã hóa có thể được tóm gọn ở sơ đồ này :
$$
Flag -> n\times b64encode() -> Caesar.encode -> MMDLX.txt
$$

Qua sơ đồ trên ta chỉ cần đảo ngược lại là xong. Vì mật mã `Caesar` có tất cả 26 trường hợp mã hóa nên ta có thể brute-force được.

Vấn đề ở chỗ file base64 ban đầu ta không thể biết nó đã được encode bao nhiêu lần cả. Mình để ý tên của đề bài là `MMDLX`. Đó là một chữ số La Mã có giá trị thập phân là `2560`. Mình đoán đó có thể là số lần encode của flag nên cũng sẽ thử luôn.

import base64
with open("MMDLX.txt", "r", encoding="utf-8") as file:
    enc = file.read().strip()

for shift in range(26):
    Caesar_dec_text = ""
    for char in enc:
        if char.isalpha():
            shift_amount = shift % 26
            if char.isupper():
                new_char = chr(((ord(char) - ord('A') - shift_amount) % 26) + ord('A'))
            else:
                new_char = chr(((ord(char) - ord('a') - shift_amount) % 26) + ord('a'))
            Caesar_dec_text += new_char
        else:
            Caesar_dec_text += char
   
    for _ in range(2560):
        try:
            temp_decoded = base64.b64decode(Caesar_dec_text).decode(errors="ignore")
            if not temp_decoded.strip():
                break  
            Caesar_dec_text = temp_decoded
        except Exception:
            break  

    if "KashiCTF{" in Caesar_dec_text:
        print(Caesar_dec_text)
        print("Shift:",shift)
        break

<details>
<summary> Flag</summary>
KashiCTF{w31rd_numb3r5_4nd_c1ph3r5}
</details>

# ACECTF2025
## Super Secure Encryption

Source code :

from Crypto.Cipher import AES
from Crypto.Util import Counter
import os

k = os.urandom(16) # Is it too short?

def encrypt(plaintext):
    cipher = AES.new(k, AES.MODE_CTR, counter=Counter.new(128)) # I was told, CTR can't be broken!
    ciphertext = cipher.encrypt(plaintext)
    return ciphertext.hex()

msg = b'This is just a test message and can totally be ignored.' # Just checking functionality
encrypted_msg = encrypt(msg)

with open('flag.txt', 'r') as f:
    flag = f.readline().strip().encode()

encrypted_flag = encrypt(flag)

with open('msg.txt', 'w+') as o:
    o.write(f"{encrypted_msg}\n")
    o.write(f"{encrypted_flag}")
    
'''output : 
#encrypted_msg : d71f4a2fd1f9362c21ad33c7735251d0a671185a1b90ecba27713d350611eb8179ec67ca7052aa8bad60466b83041e6c02dbfee738c2a3
#encrypted_flag : c234661fa5d63e627bef28823d052e95f65d59491580edfa1927364a5017be9445fa39986859a3'''

# PWNME
## Easy Diffy

Source code :

from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
from hashlib import sha256

import os

# generating strong parameters

flag = b"REDACTED" 

p = getPrime(1536)
g = p-1

a = getPrime(1536)
b = getPrime(1536)

A = pow(g, a, p)
B = pow(g, b, p)

assert pow(A, b, p) == pow(B, a, p)

C = pow(B, a, p)

# Encrypting my message

key = long_to_bytes(C)
key = sha256(key).digest()[:16]

cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(flag, AES.block_size))

print(f"{p = }")
print(f"{g = }")
print("ciphertext =", ciphertext.hex())

'''output:
p = 1740527743356518530873219004517954317742405916450945010211514630307030225825627940655848700898186119703288416676610512180281414181211686282526701502342109420226095690170506537523420657033019751819646839624557146950127906808859045989204720555752289247833349649020285507405445896768256093961814925065500513967524214087124440421275882981975756344900858314408284866222751684730112931487043308502610244878601557822285922054548064505819094588752116864763643689272130951
g = 1740527743356518530873219004517954317742405916450945010211514630307030225825627940655848700898186119703288416676610512180281414181211686282526701502342109420226095690170506537523420657033019751819646839624557146950127906808859045989204720555752289247833349649020285507405445896768256093961814925065500513967524214087124440421275882981975756344900858314408284866222751684730112931487043308502610244878601557822285922054548064505819094588752116864763643689272130950
ciphertext = f2803af955eebc0b24cf872f3c9e3c1fdd072c6da1202fe3c7250fd1058c0bc810b052cf99ebfe424ce82dc31a3ba94f
'''

Ở đây challenge sẽ nói về thuật toán trao đổi khóa Diffe-Hellman. Sau khi có được khóa bí mật chung :
$$
K_{A} \equiv {C_{B}}^{a} \pmod p \equiv {[g^{b} \pmod p]}^{a} \equiv g^{a\times b} \pmod p
$$
Hoặc :
$$
K_{B} \equiv {C_{A}}^{b} \pmod p \equiv {[g^{a} \pmod p]}^{b} \equiv g^{a\times b} \pmod p
$$

Thì ta sẽ đem khóa đó đi băm qua hàm $SHA256$ và sử dụng giá trị băm đó để làm khóa cho **AES_ECB** mã hóa Flag của ta.

Bây giờ đề cho hai giá trị $p,g$ thì ta phải làm cách nào đó để có thể suy ra được khóa mà giải mã AES.

Ở đây $g$ được cho bởi $g=p-1$, điều đó có thể gây ra một lỗ hỏng khá lớn.

Ta biết được rằng trong thuật toán trao đổi khóa Diffie-Hellman thì $p$ ở đây sẽ là số nguyên tố bất kì, $g$ là phần tử sinh trong Modulo $p$. Từ $g$, ta sẽ tìm ra nhiều phần tử khác trong Modulo $p$. Các phần tử đó tập hợp lại với nhau thành nhóm **Cyclic**.

Quay trở lại với challenge, đầu tiên ta cần phải đi tính giá trị công khai để trao đổi là:
$$
\begin{cases}
C_A \equiv g^a \pmod{p}\\
C_B \equiv g^b \pmod{p}
\end{cases}
$$

Để dễ giải thích thì mình sẽ chọn :
$$
C_A \equiv g^a \pmod{p}
$$
Ta sẽ gửi giá trị này cho đối phương, rồi sau đó, họ sẽ dùng khóa bí mật $b$ của mình để tính giá trị khóa bí mật chung :
$$
K \equiv C_A^b \pmod{p} \equiv (g^a)^b \pmod{p} \equiv g^{ab}\pmod{p}
$$
Có $g=p-1$, thay vào ta được :
$$
K \equiv (p-1)^{ab} \pmod{p}
$$

Tới đây mình sẽ chỉ ra vấn đề trong cách chọn $g=p-1$. Ta biết được rằng :
$$
p \mod(p)=0
$$

$$
\Leftrightarrow p\equiv0\mod(p)
$$

$$
\Leftrightarrow p-1\equiv-1\mod(p)
$$

$$
\Leftrightarrow (p-1)^x\equiv(-1)^x\mod(p)
$$

$$
\Leftrightarrow g^x\equiv(-1)^x\mod(p)
$$
Tới đây sẽ có hai trường hợp xảy ra :
$$
\begin{cases}
g^x\equiv1\mod(p) \text{, nếu x = 2k} \\
g^x\equiv-1\mod(p) \text{, nếu x = 2k+1}
\end{cases}
$$

Như vậy, khi thay $x=ab$ thì ta sẽ có :
$$
\begin{cases}
K\equiv g^{ab}\equiv1\mod(p) \text{, nếu ab = 2k} \\
K\equiv g^{ab}\equiv-1\mod(p) \text{, nếu ab = 2k+1}
\end{cases}
$$
>Ở đây, $g^{ab}\equiv-1\mod(p)\equiv(p-1)\mod(p)$

Có thể thấy rằng, dù cho có chọn $a,b$ kĩ tới đâu thì khóa cuối cùng lúc này chỉ có thể là $1$ hoặc $-1$. Đó chính là điểm yếu chính khi ta chọn phần tử sinh $g=p-1$.

Tới đây ta chỉ cần thử $K=1$ hoặc $K=-1$ ròi quăng vào trong hàm băm $SHA256$ là đã có được $key$ giải mã **AES_ECB** rồi.

from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from hashlib import sha256

p = 1740527743356518530873219004517954317742405916450945010211514630307030225825627940655848700898186119703288416676610512180281414181211686282526701502342109420226095690170506537523420657033019751819646839624557146950127906808859045989204720555752289247833349649020285507405445896768256093961814925065500513967524214087124440421275882981975756344900858314408284866222751684730112931487043308502610244878601557822285922054548064505819094588752116864763643689272130951
ciphertext = bytes.fromhex("f2803af955eebc0b24cf872f3c9e3c1fdd072c6da1202fe3c7250fd1058c0bc810b052cf99ebfe424ce82dc31a3ba94f")

key1 = sha256(long_to_bytes(1)).digest()[:16]
key2 = sha256(long_to_bytes(p - 1)).digest()[:16]

for key in [key1, key2]:
    cipher = AES.new(key, AES.MODE_ECB)
    try:
        plaintext = unpad(cipher.decrypt(ciphertext), AES.block_size)
        print("Flag:", plaintext.decode()) 
        break  
    except ValueError:
        continue 

<details>
<summary>Flag</summary>
PWNME{411_my_h0m13s_h4t35_sm411_Gs}
</details>

## Square Power

Source code :

from Crypto.Util.number import getStrongPrime
from math import gcd
from random import randint
from typing import Tuple
from Crypto.Cipher import AES
from hashlib import sha256

flag = b"PWNME{xxxxxxxxxxxxxxxxxxxxxxxxx}"

def generate_primes() -> int:
    p = getStrongPrime(512)
    q = getStrongPrime(512)

    while gcd(p*q, (p-1)*(q-1)) != 1:
        p = getStrongPrime(512)
        q = getStrongPrime(512)

    return p*q

def generate_public_key() -> Tuple[int, int]:
    n = generate_primes()
    k = randint(2, n-1)
    while gcd(k, n) != 1:
        k = randint(2, n-1)
    g = 1 + k * n
    return n, g, k

n, g, k = generate_public_key()

a = randint(2, n-1)
b = randint(2, n-1)


A = pow(g, a, n*n)
B = pow(g, b, n*n)

secret_key = pow(B, a, n*n)

def encrypt(m: bytes, secret_key: int) -> str:
    hash_secret_key = sha256(str(secret_key).encode()).digest()
    cipher = AES.new(hash_secret_key, AES.MODE_ECB)
    return cipher.encrypt(m).hex()

print(f"{n = }")
print(f"{g = }")
print(f"{k = }")

print(f"{A = }")
print(f"{B = }")

print(f'enc = "{encrypt(flag, secret_key)}"')
'''output:
n = 130480001264795511204952981970554765286628282097708497573805562495761746956689294837477924716000173700265689121058390655726461662172763702188805523675445230642476356316152454104476211773099930843629048798894397653741145611772970364363628025189743819724119397704649989182196725015667676292311250680303497618517
g = 14232999694821698106937459755169111250723143832548091913379257481041382160905011536064172867298828679844798321319150896238739468953330826850323402142301574319504629396273693718919620024174195297927441113170542054761376462382214102358902439525383324742996901035237645136720903186256923046588009251626138008729683922041672060805697738869610571751318652149349473581384089857319209790798013971104266851625853032010411092935478960705260673746033508293802329472778623222171537591292046922903109474029045030942924661333067125642763133098420446959785042615587636015849430889154003912947938463326118557965158805882580597710148
k = 109081848228506024782212502305948797716572300830339785578465230204043919222714279516643240420456408658167645175971167179492414538281767939326117482613367750888391232635306106151999375263906703485783436272382449557941704742019717763385971731987034043089865070488786181508175732060731733665723128263548176110391
A = 10331979810348166693003506393334562363373083416444082955583854323636220335613638441209816437198980825253073980493123573286927762799807446436773117670818921078297923733365129554252727963674496148945815529457095198387555733553703069705181377382893601879633657895337279524071439340411690401699779320407420258592904893010800421041848764790649945309236525529148459624417556599146885803882692326627657181584151248747924080070945415558421472606778565193931117263508570619290441914589981949634553417159683167906276897159926442471600725573380647253372071392282203683205441190912735696337884772579017885457286629133944441076065
B = 4081342267323018166249607688978380665241423816957875747125328810958590656153973787783246867777679461978030117454679495989870502705358238920918102708702013201363687875430336612386215884751792630402395947375495263771248401103245739000962715422458344125251671671250588124240486938525081520695571867300148511333511433839123962435025865462662009339451634433842267524048553313626315201481951251476302835595998914217740184369102003837614515913319042566394680732429410107620067602633793215206219823499602447575406162296590635685877032818801721681953430382920303700518722500790613216329394164889181089201919505288870098353385
enc = "abd9dd2798f4c17b9de4556da160bd42b1a5e3a331b9358ffb11e7c7b3120ed3"
'''

Ở challenge này vẫn nói về Diffie-Hellman, nhưng lần này $g$ đã được cho khác với challenge đầu tiên.
$$
g=1+k\times n
$$

$$
\Leftrightarrow g=1+k*p*q
$$

Điều đáng nói ở đây là cách tính khóa truyền đi cũng có vấn đề :
$$
\begin{cases}
C_A = g^a\mod(n^2)\\
C_B = g^b\mod(n^2)
\end{cases}
$$
Modulo thay vì là số nguyên tố thì nó lại là $n^2$ ?? Hãy xét đến phương trình :
$$
g^a\mod(n^2)=C_A
$$

$$
\Leftrightarrow (1+k.n)^a\mod(n^2) = C_A
$$

Khai triển nhị thức Newton cho $(1+k.n)^a$ ta có :

$$
(1 + k.n)^a = 1^a+1^{a-1}.(kn)+1^{a-2}.(kn)^2+...+(kn)^a
$$

$$
\Leftrightarrow ((1+k.n)^a=1+kn+(kn)^2+...+(kn)^a) \mod(n^2)
$$
>Ở đây vẫn còn hệ số khai triển nhưng mình không đưa vào vì nó sẽ khá rối

Theo đúng tính chất của phép tính Modulo thì bất kì số nào trong quá trình tính không được vượt quá Modulo, nên lúc này ta sẽ tính Modulo cho từng phần tử. Điều đặc biệt là bắt đầu phần tử $(kn)^2$ thì modulo sẽ bằng 0, do $(kn)^2, (kn)^3,...$ chia hết cho $n^2$

Vì vậy nên khi này ta có :
$$
C_A \equiv(1+k.n)^a\mod(n^2)
$$

$$
\Leftrightarrow C_A\equiv(1+a.k.n)\mod(n^2)
$$

$$
\Leftrightarrow C_a\equiv(1+a.k.n)\mod(n^2)
$$

$$
\Leftrightarrow \frac{(C_A-1)\times pow(k,-1,n^2)}{n}\equiv a\mod(n)
$$

Như vậy, ta đã có được khóa bí mật $a$, bây giờ chỉ cần dùng nó để tính khóa bí mật chung nữa là xong.
$$
B\equiv g^b\mod(n^2)
$$

$$
\Leftrightarrow B^a\equiv g^{ab}\mod(n^2)
$$

from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from hashlib import sha256
from binascii import unhexlify
n = 
g = 
k = 
A = 
B = 
enc = "abd9dd2798f4c17b9de4556da160bd42b1a5e3a331b9358ffb11e7c7b3120ed3"

a = pow(((A-1)*pow(k, -1, n**2))//n,1,n) 
secret_key = pow(B,a,n**2)

enc_flag = "abd9dd2798f4c17b9de4556da160bd42b1a5e3a331b9358ffb11e7c7b3120ed3"
hash_secret_key = sha256(str(secret_key).encode()).digest()

cipher = AES.new(hash_secret_key, AES.MODE_ECB)
decrypted_flag = cipher.decrypt(unhexlify(enc_flag))
print(decrypted_flag.decode())

<details>
<summary>Flag</summary>
PWNME{Thi5_1s_H0w_pAl1ier_WorKs}
</details>

## My Zed