公钥密码1.0.doc

2011年 2012 学年第 一学期 密码学基础 网络工程0901-0902 开课时间：2011-08第4章公钥密码基本概念公钥密码体制是在单钥密码体制遭遇两个难题的情况下提出来的，这两个问题就是密钥分配(共享)和数字签名。公钥密码也称双钥密码体制，它将加密和解密分开处理，采用两个相关密钥，一个密钥是公开的，用于加密；另一个密钥是保密的，用于解密。公钥密码体制如教材图4-1。公钥加密算法不仅能用于加解密，还能用于对发送方的消息提供认证，如教材图4-2，图4-3。构造公钥密码时，一种称为单向函数的函数起着主要作用见教材4.2.2节描述。目前，构造既安全又实用的公钥密码算法的主要数学问题有三类，分别是（1）大数因子分解问题：对应的算法称为RSA算法（2）有限域的乘法群上的离散对数问题：对应的算法称为ELGamal算法（3）椭圆曲线有限群上的离散对数问题：对应的算法称为Ecc算法。RSA算法ELGamal算法和Ecc算法已被写入大多数国际标准算法。公钥密码的应用算法加密解密数字签名密钥交换RSA是是是椭圆曲线是是是Diffie-Hellman否否是Dss否是否RSA算法引理：若n是两个素数p和q的乘积，则(n)=(p)(q)=(p-1)(q-1)。(教材定理4-3)算法描述1.生成密钥选取大素数p和q（选定保密）计算n=pq，(n)=(p-1)(q-1)，其中(n)是n的欧拉函数值（计算公开）随机选一整数e，满足1e(n)，且(n),e)=1（选定公开）计算d，满足de1(mod(n)（计算保密）公开钥：Pk=e,n，秘密钥：Sk=d,n。2.加密准备：先将明文m数字化，然后把明文分成若干段m1m2m3.，每一个明文段的值小于n（采用二进制数，选取小于n的2的最大次幂）。也就是说，p和q为100位素数，那么m将有200位，每个消息分组mi应小于200位长。如果需要加密固定的消息分组，可以在分组中适当的填充一些0并确保该数比n小。对每一段明文mi加密，加密后的密文c由相同长度的分组ci组成。(5) 加密：明文：0min密文：cimie(mod n)3.解密解密消息时，取加密后的分组ci，并计算密文：0cn明文：micid(mod n)例1 (1)选取p=7，q=17。(2)计算n=pq=119,(n)=(p-1)(q-1)=96。(3)选取e满足1e(n),且(e,(n)=1，选择e=5。(4)确定d使de1(mod96)且d96。采用欧几里德算法计算d:96=195+1,5=51,5(-19)+96=1,5(-19)1(mod96),5-1-19(mod96)。考虑到5-1通常是5的模96逆的全体中的最小正整数，因此，5-1=96k-19,k是整数。取k=1，5-1=77,而775=385=496+1，所以d=77。得公开钥：Pk=(5,119)，秘密钥：Sk=(77,119).设明文m=19，由此加密：密文为c195mod 119 2476099mod 11966解密：原明文为6677mod 11919=m明文19195mod119=666677mod119=19密文66明文19加密解密Pk=(5,119)Sk=(77,119)例2 选取p=17，q=11。计算n=pq=1711=187,(n)=(p-1)(q-1)=1610=160。选取e=7。确定d使de1(mod160)且d160。因为（直接心算）237=161=1160+1，所以d=23。得公开钥：Pk=(7,187)，秘密钥：Sk=(23,187).输入明文m=88加密：密文为c887mod 187 894432mod 18711计算：887mod 187=(884mod 187)(882mod 187)(881mod 187) mod 187，881mod 187=88882mod 187=7744mod 187=77884mod 187=59969536 mod 187=132887mod 187=(8877132) mod 187=894432 mod 187=11解密：原明文为m=1123mod 187=79720245mod 187=88计算：1123mod 187=(111mod 187)(112mod 187)(114mod 187)(118mod 187)(118mod 187) mod 187111mod 187=11112mod 187=121114mod 187=14641 mod 187=55118mod 187=214358881 mod 187=331123mod 187=(11121553333) mod 187=79720245 mod 187=88例3(1)选取p=43，q=59，(2)计算n=pq=4359=2537,(n)=(p-1)(q-1)=4258=2436。(3)随机选取e=13，满足1e(n),且(13,2436)=1。(4)确定d使de1(mod2436)或13d1(mod2436)且d2436。现采用欧几里德算法计算d:2436=13187+5，13=52+3，5=31+2，3=21+1。回代1=3-2，2=5-3，3=13-52，5=2436-13187。所以1=3-2=3-(5-3)=2(13-52)-5=213-55=213-5(2436-13187)=93713-52436。即139371(mod2436)，13-1=937=d。得公开钥：Pk=(13,2537)，秘密钥：Sk=(937,2537).考虑明文“Public”,利用英文字母表顺序（教材表1-2）数字化明文为：152001110802(亦可先分组，后数字化)分组为：1520 0111 0802加密：密文分组为:c1152013mod 25372476099mod 25370095c2011113mod 25372476099mod 25371648c3080213mod 25372476099mod 25371410计算：011113mod 2537=(01118mod 2537)(01114mod 2537)(01111mod 2537) mod 253701111mod 2537=11101112mod 2537=(111111)mod 2537=12321mod 2537=217301114mod 2537=(21732173)mod 2537=4721929mod 2537=57201118mod 2537=(572572)mod 2537=327184mod 2537=2448011113mod 2537=(2448572111)mod 2537=155428416 mod 2537=1648密文为:c=(c1,c2,c3)=(0095,1648,1410)=009516481410解密：从略例4 教材例4-254.计算问题见教材4.3.2及例4-26为了提高指数运算的效率，计算ab（a和b是正整数）时，可以考虑按照下述方法进行：将b表示为二进制数bkbk-1.b1b0,即于是5.解密正确性证明证明:证mcd(mod n)，即证当mn时，cdm(mod n)，亦即medm(mod n)。因为de1(mod(n)，所以存在整数k使得de=k(n)+1。分两种情况考虑：当m与n互素时，由欧拉定理，m(n)1(mod n) medmk(n)+1m(mod n)。当m与n不互素时，由于mn，n=pq，p和q是素数且pq。故m必含p和q中的一个为因子，且只含其中一个为因子。设m=cp且qm。由费尔马定理mq-11(mod q) mk(n)mk(p-1)(q-1)1k(p-1)1(mod q)从而存在整数h使得mk(n)=hq+1两边同乘m，注意到m=cpmk(n)+1=hqcp+m=hcn+m mk(n)+1m(mod n)，即medm(mod n)证毕。6.引理证明证明：设n=pq，Zn=0,1,2,.,pq-1,Zn中不与n互素的数有3类：A=p,2p,.,(q-1)p,B=q,2q,.,(p-1)q,C=0,且AB=F。否则，ip=jq，