公钥密码体制及典型算法-RSA

.,1,公钥密码体制及典型算法,.,2,在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个基本工具。而公钥密码体制则为密码学的发展提供了新的理论和技术基础，一方面公钥密码算法的基本工具不再是代换和置换，而是数学函数；另一方面公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。,1公钥密码体制的基本概念,.,3,公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。单钥密码体制在进行密钥分配时,要求通信双方或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。1976年W.Diffie和M.Hellman对解决上述两个问题有了突破，从而提出了公钥密码体制。,公钥密码体制的基本概念,.,4,对称密码体制的缺陷,密钥分配问题通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；密钥管理困难问题在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是非常大。n用户保密通信网，用户彼此间进行保密通信需要个密钥。n=1000：499500个密钥n=5000：12497500个密钥没有签名功能，无法实现抗抵赖问题：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。陌生人间不便进行保密通信问题,.,5,别名：公钥密码体制，双钥密码体制两个密钥：公开密钥（公钥）：可以被任何人知道,用于加密或验证签名秘密密钥（私钥）：只能被消息的接收者或签名者知道,用于解密或签名。加密或验证签名者不能解密或生成签名（已知密码算法和加密密钥，求解密密钥在计算上是不可行的）。安全性基础：基于数学难题标志性文献W.DiffieandM.E.Hellman,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654,公钥密码体制的基本概念,.,6,由私钥及其他密码信息容易计算出公开密钥(apolynomialtime(P-time)problem)由公钥及算法描述,计算私钥是难的(anNP-timeproblem)因此,公钥可以发布给其他人(wishingtocommunicatesecurelywithitsowner)密钥分配问题不是一个容易的问题(thekeydistributionproblem),公钥密码体制的基本概念,.,7,公钥算法分类,Public-KeyDistributionSchemes(PKDS，公钥分配系统)用于交换秘密信息(依赖于双方主体)常用于对称加密算法的密钥PublicKeyEncryption(PKE，公钥加密)用于加密任何消息任何人可以用公钥加密消息私钥的拥有者可以解密消息任何公钥加密方案能够用于密钥分配方案PKDS许多公钥加密方案也是数字签名方案SignatureSchemes（签名方案）用于生成对某消息的数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名,.,8,公钥密码系统可用于以下三个方面：(1)通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信。,.,9,(2)数字签名：将私钥作为加密密钥，公钥作为解密密钥，可实现由一个用户对数据加密而使多个用户解读。,.,10,(3)密钥交换：通信双方交换会话密钥，以加密通信双方后续连接所传输的信息。每次逻辑连接使用一把新的会话密钥，用完就丢弃。,.,11,公开密钥算法的特点:,（1）发送者用加密密钥PK对明文X加密后，在接收者用解密密钥SK解密，即可恢复出明文，或写为：DSK(EPK(X)X解密密钥是接收者专用的秘密密钥，对其他人都保密。此外，加密和解密的运算可以对调，即EPK(DSK(X)X（2）加密密钥是公开的，但不能用它来解密，即DPK(EPK(X)X,.,12,公开密钥算法的特点:,（3）在计算机上可以容易地产生成对的PK和SK。（4）从已知的PK实际上不可能推导出SK，即从PK到SK是“计算上不可能的”。（5）加密和解密算法都是公开的。,.,13,公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密。因此公钥密码体制也称为双钥密码体制。算法有以下重要特性：已知密码算法和加密密钥，求解密密钥在计算上是不可行的。,公钥密码体制的原理,.,14,图公钥体制加密的框图,.,15,加密过程有以下几步：要求接收消息的端系统，产生一对用来加密和解密的密钥，如图中的接收者B，产生一对密钥PKB，SKB，其中PKB是公开钥，SKB是秘密钥。端系统B将加密密钥（如图中的PKB）予以公开。另一密钥则被保密（图中的SKB）。,公钥密码体制的原理,.,16,A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKBm,其中c是密文，E是加密算法。B收到密文c后，用自己的秘密钥SKB解密，表示为m=DSKBc，其中D是解密算法。,公钥密码体制的原理,.,17,公钥密码体制认证框图,.,18,因为只有B知道SKB，所以其他人都无法对c解密。公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息m提供认证，如下图所示。用户A用自己的秘密钥SKA对m加密，表示为c=ESKAm将c发往B。B用A的公开钥PKA对c解密，表示为m=DPKAc,公钥密码体制认证的原理,.,19,因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。另一方面，任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对消息来源和消息完整性的认证。,公钥密码体制认证的原理,.,20,在实际应用中，特别是用户数目很多时，以上认证方法需要很大的存储空间，因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容。改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证符。认证符具有这样一个性质：如果保持认证符的值不变而修改文件这在计算上是不可行的。用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。,公钥密码体制认证的原理,.,21,以上认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。如下图所示。,公钥密码体制认证的原理,.,22,公钥密码体制的认证、保密框图,.,23,发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为c=EPKBESKAm解密过程为m=DPKADSKBc即收方先用自己的秘密钥,再用发方的公开钥对收到的密文两次解密。,公钥密码体制认证的原理,24,公钥保密和认证体制,.,25,公钥密码算法应满足以下要求:接收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKBm在计算上是容易的。收方B用自己的秘密钥对c解密，即m=DSKBc在计算上是容易的。,公钥密码算法应满足的要求,.,26,敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的。敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的。加、解密次序可换，即EPKBDSKB(m)=DSKBEPKB(m)其中最后一条虽然非常有用，但不是对所有的算法都作要求。,公钥密码算法应满足的要求,.,27,以上要求的本质之处在于要求一个陷门单向函数。单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像xX，且由x易于计算它的像y，由y计算它的原像x是不可行的。这里所说的易于计算是指函数值能在其输入长度的多项式时间内求出，即如果输入长n比特，则求函数值的计算时间是na的某个倍数，其中a是一固定的常数。这时称求函数值的算法属于多项式类P，否则就是不可行的。例如，函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则认为求函数值是不可行的。,公钥密码算法应满足的要求,.,28,注意这里的易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别。在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的。而在此所说的两个概念是指算法在几乎所有情况下的情形。称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成。,公钥密码算法应满足的要求,.,29,总结为：陷门单向函数是一族可逆函数fk，满足Y=fk(X)易于计算（当k和X已知时）。X=f-1k(Y)易于计算（当k和Y已知时）。X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）。因此，研究公钥密码算法就是要找出合适的陷门单向函数。,公钥密码算法应满足的要求,.,30,和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用。因此公钥密码体制目前主要用于密钥管理和数字签字。对公钥密码算法的第2种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。,对公钥密码体制的攻击,.,31,还有一种仅适用于对公钥密码算法的攻击法，称为可能字攻击。例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较。如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，这种攻击的本质是对56比特DES密钥的穷搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。,对公钥密码体制的攻击,.,32,强力攻击(对密钥)密钥不能太短，防止密钥穷举但也不能太长，以免影响速度公开密钥算法本身可能被攻破赖以安全的基石-数学难题被破解可能报文攻击(对报文本身的强力攻击)对所有可能报文加密，直到与截获密文相同,对公钥密码体制的攻击,.,33,RSA算法是1978年由罗纳德李维斯特（RonRivest）、阿迪萨莫尔（AdiShamir）和伦纳德阿德曼（LeonardAdleman）提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。RLRivest,AShamir,LAdleman,OnDigitalSignaturesandPublicKeyCryptosystems,CommunicationsoftheACM,vol21no2,pp120-126,Feb1978,2RSA算法,.,34,由Rivest,Shamir和Adleman在1978年提出数学基础:大整数因子分解的困难性，Euler定理,.,35,1.密钥的产生选两个保密的大素数p和q(各100200位十进制数字，且p不等于q)。计算n=pq，(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。随机选一整数e，满足1e(n)，且gcd(n),e)=1。计算d，满足de1mod(n),即d是e在模(n)下的乘法逆元，因e与(n)互素，由模运算可知，它的乘法逆元一定存在。d=e-1(mod(n)以e,n为公开钥,d,n为秘密钥。(p,q不再需要，可以销毁),算法描述,.,36,2.加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：cmemodn,RSA加密算法描述,.,37,3.解密对密文分组的解密运算为：mcdmodn下面证明RSA算法中解密过程的正确性。证明：由加密过程知cmemodn，所以cdmodnmedmodnm1mod(n)modnmk(n)+1modn,RSA解密算法描述,.,38,下面分两种情况：m与n互素，则由Euler定理得m(n)1modn,mk(n)1modn,mk(n)+1mmodn即cdmodnm。gcd(m,n)1，先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)1意味着m是p的倍数或q的倍数，不妨设m=cp，其中c为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与mn=pq矛盾。,.,39,由gcd(m,q)=1及Euler定理得m(q)1modq，所以mk(q)1modq,mk(q)(p)1modq,mk(n)1modq因此存在一整数r，使得mk(n)=1+rq，两边同乘以m=cp得mk(n)+1=m+rcpq=m+rcn即mk(n)+1mmodn，所以cdmodnm。(证毕),RSA解密算法证明,.,40,例：选p=7，q=17。求n=pq=119，(n)=(p-1)(q-1)=96。取e=5，满足1e(n)，且gcd(n),e)=1。确定满足de=1mod96且小于96的d，因为775=385=496+1，所以d为77，因此公开钥为5，119，秘密钥为77，119。设明文m=19，则由加密过程得密文为c195mod1192476099mod11966解密为6677mod11919,RSA解密算法证明,.,41,RSA算法实例,例假设Alice和Bob使用RSA密码体制进行全英文字符的保密通信。假设Alice选择、，Bob选择、，并采用双字母加、解密方式。（1）说明Alice和Bob建立RSA密码体制的方法。（2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。,.,42,4、RSA算法实例,例（1）说明Alice和Bob建立RSA密码体制的方法。,解Alice计算：,.,43,4、RSA算法实例,例（1）说明Alice和Bob建立RSA密码体制的方法。,解Bob计算：,.,44,4、RSA算法实例,例5-1（2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。,解Alice加密：“public”代换为数字并按双字母分组：152001110802,.,45,4、RSA算法实例,例（2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。,解Bob解密：密文“009516491410”,明文:public,.,46,1.RSA的加密与解密过程RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677mod119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(ab)modn=(amodn)(bmodn)modn就可减小中间结果。,RSA算法中的计算问题,.,47,再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bkbk-1b0，即m=bk2k+bk-12k-1+b12+b0因此,RSA算法中的计算问题,.,48,例如：19=124+023+022+121+120，所以a19=(a1)2a0)2a0)2a1)2a1从而可得以下快速指数算法：c=0;d=1；Fori=kdownto0doc=2c;d=(dd)modn;ifbi=1thenc=c+1;d=(da)modnreturnd.,RSA算法中的计算问题,.,49,其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，算法中完全可将之去掉。,RSA算法中的计算问题,.,50,例求7560mod561。将560表示为1000110000，所以7560mod561=1。,.,51,2.RSA密钥的产生产生密钥时，需要考虑两个大素数p、q的选取，以及e的选取和d的计算。因为n=pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（102002664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。,RSA密钥产生,.,52,寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。例如Miller-Rabin算法。,RSA密钥产生,.,53,可见寻找大素数是一个比较繁琐的工作。然而在RSA体制中，只有在产生新密钥时才需执行这一工作。p和q决定出后，下一个需要解决的问题是如何选取满足1eq，由(n)=(p-1)(q-1)，则有p+q=n-(n)+1以及由此可见，由p、q确定(n)和由(n)确定p、q是等价的。,RSA的安全性,.,58,为保证算法的安全性，还对p和q提出以下要求：（1）|p-q|要大由，如果|p-q|小，则也小，因此稍大于n，稍大于。可得n的如下分解步骤：顺序检查大于的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。由x2-n=y2，得n=(x+y)(x-y)。,RSA的安全性,.,59,RSA中p、q选择不当(|p-q|不大)的举例,例：n=143,目标：分解n解：,.,60,（2）p-1和q-1都应有大素因子这是因为RSA算法存在着可能的重复加密攻击法。设攻击者截获密文c，可如下进行重复加密：,RSA的安全性,.,61,RSA的安全性,.,62,设m在模n下阶为k，由得，所以k|(et-1)，即et1(modk)，t取为满足上式的最小值（为e在模k下的阶）。又当e与k互素时t|(k)。为使t大，k就应大且(k)应有大的素因子。又由k|(n)，所以为使k大，p-1和q-1都应有大的素因子。此外，研究结果表明，如果en且dn1/4，则d能被容易地确定。,RSA的安全性,.,63,RSA中P、q选择不当(p-1或q-1没有大素因子)的举例,例：p=17，q=11，e=7，则n=187。设m=123，则：C1=1237mod187=183C2=1837mod187=72C3=727mod187=30C4=307mod187=123明文m经过4次加密，恢复成明文。,.,64,RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。1.共模攻击在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。,对RSA的攻击,.,65,设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），明文消息是m，密文分别是c1me1(modn)c2me2(modn)敌手截获c1和c2后，可如下恢复m。用推广的Euclid算法求出满足re1+se2=1的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c-11，由此得(c-11)-rcs2m(modn)。,对RSA的攻击,.,66,2.低指数攻击假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。设3个用户的模数分别为ni(i=1,2,3)，当ij时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。设明文消息是m，密文分别是:c1m3(modn1)c2m3(modn2)c3m3(modn3)由中国剩余定理可求出m3(modn1n2n3)。由于m3n1n2n3，可直接由m3开立方根得到m。,.,67,另一种欺骗性的攻击RSA,.,68,思考题,1.,2.,.,69,RSA参数选择,需要选择足够大的素数p,q通常选择小的加密指数e,且与(N)互素e对所有用户可以是相同的最初建议使用e=3现在3太小常使用e=216-1=65535解密指数比较大,.,70,(1)n=pq的确定：p与q必须为强素数强素数p的条件：(a)存在两个大素数p1和p2，p1|(p1)，p2|(p1)(b)存在4个大素数r1,s1,r2及s2，使r1|(p11),r2|(p21),s1|(p11),s2|(p21)。p1和p2为二级素数；r1,r2,s1和s2为三级素数,RSA参数的选择,.,71,采用强素数的理由如下：若，pi为素数，ai为正整数分解式中piB，B为已知一个小整数则存在一种p1的分解法，使我们易于分解n令n=pq，且p1满足上述条件，piB令aai，i=1,2,t可构造显然(p1)R，由费尔马定理2R1modp令2R=xmodn，若x=1则选3代2，直到出现x1此时，kR=1modp有解的充要条件是kR=xmodn(p,n)=p|x-1由GCD(x1,n)=p，就得到n的分解因子p和q,RSA参数的选择,.,72,p与q之差要大若p与q之差很小，则可由n=pq估计(pq)/2=n1/2，由(pq)/2)2n=(pq)/2)2，等式右边为小的平方数，可以试验给出p,q的值例：n=164009，估计(pq)/2405，由4052n=16=42，可得(pq)/2=405，(pq)/2=4，p=409，q=401,RSA参数的选择,.,73,p1与q1的最大公因子要小惟密文攻击下，设破译者截获密文y=xemodn破译者做下述递推计算：xi=xi-1emodn=(xe)imodn若ei=1mod(n)，则有xi=xmodn，且ei+1=emod(n)，即xi+1=x若i小，则由此攻击法易得明文x。由Euler定理知，i=(p1)(q1)，若p1和q1的最大公因子小，则i值大，如i=(p1)(q1)/2，此攻击法难于奏效。,RSA参数的选择,.,74,p，q要足够大，以使n分解在计算上不可行,RSA参数的选择,.,75,e的选取原则(e,(n)=1条件易于满足，因为两个随机数互素的概率约为3/5e不可过小：若e小，x小，y=xemodn，当xen，则未取模，由y直接开e次方可求x，易遭低指数攻击e小时，加密速度快，Knuth和Shamir曾建议采用e=3但e太小存在一些问题选e在mod(n)中的阶数i(ei1mod(n)达到(p1)(q1)/2,p，q要足够大，以使n分解在计算上不可行,RSA参数的选择,.,76,d的选择e选定后可用Euclidean算法在多项式时间内求出dd小，签字和解密快，在IC卡中尤为重要(复杂的加密和验证签字可由主机来做)d要大于n1/4：类似于加密下的情况，d不能太小否则由已知明文攻击，构造y=xemodn，猜测d的值：做ydmodn，直到试凑出ydxmodnWiener给出对小d的系统攻击法，证明了当d长度小于n的1/4时，由连分式算法，可在多项式时间内求出d值,RSA参数的选择,.,77,不可用公共模由一密钥产生中心(KGC)采用一公共模，分发多对密钥，公布相应公钥ei这当然使密钥管理简化，存储空间小，且无重新分组问题但如前所述，它在安全上会带来问题。明文熵要尽可能地大明文熵要尽可能地大，以使在已知密文下，要猜测明文无异于完全随机等概情况。用于签字时，要采用Hash函数,RSA体制实用中的其它问题,.,78,RSA理论,RSA基于FermatsTheorem:ifN=pqwherep,qareprimes,then:X(N)=1modNforallxnotdivisiblebyporq,iegcd(x,(N)=1where(N)=(p-1)(q-1)但在RSA中，e破译该体制等价于对大整数的分解。RSA中选取的公开钥e满足1e(n)，且gcd(e,(n)=1。Rabin密码体制则取e=2。,Rabin密码体制,.,99,1.密钥的产生随机选择两个大素数p、q，满足pq3mod4，即这两个素数形式为4k+3；计算n=pq。以n作为公开钥，p、q作为秘密钥。,Rabin密钥的产生,.,100,2.加密cm2modn其中m是明文分组，c是对应的密文分组。,Rabin加密描述,.,101,3.解密解密就是求c模n的平方根，即解x2cmodn，由中国剩余定理知解该方程等价于解方程组由于pq3mod4，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即xmmodp,x-mmodpxmmodq,x-mmodq,Rabin解密描述,.,102,经过组合可得4个同余方程组由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等。,Rabin解密描述,.,103,下面证明，当pq3mod4，两个方程x2cmodp,x2cmodq的平方根都可容易地求出。由p3mod4得，p+1=4k，即1/4(p+1)是一整数。因c是模p的平方剩余，故,.,104,所以和是方程x2cmodp的两个根。同理和是方程x2cmodq的两个根。由以前知识知，求解方程x2amodn与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。,Rabin解密描述,.,105,已经说过，为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（ellipticcurvecryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景。ECC已被IEEE公钥密码标准P1363采用。,5椭圆曲线密码体制,.,106,椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：y2+axy+by=x3+cx2+dx+e(4.1)其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。,5.1椭圆曲线,.,107,椭圆曲线的两个例子,.,108,从图可见，椭圆曲线关于x轴对称。椭圆曲线上的加法运算定义如下：如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）：O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。,椭圆曲线的描述,.,109,设P1=(x,y)是椭圆曲线上的一点（如图所示），它的加法逆元定义为P2=-P1=(x,-y)。这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，还可得O=-O,椭圆曲线的描述,.,110,设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下：画一条通过Q、R的直线与椭圆曲线交于P1（这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q和P1=R）。由Q+R+P1=O得Q+R=-P1。点Q的倍数定义如下：在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，等。以上定义的加法具有加法运算的一般性质，如交换律、结合律等。,椭圆曲线的描述,.,111,密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）。其中最为常用的是由方程y2x3+ax+b(modp)(a,bGF(p),4a3+27b2(modp)0)定义的曲线。,5.2有限域上的椭圆曲线,.,112,例：p=23，a=b=1，4a3+27b2(mod23)80，方程为y2x3+x+1，其图形是连续曲线。然而我们感兴趣的是曲线在第一象限中的整数点。设Ep(a,b)表示方程(4.2)所定义的椭圆曲线上的点集(x,y)|0xp,0yp，且x,y均为整数并上无穷远点O。本例中E23(1,1)由表4.6给出，表中未给出O。,有限域上的椭圆曲线,.,113,一般来说，Ep(a,b)由以下方式产生：对每一x(0xp且x为整数），计算x3+ax+b(modp)。决定中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根（y=0时只有一个平方根）。,有限域上的椭圆曲线,.,114,Ep(a,b)上的加法定义如下：设P，QEp(a,b)，则P+O=P。如果P=(x,y)，那么(x,y)+(x,-y)=O，即(x,-y)是P的加法逆元，表示为-P。由Ep(a,b)的产生方式知，-P也是Ep(a,b)中的点，如上例，P=(13,7)E23(1,1)，-P=(13,-7)，而-7mod2316，所以-P=(13,16)，也在E23(1,1)中。,有限域上椭圆曲线的加法,.,115,设P=(x1,y1)，Q=(x2,y2)，P-Q，则P+Q=(x3,y3)由以下规则确定：x32-x1-x2(modp)y3(x1-x3)-y1(modp)其中,有限域上椭圆曲线的加法,.,116,例：仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，则所以P+Q=（17,20），仍为E23(1,1)中的点。,有限域上椭圆曲线的加法,.,117,若求2P则所以2P=(7,12)。,有限域上椭圆曲线的加法,.,118,倍点运算仍定义为重复加法，如4P=P+P+P+P。从上例看出，加法运算在E23(1,1)中是封闭的，且能验证还满足交换律。对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，所以Ep(a,b)是一个Abel群。,有限域上椭圆曲线的加法,.,119,为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，QEp(a,b)，kp，则由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。Diffie-Hellman密钥交换和ElGamal密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两种密码体制。,5.3椭圆曲线上的密码,.,120,1.Diffie-Hellman密钥交换首先取一素数p2180和两个参数a、b，则得方程(4.2)表达的椭圆曲线及其上面的点构成的Abel群Ep(a,b)。第2步，取Ep(a,b)的一个生成元G(x1,y1)，要求G的阶是一个非常大的素数，G的阶是满足nG=O的最小正整数n。Ep(a,b)和G作为公开参数。,.,121,两用户A和B之间的密钥交换如下进行：A选一小于n的整数nA，作为秘密钥，并由PA=nAG产生Ep(a,b)上的一点作为公开钥。B类似地选取自己的秘密钥nB和公开钥PB。A、B分别由K=nAPB和K=nBPA产生出双方共享的秘密钥。这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPA。攻击者若想获取K，则必须由PA和G求出nA，或由PB和G求出nB，即需要求椭圆曲线上的离散对数，因此是不可行的。,Diffie-Hellman密钥交换,.,122,Diffie-Hellman公钥分配方案,不能用于交换任意消息可以建立共享密钥(双方共享)依赖于双方的公、私钥值基于有限域上的指数问题安全性是基于计算离散对数的困难性,.,123,例：p=211，Ep(0,-4)，即椭圆曲线为y2x3-4，G=(2,2)是E211(0,-4)的阶为241的一个生成元，即241G=O。A的秘密钥取为nA=121，公开钥为PA=121(2,2)=(115,48)。B的秘密钥取为nB=203，公开钥为PB=203(2,2)=(130,203)。由此得到的共享密钥为121(130,203)=203(115,48)=(161,169)，即共享密钥是一对数。如果将这一密钥用作单钥加密的会话密钥，则可简单地取其中的一个，如取x坐标，或取x坐标的某一简单函数。,Diffie-Hellman密钥交换,.,124,Diffie-Hellman举例,选取素数p=97,及本根a=5Alice选取秘密xA=36&计算公钥yA=536=50mod97Bob选取秘密xB=58&计算公钥yB=558=44mod97AliceandBob交换公钥(50&44respectively)Alice计算公享秘密K=4436=75mod97Bob计算公享秘密K=5058=75mod97,.,125,Diffie-HellmaninPractise,两个主体每次可以选择新的秘密密钥(私钥),并计算及交换新的公钥可以抵抗被动攻击,但不能抵抗主动攻击每次可以给出新的密钥为抵抗主动攻击,需要其它新的协议也可以建立长期公钥,.,126,2.ElGamal密码体制Diffie-Hellmankeydistributionscheme的变形能够用于安全交换密钥publishedin1985byElGamal:T.ElGamal,APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms,IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.安全性是基于离散对数缺点：增加了消息长度（2倍）,ElGamal密码体制,.,127,(1)ElGamal密码体制的原理密钥产生过程：首先选择一素数p以及两个小于p的随机数g和x，计算ygxmodp。以(y,g,p)作为公开密钥，x作为秘密密钥。,ElGamal密码体制,.,128,ElGamal加密,加密过程：设欲加密明文消息M，随机选一与p-1互素的整数k，0=k=p-1计算消息密钥K:K=yBkmodp计算密文对:C=C1,C2C1gkmodp,C2ykMmodp，发送到接收者k需要永久保密,.,129,解密过程：首先计算messagekeyK计算明文:这是因为,ElGamal解密,.,130,ElGamalExample,选择p=97及本原根a=5；recipientBob选择秘密钥xB=58&计算并发布公钥yB=558=44mod97Alice要加密M=3toBob首先得到Bob的公开密钥yB=44，选择随机k=36计算:K=4436=75mod97计算密文对:C1=536=50mod97C2=75.3mod97=31mod97发送50,31toBobBob恢复messagekeyK=5058=75mod97Bob计算K-1=22mod97Bob恢复明文M=31.22=3mod97,.,131,(2)利用椭圆曲线实现ElGamal密码体制首先选取一条椭圆曲线，并得Ep(a,b)，将明文消息m通过编码嵌入到曲线上得点Pm，再对点Pm做加密变换。这里不对具体的编码方法做进一步介绍，读者可参考有关文献。取Ep(a,b)的一个生成元G，Ep(a,b)和G作为公开参数。,利用椭圆曲线实现ElGamal密码体制,.,132,用户A选nA作为秘密钥，并以PA=nAG作为公开钥。任一用户B若想向A发送消息Pm，可选取一随机正整数k，产生以下点对作为密文：Cm=kG,Pm+kPAA解密时，以密文点对中的第二个点减去用自己的秘密钥与第一个点的倍乘，即Pm+kPA-nAkG=Pm+k(nAG)-nAkG=Pm攻击者若想由Cm得到Pm，就必须知道k。而要得到k，只有通过椭圆曲线上的两个已知点G和kG，这意味着必须求椭圆曲线上的离散对数，因此不可行。,利用椭圆曲线实现ElGamal密码体制,.,133,例：取p=751，Ep(-1,188)，即椭圆曲线为y2x3-x+188,Ep(-1,188)的一个生成元是G=(0,376)，A的公开钥为PA=(201,5)。假定B已将欲发往A的消息嵌入到椭圆曲线上的点Pm=(562,201)，B选取随机数k=386，由kG=386(0,376)=(676,558)，Pm+kPA=(562，201)+386(201,5)=(385,328)，得密文为(676,558),(385,328)。,利用椭圆曲线实现ElGamal密码体制,.,134,3.椭圆曲线密码体制的优点与基于有限域上离散对数问题