小學(xué)時學(xué)過的質(zhì)數(shù)
小學(xué)數(shù)學(xué)課上我們都學(xué)過質(zhì)數(shù)，也叫素數(shù)，就是大于1的整數(shù)，除了1和它自身外沒有別的因子。很明顯4不是質(zhì)數(shù)，因為4=1×4=2×2，除了1和它本身外，2也是它的因子。
“質(zhì)數(shù)”是咱們中國的稱呼，老外那邊叫“prime number”。
那么，小學(xué)時學(xué)的“質(zhì)數(shù)”到底有什么用？什么時候用呢？
我們每天都在用質(zhì)數(shù)
其實我們每天上網(wǎng)的時候都會用到質(zhì)數(shù)，比如上百度，淘寶，京東，微博、拼多多等網(wǎng)站時。（如果你是使用Git的程序員的話，就更會用到質(zhì)數(shù)-SSH公鑰體系）
“上網(wǎng)時沒有用質(zhì)數(shù)啊”這應(yīng)該是大多數(shù)人的想法。不過，你確實用了。這些網(wǎng)址的開頭都是“https”，在你登錄這些網(wǎng)站的時候，瀏覽器和網(wǎng)站之間的信息傳輸就用到了質(zhì)數(shù)進(jìn)行加解密。小學(xué)數(shù)學(xué)老師沒告訴我們，但這是真的。
不光人類使用質(zhì)數(shù)，動物也會使用質(zhì)數(shù)。
懂?dāng)?shù)學(xué)的蟬
其實動物對質(zhì)數(shù)的應(yīng)用要早于人類，最有名的例子就是北美的周期蟬。周期蟬有兩種，13年蟬和17年蟬（注意，都是質(zhì)數(shù)）。以美國喬治亞州的17年蟬為例，2000年的時候出現(xiàn)過一次，再次出現(xiàn)就是2017年（從2002~2016年間沒有出現(xiàn)），下一次就是2034年......很奇怪的一個現(xiàn)象。
為這么周期蟬總是間隔質(zhì)數(shù)年后出現(xiàn)？科學(xué)家猜測其原因是：避開周期性出現(xiàn)的天敵。蟬的天敵也有周期，如果生命周期不是質(zhì)數(shù)，和天敵周期重合的概率就會大很多。假設(shè)蟬的周期是12年，就會和周期為2、3、4、6年的天敵重合。所以有些人把周期蟬稱為懂?dāng)?shù)學(xué)的蟬。
但上述理論并不完美，因為有些天敵是年年有的，比如鳥，17年蟬也無法幸免于難。所以現(xiàn)在科學(xué)家也沒完全解釋13年蟬和17年蟬周期性出現(xiàn)的原因。而且，中國南方的蟬是年年有的。盡管如此，人們還是把周期蟬稱為“懂?dāng)?shù)學(xué)的蟬”。
周期蟬的生命周期為什么是質(zhì)數(shù)仍是個謎，但人類使用質(zhì)數(shù)的原因就非常確定。除了前面提到的上網(wǎng)，我們還在哪些領(lǐng)域使用質(zhì)數(shù)呢？
在齒輪嚙合上。相鄰的兩個齒輪是互質(zhì)的（比如48/17），避免齒輪中固定的兩個齒反復(fù)接觸，延長齒輪的壽命（如果是48/16的話，某些齒會頻繁接觸，而某兩個齒永遠(yuǎn)都不會接觸，這對齒輪壽命不利）。
從上面的例子看，質(zhì)數(shù)還是挺有用的。
從“玩具”到影響世界
盡管現(xiàn)在我們每天都會使用質(zhì)數(shù)，但在歷史上很長一段時間里質(zhì)數(shù)只是數(shù)學(xué)家們的“玩具”，沒有任何實用性。
“很長一段時間”到底是多長呢？可以負(fù)責(zé)任的告訴你，至少兩千多年。
古希臘的數(shù)學(xué)家歐幾里得在公元前300年左右（中國的戰(zhàn)國時期，那時屈原還健在，秦始皇要等到59年后才會出生）就證明了存在無數(shù)個質(zhì)數(shù)。但是人們（包括數(shù)學(xué)家們）始終不知道質(zhì)數(shù)除了讓數(shù)學(xué)家消遣娛樂之外還有啥用（不得不說，古代數(shù)學(xué)家們消遣娛樂的方式真是奇特）。英國的大數(shù)學(xué)家哈代（不是寫小說的那個托馬斯·哈代）就曾經(jīng)在1940年自豪地說“過去沒有人發(fā)現(xiàn)這些數(shù)（質(zhì)數(shù)）及其理論用在軍事上，未來很多年也不會”。
哈代并沒有給“未來很多年”加一個期限，所以我們不知道他所認(rèn)為的“很多年”到底是多少年。但現(xiàn)在我們可以給它加一個期限：33年。
在1973年的時候英國政府通信總部的數(shù)學(xué)家就提出了公鑰加密算法，但當(dāng)時該算法屬于政府絕密信息，直到1997年才被解密。
美國的兩個學(xué)者在1976年提出了公鑰密碼學(xué)，引起了學(xué)術(shù)界的轟動。
1977年麻省理工學(xué)院的3位密碼學(xué)家提出了實際的公鑰密碼學(xué)方案，就是使用至今的RSA算法，用他們3人的姓氏的首字母命名。RSA中用的就是質(zhì)數(shù)。
RSA算法中關(guān)鍵的一步就是生成2個大質(zhì)數(shù)p和q。在PKCS# v2.1及后續(xù)版本中，允許使用多個質(zhì)數(shù)（PKCS，Public Key Cryptography Standards，公鑰密碼學(xué)標(biāo)準(zhǔn)）。兩個大質(zhì)數(shù)求乘積很容易，但是分解該乘積卻非常難，這決定了RSA算法的安全性。
RSA算法在全球商業(yè)領(lǐng)域取得了巨大的成功（"知識就是力量"——培根），至今仍是全球最流程的公鑰加密算法，三位作者也順勢在1982年成立了RSA Security公司（“知識就是金錢”）。
RSA公司很多人都沒聽過，畢竟它只是一家2B的公司。不過在2013年的“棱鏡門”泄密事件中，RSA公司卻得到了超高的曝光率。借用《潛伏》里吳站長的一句話：本來想露臉，結(jié)果把屁股露出來了！據(jù)路透社報道，RSA公司收了NSA（美國國家安全局）1000萬美金，在其軟件BSafe中默認(rèn)使用被RSA植入后門的隨機數(shù)生成算法DUAL_EC_DRBG，這部分內(nèi)容在“戲說密碼學(xué):(2)密碼的破譯方法”中我們詳細(xì)講過。
咱們先看看RSA算法能干啥。
RSA能干啥
RSA算法主要是用來數(shù)據(jù)加密和數(shù)字簽名。
RSA的神奇之處在于它有一個公鑰和一個私鑰，公鑰可以公開，任何人都可以用，私鑰只能你自己用，必須保護(hù)好。公鑰加密的信息只能用私鑰解密（公鑰也解不開，就是這么神奇）。
這根我們平常理解的加密不一樣。加密相當(dāng)于上鎖，解密相當(dāng)于開鎖。日常生活中上鎖和開鎖用的是同一把鑰匙（家家的鎖都是這樣的），沒有問題，但是在上網(wǎng)時這樣做是有問題的。
有什么問題呢？
假如說你登錄網(wǎng)上銀行給朋友轉(zhuǎn)賬，不幸的是你被黑客盯上了。當(dāng)你在網(wǎng)銀上填寫朋友的賬號和轉(zhuǎn)賬金額后，賬號和金額會通過互聯(lián)網(wǎng)傳給銀行。當(dāng)然，這中間需要經(jīng)過很多路由器（比如你家的路由器）。黑客完全可以截獲你發(fā)給銀行的信息（太容易了），然后把你轉(zhuǎn)賬的目標(biāo)賬號修改成他的賬號，這樣錢就到他那兒了，太危險了。
為了避免上面的情況發(fā)生，你填寫的目標(biāo)賬號和轉(zhuǎn)賬金額都是加密后傳給銀行（雖然你沒有看到，但是瀏覽器默默幫你加密了），這下黑客沒辦法了吧？還是有辦法的！
你登錄網(wǎng)銀的時候，銀行會把秘鑰傳給你的瀏覽器，黑客當(dāng)然也能截獲秘鑰。剛才我們說了，加密和解密用同一個秘鑰（鑰匙），黑客截獲了你和銀行間的秘鑰，就能解開加密的數(shù)據(jù)，還是可以把你轉(zhuǎn)賬的目標(biāo)賬號換成他的賬號。這下郁悶了：還能不能開心的用網(wǎng)銀轉(zhuǎn)賬了？難道非得親自去銀行柜臺辦理？
先看看問題的根源：由于黑客能截獲你和銀行之間的所有信息，所以無論發(fā)送的是秘鑰還是賬號，統(tǒng)統(tǒng)都逃不過黑客的眼睛。這時候加密形同虛設(shè)了。那怎么才能安全的轉(zhuǎn)賬呢？
現(xiàn)在該RSA算法展示真正的技術(shù)了！
假設(shè)銀行放棄了上面的加密方式，轉(zhuǎn)而使用RSA算法。當(dāng)你登錄網(wǎng)銀的時候，銀行先把它的公鑰發(fā)給你的瀏覽器（公鑰可以給任何人看，包括黑客），當(dāng)你輸入轉(zhuǎn)賬金額和賬號后，瀏覽器先用銀行的公鑰進(jìn)行加密，然后發(fā)給銀行。注意，公鑰加密的數(shù)據(jù)只能用私鑰解密，而私鑰在銀行手里！這時黑客截獲了加密數(shù)據(jù)也無法解密，此時黑客的內(nèi)心是痛苦的：我沒有銀行的私鑰?。∵@樣我們就安全的完成了網(wǎng)銀轉(zhuǎn)賬。
這就是RSA算法的神奇之處。RSA算法實現(xiàn)了在不安全信道上進(jìn)行數(shù)據(jù)的安全傳輸。
RSA算法不僅可以用于銀行系統(tǒng)，還可以用于個人間的數(shù)據(jù)安全分享。比如說你和朋友想分享一些文件，但是你倆的網(wǎng)絡(luò)被黑客監(jiān)控了。這時你可以和朋友交換公鑰，把要分享的文件先通過他的公鑰加密后發(fā)給他，黑客由于沒有你朋友的私鑰而無法解密，只有你朋友能解密。你朋友用同樣的方法把他的文件加密分享給你。進(jìn)一步擴展，任何兩個單位/個人之見都可以通過這種方式加密分享數(shù)據(jù)，而不用擔(dān)心被黑客解密。
這么看來，RSA算法既神奇又實用！
前些年大起大落的比特幣（區(qū)塊鏈技術(shù)），用的就是公鑰密碼算法，雖然不是RSA算法，但原理相同。
自從誕生的那一天起，RSA算法就接受來自全球黑客、學(xué)者、研究人員的攻擊。40多年過去了，事實證明RSA算法很安全，只要你的秘鑰夠長。RSA秘鑰長度通常是1024~4096位。2010年的時候攻破了RSA-768，一些專家認(rèn)為RSA-1024在不遠(yuǎn)的未來會被攻破，但沒幾乎有人認(rèn)為RS-4096能夠在可預(yù)見的未來被攻破。
RSA還有一個作用就是數(shù)字簽名，這是后話。
RSA算法的缺點：慢
是的，盡管RSA算法即安全又神奇，但是它的計算速度很慢，比AES算法慢了不止千倍萬倍。以RSA-4096為例（安全強度介于AES-128和AES-192之間）和AES-256做對比，在Intel Core i7-7700 CPU、16GB RAM的Windows 10電腦上，RSA-4096解密1000次大概需要34.7秒（如果在解密軟件中讓用戶等34秒，估計開發(fā)人員會餓死），而AES-256解密1000次只需0.44ms。二者之間大概差了十萬倍。
所以通常把RSA算法和AES算法一起使用，先用RSA算法在不安全信道上傳輸AES的秘鑰，后續(xù)就用AES進(jìn)行數(shù)據(jù)加解密。這樣既安全又快速——so easy!
為了增強RSA的安全性，還會對數(shù)據(jù)進(jìn)行填充，就是摻入一些亂七八糟的數(shù)據(jù)，讓原來的數(shù)據(jù)看起來更亂。常用的有PKCS#1填充（已經(jīng)不安全）和OAEP（最優(yōu)非對稱加密填充，Optimal asymmetric encryption padding）填充。
RSA中的因式分解到底有多難？
因式分解的難度決定了RSA算法的安全性，這是RSA算法的命門所在。那么因式分解一個大數(shù)據(jù)到底有多難呢？
下面是RSA-4096生成的參數(shù)，其中n=p*q。如果只知道n而不知道p和q，現(xiàn)有的技術(shù)想要分解出p和q，需要很長很長時間?！昂荛L很長”是多長呢？科學(xué)家推測地球已經(jīng)誕生了46億年了，大約還能再存活50億年。以目前的技術(shù)，分解p和q的時間要比這長多了?，F(xiàn)在全球最快的超級計算機是美國的“頂點”（Summit），峰值速度是20億億次/秒（200PLOPS，即2×10^17），在p和q未知的情況下，用它來從n中分解出p和q大概需要52萬億年。
如果能夠破解RSA-4096，就可以干很多事情：比如全球銀行的錢都是你的了，政府可以用這項技術(shù)摧毀任何其他國家的金融體系......
n=0xcd07894d8d39ee11e150e840ce0634fe47d6f0202090c4b1fee94281f8c2166088beb6106a1df4643584f44aeda3e0c37882f008f98ad4a5c0a3a03bacf975509cc85a6a94554bd00bcd39650e898271593110f18b231051e3161400c8a0881d91f23a0c3bbd52247d80ad56d21543f6e601eb2a60515b6cb425a2a85efa7832bada6be256cdd444aeb8ed03d2833cd76dec6947a8254c89dd48d6cfb29c67ae222b5f684dfc174aafe34744fb5e562a240f276ade902f93d314bde97dd11a3e8b2b8312a7e69be6a6e09a4ed7ac33712ac2d52c0d120b8dc801d177ebca47d4945c760e6b523f8a21e23208a8b73babb382048176754cd4c7c19c24eeafdf4ef337bf61fc6aa180105071bef50deb25adfb36139e71faa885b0c0a9709af7bad9da5523dfe336b336884f72adb5379b7bf50165255babb4c11e1b86a5545ce637fb044c7cd6b820a442d18dbe526e22a121cbdaf4fb824ff041203ca61b0cb545fb531963167566f7e92bb1492342567e2c93e0003299f2a02a035f03f675c992361a19b471cbf93d7adc21c5d63c97cbac26b0ac746f521c1611b29393b30dabf9968bd5a8ac8e6c996f90bd907e2841c6531dffbd11f53551a09632f1c779c905101e3bb2fadc6403dca7bf5cc86dffa52548546e09dfe7eeb71ce02ee8090ea813dfeb4ed2c376025f204432a2e91581ff9209ea670d8007d0157ebe74f9
p=0xdf6f823ed432354aa21d2847947a7d01b2cf436ef17e7a91e49dcd6fd579c9706628477b1584cdc4a284b3cc960638d8c4352fc9efd826f6106d1d4feb75541adc84d0a2a7d59e7f43c6338488319ff5d7e90f5e26380e4253f0e94df51fe924bcacf4cf61729a52a757cc64faa334942cbf72fcef71fff105db5be1f9a3876467d2813529afae6a824f69243f9d5b880127ccc055cedb32d66cacb811027f9f228a9c99d06ecd533bcca752ded278c9ed34ff79ac2e67ba0a925d09aae38bfad7a10a81cc8335b1e8258640f3e620645c9abc37d6299464ab98daf8dc811c5b7898b2be6af53769b23306dc6be0e17d2d352d77fad11cb199fa67c71c207c5f
q=0xeae9490d7f7f3de71beb33c3c4d5ea51464e9a82747e5901040c2b08d9e6012acfd20abb0402f6eb06e0472c45091c7cfde6e7c9b024aad1cb4aea8327919c52e97250cac80ad3776c31f6f5ca2af8d9862f58fc3a7a5e442b2e441241f8e4a5a518c47ff9a2b923fb8b2e4be5793788618bdfc2a4117dc44811e6227b1be7e6d7ab8d250ee3f2d1ad69e929bfc3f8ee736ae85d716d70fb776f6888a64d6ee823fd9665eb2f85577c193316f4d4c4fd27932100e9783b6bfff76402f504a17858ae2e80cf0d2c953e7395adfb42490f4a61a060bf8dce3fb69c5af9baee89663d58e6de22fdac6982579c8f411f6586c7b8f4a9ddd2a10a4390c4d2ba138da7
當(dāng)然，如果黑客能偷偷把銀行的公鑰換成自己的公鑰，網(wǎng)銀轉(zhuǎn)賬就還是不安全。于是網(wǎng)絡(luò)安全人員提出了“證書”的概念，來證明哪個公鑰是銀行的，哪個不是，以此來防范黑客。
RSA算法還可以用來數(shù)字簽名，我們下次再聊。
參考：
[1]質(zhì)數(shù). https://zh.wikipedia.org/wiki/素數(shù)
[2]Prime Number. https://en.wikipedia.org/wiki/Prime_number
[3]RSA加密算法. https://zh.wikipedia.org/wiki/RSA加密演算法
[4]RSA(Cryptosystem)https://en.wikipedia.org/wiki/RSA_(cryptosystem)
[5]PKCS #1: RSA Cryptography Specifications Version 2.2. https://www.rfc-editor.org/rfc/pdfrfc/rfc8017.txt.pdf
[6]周期蟬.https://zh.wikipedia.org/wiki/周期蟬
[7]Periodical cicadas. https://en.wikipedia.org/wiki/Periodical_cicadas
[8]RSA Security. https://en.wikipedia.org/wiki/RSA_Security
徐紅偉@百香果科技
