什麼是打破網際網路加密的人類最強數學「一般數體篩法（GNFS）」？

我們每天使用的網際網路。LINE 訊息、YouTube、Amazon 購物等，所有的通訊都受到「加密」保護。目前世界上最廣泛使用的加密技術代表是「RSA 加密」。

RSA 加密防禦的核心非常簡單。它利用了 ** 「即使是電腦也無法解開巨大數字的質因數分解」 ** 這個數學特性。例如，「15」我們馬上就知道是「3 × 5」，但一旦變成「270 位數的數字」，即使集結全世界的超級電腦，也需要耗費數億年才能解開。

然而，數學家們並沒有閒著。為了打破這道堅不可摧的密碼防線，人類創造了一種宛如魔法般的演算法（計算步驟），稱為 ** 「一般數體篩法（GNFS：General Number Field Sieve）」 ** 。

在這篇文章中，我們完全不使用專業術語，僅使用 ** 國中學到的數學（質因數分解、代數式、最大公因數） ** 知識，一步步徹底解說這個「人類最強演算法」破解密碼的原理！

第 1 章：破解密碼的目標是「國三的公式」

面對巨大質因數分解的最大必殺技。這就是在國三學到的這個公式。

** $X^2 - Y^2 = (X + Y)(X - Y)$ **

你可能會想：「咦，這麼基礎的公式就能破解密碼嗎？」。然而，這正是解開一切的萬能鑰匙。

破解密碼的最終目標，對於一個巨大的數字 $N$，就是找到 ** 「將 $X^2$ 和 $Y^2$ 除以 $N$ 後，餘數會相同的數字（$X$ 和 $Y$）」 ** 。

為什麼「餘數相同」就能破解密碼？

假設有兩個數字 $X^2$ 和 $Y^2$，它們「除以 $N$ 的餘數相同」。餘數相同代表著，相減後的 ** 「$X^2 - Y^2$」必定能被 $N$ 整除（成為 $N$ 的倍數） ** ，這是一個法則。

在這裡，我們假設用於加密的巨大數字 $N$ 是由兩個秘密質數（$p$ 和 $q$）相乘而成的（$N = p \times q$）。

將 $X^2 - Y^2$ 因式分解後會變成 ** $(X - Y)(X + Y)$ ** 。這成為 $N$ 的倍數，意味著在這個乘法中的某處，隱藏著秘密質數 $p$ 和 $q$。

奇蹟在此發生。這兩個質數 $p$ 和 $q$，有 ** 50%（二分之一） ** 的數學機率，會分開進入不同的房間： ** 「$p$ 進入 $(X - Y)$ 的房間」和「$q$ 進入 $(X + Y)$ 的房間」 ** 。

在只有質數 $p$ 進入 $(X - Y)$ 房間的狀態下，讓我們計算 $(X - Y)$ 和 $N$ 的 ** 「最大公因數（共通的最大零件）」 ** 。

$(X - Y)$ 的內容＝ $p \times$ 某個數字
$N$ 的內容＝ $p \times q$ 共通的零件只有 ** 「$p$」 ** ！

也就是說，在計算出最大公因數的瞬間，隱藏的質數 $p$ 就會掉出來，密碼就被完全破解了。（※最大公因數只要使用「輾轉相除法」，用手機也能瞬間計算出來）

** 【小專欄：為什麼是 2 次方？3 次方或 2 倍不行嗎？】 **

如果是「$2X - 2Y$」會變成 $2(X - Y)$，因為只有一個房間，所以無法將質數分開。如果是「$X^3 - Y^3$」，房間的大小會變得不平衡，計算會變得不必要的繁重。為了將質數漂亮地分開到兩個房間，「2 次方」是成本效益最高的。

第 2 章：如何尋找 X 和 Y？「收集質數卡片的拼圖」

目標已經很清楚了。但是，如果盲目地尋找「餘數相同的 $X^2$ 和 $Y^2$」，直到宇宙毀滅也找不到。因此，數學家們想出了一個被稱為 ** 「收集質數卡片的拼圖」 ** 的天才方法。

Step 1：只用篩子收集沙金（平滑數）

首先，準備一個適當的數字 $Z$，將其平方後除以 $N$ 算出餘數 $W$。（$Z^2 = W$ 的餘數世界）

將得出的餘數 $W$ 進行質因數分解。在這裡，只有當出現 ** 「只由 2、3、5、7 等小質數組成的 $W$」 ** 時，才將該算式作為「中獎卡片」保留下來，如果混入了大的質數就丟棄。這就像在河裡用篩子過濾掉大石頭，只收集沙金一樣的作業。

Step 2：全部變成「偶數個」的拼圖

例如，假設收集到了以下 3 張沙金卡片。

卡片 A： $Z_1^2 = 2^3 \times 3^1$
卡片 B： $Z_2^2 = 2^1 \times 5^1$
卡片 C： $Z_3^2 = 3^1 \times 5^1$

我們將這些全部相乘。右側會變成 $(2^3 \times 3^1) \times (2^1 \times 5^1) \times (3^1 \times 5^1)$，整理過後會變成 ** 「$2^4 \times 3^2 \times 5^2$」 ** 。

