第四讲公钥密码

第四讲公钥密码公钥密码的理论基础RSA公钥密码ElGamal公钥密码椭圆曲线上的M-V公钥密码4．1、公钥密码的理论基础公开钥明文密文私钥明文秘密钥秘密钥明文密文明文密钥建立大数分解问题－RSA公钥密码有限域上的离散对数问题－Elgamal公钥密码椭圆曲线上离散对数问题单向函数：计算F(m,Kp)＝c容易，但由c计算m不容易。陷门单向函数：如果已知Ks，则由c计算m是容易的。什么样的函数是单向函数？如何利用单向函数、公开钥进行加密？计算难易－－计算复杂性理论为基础公钥密码与对称钥密码的比较：公钥密码：不需共享密钥；理论基础坚实；产生数字签名;速度慢、密钥长.对称钥密码：速度快，密钥短，可作为基本单元构建各种密码工具如伪随机数产生器、Hash函数；需要实现共享密钥、密钥管理困难；没有可证明安全性；公钥密码－－有效的数字签名和密钥管理；少量数据的加密公钥常用于加密对称密钥。这样的系统称为混合密码系统。对称钥密码－－有效的大量数据加密和一些数据完整性应用。公钥密码系统的应用•三种用途：–加密/解密：–数字签名：发送方用自己的私钥签署报文，接收方用对方的公钥验证对方的签名。–密钥交换：双方协商会话密钥算法加密/解密数字签名密钥交换RSAYYYDiffie-HellmanNNYDSANYN•RonRivest,AdiShamir,LeonardAdleman•RSA的安全性基于大数分解的难度•RSA在美国申请了专利（已经过期），在其他国家没有•RSA已经成了事实上的工业标准，在美国除外4.2、RSA公钥密码(2)令n＝pq，用户公布n。计算并保密。一、RSA密码体制(Rivest-Shamir-Adelman))1)(1()(qpn)(n1))(,gcd(ne))((mod1nde(1)选择一对不同的大素数p和q，将p和q保密。(3)选取正整数e，使其满足e是公开钥。(4)计算d，满足，d是私钥。(5)加密过程为：(6)解密过程为：)(mod)(nmmEce)(mod)(nccDd当gcd(m,n)1时，因为n=pq，且p和q都是素数，所以gcd(m,n)一定为p或q，假设gcd(m,n)=p，则m一定是p的倍数，设m=cp解密过程的正确性：nmnmnmmmEmEDnteddedmod?modmod)())(())((1)(pc1qmqmod11qmqmntptqmod1,mod1)()()1(1对任意明文，当gcd(m,n)=1时，根据Euler定理，nm1nmnmnmtntmodmod1mod1)(所以存在一个整数s，使得用m=cp乘以两边，有nmmntmod1)(sqmnt1)(csnmscpqmmnt1)(例：220)123)(111()(n}252,251,,2,1,0{nZ110253mod165154253mod1653c165253mod110147m(1)p＝11,q=23,(2)n=pq=11×23=253,(3)取e=3，gcd(3,220)=1，e为公钥；(4)由扩展欧几里的算法求出3mod220的逆为d=147。(5)明文空间为对于明文m=165，则密文(6)解密过程例：,2537mod177717302537mod1520)1730(2537mod1520)1730(,2537mod1730)1520(2537mod1520)1520(2537mod15202537mod1520232626216213pp952537mod1672170117012537mod17772537mod167217772537mod)15201777(17772537mod152017772223pp模幂算法：253mod110110110110253mod110110110)110(253mod110110)110(253mod110110)))110(((253mod110110))110((253mod110)110(253mod1102222222222222222242222229222221822223622732147165253mod121253mod,6242253mod,555253mod154253mod,4187253mod,3154253mod,2165253mod220253mod,1209253mod110253mod,0,110,12222222xyxyyiyyiyyxyxiyyiyyiyyxyxiyyxyxiyx147＝128＋16＋3＝10010011模逆算法：根据扩展的欧几里得算法gcd(a,b)=sa+tb,s和t为整数tbsarbarqrrrqrrrqrrrqrrrqrrrqrrrqrbrqrrrqbabqrrbqaiiiiiitriiii223112221223444342123332311222121111),gcd(二、RSA的安全性1、RSA的安全性建立在大合数n的分解是困难的基础上，如果分解已知，则就能求出密钥d；2、如果已知，则可得到n的分解p和q；)(npqnnnqpqpnqpn),(1)(1)1)(1()(0)(1(2nxnnx所以p和q以上方程的解，此方程是容易解的。3、p和q应为安全素数或强素数。p=2p1+1的素数为安全素数，其中p1为素数。强素数是p-1、p+1都有大素因子p1、p2，并且p11，p21还有大素因子。4、e和d的选择e不能太小，应使其在模的阶最大。d应大于n的长度的1/4。6、单纯的RSA不能抵抗选择密文攻击。5、随着计算能力的不断增加和因子分解算法能力不断提高，p和q的选择越来越大。目前较安全的RSA的n一般为1024bit或2048bit。需要更多的数论和密码学知识……•攻击方法–蛮力攻击：对所有密钥都进行尝试–数学攻击：等效于对两个素数乘积(n)的因子分解•大数的因子分解是数论中的一个难题十进制数字位数近似比特数得到的数据MIPS年100332199171103651992751203981993830129428199450001304311996500因子分解的进展RSA算法的性能•速度–软件实现比DES慢100倍–硬件实现比DES慢1000倍512位768位1024位加密0.030.050.08解密0.160.480.93签名0.160.520.97验证0.020.070.084．3、ElGamal公钥密码一、离散对数问题群的阶：有限群中元素的个数。群元素的阶：乘法群中满足的最小正整数m。称为g在群中的阶。1mg1353;5343;4363;6323;23;337mod182;42;22116543213211)6,5,4,3,2,1(*7Z是乘法群，群的阶为6。循环群：群G的每一个元都是G的某一个固定元g的乘方。g称为G的生成元。1366;661535;3525;2565;6545;45;551424;24;4421654321321本原元：循环群中的生成元称为域的本原元。*pZpZ)6,5,4,3,2,1,0(7Z是域，3和5是它的本原元。有限域上的离散对数问题：给定一个素数p和Zp的一个本原元，对于找一个唯一整数使得pZ20,pnnpnmodlogn通常记为17mod15log19mod13log13mod9log32213mod92562819mod13322517mod15100272736例：已知3,7,71p求37,417,167,537,387,467,377,56787,627,197,237,547,287,47,317,457,477,277,147,27,517,587597,597497,497262524232221201918171615141312111098765432对于一般离散对数问题，没有其它有效算法，只有穷搜索，所以是指数时间的算法，是困难的…….pdmodlog加密变换：对于任意明文，秘密随机选取一个整数，密文为（2）随机选择整数，计算，是公钥，d是私钥；二、ElGamal密码体制pZ20,pddpdmodpZppZZpZm20,pkk),()mod,mod(21ccpmpckkppZZccc),(21pccmdmod)(112（1）选择大素数p，是一个本原元，p和是公开的；（3）明文空间为，密文空间为（4）解密变换：对任意密文明文为（3）用户A想秘密地发送明文M＝11给用户B，A选择一个随机数，并计算（2）用户B选择整数d＝10，作为自己的私钥，计算作为自己的公钥；解密变换的正确性：pmpmpmccppmcpcdkdkkdkddkkmodmod)(mod)()(mod,mod,mod11122121719mod2mod10pd2190,7kk,1419mod2mod71pck1719mod1711mod172pmck例：（1）选取素数p＝19，生成元；19mod1141719mod)14(17mod)(110112pccdA将（14，17）发送给B；（4）B计算三、ElGamal密码体制的安全性（书中例5.5，p＝2579较大。）1、ElGamal是基于有限域上的离散对数困难性；2、素数p至少为150位十进制数；3、p-1至少有一个大素因子。4．4、椭圆曲线上的M-V公钥密码一、有限域上的椭圆曲线64223312axaxaxyaxyaybaxxy32椭圆曲线就是方程所确定的平面曲线。经过坐标变换可转化为有限域上的椭圆曲线就是方程的系数和取值都为有限域的元素。pZpZbapbaxxy,,mod)(32ppZZyx),(pbamod027423有限域（p为大于3的素数）上的椭圆曲线的点再加上一个无穷远点所组成的集合E。是满足同余方程，其中保证有三个根PxRP+QQyll'可以在椭圆曲线上定义加法运算：对于任意点EyxQEyxP),(,),(2211elseyxyyxxifQP),(,332121QPifyaxQPifxxyyyxxyxxx12112121313212323)(可以证明：椭圆曲线E关于加法构成一个交换群。|E|表示有限域上的椭圆曲线E中的点的数目。要精确计算该值是困难的，有Hasse定理给出上界和下届。Hasse定理：ppEpp21||21（1）设p3是一个素数，E是有限域上的椭圆曲线，是椭圆曲线上的一个点，并且阶足够大，使得由生成的循环子群中离散对数问题是难解的。p和E以及都公开。椭圆曲线上的离散对数问题：设p3是一个素数，E是有限域上的椭圆曲线，设G是E的一个循环子群，二、Menezes-Vanstone公钥密码体制pZG,n1)(0ordn是G的一个生成元，求满足已知的唯一整数n。M-V公钥密码体制EpZ（2）随机选取整数d，，计算1)(0orddd是公开钥，d是保密的私钥。（3）明文空间为密文空间为ppZZppZZE加密时，对于任意明文ppZZxxx),(211)(0ordk),,(