第七章-密码体制的安全性测度

第7章：信息论与密码体制的安全性测度Shannon的信息论和保密码通信理论1.信息论与密码学的发展古典密码学：密码专家常常根据自己的感觉和经验进行密码设计和分析，密码设计中的技巧性和经验性很强.Shannon：美国工程师1948年发表“AMathematicalTheoryofommunication”，标志信息论的诞生1949年发表“CommunicationTheoryofSecrecysystem”，以信息论为基础，用概率统计为数学手段对保密通信问题进行了分析。由香农提出的保密系统模型目前仍然是现代密码学的基本模型.•1973年，美国国家标准局（NBS）发布了公开征集标准分组密码算法(DES)的决定•公钥密码学建立：1976年，Diffie和Hellman提出了公钥密码设计思想公开DES算法和公钥密码学的建立标志着现代密码学的开始•美国在2000年公布了高级加密标准(AES-AdvancedEncryptionStandard),欧洲在2000年1月也推出了欧洲加密标准评选计划，在2003年2月27日公布了各个算法标准2.Shannon的信息论与信息传输理论Shannon通信系统Shannon通信系统:信源：产生信息的来源编码：把信息变为信号的运算以适合在信道中的传输信道：用来从发射者到接收者之间传输信号的介质译码：把信号变为信息的运算信宿：信息传输的归宿和目的地，信息接收人或仪器编码译码信宿信源信道干扰源3.信息安全与密码学密码学(Cryptology):是研究密码系统或通信信息安全的一门科学。它主要包括两个分支:密码编码学和密码分析学。密码编码学(Cryptography):寻找确保信息保密或信息得到认证的方法密码分析学(Cryptanalytics):主要是研究破译加密信息或消息的伪造密码技术革新是信息安全的关键技术.Shannon保密通信系统公开信道m信源)(mECk加密器kK密钥源m信宿)(CEmk1解密器kK密钥源密码分析者密钥信道C明文(Plaintext):没有加密的消息密文(Ciphertext):加密后的消息加密算法(Encryption):将明文变换成密文的过程解密算法(Decryption):将密文恢复成明文的过程加密和解密过程通常在一组密钥(key)的控制下进行，密钥分别称为加密密钥和解密密钥。基本概念密码体制系是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）（4）任意k∈K，有一个加密算法ek∈E和相应的解密算法dk∈D，使得ek:PC和dk:CP分别为加密解密函数，满足dk(ek(x))=x，这里x∈P。密码体系形式化描述加密算法足够强大：仅知密文很难破译出明文基于密钥的安全性，而不是基于算法的安全性：基于密文和加/解密算法很难破译出明文算法开放性：开放算法，便于实现加密的安全性问题理论安全和实际安全理论安全，或无条件安全：攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。Shannon用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密，One-timePad，不实用。实际安全，或计算上安全：如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行（ComputationallyInfeasible）。无条件保密性也叫完善保密性。一个保密系统具有完善保密性，是指攻击者在有无限的攻击时间和资源下无法破译此系统。Shannon在理论上证明了在唯密文攻击条件下完善保密性的系统是存在的。“一次一密”(one-timepad)保密系统:假设密钥空间大于或等于明文空间，密钥空间的各个分量是统计独立的，并且是等概率地选取，对不同的明文用不同的密钥进行加密。在此假设条件下，仅从密文得不到明文的任何信息“一次一密”保密系统在理论上被认为是不可破译的。即使密码分析者知道了和一段密文相对应的明文，他也仅仅得到了这一段的密钥，由于密钥空间大于或等于明文空间，密钥不重复使用，因此，已知密钥对其他密文并不适用但是，进行大量的明文加密，产生如此多的一次一密的密钥十分困难，密钥的管理和通信双方的沟通也有困难。实际的加密系统是通过双方共享重复使用的有限长度的主密钥，利用算法复杂性产生伪随机数进行加密所以：一次一密（one-timepad）方案不实用。熵的密码意义：如果H(M)=0,则表示该信息不含任何不确定性，因此，该信息或该事件百分之百会发生。从通信的角度看，既然该信息百分之百会发生，意义就不大，没有必要再发送。反之，如果H(M)很大，则表示信息的不确定性很大，从而收方收到该信息时，其信息量就相当大（重要）了。从安全角度看，如果信息的熵值不大，即不确定性太小，此条件提供攻击者很大的概率可以猜中该信息，从密码技术角度来说，就易破解；反之，熵值越大，越难破解。4.熵与密码学从信息论的观点看，一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果H(P)=H(P|C)。（知道密文与不知道密文时，关于明文的熵大小一样）对于完善保密系统，也有H(K)=H(K|C)。密码体制的熵从Shannon理论知道，仅当可能的密钥数目至少与可能的消息数目一样多时，它完全保密才是可能的。换句话说，密钥至少必须与消息本身一样长，并且没有密钥被重复使用时，这就是一次一密体制。所以可以说，密码体制的熵可用密钥空间大小的量度。即密钥的数目为K的密码体制的熵为：H（K）=log2K一般而言，一个密码体制的熵越大，不确定性越大，破译它就越困难。所以，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵5.互信息量与保密性从密文C中提取关于明文P的信息为：(;)()(/)IPCHPHPC(7.4.1)或从密文中提取密钥信息：(;)()(/)IKCHKHKC(7.4.2)因此，Ｈ(P/C)和Ｈ(K/C)越大，攻击者从密文中获得明文或密钥信息越少。(/)0HPCK(7.4.3)于是(;)()(/)()IPCKHPHPCKHP(7.4.4)对于合法用户，知道密钥和密文，就可以得到明文，即：说明对于合法用户，知道密钥和密文的情况下，就可以得到全部明文！(7.4.５)说明：密钥空间越大，从密文中可以提取的关于明文的信息量就越小。对于完善保密系统，有：(;)0IPC(7.4.６)当密钥空间大于明文空间，即()≥()HKHP(7.4.７)定理：对任意密码系统，有)()(),(KHPHCPI６.唯一解距离设给定Ｎ长密文序列：12,,,NNCcccY其中Ｙ为密文字母表。根据条件熵的性质：12112/,,,≤/,,,NNHKcccHKccc(7.4.８)易知，随着Ｎ的增大，密钥疑义度Ｈ(K/C)减小。唯一解距离V0是指攻击者在进行唯密文攻击时必处理的密文量的理论下界：亦即截获的密文越多，从中提取的关于密钥的信息就越多。当疑义度减小到零，即(/)0HKC时(;)()(/)()IKCHKHKCHK(7.4.9)密钥被完全确定，从而实现破译。如果令00()IHHP(7.4.10)代表明文信息变差，其中()HP和0H分别代表明文熵和明文最大熵，可以证明，唯一解距离00()HKVI(7.4.11)密码分析攻击有6类惟密文攻击已知明文攻击选择明文攻击自适应选择明文攻击选择密文攻击选择密钥攻击分析方法数学方法边信道攻击数学方法穷举搜索统计分析逆向推理线性分析差分分析相关分析边信道攻击时间攻击能量攻击电磁攻击故障攻击