6、第六讲 公钥密码

计算机安全保密第六讲公钥密码武汉大学计算机学院2第六讲公钥密码RSA背包算法ElGamalECC3公钥密码体制的概念加密密钥与解密密钥不同，且由其中一个不容易得到另一个，则这种密码系统是非对称密钥系统。往往其中一个密钥是公开的，另一个是保密的。因此，相应的密码体制叫公开密钥密码体制。4W.Diffie和M.Hellman1976年在IEEETrans.onInformation刊物上发表了“NewDirectioninCryptography”文章，提出了“公开密钥密码体制”的概念，开创了密码学研究的新方向。5在公开密钥密码体制中，加密密钥是公开的，解密密钥是保密的，加/解密算法都是公开的。公开密钥密码体制的主要算法有RSA、背包算法、Elgamal、Rabin、DH等。6公钥体制加/解密模型加密(E)解密(D)发送M接收MKeKd密文C=E(M,Ke)7公开密钥密码的基本工作方式设M为明文，C为密文，E为公开密钥密码的加密算法，D为解密算法，Ke为公开的加密钥，Kd为保密的解密钥，每个用户都分配一对密钥，而且将所有用户的公开的加密钥Ke存入共享的密钥库PKDB。AKeABKeBPKDB8用Ke对明文加密后，再用Kd解密，即可恢复出明文，即M=DKd{EKe(M)}加密和解密运算可以对调，即M=DKd{EKe(M)}=EKe{DKd(M)}9在计算上很容易产生密钥对Ke和Kd已知Ke是不能推导出Kd的，或者说从Ke得到Kd是“计算上不可能的”。10比较对称密码（对称分组密码）与非对称密码（公钥密码）相同点都可以进行加密和解密都可以由硬件或者软件实现安全强度都由密钥的长度决定11对称密码与公钥密码区别公钥密码的安全性是基于某些公开的数学难题，而对称密码的安全性主要基于难以寻找规律的混杂公钥密码的密钥长度可以根据需求灵活的调整，而对称密码的密钥长度是在设计是就已经被固定了公钥密码可以方便实现数字签名功能，而对称密码基本上不能公钥密码算法很慢，对称密码快（约1000倍）对称密码公钥密码一般要求：1、加密解密用相同的密钥2、收发双方必须共享密钥安全性要求：1、密钥必须保密2、没有密钥，解密不可行3、知道算法和若干密文不足以确定密钥一般要求：1、加密解密算法不相同，但使用不同的密钥2、发送方拥有加密或解密密钥，而接收方拥有另一个密钥安全性要求：1、两个密钥之一必须保密2、无解密密钥，解密不可行3、知道算法和其中一个密钥以及若干密文不能确定另一个密钥13混合加密方法对称密钥密码算法的特点是算法简单，加/解密运算速度快；但其密钥管理复杂，不便于数字签名。而公开密钥密码算法的特点是密钥管理简单，便于数字签名；但算法的理论复杂，加/解密运算速度慢。两者的优缺点互补。14因此，在实际应用中，公开密钥密码系统并没有完全取代对称密钥密码系统。而是采用对称密钥加密方法与公开密钥加密方法相结合(混合)的方式，如下图所示。15加密后的对称密钥明文明文对称密钥加密(对称算法)加密(公钥算法)对称密钥解密(对称算法)解密(公钥算法)B的公钥B的私钥密文两种密码体制的混合应用16这种混合加密方式的原理是：在发送端先使用DES或IDEA对称算法加密数据，然后使用公开算法RSA加密前者的对称密钥；到接收端，先使用RSA算法解密出对称密钥，再用对称密钥解密被加密的数据。要加密的数据量通常很大，但因对称算法对每个分组的处理仅需很短的时间就可完成，因此对大量数据的加密/解密不会影响效率（若使用DES加密芯片，则速度会更快）；17用RSA算法将对称密钥加密后就可公开了，而RSA的加密密钥也可以公开，整个系统需保密的只有少量RSA算法的解密密钥，因此这些密钥在网络中就很容易被分配和传输了；又因为对称密钥的数据量很少(64/128位)，RSA只需对其做1~2个分组的加密/解密即可，也不会影响系统效率的。因此，使用这种混合加密方式既可以体现对称算法速度快的优势，也可发挥公钥算法密钥管理方便的优势，二者各取其优，扬长避短。18公开密钥密码的基本工作方式1、确保数据秘密性：发方：①A首先查PKDB，查到B的公开的加密钥KeB。②A用KeB加密M得到C：C=E（M，KeB）③A发C给B。收方：①B接受C。②B用自己的KdB解密，得到明文M=D(C，KdB)。19公开密钥密码的基本工作方式1、确保数据秘密性：安全性分析：①只有B才有KdB，因此只有B才能解密，所以确保了秘密性。②任何人都可查PKDB得到A的KeA，所以任何人都可冒充A给B发送数据。不能确保真实性。20公开密钥密码的基本工作方式2、确保数据真实性：发方：①A首先用自己的KdA对M解密，得到C=D(M，KdA)。②A发C给B。收方：①B接受C。②B查PKDB查到A的公开的加密钥KeA。③B用KeA加密C，得到明文M=E（C，KeA）。21公开密钥密码的基本工作方式2、确保数据秘密性：安全性分析：①只有A才有KdA，因此只有A才能解密产生C，所以确保了真实性。②任何人都可查PKDB得到A的KeA，所以任何人都可加密得到明文。不能确保秘密性。22公开密钥密码的基本工作方式3、同时确保数据秘密性和真实性：发方：①A首先用自己的KdA对M解密，得到S：S=D(M，KdA)②查PKDB，查到B的公开的加密钥KeB。③用KeB加密S得到C：C=E（S，KeB）④A发C给B。23公开密钥密码的基本工作方式3、同时确保数据秘密性和真实性：收方：①B接受C。②B用自己的KdB解密C，得到S：S=D（C，KdB）③B查PKDB查到A的公开的加密钥KeA。④B用A的公开的加密钥KeA加密S，得到M：M=E（S，KeA）24公开密钥密码的基本工作方式3、同时确保数据秘密性和真实性：安全性分析：①只有A才有KdA，因此只有A才能解密产生S，所以确保了真实性。②只有B才有KdB，因此只有B才能获得明文，所以确保了秘密性。25背包算法背包问题:已知M1,M2,…,Mn和S,求b1,b2,…,bn,bi{0,1},使S=b1M1+b2M2+…+bnMn背包算法的思想:明文作为背包问题的解,对应于bi,密文为重量和。算法的关键：两个背包问题超递增序列：其中每个元素都大于前面所有元素的和超递增背包：重量列表为一个超递增序列26超递增背包的解法：对于i=n,n-1,…,1bi=0当1当秘密密钥：超递增背包问题的重量序列公开密钥：有相同解的一个一般背包问题的重量序列从秘密密钥建立公开密钥：选择一个超递增序列作为秘密密钥，如：{2，3，6，13，27，52}；将其中每个值都乘以一个数n，对m求余，例如：n=31,m=105；得到的序列作为公开密钥：{62，93，81，88，102，37}。()sjjijinMbM1()sjjijinMbM127数论基础(1)模运算若a=b+kn对某些整数k成立则ab(modn)称b为a模n的余数，或a与b是模n的同余28数论基础(1)模运算若a≡0(modn),则n|a;a≡b(modn)等价于a与b分别用n去除,余数相同.称b为a模n的余数，或a与b是模n的同余29数论基础(1)模运算反身性a≡a(modm)对称性若a≡b(modm)则b≡a(modm)传递性如果a≡b(modm)，b≡c(modm),那么a≡c(modm)线性运算如果a≡b(modm)，c≡d(modm),那么(1)a±c≡b±d(modm)，(2)a*c≡b*d(modm)30加密：将明文分成长度与背包序列相同的块，计算背包总重量。例如：背包{62，93，81，88，102，37}，明文011000，密文为：93+81=174解密：先计算n-1，为n关于模m的乘法逆元。将密文的值与n-1模m相乘用秘密的背包求解，得到明文例：n=31,m=105,n-1=61,174*61mod105=9=3+6,明文为011000实际实现安全性31RSA1976年由三名美国MIT科学家Rivest,shamir和Adelman提出的一种著名的公开密钥密码算法(以该三位姓氏的第一个字母命名)依赖数学难题：IFP(IntegerFactorizationProblem)32经过多年的分析研究,在众多的公钥体制中，RSA倍受推崇，已被ISO/TC97的数据加密技术分委员会SC20推荐为公钥数据加密标准。RSA算法是建立在素数理论(Euler函数和欧几里德定理)基础上的算法。33数论基础(1)模运算若a=b+kn对某些整数k成立则ab(modn)称b为a模n的余数，或a与b是模n的同余34(2)素数一个只能被1和它本身整除的正整数。如以下各数为素数：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47，53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,…,2521,2365347734339,2756839-1等都是素数。35(3)两数互素两个数的最大公因子为1，则两数互素。gcd(a,n)=1a和n互素15与28互素，13与500互素，而15与27不是互素一个素数与它的倍数以外的任何其它数都是互素的36(4)欧拉定理设a,m∈N,(a,m)=1,则aφ(m)≡1(modm)对正整数n，欧拉函数是少于或等于n的数中与n互素的数的数目；如果m是素数,φ(m)=m-1；否则φ(m=q1r1*q2r2*...*qiri)=m(1-1/q1)(1-1/q2)...(1-1/qi))推论:费马小定理:若p为质数，则ap≡a(modp)即a(p-1)≡1(modp)37(5)因子分解对于一个数进行因子分解，就是找出其各个素数因子，如：15=35，80=22225，252601=4161101等。在数论中，因子分解是一个古老的问题。分解一个数很简单，但其过程很费时。目前最好的因子分解算法有：38数域筛选法：对大于110位字长的数，数域筛选法是已知的最快的因子分解算法。当它最初被提出时，还不算实用，但随着后来的一系列改进，成为新的一种因子分解实用算法。二次筛选法：对于低于110位的十进制数，二次筛选法是已知的最快算法，且已得到广泛应用。该算法最快的版本叫多重多项式二次筛选的双重大素数算法。39椭圆曲线法：该算法曾用于寻找43位长数字的因子，对于更大的数是无用的。此外，还有蒙特卡罗算法、连分式算法、试除法等因子分解算法。40由数论知识可知，将一个具有大素数因子的合数进行分解是很困难的，或者说这个计算量是令人望而生畏的。RSA正是建立在这个理论基础之上的。RSA算法的加密密钥Ke是公开的，而解密密钥Kd是保密的。三、RSA公开密钥密码1、加解密算法①随机地选择两个大素数p和q，而且保密；②计算n=pq，将n公开；③计算φ(n)=(p-1)(q-1)，对φ(n)保密；④随机地选取一个正整数e，1eφ(n)且（e，φ(n)）=1，将e公开；⑤根据ed＝1modφ(n)，求出d，并对d保密；⑥加密运算：C＝Memodn⑦解密运算：M＝Cdmodn三、RSA公开密钥密码2、算法论证①E和D的可逆性要证明：D(E(M))=MM＝Cd＝(Me)d＝Medmodn因为ed＝1modφ(n)，这说明ed＝tφ(n)+1,其中t为某整数。所以，Med＝Mtφ(n)+1modn。因此要证明Med＝Mmodn，只需证明Mtφ(n)+1＝Mmodn。三、RSA公开密钥密码2、算法论证①E和D的可逆性在（M，n）＝1的情况下，根据数论(Euler定理)，Mtφ(n)＝1modn，于是有，Mtφ(n)+1＝Mmodn。三、RSA公开密钥密码2、算法论证①E和D的可逆性在（M，n）≠1的情况下，分两种情况：第一种情况：M∈{1,2,3,…,n-1}因为n=pq，p和q为素数，M∈{1,2,3,…,n-1}，且（M，n）≠1。这说明