[發明專利]基于大數據彩虹表的解密方法和裝置

在審

• 申請號: 201611147432.0
• 申請日: 2016-12-13
• 公開（公告）號: CN106712928A
• 公開（公告）日: 2017-05-24
• 發明（設計）人: 劉清蟬;李翔;黃衍璽;張建偉;楊明;趙永輝;楊昊
• 申請（專利權）人: 云南電網有限責任公司電力科學研究院
• 主分類號: H04L9/06
• 分類號: H04L9/06;H04L9/32
• 代理公司: 北京弘權知識產權代理事務所(普通合伙)11363
• 代理人: 逯長明,許偉群

技術領域

本發明涉及密碼逆向恢復技術領域，尤其涉及一種基于大數據彩虹表的解密方法和裝置。

背景技術

隨著互聯網的迅猛發展，網絡信息安全要求越來越高。為了保證安全，通常采用密碼加密和解密技術。互聯網中各種協議的加密技術和手段層出不窮，出現了諸如MD5、SHA1、LM、NTLMHASH和MD4等加密算法。對于各種加密算法實施之后獲得的密文，采用解密技術來破解密文得到明文。

目前，對于簡單的密碼和密碼系統，密碼破解可以采用暴力破解的方式。而對于較復雜的密碼和密碼系統，例如對于大于8位的密碼，暴力破解的計算量非常大。通常采用彩虹表進行破解。彩虹表是一個龐大的針對各種可能的數字、字母組合預先計算好的哈希(hash)值的集合，彩虹表技術就是建立一個源數據與加密數據之間對應的哈希表，這樣在獲得加密數據后通過比較、查詢或者一定的運算，可以快速定位源數據，從而通過彩虹表的構造和查找，能夠破解密碼獲得明文。

然而，彩虹表作為一種壓縮的哈希表，對于較長的密碼，彩虹表往往占用空間巨大，破解時間很長，在某些情況下，超出單機存儲范圍，或者即使在集群上能夠滿足存儲但是生成時間太長，無法滿足實際需要。另外，由于彩虹表文件很大，在查找破解的過程中，耗時很長效率很低。即使存在某些商用的彩虹表，往往只能破解9位以下的密碼，而且破解的準確率只有80％左右，破解時間長，難以滿足實際需要。

發明內容

為克服相關技術中存在的問題，本發明提供一種基于大數據彩虹表的解密方法和裝置，對于1-12位的數字字母組合的密碼，利用得到的加密結果密文，能夠通過利用多個GPU并行生成彩虹表中的哈希鏈，來大大提高彩虹表生成速度，并且對生成的彩虹表進行索引排序，大大縮短解密階段的彩虹表查找時間，從而大大縮短解密時間。

根據本發明實施例的第一方面，提供一種基于大數據彩虹表的解密方法，包括：將彩虹表任務分配給n個GPU計算節點，其中n為大于1的整數；每個GPU計算節點根據分配的彩虹表任務生成一個彩虹表；將生成的彩虹表中的哈希鏈的鏈尾節點進行索引分組，對分組內的鏈尾節點進行排序；在經索引分組和排序的彩虹表內，對待解密的密文先執行索引查找然后執行二分查找，以獲得相應的明文完成解密。

根據本發明的一個實施例，將彩虹表任務分配給n個GPU計算節點包括：根據明文的取值范圍、彩虹表的查找成功率來設置彩虹表任務的大小,彩虹表任務包括多個哈希鏈任務，每個哈希鏈任務要生成一個哈希鏈；將所述彩虹表任務按照哈希鏈任務的數量分配給n個GPU計算節點。

根據本發明的一個實施例，在哈希鏈任務的數量為m的情況下，m/n＝x+y，其中，x為m除以n得到的商，y為余數，m為大于1的整數、x為大于0的整數，y為整數，將所述彩虹表任務分配給n個GPU計算節點包括：先均為n個GPU計算節點中的每個GPU計算節點分配x個哈希鏈任務；然后將剩余的y個哈希鏈任務順序地再分配給n個GPU計算節點中的前y個GPU計算節點，為前y個GPU計算節點中的每個GPU計算節點分配一個哈希鏈任務。

根據本發明的一個實施例，將生成的彩虹表中的哈希鏈的鏈尾節點進行索引分組，對分組內的鏈尾節點進行排序包括：根據哈希鏈的鏈尾節點的二進制數值的大小范圍來對彩虹表進行索引分組；對每個分組內的哈希鏈的鏈尾節點按照二進制數值的大小順序進行排序。

根據本發明的一個實施例，待解密的密文通過LM、MD4、NTLSHASH、MD5或SHA1算法加密，與待解密的密文相對應的密碼為1-12位。

根據本發明實施例的第二方面，提供一種基于大數據彩虹表的解密裝置，包括：n個GPU計算節點，被分配彩虹表任務，每個GPU計算節點生成一個彩虹表，n為大于1的整數；彩虹表索引排序單元，用于對n個GPU計算節點生成的彩虹表中的哈希鏈的鏈尾節點進行索引分組，對分組內的鏈尾節點進行排序；查找單元，用于在經索引分組和排序的彩虹表內，對待解密的密文先執行索引查找然后執行二分查找，以獲得相應的明文完成解密。

根據本發明的一個實施例，基于大數據彩虹表的解密裝置還包括文件系統，用于向n個GPU計算節點分配彩虹表任務，存儲n個GPU計算節點生成的彩虹表。

根據本發明的一個實施例，文件系統包括：彩虹表生成日志記錄單元，用于為各個GPU計算節點設置彩虹表生成數據參數，寫入彩虹表生成標記，彩虹表生成標記用于指示彩虹表生成是否成功；日志檢查單元，用于檢查彩虹表生成標記，如果彩虹表生成標記指示彩虹表生成不成功，調用相應的GPU計算節點繼續生成彩虹表。