第4章 公钥密码体制

第4章公钥密码体制主要内容公钥密码体制的产生数论基础公钥密码体制的基本原理RSA公钥密码体制其它公钥密码算法传统密码体制在应用中的缺陷密钥管理的麻烦密钥难以传输不能提供法律证据缺乏自动检测密钥泄密的能力整除定理：设整数a和b，如果存在整数k，使b=ak，则说b能被a整除，记作：a|b例：3|15，-15|60性质：对所有整数a≠0，a|0、a|a成立对任意整数b，1|b成立素数(primenumber)定义：如果整数p(p1)只能被1或者它本身整除，而不能被其他整数整除，则其为素数，否则为合数。素数定理：在各种应用中，我们需要大的素数,如100位的素数素数是构成整数的因子，每一个整数都是由一个或几个素数的不同次幂相乘得来的。(),()(),,1lnlnxxxxxxxxx设是小于的素数的个数则且当最大公约数a和b的最大公约数是能够同时整除a和b的最大正整数，记为gcd(a,b)。如果gcd(a,b)=1，则说a和b是互素的。定理：设a和b是两个整数(至少一个非0)，d=gcd(a,b)，则存在整数x和y，使得ax+by=d特殊地，如果a和b互素，则有整数x和y，使得ax+by=1同余设整数a，b，n(n≠0)，如果a-b是n的整数倍，则a≡b(modn)，即a同余于b模n。也可理解为a/n的余数等于b/n的余数。(modn)运算将所有的整数(无论小于n还是大于n)，都映射到{0,1,…,n-1}组成的集合。模算术的性质：(amodn)+(bmodn)=(a+b)modn(amodn)-(bmodn)=(a-b)modn(amodn)*(bmodn)=(a*b)modn性质有整数a，b，c，n(n≠0)：如果a≡b(modn)，b≡c(modn)那么a≡c(modn)如果a≡b(modn)，c≡d(modn)那么a+c≡b+d，a-c≡b-d，ac≡bd(modn)计算117mod13计算21234mod789指数运算的优化启示：如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此12012222kkkbbbbbmaaaaaa例如：23=1×24+0×23+1×22+1×21+1×20a23=?快速指数算法：(给定a,m)d=1；Fori=kDownto0DO{d=(d×d)modn;ifbi=1then{d=(d×a)modn}}returnd.算法验证：例如求7560mod561。将560表示为1000110000迭代指数中间值(1248173570140280560）算法的中间结果(749157526……671)所以7560mod561=1。除法设整数a，b，c，n(n≠0)，且gcd(a,n)=1。如果ab≡ac(modn)，那么b≡c(modn)证明：∵gcd(a,n)=1，∴有x和y，使ax+ny=1两边同乘以(b-c):(b-c)(ax+ny)=b-c即:(ab-ac)x+n(b-c)y=b-c……①∵ab≡ac(modn),即ab=ac+k1n,∴ab-ac是n的倍数同时，n(b-c)y显然也是n的倍数所以，:(ab-ac)x+n(b-c)y也是n的倍数，假设是k2倍则①式变为：b-c=k2n即b≡c(modn)欧几里德算法(Euclid)用欧几里德算法求最大公约数。求：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乘法逆元如果gcd(a,b)=1，那么：存在a-1，使a*a-1≡1modb存在b-1，使b*b-1≡1moda这里，把a-1称为a模b的乘法逆元，b-1称为b模a的乘法逆元用扩展的欧几里德算法求乘法逆元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*12345费尔马小定理(Fermat)如果p是一个素数,a不是p的倍数，则：ap-1≡1(modp)证明：设有一整数空间S={1,2,…,p-1}再设有一函数Ψ(x)=ax(modp)x∈S(1)对于任何x∈S，有Ψ(x)∈S(2)对于x和y(x≠y),有Ψ(x)≠Ψ(y)(3)根据乘法定理和除法定理(p-1)!ap-1≡(p-1)!modp欧拉函数Ф(n)：小于n且与n互素的正整数的个数显然，对于素数p，有Ф(p)=p-1设有两个素数p和q，p≠q，那么对于n=pq，有：Ф(n)=Ф(pq)=Ф(p)*Ф(q)=(p-1)*(q-1)欧拉定理(Euler)对于任意互素的a和n，有aФ(n)≡1modn证明：对于整数n，与n互素的数有Ф(n)个：令这些数为：R={x1,x2,…,xФ(n)}用a与R中的每个元素相乘模n，得到集合S：S={ax1modn,x2modn,…,xФ(n)modn}其实S就是R：(ax1modn)RS中的元素是唯一的那么：R中各元素相乘就等于S中各元素相乘：∈()()11modnniiiixaxn离散对数由Euler定理可知，互素的a和n，有aФ(n)≡1modn也就是说，至少存在一个整数m，使am≡1modn成立使得成立am≡1modn的最小正幂m，称为a的阶、a所属的模n的指数，或a所产生的周期长。本原根：如果使得am≡1modn成立的最小正幂m：m=Ф(n)，则称a是n的本原根。指标某素数p，有本原根a，且：X1=a1modp，X2=a2modp，…，Xp-1=ap-1modp，则：x1≠x2≠…≠xp-1令：S={x1,x2,…,xp-1}，T={1,2,…,p-1}则：S=P对于任意整数b，有b≡rmodp(0≤r≤p-1)所以，对于b和素数p的本原根a，有唯一的幂i，使得：b≡aimodp，0≤i≤p-1指数i称为a模p的b的指标，记为inda,p(b)指标的性质inda,p(1)=?inda,p(a)=?乘法性质幂性质离散对数的计算对于方程y=gxmodp给定g,x,p,计算y比较容易。但给定y,g,p,求x非常困难。X=indg,p(y)其难度与RSA中因子分解素数之积的难度有相同的数量级。公钥密码体制(Publickeysystem)公钥密码学与其他密码学完全不同：公钥算法基于数学函数而不是基于替换和置换使用两个独立的密钥公钥密码学的提出是为了解决两个问题：密钥的分配数字签名1976年Diffie和Hellman首次公开提出了公钥密码学的概念，被认为是一个惊人的成就。公钥密码体制的原理公钥体制(Publickeysystem)(Diffie和Hellman,1976)每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。主要特点：加密和解密能力分开多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。公钥密码体制有4个组成部分明文：算法的输入，它们是可读信息或数据，用M表示；密文：算法的输出。依赖于明文和密钥，对给定的消息，不同的密钥产生密文不同。用E表示；公钥和私钥：算法的输入。这对密钥中一个用于加密，为Ke，此密钥公开；一个用于解密，为Kd，此密钥保密。加密算法执行的变换依赖于密钥；加密、解密算法公钥密码体制下的秘密通信公钥加密体制的特点加密和解密能力分开多个用户加密的消息只能由一个用户解读，可用于公共网络中实现保密通信用私钥加密的消息可以用对应的公钥解密，所以由一个用户加密消息而使多个用户可以解读，可用于认证系统中对消息进行数字签字无需事先分配密钥密钥持有量大大减少提供了对称密码技术无法或很难提供的服务：如与哈希函数联合运用可生成数字签名，可证明的安全伪随机数发生器的构造，零知识证明等保证机密性MEKbeE(M,Kbe)DKbdMKbe：Bob的公钥Kbd：Bob的私钥保证真实性Kad：Alice的私钥Kae：Alice的公钥MEKadE(M,Kad)DKaeM既保证机密性又保证真实性Kad：Alice的私钥Kae：Alice的公钥MEKbeE(C1,Kbe)DKbdMEKadC1=E(M,Kad)C1DKaeKbe：Bob的公钥Kbd：Bob的私钥公钥密码应满足的要求接收方B产生密钥对在计算上是容易的发送方A用收方的公开钥对消息m加密以产生密文c在计算上是容易的。收方B用自己的秘密钥对密文c解密在计算上是容易的。敌手由密文c和B的公开密钥恢复明文在计算上是不可行的。敌手由密文c和B的公开密钥恢复秘密密钥在计算上是不可行的加解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB(m)],不是对任何算法都做此要求。对公钥密码体制的攻击和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用。因此公钥密码体制目前主要用于密钥管理和数字签字。对公钥密码算法的第2种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。RSA算法RSAAlgorithm概况MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman[Rivest等1978,1979]发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。算法原理RSA算法使用了乘方运算。要求：明文M经过加密得到密文C：C=Memodn密文C经过解密得到明文M：Cdmodn=(Memodn)dmodn=Medmodn=M即：必须存在e，d，n，使Medmodn=M成立如何确定e,d,n确定n：独立地选取两大素数p和q(各100～200位十进制数字)计算n=p×q，其欧拉函数值(n)=(p－1)(q－1)确定e：随机选一整数e，1e(n)，gcd((n),e)=1确定d：根据ed=1mod(n)在模(n)下，计算d这样确定的e,d,n是否能使Medmodn=M成立呢？因为ed=1mod(n)即ed=k(n)+1所以：Med=Mk(n)+1如果M和n互素，即gcd(M,n)=1那么，根据欧拉定理(如果gcd(a,n)=1，则aФ(n)≡1modn)：有：M(n)≡1modn所以：Med≡Mk(n)+1≡M[M(n)]kmodn≡M[1]kmodn≡Mmodn如果M和n不互素，即gcd(M,n)≠1，即M和n有大于1的公约数。因为n=pq，而p、q都是素数，不可再分解，所以M一定包含了p或q为因子。又因为Mn，所以M不可能既是p的倍数又是q的倍数。不妨设M是p的倍数，M=cp。由于M不是q的倍数，所以gcd(M,q)=1，则M(q)≡1modq，所以：[M(q)](p)≡1mod