---
# System prepended metadata

title: 'CRYPTOHACK Writeup: Diffie-Hellman (Author: dpduy123)'

---


# CRYPTOHACK Writeup: Diffie-Hellman (Author: dpduy123)

## Starter 

### Diffie-hellman starter 1
- Đề bài yêu cầu tìm d sao cho g * d mod p = 1
-> d = inverse(d, p)

```python = 0
from factordb.factordb import FactorDB
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD

def get_phi(N):
  f = FactorDB(N)
  f.connect()
  f2 = list(f.get_factor_list())
  f_dict = {}

  phi = 1
  for u in f2:
    if u in f_dict:
      phi *= u
    else:
      f_dict[u] = 1
      phi *= u-1
  return phi

print(get_phi(get_phi(28151)))
```

Flag: `11240`
### Diffie-hellman starter 2
- Đề bài yêu cầu tìm nghiệm nguyên thủy nhỏ nhất của một tập số được sinh bởi số nguyên tố p = 28151 (1->p-1). Có thể brute-force từng số để tìm kết quả nhưng khi sử dụng một vài chứng minh toán học có thể khiến thời gian tìm kiếm ngắn hơn rất nhiều

```python = 0 
from factordb.factordb import FactorDB
from Crypto.Util.number import *

p = 28151

f = FactorDB(p - 1) 
f.connect() 
f2 = list(f.get_factor_list()) 
sorted(f2, reverse = True) 

for i in range(1, p): 
    g = i
    ok = True
    for u in f2: 
        if pow(i, (p - 1) // u, p) == 1:
            ok = False 
            break
        if ok == True:
            print(g) 
            exit()
```
Flag: `7`
### Diffie-hellman starter 3
-	Đề bài cho 3 số g, a, p. Yêu cầu tính g^a mod p.
-	Đề bài còn giới thiệu cách chọn key sao cho mã hóa được tiện lợi và an toàn nhất 

```python = 0
from factordb.factordb import FactorDB
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD
g= 2

p= 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919

a = 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815

print(pow(g, a, p))
```

Flag:`1806857697840726523322586721820911358489420128129248078673933653533930681676181753849411715714173604352323556558783759252661061186320274214883104886050164368129191719707402291577330485499513522368289395359523901406138025022522412429238971591272160519144672389532393673832265070057319485399793101182682177465364396277424717543434017666343807276970864475830391776403957550678362368319776566025118492062196941451265638054400177248572271342548616103967411990437357924`

### Diffie-hellman starter 4
-	Đề bài sử dụng việc trao đổi khóa bằng giao thức Diffie-hellman
-	Alice sẽ đưa cho ta giá trị A = g^a mod p
-	Ta sẽ có B = g^b mod p và 1 private key b
-	Sử dụng công thức A^b mod p= g^(ab) mod p = Flag => ta có thể có được Flag chỉ với A, public key g, p và private key của bản thân

```python = 0
from factordb.factordb import FactorDB
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD
g= 2

p= 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919


A= 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601

b= 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720

B= 518386956790041579928056815914221837599234551655144585133414727838977145777213383018096662516814302583841858901021822273505120728451788412967971809038854090670743265187138208169355155411883063541881209288967735684152473260687799664130956969450297407027926009182761627800181901721840557870828019840218548188487260441829333603432714023447029942863076979487889569452186257333512355724725941390498966546682790608125613166744820307691068563387354936732643569654017172
print(pow(A, b, p))
```

Flag: `1174130740413820656533832746034841985877302086316388380165984436672307692443711310285014138545204369495478725102882673427892104539120952393788961051992901649694063179853598311473820341215879965343136351436410522850717408445802043003164658348006577408558693502220285700893404674592567626297571222027902631157072143330043118418467094237965591198440803970726604537807146703763571606861448354607502654664700390453794493176794678917352634029713320615865940720837909466`
### Diffie-hellman starter 5
-	Đề bài cho các thông số A, B, g, p, b và iv, encrypt_text và 1 file source.py. Tìm ra được secret_key như cách bài trên và giải mã ngược lại theo như file source để tìm ra 

```python = 0
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
g: 2

p= 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919

A= 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784

b= 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944

B= 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581

iv = '737561146ff8194f45290f5766ed6aba'
encrypted_flag = '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'

shared_secret = pow(A, b, p)
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
ciphertext = bytes.fromhex(encrypted_flag)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)   
flag = cipher.decrypt(ciphertext)
print(flag)
```
Flag: `crypto{sh4r1ng_s3cret5_w1th_fr13nd5}`

## MAN IN THE MIDDLE 

### Parameter Injection
- Kết nối socket.cryptohack.org 13371


