劉迎風(fēng)，劉勝利

(1.上海市大數(shù)據(jù)中心，上海 200072；2.密碼科學(xué)技術(shù)國家重點實驗室，北京市5159信箱，100878 3． 上海交通大學(xué) 計算機科學(xué)與工程系，上海 200240 4.成都衛(wèi)士通信息產(chǎn)業(yè)股份有限公司 摩石實驗室，北京 100070)

基于口令認(rèn)證系統(tǒng)[1-2]一般都使用用戶名和口令對用戶進(jìn)行鑒別，這也是目前最廣泛的身份認(rèn)證方式。各大網(wǎng)站、銀行系統(tǒng)、郵件系統(tǒng)、電腦登錄等都使用了這種方法。目前基于口令的認(rèn)證系統(tǒng)大都使用以下兩種方法。第一種方法是認(rèn)證服務(wù)器將“(用戶名，口令)”存入數(shù)據(jù)庫。認(rèn)證時，用戶從客戶端輸入自己的用戶名和口令，用戶名和口令經(jīng)網(wǎng)絡(luò)傳輸后，服務(wù)器對數(shù)據(jù)庫尋找“(用戶名，口令)”進(jìn)行匹配。如果匹配成功，則認(rèn)證通過；否則，認(rèn)證失敗。這種方法將各個用戶的口令以明文方式存儲在數(shù)據(jù)庫中，大大增加了口令被竊的風(fēng)險。例如，黑客入侵網(wǎng)站并獲取網(wǎng)站數(shù)據(jù)庫中的數(shù)據(jù)，或者內(nèi)部管理人員竊取網(wǎng)站數(shù)據(jù)庫的數(shù)據(jù)，就可以從數(shù)據(jù)庫中直接獲得口令。目前已有來自RockYou、MySpace、CSDN、天涯、DuDuNiu等共兩百多個網(wǎng)站的用戶和口令信息在網(wǎng)上被傳播和販賣。第二種方法則是對用戶口令的哈希加鹽，也就是口令后面加一段隨機值(salt)，然后進(jìn)行哈希運算，得到加鹽哈希值。認(rèn)證服務(wù)器將“(用戶名，鹽，加鹽Hash值)”存入數(shù)據(jù)庫。認(rèn)證時，只需計算用戶口令的加鹽哈希值，并判斷與庫中的值是否一致即可。

口令的優(yōu)缺點相輔相成。其優(yōu)點是：容易記憶；缺點是：作為隨機變量，其概率分布不均，故熵值不高。WANG等人[3-4]對中國網(wǎng)站用戶所調(diào)的口令的特點進(jìn)行了分析，發(fā)現(xiàn)用戶更喜歡使用人名、生日及與自己相關(guān)的一些信息作為口令。雖然目前已經(jīng)存在并實現(xiàn)了比較好的基于口令的認(rèn)證手段，但是，口令因其自身“易記低熵”的特性，很難將其用于加密等更復(fù)雜的密碼系統(tǒng)中。正是因為這個特點，目前關(guān)于口令的更多應(yīng)用是將口令作為一個因子進(jìn)行雙因子或者多因子認(rèn)證[2，5-6]。

目前，我國已經(jīng)制定了中國的國密標(biāo)準(zhǔn)算法系列(如SM1、SM2、SM3、SM4、SM7、SM9、ZUC算法)。這些密碼算法絕大多數(shù)都需要密鑰的參與。有了密鑰，密碼算法就可以實現(xiàn)豐富的密碼功能，保障信息安全。而密碼算法實現(xiàn)安全的必要條件是：密鑰均勻隨機。

口令“易記低熵”，可以做認(rèn)證，但是不能實現(xiàn)加密等其它的密碼功能。而密碼算法雖然可以提供豐富的密碼功能，卻需要一個均勻隨機的密鑰做支撐。一個自然的想法是：“能否將口令結(jié)合到密碼系統(tǒng)中去？”

