一種基于分段式字符集的彩虹表明文生成方式?

張琛嶺

(上海交通大學電子信息與電氣工程學院，上海200240)

一種基于分段式字符集的彩虹表明文生成方式?

張琛嶺

(上海交通大學電子信息與電氣工程學院，上海200240)

Oechslin提出的彩虹表應用時間空間折中思想,是密碼學中逆轉單向函數的有效工具,但現在廣泛使用的單一字符集彩虹表,在明文位數較大時,因明文空間的迅速膨脹,消耗計算資源的迅速增加,其應用遇到了瓶頸。為此,針對人為口令字符集構成特點,提出分段式字符集彩虹表明文生成方式,將取自不同字符集的不同位數明文拼接組成新的明文,可以有效地壓縮明文空間,增加覆蓋的最大明文位數。對取自CSDN的1000個真實口令哈希進行實驗,結果表明,在原始彩虹表的基礎上,使用分段式字符集彩虹表使恢復成功率提升39.1%。

單向函數;時間空間折中;彩虹表;真實口令;分段式字符集;哈希恢復成功率

0 引言

單向函數的逆轉問題是密碼學中一個重要的研究方向,當所針對的明文空間較大時,單純的時間暴力破解或查表破解往往無法滿足要求。1980年Hellman首次提出時間空間折中算法(TMTO)[1],以部分存儲空間為代價,縮減在線破解時間,并將其應用于DES的破解。之后Rivest提出可區分點算法(DP)[2],仍以時間空間折中思想為基礎,對Hellman的算法進行了一些改動,使得所需查表次數明顯減少。彩虹表算法是Oechslin于2003年提出的基于時間空間折中思想的算法[3],它的預計算表在結構上與前兩種算法均不相同,表的數量很少,但每張表中使用了多個R函數,且鏈長保持一致?！?br>