---
# System prepended metadata

title: Diffie Hellman

---

# CryptoHack

## Working with Fields

### Đề bài
![image](https://hackmd.io/_uploads/HJB1_PrLbe.png)

### Ý tưởng
:::info
- Nếu các phép toán cộng, nhân đều được xử lý trong module n thì nó sẽ là vành nếu n là hợp số, và nó sẽ là trường nếu n là số nguyên tố.
- Để lý giải thì mọi số e trong trường sẽ tồn tại một số nghịch đảo nhân là d với $e*d \equiv 1 \ (mod \ n)$, và theo RSA, muốn tồn tại d thì gcd(e,n) = 1, và đó là lý do nếu n là số nguyên tố thì nó sẽ là trường.
:::

### Code
```python=
p = 991
g = 209
print(pow(g, -1, p))
```

## Generators of Groups
![image](https://hackmd.io/_uploads/HJ7SM_SUZl.png)

### Ý tưởng
:::info
- Theo định lý Lagrange trong lý thuyết nhóm thì cấp của mọi nhóm con đều là ước số của cấp của nhóm cha (n-1).
- Và phần tử nguyên thủy (phần tử sinh) là khi đó cấp nhóm do nó sinh ra sẽ bằng cấp của nhóm cha (n-1).
:::
- Và để tìm ra đâu là phần tử sinh thì ta có như sau: mình sẽ tìm các k là các ước số lớn của n-1. Và kiểm tra xem pow(a,k,p) == 1 hay không, nếu nó thỏa thì a không phải là phần tử sinh (a ở đây là số bất kì từ 2-n).
- Ví dụ như trong đề bài, ta có n = 28151, n-1 = 28150 = $2*5^2*563$ => các k lần lượt là 28150/2, 28150/5, 28150/563. Để lý giải tại sao mình làm vậy thì cấp của mọi nhóm con là ước số của n-1, và nếu tại các ước số lớn này mà pow(a,k,p) != 1 thì chắc chắn rằng khi k = n-1, pow(a,k,p) == 1, và đó là cách để ta xác định được đâu là phần tử sinh. 

### Code
```python=
n = 28151
k = [14075, 5630, 50]

for i in range(2,n):
    if all(pow(i, h, n) != 1 for h in k):
        print(i)
        break
```

## Computing Public Values

### Đề bài
![image](https://hackmd.io/_uploads/H12CVYHUZg.png)

### Ý tưởng 
:::info
- Cách mà Diffie-Hellman lựa chọn một số nguyên tố p an toàn bằng cách $p = 2*q + 1$, tức là với p là một số siêu lớn thì q cũng sẽ là một số lớn không kém. Điều này giúp ngăn chặn khỏi thuật toán Pohlig-Hellman bằng cách phân tích p thành các thừa số nguyên tố rồi sử dụng crt để giải bài toán thay vì logarit rời rạc. 
:::

### Code
```python
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
a = 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
print(pow(g, a, p))
```

## Computing Shared Secrets

### Đề bài
![Screenshot from 2026-01-27 09-12-52](https://hackmd.io/_uploads/SkFOljHUZl.png)

### Ý tưởng
- Nói qua về giao thức Diffie-Hellman thì Alice và Bob muốn gửi tin nhắn cho nhau, và họ đang tìm cách để tạo ra cùng một khóa để cả hai tiện khi giao tiếp. Và đây là cách cả hai người đó tạo khóa:
- Alice có khóa bí mật a, và Alice tạo ra khóa công khai A bằng cách $A = g^a \ (mod \ p)$. Bob có khóa bí mật b, và khóa công khai $B = g^b \ (mod \ p)$.
- Lúc này hai người trao đổi khóa công khai cho nhau, và khóa chung (shared key) được tính bằng cách $A^b = B^a = g^{ab}$.
- Lúc này, hai người có thể gửi tin nhắn với nhau thông qua shared key đó. 

### Code 
```python=
A = 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
b = 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919

print(pow(A, b, p))
```

## Deriving Symmetric Keys

### Đề bài
![image](https://hackmd.io/_uploads/rkG3wsSI-l.png)
:::spoiler decrypt.py
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')


shared_secret = ?
iv = ?
ciphertext = ?

print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler source.py
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
import os
from secret import shared_secret

FLAG = b'crypto{????????????????????????????}'


def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data


print(encrypt_flag(shared_secret))
```
:::
### Ý tưởng
- Đề kêu gì thì làm đó 

### Code
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')


A =  112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919


shared_secret = pow(A, b, p)
iv = '737561146ff8194f45290f5766ed6aba'
ciphertext = '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'

print(decrypt_flag(shared_secret, iv, ciphertext))
```

## Parameter Injection

### Đề bài
![image](https://hackmd.io/_uploads/SJEVcsS8Zx.png)

### Ý tưởng
- Bài này cho phép ta kiểm soát những giá trị mà Alice và Bob sẽ gửi, nhưng vấn đề là ta lại không biết private key của cả 2 thằng để có thể tạo ra shared key. Nhưng vì ta kiểm soát được nên ta chỉ việc gửi A = 1 và B = 1 thì lúc này shared key cũng = 1.
![image](https://hackmd.io/_uploads/Skcc5sSIZl.png)

### Code
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')


shared_secret = 1
iv = "67dd12eff12bc79ec7e30c1fec260c5f"
ciphertext = "b22f1e534f5c97884394c01a430221f0aca65d8494ad8b1a2a77d583545e7b63"

print(decrypt_flag(shared_secret, iv, ciphertext))
```

## Export-grade

### Đề bài
![image](https://hackmd.io/_uploads/Syf8wRHIbg.png)

### Ý tưởng
- Bài này cho phép ta chọn các kích thước khóa, thì ta chỉ đơn giản là chọn cái yếu nhất và sử dụng `discrete_log` của sagemath để giải.

### Code
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from sage.all import *


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

p = 0xde26ab651b92a129
g = 0x2 
A = 0x30ba550f1c351763
B = 0x4a9e81d4a7012361

f = GF(p)
g_element = f(g)
A_element = f(A)
a = discrete_log(A_element, g_element)

shared_secret = pow(B, a, p)
iv = "2346c4228c37b24862a3947855877877"
ciphertext = "7949415a64321c483407a67c49eb662f8d4940416216af42978254bbb88581b0"

print(decrypt_flag(shared_secret, iv, ciphertext))
```

## Static Client

### Đề bài 
![image](https://hackmd.io/_uploads/S1ziTASLbl.png)

### Ý tưởng
- Bob yêu cầu ta gửi các tham số, và sau một vài lần test thì mình sẽ xài trick lỏ là p = p_gốc, g = A_Alice, A = 1. Và khi đó, B của Bob đã vô tình cho ta biết được shared key của cả 2. Lúc này ta có thể giải mã ra flag bằng shared key, iv và encrypted flag của Alice. Còn ta muốn giải ra của Bob thì shared key = 1 (vì A ta gửi = 1), iv và encrypted flag của Bob.
![image](https://hackmd.io/_uploads/BkmUCASUWe.png)

### Code
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib



def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')


shared_secret = 0x7d9ca97291d3336ff41c3efe7cefc3ca01340fbad49005cbf59e9e6c23846595786b339ee914827d63d1a11672b22701e93b7fc4d3690889fc55246babf4754cb76eb112f47250d47f5b4c7405df20854fe6867ba2e98bdcb1361a7013b42778c2ec4fb267e4d09a9c4ca072ddd823692ce50fa0689220ae984a623864f1614dc35cf5884344dce269125f1d53b996070b546bd0c97d60a092501803b02f02cbf44c664bc41dac2b33fe2044ff3d90e956d86ffd37d723d8bab78e32e073bb52
iv = "5e15afbc78924a276015049dd42ec2f1"
ciphertext = "7b79327b4be41dbd47ee3dd9de2e08dcf789ac9e67086e340cd604e96e18fe46"

print(decrypt_flag(shared_secret, iv, ciphertext))
```

## Additive

### Đề bài
![image](https://hackmd.io/_uploads/S1ssTRII-g.png)

### Ý tưởng 
- Bài này bảo ta nó sử dụng nhóm cộng và điều này có chút khác so với nhóm nhân bình thường của ta. Cụ thể là:

| multiplicative group  | additive group        | Lý giải                                                                        |
| --------------------- | --------------------- | ------------------------------------------------------------------------------ |
| $A \equiv g^a \ (mod \ n)$ | $A \equiv g*a \ (mod \ n)$ | Với nhóm nhân, nó thực chất là $g*g*g*g...$ và nhóm cộng thì nó là $g+g+g+g+g$    |
| $S \equiv A^b \ (mod \ n)$ | $S \equiv A*b \ (mod \ n)$ | Giải thích như trên, tóm gọn lại thì nhóm nhân ta sẽ thực hiện các phép tính nhân, và nhóm cộng thì ta sẽ thực hiện phép tính cộng.|

![image](https://hackmd.io/_uploads/r138eyPU-e.png)
- Dựa trên output của server thì ta có thể dễ dàng tìm được shared key bằng cách lấy $S = \frac{A*B}{g} \ (mod \ n)$

### Code 
```python= 
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib



def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')
A = 0xd7f06981c7b193047115c1f7e19889784712c55c24bc1ad9f4cee118fe539e6bd457fb6ddba16c9bad30d64a1ad98e5a0ccdc62b556dc315a9c483f589d70a3b8b25c11aa7a8e4ba0149c63689b867e2b0baf2960639e1882e82d18e0eb0b7155319b188f91ec6a0b320f8d37c9f87ab6adfa68d0a25a3fd2d74f1c95bc76544d200db3d167fa92eb3392e3c53a88d90f4c8d850652e52b3c5d337956a60427c2cf2e6f173faf1a4d416939da2a252a9521234d4d042411199fc3b23c3f9721a
B = 0x6b8138c4b9e1bb01ed4d9964a0b3b5d48dce1cad0a9934cbe0c3f79c2dd8e1bbb065a343530ad58ec83734e32f604bd556bcaa83616b753fabfe144cc3e3eddc572e4cc6a374868a4df18c66dc995560aaa396701349b9c30cbd8a1ee1bcc0762a288846efdf1d2e904d58c0715c6ae11b3103928b22429ae6b7ead3024f77f48cc44deff42137d3fe1d5f64faaf4e2a4a9ccf084586eb0d33e24fe25b3c039a634cc02361efbb5024260b76162d244d77cc0c719925ccabdf99838edbcb1b01
g = 0x02
p =0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff


shared_secret = A*B//g % p
iv = "6f93a3e8c0793d544a54b77e78fa5532"
ciphertext = "c9487ebc59e0d65c9784cd2675a7a96167ef67604d81220eea6ccc906641dff4b1c99287cb1d98a2ddf426329dd77464"

print(decrypt_flag(shared_secret, iv, ciphertext))
```

## Static Client 2 

### Đề bài
![image](https://hackmd.io/_uploads/BJ9lTB_Lbe.png)


### Ý tưởng
- Bài này thì cũng yêu cầu ta tìm ra flag của Alice, mình đã thử cách giống bài 1 là gửi g' = A, tuy nhiên nó không được thì phải. Và lúc sau thì mình nghĩ rằng ta có thể thay p thành một số khác sao cho p' >= p và p'-1 là một smooth. Lúc này ta có thể dùng discrete_log để tìm ra b. Và lúc này ta sẽ tìm ra được shared key, nếu ta muốn đọc tin nhắn của Bob thì shared key phải nằm trong trường p', còn nếu ta muốn đọc tin nhắn của Alice thì shared key phải nằm trong trường p.
- Đây là code để tìm p'
```python=
from sympy import isprime

p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff

def smooth_prime(): 
    value = 1
    i = 1
    while True:
        value *= i
        
        candidate = value + 1
        
        if candidate.bit_length() >= p.bit_length() and isprime(candidate):
            return candidate
            
        i += 1

q = smooth_prime()
print(hex(q))
```
![image](https://hackmd.io/_uploads/HkRDBUPIZx.png)

### Code
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from sage.all import *


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
p_ = 0x72b20ce22e5616f923901a946b02b2ad0417882d9172d88c1940fec763b0cdf02ca5862cfa70e47fb8fd10615bf61187cd564a017355802212a526453e1fb9791014f070d77f8ff4dd54a6d1d58969293734e0b6bc22f3ceea788aa33be35eed4bdc1c8ceb94084399d98e13e69a2b9fa6c5583836a15798ba1a10edd81160a15662cdf587df6b816c570f9b11a466d1b4c328180f614e964f3a5ec61c3f2b759b21687a122f9faefc86fe69a3efd14829639596eb7f2de6eab6b444d06233d34d0651e6fed17db4d0025e58db7cad8824c3e93ed24df588a0a4530be2676e995f870172b9e765ec2886bce140000000000000000000000000000000000000000000000000000000000000000000000000000001
g = 0x02
A = 0x753628cab38a76130f9308478cb9f7a2eb0592c607e72381b395fa8c84e60f35545c9f3176346f159b37ea49a57e772e27af3d1d1cc895609fb6d466107d8cd2cf3fa8bcbc988d7f96f0a4305f08c849a48aada33824fe66ae2b66ec26179c1f799441c2e107cfcaab3981a8feec855a82f3af55772df6e3570848dadd45407228f14f610c2b3c5f1a1a4546cd20f36a5249998707b3dbac57f62903f77ad147ae8e59f6867fe703209395ce6d75e0ca8c9eb7f38bc4cda1bfeacf56ca56b23e
B =0x56c2f62b18614911dfca2942d1c5f60d84f2d95dde472190424658940f9fd7aeb5af05432b2e4db94feb69040a7d7d39700463f4e1c98903edc7740e2f72eb7beea78206c0a1cc80c7adc5de2a1599e5cfcc183a790d8ee4cb009627899341298722cc2fb9c30f7ce78fad0ed743fa227341d4085335504a26febca986e25bb8fab55d0b3396e49d4db63a52ac33f0a31b6d8a55e7902dce7b8ee66a3d338a2d62d647297adcc7fd1007bb1be74db7c7af9d6374db3f3950dad7895c2244ff40e2d1ae577740ef672b0c29d97a8175dc34a8e2a014a8e279fed464fbbd9e79109ec2aba2cefddfedfc092c0dd48e8d276da5e3b04959bf8829bc8187215cc6cc063842bc3ac69d5b62eddfc00f1fe2678c65656d

f = GF(p_)
b = discrete_log(f(B), f(g))


shared_secret = pow(A, b, p)
iv = "de9bac47b076b8f16ea8956eaecf3402"
ciphertext = "24037a759eeef3f3d67630fdc06e4dabd5771eb1a7c2ee94f51ceb0a143c0aeac4d6578002805aaec9c2b86aa222a1ef"

print(decrypt_flag(shared_secret, iv, ciphertext))
```

## Script Kiddie

### Đề bài 
![image](https://hackmd.io/_uploads/BysNwAhLbg.png)
:::spoiler script.py
```python=
from Crypto.Cipher import AES
import hashlib
import secrets


def header():
    print("""  _____  _  __  __ _
 |  __ \(_)/ _|/ _(_)
 | |  | |_| |_| |_ _  ___
 | |  | | |  _|  _| |/ _ \
 | |__| | | | | | | |  __/
 |_____/|_|_| |_| |_|\___|
 | |  | |    | | |
 | |__| | ___| | |_ __ ___   __ _ _ __
 |  __  |/ _ \ | | '_ ` _ \ / _` | '_ \
 | |  | |  __/ | | | | | | | (_| | | | |
 |_|  |_|\___|_|_|_| |_| |_|\__,_|_| |_|

                                        """)


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def pkcs7_unpad(message, block_size=16):
    if len(message) == 0:
        raise Exception("The input data must contain at least one byte")
    if not is_pkcs7_padded(message):
        return message
    padding_len = message[-1]
    return message[:-padding_len]


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)
    return pkcs7_unpad(plaintext).decode('ascii')


def generate_public_int(g, a, p):
    return g ^ a % p


def generate_shared_secret(A, b, p):
    return A ^ b % p


def goodbye():
    print('Goodbye!')


def main():
    header()
    print('[-] Collecting data from Alice')
    p = int(input('> p: '))
    q = (p - 1) // 2
    g = int(input('> g: '))
    A = int(input('> A: '))
    print('[+] All data collected from Alice')

    print('[+] Generating public integer for alice')
    b = secrets.randbelow(q)
    B = generate_public_int(g, b, p)
    print(f'[+] Please send the public integer to Alice: {B}')
    print('')
    input('[+] Press any key to continue')
    print('')

    print('[+] Generating shared secret')
    shared_secret = generate_shared_secret(A, b, p)

    query = input('Would you like to decrypt a message? (y/n)\n')
    if query == 'y':
        iv = input('[-] Please enter iv (hex string)\n')
        ciphertext = input('[-] Please enter ciphertext (hex string)\n')
        flag = decrypt_flag(shared_secret, iv, ciphertext)
        print(f'[+] Flag recovered: {flag}')
        goodbye()
    else:
        goodbye()


if __name__ == '__main__':
    main()
```
:::
:::spoiler output.txt
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g: 2
A: 539556019868756019035615487062583764545019803793635712947528463889304486869497162061335997527971977050049337464152478479265992127749780103259420400564906895897077512359628760656227084039215210033374611483959802841868892445902197049235745933150328311259162433075155095844532813412268773066318780724878693701177217733659861396010057464019948199892231790191103752209797118863201066964703008895947360077614198735382678809731252084194135812256359294228383696551949882
B: 652888676809466256406904653886313023288609075262748718135045355786028783611182379919130347165201199876762400523413029908630805888567578414109983228590188758171259420566830374793540891937904402387134765200478072915215871011267065310188328883039327167068295517693269989835771255162641401501080811953709743259493453369152994501213224841052509818015422338794357540968552645357127943400146625902468838113443484208599332251406190345653880206706388377388164982846343351
iv: 'c044059ae57b61821a9090fbdefc63c5'
encrypted_flag: 'f60522a95bde87a9ff00dc2c3d99177019f625f3364188c1058183004506bf96541cf241dad1c0e92535564e537322d7'
:::
### Ý tưởng 
- Dễ dàng thấy khi ta đọc source code thì có:
```python=
def generate_public_int(g, a, p):
    return g ^ a % p


def generate_shared_secret(A, b, p):
    return A ^ b % p
```
- Thì dấu ^ ở đây thực chất là phép xor chứ không phải phép mũ. Vì thế ta có: $B =  g \ \oplus b$, shared_key $= A \oplus b$ (tất cả đều nằm trong trường p). Vì thế ta có thể dễ dàng suy ra được:
$$
sk = A \oplus B \oplus g 
$$
- Hết bài.

### Code 
```python=
from Crypto.Cipher import AES
import hashlib
import secrets


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def pkcs7_unpad(message, block_size=16):
    if len(message) == 0:
        raise Exception("The input data must contain at least one byte")
    if not is_pkcs7_padded(message):
        return message
    padding_len = message[-1]
    return message[:-padding_len]

def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)
    return pkcs7_unpad(plaintext).decode('ascii')


p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g = 2
A = 539556019868756019035615487062583764545019803793635712947528463889304486869497162061335997527971977050049337464152478479265992127749780103259420400564906895897077512359628760656227084039215210033374611483959802841868892445902197049235745933150328311259162433075155095844532813412268773066318780724878693701177217733659861396010057464019948199892231790191103752209797118863201066964703008895947360077614198735382678809731252084194135812256359294228383696551949882
B = 652888676809466256406904653886313023288609075262748718135045355786028783611182379919130347165201199876762400523413029908630805888567578414109983228590188758171259420566830374793540891937904402387134765200478072915215871011267065310188328883039327167068295517693269989835771255162641401501080811953709743259493453369152994501213224841052509818015422338794357540968552645357127943400146625902468838113443484208599332251406190345653880206706388377388164982846343351
iv = 'c044059ae57b61821a9090fbdefc63c5'
encrypted_flag = 'f60522a95bde87a9ff00dc2c3d99177019f625f3364188c1058183004506bf96541cf241dad1c0e92535564e537322d7'


shared_key = A ^ B ^ g % p
flag = decrypt_flag(shared_key, iv, encrypted_flag)
print(flag)
```

## The Matrix

### Đề bài 
![Screenshot from 2026-02-01 23-00-47](https://hackmd.io/_uploads/rJPKYgTLbg.png)
:::spoiler the_matrix.sage 
```python=
import random

P = 2
N = 50
E = 31337

FLAG = b'crypto{??????????????????????????}'

def bytes_to_binary(s):
    bin_str = ''.join(format(b, '08b') for b in s)
    bits = [int(c) for c in bin_str]
    return bits

def generate_mat():
    while True:
        msg = bytes_to_binary(FLAG)
        msg += [random.randint(0, 1) for _ in range(N*N - len(msg))]

        rows = [msg[i::N] for i in range(N)]
        mat = Matrix(GF(2), rows)

        if mat.determinant() != 0 and mat.multiplicative_order() > 10^12:
            return mat

def load_matrix(fname):
    data = open(fname, 'r').read().strip()
    rows = [list(map(int, row)) for row in data.splitlines()]
    return Matrix(GF(P), rows)

def save_matrix(M, fname):
    open(fname, 'w').write('\n'.join(''.join(str(x) for x in row) for row in M))

mat = generate_mat()

ciphertext = mat^E
save_matrix(ciphertext, 'flag.enc')
```
:::

:::spoiler flag.enc 
00000001111101100001101010010001001011000110001001
10111010010100110001011011111110011000001001000001
01011101000110110101010100100100111110110110011111
11101100011011010001111011011000100010110001001010
11111111101001010101001011111101010010011010101001
10010011101000000010000110100101111011110011101110
00011100010011010110000000001011000111010101001011
01001111000110100111110011000101011110010111111110
01111001110011000100000110010101011111010000000011
11001101010111111011110110101010001101001001111101
01100111000100010101000001011011001101001110101000
00010001001011101111100010101101011000101100010111
01101100101101011101101000110001011111111010000100
00001110111111000111111100011110000101100100000011
10001001111111011000111011111010110111111111000110
01111101100011110110111000011110000100111001110100
11111100110101111001111000110100011010111011110001
00100011011100101010111011111100000010000101111111
01111001110100011111011100100011011010010011111000
01011011101011111111101011011011000111110011111010
00010100110111110011111100111101100000001101110111
10011011011101110101100110110000011101000010101011
01111000001111011011111000100010010010010111101001
00100000010001110000001101111100011111110011011000
10010101101011011111101111101000111010010011111001
10011011000111000001010111011000000000100111100011
11001001010001111111000011011011101001101010001000
00100100000101110010001001011001111011001110100001
00000101000101100111010111101010001101111110011001
00101000011010100110100111111110000101011001011110
11011001001111111010000001100111011101101100110110
00111000011011011111111011110001001101001101101100
11110010101001100110000110110000100000101010101011
00101001000011001110110111100010010011100101001000
11000100010010111110110010100110110110101000110110
01101011000111001111011110000110001011111000011100
11010011001111111110100101100011000000000011110001
10000011000101100011000110111111011010110111101000
11000011000100010001001011010011010000001101100011
11011001111001010100010101001100001010101100010010
10110101010111111010110001111111100100110001001100
11101001100110001001001100000011100101001010011010
10000011100110001101010110010010100001010011011101
10001110111111100110011000010000011011011111011001
00011100011111110101011100111000110010100011000010
00111111010010111100100101100001001011110101111100
10000100101101000011011010100100011111100101101111
00011101110001001010111001111011111110110011011001
11111100110101111100110001011001000001111100110011
00110010110110011001001111110110000011001111010110
:::
### Ý tưởng 
- Bài này core idea của nó chính là giải RSA trong ma trận. Và mình đã học nó từ [đây](https://www.gcsu.edu/sites/files/page-assets/node-808/attachments/pangia.pdf). 
- Giải thích nôm na thì với RSA thông thường ta tính $d \equiv e^{-1} \ (mod \ \phi(n))$. Nhưng trong ma trận thì $\phi(n)$ chính là cấp của ma trận, với kí hiệu làcông thức là: $|GL(N, \mathbb{F}_p)|$ (với bài này N = 50, p = 2), có công thức là:
$$
|G| = (p^N - 1)(p^N - p)(p^N - p^2) \dots (p^N - p^{N-1})
$$
- Tuy nhiên |G| lại là một số rất lớn và theo định lý Larange thì cấp của nhóm con đều là ước số của cấp của nhóm cha. Nói chung là ta sẽ sử dụng `multiplicative_order()` để tính cấp của ma trận trong đề bài (một số nhỏ hơn rất nhiều so với thằng kia). 
- Sau khi hiểu được nguyên lý gốc thì ta có thể ra gần hết bài, ngoại trừ một chi tiết nhỏ này:
```python=
rows = [msg[i::N] for i in range(N)]
```
- Bài này ta phải truy ngược từ cột chứ không phải từ dòng.
- Đến đây thì hết bài.

### Code 
```python=
from sage.all import *

data = """00000001111101100001101010010001001011000110001001
10111010010100110001011011111110011000001001000001
01011101000110110101010100100100111110110110011111
11101100011011010001111011011000100010110001001010
11111111101001010101001011111101010010011010101001
10010011101000000010000110100101111011110011101110
00011100010011010110000000001011000111010101001011
01001111000110100111110011000101011110010111111110
01111001110011000100000110010101011111010000000011
11001101010111111011110110101010001101001001111101
01100111000100010101000001011011001101001110101000
00010001001011101111100010101101011000101100010111
01101100101101011101101000110001011111111010000100
00001110111111000111111100011110000101100100000011
10001001111111011000111011111010110111111111000110
01111101100011110110111000011110000100111001110100
11111100110101111001111000110100011010111011110001
00100011011100101010111011111100000010000101111111
01111001110100011111011100100011011010010011111000
01011011101011111111101011011011000111110011111010
00010100110111110011111100111101100000001101110111
10011011011101110101100110110000011101000010101011
01111000001111011011111000100010010010010111101001
00100000010001110000001101111100011111110011011000
10010101101011011111101111101000111010010011111001
10011011000111000001010111011000000000100111100011
11001001010001111111000011011011101001101010001000
00100100000101110010001001011001111011001110100001
00000101000101100111010111101010001101111110011001
00101000011010100110100111111110000101011001011110
11011001001111111010000001100111011101101100110110
00111000011011011111111011110001001101001101101100
11110010101001100110000110110000100000101010101011
00101001000011001110110111100010010011100101001000
11000100010010111110110010100110110110101000110110
01101011000111001111011110000110001011111000011100
11010011001111111110100101100011000000000011110001
10000011000101100011000110111111011010110111101000
11000011000100010001001011010011010000001101100011
11011001111001010100010101001100001010101100010010
10110101010111111010110001111111100100110001001100
11101001100110001001001100000011100101001010011010
10000011100110001101010110010010100001010011011101
10001110111111100110011000010000011011011111011001
00011100011111110101011100111000110010100011000010
00111111010010111100100101100001001011110101111100
10000100101101000011011010100100011111100101101111
00011101110001001010111001111011111110110011011001
11111100110101111100110001011001000001111100110011
00110010110110011001001111110110000011001111010110"""
P = 2
N = 50
E = 31337


mat = [list(map(int, row)) for row in data.splitlines()]
C = Matrix(GF(P),mat)

C_order = C.multiplicative_order()
D = pow(E, -1, C_order)
M = C**D

bits = []
for c in range(N):
    for r in range(N):
        bits.append(M[r][c])

flag = ""
for i in range(0, len(bits), 8):
    chunk = bits[i:i+8]
    byte_val = int("".join(map(str, chunk)), 2)
    flag += chr(byte_val)
print(flag)
```
# Hackropole

## El Gamal Fait 1/2

### Đề bài 
:::spoiler el-gamal-fait-1.py
```python=
from Crypto.Random.random import randrange
from Crypto.Util.number import getPrime

def generate(bits):
    p = getPrime(bits)
    x = randrange(p)
    g = randrange(2, p)
    y = pow(g,x,p)
    return p, g, x, y

def sign(p, g, x, m):
    k = randrange(p)
    r = pow(g, k, p)
    inv_k = pow(k, -1, p - 1)
    s = ((m - x * r) * inv_k) % (p - 1)
    return r, s

def verify(p, g, y, m, r, s):
    if r <= 0 or r >= p - 1 or s < 0 or s >= p - 1:
        return False
    return pow(g, m, p) == ((pow(y, r, p) * pow(r, s, p)) % p)

print("Public key:")
p, g, x, y = generate(2048)
print(f"{p = }")
print(f"{g = }")
print(f"{y = }")

try:
    print("Input a message.")
    m = int(input(">>> "))

    print("Input a signature. First, input r.")
    r = int(input(">>> "))

    print("Now, input s.")
    s = int(input(">>> "))

    if verify(p, g, y, m, r, s):
        print("Congratulations! The message and signature match. Here is your flag:")
        print(open("flag.txt").read())
    else:
        print("Better luck next time!")
except:
    print("Please check your inputs!")

```
:::

### Ý tưởng 
- Trước tiên, đây là một bài toán theo kiểu `ElGamal signature`, nôm na là nó sẽ có p, g, y là 3 public key, message m, với 2 private key r, s. 
:::info
- Cách để tạo ra private key gốc của `ElGamal signature` là:
- Chọn một số $1<k<p-1$  sao cho GCD(k,p-1)==1 (cốt là để tồn tại $k^{-1} \ (mod \ p-1)$.
- Tính $r = g^k \pmod p$.
- Tạo ra h = H(m), ta phải băm message ra thành h, **khúc này quan trọng** .
- Tính $s = (h - xr) \cdot k^{-1} \pmod{p-1}$.
- Và từ đó ta đã có s, r.
- Cuối cùng ta được công thức tổng quát như sau:
$$g^{H(m)} \equiv (y)^r (r)^s \pmod p$$
:::
- Quay ngược lại bài toán, như ta thấy thì nó không yêu cầu phải băm message, và vì thế ta có thể chọn một message bất kì hay cụ thể ở đây mình sẽ chọn m = 0. Lúc này công thức tổng quát của ta sẽ thành:
$$
1 \equiv g^{0} \equiv (y)^r (r)^s \pmod p
$$
- Bây giờ việc duy nhất của ta là phải tìm r, s làm sao cho nó cũng = 1.
- Lúc này giữa trên cảm tình của mình (làm đại) thì ta nhận thấy rằng, mình sẽ cho s = r, lúc này vế phải sẽ thành:
$$
(y*r)^r
$$
- Giờ để cho nó = 1 thì dễ thấy nhất, r sẽ bằng pow(y,-1,p). Lúc này vế phải sẽ = 1. Hết bài.

### Code
```python=
from pwn import *

context.log_level = 'debug'
c = remote("localhost", 4000)
c.recvuntil(b"p =")
p = int(c.recvline())
c.recvuntil(b"g =")
g = int(c.recvline())
c.recvuntil(b"y =")
y = int(c.recvline())

m = 0
r = pow(y,-1,p)
s = r 

c.recvuntil(b">>> ")
c.sendline(str(m).encode())
c.recvuntil(b">>> ")
c.sendline(str(r).encode())
c.recvuntil(b">>> ")
c.sendline(str(r).encode())
c.interactive()
```

## El Gamal Fait 2/2

### Đề bài
:::spoiler el-gamal-fait-2.py
```python=
from Crypto.Random.random import randrange
from Crypto.Util.number import getPrime

def generate(bits):
    p = 2
    while p % 4 != 1:
        p = getPrime(bits)
    x = randrange(p)
    g = 2
    y = pow(g, x, p)
    return p, g, x, y

def sign(p, g, x, m):
    k = randrange(p)
    r = pow(g, k, p)
    inv_k = pow(k, -1, p - 1)
    s = ((m - x * r) * inv_k) % (p - 1)
    return r, s

def verify(p, g, y, m, r, s):
    if r <= 0 or r >= p or s < 0 or s >= p - 1:
        return False
    return pow(g, m, p) == ((pow(y, r, p) * pow(r, s, p)) % p)

print("Public key:")
p, g, x, y = generate(2048)
print(f"{p = }")
print(f"{g = }")
print(f"{y = }")

try:
    m = randrange(p)
    print(f"Your task is to sign the following message m = {m}")

    print("Input a signature. First, input r.")
    r = int(input(">>> "))

    print("Now, input s.")
    s = int(input(">>> "))

    if verify(p, g, y, m, r, s):
        print("Congratulations! The message and signature match. Here is your flag:")
        print(open("flag.txt").read())
    else:
        print("Better luck next time!")
except:
    print("Please check your inputs!")
```
:::

### Ý tưởng
- Bài này khác với bài trước là ta sẽ không được tự ý nhập m, tuy nhiên g luôn cố định = 2. Và lúc này công thức tổng quát của ta sẽ là:
$$
2^m \equiv y^r*r^s \pmod p
$$
- Vấn đề lúc này thì bản thân mình nghĩ sẽ phụ thuộc phần lớn vào kĩ năng biến đổi và sự nhạy bén với số liệu của mỗi người cũng như là "ăn hên". 
- Với mình thì ban đầu mình nghĩ rằng s phải liên quan đến m hoặc -m hoặc đại loại gì đó và cũng như ta phải tìm một cách nào đó để $y^r$ thành 1 hoặc làm sao để nó không ảnh hưởng tới phần cơ số vì cơ số luôn cố dịnh = 2. Và lúc đó mình đã nghĩ tới định lý fermat nhỏ: $y^{p-1} \equiv 1 \ (mod \ p)$, tức là r = p-1. Nhưng sau một lúc biến đổi thì nó lại thành ra như này:
$$
2^m \equiv 1*(p-1)^m \pmod p
$$
=>
$$
2^m \equiv (-1)^m \pmod p
$$
- Lúc này chắc chắn là nó sai, và trong lúc đó thì mình vô tình rùa ra bằng cách để ý rằng $p \equiv 1 \ (mod \ 4)$, và lúc này mình nghĩ tới công thức $(x/p) \equiv x^{(p-1)/2} \ (mod \ p)$ của `Legendre Symbol` 
:::danger
- cái này hình như là rùa vì thực chất dữ kiện đó của p hình như giúp cho nó không rơi vào safe prime chứ chẳng liên quan gì tới cái này hết thì phải =)))
:::
- Lúc này mình đã biến đổi như sau:
$$
2^m \equiv y^{(p-1)/2}* (\frac{p-1}{2})^{-m} \pmod p
$$
=>
$$
2^m \equiv y^{(p-1)/2}* ((\frac{-1}{2})^{-1})^m \pmod p
$$
=> 
$$
2^m \equiv y^{(p-1)/2}* (-2)^m \pmod p
$$
- Thì cái này sẽ đúng trong cụ thể 2 trường hợp: 1 là khi $y^{(p-1)/2}$ = 1 và m là số chẵn, 2 là khi $y^{(p-1)/2}$ = -1 và m là số lẻ.
- Lúc này gần như là hết bài trừ việc ta phải biến đổi một chút làm sao cho thỏa điều kiện của hàm verify trong source code.
:::spoiler raw.png
![65bbcfed-b2f8-45d3-987a-c90937720f45_515171a7-0658-422a-aa4b-32d7e4e5e382](https://hackmd.io/_uploads/r16vQjhLZx.jpg)
:::

### Code
```python=
from pwn import *

while True:
    c = remote("localhost", 4000)
    c.recvuntil(b"p = ")
    p = int(c.recvline())
    c.recvuntil(b"g = ")
    g = int(c.recvline())
    c.recvuntil(b"y = ")
    y = int(c.recvline())
    c.recvuntil(b"m = ")
    m = int(c.recvline())

    r = (p-1)//2
    s = -m % (p-1)

    c.recvuntil(b">>> ")
    c.sendline(str(r).encode())
    c.recvuntil(b">>> ")
    c.sendline(str(s).encode())

    response = c.recvall()
    if(b"FCSC" in response):
        print(response.decode())
        break
```
# Dreamhack 

## Textbook-DH

### Đề bài
`level 3`
:::spoiler challenge.py
```python=
#!/usr/bin/python3
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
import hashlib
import random

class Person(object):
    def __init__(self, p):
        self.p = p
        self.g = 2
        self.x = random.randint(2, self.p - 1)
    
    def calc_key(self):
        self.k = pow(self.g, self.x, self.p)
        return self.k

    def set_shared_key(self, k):
        self.sk = pow(k, self.x, self.p)
        aes_key = hashlib.md5(str(self.sk).encode()).digest()
        self.cipher = AES.new(aes_key, AES.MODE_ECB)

    def encrypt(self, pt):
        return self.cipher.encrypt(pad(pt, 16)).hex()

    def decrypt(self, ct):
        return unpad(self.cipher.decrypt(bytes.fromhex(ct)), 16)

flag = open("flag", "r").read().encode()
prime = getPrime(1024)
print(f"Prime: {hex(prime)}")
alice = Person(prime)
bob = Person(prime)

alice_k = alice.calc_key()
print(f"Alice sends her key to Bob. Key: {hex(alice_k)}")
print("Let's inturrupt !")
alice_k = int(input(">> "))
if alice_k == alice.g:
    exit("Malicious key !!")
bob.set_shared_key(alice_k)

bob_k = bob.calc_key()
print(f"Bob sends his key to Alice. Key: {hex(bob_k)}")
print("Let's inturrupt !")
bob_k = int(input(">> "))
if bob_k == bob.g:
    exit("Malicious key !!")
alice.set_shared_key(bob_k)

print("They are sharing the part of flag")
print(f"Alice: {alice.encrypt(flag[:len(flag) // 2])}")
print(f"Bob: {bob.encrypt(flag[len(flag) // 2:])}")
```
:::

## Ý tưởng 
- Bài này về cơ bản thì chả khác gì bài `Parameter Injection` của cryptohack hết, ta chỉ cần gửi k = 0 hoặc k = 1 để biến `sk` thành một hằng số và giải thôi.
![image](https://hackmd.io/_uploads/rk3dzhhUbl.png)

## Code 
```python=
#!/usr/bin/python3
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
import hashlib
import random

def decrypt(ct):
    aes_key = hashlib.md5(str(1).encode()).digest()
    cipher = AES.new(aes_key, AES.MODE_ECB)
    return unpad(cipher.decrypt(bytes.fromhex(ct)), 16)

A = "e48e9174a9103e249f4bb809e13d58d49283e2438954799030be4854328adacbeb310c79bce3e91719f218158359af0d"
B = "2a69648d494907e551b69b74676f2e528644a526e5f7bc8b6300f1bd8ad5f091a9e40939960ea5bd0ad2ceff23a14f96"

print(decrypt(A))
print(decrypt(B))
```

