密码学的基本概念和信息理论基础

1密码学的基本概念和信息理论基础2什么是密码学•密码学是研究密码系统或通信安全的一门学科•密码编码学是使得消息保密的学科，从事此行的称为密码编码者•密码分析学（密码破译学）是研究加密消息的破译的学科，从事此行的称为密码分析者，精于此道的人被称为密码学家，现代的密码学家通常是理论数学家3密码学的发展历史•第1阶段：1949年以前，科学密码学的前夜。•第2阶段：从1949年到1975年。–标志：1949年Shannon发表的《保密系统的信息理论》一文，标志着密码学阶段的开始。•第3阶段：1976年至今。–标志：1976年Diffie和Hellman发表了《密码学新方向》一文。4保密通信的Shannon模型5组成部分•X，明文（plain-text）：作为加密输入的原始信息。•Y，密文（cipher-text）：对明文变换的结果。•E，加密（encrypt）：是一组含有参数的变换。•D，解密（decrypt）：加密的逆变换。•Z，密钥（key）：是参与加密解密变换的参数。一个密码系统由算法以及所有可能的明文、密文和密钥（分别称为明文空间、密文空间和密钥空间）组成。6密码体制的分类•几种不同的分类标准–按操作方式进行分类•操作方式：是明文变换成密文的方法。•替代操作、置换操作、复合操作。–按照使用密钥的数量进行分类•对称密钥（单密钥），如DES密码体制。•公开密钥（双密钥），如RSA密码体制。•普遍采用对称密钥和公钥密钥密码相结合的混合加密体制，即加解密采用对称密钥密码，密钥传送则采用公钥密码。–按照对明文的处理方法进行分类•流密码。•分组密码。7Kerckhoffs假设•假定：密码分析者知道对方所使用的密码系统–包括明文的统计特性、加密体制（操作方式、处理方法和加/解密算法）、密钥空间及其统计特性。–不知道密钥。•成功的密码分析不权能够恢复出消息明文和密钥，而且能够发现密码体制的弱点，从而控制通信。•在设计一个密码系统时，目标是在Kerckhoffs假设的前提下实现安全。8密码分析•密码分析：从密文推导出明文或密钥。•密码分析：常用的方法有以下4类：–惟密文攻击（cybertextonlyattack）；–已知明文攻击（knownplaintextattack）；–选择明文攻击（chosenplaintextattack）；–选择密文攻击（chosenciphertextattack）。9惟密文攻击•密码分析者知道一些消息的密文（加密算法相同），并且试图恢复尽可能多的消息明文，并进一步试图推算出加密消息的密钥（以便通过密钥得出更多的消息明文。10已知明文攻击•密码分析者不仅知道一些消息的密文，也知道与这些密文对应的明文，并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密）。11选择明文攻击•密码分析者不仅知道一些消息的密文以及与之对应的明文，而且可以选择被加密的明文（这种选择可能导致产生更多关于密钥的信息），并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密）。12选择密文攻击•密码分析者能够选择不同的密文并能得到对应的明文，密码分析的目的是推导出密钥。主要用于公钥算法，有时和选择明文攻击一起被称作选择文本攻击。13密码系统•一个好的密码系统应满足：–系统理论上安全，或计算上安全；–系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密；–加密和解密算法适用于密钥空间中的所有元素；–系统既易于实现又便于使用。14密码学的基本功能•保密性：基本功能，使非授权者无法知道消息的内容。•鉴别：消息的接收者应该能够确认消息的来源。•完整性：消息的接收者应该能够验证消息在传输过程中没有被改变。•不可否认性：发送方不能否认已发送的消息。15古典加密技术•代替密码•置换密码16Vernam密码•明文：10111•密钥：01011•密文：1110017代替密码•代替密码（substitutioncipher）：明文中的每个字符被替换成密文中的另一个字符。–简单代替，即单字母密码，如Caesar(凯撒)密码；–多码代替密码(同音代替密码)；–多字母代替密码(字母成组加密，用Huffman编码作密码)；–多表代替密码，如Vigenère密码。18Caesar密码•ADBECFDGEHFIGJ•HKILJMKNLOMPNQ•ORPSQTRGSHTIUJ•VDWEXFYGZH•f(x)=x+3mod26•明文：GOOD•密文：JRRG•f(x)=x+imod26(i為該字元的位置)•密文：JSTG19Playfair密码•Playfair加密法，密钥为一个5乘5的矩阵，将25个英文字母随意排列(其中I和J为同一位置)•加密规则：将明文字串分成两两字元组。若明文字串长度为奇数，则在明文后随意添加一个字符。将每一字元组对应到密钥矩阵中–如果构成一个矩形，则取对角线之字元为密文；–如果为一直线，则取上/下方（或左/右方）字元；–如果为一点，则可取八方之临近字元为密文。•解密规则：加密规则的反向动作。20Playfair密码PICNUXRODY•密钥：LTAFEQVKZGHBSMW明文：DEFFENCE，分组后(D,E)(F,F)(E,N)(C,E)密文：YFDDFUUA21作业•论述Caesar(凯撒)密码、Playfair密码的加密算法，并用程序实现Playfair加密算法。22置换密码•置换密码（permutationcipher）：又称换位密码（transpositioncipher），并没有改变明文字母，只改变了这些字母的出现顺序。23代替密码的特点•单字母代换密码：明文中字母的出现频度、重复字母的模式和字母相互之间的结合模式等统计特性不变，安全性差。•多码代替密码：没有隐藏明文中不同字母的统计特性，安全性有所提高。•多字母代替密码：字符块被成组加密，有利于抗击统计分析。•多表代替密码：有多个映射表，可隐藏单字母出现的频率分布。24Vigenère密码–构成•明文：每个字符惟一对应一个0~25间的数字。•密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如a表示位移0，b表示位移1，c表示位移2，......）。–加密过程：•将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模26），得到密文数字串；•最后，将密文数字串转换为字母串。25Vigenère密码的密码分析（1）•第一步：确定密钥的长度，主要方法有：–Kasiski测试法；–重合指数法。26Kasiski测试法•基本原理：对于密钥长度为d的Vigenère密码，如果利用给定的密钥表周期性地对明文字母进行加密，则当明文中有两个相同的字母组在明文序列中间隔的字母数为d的倍数时，这两个明文字母组对应的密文字母组一定相同；反之，如果密文中出现两个相同的字母组，则其对应的明文字母组不一定相同。27重合指数法•对于长度为d的字母串，x=x1,x2,…,xn，“重合指数”指的是x中两个随机元素相同的概率，记为：Ic(x)=。•基本思想：对于长度分别为n的密文串y=y1y2…yn，将其分为长度为n/d的d个子串Yi（i=1,2,…,d)，如果密钥长度为d，则Ic(Yi)≈0.065(1≤i≤d)，否则，因为采用不同的密钥依位加密，子串Yi将更为随机。对于一个完全随机的密文串，Ic(y)≈26(1/26)2=0.038。由于0.038与0.065的差值足够大，所以在一般情况下，依据重合指数法能够判断出正确的密钥长度。25022502)1(/)1(/iiinifnnffi28Vigenère密码的密码分析（2）第二步：确定密钥。通常采用重合互指数法。对于长度分别为n及n′的字母串x=x1x2…xn和y=y1y2…yn，“重合互指数”指的是x的一个随机元素与y的一个随机元素相同的概率，记为MIc(x,y)。其值仅依赖于(ki,kj)mod26。Ki为第i个密钥字在英文字母表中的序号，kj为第j个密钥字在英文字母表中的序号。通过采用重合互指数法，可以获得任何两个子串Yi与Yj的相对移位。29Shannon的保密系统信息理论•1949年，Shannon发表了一篇题为《保密系统的信息理论》的论文。•用信息论的观点对信息保密问题进行了全面的阐述，使信息论成为密码学的一个重要理论基础。•宣告了科学的密码学时代的到来。•从概率统计观点出发研究信息的传输和保密问题。30通信系统模型•目的：在信道有干扰的情况下，使接收的信息无错误或差错尽可能小。31保密系统模型•目的：使窃听者即使在完全准确地收到了接收信号的情况下也无法恢复出原始消息。32保密系统的数学模型•信源是产生消息的源，在离散的情况下可以产生字母或符号。•当信源为无记忆时：（P为各元素的概率分布）LPp(m)=P(m1,m2,……,mL)=∏P(ml)L=1•密钥源是产生密钥序列的源，通常是离散的，为无记忆均匀分布源，各密钥符号为均匀等概率。•明文空间、密文空间、密钥空间•密文空间的统计特性由明文和密钥的统计特性决定。关于密文空间的条件概率分布，任何知道密文空间和密钥空间的概率分布的人，都能确定密文空间的概率分布和明文空间。33•在保密系统研究中，假定信道是无干扰的，对于合法接收者，他知道解密变换和密钥，易于从密文得到原来的消息m，即m=Dk(c)=Dk(Ek(m))•在无干扰的条件下，假定密码分析者可以得到密文c，而且一般假定密码分析者知道明文的统计特性、加密体制、密钥空间及其统计特性，但不知道加密截获的密文c所用的特定密钥。密码的安全完全寓于密钥安全性之中。34密码体制的安全性（1）•无条件安全或完善保密性（unconditionallysecure）：–不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；–具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。35完善保密性•一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果H(P)=H(P|C)，其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法，D为解密算法，则完善保密系统存在的必要条件是H(P)≤H(K)。可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。–从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。•存在完善保密系统如：一次一密（one-timepad）方案；不实用。36密码体制的安全性（2）•实际上安全–计算上安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。–可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量。37伪密钥和惟一解距离•当分析者截获到密文c时，他首先利用所有的密钥对其进行解密，并得到明文m/＝Dk(c)，k∈K。接下来，对于所有有意义的消息m/，他记录下与之对应的密钥。这些密钥构成的集合通常含有多个元素，并且至少含有一个元素，即正确的密钥。人们把那些可能在这个集合中出现但并不正确的密钥称为伪密钥（spuriouskey）。•一个保密系统的惟一解距离定义为使得伪密钥的期望数等于零的n的值，记为n0，即在给定的足够的计算时间下分析者能惟一地计算出密钥所需要的密文的平均量。•n0用于衡量在惟密文攻击下破译一个密码系统时，密码分析者必须处理的密文量的理论下界。•当截获的密文量大于n0时，原则上可以破译该密码。38Simmons认证系统的信息理论•内容：将信息论用于研究认证系统的理论安全性和实际安全性问题，指出认证系统的性能极限以及设计认证码所必须遵循的原则。•认证理论的主要研究目标：一是推导欺骗者欺骗成功的概率的下界；二是构造欺骗者欺骗成功的概率尽可能小的认证码。39认证系统模型•一种是无仲裁者的认证系统模型。在这种模型中，只有3种参加者，即消息的发送者、接收者和入侵者。消息的发送