基于信息论的密码学

期中知识要点回顾 （兼作小论文、实验、作业的评说） 1. 信息论的两个核心概念是“熵”和“码”,它们是紧密相关的。 a) 熵通常用作信息系统中的 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，回答理论问题，具有理论性。 i. 压缩编码的极限是什么？ ii. 差错控制编码的极限是什么？ iii. 理想的保密传输系统应该具有什么特征？ iv. 信道传输的极限性能是什么？ b) 码通常用作信息系统中的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ，解决实际问题，具有实用性。 i. 高性能设计（压缩码，信源编码，去冗余性） ii. 高可靠性设计（差错控制编码，信道编码，线性变换，增加冗余性） iii. 高安全性设计（密码，含参量的离散非线性变换） 2. 熵 a) 通信前的发端消息对于收端、未处理的原始数据对于观察者，具有“不确定性”， 用熵度量之， ( ) ( ) lo g ( ) x H X p x p x= −∑ b) 离散随机变量的熵 c) 离散随机序列的熵(AEP) d) 离散平稳随机过程的熵率 e) 熵是无失真压缩的极限， i. 对于均匀分布而言，没有压缩余地 ii. 对于非均匀分布而言，压缩的极限平均码长就是熵，此时的码被称为最优 码。 （连续情形的熵是期中以后的教学内容） 3. 条件熵与互信息 a) 完成通信或处理后，相当于观察到随机变量Y ，消除了部分或全部的不确定性， 即 熵 减 少 为 条 件 熵 ( | )H X Y ， 熵 的 减 少 量 用 互 信 息 度 量 之 ， ( ; ) ( ) ( | )I X Y H X H X Y= − 。 b) 互信息 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达了: 完成通信或处理后，所获得的信息量 i. 如果 ( | )H X Y =0,则 ( ; ) ( ) 0I X Y H X= − ，所以从数量上看，熵不仅表 达了“不确定性”，还表达了“信息量”。此时可依赖观察到的Y 重建 X ， 是没有误差的。 ii. 如果 ( | )H X Y >0,则 ( ; ) ( )I X Y H X< ，表明通信或处理不能够完全消除 不确定性，此时依赖观察到的Y重建 X ，是有误差的。 iii. 人们可以通过一定的工作（如通信、处理等），减少不确定性，要彻底消 除不确定性是困难的。 4. 互信息的最大值----信道容量 a) 一个好的信息流通系统，应该能够做到： 不 论 原 始 不 确 定 性 ( ) ( ) lo g ( ) x H X p x p x= −∑ 有 多 大 ， 应 保 证 ( ; ) ( ) ( | )I X Y H X H X Y= − 尽可能大， 这就引出了信道容量的概念 ( ) max ( ; ) p x C I X Y= b) 计算信道容量 i. 简单特殊信道容量的计算 ii. 一般信道容量的迭代计算算法 c) 信道编码定理指明了只要通信速率不超过信道容量，可以通过适当的编码，使 通信系统的错误概率尽可能小。 i. 线性码：Hamming纠错码 ii. 循环码：CRC检错码 课堂练习题： i. 给出 ( ) 0H X = 的条件，并予以证明。 ii. 给出 ( | ) 0H X Y = 的条件，并予以证明。 iii. 给出 ( ; ) 0I X Y = 的条件，并予以证明。 iv. 给出 0C = 的条件，并予以证明。 v. 给出以 x8 + x2 + x + 1为生成多项式的循环码的生成矩阵和校验矩阵。 延伸： 数字水印的逻辑信道（纠错码用于数字水印的预处理） 数据分析的属性约简（基于条件熵、互信息） 基于熵的最优化（熵与 GA和 ACO的结合等） 基于信息论的密码学 （Cryptography Based on Information Theory） 1949年，Shannon发表了题为“保密系统的通信理论”的论文，把信息论引入密码学中， 使得信息论成为研究密码学的一个重要理论基础，并将已有数千年历史的密码学推上了科学 的轨道，形成了科学的私钥密码学理论，很多学者将此后的时代称为科学密码学时代。 1976年，Diffie-Hellman发表了“密码学的新方向”，使得科学密码学进入一个新时期： 非对称密码体制 时期。 保密通信系统设计的目的是使攻击者即使在完全准确地接收到信号的情况下也无法恢 复出原始消息。 本章目标：在信息论的框架下，回答一个基本问题：保密通信系统在什么条件下具有无 条件安全性（理论安全性）？ 安全性 密码系统有两种安全性标准： 一是无条件安全性（理论安全性、完善保密性、完全保密性），指破译者具有无限时间、 截获足够多的密文、具有无限计算资源下的抗破译能力； 二是实用安全性（实际安全性），指在破译者仅有一定计算资源及其它实际限制下的抗 破译能力。可以分为计算安全性（computational secure）和可证明安全性（provable secure）： 计算安全性：如果破译一个系统在原理上是可行的，但是用已知的算法和现有计算工具 不可能完成所要求的计算量，就称其为计算上安全的。 可证明安全性：如果能够证明破译某密码体制的困难性等价于解决某个数学难题，就称 其为可证明安全的。 计算安全性和可证明安全性都是从计算量来考虑问题的，不完全相同。  计算安全性要算出或估计出破译的计算量下限。  可证明安全性要从理论上证明破译的计算量不低于解已知难题的计算量。 ( ) ( ) ( ( )) ke kd kd ke kd ke c E m m D c D E m D E I = = = = 图：保密通信系统模型 公开信道 秘密信道 明文m 密文 c 明文m 信源 加密编码器 Eke 解密译码器 Dkd 接收者 密钥 k 密码分析者 1976 年以前研究的密码体制都具有特征： d ek k= 或两者之间存在简单的关系，称这 样的密码体制为对称密码体制或单钥密码体制。1976 年以后，出现了一种新的密码体制， 其特征是 d ek k≠ ，并且由 ek 不能简单地计算出 dk ，其计算难度通常都是与一些数学难题的 求解有关，称这样的密码体制为非对称密码体制或双钥密码体制。 加密解密 密钥分发 数字签名 代表体制 对称密码体制 速度快 难 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 复杂 DES,AES,IDEA 非对称密码体制 速度慢 易 方案简单 DH, RSA,ECC 混合密码体制 用非对称密码体制做密钥分发，用对 称密码体制做数据的加密和解密 一个安全的密码系统通常应满足如下条件： 1. 系统即使不是理论上不可破译，至少也应当是实用上不可破译； 2. 系统保密性不是依赖于加密算法与解密算法，而是依赖于密钥的保密性； 3. 加密运算、解密运算简单快速，易于实现； 4. 密钥量适中，密钥的分配、管理方便。 密码分析（cryptanalysis） 密码系统的攻击类型，按照攻击者可获取的信息量来决定. 攻击类型 攻击者掌握的内容 例子 算法 密文 其它信息 1. 惟密文攻击 （ciphertext only） 加 密 算法 截获的 部分密文 2. 已知明文攻击 （known plaintext） 加 密 算法 截获的 部分密文 一个或多个明文-密文对 有固定格式或某些固定内容的 文件、文档 3. 选择明文攻击 (chosen plaintext) 加 密 算法 截获的 部分密文 攻击者选择的明文消息以 及由密钥产生的相应密文 攻击者有机会使用密码机，在 源系统中插入明文，可以蓄意 插入揭示密钥结构的消息模式 4. 选择密文攻击 (chosen ciphertext) 加 密 算法 截获的 部分密文 攻击者选择的密文消息 以及相应的被解密的明文 攻击者有机会使用密码机，可 选择一些密文，并产生明文 5. 选择文本攻击 （chosen text） 加 密 算法 截获的 部分密文 3和 4的结合 3和 4的结合 按攻击手段分类 攻击类型 英文术语 分组密码的分析方法 1. 强力攻击 Brute-force approach 尝试所有可能的密钥 增 大 密 钥 空 间 （key space） 2. 统计测试 Statistical test approach 统计符号模式的频度 扩散、混淆等 3. 差分密码分析 Differential Cryptanalysis 选择明文攻击中选择 一些特殊的模式 4. 线性密码分析 Linear cryptanalysis 5. 差分--线性密码分析 Differential-Linear Cryptanalysis 6. 插值攻击 Interpolation Cryptanalysis 7. 密钥相关攻击 序列密码的分析方法 公钥密码的分析方法 密码学的三个阶段 阶段 假设前提 体制 关键人物 第一阶段 1949年以前 古典密码学时期 算法不公开 密钥不公开 对称体制 第二阶段 1949年以后 科学密码学的开始 算法公开* 密钥不公开 对称体制 （单钥体制） Shannon 第三阶段 1976年以后 公钥密码学的开始 算法公开* 加密密钥公开 非对称体制 （双钥体制） 混合体制 Dieffie-Hellman *密码体制的算法公开，也被称为 Kerckhoff假设 完全保密系统 下面针对惟密文攻击（ciphertext only）研究对称密码系统的理论安全性 定 义 【 完 全 保 密 】 密 码 系 统 。 ( , , , , )k kM B K E D 称 为 完 全 保 密 ， 是 指 对 , , ( ) 0i j jm M c B p c∀ ∈ ∈ > ，有 ( | ) ( )i j ip m c p m= 即 ( ; ) ( ; ) 0I M B I B M= = 定理【完全保密的充要条件】密码系统 ( , , , , )k kM B K E D 为完全保密的充要条件是指对一 切 , , ( ) 0i j jm M c B p c∈ ∈ > ，有 ( | ) ( )j i jp c m p c= 证明：因为 ( | ) ( ) ( | ) ( ) ( , )j i i i j j i jp c m p m p m c p c p m c= = 所以 , , ( ) 0i j jm M c B p c∀ ∈ ∈ > ， ( | ) ( )i j ip m c p m= ⇔ ( | ) ( )j i jp c m p c= 上述定理表明：对于每个密文 , ( ) 0j jc B p c∈ > ，则对任意的 ,im M∈ 总存在密钥 k，满足 ( )k i jE m c= ，其理由是 ( | ) ( ) 0j i jp c m p c= > 。 定理【数量关系】在一个完全保密的密码系统 ( , , , , )k kM B K E D 中， （1） B M≥ （2） K M≥ ，不同的密钥数目不会少于不同明文的数目。 在证明上述定理之前，首先说明该定理的用途：对于一个分组密码体制而言，若密钥串 的长度为 Kl ，则明文数据的分组长度 Ml 最好不要超过 Kl ，即 M Kl l≤ 。 下面证明该定理。 证明： （1） k K∀ ∈ ，由于加密变换为一一变换， 故有 , , ( ) ( )i j i j k i k jm m M m m E m E m∀ ∈ ≠ ⇒ ≠ ，从而密文数目不会少于明文数目， 即 B M≥ 。 （2） , ( ) 0 , , . . ( ) i i i k i c B p c m M k K s t E m c ∀ ∈ > ⇒ ∀ ∈ ∃ ∈ = 并且 若 i j≠ ，则 i jk k≠ ， 否则 i jk k E E= 将两个不同的明文 ,i jm m 变换成同一个密文 c， 与“编码变换是一一对应的”相矛盾。 从而加密变换数不会少于明文的数目，即密钥数至少同明文数目相等 K M≥ 定理【特殊数量关系】在一个密码系统 ( , , , , )k kM B K E D 中，若 M B K n= = = ，则该 密码为完全保密的充要条件是： （1） , , | , . . ( ) i j k i j m M c B k s t E m c ∀ ∈ ∀ ∈ ∃ = （2） 1, ( )k K p k n ∀ ∈ = 证明： 充分性证明。 若（1）（2）成立，则对 ,i jm M c B∀ ∈ ∀ ∈ 有 1( | ) ( )j ip c m p k n = = 1 1 1 1( ) ( | ) ( ) ( ) ( | ) n n j j i i i j i i i p c p c m p m p m p c m n n= = = = = =∑ ∑ 故由定理【完全保密的充要条件】知，该密码系统为完全保密系统。 必要性证明。 （1）若该密码系统是完全保密的，由于 M B= ，而每个 kE 都是一一变换，故 , ( ) 0j jc B p c∀ ∈ > 。 进而由完全保密的充要条件，对任意的 ,im M∈ 至少存在一个密钥 k，满足 ( )k i jE m c= 。 （注解：若用二部图来解释，任意两对顶点之间有边相连） 又若有两个不同的 1 2,k k K∈ ，而 1 2( ) ( )k i k i jE m E m c= = 则由于 m M∀ ∈ ，均可对应为任一个 c B∈ ，此时对于不同的 c需要不同的 kE ，故至少有 B 个不同的 kE ，使得m在它们的映射之下互不相同。 而 K B= ，故不可能有 1 2k k≠ ，且 1 2( ) ( )k i k i jE m E m c= = 的情况产生，与假设矛盾，从 而（1）成立。 （2） 又 j∀ ，有 1 2( | ) ( | ) . . .( | ) ( )j j j n jp c m p c m p c m p c= = = = ， 而 ( | )j ip c m 表明将明文 im 加密成密文 jc 的概率，它等于将明文 im 加密成密文 jc 的所有密 钥的概率之和，即： : ( ) ( | ) ( ) k i j j i k E m c p c m p k = = ∑ 由（1）可知，满足 ( )k i jE m c= 的 k只有一个，记为 ijk ，所以 ( ) ( | ) ( )ij j i jp k p c m p c= = 当 im 跑遍明文空间时， ijk 跑遍密钥空间，所以密钥等概率。 定理【存在性】完全保密系统存在。 提示：构造性证明 1 1 2 2( ) ( , ,..., )k N Nc E m m k m k m k m k= = ⊕ = ⊕ ⊕ ⊕ 唯一解距离 本节讨论在惟密文攻击下破译一个密码系统时密码分析者必须处理的密文量的理论下 界。Shannon从密钥含糊度（疑义度） ( | )H K C 出发研究了此问题。 ( | )H K C 给出了在给 定密文下密钥的不确定性。 定义【明文熵、密钥熵、含糊度】 对密码系统 ( , , , , )k kM B K E D ， 明文熵定义为 ( ) ( ) lo g( ) m M H M p m p m ∈ = −∑ 密钥熵定义为 ( ) ( ) lo g ( ) k K H K p k p k ∈ = −∑ 明文含糊度定义为 , ( | ) ( , ) log ( | ) t n t n m X c Y H X Y p c m p m c ∈ ∈ = − ∑ 密钥含糊度定义为 , ( | ) ( , ) log ( | ) n n k K c Y H K Y p c k p k c ∈ ∈ = − ∑ 定义【惟一解距离】一个密码系统的惟一解距离 0N 定义为使 ( | ) 0 nH K Y = 的最小正 整数 n，即 0N = min {: ( | ) 0} nn H K Y = 。 直接计算 ( | )nH K Y 或计算 0N = min {: ( | ) 0} nn H K Y = 都是非常困难的。 Shannon提出利用随机密码模型来估计 ( | )nH K Y 。随机密码模型满足如下假设： 1) 明文、密文共用同一个字母表 A，长度为 n的明文集合 nA 划分成两个集合 nB 和 n n nB A B= − ， nB 中的明文是有意义的，而 nB 中的明文是无意义的，且当 n→∞ 时， nB 中明文出现的概率可忽略不计； 2) 密钥为等概率分布； 3) 对于 k K∈ ，对应的加密变换 kE 是 n nA A→ 的一一映射； 4) nB 中的明文为等概率分布 定理【密钥含糊度的计算 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 】若密码系统 ( , , , , )k kM B K E D 满足随机密码模型假设、 并且将长度为 n的明文加密成长度为 n的密文，则 ( | ) ( ) ( ) ( )n n nH K Y H K H X H Y= + − 证明： 对于满足随机密码模型假设的密码系统而言， （1） ( | , ) 0n nH Y K X = （已知密钥和明文可以求出密文） （2） ( | , ) 0n nH X K Y = （已知密钥和密文可以求出明文） （3） ( , ) ( ) ( )n nH K X H K H X= + （明文和密钥相互独立） 由条件熵与联合熵之间的关系有 （4） ( | , ) ( , , ) ( , )n n n n nH Y K X H Y K X H K X= − （5） ( | , ) ( , , ) ( , )n n n n nH X K Y H Y K X H K Y= − 由（1）（2）（4）（5）式得： （6） ( , ) ( , )n nH K Y H K X= 所以由（6）和（3）式有 ( | ) ( , ) ( ) ( , ) ( ) ( ) ( ) ( ) n n n n n n n H K Y H K Y H Y H K X H Y H K H X H Y = − = − = + − 定义【信息率与剩余度】：信源的绝对信息率定义为 0 logR A= ，信源的近似信息率定 义为 log n n B R n = ，信源的近似剩余度定义为 0n nd R R= − 。 由假设条件知， 0 ( ) log ( ) log n n n n H X nR B H Y nR n A = = = = 所以有 0( | ) ( ) n nH K Y H K nR nR= + − 令 ( | ) 0nH K Y = ，则有 0 0 ( ) ( ) n n H K H KN n R R d = = = − 记 lim nnH R→∞= 为信源信息率，n充分大时，可用 H来代替 nR ，即有 0 0 ( )H KN n R H = = − 注解： （1） 0 0 ( ) ( ) n n H K H KN n R R d = = = − 是一个理论值，它说明：在截获的密文长度大于 0N 时，如果破译者具有无限的计算能力，并且能充分利用信源的全部统计 知识，则可唯一确定所使用的密钥，从而可以破译该密码。 （2） 一般而言，破译一个密码系统所需要的密文量均远大于它。 （3） 从理论上讲，惟一解距离与密钥熵成正比，与剩余度成反比。因此，如果希 望一个密码系统的破译难度大，就希望惟一解距离大，也就是希望密钥熵大 而剩余度小。 （4） 对 应 随 机 密 码 模 型 假 设 ， 如 果 密 钥 空 间 大 ， 则 密 钥 熵 大 。 1 1( ) ( ) log ( ) log log k K k K H K p k p k K K K∈ ∈ = − = − =∑ ∑ 。 （5） 理论安全性毕竟是理想假设下的结论，现实的密码系统则是考虑实用安全性 的。实用安全性通常以“计算复杂性”为理论基础。 基于信息论的密码学 安全性 密码分析（cryptanalysis） 完全保密系统 唯一解距离