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