![Pi1](https://hackmd.io/_uploads/rkeUgdKe0.png)
-	Khi ta gửi Bob {p, g, A} được chuyển đổi từ hex sang int thì Bob sẽ gửi lại cho ta B, iv và encrypted_flag.
-	Bây giờ thì ta chỉ cần giải mã giống như bài Diffie-Hellman Starter 5.
```python = 0
import pwn
import json
import hashlib
from Crypto.Cipher import AES

host = "socket.cryptohack.org"
port = 13371

def exploit():
    pr = pwn.connect(host, port)
    try:
        pr.readuntil(": ")
        line = json.loads(pr.readline().strip().decode())
        #p = int(line['p'][2:].strip('f'), 16)
        p = int(line['p'], 16)
        g = int(line['g'], 16)
        A = int(line['A'], 16)

        payload = json.dumps({"p":hex(p),"g":hex(g),"A":hex(p)})
        print(payload, len(payload))
        pr.sendlineafter(": ", payload)

        pr.readuntil(": ")
        line = json.loads(pr.readline().strip().decode())
        B = int(line['B'], 16)

        payload = json.dumps({"B":hex(p)})
        print(payload, len(payload))
        pr.sendlineafter(": ", payload)

        pr.readuntil(": ")
        line = json.loads(pr.readline().strip().decode())
        print(line)

        iv = bytes.fromhex(line['iv'])
        encrypted_flag = bytes.fromhex(line['encrypted_flag'])
        sha1 = hashlib.sha1()
        secret = 0
        sha1.update(str(secret).encode())
        key = sha1.digest()[:16]
        aes = AES.new(key, AES.MODE_CBC, iv)
        print(aes.decrypt(encrypted_flag))
    finally:
        pr.close()

exploit()
```
Flag: `crypto{n1c3_0n3_m4ll0ry!!!!!!!!}`

### Export-grade
-	Kết nối socket.cryptohack.org 13379 (chọn DH64) để lấy p, g, A, B, iv và encrypted_flag.
![Picture1](https://hackmd.io/_uploads/HkDhd_YlR.png)
- 	Giải secret_key của Alice hoặc Bob rồi sau đó có được khóa thì mình chỉ cần giải mã theo đúng trình tự của AES.mode_CBC là ra được flag.
```python = 0
p = "0xde26ab651b92a129"
g = "0x2"
A = "0x7854d1676ca1d252"
B = "0x254a8bf94895190c"
iv =  "b32980767d8d4c299634b787ab6e6096"
encrypted_flag = "d468c7d63632acb966b75ec66ebc0f8d1995c8d7eeddcd88dc5e0e0a7491767d"

p = int(p, 16)
g = int(g, 16)
A = int(A, 16)
B = int(B, 16)
iv = bytes.fromhex(iv)
encrypted_flag = bytes.fromhex(encrypted_flag)

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

def decrypt(secret, iv, cipher):
    sha1 = hashlib.sha1()
    sha1.update(str(secret).encode())
    key = sha1.digest()[:16]
    aes = AES.new(key, AES.MODE_CBC, iv)
    plain = aes.decrypt(cipher)
    print(plain)

"""
A = pow(g, a, p)
B = pow(g, b, p)
ka = pow(B, a, p)
kb = pow(A, b, p)
"""

# Tính key của Alice (a) bang92 Discrete logarithm tại https://www.alpertron.com.ar/DILOG.HTM 
a = 146150597243831982  
Flag = pow(B, a, p)
decrypt(Flag, iv, encrypted_flag)
```
Flag: `crypto{d0wn6r4d35_4r3_d4n63r0u5}`

### Static Client
-	Kết nối socket.cryptohack.org 13373 

![Picture1](https://hackmd.io/_uploads/S1qwc_FxR.png)
-	Ta biết rằng sau khi gửi parameter(p,g,A) thì Bob sẽ gửi lại B = g^b (Mod P). Vậy nếu mình thay g = A, p giữ nguyên và A là số gì cũng được thì Bob sẽ gửi lại A^b (mod P) và đây chính là khóa mình cần tìm :))
-	Có được khóa thì mình chỉ cần giải mã theo đúng trình tự của AES.mode_CBC là ra được flag.
```python = 0
import json
from pwn import *
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad,unpad

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

con=remote('socket.cryptohack.org',13373,level='debug')
con.recvuntil(b'Intercepted from Alice: ')
alice=json.loads(con.recvline())
p_hex,g_hex,A_hex=alice['p'],alice['g'],alice['A']
con.recvuntil(b'Intercepted from Bob: ')
B_hex=json.loads(con.recvline())['B']
con.recvuntil(b'Intercepted from Alice: ')
content=json.loads(con.recvline())
iv_hex,enc_flag_hex=content['iv'],content['encrypted']
to_bob={"p":p_hex,"g":A_hex,"A":'0x1'}
con.sendline(json.dumps(to_bob))
con.recvuntil(b'Bob says to you: ')
shared_secret=int(json.loads(con.recvline())['B'],16)
con.recvline()

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_hex, enc_flag_hex))
```

Flag: `crypto{n07_3ph3m3r4l_3n0u6h}`


## GROUP THEORY 
### Additive
-	Kết nối socket.cryptohack.org 13380

![Picture1](https://hackmd.io/_uploads/r1ugjdYlR.png) 
-	Ta nhận được p, g, A, B, iv, và encrypted.
-	Ở bài này, Alice và Bob trao đổi với nhau qua giao thức Diffie-Hellman nhóm cộng (Z, +) thay vì nhóm nhân như mọi khi nên ta sẽ không dùng Discrete Logarithm để tìm secret_key (a) của Alice mà sẽ dùng tính chất theo nhóm (Z,+) ta có:
		a = A * (g ^ (-1) mod p) mod p

```python = 0
p = "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff"
g = "0x2"
A = "0x464a9c516d7eed0df5222a109536fc47a37658c5917f7e49f3aa41b187479640f87413a21eabfa2f75ea7d6c653e3ae6bff686a2a29f23480eedbb333fff37129f059baebb28a52dfdab16366830c4735b56dd9602fb2e0cddafa05d59ac73062cb4ce18f1e758ed67450fda1288cf5510e49f5751a59df0454479b64d3ac9fc2276862899d5a10162b627d1b956c82ed3adae06daf05b55abd97998e39906db9635eb8f9de1147960f306725b8d11b3474d1422407319bb1246892e1fed3545"
B = "0xaef0201c204c8e70d1bd68cfe8fc9aef77f83759f01c0fe59c829da3486cc788815a7bba11f68998570e6ce7bf63be2178d050f0d7d4894062a41afbe8c556826772e1d97c1eba8e5955165e8cf422f26305ac572fc0f9015a73803e869ef2c5b0a1f1f4b7e482600e5fdcf6b6779aead2e1176fe6f9dab1d0a0b67893fb9ac3954e52cd39200b374ca777c16366bb3cbd55e84983563cc46eca0c4e101011429e7528735fb3a2d83469b5d5b7053232c957d4d22f2dba2456f8144a73728c88"
iv =  "25ceab008787a8fa353ec21a70599963"
encrypted_flag = "8ec2aab10681db61d7aaaa7f903425ed9554b70544d5665fb632476248c5490987ac68d0223461b1ecc1cb526c1bce45"

p = int(p, 16)
g = int(g, 16)
A = int(A, 16)
B = int(B, 16)
iv = bytes.fromhex(iv)
encrypted_flag = bytes.fromhex(encrypted_flag)

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

def decrypt(secret, iv, cipher):
    sha1 = hashlib.sha1()
    sha1.update(str(secret).encode())
    key = sha1.digest()[:16]
    aes = AES.new(key, AES.MODE_CBC, iv)
    plain = aes.decrypt(cipher)
    print(plain)

"""
A = pow(g, a, p)
B = pow(g, b, p)
ka = pow(B, a, p)
kb = pow(A, b, p)
"""

a = (A * inverse(g, p)) % p
Flag = B * a % p 
decrypt(Flag, iv, encrypted_flag)
```

Flag: `crypto{cycl1c_6r0up_und3r_4dd1710n?}`

### Static Client 2 
-	Kết nối socket.cryptohack.org 13378 

![Picture1](https://hackmd.io/_uploads/ByTsi_tgA.png)
-	Chall bài này có vẻ giống với bài Static Client tuy nhiên thì dùng cách giải như bài trên sẽ không hiệu quả nên ở đây mình thay đổi parameters cho Bob như sau: 
-	     G' = 2
	     P’ = P' - 1 là smooth-number và P' > P
	     A' = A
-	Sau khi gửi, ta nhận lại từ Bob B = g^b mod (smooth p). Với cách chọn p' như trên cho chúng ta có thể áp dụng thuật toán Pohlig–Hellman để giải quyết bài toán logarit rời rạc B từ đó tìm được b.

```python = 0
from Crypto.Util.number import *
from pwn import *
from sympy.ntheory.residue_ntheory import discrete_log
from json import *

r = remote("socket.cryptohack.org", 13378)

A_data = loads(r.recvline().split(b":", 1)[1])
B_data = loads(r.recvline().split(b":", 1)[1])
cipher = loads(r.recvline().split(b":", 1)[1])
p = int(A_data["p"], 16)
A = int(A_data["A"],16)

i = 2
smooth_p = 1
while smooth_p < p or not isPrime(smooth_p + 1):
    smooth_p *= i
    i += 1
smooth_p += 1
print("P' = ", smooth_p) 

r.sendline(dumps({
    "g":"0x02",
    "A": hex(A),
    "p": hex(smooth_p)
}).encode())
B = int(r.recvline().decode().split()[13][1:-2],16)
b = discrete_log(smooth_p, B, 2)
shared_secret = pow(A, b, 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):
    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()
    else:
        return plaintext 

print(decrypt_flag(shared_secret, cipher["iv"], cipher["encrypted"]))
```

Flag: `crypto{uns4f3_pr1m3_sm4ll_oRd3r}`