# DiffieHellman
- DiffieHellman.py
```python=
from Crypto.Util.number import *
from secrets import randbelow
flag = b'BSidesIndore{?????????????????????????????????????????}'
p = getPrime(1024)
a = randbelow(p)
b = randbelow(p)
s = randbelow(p)
#private_key
na = randbelow(p)
nb = randbelow(p)
def f(z):
return (a * z + b) % p
def compose_f(z , n):
for _ in range(n):
z = f(z)
return z
#public_key
A = compose_f(s, na)
B = compose_f(s, nb)
shared_secret = compose_f(A, nb)
assert compose_f(B, na) == shared_secret
m = bytes_to_long(flag)
hint = (shared_secret * m) % p
print('p=' , p)
print('a=' , a)
print('b=' , b)
print('s=', s)
print('A=' , A)
print('B=' , B)
print('Hint=' , hint)
```
- output.txt
```
p= 177570430264404042586947209415361175829662877465021738163452003044204801236884005980142784114098378718171232421758262680024168974955507208327903586791589504974287563947107311706980541752128561476280897335081377540882450802053121704994636737618193754484639531123445136371629051163053932580571940280678765406507
a= 43956506117080063425552748919558963635605098605326775979012360863142443520592114771800350897421485025125720482734237579881628822814442838128036568093867197695237846018696049279357474258871874227658474923562729861151927356523476281314556495465881999078214836635672825087229897489780543610449600598310975845972
b= 174696548246270768822111154128350984851623375416115231737870633294112190977226571494266879050596220994493007232484609234595354342745045435123046789963360269847186352233769676144998148572751650872487364118516515673999802276136983028240521720649825627376559451556059366974145722267864743175103312487712498074749
s= 12434113186075391543764483911407788417903733970619704242876093325272607987251561194578833768854877839420807906348010197072863684238585629167767699669787141090172275735228322001099182693707345110444778401752303810786206722286874416348628222046081716777562273093345200683040455119310424421838556869940942435673
A= 136407737305511360356397851151387434747104130517942844746307421591300142246172197908094415745159427162154420196514774405243398839327050657296253147517687400701852380101057349604958670296473446404895687124842088949969419486055881611144671929238142825450181746276221000200846658169851653919504352250739069860730
B= 26467203262894711969159457169326125007000815712021405657352754729857627693311672965448787149024723113418146398326650495992712486220869311766554396353531102926524277200284073965641737905200427505698807999274743916487363108331073718034682818342814978156028844309220276666373635341609073539725142950450555754476
Hint= 111835764538968835283671465944316573442933510238606935593825235958809709981307851841392212790079210442271736305104653249935653746189422754282042111667903170916672655913492221169563628845786374370984595021502163203501215307272819616639858055813062468690363664768682360975293577533019188775265576784532652545007
```
- Đoạn code trên mô tả lại giao thức trao đổi khóa Diffie-Hellman (DH) để tạo ra một khóa chia sẻ (shared_secrets) giữa hai bên trao đổi thông tin (nếu bạn không rõ về nó thì có thể đọc thêm tại [đây](https://vi.wikipedia.org/wiki/Trao_%C4%91%E1%BB%95i_kh%C3%B3a_Diffie-Hellman))
- Bài này thay vì tính toán trong một multiplicative group như các bài DH thông thường thì họ sử dụng [LCG](https://en.wikipedia.org/wiki/Linear_congruential_generator) (Linear congruential generator). Qua đoạn code thì ta thấy:
- Đề bài cho một hàm `f(x) = ax + b mod p`
- Tính $A = f_{n_B}(s)$, $B = f_{n_A}(s)$ với $f_n(x) = f(f(..(f(x))))$ (n hàm f)
- Tính shared_secret = $f_{n_B}(A)$ hoặc $f_{n_A}(B)$
- Tính `hint = (shared_secret * m) mod p` với m là `bytes_to_long(flag)`
- Mấu chốt ở đây mình phải tìm được `shared_secret`. Dễ thấy shared_secret = $f_{n_A+n_B}(s)$ nên ý tưởng ban đầu là phải tìm bằng được 2 số n_A và n_B
- Mình sẽ thực hiện biến đổi một tí (lưu ý mình đang biến đổi trên Fp):
$f_1(x) = ax + b$
$f_2(x) = a(ax + b) + b = a^2x + ab + b$
$f_3(x) = a(a^2x+ab+b)+b = a^3x + a^2b + ab + b$
...
Ta có thể dự đoán: $f_n(x) = a^nx + a^{n-1}b + a^{n-2}b+ ... + ab + b$
Thực hiện biến đổi một tí cho gọn nào:
$(a-1).(f_n(x) - x) = (a-1)(a^nx -x + a^{n-1}b + a^{n-2}b+ ... + ab + b)$
$= (a-1).x(a^n-1) + b(a^n-1)$
$= (a^n-1)(b+x(a-1))$
Vì vậy, từ $A = f_{n_B}(s)$ suy ra $(a-1)(A-s) = (a^{n_B}-1)(s(a-1) + b)$
$\Rightarrow a^{n_B} = (a-1).(A-s).(s(a-1)+b)^{-1} + 1$
Mình cũng sẽ tìm được $a^{n_A}$ theo cách tương tự.
- Để tìm được $n_A, n_B$, mình phải giải bài toán [DLP](https://en.wikipedia.org/wiki/Discrete_logarithm) và tất nhiên nó là bài toán khó.Tuy nhiên để ý rằng:
shared_secret = $f_{n_A+n_B}(s) = (a^{n_A+n_B}-1)(s(a-1)+b).(a-1)^{-1}+s$
Dễ dàng tính được $a^{n_A+n_B} = a^{n_A}.a^{n_B}$, vì vậy mình có thể tìm shared_secret mà không cần tìm $n_A,n_B$.
- Vậy là xong phần ý tưởng rồi, code thôi ^^
```python=
p= 177570430264404042586947209415361175829662877465021738163452003044204801236884005980142784114098378718171232421758262680024168974955507208327903586791589504974287563947107311706980541752128561476280897335081377540882450802053121704994636737618193754484639531123445136371629051163053932580571940280678765406507
a= 43956506117080063425552748919558963635605098605326775979012360863142443520592114771800350897421485025125720482734237579881628822814442838128036568093867197695237846018696049279357474258871874227658474923562729861151927356523476281314556495465881999078214836635672825087229897489780543610449600598310975845972
b= 174696548246270768822111154128350984851623375416115231737870633294112190977226571494266879050596220994493007232484609234595354342745045435123046789963360269847186352233769676144998148572751650872487364118516515673999802276136983028240521720649825627376559451556059366974145722267864743175103312487712498074749
s= 12434113186075391543764483911407788417903733970619704242876093325272607987251561194578833768854877839420807906348010197072863684238585629167767699669787141090172275735228322001099182693707345110444778401752303810786206722286874416348628222046081716777562273093345200683040455119310424421838556869940942435673
A= 136407737305511360356397851151387434747104130517942844746307421591300142246172197908094415745159427162154420196514774405243398839327050657296253147517687400701852380101057349604958670296473446404895687124842088949969419486055881611144671929238142825450181746276221000200846658169851653919504352250739069860730
B= 26467203262894711969159457169326125007000815712021405657352754729857627693311672965448787149024723113418146398326650495992712486220869311766554396353531102926524277200284073965641737905200427505698807999274743916487363108331073718034682818342814978156028844309220276666373635341609073539725142950450555754476
Hint= 111835764538968835283671465944316573442933510238606935593825235958809709981307851841392212790079210442271736305104653249935653746189422754282042111667903170916672655913492221169563628845786374370984595021502163203501215307272819616639858055813062468690363664768682360975293577533019188775265576784532652545007
# from sympy.ntheory import discrete_log
from Crypto.Util.number import *
def decompose_f(C):
ans = (C - s) % p
ans = (ans * (a-1) * pow(b + (a-1)*s, -1,p) + 1) % p
# assert (ans - 1) * (s*(a-1)+b) % p == (a-1)*(C - s) % p
return ans
pow_nb = decompose_f(A)
pow_na = decompose_f(B)
shared_secret = ((pow_na * pow_nb - 1) * (s*(a-1) + b) * pow(a-1,-1,p) + s) % p
# assert (a-1)*(shared_secret - s)% p == (pow_nb * pow_na -1) * (s*(a-1) + b) % p
m = Hint * pow(shared_secret, -1, p) % p
print(long_to_bytes(m))
# BSidesIndore{yOu_5hou1D_7ry_S0M3ThIn9_elSe_o7h3r_TH4n_lcg}
```
- Flag: `BSidesIndore{yOu_5hou1D_7ry_S0M3ThIn9_elSe_o7h3r_TH4n_lcg}`
Sign in with Wallet
Connect another wallet