算法分析设计13_密码算法

算法设计与分析张怡婷Email:[e-mail]13.2第13章密码算法学习要点：了解信息安全的基本知识和现代密码体制掌握同余、按模计算、欧拉定理、求逆等数论基础知识了解背包密码算法掌握RSA算法的加密/解密原理和过程ch13.3章节内容:13.1信息安全和密码学13.2数论初步13.4RSA算法ch13.413.1信息安全和密码学信息安全的目标：保护信息的机密性、完整性，并具有抗否认性和可用性。ch13.5信息安全的目标：保护信息的机密性、完整性，并具有抗否认性和可用性。机密性（confidentiality）是指非授权用户不能知晓信息内容。一方面，可以进行访问控制（accesscontrol），阻止非授权用户获得机密信息；另一方面，通过加密变换使非授权用户即使得到机密信息（密文形式），也无法知晓信息内容（明文）。ch13.6信息安全的目标：保护信息的机密性、完整性，并具有抗否认性和可用性。完整性（integrity）是指维护信息的一致性，即信息在生成、传输、存储和使用过程中不发生非授权的篡改。一方面，可以通过访问控制来阻止篡改行为；另一方面，可通过消息认证（messageauthentication）来检验信息是否已经被篡改。ch13.7信息安全的目标：保护信息的机密性、完整性，并具有抗否认性和可用性。抗否认性（non-repudiation）是指确保通信双方无法事后否认曾经对信息进行的生成、签发和接收等行为。ch13.8信息安全的目标：保护信息的机密性、完整性，并具有抗否认性和可用性。可用性（availability）是指保证授权用户能方便的访问所需信息。ch13.9信息安全的目标：保护信息的机密性、完整性，并具有抗否认性和可用性。信息安全的机密性、完整性和抗否认性都依赖于密码算法：通过加密可以保护信息的机密性；通过信息摘要可以检测信息的完整性；使用数字签名可达到抗否认性的目的。密码技术是实现信息安全的核心技术，是信息安全的基础。ch13.10密码学发展大致经历三个阶段：古代加密（手工阶段）、古典密码（机械阶段）和现代密码（计算机阶段）。现代密码学主要有两个分支：密码编码学（cryptography)和密码分析学（cryptanalysis)。前者致力于建立难以攻破的安全密码体制；后者力图破译对方的密码体制。ch13.11加密E解密DC=Ek(m)（公共信道）m=Dk(C)发送方m接收方（秘密信道）kk图13-1传统保密通信机制m:明文(plaintext)C:密文(ciphertext)k:密钥(key)加密(Encryption)：对明文m进行含参数k的变换C=Ek(m)得到密文C的过程。Ek称为加密算法。解密(Decryption)：接收方接收密文后，进行逆变换m=Dk(C)，恢复明文m的过程。Dk称为解密算法。用于加密和解密的数学函数称为密码算法(cipher)。传统密码体制中，加密和解密所用的密钥是相同的，所以称为对称密码（symmetricencryption）。这种密码体制下，通信双方使用的密钥必须通过秘密信道传递，因而分发密钥成为薄弱环节。ch13.1213.1.3密码体制一个密码系统包括可能的明文、密文、密钥、加密算法和解密算法。密码系统的安全性是基于密钥的，而不是加密和解密算法自身。因此算法往往可以作为标准公布。密码体制从原理上分成两类：对称密码体制和非对称密码体制。ch13.13对称密码体制（symmetricencryption）加密E解密DC=Ek(m)（公共信道）m=Dk(C)发送方m接收方（秘密信道）kk图13-1传统保密通信机制加密和解密使用相同的密钥；从加密模式上分为序列密码和分组密码（代表:DES）两类。序列密码的工作方式：将明文逐位转换成密文。分组密码的工作方式：将明文分成固定长度的组（如：64位/组），用同一密钥和算法对每一块加密，输出也是固定长度的密文。ch13.14对称密码体制（symmetricencryption）主要问题：任意一对用户间均需有各自的密钥，n个用户共需C(n,2)个密钥，这些密钥必需在发送/接收数据之前经秘密信道完成分发。每个用户必须心记与其通信的n-1个用户的密钥。加密和解密使用相同的密钥；从加密模式上分为序列密码和分组密码（代表:DES）两类。序列密码的工作方式：将明文逐位转换成密文。分组密码的工作方式：将明文分成固定长度的组（如：64位/组），用同一密钥和算法对每一块加密，输出也是固定长度的密文。ch13.15优点：加、解密速度快。安全强度高。对称密码体制（symmetricencryption）加密和解密使用相同的密钥；从加密模式上分为序列密码和分组密码（代表:DES）两类。序列密码的工作方式：将明文逐位转换成密文。分组密码的工作方式：将明文分成固定长度的组（如：64位/组），用同一密钥和算法对每一块加密，输出也是固定长度的密文。ch13.16为解决密钥的发放与管理，WhitfieldDiffie和MartinHellman于1976发布Diffie–Hellman密钥交换协议：提出了公开密钥思想。是离散对数问题的应用（双方各自持有a、b两个秘密整数，原根g和模p公开。gabmodp=gbamodp即是双方商定的密钥。）它可以让双方在完全没有对方任何预先信息的条件下通过公共信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。ch13.17使用两个密钥：一个是公有密钥k1（任何人都可以用），一个是私有密钥k2（只有解密人可以使用）。在不知道陷门信息的情况下，加密密钥和解密密钥是不能相互算出的。也称公开密钥密码体制或双密钥密码体制。基础是NP难度问题，如背包问题和大整数分解问题。最著名的代表：RSA加密算法（安全性基于大整数分解的难度）。非对称密码体制（asymmetricencryption）任何人都可用公有密钥k1加密消息并发送给持有相应私有密钥k2的人，只有持有k2的人才能解密。——实现公共网络的保密通信。ch13.18用私有密钥k2加密的消息，任何人都可用公有密钥k1解密，并由此证明消息来自持有k2的人。——实现对消息的数字签名。使用两个密钥：一个是公有密钥k1（任何人都可以用），一个是私有密钥k2（只有解密人可以使用）。在不知道陷门信息的情况下，加密密钥和解密密钥是不能相互算出的。也称公开密钥密码体制或双密钥密码体制。基础是NP难度问题，如背包问题和大整数分解问题。最著名的代表：RSA加密算法（安全性基于大整数分解的难度）。非对称密码体制（asymmetricencryption）ch13.1913.2数论初步定理11-2费马小定理（Fermatlittle）若n是素数，则对所有整数0an，应有an-1≡1(modn)如果n是素数，则一定满足费马小定理。反之不然。Carmichael数虽然满足费马小定理，却是合数而不是素数。定理11-3有助于检测Carmichael数的合数性。定理11-3二次探测定理如果n是一个素数，且0xn，则方程x2≡1(modn)有且仅有两个解为x=1和x=n-1。ch13.20定义13-1同余设n是一个自然数，若a-b是n的倍数，则称a与b关于模n同余，记作a≡b(modn)，称b是a对模n的余数。反之，a也是b对模n的余数。a≡b(modn)等价于a(modn)=b(modn)。a(modn)=b意味着a=kn+b，k是整数。ch13.21定理13-1按模计算原理设a和b是整数，θ代表二元算术运算+、-或×，则(aθb)modn=[(amodn)θ(bmodn)]modn推论：1mod((mod))modttienenn按模计算的好处是：限制了中间结果的范围，使得可以对大数执行atmodn，而不会产生很大的中间结果。公开密钥密码算法大量使用幂的取模运算。ch13.22定义13-2欧拉(Euler)函数设n是自然数，数列1,2,...,n-1中与n互素的数的个数称为n的Euler函数，记作Φ(n)。性质13-2若p是素数，则Φ(p)=p-1。定理13-2设p和q是素数，对n=pq，有Φ(n)=Φ(p)Φ(q)=(p-1)(q-1)ch13.23定理13-3欧拉(Euler)定理对任意整数a和n互素，则aΦ(n)=1(modn)当n为素数时，Φ(n)=n-1，有an-1=1modn。——费马小定理推论13-2若0≤mn，gcd(m,n)=1，有mkΦ(n)≡1(modn)mkΦ(n)+1≡m(modn)ch13.24定义13-3设a是整数，若存在x使得ax≡1(modn)，则称a与x互逆，x是a关于模n的乘法逆元(inverse)，记做x=a-1。定理13-4求逆若gcd(a,n)=1，则一元同余方程ax≡1(modn)有唯一解为：x=aΦ(n)-1(modn)若n是素数，则进一步简化为：x=an-2(modn)由欧拉定理:若a和n互素，则aΦ(n)≡1(modn)。①因此ax≡aΦ(n)(modn)，则x=aΦ(n)-1(modn)。②若n是素数，Φ(n)=n-1，则x=an-2(modn)。ch13.2513.3背包密码算法第一个公开密钥算法。由RalphMerkel和MartinHellman开发。将NP难度问题应用于公开密钥密码学的一个开端。安全性建立在背包问题是NP完全的基础上。以难解的一般背包问题实例为公开密钥来加密明文，使用易解的背包问题为私人密钥来解密密文。难解的背包实例是由易解的背包实例变换得到的。Shamir和Zipper找到了从普通背包重构超递增背包的途径，从而攻破了这一背包密码算法。一个以NP完全问题为基础的密码算法，并不一定是绝对安全的。ch13.2613.4RSA算法第一个较完善的公开密钥算法。既能用于加密，也能用于数字签名。安全性基于大整数分解的难度。ch13.27产生一对密钥的过程（1）选择两个大素数（如200位十进制数）p和q，p≠q；（2）计算乘积n=pq，得到欧拉函数Φ(n)=(p-1)(q-1)；（3）选择随机整数e，使得gcd(e,Φ(n))=1，且0eΦ(n)；（4）计算d=e-1modΦ(n)。d为e的关于模Φ(n)的乘法逆元，满足ed=1(modΦ(n))；（5）则公开密钥为{e,n}，私人密钥为{d,n}。注意：p和q在之后的加、解密过程中不再需要，但必须保密；欧拉函数Φ(n)仅用于生成私人密钥d，之后也不再用到。ch13.28加/解密过程（若消息很长，则将消息分成小于n的明文分组。）若M是一个明文分组，C是M对应的密文：加密公式：C=Memodn；解密公式：M’=Cdmodn;证明：M’=Cdmodn=(Memodn)dmodn=Medmodn=M1+k·Φ(n)modn=Mmodn因此M’=M，从密文分组C能够解密恢复得到明文M。由于ed=1(modΦ(n))n为两个大素数p和q的乘积，M恰为p或q的可能性很小，因此认为M和n互质。由推论13-2有mkΦ(n)≡1(modn)ch13.29问题：如何从公开密钥e求得e关于模Φ(n)的逆元——私人密钥d？取余用扩展Euclid算法。如：求17关于模24的逆元24*1+17*0=2424*0+17*1=1724*1+17*(-1)=7ch13.30问题：如何从公开密钥e求得e关于模Φ(n)的逆元——私人密钥d？用扩展Euclid算法。如：求17关于模24的逆元24*1+17*0=2424*0+17*1=17取余24*1+17*(-1)=724*(-2)+17*3=3ch13.31问题：如何从公开密钥e求得e关于模Φ(n)的逆元——私人密钥d？用扩展Euclid算法。如：求17关于模24的逆元24*1+17*0=2424*0+17*1=17取余24*1+17*(-1)=724*(-2)+17*3=324*5+17*(-7)=1mod24因此-7是17