質數如何用於信息加密？

加密

黑客如果試圖用每秒鐘測試100萬個組合的計算機，來破解隱藏銀行卡信息的400位加密編碼，大約需要10^194秒才能完成這一壯舉。相比之下，宇宙年齡不到10^18秒。就目前而言，破解這樣的密碼似乎是一項相當繁瑣的任務。

早在17世紀，以費馬大定理而聞名的費馬發明了一種精妙的方法，來確定一個數字是質數還是合數時，其他人無法理解這個證明的實用性。這個證明被認為就像一尊雕像，美麗但無用。那時，關於質數的發現僅僅是為了揭示和理解數學中隱藏的複雜性，它們還沒有為現實世界的問題提供任何實質性的解決方案。

直到400年後互聯網誕生之時，數十億用戶的隱私，從機密的電子郵件內容到電子商務網站的交易都完全依賴於質數。那麼，質數是如何被用於加密的呢？

黑客

質數只能被1和自身整除，它們通常被稱為數字領域的「原子」，因為它們是構成每個數字基本的、不可分割的單位。例如，10可以寫成2和5的乘積，這就是兩個質數。或者150作為15和10的乘積，可以進一步分解，寫成是3和5、2和5的乘積，這些都是質數。又或者，更大的數字，比如126356，可由更大的質數組成，2、2、31和1019。

在數學中，把一個合數變成質數乘積的過程被稱為質因子分解。對於一台計算機來說，把兩個很大的質數相乘，即使每一個質數長達100位，計算出結果也並不難。然而，把一個很大的數分解成質數的乘積則是出了名的困難，即使對於超級計算機來說也是如此。這個難點被李維斯特、薩莫爾和阿德曼三位數學家在1977年發明的RSA加密演算法時利用。

加密

假設C是兩個質數P和Q的乘積，當加密時，比如加密銀行卡信息，數字C被用來生成公開密匙，即公鑰。正如其名字所示，這個密鑰是公開的，這意味著它可以被網路中的任何人攔截和讀取。眾所周知，銀行使用的公鑰長度為1024位（309位數字），以確保私人交易信息。

通過把一個公鑰鎖在一個「盒子」中，它的句柄與一個幾百位數的組合密碼鎖緊密地結合在一起，從而保護私有信息。這個盒子本身可以被任何人訪問，但是裡面的內容不行。當一個黑客想暗中竊取這個盒子，他在不知道密碼組合以及沒有私鑰的情況下不可能解鎖它。這個私鑰只由信息發送者和接收者——銀行和用戶所持有。

RSA加密演算法

在不知道私鑰的情況下，黑客必須把C進行質因子分解，如果這個數很大，位數達到上千位，他可能要花上幾千年的時間才能分解出來。這是因為把一個很大的數分解成兩個較大質數相當困難，有些質數確實可以很大。目前已知最大的質數為2^77232917-1，它的素性已經被計算機驗證了。這個數有2300萬位，如果要把這個數字寫在A4紙上，寫完這個數估計要用4500張。

雖然大數的分解質因數並非不可能，只是所需耗費的時間太長。隨著技術的進步，我們也許能夠更快地處理數字。量子計算機可能會實現這一目標，但目前，在它們變得功能齊全、普遍存在之前，還有很長的路要走。目前，計算機分解的最大數達到了768位（232位數字），而現行公鑰為1024位（309位數字），有些甚至已經升級到2048位（617位數字），所以我們基本上不用擔心信息被泄露。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！