口令是個人主觀設(shè)定并記憶的，隨機性不高，不符合密鑰的要求。顯然，不能直接將口令用作密鑰。如果能夠?qū)⒖诹钷D(zhuǎn)換成密鑰，那么就可以使用口令來調(diào)用密碼算法了。問題是：“如何將口令轉(zhuǎn)換成均勻隨機的密鑰呢？”

文中的研究目的是回答上述兩個問題，提出將口令轉(zhuǎn)換成均勻隨機的密鑰的技術(shù)，將口令結(jié)合到密碼系統(tǒng)中去，進(jìn)而實現(xiàn)更加靈活豐富的密碼功能。

1 基本概念及基礎(chǔ)知識

統(tǒng)計距離是一種用來衡量兩個隨機變量的概率分布的相似性的標(biāo)尺，兩個隨機變量的統(tǒng)計距離越小，這兩個隨機變量的概率分布就越相近。下面是統(tǒng)計距離的正式定義。

定義2【最小熵】對于集合X上的隨機變量X，定義H為X的最小熵，熵的單位是bit。

定義3【通用哈希(Universal Hash)函數(shù)】[7]設(shè)H： X→Y是一個函數(shù)族。如果對于所有的x≠x′∈X，Pr[H←H：H(x)=H(x′)]≤ 1/|Y|，那么H是一個通用哈希(Universal Hash)函數(shù)族。

定義4【Toeplitz矩陣】[8]如果矩陣(可以不是方陣)中每條自左上至右下的45°斜線上的元素都相同，那么稱這個矩陣為Toeplitz矩陣。

引理1【剩余哈希引理(Leftover Hash Lemma)】[9]H={H：X→Y }是一個通用哈希(Universal Hash)函數(shù)族。對于集合X上的隨機變量X，只要滿足H(X)≥k，都有

(1)

其中，H為H中均勻隨機選取的哈希函數(shù)，Uy為集合Y上的均勻分布。

2 基于口令的密鑰提取方案

首先對大量的口令進(jìn)行統(tǒng)計分析，探詢其統(tǒng)計規(guī)律。針對其統(tǒng)計特性，提出基于口令的密鑰提取方案。在基于口令的密鑰提取方案中，首先利用口令的統(tǒng)計特性估計“口令的熵值”，再根據(jù)熵值選擇“Toeplitz矩陣”。使用Toeplitz矩陣對口令進(jìn)行壓縮以提取密鑰。所提取的密鑰可以應(yīng)用于不同的密碼系統(tǒng)中以實現(xiàn)認(rèn)證或者加密。最后，建議通過“標(biāo)準(zhǔn)的密鑰擴展函數(shù)”，對密鑰進(jìn)行擴展，這樣就可以從一個口令推得多個密鑰，應(yīng)用于多個不同的密鑰系統(tǒng)中。下面將分三小節(jié)描述：2.1節(jié)中介紹如何對口令庫進(jìn)行統(tǒng)計分析；2.2節(jié)中介紹提出的基于口令的密鑰提取方案，將詳細(xì)描述方案的各個模塊，以及各個模塊之間的聯(lián)系；2.3節(jié)中解釋密鑰提取的原理。

2.1 口令庫的統(tǒng)計分析

從網(wǎng)絡(luò)上收集到了DuDuNiu網(wǎng)站的公開口令庫，從中選取 200 000 條口令進(jìn)行簡單的分析。圖1為 200 000 條口令中使用頻率最高的14個口令。從圖1中可以看出，用戶使用最多的口令多為字母、數(shù)字的簡單組合，如口令q123456出現(xiàn)了 1 890 次、口令a123456出現(xiàn)了988次、口令123456出現(xiàn)了978次。這種簡單的口令固然降低了用戶的記憶難度，但是其概率分布極不均勻。另一方面，一個均勻隨機的口令看上去往往是無意義的、很難以被記憶的，用戶很難直接對一個均勻隨機的密鑰進(jìn)行記憶。

圖1 DuDuNiu網(wǎng)站最常用口令分布

希望能夠找到一種方法：可以從口令中獲取均勻隨機的密鑰，這樣既避免了增加用戶的記憶負(fù)擔(dān)，又可以使用所獲得的密鑰實現(xiàn)密碼功能。

