為什麽質數能被用於加密算法？

素數或者說質數，是指只能被1和自身整除的大於1的自然數。對於其他比1大的自然數，它們就都是合數，能夠被除了1和自身之外的其他數整數。顯然，質數和質數相乘所得到的數必然是合數。

一直以來，質數的研究被認為只有純數學上的意義，實際並沒有什麽價值。直到上個世紀70年代，麻省理工學院（MIT）的三位數學家李維斯特、薩莫爾和阿德曼共同提出了一種公開密鑰加密算法，也就是後來被廣泛應用於銀行加密的RSA算法，人們才認識到了質數的巨大作用。

質數為什麽能用於加密算法？

這個問題就要涉及到大數的質因數分解。如果把一個由較小的兩個質數相乘得到一個合數，將其分解成兩個質數（除了1和自身的組合之外）很容易，例如，51的兩個質因數為3和17。然而，如果兩個很大的質數相乘之後得到一個非常大的合數，想要逆過來把該數分解成兩個質數非常困難。例如，511883，分解成兩個質因數之後為557和919；2538952327（超過25億），分解成兩個質因數之後為29179和87013，這個難度明顯要比上一個數大得多。

截至今年一月份，目前已知最大的質數是2^82589933?1，這個數擁有超過2486萬位。即便是超級計算機，也很難有效對兩個質數相乘得到的合數進行質因數分解，所以這樣的原理可以用於加密算法。

什麽是RSA加密算法？

RSA算法是一種非對稱加密算法，加密和解密所用的密鑰是不一樣的，解密所用的密鑰對應於加密所用的密鑰。假設甲向乙發送信息a，那麽，a是需要進行加密的信息；再假設b是一個由兩個質數相乘得到的合數；c是一個與歐拉函數有關的數，這是公鑰；d是c關於歐拉函數值的模倒數，d就是私鑰。

信息加密

乙在產生合數b和公鑰c、私鑰d之後，乙會把b和c傳給甲，d則保密不被傳輸。甲利用公鑰c對信息a進行加密，即計算a^c除以b的余數e，即a^c mod b=e，所得到的e就是密文。於是，甲把密文e傳送給乙。

信息解密

乙在得到密文之後，利用私鑰d對密文e進行解密。可以證明，e^d除以b的余數正是信息a，即e^d mod b=a，這樣就完成了信息的解密。

由於合數b、公鑰c、密文e都會被傳送，這些信息就有可能被竊取。如果竊取者想要破解信息，需要知道私鑰d。想要通過公鑰c來算出密鑰d，就需要對合數b進行質因數分解。但合數b是由兩個質數相乘得到的大數，想要成功分解該數極其困難。

目前，RSA加密算法用到的大數已經有數百位，它們一般都是分解成兩個上百位的質數。如果繼續增加大數的位數，還能進一步降低被破解的風險。因此，RSA加密算法的安全性能十分有保障，這就是為什麽它會被廣泛應用的原因。