第11讲--公钥密码概述1(密码学)

1、第五章公钥密码体制,上课安排,公钥密码体制的概念、思想和工作方式数论简介Diffie-Hellman密钥交换算法RSA算法EIgamal公钥算法ECC算法,背景,在拥有大量用户的通信网络，若想让两两用户都能进行保密通信，即要求(1)任意一对用户共享一个会话密钥(2)不同的用户对共享的会话密钥不相同对于分配中心，N个用户则需要分配CN2个会话密钥，大量的数据存储和分配是一件很麻烦的事，在计算机网络环境下显的尤为突出。另外传统密码不易实现数字签名，也进一步限制了其发展。,公开密钥算法的提出,公钥密码学是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见文献：W.Diffi

2、eandM.E.Hellman,NewDirectrionsinCryptography，IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654,公开密钥算法,公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制双钥体制的公钥可以公开，因此也称公钥算法公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了30多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作用,加密与解密由不同的密钥完成加密：解密：知道加密算法，从加密密钥得到解密密钥在计算上是不可行的两个密钥中任

3、何一个都可以作为加密密钥，而另一个用作解密密钥（不是必须的）,公开密钥算法的基本要求,用公钥密码实现保密,用户拥有自己的密钥对(KU,KR)公钥KU公开，私钥KR保密,用公钥密码实现鉴别,条件：两个密钥中任何一个都可以用作加密而另外一个用作解密鉴别：鉴别保密,公开密钥算法,公钥算法的种类很多，具有代表性的三种密码：基于整数分解难题（IFP）的算法体制基于离散对数难题（DLP）算法体制基于椭圆曲线离散对数难题（ECDLP）的算法体制,数论简介,模运算费玛定理和欧拉定理中国剩余定理,模运算,设n是一正整数,a是整数,若a=qn+r,0rn,则amodn=r若(amodn)=(bmodn),称为a,

4、b模n同余，记为abmodn称与a模n同余的数的全体为a的同余类，记为a，a称为这个同余类的代表元素,模运算,同余的性质若n|(a-b)，则abmodn(amodn)(bmodn),则abmodnabmodn，则bamodnabmodn，bcmodn，则acmodn求余运算amodn将a映射到集合0,1,n-1,求余运算称为模运算,模运算,模运算的性质(amodn)+(bmodn)modn=(a+b)modn(amodn)-(bmodn)modn=(a-b)modn(amodn)(bmodn)modn=(ab)modn,例：Z8=0,1,2,3,4,5,6,7,模8加法和乘法,模运算,若x+y

5、=0modn,y为x的加法逆元。每一元素都有加法逆元若对x，有xy=1modn，称y为x的乘法逆元。在上例中，并非所有x都有乘法逆元定义Zn=0,1,.,n-1为模n的同余类集合。,Zn上模运算的性质,交换律（x+w)modn=(w+x)modn(xw)modn=(wx)modn结合律(x+w)+ymodn=x+(w+y)modn(xw)ymodn=x(wy)modn分配律w(x+y)modn=wx+wymodn,单位元,单位元(0+w)modn=wmodn(1w)modn=wmodn加法逆元：对wZn,有zZn，满足w+z=0modn,z为w的加法逆元，记为z=-w。加法的可约律(a+b)(

6、a+c)modn,则bcmodn对乘法不一定成立，因为乘法逆元不一定存在。,模运算,定理:设aZn,gcd(a,n)=1,则a在Zn有乘法逆元证明思路：用反证法证明a和Zn中任何两个不同的数相乘结果都不相同从而得出aZn=Zn,因此存在xZn,使ax=1modn设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律(ab)=(ac)modn,b=cmodn,费玛定理,若p是素数，a是正整数且gcd(a,p)=1，则ap-11modp证明：gcd(a,p)=1,则aZp=Zp,a(Zp-0)=Zp-0amodp,2amodp,(p-1)amodp=1,p-1(amodp)(2amodp)(p-1)amodp=(p-1)!modp(p-1)!ap-1=(p-1)!modp(p-1)!与p互素，所以乘法可约律，ap-1=1modp,欧拉函数与欧拉定理,欧拉函数设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为定理：若n是两个素数p和q的乘积，则欧拉定理：若a和n互素,则,欧几里德算法,求两个正整数的最大公因子两个正整数互素，可以求一个数关于另一个数的乘法逆元性质:对任意非负整数a和正整数b,有gcd(a,b)=gcd(b,amodb),中国剩余定理,如果已知某个数关于一些两两互素的数的同余类集，就可以重构这个数定理(中国剩余定