# 遊戲開始-RSA

影片中，志書在天台上要求解一個非常困難的問題：
::: warning
『哪一個四位數字的215887次方除以16973393的餘數是4076』
:::
轉換成數學問題就是求下面方程式中的$x$
$$
x^{215887} = 16973393 n + 4076,
$$
其中$n$是一個正整數。這個問題乍看之下是幾乎不可能完成的。因為根本沒時間去計算上千個數字的215887的次方除以16973393的餘數。這樣的$x$與$4076$的對應方式，就是加密方法中的RSA加密/解密法。其中把$x\rightarrow 4076$稱為加密，而從$4076\rightarrow x$的過程就是解密。解密過程是需要一個解密的次方數字$d$，然後把$4076^d$除以169733393的餘數算出來就好。但如果不知道$d$是什麼，這個解密出來的答案就有超級多種可能，因為每一個$d$都可以解出一個數字來。所以這個$d$就被稱為解密的私鑰。私鑰只有解密的人擁有。為了以下說明方便，我們暫且把解密的人叫做Sofie吧。而$(16973393,215887)=(N,e)$則被稱為加密的公鑰，公鑰是可以公開每一個人的。意思就是，每一個人都可以把他想要傳給Sofie的數字$x$，計算它的215887次方除以16973393的餘數$y$傳給Sofie，這樣Sofie就可以透過私鑰$d$把原先的$x$解出來了。而且Sofie還不用怕被別人知道$y$是多少，這也讓這個方法所加密出來的數字，可以公開地在網路上傳播。

## 加解密的關鍵，來自餘數的循環
如果我們把一個非零的數字$a$，它的1、2、3、…、$k$($k>a$)次方，除以一個與$a$互質的數字$N$，並把餘數一一列出來。那麼你會發現，這個餘數過幾個之後就會循環出現。舉例來說，2的1次方到15次方除以11的餘數分別為
::: success
2、4、8、5、10、9、7、3、6、1、2、4、8、5、10 $\ldots$
:::
上面的例子中，2的11次方就除以11的餘數就跟2的1次方一樣，都是2了。之後就開始循環。而這個循環的原因其實可以直覺想到，因為除以11的餘數只有0~10，因為$a$跟$N$是互質的，所以不會出現0。因此，最多也只有10個可能出現的餘數，即使前面10個次方的餘數都不一樣，但第11個，也就是$2^{11}$，它除以11的餘數一定會跟前面的重複。而下一個餘數，都會是上一個餘數乘以2之後的餘數(大家可以想想為什麼)，所以就開始循環了。這個定理也就是費馬小定理的前身，$a^N$除以$N$的餘數會是$a$。而它的前一個次方，也就是$2^{10}$除以11的餘數就一定會是1。這個定理，我們叫它『費馬小定理』

## 費馬小定理
::: danger
如果$a$跟$N$互質，且$N$是質數的話，那麼$a^{N-1}$除以$N$的餘數是1
:::
這是一個數論中常用的定理。此外，若我們回去看，$a^k$，$k=1,2,3,\ldots$餘以$N$的餘數，它在$a^N$會循環。也就是它經過$N-1$個之後會重複。不過真正的循環節會是$N-1$的因數。就像上面$N=11$，那麼它10個之後會循環。

以下是$3^k$，$k=1,2,3,\ldots$除以11的餘數。雖然從上面的定理知道它10個會循環，但它5個其實就開始循環了。
::: success
3、9、5、4、1、3、9、5、4、1、3 $\ldots$
:::

