先從一條不安全的路開始
Alice 想和 Bob 第一次共享祕密，但 Eve 看得到兩人之間的通道。RSA 的故事就從這個麻煩開始：能不能做出任何人都能鎖、只有 Bob 能打開的數學機關？
十二張漫畫會依序走過質數、模運算、費馬小定理、Euler 定理、模數與成對指數，再親手算完 7 → 13 → 7。每個符號都要等到它有工作時才登場。
5、11 與 55 都是故意選小的玩具數字，完全不具安全性。它們的價值是讓你不用相信黑盒子，也能驗算 RSA 的骨架。
Alice 想把一個祕密交給 Bob，Eve 卻能看見網路上的每一個封包。若兩人早就共享一把祕密金鑰，後面的加密並不難；真正棘手的是第一次聯絡：保護資料的那把鑰匙，要怎麼先安全送到對方手上？
Bob 可以先公開一種上鎖方法，把開鎖所需的資料留在自己手上。RSA 用兩個祕密質數與一對指數安排這種分工。要理解指數為何能還原訊息，得先看懂餘數與循環。我們用時鐘理解模運算，再沿著費馬（Fermat）與歐拉（Euler）的定理，驗算 7 → 13 → 7。這組數字完全不安全，但每一步都能親手核對。
1. 祕密如何穿過公開世界？
先從「第一把鑰匙」想起
想像 Alice 有一只很牢的箱子，但上鎖與開鎖都用同一把鑰匙。她當然可以把祕密放進箱子；問題是 Bob 沒有鑰匙。若 Alice 把鑰匙直接寄出去，沿途監看的 Eve 也能複製。若再拿第二把鑰匙保護第一把，Bob 又得先取得第二把，問題只是往前搬，沒有消失。
公開金鑰密碼把上鎖與開鎖分成兩種能力。Bob 公開一把「只能拿來上鎖」的鑰匙，把能開鎖的私密鑰匙留在自己手上。Alice 取得並確認 Bob 的公鑰後，就能保護要交給他的內容，不需要先共享一把祕密鑰匙。公鑰是否真的屬於 Bob，會在第 10 節處理。
這一頁暫時沒有算式
這裡需要兩種彼此相關、能力卻不對稱的運算。公開的一邊要容易執行；只拿到公開資料的人，反推私密運算要困難到不切實際。Eve 可以知道演算法與公開參數，設計不能靠她沒看懂來保護資料。RSA 原始論文也是從公開加密程序、私密解密程序與金鑰配送問題描述這種分工。[1]
回到真實用途
漫畫裡寄的是一封信，後面手算的則是一個小整數。這只是教學模型：先看懂公開運算與私密運算如何配對，再理解它們能怎麼協助兩端建立共同祕密。真實文件不會原封不動塞進這條玩具算式，也不該自己照課本拼一套密碼系統；實務上要交給成熟、經過審查的函式庫。
2. 質數為什麼像數字世界的積木？
先把質數當成不能再拆的積木
質數只有兩個正因數：1 和它自己。2、3、5、7、11 都符合；12 可以拆成 2×2×3，15 可以拆成 3×5，所以它們叫合成數。大於 1 的每個整數都能拆成質數的乘積，而且不管先拆哪一邊，最後使用的質數積木相同，只差排列順序。
這件事有個很有意思的不對稱：把兩塊積木乘在一起很直接，但只看完成品，要猜出原來是哪兩塊，未必同樣容易。數字只有 55 時，我們一眼就能認出 5×11；位數長到電腦也難以逐一嘗試時，情況就完全不同。
把玩具例子拆一次
拿 55 來試。它不是偶數，所以 2 不是因數；各位數相加是 10，所以 3 也不是因數；尾數是 5，因此可以除以 5，得到 11。於是 55=5×11。小數字的分解很輕鬆，正好讓我們之後能反覆核對。
但別把「產生大質數」和「分解巨大合成數」混為一談。電腦可以先隨機產生候選數，再用有效的質數測試挑出合格的大質數；這不代表它拿到兩個未知大質數的乘積後，也能同樣快地找回原因數。
它在 RSA 裡負責什麼
Bob 之後會祕密選兩個大質數，再公開它們的乘積 n。知道那兩個因數的人，可以算出建立私鑰所需的週期資訊；只拿到巨大 n 的人，想走回去就得面對整數分解問題。這是 RSA 的安全直覺，不是「乘法沒有反運算」，也不是保證任何尺寸的數字都安全。[1]
3. 數字走到盡頭，為什麼會繞回來？
17 mod 5 = 2 只留下餘數。把數字排成環，超過最後一格就從 0 重新開始。先把 mod 當成一只時鐘
一般數線會一直往右延伸；時鐘不會。12 點再過一小時回到 1 點，因為我們只在意「繞完幾圈後停在哪裡」。餘數運算也是同一個畫面。寫下 17 mod 5，是在問 17 每五個分成一圈，最後停在哪一格。
看兩道最小的算式
先做除法：17=3×5+2，所以 17 mod 5=2。再看加法，4+4=8，8 除以 5 餘 3，因此寫成 4+4 ≡ 3 (mod 5)。符號 ≡ 讀作「在模 5 之下同餘」；兩者在餘數時鐘上落在同一格，普通整數 8 仍不等於 3。
乘法也照樣繞圈：3×4=12，而 12=2×5+2，所以 3×4 ≡ 2 (mod 5)。在 mod 5 的世界裡，結果永遠只會是 0、1、2、3、4 之一。
為什麼 RSA 離不開它
RSA 會計算很高次的冪，但每乘一次，就可以只保留除以 n 的餘數。這種「邊算邊縮小」的方式叫模冪運算。它讓電腦不必先造出一個天文大的完整整數，也讓數字在有限的餘數世界裡產生可觀察的循環。下一頁的 Fermat，就是在這個圓環上看出規律。
4. 費馬在質數圓環裡看見了什麼？
2 的冪次如何在七格圓環循環，再看公式；條件不能從圖上剪掉。先追著 2 跑一圈
把模數設成質數 7，從 2 開始反覆乘 2。2¹ 落在 2，2²=4 落在 4；到了 2³=8=1×7+1，餘數繞回 1。再乘一次，又從 2、4、1 重走。冪次看似一直增加，餘數卻只在幾個位置之間循環。
若直接跳到公式，這個現象很容易變成死背；先看軌跡，就會知道定理其實是在描述「走完某個週期後會回到 1」。
再把條件放回公式
費馬小定理說：當 p 是質數，而且 a 不被 p 整除時，a^(p−1) ≡ 1 (mod p)。代入 p=7、a=2，就得到 2⁶ ≡ 1 (mod 7)。我們剛才在第三次方已經碰到 1，第六次方當然也會再次回到 1。
兩個條件都要留下。模數不是質數時，不能原封不動套用；a 若本來就含有因數 p，也不符合這個版本的前提。懂得檢查條件，比記住公式長相更重要。
這顆齒輪還不是整台 RSA
費馬小定理告訴我們：在質數模數下，特定冪次會繞回 1。RSA 公開的模數是兩個質數的乘積，並非單一質數。下一步需要歐拉把「質數圓環的週期」推廣到合成數，才有辦法安排一對互相還原的指數。
5. 歐拉怎麼把規律帶到更多數字？
φ(n) 不是神祕常數，它只是在數 1 到 n−1 裡，有多少數和 n 互質。先弄懂「互質」在說什麼
兩個數不需要自己都是質數，也可能彼此互質。判斷方法是找最大公因數：若只共同擁有因數 1，就稱為互質。gcd(7,55)=1，所以 7 和 55 互質；gcd(5,55)=5，所以 5 和 55 不互質。這個條件會決定我們能不能使用下一個循環定理。
數一數 55 的循環有多長
歐拉函數 φ(n) 的工作很樸素：數出 1 到 n−1 之間，有多少整數與 n 互質。當 n=pq，而 p、q 是不同質數時，不必逐個檢查，直接用 φ(n)=(p−1)(q−1)。
本課選 p=5、q=11，所以 n=55，接著算出 φ(55)=(5−1)(11−1)=4×10=40。40 數的是這個餘數世界裡與 55 互質的位置，沒有憑空多出一個密碼。
歐拉定理接著說：若 gcd(a,n)=1，那麼 a^φ(n) ≡ 1 (mod n)。放進本例，任何與 55 互質的 a 都有 a⁴⁰ ≡ 1 (mod 55)。這就是我們稍後安排指數的基準週期。
它如何接上 RSA
RSA 稍後會找兩個互相搭配的指數，使它們合起來等於「若干個完整週期，再多一步」。完整週期會在模運算裡化成 1，多出來的那一步則把原值留下。先記住這個畫面；數字與字母到第 7 節才會正式登場。
工程師延伸：互質條件會不會漏掉某些訊息？
主線先用與 55 互質的 7 建立歐拉定理的直覺。完整 RSA 正確性不能只說「所有訊息都套歐拉定理」；對不互質的代表值，要分別在 mod p 與 mod q 下檢查，再用中國剩餘定理把結果合回 mod n。原始 RSA 論文的正確性論證也分開處理這些情況。[1]
6. 兩個祕密質數怎麼變成公開 n？
n；兩個因數 p、q 必須留在私鑰邊界內。Bob 先在自己的房間裡準備
Bob 選兩個不同的質數 p=5 與 q=11。這一步發生在私密的一側，像是在工作室裡挑好兩塊積木；外面的人不需要看到選擇過程。接著他把兩數相乘：n=pq=5×11=55。
從這一刻起，角色分開了。乘積 n=55 會放進公鑰，將來 Alice 加密、Bob 解密都會用到；因數 p=5、q=11 必須保護。因為一旦知道它們，任何人都能立刻算出 φ(n)=40，再往私密指數前進。
把已知數字整理成一張小抄
目前只有三行：p=5、q=11、n=pq=55。再利用上一節的公式，補上 φ(n)=(p−1)(q−1)=4×10=40。這張小抄還沒有公鑰與私鑰，因為成對的兩個指數尚未選出。
玩具數字與真實金鑰的距離
55 小得任何人都能分解，完全沒有安全性。教材故意這樣選，讓你不用計算機也能驗算每一步，不能直接部署這組參數。真實系統使用大得多、由可靠亂數產生並經過檢查的質數；「難以分解」也只是在既定攻擊方法、資源與時間下的實務判斷，不是數學上永遠無法破解的保證。
7. e 和 d 為什麼會互相解鎖？
d 不是登入密碼；它是依 e 與週期關係算出的模反元素。先決定公開的那一邊
Bob 要選一個公開指數 e。它不能隨便挑：e 必須與剛才算出的 φ(55)=40 互質，才找得到能和它配成一對的數。本例取 e=3；因為 gcd(3,40)=1，這個選擇可用。
現在先問搭檔問題：3 乘上哪個數，除以 40 後會餘 1？
把 d 找出來
逐一試也可以：3×1=3、3×2=6……直到 3×27=81。由於 81=2×40+1，所以 81 mod 40=1，得到 d=27。現在才替這個關係取名字：ed ≡ 1 (mod 40)，而 d 是 e 在模 40 之下的乘法反元素。
現在可以把關係寫得很清楚：e=3、d=27，兩者相乘是 ed=81=1+2×40。也就是兩個完整的 40 步循環，再多走一步。這個「多走一步」正是訊息最後能回到自己的原因。
哪一些能公開，哪一些不能
公鑰是 (n,e)=(55,3)，可以交給 Alice，也可以被 Eve 看見。私密的一側包含 d=27，通常也保留祕密因數與加速運算所需的資料。d 由數學關係算出，和 Bob 自選的登入密碼不同；它和能重建它的材料都需要保護。
工程師延伸：為什麼有時會看到 λ(n)？
這一課使用 Euler 的 φ(n)，因為它最容易接上前面的定理。本例還可以用 Carmichael 函數 λ(55)=lcm(4,10)=20 描述更短的共同週期，而 81 mod 20 同樣等於 1。兩種寫法不會改變本課固定的 e=3、d=27 與往返結果。
8. 公鑰怎麼把 7 鎖成 13？
mod 55；挑選成對指數時用 mod 40，兩個模數不要混在一起。先把 7 當成要送出的代表值
為了專心看數學，我們暫時把 Alice 要處理的內容寫成小整數 m=7。這個 m 叫訊息代表值，不是說真實世界只能加密數字 7；電腦裡的資料本來就會經過編碼，但教材先把那些細節放到一旁。
Alice 已經拿到 Bob 的公鑰 (n,e)=(55,3)。她只需要公開資料就能「上鎖」，公式是 c=m^e mod n。c 代表算完後得到的密文代表值。
一行一行代入
先代入：c=7³ mod 55。再算次方：7³=343。最後找餘數：343=6×55+13，所以 343 mod 55=13。結論是 c=13，也就是教學鏈的前半段 7 → 13。
注意這裡用的是 mod 55。上一節的 mod 40 用來挑選互相配對的 e、d；真正把訊息送進 RSA 運算時，模數是公鑰裡的 n=55。兩個數都在課堂上反覆出現，工作卻不同。
這一步解決了什麼
Alice 能用公開鑰匙把 7 變成 13，不需要接觸 Bob 的 d、p 或 q。Eve 看得到公鑰和 13，也知道整套演算法；RSA 的設計正是假設這些資訊都公開，私密材料仍不能因此被輕易推回。下一節輪到 Bob 使用只有他擁有的那一邊。
9. 私鑰為什麼能把 13 帶回 7？
ed=81=1+2×40，所以對互質的教學值 7 而言，多出的完整週期會繞回 1。Bob 收到的只有 13
傳輸途中，Eve 可以看到 c=13；Bob 看到的也是同一個數。差別在於 Bob 手上有私密指數 d=27。他計算 m=c^d mod n=13²⁷ mod 55，結果會回到 7。
先看為什麼能回來
把加密與解密接在一起，等於先把 m 提高到 e 次方，再把結果提高到 d 次方，合起來就是 m^(ed)。我們已經安排 ed=3×27=81=1+2×40。
對與 55 互質的教學值 7，歐拉定理告訴我們 7⁴⁰ ≡ 1 (mod 55)。因此 7⁸¹=7×(7⁴⁰)²；兩個完整週期都變成 1，只留下前面的 7。金鑰生成時安排的週期關係，讓 13 回到 7，並非巧合。
若想直接驗算 13²⁷，也不必把巨大整數整個展開。反覆平方並隨手取餘數：13²=169=3×55+4，所以先得到 4；13⁴≡4²=16；13⁸≡16²=256=4×55+36；13¹⁶≡36²=1296=23×55+31。
接著利用 27=16+8+2+1，把需要的項目組回來：13²⁷≡31×36×4×13 (mod 55)。逐步取餘數，31×36≡16、16×4≡9、9×13≡7，最後確實回到 7。
把往返結果讀成一句話
公開運算完成 7 → 13，私密運算完成 13 → 7。任何人都能做前一段，只有握有私密材料的 Bob 應該能有效完成後一段。這是玩具 RSA 最核心的機械結構；它讓我們看懂公私鑰如何配對，並不代表這組小數字可以保護任何真實資料。
工程師延伸：不互質的代表值怎麼辦？
若代表值剛好含有因數 5 或 11，不能直接引用 gcd(m,55)=1 的 Euler 敘述。完整證明會分別在 mod 5 與 mod 11 下看結果：能用 Fermat 的部分照週期走，整除該質數的部分則同時保持為 0；兩邊一致後，再合回唯一的 mod 55 結果。這就是主線沒有把「互質」條件偷偷刪掉的原因。[1]
10. 這把公鑰真的屬於 Bob 嗎？
公開不等於自帶姓名
Bob 可以把公鑰貼在網站上，Alice 也能順利用它計算。可是公鑰本身只是一組資料，不會自己站起來說「我真的屬於 Bob」。如果 Eve 攔下連線，換成自己的公鑰，再貼上 Bob 的名字，Alice 仍會得到一個數學上完全有效的結果。
問題在於，那份祕密其實鎖給了 Eve。RSA 沒有算錯，公鑰與私鑰也各自成對；Alice 錯的是把「能使用的公鑰」誤認成「Bob 的公鑰」。
這裡要檢查的不是乘法
假設 Bob 事先用另一條可信管道告訴 Alice 公鑰指紋，Alice 就能核對收到的鑰匙是否相同。真實網路也常使用憑證與信任鏈，把公開金鑰、主體名稱、簽發者與有效期限放在可驗證的結構裡。應用程式還是要檢查名稱、期限與信任路徑；不是看到「有憑證」三個字就全部接受。[4]
把兩個問題分開記
第一個問題是數學配對：這把公鑰與某把私鑰能不能互相還原？第二個問題是身分：那把私鑰真的由 Bob 控制嗎？RSA 的算式回答前者，可信指紋、憑證或另一條可信聯絡管道協助回答後者。只有兩邊都成立，Alice 才知道自己鎖對了人。
11. 「交換金鑰」其實有兩種故事
先用兩種日常情境來分
第一種像 Alice 挑好一把房門鑰匙，裝進只有 Bob 能開的盒子，再寄給 Bob。最後兩人都有同一把鑰匙，但它一開始是 Alice 決定的。這叫「金鑰傳遞」（key transport）。RSA 可以參與的，是這種一方先選好祕密，再用對方已驗證的公鑰保護它的路徑。[2]
第二種比較像兩人各帶一種材料，在公開桌面上依規則混合，最後各自在手邊得到相同顏色；完整結果不是任何一方單獨先挑好的。這叫「金鑰協議」（key agreement），Diffie–Hellman 是經典的歷史例子。[3]
不用公式，也能問對問題
只要問一句：「最後那個共享祕密，是誰決定的？」若 Alice 先選 K，Bob 只是安全收到，就是傳遞；若 Alice 與 Bob 都提供資訊，再各自在本地導出同一個 K，就是協議。兩條路的終點看起來相似，過程與安全性質卻不完全相同。
回到開場的 Alice 與 Bob
第 1 頁問「第一把祕密鑰匙怎麼安全到達？」現在有了比較精確的答案：公開金鑰技術能協助兩端建立共同祕密，但「一方送過去」與「雙方一起算出來」要分開說。無論採哪一條路，還是得確認對方身分、保護私密材料，並使用可靠亂數與成熟實作。
12. 把 RSA 的故事重新走一遍
從第一把鑰匙回看往返算例
Bob 做出一個人人都能使用的公開鎖法，卻把開鎖能力留在自己手上。質數提供了容易相乘、但在尺寸夠大時不容易從乘積找回因數的不對稱；餘數運算把數字放進會繞圈的世界；費馬與歐拉告訴我們，這些冪次在適當條件下會回到 1。
再看一次完整數字鏈
先選 p=5、q=11，得到 n=55 與 φ(n)=40。選公開指數 e=3，再找出 d=27，因為 3×27=81=1+2×40。於是公鑰是 (55,3)，私密的一側保護 d=27 與相關材料。
Alice 使用公開鑰匙：7³ mod 55=13。Bob 使用私密鑰匙：13²⁷ mod 55=7。整條玩具路徑就是 7 → 13 → 7；每個數字都有前一節交代過的來源，沒有任何魔法常數。
最後回到可靠系統
漂亮公式只回答「這對鑰匙為什麼能配合」。要成為可靠系統，還要妥善產生與保管私密材料、確認公鑰主人、選擇合適的金鑰建立方式，並交給成熟函式庫實作。這些邊界也決定真實安全性，不能當成數學之外的雜事。
五點帶走
- RSA 從「第一把祕密鑰匙怎麼安全交給對方」的難題出發：公開鎖法，保護開法。
- 質數相乘得到公開
n；安全直覺來自巨大n難以回推祕密因數。 - 餘數運算、費馬、歐拉與
φ(n)建立了指數循環；d是算出來的模反元素，不是登入密碼。 - 本課固定手算鏈為
p=5、q=11、n=55、φ=40、e=3、d=27，結果是7 → 13 → 7。 - 數學配對不等於身分可信；「一方送出祕密」與「雙方共同導出祕密」也不是同一件事。
想再往下一層，可以接著讀 Shor 漫畫小教室，看看大型量子電腦為什麼會改變 RSA 背後的因數分解假設。
References
- Rivest, Shamir & Adleman（1978），Communications of the ACM 21(2), 120–126：RSA 原始構造、公開／私密程序、歐拉／費馬正確性與金鑰配送背景。
- NIST SP 800-56B Rev. 2：整數分解密碼學的金鑰建立與金鑰傳遞用語。
- Diffie & Hellman（1976），IEEE Transactions on Information Theory 22(6), 644–654：公開通道上的金鑰協議經典模型。
- RFC 5280，Internet X.509 Public Key Infrastructure Certificate and CRL Profile：公開金鑰、主體名稱與憑證信任路徑。
親手驗算 RSA 的往返
把訊息代表值改成 5，再走完加密與解密。5 和 55 不互質，仍會還原：這能檢查正文「不能只引用 Euler 定理」的提醒。勾選途中改動，再觀察收到的密文與還原值。
固定 p=5、q=11、e=3、d=27。小整數 RSA 沒有 padding，完全不安全；算例正確也不證明來源或完整性。
學習指南
安全基礎
查看課程大綱 → · 進度只計入已發布課程
先備知識
- 只需基本算術，不要求密碼學基礎
我學會了什麼
- 說明公開金鑰密碼如何處理第一次共享祕密的難題
- 把質數、模運算、費馬定理與 Euler 定理串成 RSA 的數學路線
- 建立 n = 55、e = 3、d = 27 的玩具金鑰對
- 驗算完整的 7 → 13 → 7 教學算例
- 區分金鑰傳遞、金鑰協議與公鑰身分確認