2.2 基于口令的密鑰提取方案

設(shè)計了一個基于口令的密鑰提取方案(Password-Based Key Generation Scheme，PBKGS)。在PBKGS方案中，首先對口令進(jìn)行二進(jìn)制轉(zhuǎn)換，得到一個n維二進(jìn)制向量；之后測定口令庫的熵值，并根據(jù)熵值確定下一步密鑰提取矩陣的行的維數(shù)k；接下來確定密鑰提取矩陣，先選取一個均勻隨機的n維二進(jìn)制向量，隨后對該向量進(jìn)行循環(huán)移位編碼得到n×n維Toeplitz方陣，并根據(jù)上一步得到的矩陣行數(shù)k(k

將從口令中提取密鑰的機制抽象為四步驟：口令的二進(jìn)制轉(zhuǎn)換、熵的測定與矩陣維數(shù)的確定、向量-矩陣編碼以及密鑰提取。下面將具體解釋每一步的做法。

圖2 基于口令的密鑰生成方案(PBKGS)

2.2.1 口令的二進(jìn)制轉(zhuǎn)換

口令的二進(jìn)制轉(zhuǎn)換指的是將口令p由ASCII碼[10]轉(zhuǎn)換為二進(jìn)制比特串。具體地說，假設(shè)口令p=(w1，w2，…，wt)包括t個ASCII碼，其中wi均是ASCII碼。由于ASCII碼的取值范圍為0～127，且127=27-1，因而可以將每一位ASCII碼用一個7位長的二進(jìn)制串來表示，即wi：=(i1，i2，…，i7)。最后，將每一位ASCII碼的二進(jìn)制展開并連接起來，就得到了口令p的二進(jìn)制表示向量X=(x0，x1，…，x7t-1)。令n=7t。

2.2.2 熵的測定&矩陣維數(shù)的確定

在信息論中，熵是一種用來衡量隨機變量的分布隨機性大小的量度。一個隨機變量的熵越大，這個變量的隨機性就越強，越符合我們所說的“均勻隨機”。在算法中，一個口令的熵值決定了最后能夠提取的字符串的長度。所以檢測一個口令庫的熵是必不可少的一步。

熵的定義有很多種，香農(nóng)(Shannon)熵、雷尼(Renyi)熵、最小(Minimal)熵，等等。在此，采用最小熵的定義來衡量口令庫的熵(關(guān)于為什么采用最小熵，將會在2.3節(jié)中給出回答)。

假設(shè)經(jīng)過計算，長度為nbit的字符串的熵為k，那么給定一個整數(shù)0

圖3 熵的測定&矩陣維數(shù)的確定

2.2.3 向量-矩陣編碼

由2.2.2節(jié)，在知道了提取矩陣A的維數(shù)k和n的值之后，先選取一個均勻隨機的n維二進(jìn)制列向量a=(a0，a1，…，an-1)T，然后將a作為一個n×n矩陣的第1列a(1)，隨后將列向量a的所有分量的位置循環(huán)后移一位，也就是說，此時a(2)=(an-1，a0，…，an-2)T，將a(2)作為這個n×n矩陣的第2列。并按照這種循環(huán)后移的方法，填充好后面的所有列。具體地說，這個n×n矩陣的第i列(1≤i≤n)填充的是列向量a(i)=(an-(i-1)，an-(i-2)，…，an-i)T。在填充好所有的列后，就得到了由列向量a生成的n×n維Toeplitz方陣。對Toeplitz方陣進(jìn)行截斷，保留方陣的前k行，得到k×n維Toeplitz矩陣A。具體見圖4。

圖4 Toeplitz矩陣生成示意圖

2.3 密鑰提取及原理

在2.2.3節(jié)得到的k×n維的二進(jìn)制矩陣A，在2.2.1節(jié)從口令中導(dǎo)出了n維二進(jìn)制列向量X=(x0，x1，…，xn-1)T。由于矩陣A=(aij)與向量X都是二進(jìn)制向量，可以通過矩陣乘法運算得到所提取的字符串(列向量)K=(K0，K2，…，Kk-1)T，其計算方式如下：

K=AX，

(2)

定理1在基于口令的密鑰提取方案(PBKGS方案)中，若口令p的熵為H(p)=m，則所提取的字符串幾乎均勻分布。若Uk代表{0，1}k上的均勻分布，則K的分布與Uk均勻分布的統(tǒng)計距離滿足

Δ((a，K)，(a，Uk))≤2-(m-k)/2。

(3)

證明在方案的向量-矩陣編碼步驟中，首先選取了一個均勻隨機的n維列向量a=(a0，a1，…，an-1)T，然后按照一個特定循環(huán)移位的編碼方式，得到了一個n×n的矩陣A。從編碼方式可以直觀地看出，得到的n×n維的矩陣中每條與主對角線平行的所有斜線上的元素都是一樣的，故編碼得到的n×n維的矩陣是Toeplitz矩陣。隨后將其截短，取其前k行，得到了一個k×n維的矩陣A，由于截短操作并不會對矩陣中元素的值進(jìn)行改變，所以在截短后的矩陣A中，和原來未截短時n×n維的矩陣相比，截短后矩陣的自左上至右下的斜線上的元素仍然是一樣的，也就是說，矩陣A同樣也是Toeplitz矩陣。

由這個例子可以看出，熵?fù)p和提取出字符串與均勻分布之間的誤差是息息相關(guān)的。犧牲的熵越多，那么提取出的字符串越均勻，但提取出的字符串越短。在實際應(yīng)用中，可以根據(jù)實際情況來靈活地調(diào)整PBKGS方案的參數(shù)，如果要用的密碼算法對密鑰均勻性要求較高，就可以選擇熵?fù)p大一些來獲得更貼近均勻分布的字符串。否則，就將熵?fù)p定的小一些，提取更長的字符串。