## 為什麼這個循環節可以用來加密？
舉個例字，假設Sofie把$(N,e)$設定成$(N=11,e=3)$。那麼每一個人要傳訊息給Sofie時，舉例來說，要傳$x=2$給Sofie。那麼經過RSA加密後的$y = 2^3 = 8$。那麼Sofie要用哪一個數字$d$來解密呢？這時候我們可以選擇$d = 7$。因為$3 \times 7$會是21，剛好是循環節(長度為10)的倍數再加1。這時候我們計算
$$
8^7 = (2^{3})^7 = 2^{21} \rightarrow 2^{11} \rightarrow 2
$$
其中$\rightarrow$表示往前一個循環節，因為10個一循環，所以$2^{21}$跟$2^{11}$除以N的餘數會一樣。再往前一個循環節，就會是$2^1$也就是2。上面這一個寫法，在數學上會用下面的同餘($a \equiv b \mod N$)符號，來表示$a$跟$b$除以$N$的餘數一樣
$$
2^{21} \equiv 2^{11} \equiv 2^1 = 2 \mod 11
$$
最後面的$\mod 11$表示除數是11的意思。大家可以把一開始的數字$x=2$換成$x=3$，那麼加密後會是$3^3=27$除以11的餘數5，也就是$y=5$。而解密的計算跟剛剛類似，$y^7=5^7=78125$，此時餘以$11$的餘數是$7-8+1-2+5=3$。是不是透過次方就把$3 \leftrightarrow 7$給連結起來了？(Q: 那4傳過去應該是誰呢？)上述的算式可以用數論的同餘概念，就是$3^3$跟$5$在計算除以11的餘數是一樣的；然以把兩者各7次方。也就是$(3^3)^7 = 3^{21}$跟$5^7$除以11的餘數也是一樣的。而$3^{21}\rightarrow 3^{11} \rightarrow 3^1 = 3$。透過循環節及同餘的寫法，計算就會簡單很多。馬上就知道是$5^7$除以11的餘數是3，如下
$$
3^3 \equiv 5 \mod 11 \Rightarrow 5^7 \equiv (3^3)^7 = 3^{21} \equiv 3 \mod 11
$$
而在RSA演算法中，$e$跟$d$的取法就是從循環節來的。如果循環節是$r$，那麼$e$跟$d$的乘積只要比$r$多1即可。所以加密次方$e$跟解密次方$d$之間的關係是
$$
e d \equiv 1 \mod r
$$

## 進階版本的費馬小定理
::: danger
如果$a$跟$N$互質，$N$是一般的數字，那麼$a^{\phi(N)}$除以$N$的餘數是1；其中$\phi(N)$表示小於$N$且跟$N$互質的正整數個數。
:::
這是費馬小定理一般化的結論。類似於前面的想法，既然$a$跟$N$互質，所以$a^k$與$N$也是互質的，所以$a^k$除以$N$最多就是有$\phi(N)$個不同的餘數。因此，只要$k$超過$\phi(N)$，一定就會跟前面的重複。就會循環了。舉例來說，除以$15$的餘數，經過$\phi(15)=8$個一定會循環。下面就列出了$2^k$除以$15$的餘數(實際上經過4個就循環了)
::: success
2、4、8、1、2、4、8、1 $\ldots$
:::
這裡要提到一個特殊情況，如果$N$是兩個質數$p$跟$q$相乘，那麼$\phi(N)=(p-1)(q-1)$。這類型兩個質數相乘的$N$，就是RSA演算法所使用的公鑰之一的$N$。如果知道$p$跟$q$，那麼算出$N$是很簡單的。但如果只給$N$，要透過質因數分解找到$p$跟$q$，就是困難的任務。
::: info
米珊：『這就像把糖跟鹽混在一起很簡單，但要把它們分開很難』
:::

## 能猜到$N$的質因數分解的Shor演算法
Shor演算法的原始版本
::: success
如果可以找到$a^{2k}$除以$N$的餘數是$1$，那麼$N$可能有$\gcd(N, a^k+1)$或$\gcd(N, a^k-1)$的因數。其中$\gcd(b,c)$是$b$跟$c$的最大公因數
:::
這個其實用到了國中學過的平方差公式，因為$a^{2k}$除以$N$的餘數是$1$，所以$a^{2k}-1=(a^k-1)(a^k+1)$會被$N$整除。這時候因式分解出來的兩個數字$a^k-1$跟$a^k+1$，就很有可能是$N$的因數。而在劇中，志書所用的是出題老師延伸的版本，因為志書發現了$$2^{192} \equiv 2^{4} \mod 16973393$$其實已經開始循環了。不拘泥於Shor演算法要找到餘數為$1$。志書直接分解了$2^{192}-2^4=(2^{96}-2^2)(2^{96}+2^2)$。而且之前志書在計算$2^{192}$次方時，由於米珊的提醒之下，採用了平方來進行Fast Power Algorithm。故$2^{96}$已經算好了，所以才能夠在時間內把答案算出來。

