公钥加密算法和RSA

计算机信息安全第4章公钥密码学与RSA(1)加密与解密由不同的密钥完成。加密XY:Y=EKU(X)；解密YX:X=DKR(Y)=DKR(EKU(X))。(2)知道加密算法、加密密钥，得到解密密钥在计算上是不可行的。(3)两个密钥中任何一个都可以用作加密，而另一个用作解密(不是必须的)，即X=DKR(EKU(X))=EKU(DKR(X))。(1)密钥管理困难两两通信分别需用一个密钥，因此n个用户需要C(n,2)=n(n-1)/2个密钥，用户增大时,所需密钥量急增。如:n=100时，C(100,2)=4995个；n=5000时，C(5000,2)=12497500个。(2)需要约定密钥密钥要预先通过某一秘密信道进行协商，对这个信道安全性要求比正常传送消息的信道安全性要高。(3)数字签名问题传统加密算法无法实现抗抵赖的需求。对称算法的不足应用范围：(1)加密/解密；(2)数字签名(身份鉴别)；(3)密钥交换。•涉及各方：发送方、接收方、攻击者。•涉及数据：公钥、私钥、明文、密文。•公钥算法应满足的条件：–产生密钥对在计算上是可行的；–已知公钥和明文，产生密文在计算上是可行的；–接收方利用私钥来解密密文在计算上是可行的；–对于攻击者，利用公钥来推断私钥在计算上是不可行的；–已知公钥和密文，恢复明文在计算上是不可行的；–(可选)加密和解密的顺序可交换。对公钥密码的要求公钥密码体制的应用单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fk1(x)是容易的；(2)给定y,计算x使x=fk1-1(y)是不可行的；(3)存在k2，已知k2时，对给定的任何y，若相应的x存在，则计算x使fk21(y)是容易的。•大整数分解问题（TheIntegerFactorizationProblem,RSA体制）。•离散对数问题有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem,ElGamal体制）。•定义在有限域的椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,类似ElGamal体制）。•1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布。•RSA是一种分组加密算法，明文和密文在0~n-1之间，n是一个正整数。•应用最广泛的公钥密码算法。•只在美国申请专利，已于2000年9月到期。•分组大小为k比特,2kn2k+1。•公开密钥{n,e}，其中n为两个素数p和q的乘积(推荐p、q等长),e与(p-1)(q-1)互素,且满足ed1(mod(p-1)(q-1))。•私有密钥{n,d}，d满ed1(mod(p-1)(q-1))，即d与e关于模(p-1)(q-1))互逆。•加密算法cmemodn，这里m为明文、n与e为加密密钥。•解密算法mcdmodn，这里c为密文、n与d为解密密钥。公钥密码RSA的理论基础是大素数相乘和因子分解可以被看成一个单向函数。•用户Alice产生两个大素数p和q，pq。•Alice计算n=pq，n的Euler数(n)=(p-1)(q-1)。•Alice选择随机数e，(0e(n))，使gcd(e,(n))=1。•Alice使用Euclidean算法计算de1mod(n)。•Alice使用RSA时的公开密钥为KU={n,e}，秘密密钥为KR={n,d}。•RSA的公开密钥为KU={n,e}，秘密密钥为KR={n,d}。•选好这些参数后，将明文划分成块，使每个明文报文P长度m满足0mn。•加密P时，计算CPemodn。•解密C时，计算PCdmodn。•由于模运算的对称性，可以证明，在确定的范围内，加密函数和解密函数是互逆的。RSA公开加解密体制•RSA的公开密钥为KU={n,e}，秘密密钥为KR={n,d}。•选好这些参数后，将明文划分成块，使得每个明文报文x长度m满足0mn。•签名P时，计算y=Sig(x)=xd(modn)。•验证签名时，计算x′＝ye(modn)?=x。RSA公钥密码的正确性RSA签名Fermat定理p是素数，a是整数且不能被p整除，则ap1≡1modp。Fermat定理推论p素数，a是任意整数，则ap≡amodp。Euler定理若a与n为互素的正整数,则a(n)≡1modn。Euler定理推论1若n=pq，p≠q都是素数，k是任意整数，则m(p-1)(q-1)+1≡mmodn，对任意0mn。Euler定理推论2mk(p-1)(q-1)+1≡mmodn,对任意0mn。因为ed1mod(n),那么存在一个k使ed=1+k(n)。故RSA应用实例步骤1.随机选择二个互不相同的素数；(一般采用概率测试算法)如p=17，q=11；步骤2.计算模数n=pq=17×11=187；步骤3.计算Euler数(n)=(p–1)(q–1)=16×10=160;步骤4.随机选择一个满足gcd(e,(n))=1的参数e；选择e=7，满足gcd(e,160)=1；步骤5.确定满足de1mod(n)的参数值d；(采用欧几里德算法)本例中(e,160)=(7,160)=1由于160=22×7+6，7=1×6+17=1×(160–22×7)+1=1×160–22×7+1,即–1×160+23×7=1所以23×71mod160，得d=23满足d160且de1mod160。步骤6.公开密钥KU={187,7}；步骤7.秘密密钥KR={187,23}。通过以上计算，已建立起RSA应用实例。对任意整数a,b,k，gcd(a,b)=gcd(b,a+kb)=gcd(b,amodb)例如gcd(55,22)=gcd(22,55mod22)=gcd(22,11)=11Eclid算法求最大公约数(d,f)。假定df0，则Step1.X←d,Y←f；Step2.ifY=0thenreturnX=gcd(d,f)；Step3.R←XmodY；Step4.X←Y；Step5.Y←R；Step6.转Step2。上述的循环最多进行2×log2(max(f,d))次。实例ExtEclid(d,f)：求最大共约数或模逆,假定df0。1.(X1,X2,X3)←(1,0,f)，(Y1,Y2,Y3)←(0,1,d)；2.ifY3=0thenreturnX3=gcd(d,f),noinverse；3.ifY3=1thenreturnY3=gcd(d,f)，Y2=d-1modf；4.Q←(X3/Y3)的整数部分；5.(T1,T2,T3)←(X1QY1,X2QY2,X3QY3)；6.(X1,X2,X3)←(Y1,Y2,Y3)；7.(Y1,Y2,Y3)(T1,T2,T3)；8.goto2。fX1+dX2=X3，fY1+dY2=Y3；若Y3=1，则fY1+dY2=1dY2=(Y1)f+1dY2≡1modfY2=d1ModfRSA加解密实例针对上述RSA应用实例，若给定明文消息M=88(88187)，则(1)加密M的计算过程为C887mod187[(881mod187)(882mod187)(884mod187)]mod187由于(881mod187)88(882mod187)[(881mod187)(881mod187)]mod1877744mod187=77(884mod187)=[(882mod187)(882mod187)]mod187=5929mod187=132所以C=887mod187=(8877132)mod187=894432mod187=11；(2)解密C的计算过程为M=1123mod187=[(111mod187)(112mod187)(114mod187)(118mod187)(118mod187)]mod187=(11121553333)mod187=79720245mod187=88。模乘性质(abmodn)=[(amodn)(bmodn)]modn。计算a16=aaaaaaaaaaaaaaaa，采用一般方法需15次乘法，若计算a2、a4、a8、a16，则只需4次乘法。90年代大数分解的进程RSA的安全性是基于加密函数ek(x)=xe(modn)是一个单向函数，所以,对攻击者来说,求逆计算不可行。RSA安全性依据对RSA实现的攻击对RSA的具体实现存在一些攻击方法，但不是对基本算法的，而是针对协议的。–对RSA的选择密文攻击；–对RSA的公共模攻击；–对RSA的小加密指数攻击；–对RSA的小解密指数攻击；–时间性攻击：取决于解密算法的运算时间。RSA-155的分解1999年8月22日，荷兰H.Riele领导的来自6个国家的研究人员组成的团队,用了5个月时间（计算机时间估计为8000mipsyears）找到了一个512-bitRSA密钥n的一个素因子。•用户拥有自己的密钥对(KU,KR)。•公钥KU公开，私钥KR保密。•AB:Y=EKUb(X)。•B:DKRb(Y)=DKRb(EKUb(X))=X。•条件两个密钥中任何一个都可以用作加密而另一个用作解密。•鉴别AALL：Y=DKRa(X)；ALL：EKUa(Y)=EKUa(DKRa(X))=X。•鉴别+保密AB：Z=EKUb(DKRa(X))；B：EKUa(DKRb(Z))=X。END