---
# System prepended metadata

title: '[WRITE UP ] Cryptohack - Diffie Hellman'

---

# [WRITE UP ] Cryptohack - Diffie Hellman

## 1. Diffie-Hellman Starter 1
![](https://i.imgur.com/i5YYK5a.png)

**result** : 569

## 2. Diffie-Hellman Starter 2

![](https://i.imgur.com/zR9szha.png)

Mình sẽ tìm g sao cho g^n mod p = g (1<g<p)

```python=
def is_generator(k, p):
  for n in range(2, p):
    if pow(k, n, p) == k:
      return False
  return True

p = 28151
for k in range(p):
  if is_generator(k, p):
    print(k)
    break
```
**result :** 7

## 3. Diffie-Hellman Starter 3
![](https://i.imgur.com/RvvlnOM.png)

solve.py
```python=
g =2
p=2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
a=972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
print(pow(g,a,p))
```
**result:** 
:::success
1806857697840726523322586721820911358489420128129248078673933653533930681676181753849411715714173604352323556558783759252661061186320274214883104886050164368129191719707402291577330485499513522368289395359523901406138025022522412429238971591272160519144672389532393673832265070057319485399793101182682177465364396277424717543434017666343807276970864475830391776403957550678362368319776566025118492062196941451265638054400177248572271342548616103967411990437357924
:::
## 4. Diffie-Hellman Starter 4

![](https://i.imgur.com/9MGC9nD.png)

Như trong hình thì mình có thể nhận thấy đây là giao thức trao đổi chìa khóa Diffie - Hellman.

Để thực hiên giao thức này, ta cần có : 
* Người A có 1 số a 
* Người B có 1 số b
* a, b là 2 số private 
* g,p là 2 số public

Sau đó : 
* C~A~ = g^a^ mod p
* C~B~ = g^b^ mod p
* A và B sẽ trao đổi C~A~ và C~B~ cho nhau

Biến đổi : 
* Người A sẽ tính như sau:

(C~B~)^a^ mod P = (g^b^)^a mod P = g^ab^ mod P = K

* Người B sẽ tính như sau: 

(C~A~)^b^ mod P = (g^a^)^b mod P = g^ab^ mod P = K

Như vậy A và B không cần gửi K nhưng vẫn có được K :cat: 

Và đây cũng chính là cách mà mình dùng để giải challenge trên =)) 

```python=
g = 2

p=2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A =70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
b = 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720

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

```
**result:** 
:::success
1174130740413820656533832746034841985877302086316388380165984436672307692443711310285014138545204369495478725102882673427892104539120952393788961051992901649694063179853598311473820341215879965343136351436410522850717408445802043003164658348006577408558693502220285700893404674592567626297571222027902631157072143330043118418467094237965591198440803970726604537807146703763571606861448354607502654664700390453794493176794678917352634029713320615865940720837909466
:::

## 5. Diffie-Hellman Starter 5

![](https://i.imgur.com/G1TtUFp.png)

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

```
Nhìn vào ảnh trên thì mình biết việc đầu tiên cần làm chính là tìm khóa được trao đổi.

Sau khi có được khóa thì dựa vào source để tìm flag. Cụ thể là khóa sẽ được hash và chỉ lấy 16 bytes đầu để làm khóa , sau đó flag sẽ được pad và mã hóa bằng AES.CBC. 

Giờ mình đã có khóa, IV, và ciphertext nên giờ chỉ cần làm ngược lại so với chu trình mã hóa là sẽ có được flag :smiley_cat: 

solve.py
```pyhton=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A= 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
B= 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581
shared_secret = pow(A,b,p)
iv = '737561146ff8194f45290f5766ed6aba'
encrypted_flag = '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'

sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
ct = bytes.fromhex(encrypted_flag)
iv = bytes.fromhex(iv)
cipher = AES.new(key,AES.MODE_CBC,iv)
flag = cipher.decrypt(ct)
print(flag)
#crypto{sh4r1ng_s3cret5_w1th_fr13nd5}
```
**flag:** crypto{sh4r1ng_s3cret5_w1th_fr13nd5}