技術領域

本發明涉及的是一種計算機安全領域的加密系統及方法，具體是一種基于生成元擴展彩虹表的密碼恢復系統及其恢復方法。

背景技術

彩虹表是密碼學領域一種重要的方法和工具，最初由Hellman在《一種基于時間空間折中算法的密碼分析方法》（A?cryptanalytic?time-memory?trade?off）一文中提出，它的核心思想是空間與時間的折中，通過預計算的方式來減少口令恢復的時間花銷。本質上，彩虹表的生成需要窮舉遍歷整個明文空間，生成的時間是和彩虹鏈的長度、條數有關，恢復成功率是和明文空間以及彩虹表的大小規模有關的。也就是說對于固定的明文空間，想要生成一張恢復成功率較高的彩虹表，幾乎需要遍歷所有的明文空間，其時間上的代價是和窮舉口令恢復相近的，但是一旦生成這張彩虹表，以后只需要以較少的時間就可以判斷哈希值對應的明文在不在這張表中。

彩虹表是在時間空間折中方法基礎上進行改進而產生的一種技術，其核心思想是將明文計算得到的哈希值由一個R函數映射回明文空間，從而可以交替地計算明文和哈希值：R(HASH)=PLAIN。R函數是彩虹表設計的關鍵，需要滿足以下兩個特點：隨機性，從哈希值計算到空間中的每個明文的概率相同；計算速度快，因為在計算一張彩虹表的過程中，R函數和哈希函數被調用的次數大致相同，需要能夠快速得到結果的R函數。經典彩虹表利用哈希值的前8字節的內容加上當前在彩虹鏈中的位置，對總空間取模來計算明文對應的Index數值，然后將空間中某個Index轉換到具體對應的明文。

雖然使用彩虹表能夠獲得在線恢復口令階段比窮舉口令恢復高得多的時間效率，但是目前生成長密碼（10位以上）的彩虹表在時間上仍然是不能承受的，某部門對哈希口令恢復的實踐表明，超過10位的口令無論使用何種方法恢復成功率均低于10%。因此一種有效的長口令恢復方案無論在理論還是實踐中都是非常具有價值的。

事實上，對于長密碼的完整明文空間（95^N，N為密碼長度），有很大一部分的口令的利用率相當的低。大部分口令庫中的口令都是人為設定的，因此必然是相對便于記憶的。如果能夠優先考慮那些利用率高的有意義的口令，將會有效地減小明文空間，雖然不能提高按照經典算法計算的恢復成功率，但是對現實口令庫的來說，恢復成功率將是可觀的。

目前，增加計算速度是比較熱門的研究方向，分布式（云計算）和GPGPU都屬于這個范疇，但由于硬件限制，速度提高必有上限。

經過對現有技術的檢索發現，仇李寅在《基于Hadoop的擴展彩虹表生成研究》（上海交通大學2011年碩士論文）中提出了一種改進的彩虹表技術，該文獻中以Hadoop作為云計算的基礎架構，使用Map?Reduce框架來進行彩虹表的生成和破解。但是該現有技術的缺陷在于：對于擴表的生成元沒有形成有效的方法，本發明主要是基于數據挖掘的方法對于真實口令庫進行生成元的挖掘和制定。另外，以Hadoop為基礎的基于云計算的擴表的生成和使用由于環境限制，生成和使用都有較大的局限，不利于擴表在實際環境中的應用。

發明內容

本發明針對現有技術存在的上述不足，提出一種基于生成元擴展彩虹表的密碼恢復系統及其恢復方法，以減小明文空間的方法來達到在可接受時間范圍內生成長口令彩虹表的目的，其意義在于為恢復人為設置的長口令提供一種在切實可行的方案。本發明通過使用彩虹表中時間空間折中的思想對這些字典的存儲方式進行改進，產生出基于生成元的彩虹表，能夠大大降低人為口令的恢復時間。

本發明是通過以下技術方案實現：

本發明涉及一種基于生成元擴展彩虹表的密碼恢復系統，包括：包含擴展彩虹表生成模塊、擴展彩虹表口令恢復模塊的若干客戶端，即網絡節點，以及與若干網絡節點相連接的包含數據挖掘模塊、存儲器以及系統初始化模塊的服務器，其中：用戶通過管理終端網站管理服務器的數據挖掘模塊和系統初始化模塊的工作，服務器中的數據挖掘模塊生成生成元字典，服務器中的系統初始化模塊生成包含生成元字典信息的分布式初始化配置文件，服務器中的系統初始化模塊與網絡節點中的擴展彩虹表生成模塊和擴展彩虹表口令恢復模塊相連接并傳輸系統初始化配置信息。