遊戲開始-RSA

影片中，志書在天台上要求解一個非常困難的問題：

『哪一個四位數字的215887次方除以16973393的餘數是4076』

轉換成數學問題就是求下面方程式中的

$x$

$$x^{215887}=16973393n+4076,$$
其中

$n$是一個正整數。這個問題乍看之下是幾乎不可能完成的。因為根本沒時間去計算上千個數字的215887的次方除以16973393的餘數。這樣的

$x$與

$4076$的對應方式，就是加密方法中的RSA加密/解密法。其中把

$x\to 4076$稱為加密，而從

$4076\to 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的餘數分別為

2、4、8、5、10、9、7、3、6、1、2、4、8、5、10

$\dots$

上面的例子中，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。這個定理，我們叫它『費馬小定理』

費馬小定理

如果

$a$跟

$N$互質，且

$N$是質數的話，那麼

$a^{N-1}$除以

$N$的餘數是1

這是一個數論中常用的定理。此外，若我們回去看，

$a^k$，

$k=1,2,3,\dots$餘以

$N$的餘數，它在

$a^N$會循環。也就是它經過

$N-1$個之後會重複。不過真正的循環節會是

$N-1$的因數。就像上面

$N=11$，那麼它10個之後會循環。

以下是

$3^k$，

$k=1,2,3,\dots$除以11的餘數。雖然從上面的定理知道它10個會循環，但它5個其實就開始循環了。

3、9、5、4、1、3、9、5、4、1、3

$\dots$

為什麼這個循環節可以用來加密？

舉個例字，假設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}\to 2^{11}\to 2$$
其中

$\to$表示往前一個循環節，因為10個一循環，所以

$2^{21}$跟

$2^{11}$除以N的餘數會一樣。再往前一個循環節，就會是

$2^1$也就是2。上面這一個寫法，在數學上會用下面的同餘(

$a\equiv b\mathrm{mod}N$)符號，來表示

$a$跟

$b$除以

$N$的餘數一樣

$$2^{21}\equiv 2^{11}\equiv 2^1=2\mathrm{mod}11$$
最後面的

$\mathrm{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}\to 3^{11}\to 3^1=3$。透過循環節及同餘的寫法，計算就會簡單很多。馬上就知道是

$5^7$除以11的餘數是3，如下

$$3^3\equiv 5\mathrm{mod}11\Rightarrow 5^7\equiv (3^3{)}^7=3^{21}\equiv 3\mathrm{mod}11$$
而在RSA演算法中，

$e$跟

$d$的取法就是從循環節來的。如果循環節是

$r$，那麼

$e$跟

$d$的乘積只要比

$r$多1即可。所以加密次方

$e$跟解密次方

$d$之間的關係是

$$ed\equiv 1\mathrm{mod}r$$

進階版本的費馬小定理

如果

$a$跟

$N$互質，

$N$是一般的數字，那麼

$a^{\varphi (N)}$除以

$N$的餘數是1；其中

$\varphi (N)$表示小於

$N$且跟

$N$互質的正整數個數。

這是費馬小定理一般化的結論。類似於前面的想法，既然

$a$跟

$N$互質，所以

$a^k$與

$N$也是互質的，所以

$a^k$除以

$N$最多就是有

$\varphi (N)$個不同的餘數。因此，只要

$k$超過

$\varphi (N)$，一定就會跟前面的重複。就會循環了。舉例來說，除以

$15$的餘數，經過

$\varphi (15)=8$個一定會循環。下面就列出了

$2^k$除以

$15$的餘數(實際上經過4個就循環了)

2、4、8、1、2、4、8、1

$\dots$

這裡要提到一個特殊情況，如果

$N$是兩個質數

$p$跟

$q$相乘，那麼

$\varphi (N)=(p-1)(q-1)$。這類型兩個質數相乘的

$N$，就是RSA演算法所使用的公鑰之一的

$N$。如果知道

$p$跟

$q$，那麼算出

$N$是很簡單的。但如果只給

$N$，要透過質因數分解找到

$p$跟

$q$，就是困難的任務。

米珊：『這就像把糖跟鹽混在一起很簡單，但要把它們分開很難』

能猜到

$N$的質因數分解的Shor演算法

Shor演算法的原始版本

如果可以找到

$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\mathrm{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$次。所以志書說，要計算高次方很難。但是在米珊的提醒下：

米珊：『用平方呢？』

這時給了志書靈感，透過平方快速地把

$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\times 4513$$

讓我們回到原問題

如果我們可以找到對應於公鑰

$(N,e)=(16973393,215887)$的私鑰

$d$，那麼只要把

${4076}^d$除以

$16973393$的餘數找到，那麼就會是

$x$了。但是怎麼找到

$d$呢？從上面的過程中，我們可以知道它有可能的循環節是

$\varphi (16973393)=3760\times 4512=16965120$，所以我們只需要找到

$d$，使得

$215887\times d$除以

$16965120$的餘數是1就可以。也就是解

$$215887d=16965120m+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\mathrm{mod}N$$透過把

$x$一直平方2次，會得到

$${4076}^{12}\equiv -2545316\mathrm{mod}N$$繼續再平方6次，會得到

$${4076}^{768}\equiv 9499105\mathrm{mod}N$$另外再計算

$$y=4076x^3={4076}^{10}\equiv -6194786\mathrm{mod}N$$再平方4次，會得到

$${4076}^{160}\equiv 4231460\mathrm{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\mathrm{mod}16973393$$

因此，最後志書算出來的答案就是

x = 9487

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

同場加映：

$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_n^{11}}=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$$也就是最後的答案。