數學中的質數只能被1和自身整除,而且有無窮個。這個已經被歐幾裡德證明過了,除此之外,謎一樣的質數也是網絡安全方面重要的一個角色。
目前正在進行中的網際網路梅森素數大搜索(GIMPS)項目就是為了發現更多的質數,已知最大的質數具有23249425個位數,要寫完這個質數需要9000頁張紙,而目前已知的原子數量不會超過100個位數。
這個由一個志願者花了14年的時間計算後得出的質數寫作2-1。有人會提出疑問,需要知道這麼大位數的質數嗎?知道這些質數有什麼用?
質數在網絡安全領域的應用之一就是RSA加密。
1978年Ron Rivest,Adi Shamir,Leonard Adleman三人創建的RSA加密,其中就利用了質數的組合。現在的加密網絡傳輸協議中應用到了RSA加密原理。在這個原理中需要使用2個質數,質數越大加密越安全。
以數字70來舉例,可以分解為2個35,35分解為5×7,因此70可以看作由2、5、7這幾個數字構成,而這幾個數字都是不可再進行分解,因此將這個過程稱為70的質因數分解。
通常兩數相乘比較簡單,而要對一個數進行質因數分解卻非常困難,這也是RSA加密為什麼需要利用質數的原理。
假設Alice和Bob兩人,在網上希望進行加密通信,這就需要使用加密系統。
如果兩人第一次見面可以商定一個只有他們才知道的加密解密系統,而在網上卻做不到這點,兩人一開始必須通過不加密的網絡連接後才能加載加密系統,這個過程非常危險。
這時就用到RSA算法。下面用通俗一點的行文簡單介紹一下它的原理:
Alice的兒子想和Bob的女兒處朋友,Alice就公開在網上問了Bob一句:「你女兒多少斤?」
為了得到這個答案,Alice首先選擇2個大的質數得到一個乘積N(公鑰,可以在網絡上公開傳播,第三方也可以截獲),將「100」加密後發送給Bob;
Bob接收到數據後,他也不知道Alice的原信息是什麼(因為Bob雖然知道公鑰N,但他沒有產生N的2個大質數,所以解不開Alice給他發的信息),所以他就不理了,直接把他女兒的真實體重「180」混合在Alice的原信息中,用之前的公鑰N加密之後發回給Alice。
這樣折騰一圈有什麼好處呢?好處就是即使有第三方截獲了信息,而且還知道了公鑰N,例如Eve,他兒子也想和Bob的女兒處朋友,也想知道Bob的女兒有多重,就偷聽了他們倆的對話。
這時候Eve截獲的信息用公鑰N解密之後發現是「280」,這時候估計就放棄了。
如果Eve聰明一點的話可能會猜測到Alice往裡面「摻水」了,但他也沒辦法啊,他破譯不了Alice的原始信息,不知道摻了多少水。
現在Alice接收到Bob發回的混合信息「280」,再減去之前自己放的「100」,就知道Bob他女兒有多重了。
(以上只是做個簡單的類比,真實的細節會更複雜,大家有興趣可以去了解一下)
隨著技術的發展,電腦的運行速度越來越快,因此簡單的質數已經不能滿足加密的需求,所以需要不停尋找更大的質數。
目前找到的最大質數由於位數太多,無法用於現實生活中的加密,而且量子計算機的出現可能會打破這種定律。
當然數學家最初並不是為了加密才去尋找最大質數,而是為了尋求探索過程中不斷發現新寶藏的那種感覺。
更多時候數學家並不關心找到的質數是不是有用或是不是最大質數,而是為了滿足人類的求知慾。
更多有趣的科技文章,歡迎關注我們:http://www.wttech.org/