---
# System prepended metadata

title: 'Cryptohack Part 4: DIFFIE-HELLMAN.'
tags: [CryptoHack]

---

# STARTER
## Diffie-Hellman Starter 1
![image](https://hackmd.io/_uploads/rJApW-Xnp.png)
- Chall yêu cầu ta tìm d= inverse(g, p).
- Ta có thể sử dụng Euclid mở rộng để tìm hoặc sử dụng hàm trong python để tìm d.
```python
g= 209
p= 991
d= pow(g,-1 , p)
print(d)
```
![image](https://hackmd.io/_uploads/H1cqXWQhT.png)
- Flag: `569`

## Diffie-Hellman Starter 2
![image](https://hackmd.io/_uploads/S1jCm-mha.png)
- Chall yêu cầu ta tìm phần tử sinh nhỏ nhất trong trường $F_p$ hay đơn giản hơn là tìm g thỏa mãn: $g= g^n\ mod(p)$.
```python
def find(g, p):
  for n in range(2, p):
    if pow(g, n, p) == g:
      return False
  return True

p = 28151
for g in range(p):
  if find(g, p):
    print(g)
    break
```
- Flag: `7`

## Diffie-Hellman Starter 3
![image](https://hackmd.io/_uploads/HkMhBZm3T.png)
- Chall yêu cầu ta tình $g^a\ mod(p)$
```Python
a=  972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
p=  2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g= 2
flag= pow(g, a, p)
print(flag)
```
- Flag: `1806857697840726523322586721820911358489420128129248078673933653533930681676181753849411715714173604352323556558783759252661061186320274214883104886050164368129191719707402291577330485499513522368289395359523901406138025022522412429238971591272160519144672389532393673832265070057319485399793101182682177465364396277424717543434017666343807276970864475830391776403957550678362368319776566025118492062196941451265638054400177248572271342548616103967411990437357924`

## Diffie-Hellman Starter 4
![image](https://hackmd.io/_uploads/ry848Zm3a.png)
- Ta có giá trị nhận được từ Alice là như sau: $A= g^a mod(p)$.
- Tương tự ta sẽ có $B= g^b mod(p)$.
- Ta cần có khóa chung tạm gọi là key: $key= g^{ab} mod(p)$ <=> $key= A^b mod(p)$
```Python
A = 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
b = 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
print(pow(A,b,p))
```
- Flag: `1174130740413820656533832746034841985877302086316388380165984436672307692443711310285014138545204369495478725102882673427892104539120952393788961051992901649694063179853598311473820341215879965343136351436410522850717408445802043003164658348006577408558693502220285700893404674592567626297571222027902631157072143330043118418467094237965591198440803970726604537807146703763571606861448354607502654664700390453794493176794678917352634029713320615865940720837909466`

## Diffie-Hellman Starter 5
![image](https://hackmd.io/_uploads/SkmPsbXh6.png)
- Chall này flag bị encrypt bằng AES mode CBC với key= share_secret.
```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):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    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')

g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A= 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
B= 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581
shared_secret = pow(A,b,p)
iv = '737561146ff8194f45290f5766ed6aba'
ciphertext= '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'

print(decrypt_flag(shared_secret, iv, ciphertext))
```
- Flag: `crypto{sh4r1ng_s3cret5_w1th_fr13nd5} `

# MAN IN THE MIDDLE
## Parameter Injection
![image](https://hackmd.io/_uploads/B1NlkM73T.png)
- Chall này kêu ta sử dụng source của chall `Diffie-Hellman Starter 5`.
- Tuy nhiên có một điểm khác là ở đây `B= 1` nên `shared_secret= 1`.
```Python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from pwn import *
import json
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):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    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')

r = remote("socket.cryptohack.org", 13371)
r.recvuntil("Send to Bob:")
r.sendline(b'{"p":"0x01", "g":"0x02", "A":"0x03"}')
r.recvuntil("Intercepted from Bob: ")
r.sendline(b'{"B":"0x01"}')
r.recvuntil(b"Intercepted from Alice: ")
recv = r.readline().strip()
recv= json.loads(recv)
iv = recv["iv"]
ciphertext = recv["encrypted_flag"]
shared_secret = 1
print(decrypt_flag(shared_secret, iv, ciphertext))
```
- Flag: `crypto{n1c3_0n3_m4ll0ry!!!!!!!!}  `

## Export-grade
![image](https://hackmd.io/_uploads/r1ekQGm26.png)
```Python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from pwn import *
import json
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):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    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')

r = remote("socket.cryptohack.org", 13379)
r.recvuntil("Send to Bob:")
r.sendline(b'{"supported": ["DH64"]}')
r.recvuntil("Send to Alice:")
r.sendline(b'{"chosen": "DH64"}')
r.recvuntil(b"Intercepted from Alice: ")
recv = r.readline().strip()
recv= json.loads(recv)
p= int(recv["p"], 16)
g= int(recv["g"], 16)
A= int(recv["A"], 16)
r.recvuntil(b"Intercepted from Bob: ")
recv = r.readline().strip()
recv= json.loads(recv)
B= int(recv["B"], 16)
r.recvuntil(b"Intercepted from Alice: ")
recv = r.readline().strip()
recv= json.loads(recv)
iv= recv["iv"]
ciphertext= recv["encrypted_flag"]
# for a in range(1000):
#     x= pow(g, a)% p
#     if x== A:
#         print(a)
#         break
from sympy.ntheory.residue_ntheory import *
a = discrete_log(p, A, g) 
shared_secret = pow(B, a, p)
print(decrypt_flag(shared_secret, iv, ciphertext))
```
- Flag: `crypto{d0wn6r4d35_4r3_d4n63r0u5}`

## Static Client
![image](https://hackmd.io/_uploads/ry4BXXX3a.png)
- Chall này vẫn như những chall trước tuy nhiên khi ta có thể tương tác với Bob để lấy được nhiều thông tin hơn.
- Cụ thể với chall này, nếu ta gửi cho Bob bộ 3 thông tin (p, g, A) với (p= p, g= A, A= 1) thì ta sẽ nhận được B mà B sẽ chính bằng secret. 
```Python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from pwn import *
import json
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):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    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')

r = remote("socket.cryptohack.org", 13373)
r.recvuntil(b"Intercepted from Alice: ")
recv = r.readline().strip()
recv= json.loads(recv)
p= recv["p"]
g= int(recv["g"], 16)
A= recv["A"]
r.recvuntil(b"Intercepted from Bob: ")
recv = r.readline().strip()
recv= json.loads(recv)
B= int(recv["B"], 16)
r.recvuntil(b"Intercepted from Alice: ")
recv = r.readline().strip()
recv= json.loads(recv)
iv= recv["iv"]
ciphertext= recv["encrypted"]
r.recvuntil("Bob connects to you, send him some parameters: ")
r.sendline(json.dumps({"p": p, "g": A, "A": "0x01"}))
r.recvuntil("Bob says to you: ")
recv = r.readline().strip()
recv= json.loads(recv)
shared_secret= int(recv["B"], 16)
print(decrypt_flag(shared_secret, iv, ciphertext))
```
- Flag: `crypto{n07_3ph3m3r4l_3n0u6h}  `

# GROUP THEORY
## Additive
![image](https://hackmd.io/_uploads/SyxzA7726.png)
- Với chall này ta sẽ sử dụng DHKE ở nhóm  cộng.
- Khi đó $a= Ag^{-1}\ mod(p)$; $secret= aB\ mod(p)$
```Python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from pwn import *
import json
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):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    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')

r = remote("socket.cryptohack.org", 13380)
r.recvuntil(b"Intercepted from Alice: ")
recv = r.readline().strip()
recv= json.loads(recv)
p= int(recv["p"], 16)
g= int(recv["g"], 16)
A= int(recv["A"], 16)
r.recvuntil(b"Intercepted from Bob: ")
recv = r.readline().strip()
recv= json.loads(recv)
B= int(recv["B"], 16)
r.recvuntil(b"Intercepted from Alice: ")
recv = r.readline().strip()
recv= json.loads(recv)
iv= recv["iv"]
ciphertext= recv["encrypted"]
a = A * pow(g, -1 , p)
shared_secret = (B * a) % p
print(decrypt_flag(shared_secret, iv, ciphertext))
```
- Flag: `crypto{cycl1c_6r0up_und3r_4dd1710n?}`

## Static Client 2
![image](https://hackmd.io/_uploads/BJ_RB4m26.png)
- Với chall này ta nhận thấy không thể giải như chall `Static Client` do đã Bob đã nghi ngờ thông tin ta gửi đến. Nên ta sẽ phải làm cách khác.
- Ta sẽ thử sử dụng `Pohlig_hellman` để làm.
```Python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from pwn import *
import json
from Crypto.Util.number 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):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    try:
        return plaintext.decode('ascii')
    except UnicodeDecodeError:
        try:
            return plaintext.decode('utf-8')
        except UnicodeDecodeError:
            return str(plaintext)

def smooth_p():
    Smooth_p = 1
    i = 2
    while Smooth_p < p or not isPrime(Smooth_p+1):
        Smooth_p *= i
        i += 1
    Smooth_p += 1
    return Smooth_p
r = remote("socket.cryptohack.org", 13378)
r.recvuntil(b"Intercepted from Alice: ")
recv = r.readline().strip()
recv= json.loads(recv)
p= int(recv["p"], 16)
g= recv["g"]
A= recv["A"]
r.recvuntil(b"Intercepted from Bob: ")
recv = r.readline().strip()
recv= json.loads(recv)
B= int(recv["B"], 16)
r.recvuntil(b"Intercepted from Alice: ")
recv = r.readline().strip()
recv= json.loads(recv)
iv= recv["iv"]
ciphertext= recv["encrypted"]
p1= smooth_p()
r.recvuntil("Bob connects to you, send him some parameters: ")
r.sendline(json.dumps({"p": hex(p1), "g": g, "A": A}))
r.recvuntil("Bob says to you: ")
recv = r.readline().strip()
recv= json.loads(recv)
B= int(recv["B"], 16)
from sympy.ntheory.residue_ntheory import *
b= discrete_log(p1, B, 2)
shared_secret= pow(int(A, 16), b, p)
print(decrypt_flag(shared_secret, iv, ciphertext))
```
![image](https://hackmd.io/_uploads/Hy3okrmn6.png)

- Flag: `crypto{uns4f3_pr1m3_sm4ll_oRd3r}  `