3 結(jié)果測試與分析

使用了公開口令庫DuDuNiu中的200 000條口令作為測試數(shù)據(jù)。為便于提取熵，選擇其中長度超過10個ASCII碼的口令串，并將其截取為10個ASCII碼的截短口令，其中，每個ASCII碼可以表示包括字母、數(shù)字、特殊符號在內(nèi)共128種不同的符號。

由于測試使用的口令數(shù)目有限：10個ASCII碼理論上可以表示12810種(約1021種)不同的口令，而最終得到的實驗數(shù)據(jù)僅有 54 685 條，因此直接進(jìn)行最小熵的統(tǒng)計會導(dǎo)致結(jié)果不準(zhǔn)確，比如某個使用頻率很高的口令并沒有出現(xiàn)在測試集中；或者某個使用頻率很低的口令在測試集中出現(xiàn)的次數(shù)卻很多。為保證實驗數(shù)據(jù)相對于口令組合數(shù)來說是充足的，選擇將10個ASCII碼的口令分為5段，每段包含2個ASCII碼，這樣每段能夠表示的口令可能性僅為1282種(16 384 種)。這樣，實驗數(shù)據(jù)理論上是可以覆蓋所有的1282種可能的，在這種情況下計算出的最小熵是比較可信的。

表1給出了分段檢測最小熵的結(jié)果，從表中數(shù)據(jù)可以看出，每一段口令長度為14 bit(每個ASCII碼可以用7 bit來表示，每一段有兩個ASCII碼)，而最小熵僅為在2.9 bit至5.8 bit之間。這說明原口令串的隨機性較差。將所有段的最小熵累加起來得出了完整口令最小熵的一個上界值，約為23.002 bit。在不考慮剩余哈希定理的熵?fù)p失的情況下，理論上最多可以從10個ASCII碼長(70 bit長)的口令中提取23 bit均勻的字符串。

表1 口令各段統(tǒng)計的最小熵(每段兩個ASCII碼)

選擇口令第三段，即第5、6個ASCII碼(14 bit，最小熵5.783)進(jìn)行了密鑰提取實驗，表2和圖5為使用Toeplitz矩陣提取5 bit、4 bit、3 bit后熵值的對比?？梢钥闯?，在經(jīng)過哈希函數(shù)壓縮后，實際最小熵非常接近理論最小熵的最大值，說明從不太均勻的口令中提取出來的比特串非常接近均勻隨機串。

