異構(gòu)模型下彩虹表密碼分析算法的改進與實現(xiàn).pdf

1、密碼分析的問題可以通過窮搜索或查表法解決。但是它們分別需要需要大量的時間與存儲空間。進而，窮搜索與查表法存在比較大的局限。彩虹表密碼分析算法是時間與空間兩個維度上的一類折中算法。與前者相比，彩虹表的適用性更廣。
　　2003年，Oechslin提出了彩虹表算法，并使用它實現(xiàn)了對Win-dows XP登錄系統(tǒng)使用的LM算法的破解。但是，Oechslin沒有深入分析預(yù)計算所需要的時間。我們發(fā)現(xiàn)，在彩虹表的很多應(yīng)用中，預(yù)計算所需的時間仍

2、然在可接受的范圍之外。因此，本課題主要動機是減少預(yù)計算所需要的時間。近些年來，科學(xué)計算領(lǐng)域已經(jīng)開始大量采用基于中央處理器與圖形處理器的異構(gòu)模型。在所有異構(gòu)計算解決方案中，NVIDIA的統(tǒng)一計算架構(gòu)(CUDA)應(yīng)用最為廣泛。新架構(gòu)給我們帶來了新的機遇，與此同時也帶來了新的挑戰(zhàn)。
　　鑒于彩虹表算法的實際需求以及CUDA異構(gòu)模型能提供的強大計算能力，本課題基于CUDA異構(gòu)模型，改進與實現(xiàn)了彩虹表算法。具體而言，本文涉及的主要工作與創(chuàng)新

3、點如下：
　　一、研究彩虹表算法，并提出改進方案。本文分析了在線階段中，理論研究與工程實現(xiàn)之間的差異。基于此，提出了優(yōu)化參數(shù)選擇與改進表結(jié)構(gòu)的方法。優(yōu)化參數(shù)選擇側(cè)重在通用性。而改進表結(jié)構(gòu)側(cè)重在一類新的結(jié)構(gòu)。
　　二、研究CUDA編程模型，實現(xiàn)彩虹表算法。本文討論了CUDA編程的特性與優(yōu)化方法。首次全面考慮異構(gòu)模型的引進對彩虹表每一個階段的影響。與此同時，考慮到圖形處理器的特點，本文還討論了歸約函數(shù)的實現(xiàn)與線程參數(shù)的選擇。最后