# Diffie-Hellman Cryptohack.
## STARTER
### Diffie Hellman Starter 1.

Given the prime p = 991, and the element g = 209, find the inverse element d such that g * d mod 991 = 1.

print(pow(209, -1, 991))

`flag: 569`

### Diffie Hellman Starter 2.

For the finite field with p = 28151 find the smallest element g which is a primitive element of Fp.

Bài yêu cầu tìm phần tử sinh bé nhất trên trường Fp với p = 28151.

p = 28151
phi = p - 1
list = [2, 5, 563]
count = 0
for i in range(2, p):
    if pow(i, phi//list[0], p) != 1 and pow(i, phi//list[1], p) != 1 and pow(i, phi//list[2], p) != 1:
        print(i)
        break

`flag: 7`
### Diffie Hellman Starter 3.

The Diffie-Hellman protocol is used because the discrete logarithm is assumed to be a "hard" computation for carefully chosen groups.

The first step of the protocol is to establish a prime p and some generator of the finite field g. These must be carefully chosen to avoid special cases where the discrete log can be solved with efficient algorithms. For example, a safe prime p = 2*q +1 is usually picked such that the only factors of p - 1 are {2,q} where q is some other large prime. This protects DH from the Pohlig–Hellman algorithm.

The user then picks a secret integer a < p and calculates g^a mod p. This can be transmitted over an insecure network and due to the assumed difficulty of the discrete logarithm, the secret integer should be infeasible to compute.

Given the NIST parameters:

g: 2

p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919

Calculate the value of g^a mod p for

a: 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815

g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
a = 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
print(pow(g, a, p))

`flag: 1806857697840726523322586721820911358489420128129248078673933653533930681676181753849411715714173604352323556558783759252661061186320274214883104886050164368129191719707402291577330485499513522368289395359523901406138025022522412429238971591272160519144672389532393673832265070057319485399793101182682177465364396277424717543434017666343807276970864475830391776403957550678362368319776566025118492062196941451265638054400177248572271342548616103967411990437357924`

### Diffie Hellman Stater 4.

g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
b = 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
B = 518386956790041579928056815914221837599234551655144585133414727838977145777213383018096662516814302583841858901021822273505120728451788412967971809038854090670743265187138208169355155411883063541881209288967735684152473260687799664130956969450297407027926009182761627800181901721840557870828019840218548188487260441829333603432714023447029942863076979487889569452186257333512355724725941390498966546682790608125613166744820307691068563387354936732643569654017172

Đề bài yêu cầu tính khóa chung.

g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
b = 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
B = 518386956790041579928056815914221837599234551655144585133414727838977145777213383018096662516814302583841858901021822273505120728451788412967971809038854090670743265187138208169355155411883063541881209288967735684152473260687799664130956969450297407027926009182761627800181901721840557870828019840218548188487260441829333603432714023447029942863076979487889569452186257333512355724725941390498966546682790608125613166744820307691068563387354936732643569654017172

print(pow(A, b, p))

`flag: 1174130740413820656533832746034841985877302086316388380165984436672307692443711310285014138545204369495478725102882673427892104539120952393788961051992901649694063179853598311473820341215879965343136351436410522850717408445802043003164658348006577408558693502220285700893404674592567626297571222027902631157072143330043118418467094237965591198440803970726604537807146703763571606861448354607502654664700390453794493176794678917352634029713320615865940720837909466`

### Diffie Hellman Starter 5.

g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
B = 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581

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

Để lấy được flag của bài thì ta phải tính được khóa chung và dùng file `decrypt.py` để giải mã.

g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
B = 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581

shared_secret = pow(A, b, p)
iv = '737561146ff8194f45290f5766ed6aba'
encrypted = '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'
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')

print(decrypt_flag(shared_secret, iv, encrypted))

`flag: crypto{sh4r1ng_s3cret5_w1th_fr13nd5}`
## MAN IN THE MIDDLE
### Parameter Injection
Để giải quyết được bài này ta cần sử dụng MITM attack để có thể lấy được flag.
Minh họa MITM attack:
- Bước đầu tiên ta sẽ giử cho Bob những dữ liệu mà ta đã biết từ Alice.

- Sau khi gửi ta đã có thế thấy được thông tin mà Bob gửi qua cho Alice. Giờ ta sẽ gửi lại một thông tin giả với `g` và `p` đã biết và 1 số nguyên bí mật mà ta chọn bất kỳ. Ví dụ $C= g^{3}$ mod p = `0x8`. Sau đó ta sẽ gửi lại cho Alice.
- Sử dụng cách mã hóa của DH Starter 5 để giải mã và lấy được flag.

p = int("0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", 16)
g = int("0x02", 16)
A = int("0x43dfa1aca650344d2e0866aae656035e9ca5ed05d9f55c6baa581fd2c58ff9f3e742bf5a536e5672ce45eff0f2ec4bec511941571ba51748197b61dd892ba0777ab06aebfe1c72266346cfdb24dd44d1676d422039e422a9e15fc2dd53d43d7efb38ffb6551ef29d4e363c15706757bbbbd240a2203db132a4527afbb16d44d9fdef73f266b6d00a7208b1b5bb673cd4c2d247bd120d4cb25ae1855494a7938997d73bd8977a96d23754805d35b8ab2ae2f65e0199b6b0fb87fa2137174bbf31", 16)
B = int("0x62d9cb00aae0d828d6e801e16cae7d5c3212bf6c6f733e703b60043e7afa90e68e1c1925b46ca8f5be3cde5953c7b8c76758fae1dbd09114bc4f4ec540169ce4495e790c19daf68937956d8ec0c65b7d3980600e49b7d95bea64409f6ea41c554cf38986a21e18e99b27b85cd41883bf3456d97342453b227699c19c7a90341ec1533de26d749fde2384516f464b4137fd0ffc17b8c1f4bff5b8eca55d2b1a4c3fa62d6abb759a24f4a79d41548820f433bac89e25dc2b412508d4b0d168a212", 16)
print(hex(pow(g, 3, p)))
iv = "b8a143ef7140e6f2469e29159da005e4"
encrypted_flag =  "38be5c5d4e25261064b01c2812f3015ef3ec4d8dc81e435ca6d87cbd811f5d87"
shared_secret = pow(A, 3, p)
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')

print(decrypt_flag(shared_secret, iv, encrypted_flag))

`flag: crypto{n1c3_0n3_m4ll0ry!!!!!!!!}`

### Export-grade
- Vẫn sử dụng MITM để tấn công và lấy flag. Ta gửi thông tin nhận được từ Alice sang cho Bob và sẽ thu được kết quả như sau:

- Lúc này nếu như ta vẫn tấn công như bài trước bằng cách gửi lựa chọn khác như `DH64` thì sẽ không thể nhận được thông tin mà Bob gửi lại cho Alice

- Vì vậy, ta sẽ thử cách khác bằng cách không gửi cho Bob tất cả các lựa chọn mà chỉ gửi cho Bob lựa chọn duy nhất là `{"supported": "DH64"}` và lúc này Bob chỉ có thể lựa chọn `DH64` như thế ta có thể thu được thông tin ở mức mà ta có thể giải ra nhanh nhất.

- Sau khi thu được tất cả các thông tin, vì số bé lên ta hoàn toàn có thể tính được `a` ($A=g^{a}$ mod p). Với p, g, A đã biết, ta sử dụng hàm `discrete_log()` để có thể tính được `a` và giải mã như bình thường. Hoặc dùng sagemath để tính `a`

from sympy.ntheory.residue_ntheory import discrete_log
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
p = int("0xde26ab651b92a129", 16)
g = int("0x2", 16)
A = int("0xdc5b63974ff0cefb", 16)
B = int("0x451b1bee7ea11770", 16)
iv = "30bac67ac581ad7f0fd0f0f7483feee0"
encrypted_flag = "1eed38849abbf30277c48f6fa894771461a1d7a01362e19c132e067530b62633"

a = discrete_log(p, A, g)
shared_secret = pow(B, a, p)

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')

print(decrypt_flag(shared_secret, iv, encrypted_flag))

`flag: crypto{d0wn6r4d35_4r3_d4n63r0u5}`

### Static Client

- Ở bài này ta có thể gửi {p, g, A} bất kỳ cho Bob. Vì Bob sẽ gửi thông báo lại với công thức: $B=g^{b}$ mod p và sẽ tính khóa bí mật `shared_secret` = $A^{b}$ mod p hoặc $B^{a}$ mod p nên thay vì gửi g như thường thì ta sẽ gửi `g=A` từ đó thông báo mà ta nhận được từ Bob $B=A^{b}$ mod p = `shared_secret` và ta sẽ giải được bài này.

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
p = int("0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", 16)
g = int("0x02", 16)
B = int("0x8d79b69390f639501d81bdce911ec9defb0e93d421c02958c8c8dd4e245e61ae861ef9d32aa85dfec628d4046c403199297d6e17f0c9555137b5e8555eb941e8dcfd2fe5e68eecffeb66c6b0de91eb8cf2fd0c0f3f47e0c89779276fa7138e138793020c6b8f834be20a16237900c108f23f872a5f693ca3f93c3fd5a853dfd69518eb4bab9ac2a004d3a11fb21307149e8f2e1d8e1d7c85d604aa0bee335eade60f191f74ee165cd4baa067b96385aa89cbc7722e7426522381fc94ebfa8ef0", 16)
shared_secret = int("0x2b22c28042690af9e5c530a93d8cede155e3df791dbaef4a1cdb1a53d98d92affaa331d7e7a567c694ad8c75576ec1a810b27bd678b81b4f4a5c299809131843057098810350793c2241ae6e2996ae938aa45946f859f114f4adf1998e57efbb0f585c13d763e8ded38b19034cd8af253026a04ed3eebd488770f26fbbd0f67ed0edb7a4152f7b8dfbb95376a4bbc30d8f80f509b5f2029d2c681db002c9360160b872109a7bda8fa395cb04bdfee7dd8f0b7e317ea79fde757cd62eb4b6f541", 16)
iv = "0e04b889dfaca930ec74c63185949963"
encrypted = "1a38b85fb3b47973cf2314c22803a4f34ab2688461f9f123afd19ee118aab257"
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')

print(decrypt_flag(shared_secret, iv, encrypted))

`flag: crypto{n07_3ph3m3r4l_3n0u6h}`

## GROUP THEORY
### Additive


- Ta thấy gợi ý của bài là việc Bob và Alice đã sử dụng nhóm $(G, +)$ thay vì $(G, *)$ nên các dữ liệu sẽ được tính như sau:
- A gửi cho B: $A = g*a$ mod p
- B gửi cho A: $B = g*b$ mod p
- Khóa bí mật chung: $Key = g*a*b$ mod p

- Từ đây ta có thể tính được a hoặc b và có thể tính được `Key`:
- $a = A*g^{-1}$ mod p
- $b = B*g^{-1}$ mod p

p = int("0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff" , 16)
g = int("0x02", 16)
print(g)
A = int("0x60bb4ec150cbc749bd41a8d2d858b34f87f47bb765f05b6798d934124dac1b44a0f091b2e8d47cdcf7e79af5ec83ba7836109d17bf1059b7c2e29a6f615c5a72f1c1f96c7702350cfd8e0e5fc6d3f1138f21f4566aae909f4d132c580dac7945cc761e3e54a2e38976ddf2e283796efce1115c668cfc540f2406c4be4434f29e01319faf7174b4cb7cb9c592cb3833f62c17ae55be5f1cd72085c2da47c58eebf32694cd7c8c980e3e3f25e2d973eb733e64ab43e49d37927778f9ef2b94f26e", 16)
B = int("0xd457c0257c4130cedd11777ccba24d85703c7c85bc1c156ebcf5e37b7a02ac40fdb5a821d30cc9e0eea5bbecb1a55ed1cd6fd9d72b3d31475feffc020df1a07fa4948fdbf2494cb4439f2b8d28d79e0951b93c2310c700f487eeef00146c528998aeccd506e4470d6991f1c49285da02f262219879230039cf45ef58b00082064d037953711981b2e0ef8007ed66decf4be592339d4dde3bdbc6b5058dab17310c6e4193e2052c1444df461d5b50ce7390739d5f1a4d61b4a1014024d385b593", 16)
iv = "a466b68f9fa2d641dc83a606f29d568e"
encrypted = "b8d1db24a63a0f77151973398e90bc5f95d2a11d7eb7c24e5787617b4f1fdbaa64e7c507802bd609078be1d7b4f753d8"
invert = pow(g, -1, p)
a = (A*invert)%p
shared_secret = (B*a)%p

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')

print(decrypt_flag(shared_secret, iv, encrypted))

`flag: crypto{cycl1c_6r0up_und3r_4dd1710n?}`

### Static Client 2

- Bài này cũng giống với bài `Static Client` nhưng ta không thể thực hiện truyền `g` to như bài trước. Bằng cách gửi `p` là `smooth number` thì ta có thể sử dụng thuật toán `Pohlig–Hellman` để có thể tìm được `b`.

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from sympy.ntheory.residue_ntheory import discrete_log
from Crypto.Util.number import isPrime
from random import choice

# def smooth_num():
#     smooth_p = 1
#     prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
#     while True:
#         smooth_p = smooth_p * choice(prime)
#         if smooth_p > p and isPrime(smooth_p + 1):
#             smooth_p = smooth_p + 1
#             break 
#     return hex(smooth_p)

p = int("0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", 16)
g = int("0x02", 16)
A = int("0x307a582c8073692983fb5c865e16521b42f192e78aeae0dbd0e74198a82760f3aadfc6a66483130ff37520c33b02ccb6d936edf7a1f9e609af03b101299acf6dc08ec47d95e72a00f4d53663fe33a35ea074b4b07fa3acebe6158604012098ea298bd626042be788937bdd5965f9937e4882417e1a1b3e850c8cdff6356974739646010957411640c57ce44d9cfebc400dd76dc4c15c7623ebeb02c18204efbefe9b459194ccee5b6e3df71c8ea087fc34b154be6d26e9e5bcdf159ec70dbc56", 16)
B = int("0xd0d69585c6586c3b1a23e04245826be6db4aed1c9bc70f7110a30165ca878d31434aa357c2bd26d3c398284a17319504e1aeead141234afeb57dfef11417fdec44b21cea83920f300f4e0c3fb573a895371b24652c5e6ea0539b7719f0f966ac7adb9a292cc49f4d8b39560e02fa82aab3c273cc7df512a80e2de6f0e8840c00554f09460eaa2e221173a9ca13182d4e1342b1e54965e16ca5fc23b1aae80aedc7fb80e1aa9be8b0274812676e8e570e1abf65eea0c49f18794a5afba975c7c7", 16)
iv = "8d0e5b2fc489d1607bf4c8e624a54b79"
encrypted = "64058d11263837c1af61fc27103a1be5a175ddc535559e208b00a1ee0c2cea0b9f8ea13decc9ca0dbaeb5fab37c62a06"

# p1 = int(smooth_num(), 16)
# print(hex(p1))
p1 = int("0x3fd467f209528a0662b47b9770b196aedac7588347994cde7d82b1c1aac9b0b433241226ba8cd6c236fa98838383841ac501e43d80df5bd009ee6e88ed5c97c69c28e6f5394bcfeb731a4ca564cab1a3af7a0640f9de214a45eec7f4a94864fad90a94ba7d25e876ef7a090ec3fa6f027ee7b39d4eb7d48066431c54c9000a0a9d50dcbf291ac8fd1d883b940995be3f8b6dc70eb056c950c135121e634d4f7d0b7cfbed6222ff7f103832307fbb270a9feefc5ec964fa26aa15df00f9e8f5e55dc3f5923a68e98b99dc11019c0c783f3a5820ed893ac13d71b951b31516925eafb2f74cdaf567f8c59243c3d3df1b1811c5b978a41b63a19986c46acd0ba1f59d985d53a633c6e58efcce0f49cec1ac07c125fc50f10d00000000001", 16)
B1 = int("0x3ef780908fb33b1d2385d65c9d9a1acea641ae4d18fba29d177d9e6fbceb0abddcba88fa77dd9ad0259d317f6c72f1bcc655bfb20221408ad5653df2966ec7eaacf0d9857e2585f49f060cf0b824ddb16beaf83f2380f2d7533bc08a647af8759414bf9a98606f91164066554ef7d6240208c506abf551b054f2d70d40c89db2c55d91c6dc55694bcfddca22430e5fb973f9c94d721308f610de598f65a927b794f78afb8ff62d8dd892d365123b33da029443831733b92d75122de26ab408e6882889cd9cea2eb988e9932238b3a311c74a09aa94c92964b83f488fc61ac174be9bf47fb28d5e54b037de5e43bec97d1d7154df6112c9bb57a2c811aee56a69aa0997d0a4aadd7ea5285330f2ad163500905837f52a317b9c18d8624", 16)


b = discrete_log(p1, B1, g)
shared_secret = pow(A, b, p)

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')

print(decrypt_flag(shared_secret, iv, encrypted))

`flag: crypto{uns4f3_pr1m3_sm4ll_oRd3r}`