# CNS 2023 HW1 Solution
[TOC]
## 3. Multi-prime RSA
### a)
**Case 1: $m, N$ coprime**
$$
\begin{aligned}
Dec(Enc(m ,e), d) &\equiv (m^e)^d \equiv m^{ed} \mod N \\
&\equiv m^{k \phi(N) + 1} \mod N \text{ where } k \in \mathbb{Z} &\because d \equiv e^{-1} \mod \phi(N) \\
&\equiv m^{k\phi(N)}m \equiv 1 \cdot m \mod N &\text{(by Euler's theorem)} \\
&\equiv m
\end{aligned}
$$
**Case 2: $m, N$ do not coprime**
Let $m = k\prod_{s \in S} p_s^{t_s}$ where $S$ is the subset of $\{p_1, \cdots, p_r\}$ and $k \in \mathbb{Z}$. We can see that $gcd(m, N) = \prod_{s \in S} p_s$.
For all $p_s \in S$, we have
$$
\begin{aligned}
Dec(Enc(m, e), d) &\equiv (m^e)^d \equiv (k\prod_{s \in S} p_s^{t_s})^{ed} \equiv 0 \equiv m \mod p_s
\end{aligned}
$$
Also, for all $p_j \notin S$, we have
$$
\begin{aligned}
Dec(Enc(m, e), d) &\equiv (m^e)^d \equiv m^{ed - 1} m \equiv m^{u\phi(N)} m \mod p_j \quad &\text{for some } u \in \mathbb{Z} \\
&\equiv m^{(p_i - 1) v} m \mod p_j \quad &\text{for some } v \in \mathbb{Z} \\
&\equiv (m^{(p_i - 1)})^v m \equiv 1^v m \mod p_j \quad &\text{ by Fermat's Little Theorem} \\
&\equiv m \mod p_j
\end{aligned}
$$
Therefore, we have $\forall p_i, i \in \{1, \cdots, r\}$:
$$
m^{ed} \equiv m \mod p_i
$$
and, by CRT, we can get
$$
m^{ed} \equiv m \mod N
$$
> Note: You should either prove the correctness in the case when $m$ and $N$ are not coprime, or justify that $m$ and $N$ should not coprime.
### b)
1. Regular RSA can be broken by taking the square root of the modulus ($\sqrt{N} = p = q$).
2. For all $x \equiv 0 \mod p_i, i \in \{1, \cdots, r\}$, it is encrypted to $x^e \equiv 0 \mod N$.
### c)
First, we precalculate
$$
d_i \equiv d \mod (p_i - 1), d_i < p_i - 1
$$
Then, when given a ciphertext $c$, we do:
$$
\begin{align}
c^d &\equiv c^{k(p_i - 1) + d_i} \equiv (c^{p_i - 1}) ^ k c^{d_i} \mod p_i \quad \text{ for some } k \in \mathbb{Z} \\
&\equiv 1^k c^{d_i} \mod p_i \quad \text{(By Fermat's Little Theorem)} \\
&\equiv c^{d_i} \mod p_i
\end{align}
$$
Then, we can combine the results by the CRT. Let $b_i \ N/p_i$ and $b_i^{-1}$ be the multiplicative inverse of $b_i$ in $\mathbb{Z}_{p_i}$.
$$
c^d \equiv \sum c^{d_i} b_i b'_i \mod N
$$
### d)
There is no "correct" answer. Here are some commonly seen answers:
Advantage 1: Faster decryption by using CRT, as shown in subproblem c.
Advantage 2: Faster key generation when the moduli are the same, as shown in subproblem e.
Disadvantage 1: Larger modulus size to achieve same security level.
Disadvantage 2: When the CRT-exponent keys $d_i$ are too small, it will vulnerable to Chinese Remainder Theorem attack.
> Note: Many mentioned that the modulus of multi-prime RSA is easier to be factorized. This relies on two assumptions: 1. the "hardness" is compared to that of regular RSA with the same modulus size; 2. the complexity of factorization algorithm depends on the sizes of factors, which is not always true (e.g., General Number Field Sieve).
>
### e)
Pointing out that the complexity of finding a prime, i.e., $O(n^4 / log(n))$, is super-linear in the bit-length of the desired prime is sufficient.
> Note: If your proof use the fact that the prime should be roughly balanced, you should substantiate this claim.
## 4. Fun With Semantic Security
> We only provide the outline and critical parts instead of the full proof.
### a)
We want to prove by contrapositive. Assume there exists a polynomial-bounded adversary $Adv'$ who wins the SS game of $Enc(k, m)||r$ with non-negligible advantage. Construct an adversary $Adv$ who use $Adv'$ as a subroutine to play the SS game of $Enc(k, m)$ as the following diagram shows. It is then trivial to prove that $Adv$ wins the SS game of $Enc(k, m)$ with non-negligible advantage. Thus finish the proof.
```sequence
Adv'->Adv: (m_0, m_1)
Adv->Ch: (m_0, m_1)
Note right of Ch: k <- K
Ch->Adv: c <- Enc(k, m_b)
Note right of Adv: r <- K
Adv->Adv': c || r
Adv'->Adv: b'
Note right of Adv: outputs b'
```
### b)
We want to prove by contrapositive. Assume there exists a polynomial-bounded adversary $Adv'$ who wins the SS game of $Enc(k, m+r)||r$ with non-negligible advantage. Construct an adversary $Adv$ who use $Adv'$ as a subroutine to play the SS game of $Enc(k, m)$ as the following diagram shows. It is then trivial to prove that $Adv$ wins the SS game of $Enc(k, m)$ with non-negligible advantage. Thus finish the proof.
```sequence
Adv'->Adv: (m_0, m_1)
Note right of Adv: r <- M
Adv->Ch: (m_0+r, m_1+r)
Note right of Ch: k <- K
Ch->Adv: c <- Enc(k, m_b+r)
Adv->Adv': c || r
Adv'->Adv: b'
Note right of Adv: outputs b'
```
### c)
:::spoiler
In the security game of $\mathcal{E}'$, since $k$ and $r$ are both randomly sampled from $\mathcal{K}$, the two random variables $r$ and $(k+r)$ are independent. As a result, we can rewrite the $c \xleftarrow[]{R} Enc(k+r, m)||r$ in the security game to be $c \xleftarrow[]{R} Enc(k, m)||r$ where the probability distribution of $c$ remains exactly the same. Then, we can use the result of subtask a) to jump to the conclusion.
:::
## 5. Simple Crypto
### Round 1
用 online Caesar Cipher Decoder: https://www.dcode.fr/caesar-cipher
### Round 2
用 online Rail Fence Cipher Decoder: https://planetcalc.com/6947/
### Round 3
one-time pad
### Round 4
外層加密使用 Bacon Cipher，觀察出大寫 / 小寫字母對應到 A / B，且使用的模式為 separate value，再用 online decoder 解開第一層：https://calcoolator.eu/bacon-cipher-encoder-decoder-
第二層使用 Rail Fence Cipher，解法如 round 2
## 6. ElGamal Cryptosystem
```sequence
Note left of Alice: generate secret sk
Note left of Alice: pk <- (g, g^sk)
Alice->Bob: pk
Note right of Bob: generate a random y
Note right of Bob: (c1, c2) <- (g^y, ((g^sk)^y)*m)
Bob->Alice: (c1, c2)
Note left of Alice: get message m = c2 * (c1)^(-sk)
```
a) The ephemeral key $y$ is reused. So we can just send any message $m$ and get a cyphertext $(g^{sk})^y \cdot m$. With multiplying m's inverse ($m^{-1}$) we can have $g^{y\cdot sk}$, and then use it to decrypt the flag.
b) 題目可以幫我們解密一段文字，但是不會把答案告訴我們，只會回答解密出來的內文長度是否小於 128 bytes (=1024 bits)。
我們只有 flag 的密文，但是因為密文的 $c1, c2 = (g^y, ((g^sk)^y)*m)$ 。
所以如果我們把 $c2\cdot x$，明文也會變成 $m' = m \cdot x$。
也就是說，我們可以有 $m \cdot x \leq 2^{1024}$ 的 oracle。然後我們就可以二分搜一個最近的上界使得 $m \cdot x \simeq 2^{1024}$。然後就直接可以得到 $m \simeq 2^{1024} / x$。
要注意的是：雖然方法是對明文做操作，過程中數字基本上都會小於 $P$、運算上不會有被 mod 的問題。但二分搜 x 一開始的上界不能設太大，不然一開始會有機會超過 P 導致明文被 mod 下來（可以先慢慢的從 1, 2, 4, 8 ....的去試出一個安全的上界）。
比較嚴謹的說明：
因為題目有保證 len(flag) <= 50 也就是說 $0 \leq m < 2^{400}$。
所以我們可以二分搜出 $x$ 使得 $m \cdot x < 2^{1024}$、$m \cdot (x+1) > 2^{1024}$。
也就是說 $2^{1024} - m < m \cdot x < 2^{1024} \Rightarrow (2^{1024} - m) / x < m < 2^{1024} / x$。
因為 $m < x \Rightarrow (2^{1024} / x - 1) < m < 2^{1024} / x$ 。（所以頂多就差一）
c) 用 Shamir secret sharing + Elgamal 做成的 Threshold Elgama，但因為實作的 Elgamal 是使用 $Z_P \text{,with } P = 2\cdot p+1 \text{ where }p\text{ is a big prime}$。所以 Elgamal 裡 generator 的 order 是 $P - 1 = 2\cdot p$。
但因為（要做 Lagrange polynomial 要用到除法，order 的因數裡面有 2 會不好找乘法反元素，所以特別把） Shamir secret sharing 做在 $p$ 上面，也就是說我們的 Lagrange polynomial 的係數要做在 mod $p$ 上面，但把他放到次方去 power partial secret 的時候還是要 mod $P$。
最後這樣就可以得到 $(c1)^{sk}$ 或是 $(c1)^{sk+p}$，兩種可能，就有二分之一的機會會對。（如果真的很討厭要跑兩次的話，也可以把得到的 $c1^{?}$ 跟 $(c1^{?})^p$ 兩個都拿去試試看就一定會有答案。）
## 7. Bank
因為`balances`是用username的SHA1來index，所以利用SHA1碰撞可以讓user重複得到new user gift。套用[Google的研究](https://shattered.io/)的那兩個PDF檔就可以實現了。稍微看一下[原paper](https://shattered.io/static/shattered.pdf)會發現在這個exploit在後面append任何相同的字串仍然會碰撞，這樣就可以完成(b)小題。
## 8. Clandestine Operation
詳見 solve.py
a) 使用 CBC padding oracle
b) 利用類似 padding oracle 的概念，將要竄改的 field 對應到前一個 block 的 byte ${b_{-1}}$ ，改成 $b_{-1} \oplus \text{{original byte}} \oplus \text{{target byte}}$。另外因為前一個 block 被改過所以解密出來有可能會發生 `Unicode Decode Error`，所以可以操縱對應位置以外的 bytes，
Sign in with Wallet
Connect another wallet