# 遊戲開始-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$$也就是最後的答案。