表2 口令第3段的最小熵理論最大值與實際熵值的對比

圖5 口令第3段的最小熵理論最大值與實際熵值的對比

圖5給出了第三段口令以及第三段口令經(jīng)過剩余哈希定理提取為5 bit、4 bit、3 bit長二進(jìn)制串后均勻隨機性的對比。由于原口令集數(shù)目過多，圖中只給出了部分對比數(shù)據(jù)。圖6中，橫坐標(biāo)i表示每個測試集合中按照出現(xiàn)次數(shù)由多到少排序的第i位口令，縱坐標(biāo)表示口令出現(xiàn)次數(shù)的標(biāo)準(zhǔn)化值Norm，用Ni代表排在第i位的口令出現(xiàn)的次數(shù)，Norm值根據(jù)以下公式計算：Norm=Ni/N1。

可以很明顯地看出，在進(jìn)行提取之前(圖6中細(xì)實線)，口令值出現(xiàn)次數(shù)變化波動很大，而在提取為5 bit(圖中短虛線)、4 bit(圖中粗線)、3 bit(圖中長虛線)后，曲線變化波動很小，非常接近理想情況，即數(shù)據(jù)集合中所有取值可能出現(xiàn)的次數(shù)幾乎是一樣的。

圖6 對口令第三段進(jìn)行壓縮提取前后的均勻隨機性對比

通過仿真實驗可知，當(dāng)選取兩個ASCII碼進(jìn)行實驗時，原始的口令的均勻隨機性較差，而Teoplitz矩陣壓縮后，可明顯看出實際熵值已經(jīng)非常接近理論上的最大熵值。也就是說，經(jīng)過提取后的字符串的均勻隨機性已經(jīng)大大提高。

由上述結(jié)果，知道兩個ASCII碼長的口令段經(jīng)過Teoplitz矩陣所確定的Universal Hash Function進(jìn)行提取后所得到的二進(jìn)制串具有很好的均勻隨機性。

4 結(jié)論和建議

口令在日常生活中隨處可見，用處極廣。而隨著祖國科技實力的強大，中國有了自己制定的標(biāo)準(zhǔn)密碼算法，這些算法都可以用來保證個人信息的安全性。但現(xiàn)有的密碼算法要求使用的密鑰是一個均勻隨機的字符串，顯然口令并不均勻隨機。為了解決這個問題，設(shè)計了一種可以從口令中提取均勻隨機字符串的方法。并在公開口令庫DuDuNiu上進(jìn)行了測試。實驗結(jié)果表明，筆者提出的方法可以有效地提取出口令的熵，得到幾乎均勻隨機的字符串。文中所提供的密鑰提取方法有以下4個特點。

(1) 根據(jù)剩余哈希定理，利用Toeplitz矩陣作為Universal Hash Function(通用哈希函數(shù))從口令中提取均勻隨機的字符串作為密鑰。

(2) Toeplitz矩陣的表示簡潔，只需要一個二進(jìn)制向量。Toeplitz矩陣作為一種Universal Hash Function，它的表示簡潔，只需要一個二進(jìn)制向量。作為二進(jìn)制矩陣，Toeplitz矩陣的乘法和加法分別是“與”和“異或”運算，運算非?？?。此外，Toeplitz矩陣的結(jié)構(gòu)可以在進(jìn)行矩陣乘法運算時，通過并行計算提高運算效率，因此進(jìn)行密鑰提取時算法效率很高。

(3) 密鑰不需要存儲，需要時可以隨時由口令值進(jìn)行恢復(fù)，而恢復(fù)口令所需要的信息矩陣信息可以公開，且公開信息矩陣不會影響密鑰的均勻隨機特性。

(4) 所產(chǎn)生的均勻隨機的字符串既可以作為認(rèn)證密鑰，又可以作為加密密鑰，擴展了口令的密碼功能。

對以上的研究結(jié)果進(jìn)行如下分析，并給出相應(yīng)的建議：

