【正文】 計算機安全保密第二講 密碼學(xué)數(shù)學(xué)基礎(chǔ) 唐明 武漢大學(xué)計算機學(xué)院 本次課的內(nèi)容 ? ? ? ? ? 素數(shù)的產(chǎn)生 ? 有限域內(nèi)的離散對數(shù) ? 單向哈希函數(shù) 信息論 熵與疑義度 自然語言率 密碼系統(tǒng)的安全性 確定性距離 混亂與擴散 熵與疑義度 ? 1949年， Shannon發(fā)表“ Communication Theory of Secrecy Systems” ? 一條消息中的信息量，形式上由該消息的熵來度量。 一、 自信息和熵 自信息 文字、圖象、聲音是消息，信息是消息的有價值內(nèi)容 。 ①給定一 離散事件集 X， 它含有 N 個事件 x1,x2,…,x N， 事件 xi 出現(xiàn)的概率記作 pi， 1≥ pi≥0 且 ②自信息定義 定義 事件 xi的自信息，記作 I(xi),定義為 ? 注意： 自信息的定義沒有規(guī)定對數(shù)的底！ ? 對數(shù)底為 2時，自信息單位為比特（ bit） ； ? 對數(shù)底取為 e時，自信息單位為奈特（ nat） ； ? 對數(shù)底為 10時，自信息單位為哈特（ hart） 。 ???Niip11ii pxI log)( ??離散隨機事件概率對數(shù)值的絕對值。 ③自信息的含義 – 自信息度量了一個隨機事件 xi未出現(xiàn)時所呈現(xiàn)的 不確定性 ，也度量了該事件 xi出現(xiàn)后所給出的 信息量 。 – 事件的不確定性越大，則一旦出現(xiàn)給出的信息量也就越大。 ④舉例 例 計算從英文字母表中任選一個字母時所給出的自信息量。 因為從 26個字母中任取一個字母的概率為， 所以任選一個字母所給出的信息量為 261?p 261log2 ???I 一、 自信息和熵 熵 ? 自信息描述了事件集 X中一個事件出現(xiàn)給出的信息量， 整個集 X的平均信息量是該集所有事件自信息的統(tǒng)計平均值（數(shù)學(xué)期望），稱作集 X的熵 。 ? 定義 集 X的熵，記作 H(X)， 定義為 定義中，規(guī)定 0log0=0。 ? H（ X） 度量了集 X中各個事件未出現(xiàn)時所呈現(xiàn)的平均不確定性 (疑義度 )， 也度量了集 X中一個事件出現(xiàn)時所給出的平均信息量。 ???? Niii ppXH1log)( ? 疑義度：消息的熵同時也可衡量其不確定性（疑義度），即將消息隱藏在密文中時，要破譯它所需的明文比特數(shù)（即當消息被加密成密文時，為了獲取明文需要解密的明文的位數(shù)）。 一、 自信息和熵 熵 ? 舉例 例 給出集 按定義有 : ? I(x1) =log2 1/2=log2 2 =1比特， ? I（ x2） =I（ x3） =log2 1/4=log2 4=2比特。 于是 ? 一個事件集的熵越大，其不確定性越高。 ? ? 41,41,21, 321321 ???? pppxxxX。 )( ???????XH比特。 關(guān)于熵的實際例子 ? 例： X可能在下周某天去釣魚。 星期一， …… ，星期日共有七種可能（ x1， … ， x7），假設(shè)各種可能性出現(xiàn)概率相等，則： P（ Xi） =1/7，H（ x） =－ 7(1/7)log21/7=－ log21/7= log27 ? 同時， H（ x） 也指出了 X中的信息量將消息中所有可能的值進行編碼時所需的最少比特數(shù)。 2 H(x)= log27 3 ? b1b2b3可以表示一周的 7個狀態(tài)： – 000 星期日 – 001 星期一 – …… – 110 星期六 – 保留 關(guān)于熵的實際例子 ? 甲任意取一個不超過 15的整數(shù)，由乙來猜，但允許乙提 K個問題，甲只回答“是”或者“非”，問 K多大時可以確定猜到該數(shù)。 解：若令乙猜想作為事件 V， V可能有 16種結(jié)果 ， 假定這 16種結(jié)果是等概率的 ， V的熵為： H（ V） = log216 令事件 Ak=U1U2U3… Uk為提問 k個問題 ， 但 Ui的熵不超過 log22=1，（ 因為只有 “ 是 ” 或者 “ 非 ” ） ， 故 Ak的熵為不超過 k比特 ， 則： log216 ? klog22 =k， k ? 4 故 k=4 繼續(xù)前面的例子 ? 0到 15之間的數(shù)可以由 4比特信息來表示。即 —— —— —— —— 而上面的問題實際上可以轉(zhuǎn)化為如何獲得這 4個比特信息。因為每個問題的答案只有兩種，故每個問題的答案最多只能提供 1比特的信息。 因而如果要確保得到正確結(jié)果，則至少需要 4次。 那如何保證每次可以獲得 1位的信息呢？ 最直接的四個問題： 這個數(shù)被表示為四位二進制后，第一位是 0嗎？ 這個數(shù)被表示為四位二進制后，第二位是 0嗎？ …… 這樣，我們可以確保每次都可以得到一位信息。 思考？ ? 假設(shè)乙的第一個問題是“這個數(shù)字是 a嗎？” – 其中 a是 015之間的任意一個確定的數(shù)。 ?如果乙得到“是”的回答，請問該事件提供的信息量是多少？ ?如果乙得到“否”的回答，請問乙是否還能夠確保在規(guī)定次數(shù)之內(nèi)得到正確結(jié)果？為什么？ 思考？ ? 假設(shè)乙的第一個問題是“這個數(shù)字大于11嗎？” ?如果乙得到“是”的回答，請問該事件提供的信息量是多少？ ?如果乙得到“否”的回答，請問乙是否還能夠確保在規(guī)定次數(shù)之內(nèi)得到正確結(jié)果？為什么？ 關(guān)于熵的實際例子 ? 有 25個外表完全相同的硬幣，其中 24個重量完全一樣，有一個較輕的偽幣，用無砝碼的天平，試問要做多少次的比較，可以找到這枚偽幣？ 繼續(xù)前面的例子 解：事件 V為找出偽幣 ， 可能有 25個結(jié)論 ， 他們是等概率 ， 故： H（ V） = log225， 事件 U為天平稱的結(jié)果 ， 可能有 3種情況： ；； ；故： H（ U） = log23 令 Ak=U1U2U3… Uk為連續(xù)用 k次天平的事件 ， klog23 ? log225 k ? （ log225） / log23= 故 k最少為 3次 繼續(xù)前面的例子 ? 一種解決方案： i. 25=8+8+9（第一次） ? 天平兩端各放 8個，如果平衡，則偽幣在剩余的 9個之中，跳到 ii； ? 如果不平衡，則偽幣在較輕的 8個之中，跳到 iii。 ii. 9=3+3+3（第二次） ? 天平兩端各放 3個，如果平衡，則從剩下 3個中尋找偽幣。否則，從較輕的 3個中尋找偽幣。 iii. 8=3+3+2（第二次） ? 天平兩端各放 3個，如果平衡，則從剩下 2個中尋找偽幣。否則，從較輕的 3個中尋找偽幣。 思考？ ? 有 25個外表完全相同的硬幣，其中 24個重量完全一樣，偽幣重量不一樣，但不知是輕還是重，用無砝碼的天平，試問要做多少次的比較，可以找到這枚偽幣？ 自然語言率 ? 自然語言率：對于給定的一種語言，其自然語言率為 r = H(M)/ N 其中 N為消息長度。 – 英語的自然語言率： /字母～ /字母 – 它是一個語言系統(tǒng)的實際表現(xiàn)力，實際上是一個語言系統(tǒng)的實際熵。 絕對語言率 ? 絕對語言率：每個字符編碼的最大比特數(shù)，這里假設(shè)每個字符序列出現(xiàn)的機會相等。 – 若語言中有 L個字母，則絕對語言率為： R = log2L 為單個字母的最大熵。 – 英語的絕對語言率： log226 ? /字母 – 它是一個語言系統(tǒng)理論上的最大表現(xiàn)力。當每個字符出現(xiàn)的概率相同時，其具有最大表現(xiàn)力。實際上是語言系統(tǒng)的最大熵。 ? 冗余度：語言的冗余度記為 D， 定義為： D = R r 其中， R為絕對語言率， r為自然語言率。 – 英語： r = /字母，則 D = /字母。 密碼系統(tǒng)的安全性 ? 絕對安全的密碼系統(tǒng)： – M： 明文空間； K： 密鑰空間； C： 密文空間； c= E(m, k)。 E： M →C 。 – H(M), H(K) – 絕對保密的密碼系統(tǒng)的必要條件： H(K) H(M) 盧開澄，計算機密碼學(xué)，清華大學(xué)出版社。 即：一次一密（密鑰與消息本身一樣長，且密鑰不重復(fù)使用）系統(tǒng)。 ? 密碼系統(tǒng)的熵：衡量密鑰空間 K的大小的一個標準，通常是密鑰數(shù)以 2為底的對數(shù)。 H（ K） = log2k 確定性距離 ? 對于長度為 n的消息，能夠?qū)⒁欢蚊芪南⒔饷艹膳c原始明文同種語言的可懂文本的密鑰個數(shù)為： 2H(K) nD