令人驚訝的是，質數的個數變成了「4 個、2 個、2 個」， ** 全部都是偶數個 ** ！全部都是偶數個，意味著只要將整體的數量減半，就會變成「某個東西的平方」。也就是說，$(2^2 \times 3^1 \times 5^1)^2 = (60)^2$.

左側是 $(Z_1 \times Z_2 \times Z_3)^2$，所以終於， ** $X = (Z_1 \times Z_2 \times Z_3)$ ** ** $Y = 60$ ** 這對期待已久的「$X^2 = Y^2$」組合就完成了！

對於電腦來說，計算質數個數「是偶數還是奇數（0 或 1）」的拼圖是它們非常擅長的，所以用這個方法就能高速找到 $X$ 和 $Y$。

第 3 章：阻擋在前方的絕望之壁

這樣就能破解任何密碼了！……正當我們這麼想時，大問題發生了。如果密碼數字 $N$ 大約在「100 位數」以內，用這個方法（稱為二次篩法）是可以解開的，但當 $N$ 變成「200 位數、300 位數」時，計算過程中出現的 $W$ 就會變得太大。

數字一旦變得太大，「只由小質數組成的數字（沙金）」就不再出現。這變得比在沙漠中尋找隱形眼鏡還要困難，完全無法收集到解開拼圖所需的卡片。

這時候，人類的最終兵器 ** 「一般數體篩法（GNFS）」 ** 終於登場了。

第 4 章：人類最強的想法，創造「兩個世界」

GNFS 的天才發想是： ** 「因為只在現實世界中計算，所以數字才會變得巨大。那麼，我們就用多項式（代數式）創造一個『裏世界』，將計算的負擔分散成兩半吧。」 **

代數式的魔法

GNFS 使用一個基準數字 $m$，將巨大的數字 $N$ 轉換成代數式。例如如果 $N=100$，設 $m=4$，則 $100 = 4^3 + 2(4^2) + 4$。使用字母 $x$ 將其變成 ** $f(x) = x^3 + 2x^2 + x$ ** 這個算式（裏世界）。

這個算式有趣的地方在於，它具有 ** 「只要將字母 $x$ 代入 $m$（在上面的例子中是 4），隨時都能瞬間移動回到現實數字 $N$」 ** 的特性。

在兩個世界中同時尋找沙金

GNFS 製造出許多隨機的整數對 $(a, b)$，並同時進行以下兩個計算：

** 現實世界 ** ： $a - b \times m$
** 代數式的世界 ** ：依照代數式規則計算 $a - b \times x$ 的值

藉由將問題分成兩個世界，處理的數字大小會戲劇性地變小（變輕）。這就像是把巨大的岩石劈成兩半，變成容易處理的石塊一樣的概念。

然後，我們用篩子過濾，只收集那些在 ** 「現實世界和代數式的世界中，兩者都是『只由小質數組成（沙金）』」 ** 的奇蹟整數對 $(a, b)$。這就是「數體篩法」名稱的由來。

密碼終於被破解的瞬間

當從兩個世界收集到數千萬張「沙金卡片」後，就會使用超級電腦的巨大矩陣計算，找出在第 2 章做過的「質數個數全部變成偶數的組合」。

找到組合後，

將現實世界中產生的平方數設為 ** $X^2$ **
將代數式世界中產生的平方算式設為 ** $Y(x)^2$ **

最後，將代數式 $Y(x)$ 中的 $x$ 代入 $m$，使其瞬間移動到現實世界並會合。這樣一來，宛如數學魔法般， ** 「$X^2$ 和 $Y^2$ 的餘數相同」 ** 的狀態就嚴格地完成了！

接下來只要按照第 1 章的說明，計算 $X - Y$ 和 $N$ 的最大公因數，堅不可摧的 RSA 加密就會應聲瓦解，秘密質數也將隨之現身。

結語：數學永無止境

你可能會想：「太好了，只要用 GNFS 就能破解任何密碼了吧！」。然而，RSA 加密也沒有認輸。目前網際網路上使用的是被稱為「RSA-2048（約 617 位數）」這種怪物級的巨大數字。

儘管 GNFS 號稱是人類最強的演算法，但要解開 270 位數（RSA-270），據說即使將全世界的電腦連線在一起，也需要數千年甚至數萬年。就目前而言，我們的 LINE 或銀行資料還是安全的。

不過，如果出現了 ** 「能瞬間找出任何巨大數字 $X$ 和 $Y$ 的魔法」 ** 會怎麼樣呢？事實上，最接近這個存在的，就是目前正在開發的 ** 「量子電腦（Shor 演算法）」 ** 。數學上已經證明，只要利用量子力學波的特性，就能無視麻煩的卡片收集拼圖，一次就抽出正確答案。

製造密碼的人（防禦）與製造破解密碼演算法的人（攻擊）之間，無止盡的鬥智。當你知道國中學到的「質因數分解」和「代數式」，其實是在世界資安最前線激烈交鋒的武器時，是否覺得數學課變得稍微有趣一點了呢？

發現未來最強演算法的人，或許就是正在讀這篇文章的你！

(※本文為了讓中學生能理解，將密碼破解的數學魅力概念化。實際的 GNFS 是使用了代數體的理想類群、同態映射等高等大學數學來進行嚴格計算的)