來(lái)源：arstechnica
編輯：肖琴
【新智元導(dǎo)讀】密碼學(xué)達(dá)到一個(gè)新的里程碑：研究人員解開(kāi)了有史以來(lái)人類(lèi)計(jì)算過(guò)的最長(zhǎng)的RSA密鑰，并對(duì)有史以來(lái)最大的整數(shù)離散對(duì)數(shù)進(jìn)行了匹配計(jì)算。而且這次的突破不是來(lái)自硬件性能的提升，而要?dú)w功于軟件和算法的改進(jìn)。不過(guò)請(qǐng)放心，對(duì)我們的密碼影響不大。現(xiàn)在戳右邊鏈接上 新智元小程序 了解更多！
研究人員已經(jīng)在密碼學(xué)上達(dá)到一個(gè)新的里程碑，他們解開(kāi)了有史以來(lái)計(jì)算過(guò)的最長(zhǎng)RSA密鑰，并對(duì)有史以來(lái)最大的整數(shù)離散對(duì)數(shù)進(jìn)行了匹配計(jì)算。
隨著計(jì)算機(jī)硬件性能的提升，這類(lèi)新紀(jì)錄常有出現(xiàn)。但本周公布的這些記錄更有意義，因?yàn)樗鼈兊膶?shí)現(xiàn)速度比單憑硬件改進(jìn)所能預(yù)期的要快得多，這要?dú)w功于所使用的軟件和算法的改進(jìn)。
許多公鑰加密算法都依賴于兩個(gè)素?cái)?shù)乘積的極大數(shù)。其他加密算法的安全性基于解決某些離散對(duì)數(shù)問(wèn)題的難度。如果密鑰足夠長(zhǎng)，則沒(méi)有已知的方法可以破解它們提供的加密。對(duì)大數(shù)的分解和離散對(duì)數(shù)的計(jì)算破壞了給定密鑰大小的加密保證，并迫使用戶增加它所使用的熵位的數(shù)量。
事實(shí)上， 如果這個(gè)大數(shù)可以被因數(shù)分解，就意味著私鑰被破解。不過(guò)，大整數(shù)的因數(shù)分解是一件非常困難的事情。目前，除了暴力破解，還沒(méi)有發(fā)現(xiàn)別的有效方法。
維基百科這樣寫(xiě)道："對(duì)極大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性。換言之，對(duì)一極大整數(shù)做因數(shù)分解愈困難，RSA算法愈可靠。假如有人找到一種快速因數(shù)分解的算法，那么RSA的可靠性就會(huì)極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒(méi)有任何可靠的攻擊RSA算法的方式。 只要密鑰長(zhǎng)度足夠長(zhǎng)，用RSA加密的信息實(shí)際上是不能被破解的。"
這次的新記錄包括RSA-240的分解。RSA-240密鑰有240個(gè)十進(jìn)制位，大小為 795 bits。同一組研究人員還計(jì)算了同樣大小的離散對(duì)數(shù)。
在此之前，人類(lèi)破解的最長(zhǎng)RSA密鑰是2010年解開(kāi)的RSA-768(盡管位數(shù)比RSA-240更小，有232個(gè)十進(jìn)制位和768個(gè)二進(jìn)制位)，以及2016年的768-bit素?cái)?shù)離散對(duì)數(shù)的計(jì)算。
有效長(zhǎng)度是 795 bits，相較于約10年前解出來(lái)的 RSA-768 (768 bits)更大
以Intel Xeon Gold 6130 cpu(運(yùn)行于2.1GHz)為參考，這兩個(gè)新記錄的計(jì)算時(shí)間加起來(lái)約為4,000 core-years。與先前的記錄一樣，這些記錄是使用一種稱(chēng)為“數(shù)域篩選”的復(fù)雜算法完成的，該算法可用于執(zhí)行整數(shù)分解和有限域離散對(duì)數(shù)。RSA分解的篩選和矩陣化以及離散對(duì)數(shù)問(wèn)題的計(jì)算所花費(fèi)的時(shí)間大致如下:
- RSA-240 sieving: 800 physical core-years
- RSA-240 matrix: 100 physical core-years
- DLP-240 sieving: 2400 physical core-years
- DLP-240 matrix: 700 physical core-years
所需時(shí)間減少25%，功勞不在摩爾定律
這是第一次將整數(shù)分解和離散對(duì)數(shù)的記錄一起打破。這也是第一次使用相同的硬件和軟件創(chuàng)造兩項(xiàng)記錄。但不僅如此。
當(dāng)新的記錄被創(chuàng)造出來(lái)時(shí)，摩爾定律(Moore’s Law)不可避免地發(fā)揮了重要作用。摩爾定律指的是，計(jì)算機(jī)芯片的晶體管數(shù)量每隔18個(gè)月就會(huì)翻一番。晶體管的增加反過(guò)來(lái)又提高了運(yùn)行它們的計(jì)算機(jī)的計(jì)算能力，使計(jì)算機(jī)的速度和性能隨著時(shí)間的推移而提高。
盡管摩爾定律最初是英特爾聯(lián)合創(chuàng)始人戈登?摩爾在1965年提出的，但它已被視為一種幾乎不可避免的自然力，就像物理學(xué)定律一樣。考慮到摩爾定律的無(wú)情推進(jìn)，如果這樣的破紀(jì)錄事件沒(méi)有定期發(fā)生，那就變成不尋常了。
然而，與以前的里程碑相比， 這次的里程碑更少地受到摩爾定律的驅(qū)動(dòng)，而更多地受到數(shù)域篩選軟件改進(jìn)的驅(qū)動(dòng)。為了證明效率的提高，研究人員在與2016年計(jì)算768位離散對(duì)數(shù)相同的硬件上運(yùn)行他們的軟件。他們發(fā)現(xiàn)，使用舊的硬件篩選795-bit大小的記錄所需的時(shí)間比使用相同的設(shè)備執(zhí)行768-bit DLP計(jì)算 所需的時(shí)間減少了25%。
性能改進(jìn)的另一個(gè)標(biāo)志是：使用與2016年相同的硬件，795-bit對(duì)數(shù)的計(jì)算速度比768-bit的快1.33倍。在密碼學(xué)領(lǐng)域被廣泛接受的估計(jì)表明，較大的對(duì)數(shù)的計(jì)算難度應(yīng)該比較小的對(duì)數(shù)難2.25倍。總的來(lái)說(shuō)，這表明性能比預(yù)期的提高了三倍(即2.25*1.33=3)。由于這兩個(gè)位大小的硬件是相同的，性能的提高并不是由于更快的計(jì)算機(jī)的可用性。
研究人員在聲明中寫(xiě)道：“速度提高可以歸因于針對(duì)這些計(jì)算而實(shí)施的各種算法改進(jìn)。”這些改進(jìn)的關(guān)鍵是對(duì)用于實(shí)現(xiàn)數(shù)域篩選的開(kāi)源軟件進(jìn)行了更新。該軟件稱(chēng)為CADO-NFS，由30萬(wàn)行用C和c++編寫(xiě)的代碼組成。
法國(guó)國(guó)家計(jì)算機(jī)科學(xué)與應(yīng)用數(shù)學(xué)研究所的高級(jí)研究員Emmanuel Thomé評(píng)價(jià)道，這些改進(jìn)包括：
我們致力于更好的并行化和內(nèi)存使用(但老實(shí)說(shuō)，我們的競(jìng)爭(zhēng)對(duì)手也做了)。
在計(jì)算的某些計(jì)算密集型部分，我們更系統(tǒng)地利用了漸近快速算法的優(yōu)勢(shì)。
這種解密有很大一部分需要“選擇參數(shù)”的藝術(shù)。“我們做得很好。一個(gè)重要部分是能夠測(cè)試許多不同的參數(shù)集，并使用我們開(kāi)發(fā)的精確仿真工具對(duì)它們進(jìn)行排序。”
我們致力于更好的并行化和內(nèi)存使用(但老實(shí)說(shuō)，我們的競(jìng)爭(zhēng)對(duì)手也做了)。
在計(jì)算的某些計(jì)算密集型部分，我們更系統(tǒng)地利用了漸近快速算法的優(yōu)勢(shì)。
這種解密有很大一部分需要“選擇參數(shù)”的藝術(shù)。“我們做得很好。一個(gè)重要部分是能夠測(cè)試許多不同的參數(shù)集，并使用我們開(kāi)發(fā)的精確仿真工具對(duì)它們進(jìn)行排序。”
團(tuán)隊(duì)中的其他研究人員包括法國(guó)國(guó)家教育部和里摩日大學(xué)的Fabrice Boudot、法國(guó)國(guó)家科學(xué)研究中心的Pierrick Gaudry，法國(guó)國(guó)家計(jì)算機(jī)科學(xué)和應(yīng)用數(shù)學(xué)研究所的Aurore Guillevic，賓夕法尼亞大學(xué)和加州大學(xué)圣地亞哥分校的Nadia Heninger，以及法國(guó)國(guó)家計(jì)算機(jī)科學(xué)和應(yīng)用數(shù)學(xué)研究所的 Paul Zimmermann。
由于人們對(duì)即將到來(lái)的量子計(jì)算機(jī)及其破解當(dāng)今公鑰加密的能力給予了極大的關(guān)注，研究人員一直忙于開(kāi)發(fā)能夠抵御此類(lèi)攻擊的新方案。
“與此同時(shí)，研究人員一直在改進(jìn)經(jīng)典算法，以解決因式分解和離散對(duì)數(shù)問(wèn)題，這與摩爾定律一起，可能導(dǎo)致研究人員使用可用的計(jì)算資源能分解的密鑰大小達(dá)到新的記錄，” Heninger表示，“對(duì)于從業(yè)人員來(lái)說(shuō)，我們的建議基本上是，希望他們已經(jīng)按照建議至少在幾年前 轉(zhuǎn)移到2048位的RSA、Diffie-Hellman或DSA密鑰，這將使他們免于任何這些改進(jìn)的影響。”
