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

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

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

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

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

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

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

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

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

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

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

- 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

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

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

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}`