後量子密碼學（二）：數學難題

難題, The hard problem

生存還是毀滅，這是一個值得考慮的問題

-莎士比亞, 哈姆雷特

在後量子密碼學（一）的文章中我們提到：「目前常見的公鑰密碼系統，如 RSA (Rivest-Shamir-Adleman) 和 ECC (Elliptic Curve Cryptography) 在隨著量子計算技術的發展，RSA、ECC將可被 Shor 演算法破解。」

很自然的我們會想到：

究竟密碼系統被破解是什麼意思？破解密碼系統很困難嗎？
有補救的機會嗎？修復密碼系統很困難嗎？

這得從公鑰密碼系統從什麼問題建構說起。實際上，現今主流使用的RSA與ECC都是建立在很難的數學問題上，用數學問題困難的本質來保護密碼系統。對了解公鑰密碼系統而言，最開始的起點就是了解背後所依賴的數學難題。

數學難題與量子電腦

大數分解難題與RSA

就讓我們從簡單的計算來小事身手吧！如果我們手上有兩個質數$p_{1}=9886847,p_{2}=1372933$，那對我們而言，計算他們的乘積 $p_{1}p_{2}$ 不是一件太困難的事情，透過計算機或者手算都很容易計算出來 $ p_{1}p_{2}=13573978512251。 $

然而，如果我們把問題反過來問呢？給定 $n=13573978512251$是兩個大質數的乘積，問說如何找到 $p_{1}, p_{2}$ 使得$n=p_{1}p_{2}$？

計算乘積$p_{1}p_{2}$ 與分解$n$兩個問題是同個數學問題的一體兩面。然而，這大大顯示了分解的計算困難度遠超於單純計算。分解一個大數成為兩個質數的乘積，被稱為大數分解問題。即使將大數分解問題透過電腦來計算，對傳統電腦而言，這也是十分困難的！透過大數分解問題，密碼學家 Rivest、Shamir 與 Adleman 發展了RSA。RSA 的安全性建立在大數分解這個分解問題的計算複雜度之上。

透過這個例子，我們了解到：

密碼系統的安全性背後都建立在計算難題之上

換言之，如果一個密碼系統背後的數學難題被攻破了，則這個密碼系統就被完全破解了！

現今常用的公鑰密碼系統大多都建立在大數分解問題（RSA）、離散對數問題（ECC）之上，這兩個問題對傳統電腦而言都是非常困難且無法破解的問題。

量子電腦與威脅

不幸的是，雖然大數分解問題與離散對數問題雖然對傳統電腦而言是非常困難的，但是對量子電腦而言，這兩個問題卻是量子電腦擅長的範圍。透過秀爾演算法，量子電腦能攻克大數分解問題、離散對數問題。這便是為什麼量子電腦會攻破現今密碼系統的原因：

量子電腦＋秀爾演算法＝攻破大數分解、離散對數問題

這也是為什麼我們需要PQC，PQC的密碼系統建立在不同的五個數學難題上，這五個數學難題與大數分解問題、離散對數問題相異，這些問題的數學難度被相信是連量子電腦都無法破解的。這也是PQC成為熱門研究領域且是世界要採用PQC的原因。