(1) 因為所提取的均勻隨機字符串較短，故建議增加口令的長度可以提取更長的均勻隨機串。研究結(jié)果顯示，最多可以從10個ASCII碼長的口令中提取出13 bit的均勻隨機串，均勻隨機串長度約為原口令長度的18.6%，長度較短。根據(jù)分析，導(dǎo)致提取出的均勻隨機串長度短的原因主要有兩個方面：一是口令的長度短、熵值低，根據(jù)分段估熵的結(jié)果，完整口令的最小熵不超過23 bit，因此本身能從口令中提取的隨機比特就很少；二是根據(jù)剩余哈希定理，為保證壓縮后的二進(jìn)制串盡可能接近均勻隨機串，還需要額外犧牲掉一部分熵值。因此，建議增加口令的長度可以提取更長的均勻隨機串。一方面，增加口令長度可以使得口令的原始熵值增加。簡單的實驗表明，當(dāng)口令長度變?yōu)樵鹊?倍時，其最小熵值大約也為原先的2倍。另一方面，使用剩余哈希定理的熵?fù)p失是一個定值，隨著口令長度的增加，提取出密鑰的長度將增加得更快。舉個例子，原始口令長度為10個ASCII碼長，最小熵為23，可以提取13 bit的均勻隨機串，假設(shè)口令長度變?yōu)樵鹊膎倍，最小熵也變?yōu)樵萵倍，即23nbit，那么在保證同樣的均勻隨機性的條件下，可以犧牲10 bit，得到(23n-10) bit長的均勻隨機串。例如n=5時，可以得到105 bit的密鑰。這樣通過增加口令長度，可以很有效地增加所提取的密鑰長度。

(2) 可以由單個口令中生成多個密鑰。通過PBKGS方案，用戶可以從口令p中提取一個均勻隨機的密鑰K。假設(shè)密鑰長度是足夠的，進(jìn)一步考慮如何從一個密鑰中得到多個密鑰。國際組織IETF給出了如何使用HMAC算法對密鑰進(jìn)行擴展[12]，國家商用密碼管理辦公室發(fā)布的《SM2密碼算法使用規(guī)范》標(biāo)準(zhǔn)[13]中介紹了一個密鑰擴展函數(shù)(Key Derivation Function，KDF)，通過KDF，就可以實現(xiàn)從一個密鑰中擴展出多個密鑰。

具體來說，當(dāng)利用PBKGS從口令中提取出了一個密鑰K后，定義一個計數(shù)器Counter(初始化為1，每一次計算后都增加1)，將Counter和密鑰K作為密鑰擴展函數(shù)的輸入，計算Ki=KDF(K，Counter)。根據(jù)密鑰擴展函數(shù)的性質(zhì)，就得到了多個密鑰K1，K2，…，這些密鑰可分別用于微信、郵箱、QQ認(rèn)證、文件加密中等應(yīng)用中的密碼算法。即使用戶有一個密鑰Ki泄露，也可以保證其他密鑰Kj，j≠i的安全性。具體見圖7。

(3) 從口令里提取的密鑰應(yīng)用于不同的密碼方案。這里簡單地介紹密鑰用于認(rèn)證、加密的場景。

認(rèn)證：用戶A希望在應(yīng)用服務(wù)器注冊個人賬號，他/她可以使用口令提取的均勻隨機串作為密鑰，產(chǎn)生一個基于身份的認(rèn)證符，并把認(rèn)證符發(fā)給服務(wù)器用于以后的身份認(rèn)證。當(dāng)用戶A需要登錄時，只需要用同樣的口令提取出均勻隨機串作為密鑰，再次產(chǎn)生基于身份的認(rèn)證符，發(fā)送給服務(wù)器即可驗證通過。

加密：用戶A希望加密一個Word文檔，他/她可以通過口令提取的均勻隨機串作為對稱加密算法的密鑰，當(dāng)用戶A需要解密時，只需要用同樣的口令提取出隨機串。對于對稱加密算法來說，加密密鑰與解密密鑰是一樣的，因此用戶A可以正確解密密文，獲得原始文檔。

圖7 密鑰擴展方案示意圖