第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且等號(hào)成立X與Y獨(dú)立.定理3.2:且等號(hào)成立X與Y獨(dú)立.聯(lián)合熵:條件熵:結(jié)論:且等號(hào)成立X與Y獨(dú)立.平均互信息:2023/1/53§3.2偽密鑰和唯一解距離主要內(nèi)容:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

幾點(diǎn)說明:

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

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

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

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

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

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

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

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

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

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

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

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

注意:

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

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

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

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

和密文空間中的任一點(diǎn)y,都有2023/1/5