# Diffie-Hellman Training

- Như các bạn đã biết ở section **RSA**, độ khó của bài toán phụ thuộc hoàn toàn vào việc có thể **phân tích thừa số nguyên tố** hiệu quả hay không. Và việc phân tích đó chính là 1 trong những bài toán khó (NP-problem).
- Hôm nay, ta cùng đi xem xét 1 bài toán khó khác đó là [**logarit rời rạc**](https://en.wikipedia.org/wiki/Discrete_logarithm) (discrete_logarithm)
- Và đồng thời, trong bài viết này, mình sẽ tóm lược cho các bạn những kiến thức cơ bản nhất về 1 giao thức (protocol) trao đổi khóa được xây dựng dưa trên bài toán khó trên tương đối quen thuộc hiện nay đó là [Diffie-Hellman key exchange](https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange).

## Prerequisites
+ Lý thuyết đồng dư
+ Trường hữu hạn
+ Your brain...

## Group Theory
+ Nhóm được định nghĩa bao gồm 1 tập hợp **G** và 1 phép toán $\star$; với mọi phần tử $a, b \in G$, để phần tử $a \star b \in G$, thì phép toán $\star$ phải thỏa mãn 3 tính chất sau:
+ **Identity**: Tồn tại phần tử $e \in G$ sao cho $\forall a \in G$, ta có $a \star e = e \star a = a$.
+ **Inverse**: $\forall a \in G$ thì chỉ tổn tại duy nhất 1 $a^{-1} \in G$ thỏa mãn $a \star a^{-1} = a^{-1} \star a = e$
+ **Associative**: $a \star (b \star c) = (a \star b) \star c \ \ \forall a, b, c \in G$
+ **Commutative**: $a \star b = b \star a \ \ \forall a, b \in G$ -> Đây là tính chất ngoài lề, nếu như 1 nhóm đã thỏa 3 tính chất trên và đồng thời thỏa mãn thêm tính chất này thì ta gọi nhóm đó là **abelian group**
+ Nếu nhóm đó có hữu hạn(đếm được) phần tử thì ta gọi là **finite group**, lực lượng của nhóm được kí hiệu là $|G|$ hoặc $\text#G$

- Những dòng trên tương đối nặng về lý thuyết, nên các bạn có thể hiểu đơn giản như thế này, trong toán học hiện tại, chúng ta luôn làm việc với các tập số như tập số tự nhiên $\mathbb{N}$, tập số nguyên $\mathbb{Z}$, .... Bản chất các tập số là group nhưng được kèm thêm 1 vài thứ khác, nên ta hoàn toàn có thể lấy các tập số này và xét 1 phép toán nào đó để kiểm tra xem nó có phải group như định nghĩa hay không.
- Chẳng hạn như, ta làm việc với tập số nguyên $\mathbb{Z}$ với phép toán là +, có thể thấy ngay phần tử identity e chính là 0, và vì là phép + nên nó thỏa mãn đủ các tính chất kết hợp, nghịch đảo, giao hoán như trên.

## DLP Problem
+ Hẳn trong chương trình học cấp 3, thì các bạn đều đã làm quen với khái niệm logarit, ta có thể hiểu hàm logarit như 1 hàm nghịch đảo của hàm mũ, và khi xét log của 1 số x nào đó trên base a thì kết quả trả ra sẽ là số mũ k sao cho $a^k = x$.
+ Tương tự, logarit rời rạc cũng gần giống với khái niệm trên, chỉ khác duy nhất là các phép toán của nó đều xét trên 1 modulo (thường là **prime**) e.g: $a^k \equiv x \ (mod \ p)$.
VD:
$log_345 \approx 3.465$
$\text{discrete_log}_345 \equiv 7 \ (mod \ 17)$

+ Vậy thì tại sao chỉ một thay đổi nhỏ là xét trên modulo **prime** lại khiến **DLP** trở thành bài toán khó. Vì đơn giản là logarit rời rạc được xét trên modulo **prime** nên kết quả trả ra của nó cũng phải là 1 số nguyên từ **[1, prime-1]** (bất cứ số `k > prime-1` nào cũng đều có thể được xét trên mod ord(prime) để đưa về số mũ `k'` trong khoảng này).
+ Vậy nên việc giải bài toán đối với dạng **logarit rời rạc** sẽ mất nhiều thời gian hơn, và gần như là không thể giải được nếu modulo quá lớn.
+ Câu hỏi đặt ra bây giờ là, làm sao mình tính được đáp án cho VD trên, hay nói 1 cách khác là liệu có tồn tại cách tính discrete_log hay không 😅.
+ Câu trả lời lại đơn giản đến bất ngờ 👀
### Bruteforce (a.k.a cày trâu, vét cạn, ...)
+ Đúng với cái tên của nó, trong 1 bài toán **DLP** các bạn đã được cung cấp 3 thông số là ``(a, x, p)`` và cần tìm `k` sao cho $a^k \equiv x \ (mod \ p)$. Vậy thì đã biết k sẽ chỉ nằm trong khoảng **[1, p-1]**, ta chỉ cần duyệt mọi số trong khoảng này để tìm ra đáp án thỏa mãn.

a = 3
p = 17
x = 45
for i in range(1, p):
    if pow(a, i, p) == x: return True

+ Tuy nhiên đpt của thuật toán này là O\(p), vậy nên sẽ không thiết thực khi ta phải chạm mặt 1 số `p` quá lớn

### Baby step Giant step (BSGS)
+ Giải thuật này bản chất cũng chỉ là bruteforce nhưng có cải tiến khá nhiều khi áp dụng kĩ thuật **Meet-in-the-middle** khiến cho đpt về cơ bản xấp xỉ O($\sqrt{p}$)
+ Các bạn có thể tham khảo [bài viết này](https://cp-algorithms.com/algebra/discrete-log.html) về giải thuật **BSGS**
### Pohlig Hellman (PH)
+ Giải thuật này cũng khá hay và chỉ được xài trong trường hợp prime có order smooth, nghĩa là p-1 có thể phân tích ra thành các thừa số nguyên tố nhỏ hơn nó (p ~ 512bits nhưng lại được dựng bằng $\prod_{i=0}^{k}{q_i} + 1$ với các $q_i$ ~ 24 bits )
+ Các bạn có thể tham khảo [bài viết này](https://www.cryptologie.net/article/196/pohlig-hellman-algorithm/) để có cái nhìn cụ thể hơn

## Diffie-Hellman key exchange
+ Như đã nói ở đầu bài, **DH key exchange** là 1 giao thức trao đổi khóa công khai mà nền tảng của nó chính là **DLP**


+ Hình ảnh trên đã mô tả tương đối chi tiết về từng bước cụ thể trong giao thức này. Các bạn nên tự tay code lại để hiểu thêm.
+ Ngoài phiên bản Diffie Hellman như trên, ta vẫn còn 1 phiên bản khác của Diffie Hellman đó là [ECDH](https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman), thì ở phiên bản các tham số mà nó sử dụng đều là các điểm trên đường cong ECC. (các bạn có thể xem lại bài viết trong section [ECC training](https://giapppp.notion.site/Elliptic-Curve-Cryptography-50d4401770b641349ad235e287b326d0))

+ Cho dù các bạn thấy tổng thể giao thức trao đổi khóa này là vô cùng an toàn vì dựa trên bài toán khó **DLP** nên attacker gần như là không thể tính ngược lại số mũ bí mật ban đầu của Alice và Bob. Nhưng giao thức này lại vướng 1 điểm yếu chí mạng khác, đó là không có cơ chế xác thực.
+ Cụ thể hơn, giả sử rằng Eve là người đứng giữa và bắt được dữ liệu mà Alice gửi cho Bob, cho dù Eve không thể biết được bí mật của Alice là gì, nhưng nếu Eve biết được thỏa thuận ban đầu về `(g, p)` giữa Alice và Bob thì Eve hoàn toàn có thể tự tạo ra 1 dữ liệu fake và gửi nó cho Bob. Vấn đề này có tên **Man-in-the-middle**


+ Vậy nên, điểm yếu chí mạng của mọi phiên bản **diffie hellman** là chưa có cơ chế xác thực dẫn đến việc sẽ dính vào **man-in-the-middle attack**

## Other notes
+ Bài viết này mình có đề cập đến group nhưng lại không nhắc về nó nhiều trong **DLP** cũng như trong **DH**, vì khái niệm group chỉ là 1 khái niệm được trừu tượng hóa lên, và các ví dụ trong **DLP** cũng như trong **DH** đều là các con số -> tương ứng với group đang ngầm xét là group số với phép toán là *.
+ Vì khái niệm nhóm là như thế, nên ta cũng có 1 số các nhóm khác như [nhóm các điểm trên ECC](https://crypto.stanford.edu/pbc/notes/elliptic/group.html), [nhóm ma trận](https://en.wikipedia.org/wiki/General_linear_group) hoặc là [nhóm hoán vị](https://en.wikipedia.org/wiki/Permutation_group), ...
+ Tương tự thế, giao thức trao đổi khóa **DH**, các giải thuật để giải bài toán **DLP** cũng có thể được sử dụng với các group kể trên.

## Homework / Practice
+ Cryptohack

Diffie Hellman starter 1 - 5
Parameter injection
Additive
Export grade
Static client 1-2
Script Kiddie (optional)
The Matrix
The Matrix Reloaded (optional)
The Matrix Revolution (optional)

+ Any challenge that you feel its useful 😎

## Lời kết
- Cuối cùng, nếu gặp bất kì khó khăn gì, trong việc hiểu bài viết này, hoặc trong việc giải bài tập, các bạn có thể hỏi 1 trong các trainer hoặc liên hệ với mình qua discord `tranminhprvt01` .