第11讲公钥密码概述1

上课安排公钥密码体制的概念、思想和工作方式数论简介Diffie-Hellman密钥交换算法RSA算法EIgamal公钥算法ECC算法背景在拥有大量用户的通信网络，若想让两两用户都能进行保密通信，即要求(1)任意一对用户共享一个会话密钥(2)不同的用户对共享的会话密钥不相同对于分配中心，N个用户则需要分配CN2个会话密钥，大量的数据存储和分配是一件很麻烦的事，在计算机网络环境下显的尤为突出。另外传统密码不易实现数字签名，也进一步限制了其发展。公开密钥算法的提出公钥密码学是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见文献：W.DiffieandM.E.Hellman,NewDirectrionsinCryptography，IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654公开密钥算法公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制双钥体制的公钥可以公开，因此也称公钥算法公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了30多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作用加密与解密由不同的密钥完成加密：解密：知道加密算法，从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以作为加密密钥，而另一个用作解密密钥（不是必须的）公开密钥算法的基本要求:()KUXYYEX:()(())KRKRKUYXXDYDEX用公钥密码实现保密用户拥有自己的密钥对(KU,KR)公钥KU公开，私钥KR保密:()bKUABYEX:()(())bbbKRKRKUBDYDEXX用公钥密码实现鉴别条件：两个密钥中任何一个都可以用作加密而另外一个用作解密鉴别：鉴别＋保密:(()):(())baabKUKRKUKRABZEDXBEDZX公开密钥算法公钥算法的种类很多，具有代表性的三种密码：基于整数分解难题（IFP）的算法体制基于离散对数难题（DLP）算法体制基于椭圆曲线离散对数难题（ECDLP）的算法体制数论简介模运算费玛定理和欧拉定理中国剩余定理模运算设n是一正整数,a是整数,若a=qn+r,0≤rn,则amodn=r若(amodn)=(bmodn),称为a,b模n同余，记为a≡bmodn称与a模n同余的数的全体为a的同余类，记为[a]，a称为这个同余类的代表元素模运算同余的性质若n|(a-b)，则a≡bmodn(amodn)≡(bmodn),则a≡bmodna≡bmodn，则b≡amodna≡bmodn，b≡cmodn，则a≡cmodn求余运算amodn将a映射到集合{0,1,…,n-1},求余运算称为模运算模运算模运算的性质[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)×(bmodn)]modn=(a×b)modn例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法＋01234567001234567112345670223456701334567012445670123556701234667012345770123456×01234567000000000101234567202460246303614725404040404505274163606420642707654321模运算若x+y=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)+y]modn=[x+(w+y)]modn[(xw)y]modn=[x(wy)]modn分配律[w(x+y)]modn=[wx+wy]modn单位元单位元(0+w)modn=wmodn(1×w)modn=wmodn加法逆元：对w∈Zn,有z∈Zn，满足w+z=0modn,z为w的加法逆元，记为z=-w。加法的可约律(a+b)≡(a+c)modn,则b≡cmodn对乘法不一定成立，因为乘法逆元不一定存在。模运算定理:设a∈Zn,gcd(a,n)=1,则a在Zn有乘法逆元证明思路：用反证法证明a和Zn中任何两个不同的数相乘结果都不相同从而得出a×Zn=Zn,因此存在x∈Zn,使a×x=1modn设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律(a×b)=(a×c)modn,b=cmodn费玛定理若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp证明：gcd(a,p)=1,则a×Zp=Zp,a×(Zp-{0})=Zp-{0}{amodp,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互素,则)n（()()()(1)(1)npqpq()a1modnn欧几里德算法求两个正整数的最大公因子两个正整数互素，可以求一个数关于另一个数的乘法逆元性质:对任意非负整数a和正整数b,有gcd(a,b)=gcd(b,amodb)中国剩余定理如果已知某个数关于一些两两互素的数的同余类集，就可以重构这个数定理(中国剩余定理)：设m1,m2,…,mk是两两互素的正整数，则一次同余方程组对模M有唯一解kiimM1kkamxamxamxmodmodmod2211112212()mod1modkkkiiiiMMMxyayayaMmmmMyymm满足