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

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

質(zhì)數(shù)為什么能用于加密算法？

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

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

什么是RSA加密算法？

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

信息加密

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

信息解密

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

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

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