### Fast Power Algorithm
這是一個計算一個數字高次方的演算法。舉例來說，如果要計算$2^{192}$，是需要把$2$乘個$192$次。所以志書說，要計算高次方很難。但是在米珊的提醒下：
::: info
米珊：『用平方呢？』
:::
這時給了志書靈感，透過平方快速地把$2$高次方算出來。影片中用了$2^{12} = 4096$，平方之後就是$4096^2=2^{24}=16777216$。這就直接算出$2^{24}$了。比$4096$乘$12$次$2$來得快多了。而$16777216=16973393-196177=N-196177$，就是志書在影片中說，『與金鑰差了$196177$』。就是除以$N$的餘數，不足$196177$。此時把$196177$平方，並考慮除以$N$的餘數，就會得到$2^{48}$除以$N$的餘數$6733398$。再平方一次，就是$2^{96}$，這時候餘數是$180524$；而$2^{24}$平方三次，就是$2^{192}$，這時候的餘數是$16=2^4$。志書在平方的過程中，找到了循環！因此志書可以用$\gcd(180524-4, 16973393)=4513$，也確定$4513$除以$N$之後是$3761$。就找到了$N$的質因數分解
$$
N = 16973393 = 3761\times4513
$$

## 讓我們回到原問題
如果我們可以找到對應於公鑰$(N,e)=(16973393,215887)$的私鑰$d$，那麼只要把$4076^d$除以$16973393$的餘數找到，那麼就會是$x$了。但是怎麼找到$d$呢？從上面的過程中，我們可以知道它有可能的循環節是$\phi(16973393)=3760\times 4512=16965120$，所以我們只需要找到$d$，使得$215887\times d$除以$16965120$的餘數是1就可以。也就是解
$$
215887 d = 16965120 m + 1
$$這個需要輾轉相除法，運算時的表格如下(如果不知道這個表格的意義，可以請教高中老師)：
| 78 | 16965120(A) | 215887(B) | 1 |
| ---:| --------:| ------:| ---:|
| 1 | 125934(A-78B) | 89953(79B-A)| 2 |
| 1 | 35981(2A-157B) | 17991(393B-5A) |
| 2 | -1(12A-943B) |

從上述的表格，可以在算出$A$跟$B$的最大公因數時，順便得到$12A-943B=-1$。因此我們可以找個一個解，是$d=943$。所以最後只需要計算$4076$的$943$次方。但$943$次方也不是很好算的。這裡還有另一個結合Fast Power Method的神奇快速算法。就是先計算$$x=4076^3 \equiv -6087094 \mod N$$透過把$x$一直平方2次，會得到$$4076^{12} \equiv -2545316 \mod N$$繼續再平方6次，會得到$$4076^{768} \equiv 9499105 \mod N$$另外再計算$$y=4076x^3=4076^{10} \equiv -6194786 \mod N$$再平方4次，會得到$$4076^{160} \equiv 4231460 \mod N$$最後利用$$943=3\times (256+4+1) + 10\times 16=768+12+3+160$$所以$$4076^{943} = 4076^{768}\times 4076^{12} \times 4076^3 \times 4076^{160}$$ $$\equiv (9499105) \times (-2545316) \times (-6087094) \times 4231460 \equiv 9487 \mod 16973393$$

因此，最後志書算出來的答案就是
::: danger
x = 9487
:::

其實在影片中的數字，都是有經過精心設計的。當初找這些數字也需要功夫。而且要讓同學們可以透過計算機或(神)手算出來的。如果有興趣研究的同學，可以思考看看是怎麼做的！

## 同場加映：
:::danger
$440 \times 2^{\frac{7}{12}}$是怎麼算出來的？
:::
這裡用到了一個神奇的方式，令$x=2^{\frac{7}{12}}$，這個問題是要解出$x^{12}=2^7$的答案。這對應到音階頻率其實是一個等比數列，這個等比數列的公比為$2^{\frac{7}{12}}$(因為經過了12個音階，會高八度；而高八度的音，頻率是兩倍)。但在高中要計算這一個數字，可以透過兩邊取$\log$，得到$$\log x = \frac{7}{12} \times 0.301 \approx 0.17558 \approx = 0.4771-0.3010 = \log 3 - \log 2 = 0.1761$$因此，我們可以猜測這個答案$x \approx \frac{3}{2}$。因為答案是四位數，不可能只是660。因此志書猜測會有小數點，所以我們得估更靠近的一個答案。為了更好的近似值，我們需要用到牛頓法求$x^{12}=2^7$的根：
$$
x_{n+1} = x_n - \frac{x_n^{12} - 2^7}{12 \times x^{11}_n} = x_n - \frac{1}{12}x_n + \frac{2^7 \times 2^{11}}{12 \times 3^{11}} \approx 1.4983
$$
然後$$440\times 1.4983 \approx 659.3$$也就是最後的答案。