第5,6講-偽密鑰和唯一解距離

§3.2偽密鑰和唯一解距離2005年3月92023/1/51

定理3.1

設(shè)b>1,則有

且,都有(2)當(dāng)且僅當(dāng),都有(1)(3)當(dāng)且僅當(dāng)存在使得上節(jié)內(nèi)容回顧熵:2023/1/52上節(jié)內(nèi)容回顧定理3.3

推論3.1且等號成立X與Y獨立.定理3.2:且等號成立X與Y獨立.聯(lián)合熵:條件熵:結(jié)論:且等號成立X與Y獨立.平均互信息:2023/1/53§3.2偽密鑰和唯一解距離主要內(nèi)容:

利用Shannon信息論,研究密文、明文和密鑰的信息量。分析唯密文攻擊條件下要唯一確定密鑰時至少需要的密文長度。2023/1/54

定理3.4設(shè)M,K,C分別是明文空間、密鑰空間和密文空間上的隨機變量，則有截獲密文后密鑰的未知信息量等于明文與密鑰總的未知信息量減去從已知的密文中獲得的信息量。直觀含義:2023/1/55

定理3.4設(shè)M,K,C分別是明文空間、密鑰空間和密文空間上的隨機變量，則有根據(jù)條件熵與聯(lián)合熵之間的關(guān)系,有證明:由于知道密文和密鑰,自然也知道明文,因而密鑰和密文都知道時提供的信息量H(K,C)等于密鑰、密文和明文都知道時提供的信息量H(K,M,C),即下證之.由和條件熵與聯(lián)合熵的關(guān)系知同理,有,故由密鑰與明文獨立知2023/1/56截獲密文C后,就可將密鑰唯一確定等價于

下面根據(jù)這個條件,計算至少需要多少密文才能將密鑰唯一確定.將密鑰唯一確定所需要的最少的密文的數(shù)量,就稱為該密碼體制的唯一解距離.

要求唯一解距離,需要首先計算計算出n長明文M的熵H(M)和n長密文的熵H(C).定理3.4說明:截獲密文C后,就可將密鑰唯一確定等價于2023/1/57(A)n長密文熵的計算我們需要做一個合理的假設(shè):

假設(shè):密文是隨機的!設(shè)密文字母表為Y,則n長密文就是由字母表Y中n個字母組成的密文字母串.結(jié)論:設(shè)n長密文服從均勻分布,則n長密文的熵為

證明:因n長密文共有個,從而由n長密文服從均勻分布和熵的性質(zhì)知2023/1/58

如何刻劃明文本身包含的未知信息量呢?我們給出如下的定義：

設(shè)明文字母表為X,則n長明文就是由字母表X中n個字母組成的明文字母串.(B)n長明文熵的計算2023/1/59定義3.5（2）設(shè)L是一種語言,則稱為該語言L的冗余度(Redundancy).定義3.5

(1)設(shè)L是一種語言,則稱為該語言L的(單字母)熵.因此,當(dāng)n很大時,近似有2023/1/510例1如果由64個二進制數(shù)構(gòu)成的某類密鑰

的熵平均是56比特,則該類密鑰的熵為0.875比特.例2如果由64個二進制數(shù)構(gòu)成的某類密鑰的熵平均是56比特,則該類密鑰的冗余度是

1-0.875=0.125比特即:平均每個密鑰比特有0.125個比特是多余的.2023/1/511

下面轉(zhuǎn)到分析需要截獲多少密文才能將密鑰唯一確定的問題.2023/1/512定義3.6稱將密鑰唯一確定所平均需要的最少的密文的數(shù)量為該密碼體制的唯一解碼量.唯一解碼量也稱為唯一解距離.

將密鑰唯一確定等價于H(K|C)=0.下面根據(jù)定理3.4的結(jié)論計算一個密碼體制的唯一解碼量.2023/1/513當(dāng)截獲n長明文X(n)對應(yīng)的n長密文Y(n)后,就可將密鑰的信息全部確定等價于現(xiàn)設(shè),則有從而即

也就是說,當(dāng)截獲個密文字母后,就可將密鑰的信息全部確定.2023/1/514

設(shè)已知密文C(n)及對應(yīng)的明文M(n).由于明文M(n)是已知的,因而此時該明文的熵H(M(n))=0,因而RL=1.這就是說,當(dāng)n=H(K)/RL=128時,就可將密鑰的信息唯一確定.即此時唯一解距離為128.

結(jié)論:設(shè)明文的(單字母)冗余度為,則所有密碼體制的唯一解距離均為

例:對于具有128比特密鑰的密碼體制,平均需要128比特的已知明文,就能將密鑰唯一確定.其中已知明文就是已知一個密文和它對應(yīng)的明文.解畢解:2023/1/515

幾點說明:

（1）由于唯一解距離量是用熵推出來的，因而它只是將密鑰唯一確定所平均需要的密文長度。由于明文熵是每份明文所包含的信息量關(guān)于所有明文的平均值，因而有時需要的密文數(shù)量少，有時需要的數(shù)量多，但其平均值就是唯一解碼距離。

（2）明文熵不同，唯一解距離也不同。明文熵就是你在攻擊過程中每個字母所能利用的信息量。

（3）如何確定唯一密鑰？確定過程實際上能否實現(xiàn)，這里并不關(guān)心。一般而言，窮舉攻擊所需的平均密文量就是該密碼體制的唯一解距離。2023/1/516

偽密鑰首先介紹候選密鑰、偽密鑰和等效密鑰的概念。

候選密鑰：攻擊者在求解正確密鑰時，求出的可能密鑰都稱為候選密鑰。

平均來看,當(dāng)?shù)玫降拿芪臄?shù)量小于唯一解距離時,候選密鑰未必只有一個,此時,就會有多個候選密鑰.

偽密鑰：攻擊者得到的候選密鑰中的錯誤密鑰稱為偽密鑰.

等效密鑰：如果兩個密鑰對所有明文的加密結(jié)果都相同,則稱這兩個密鑰為等效密鑰.

兩個等效密鑰k1和k2對應(yīng)的加密函數(shù)和就是一個函數(shù),因而它們的加密效果完全相同.2023/1/517§3.1密碼體制的數(shù)學(xué)模型密碼體制由明文空間、密文空間、密鑰空間和密碼算法四部分構(gòu)成。

被加密的明文服從明文空間上的一個概率分布pm(x)；

被使用的密鑰服從密鑰空間上的一個概率分布pk(x);

密文也服從密文空間上的一個概率分布pc(x)；.

注意:

密鑰的分布與明文的分布獨立!2023/1/518§3.3密碼體制的完善保密性

定義3.7(完善保密性)對一個密碼體制而言，如果明文與密文獨立，即對所有明文空間中的任一點x

和密文空間中的任一點y,都有則稱該密碼體制具有完善保密性(Perfectsecrecy).或稱該密碼體制是完全保密的。

等價刻劃:一個密碼體制具有完善保密性當(dāng)且僅當(dāng)對所有明文空間中的任一點x

和密文空間中的任一點y,都有2023/1/5