黎曼猜想被證明，互聯網要裸奔 下
上回書咱們說到非對稱加密演算法的扛把子RSA。這裡就來翻一翻RSA瓤子里的東西。這樣各位看官可以了解為啥素數規律和RSA有直接的關聯。
--RSA的一些數論基礎--
1、 互質：如果兩個正整數，除了1以外，沒有其他公因子，我們就稱這兩個數是互質關係（coprime）。比如，15和32沒有公因子，所以它們是互質關係。這說明，不是質數也可以構成互質關係。（質數就是素數，還記得不？）
2、 歐拉函數φ(n)：任意給定正整數n，求出在小於等於n的正整數之中，有多少個與n構成互質關係？（比如，在1到8之中，有多少個數與8構成互質關係？）
3、 歐拉定理：a^(φ(m)) 同餘1(mod m) (a與m互質)，這個定理是後面RSA公鑰私鑰互為加解密的基礎，但解釋起來很燒腦，還有一堆推論，都是數學遊戲，這裡就不展開了。
--RSA的運算過程--
前面咱有嘮過對稱加密演算法和非對稱加密演算法的很大不同，就是對稱加密演算法對密鑰不講究，而非對稱加密演算法的密鑰講究的很。RSA作為一種典型的非對稱加密演算法，密鑰不是隨便找的，是要經過一系列燒腦的操作才能整出一對合格的密鑰（公鑰、私鑰），兩者之間有很強的關聯性，所以一旦從數學的角度掌握了素數規律，擁有公鑰很可能就可以用比以前窮舉法更低的成本推算出私鑰。為啥？首先看看RSA密鑰對的生成方法。
第一步，隨機選擇兩個不相等的質數p和q。
比如選擇61和53。（實際應用中，這兩個質數越大，就越難破解。）
第二步，計算p和q的乘積n。
如上：61和53相乘。n = 61×53 = 3233
第三步，計算n的歐拉函數φ(n)。
根據上面偷懶沒細說的一個推論，φ(n) = (p-1)(q-1)=60 x 52 = 3120
第四步，隨機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質。
咱們在1到3120之間，隨機選擇17吧（實際應用中，常常選擇65537，比較安全）
第五步，計算e對於φ(n)的模反元素d。
所謂"模反元素"就是指有一個整數d，可以使得e*d被φ(n)除的餘數為1。
數學表達是
e*d ≡ 1 (mod φ(n))
這個式子等價於
ed - 1 = kφ(n)
於是，找到模反元素d，實質上就是對下面這個二元一次方程求解。
ex + φ(n)y = 1
已知 e=17, φ(n)=3120，
17x + 3120y = 1
這個方程可以用"擴展歐幾里得演算法"求解，咱就不列具體過程了。總之，算出一組整數解為 (x,y)=(2753,-15)，即 d=2753。
第六步，將n和e封裝成公鑰，n和d封裝成私鑰。
在上面的例子中，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。對的，非對稱加密演算法的密鑰就是長這麼任性！在實際的例子中，公鑰大多是以X.509證書規定的數據結構來存放的：
--RSA演算法破解分析--
1、能破嗎？怎麼破？
分析一下，有沒有可能在已知RSA密鑰的n和e的情況下，推導出d呢？
所以結論是：如果n可以被因數分解，d就可以算出，也就意味著私鑰被破解。
可以看到，RSA演算法的密鑰對是非常關鍵的。由於公鑰是公開的，RSA破解的風險主要在於私鑰的安全性，而安全性又分存儲安全性（要藏好）和演算法安全性兩方面（要抗破解）。公鑰、私鑰之間如果n可以被很快的因數分解（每個n只有一種分解可能性），d就可以被很快算出來，也就意味著私鑰被破解了。所以RSA的演算法命門在於大數的因數分解。實際上大整數的因數分解是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。維基百科是這麼描述的：
舉例而言，你可以對3233進行因數分解（61×53），但是你沒法對下面這個整數進行因數分解:
它等於這樣兩個質數（素數）的乘積：
之所以舉這個例子，因為這大概是人類成功分解過的最大整數（232個十進位位，768個二進位位）。比它更大的因數分解，還沒有被報道過的案例。而目前主流的RSA密鑰長度是2048，被認為以當今世界上最先進的計算機也是無法在合理的時間內暴力破解的（以後量子計算機成熟後就說不好了）。
另外，大夥可能會覺得奇怪：這都講到密鑰了，怎麼不順著往下說RSA的加密、解密過程呢？其實RSA的加解密演算法比較直觀，本身是公開的。所以演算法層面沒什麼好保護的，加密演算法的保護主要在密鑰保護上面。
而密鑰的保護除了密鑰本身的傳遞、保存的保護之外，最重要的是防止破解。這就呼應到上面的黎曼猜想的證明了。之所以黎曼猜想被證實有這麼大的影響，最主要的也是因為證明的過程中可能會引發數學基礎的大地震，導致RSA的基礎：素數分布的規律被找到，這令大數（值很大的數）的因數分解變得比原來成本更低，從而使黑客獲取公鑰後比以前更快速的破解私鑰。
2、演算法破了怎麼用？
RSA演算法的長期廣泛使用導致整個信息產業對其依賴性特彆強。演算法如果可以被以能接受的成本破解（數學家叫多項式時間複雜性），那影響的範圍實在太廣了。黑客可以攻入銀行的安全系統，盜取以RSA保護的信息，篡改或製造簽名保護的信息… 舉個簡單的例子，一個SSL網站的數字證書（含公鑰）是公開可獲取的。黑客可以獲取數字證書後進行演算法破解，獲取私鑰。之後便用私鑰解密基於HTTPS通信的數據，如果這個網站涉及巨額交易，之後的事情就很可能很大條了…還有更危險的事情就是用非對稱加密演算法保護的數據，一旦被破解，這些業務系統恐怕就要裸奔了！
--黎曼猜想被證明導致的RSA密碼體系風險有多大--
其實從目前的情況看起來，我們還不能完全確認阿蒂亞對黎曼猜想的證明是完全嚴謹的，而且他展示的證明論文也非常龐雜，目前還處於同僚論證的階段。業內已經有多位磚家對老先生的論文表示質疑。先不說這位邁克爾·阿蒂亞爵士是否真正攻破了這個曠世難題（老人家年齡大了，最近已有過幾次失手，所以有人質疑他這次又在吹牛皮），假設成功的證明了黎曼猜想，則大概率能夠給素數分布提供很多啟示，甚至直接的規律，比方說我們可以用黎曼猜想來估計了素數定理的誤差項，估計相鄰素數之間的間隙等等，但是我們要知道RSA2048位的密鑰長度是2048個二進位位，換算成十進位的話密鑰是超過10的幾百次方的超級大數。有學者計算過，即便在素數有規律可循的情況下，暴力破解RSA2048位的成本依然是天文數字。
即使我們可以通過黎曼猜想來獲取到某個素數公式，我們也很難用它來快速破解RSA演算法。為了破解RSA2048演算法，我們需要的不是素數公式，我們需要分解質因數，而有了素數公式只能讓分解因數這個本身耗費巨量算力的事情變得成本低了一些。現在業界常用的RSA演算法的加密密鑰的大小是2048位，根據素數定理，這個大小範圍內素數大約佔了所有整數的幾千分之一。我們或許可以用給定區間內的所有素數來給破解RSA的演算法提速數以萬倍，但是本身成本仍然是天文數字（就好比成本從十億年降到一億年沒啥區別）。如果有一天這個破解成本結合計算機運算速度的提升變得可以接受，卻很容易就被RSA密鑰長度的翻倍（提高到4096位）搞定，因為當從密鑰長度2048增加到從4096位，暴力破解的碰撞成本會被提高數百億倍。
--多說幾句--
是不是有種看了場100分鐘的球賽0比0的感覺？！當然，話又說回來，RSA演算法樹大招風。有多少黑客、學者、各路英雄都盯著RSA。無論是誰，只要能以可以接受的成本攻破RSA，即可在世界範圍內揚名立萬。當年山東大學王小雲教授通過碰撞法攻破了SHA1和MD5演算法就受到了廣泛的關注，更何況是RSA呢！從另一個角度說，萬一真的RSA演算法被攻破，曾經簽署過的電子合同也存在被篡改的可能性，現存的數字證書也不再安全。
從這個角度說，我們電子簽名的從業者應該高度關注相關的新聞，密切注意業內的動態，並隨時做好升級密鑰、切換演算法的準備。同時，也應在某些特定的場合中應積極的推薦客戶採用基於橢圓曲線演算法的國密系列演算法來替代RSA，以規避潛在的演算法破解風險。
重點來了！e簽寶作為從業十六年的行業鼻祖，一路見證電子簽名行業的演進和技術發展。無論是對於國際主流技術或者國密技術都有著最敏銳的嗅覺和判斷，e簽寶是目前唯一一家支持國產SM系列加密演算法的互聯網電子簽名平台，同時可以將SM2系列演算法植入到PDF和OFD兩種版式文件格式中，以支持政府、金融領域對自主可控的安全要求，是浙江省「最多跑一次」指定唯一的電子簽合同供應商。正是基於持續的技術投入和前沿跟蹤，我們才能一直以最安全可靠的技術體系來保障客戶的信任體系。一句話：簽合同，用e簽寶！
推薦閱讀：
TAG:自然科學 | 黎曼猜想RiemannHypothesis | 互聯網 |