第4讲 公钥密码体制

1第4讲公钥密码体制主要内容基本思想1数论简介2RSA算法3椭圆曲线密码体制44.1基本思想对称密钥编码所面临的难题密钥分配：通信密钥太多，管理和分发困难。数字签名和认证。密码体制上的突破Diffie&Hellman,“NewDirectioninCryptography”,1976。首次公开提出了“公开密钥密码编码学”的概念。这是一个与对称密码编码截然不同的方案。提出公开密钥的理论时，其实用性并没有又得到证明：当时还未发现满足公开密钥编码理论的算法；直到1978年，RSA算法的提出。1.背景2.基本特征加密和解密使用两个不同的密钥公钥PK：公开，用于加密，私钥SK：保密，用作解密密钥一个密钥加密的数据只能用另一个密钥解密公私钥加解密举例设若甲有一份需保密的数字商业合同发给乙签署。经过如下步骤：1.甲用乙的公钥对合同加密。2.密文从甲发送到乙。3.乙收到密文，并用自己的私钥对其解密。4.解密正确，经阅读，乙用自己的私钥对合同进行签署。5.乙用甲的公钥对已经签署的合同进行加密。6.乙将密文发给甲。7.甲用自己的私钥将已签署合同解密。8.解密正确，确认签署。3.优点密钥管理加密密钥是公开的；解密密钥需要妥善保存；在当今具有用户量大、消息发送方与接收方具有明显的信息不对称特点的应用环境中表现出了令人乐观的前景。新用户的增加只需要产生一对公共/私有密钥。数字签名和认证只有解密密钥能解密，只有正确的接收者才拥有解密密钥。缺点：公共密钥系统的主要弱点是加密和解密速度慢。实际应用中的加密方式混合加密技术对称密码体制：密钥分发困难公钥体制：加解密效率低将对称加密算法的数据处理速度和公钥算法对密钥的保密功能相结合利用对称加密算法加密传输数据利用非对称加密算法交换会话密钥4.公钥密码算法基础单向函数对于一个函数，如果对于其定义域上的任意x，都容易计算，同时，对于其值域中几乎所有的取值y，计算其逆函数都是不可行的，则函数被称为单向函数。可以提供单向函数的三大数学难题大整数分解问题（简称IFP）；离散对数问题（简称DLP）；椭圆曲线离散对数问题（简称ECDLP）。)(xf)(xf)(1yf)(xf单向陷门函数对于一个单向函数，如果其逆函数在已知某些辅助信息的情况下容易求解得出，则称该单向函数为单向陷门函数。构造公钥密码系统的关键是如何在求解某个单向函数的逆函数的NP完全问题中设置合理的“陷门”。)(xf)(1yf)(xf单向函数举例例1：y=anxn+an-1xn-1+…+a1x+a0例2：设n是两个大素数p和q的乘积，b是一个正整数，对x∈Zn，令f(x)≡xb(modn)，即f(x)等于被n除所得的余数，人们认为f(x)是一个从Zn到Zn的单向函数5.公钥算法的特点公开密钥算法设计需要有以下基本要求：加密与解密由不同的密钥完成；知道加密算法，从加密密钥得到解密密钥在计算上是不可行的；两个密钥中任何一个都可以作为加密而另一个用作解密。6.公钥密码算法除RSA算法以外，建立在不同计算问题上的其他公钥密码算法有：基于因子分解问题的Rabin算法；椭圆曲线公钥算法；基于有限域中离散对数难题的ElGamal公钥密码算法基于代数编码系统的McEliece公钥密码算法；基于“子集和”难题的Merkle-HellmanKnapsack（背包）公钥密码算法；目前被认为安全的Knapsack型公钥密码算法Chor-Rivest。Diffie-Hellman、RSA和DSA是三种最常用的公钥算法。Diffie-Hellman仅适用于密钥交换。RSA算法适用于数字签名和数据加密。DSA算法仅适用于数字签名。ECC具有发展前途，可用于密钥交换、数字签名、数据加密。4.2数论简介最大公因子：任意有限个整数的公因子中的最大一个。必然存在并且惟一，记为。最小公倍数：任意有限个整数的公倍数中的最小一个。必然存在并且惟一，记为。同余式：设n是一个正整数，如果，则称a和b模n同余，记作：，称整数n为同余模。naaa,,,21),,,gcd(21naaanaaa,,,21),,,(21naaalcmZba,nbnamodmod)(modnba1.数论相关术语加法逆元：设，如果存在满足，则称x是a的模n加法逆元。乘法逆元：设，如果存在满足，则称x是a的模n乘法逆元，记为a-1(modn)。整除：设整数a和b，如果存在整数k，使b=ak，则说b能被a整除，记作：a|b。例：3|15，-15|60nZanZx)(mod0naxnZanZx)(mod1nax+01234567001234567112345670223456701334567012445670123556701234667012345770123456*01234567000000000101234567202460246303614725404040404505274163606420642707654321例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法乘法逆元：若a属于Zn，存在x有ax=1(modn),则称a有可逆元x，若逆元存在且唯一。若a可逆，当且仅当gcd(a,n)=1每一元素均有加法逆元，但不一定有乘法逆元，逆元存在相应的消去律会满足整除性质：•对所有整数a≠0，a|0、a|a成立•对任意整数b，1|b成立•若a|b,b|c，则a|c•若a|b,a|c则对所有的整数a,b，a|(bx+cy)成立•若a|b,b|a，则a=b或-b素数(primenumber)定义：如果整数p(p1)只能被1或者它本身整除，而不能被其他整数整除，则其为素数，否则为合数。素数定理：对于充分大的x，可以用xlnx近似地表示π(x),不大于x的素数个数。在各种应用中，我们需要大的素数,如100位的素数素数是构成整数的因子，每一个整数都是由一个或几个素数的不同次幂相乘得来的。kekeepppn2121设m，n是两个整数，如果正整数d满足：(1)d整除m和n，即d|m，d|n;(2)若d’|m且d’|n，则d’|d。则称d是m与n的最大公因数，记为d=(m，n)。若(m，n)=1，则称m与n互素。互素强素数若n为整数，p,q是素数，且n=pq。当p,q满足以下特性时，称之为强素数。gcd(p-1,q-1)比较小p-1和q-1都有大的素因子，分别记作P,QP-1,Q-1都有大的素因子p+1,q+1都有大的素因子(p-1)/2,(q-1)/2都是素数2.欧拉函数欧拉函数（Euler’stotientfunction）欧拉函数φ(n)：表示小于n且与n互素(包括公因子1)的正整数的个数；欧拉函数的性质：对任意素数p，有φ(p)=p–1；对任意两个素数p、q，则对n=pq有：φ(n)=φ(pq)=φ(p)φ(q)=(p–1)(q–1)欧拉定理如a和n是互素的整数，则有：等价形式：nanmod1)(fnanmoda)+1(f欧拉定理推论：有两个素数p和q,令n=pq,对任意整数t和a(0an),有下列等式成立：atφ(n)+1=amodn其中：φ(n)=(p-1)(q-1)。3.欧几里德（Euclidean）算法一个用于计算两个整数的最大公因子的有效算法，算法依据：。描述如下：（1）输入a和b，其中，，，；（2）如果则依次完成：，否则返回a；（3）输出。时间复杂度为。Zba,0,baba0brbbabar,,modrba),gcd())((lg2nO)mod,gcd(),gcd(babba用欧几里德算法求最大公约数。求：gcd(482,1180)1180=2*482+216482=2*216+50216=4*50+1650=3*16+216=8*2+0所以gcd(482,1180)=2扩展的欧几里德算法扩展欧几里德算法是用来在已知a,b。求解一组p，q，使得p*a+q*b=Gcd(a,b)。（最大公因子是原数的线性表示）原理：Gcd(a,b)=Gcd(b,a%b)所以p*a+q*b=Gcd(a,b)=Gcd(b,a%b)=p*b+q*a%b=p*b+q*(a–a/b*b)=q*a+(p–a/b*q)*b这样它就将ab的线性组合就化简为b与a%b的线性组合。ab都在减小，当b减小到0时，我们就可以得出p=1,q=0然后递归回去就可以求出最终的p,q了扩展的欧几里德算法举例gcd(11111,12345)12345=1*11111+123411111=9*1234+51234=246*5+45=1*4+14=4*1+01=5-1*4=5-1*(1234-246*5)=247*5-1*1234=247*(11111-9*1234)-1*1234=247*11111-2224*1234=247*11111-2224*(12345-1*11111)=2471*11111-2224*123454.同余式性质（1）a≡b(modn)iffamodn=bmodn。（2）反身性：a≡a(modn)。（3）对称性：如果a≡b(modn)，则b≡a(modn)。（4）传递性：如果a≡b(modn)，b≡c(modn)，则a≡c(modn)。（5）如果a≡a1(modn)，b=b1(modn)，则a+b≡a1+b1(modn)，ab≡a1b1(modn)5.中国剩余定理公元前后的《孙子算经》中有“物不知数”问题：“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？”答为“23”。也就是求同余式组x≡2（mod3），x≡3（mod5），x≡2（mod7）（式中a≡b（modm）表示m整除a－b）的正整数解。明朝程大位用歌谣给出了该题的解法：“三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。”即解为x≡2×70＋3×21＋2×15≡233≡23(mod105）三三数之剩二，则置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五，一百六以上，以一百五减之，即得求解如下形式的同余方程组其中：，，，。)(mod)(mod)(mod2211rrmaxmaxmaxZmaii,ri11),gcd(jimmji令r个整数两两互素，是任意r个整数，则r个同余方程组（其中）模有惟一解，且该解的表达式为：其中，，,。rmmm,,,21raaa,,,21iimaxmodri1kiimM1)(mod1MyMaxriiiiiimMMiiimMymod1ri1中国剩余定理的用途之一是：给出了一种方法，使非常大的数对M的模运算转化到更小的数上来进行运算，当M为150位或150位以上的时候，这种方法非常有效。6.二次剩余定义设m是正整数，若同余式有解，则a叫做模m的平方剩余(或二次剩余)；否则a叫做模m的平方非剩余(或二次非剩余)。基于模运算，在有限域内定义了平方根关系。)(mod2max*,nzxa定理：(欧拉判别条件)设p是奇素数，，则(1)a是模p的平方剩余的充分必要条件是(2)a是模p的平方非剩余的充分必要条件是1),(pa)(mod121pap)(mod121pap21pQQnnP是素数，则设p，q是两不同奇素数，n=pq，则4)1)(1(34)1)(1(qpQqpQQQnppnＥuler准则：p是奇素数，pxiffQxppmod1,2/)1(7.勒让德符号由此定义，欧拉判别法则可以表示成如下形式：,0,1,1paappapa|若的平方非剩余是模若的平方剩余是模若定义设p是素数，定义勒让德符号如下：定理设p是奇素数