# ZKHack IV Puzzles #3 Chaos Theory

Puzzle: https://zkhack.dev/zkhackIV/puzzleF3.html
Solution: https://github.com/flyq/puzzle-chaos-theory

## ElGamal encryption

### Key generation
Alice:
- secret key: $x$
- public key: $H = x\cdot G$

### Encryption
Bob:
- $M = F(m)$, the $m$ is the message, and the $M$ is the element in $G$.
- ephemeral key: $y$
- shared secret: $S = H \cdot y = x \cdot y \cdot G$
- $C_1 = y \cdot G$
- $C_2 =S + M$

if someone knows $(C_1, C_2)$ and $M$, the $S = C_2 - M$

### Decryption
Alice:
- $S = C_1 \cdot x = x \cdot y \cdot G$
- $M = C_2 - S$
- $m = F^{-1}(M)$

Sender(Bob): $y$ and $C_1 = y \cdot G_1$
Receiver(Alice): $H$ in $G_1$ group
Message: $M$ in $G_1$ group
ElGamal: $(C_1, C_2)$ in $G_1$ group, $H((C_1, C_2)) = \text{hash_to_curve}((C_1, C_2)) \cdot Q$ in $G_2$ group

s: $T = y \cdot H((C_1, C_2))$

- send: $C_1$, $C_2 = H \cdot y + M = S + M$
- authenticate: $H((C_1, C_2)) \cdot y$
- check_auth: $e(G_1, T) = e(C_1, H((C_1, C_2)))$

blob: $C_1, (C_1, C_2), T, H$