Lecture06_公钥密码体制

1、l学习要点：学习要点：了解非对称密码体制的提出背景、基本思想了解非对称密码体制的提出背景、基本思想了解非对称密码体制的基本应用方向了解非对称密码体制的基本应用方向掌握三种典型的公钥密码体制掌握三种典型的公钥密码体制l DH密钥交换算法密钥交换算法lRSAlECCl问题的提出：问题的提出： l密钥管理困难密钥管理困难传统密钥管理两两分别用一对密钥时，则传统密钥管理两两分别用一对密钥时，则n 个用户个用户需要需要C( n, 2) = n( n- 1)/ 2 个密钥，当用户量增大时，个密钥，当用户量增大时，密钥空间急剧增大密钥空间急剧增大。如。如:n= 100 时时C( 100,2)= 4,950n

2、= 5000 时时C( 5000,2)= 12,497,500l陌生人间的保密通信问题陌生人间的保密通信问题 l数字签名的问题数字签名的问题传统加密算法无法实现抗抵赖的需求传统加密算法无法实现抗抵赖的需求l公钥密码又称为双钥密码、非对称密码公钥密码又称为双钥密码、非对称密码l公钥密码体制提出的标志性文献：公钥密码体制提出的标志性文献：W.Diffie and M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654

3、（1）参与方）参与方B容易通过计算产生一对密钥（公开密钥容易通过计算产生一对密钥（公开密钥KUb和私和私有密钥有密钥KRb）。）。（2）在知道公开密钥和待加密报文）在知道公开密钥和待加密报文M的情况下，对于发送方的情况下，对于发送方A，很容易通过计算产生对应的密文：很容易通过计算产生对应的密文：CEKUb（M）（3）接收方）接收方B使用私有密钥容易通过计算解密所得的密文以便使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：恢复原来的报文：MDKRb（C）DKRb（EKUb（M）（4）敌对方即使知道公开密钥）敌对方即使知道公开密钥KUb，要确定私有密钥，要确定私有密钥KRb在计在计算上是

4、不可行算上是不可行（5）敌对方即使知道公开密钥）敌对方即使知道公开密钥KUb和密文和密文C，要想恢复原来的，要想恢复原来的报文报文M在计算上也是不可行的。在计算上也是不可行的。（6）加密和解密函数可以以两个次序中的任何一个来使用）加密和解密函数可以以两个次序中的任何一个来使用: M = DKRb(EKUb(M) (机密性机密性) M = DKUb(EKRb(M) （数字签名）（数字签名）注注：1 1* *. . 仅满足仅满足(1)(1)、(2)(2)两条的称为单向函数；第两条的称为单向函数；第(3)(3)条称为陷门性，条称为陷门性，s s 称为陷门信息。称为陷门信息。 2 2* *. . 加密

5、密钥便称为公开密钥，记为加密密钥便称为公开密钥，记为PkPk。 f f函数的设计者将函数的设计者将s s 保保密，用作解密密钥，此时密，用作解密密钥，此时s s 称为秘密密钥，记为称为秘密密钥，记为SkSk。由于加密函。由于加密函数是公开的，任何人都可以将信息数是公开的，任何人都可以将信息x x加密成加密成y y= =f f( (x x) )，然后送给函，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有数的设计者（当然可以通过不安全信道传送）；由于设计者拥有SkSk，他自然可以解出，他自然可以解出x x= =f f-1-1( (y y) )。 3 3* *. .单向陷门函数的

6、第单向陷门函数的第(2)(2)条性质表明窃听者由截获的密文条性质表明窃听者由截获的密文y y= =f f( (x x) )推测推测x x是不可行的。是不可行的。是满足下列条件的函数是满足下列条件的函数f：(1)给定给定x，计算，计算y=f(x)是容易的是容易的(2)给定给定y, 计算计算x使使x=f-1(y)是困难的是困难的(3)存在存在s，已知，已知s 时时,对给定的任何对给定的任何y，若相应的，若相应的x存在，则存在，则计算计算x使使x=f-1(y)是容易的是容易的陷门单向函数陷门单向函数l蛮力攻击蛮力攻击(与对密钥类似与对密钥类似)。l公开密钥算法本身可能被攻破。公开密钥算法本身可能被攻

7、破。尚未从数学上严格证明这种攻击是不可能的尚未从数学上严格证明这种攻击是不可能的l可能报文攻击可能报文攻击(对报文本身的蛮力攻击对报文本身的蛮力攻击)。l加密加密/解密解密l数字签名数字签名l会话密钥交换会话密钥交换l本原元：本原元：对于一个素数对于一个素数q，如果数值：，如果数值： ，是各不相同的整数，并且以某，是各不相同的整数，并且以某种排列方式组成了种排列方式组成了从从1到到q-1的所有整数的所有整数则称整数则称整数a是素数是素数q的一个本原元的一个本原元qamodqa mod2qaqmod1l离散对数问题：离散对数问题：对于一个整数对于一个整数b和素数和素数q的一个本原元的一个本原元a

8、，可，可以找到一个唯一的指数以找到一个唯一的指数i，使得：，使得：b=ai mod q (i 0, q-1) 成立，则指数成立，则指数i称为称为b的以的以a为底为底的模的模q的离散对数。的离散对数。l已知已知a, i, q, 容易计算出容易计算出bl给定给定b, a, q, 计算计算i非常困难，即离散对数问题非常困难，即离散对数问题l一个素数一个素数q和一个整数和一个整数a（均公开），（均公开），a是是q的一个本原元的一个本原元l用户用户A选择一个随机数选择一个随机数XAq，并计算，并计算 l类似地，用户类似地，用户B选择一个随机数选择一个随机数XBq,并计算并计算 l每一方都对每一方都对X的

9、值保密存放而使得的值保密存放而使得Y的值对于另一方可以公的值对于另一方可以公开得到开得到l用户用户A计算密钥：计算密钥： l用户用户B计算密钥：计算密钥：l双方以双方以K作为加、解密密钥，以对称密钥算法进行保密通信作为加、解密密钥，以对称密钥算法进行保密通信qaYAXAmodqaYBXBmodqYKAXBmod)(qYKBXAmod)(l素数素数q=97,它的一个本原元它的一个本原元a=5lA和和B分别选择随机数分别选择随机数Xa=36和和Xb=58lA计算公开密钥：计算公开密钥：Ya=536mod97=50mod97 lB计算公开密钥：计算公开密钥：Yb=558mod97=44mod97 l

10、A计算会话密钥：计算会话密钥：K= 4436mod97=75mod97lB计算会话密钥：计算会话密钥：K= 5058mod97=75mod97由由Rivest,Shamir和和Adleman在在1978年提出来的年提出来的数学基础数学基础: Euler定理，其安全性建立在定理，其安全性建立在大整数因子分解大整数因子分解的的困难性之上困难性之上l明文空间明文空间P密文空间密文空间C=Znl密钥的生成密钥的生成选择互异素数选择互异素数p,q，计算，计算n=p*q, (n)=(p-1)(q-1), 选选择整数择整数e使使( (n),e)=1,0e (n),计算计算d,使使 d=e-1mod (n)公

11、钥公钥Pk=e,n私钥私钥Sk=d,nl加密加密 (用用e,n)明文：明文：Mn 密文：密文：C=Me( mod n )l解密解密 (用用d,n) 密文：密文：C 明文：明文：M=Cd（mod n )l若若BobBob选择了选择了p=7p=7和和q q1717l则则n=119, n=119, (n)=6 (n)=6161696962 25 53 3，一个正整数，一个正整数e e能用作加密能用作加密指数，当且仅当指数，当且仅当e e不能被不能被2 2，3 3所整除所整除l假设假设BobBob选择选择e=5e=5，那么用辗转相除法将求得：，那么用辗转相除法将求得： d=e d=e -1-1 77(

12、mod 77(mod 96)96)lBobBob的解密密钥的解密密钥d=77,119d=77,119，公开，公开5,1195,119 l现假设现假设AliceAlice想发送明文想发送明文1919给给BobBob步骤步骤：Bob为实现者为实现者lBob寻找出两个大素数寻找出两个大素数p和和qlBob计算出计算出n=pq和和 (n)=(p-1)(q-1).lBob选择一个随机数选择一个随机数e(0e (n)，满足（，满足（e， (n)）1lBob使用辗转相除法计算使用辗转相除法计算d=e-1(mod (n)l Bob在目录中公开在目录中公开n和和e作为她的公开钥作为她的公开钥密码分析者攻击密码分

13、析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n。若。若分解成功使分解成功使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)，然后，然后由公开的由公开的e，解出秘密的，解出秘密的d。要求：要求：若使若使RSA安全，安全，p与与q必为足够大的素数，使必为足够大的素数，使分析者没有办法在有效时间内将分析者没有办法在有效时间内将n分解出来。建议选择分解出来。建议选择p和和q大约是大约是100位的十进制素数。位的十进制素数。 模模n的长度要求至少是的长度要求至少是512比特。比特。 为了抵抗现有的整数分解算法，对为了抵抗现有的整数分解算法，对RSA模模n的素因子的素因子p和和

14、q还有如下要求：还有如下要求：(1)p, q的值应当不是很接近；的值应当不是很接近；(2)p-1 和和q-1分别含有大素因子分别含有大素因子(3)gcd(p-1,q-1)应比较小。应比较小。为了提高加密速度，通常取为了提高加密速度，通常取e为特定的小整数，如为特定的小整数，如EDI（电子数据交换）国际标准中规定（电子数据交换）国际标准中规定 e2161，ISO/IEC9796（国际标准化组织（国际标准化组织/国际电工委员会）中甚至国际电工委员会）中甚至允许取允许取e3。这时加密速度一般比解密速度快。这时加密速度一般比解密速度快10倍以上。倍以上。QX1X2X3Y1Y2Y310276001167

15、16011671168811168811779111779233982339172817117281719314231931427412231用用RSA算法加密与解密的过程：算法加密与解密的过程：例：明文例：明文=“RSA ALGORITHM”(1) 明文用数字表示明文用数字表示 空白空白=00， A=01, B=02, , Z=26 (两位两位十进制数表示十进制数表示)1819 0100 0112 0715 1809 2008 1300(2) 利用加密变换公式利用加密变换公式 C=mPK mod r, 即即C = 18191223 mod 2867=2756PK=1223=100110001

16、11 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223 (mod 2867) =18191024 1819128 181964 18194 18192 18191(mod 2867) =27562756 2001 0542 0669 2347 0408 1815选择两个大素数选择两个大素数p和和q，通常要求每个均大于，通常要求每个均大于10100。u计算计算npq和和z(p1)(q1)。u选择一与选择一与z互素的数、令其为互素的数、令其为d 。u找到一个找到一个e满足满足ed1 (mod z)。 选好这些参数后，将明文划分成块，使得每个明文报文

17、选好这些参数后，将明文划分成块，使得每个明文报文P长度长度m满足满足0mn。加密。加密P时，计算时，计算CPe(mod n)，解密，解密C时计算时计算PCd(mod n)。可以证明，在确定的范围内，加密。可以证明，在确定的范围内，加密和解密函数是互逆的。和解密函数是互逆的。 为实现加密，需要公开为实现加密，需要公开(e, n)，为实现解密需要，为实现解密需要(d, n)。如何计算如何计算ab mod n？如何判定一个给定的整数是素数？如何判定一个给定的整数是素数？如何找到足够大的素数如何找到足够大的素数p和和q ? 要点要点1：(a x b) mod n = (a mod n) x (b mo

18、d n) mod n 要点要点2：a16=aaaaaaaaaaaaaaaa =a2, a4,a8, a16更一般性的问题：更一般性的问题：amm的二进制表示为的二进制表示为bkbk-1b0, 则则 计算计算am mod nam mod n = a(2i) mod n = ( a(2i) mod n) mod nbi 0bi 0ikiibm20 Square_and_Multiply(a, m, n) y 1for i 0 to k if bi = 1 y ay mod n a aa mod n return yMiller_Rabin_Test(n, a)1. 求求m, k 使得使得 n-1

19、= m *2k2. T = am mod n3. If (T = 1 | T = n-1) return True4. for i 1 to k-15.T (T T) mod n6.if T = 1 return False7.if T = n-1 return True8. return FALSE 返回值：返回值：TRUE: n可能是素数可能是素数FALSE: n一定不是素数一定不是素数应用：应用：随机选择随机选择a n, 计算计算s次，次，如果每次都返回如果每次都返回True，则这时则这时n是素数的概率为是素数的概率为(1 - 1/4s)如何判定一个给定的整数是素数？如何判定一个给定的整

20、数是素数？1. 随机选一个奇数随机选一个奇数n (伪随机数发生器伪随机数发生器)2. 随机选择一个整数随机选择一个整数a n3. 执行概率素数判定测试执行概率素数判定测试,如果如果n 未测试通过未测试通过,则则 拒绝数值拒绝数值n, 转向步骤转向步骤14. 如果如果n已通过足够的测试已通过足够的测试, 则接受则接受n, 否则转向步骤否则转向步骤2;说明：说明： 随机选取大约用随机选取大约用 ln(N)/2的次数，如的次数，如ln(2200)/2=70 好在生成密钥对时才用到，慢一点还可忍受。好在生成密钥对时才用到，慢一点还可忍受。 确定素数确定素数p和和q以后，只需选取以后，只需选取e, 满足

21、满足gcd(e, (n)=1, 计算计算d = e-1 mod (n) （扩展的欧拉算法）（扩展的欧拉算法）如何找到足够大的素数如何找到足够大的素数p和和q ?p和和q在长度上应仅差几个数位，即在长度上应仅差几个数位，即p和和q应是应是1075 到到10100（p-1）和（）和（q-1）都应包含一个较大的素数因子）都应包含一个较大的素数因子gcd(p-1, q-1)应比较小应比较小如果如果en 且且 dn1/4,则则d可以很容易确定可以很容易确定算法的发明者建议算法的发明者建议数字签名数字签名方案：一个签名方案是由签署算法与验证算法方案：一个签名方案是由签署算法与验证算法两部分构成。可由五元关

22、系组（两部分构成。可由五元关系组（M,A,K,S,V）来描述：）来描述：(1)M是由一切可能是由一切可能消息消息所构成的有限集合；所构成的有限集合；(2)A是一切可能的签名的有限集合；是一切可能的签名的有限集合；(3)K为有限密钥空间，是一些可能密钥的有限集合；为有限密钥空间，是一些可能密钥的有限集合；(4)任意任意k K，有签署算法，有签署算法Sigk S且有对应的验证算且有对应的验证算法法VerkV,对每一个对每一个Sigk和和Verk满足条件：任意一个满足条件：任意一个签名：签名：Ver(x,y)= RSA的数字签名应用的数字签名应用真 若y=sig(x)假 若ySig(x)l选取整数选

23、取整数n=pq,M=A=Znl定义密钥集合定义密钥集合K=(n,e,p,q,d)|n=pq,d*e 1(mod (n)ln和和e为公钥；为公钥；p,q,d为保密的（私钥）为保密的（私钥）l对对xM, Bob要对要对x签名，取签名，取kK：lSigk(x) xd(mod n) y(mod n)l Verk(x,y)=真真 x ye(mod n)RSA的数字签名方案的数字签名方案假设假设Alice想把签了名的消息加密送给想把签了名的消息加密送给Bob：对明文：对明文x，Alice计计算对算对x的签名的签名y=SigAlice(x)，然后用，然后用Bob的公钥加密函数的公钥加密函数eBob,算出算出

24、z=eBob(x,y) ,Alice 将将z传给传给BobBob收到收到z后，先解密：后，先解密：dBob(z)=dBobeBob(x,y)=(x,y)后检验：后检验： VerAlice(x,y)= 真？真？问题：问题：若若AliceAlice首先对消息首先对消息x x进行加密进行加密,z=e,z=eBobBob(x),(x),然后再签名，然后再签名， y=Sigy=SigAliceAlice(e(eBobBob(x),(x),结果如何呢？结果如何呢？Alice 将（将（z,y)传给传给Bob，Bob先将先将z解密，获取解密，获取x;然后用然后用VerAlice检验关于检验关于x的加密签名的加

25、密签名y一个潜在问题一个潜在问题：如果：如果Oscar获得了这对（获得了这对（z,y)，他能用自己，他能用自己的签名来替代的签名来替代Alice的签名的签名 y =SigOscar(eBob(x)签名消息的加密传递问题签名消息的加密传递问题 l椭圆曲线密码体制以高效性著称椭圆曲线密码体制以高效性著称l由由Neal Koblitz和和Victor Miller在在1985年年分别提出分别提出lECC的安全性基于椭圆曲线离散对数问的安全性基于椭圆曲线离散对数问题的难解性题的难解性l密钥长度大大地减少密钥长度大大地减少l是目前已知公钥密码体制中每位提供加是目前已知公钥密码体制中每位提供加密强度最高的

26、一种体制密强度最高的一种体制 定义：定义：椭圆曲线是一个具有两个变元椭圆曲线是一个具有两个变元x和和y的三的三次方程，它是满足：次方程，它是满足： Y2+aXY+bY=X3+cX2+dX+e 的所有点的所有点(X,Y)的集合，外加一个零点或无穷远的集合，外加一个零点或无穷远点点O （认为其（认为其y坐标无穷大）坐标无穷大）l实数域上的椭圆曲线是对于固定的实数域上的椭圆曲线是对于固定的a、b值，满足形如方程：值，满足形如方程：Y2=X3+aX+b 的所有点的集合，外加一个零点或无穷的所有点的集合，外加一个零点或无穷远点远点l其中其中a、b是实数，是实数，4*a2 + 27*b3 != 0, X和

27、和Y在实数域上取值在实数域上取值lGF(p)域上的椭圆曲线是对于固定的域上的椭圆曲线是对于固定的a、b值，满足形如方程：值，满足形如方程：Y2=X3+aX+b mod(p) 的所有点的集合，外加一个零点或无穷的所有点的集合，外加一个零点或无穷远点远点l其中其中a、b，X和和Y在在GF(p)域上取值域上取值 0, p-1， 且满足且满足4*a2 + 27*b3 != 0l如果如果E是定义在是定义在GF(p)域上的椭圆曲线，域上的椭圆曲线，N是是E上的点的个数，则：上的点的个数，则： ppN2) 1(l是对于固定的是对于固定的a、b值，满足形如方程：值，满足形如方程：Y2+XY=X3+aX2+b

28、的所有点的集合，外加一个零点或无穷的所有点的集合，外加一个零点或无穷远点远点l其中其中a、b，X和和Y在在GF(2m)域上取值域上取值lGF(2m)域上的元素是域上的元素是m位的二进制串位的二进制串 l由多项式定义的域由多项式定义的域GF（24）l生成元为生成元为g=(0010)，g的各幂分别是的各幂分别是 1)(4xxxfg0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(10

29、01)g15=(0001)l考虑椭圆曲线：考虑椭圆曲线：l点点(g5, g3)满足该方程满足该方程 l(g3)2 + g5 g3 = (g5) 3 + g4 (g5) 2 + 1 g6 + g8 = g15 +g14 + 1 (1100) + (0101) = (0001) + (1001) + (0001) (1001) = (1001) 12432xgxxyylAbel群群 ：l加法规则加法规则1：l加法规则加法规则2：l加法规则加法规则3：互逆点：互逆点l加法规则加法规则4：加法交换律：加法交换律l加法规则加法规则5：加法结合律：加法结合律 l加法规则加法规则6： l加法规则加法规则7

30、：0)(mod27423pbaOOOPOPOQPPQQPRQPRQP)()(332211,yxSyxQyxP2123xxx1313)(yxxy1212xxyy),(),(2),(,33111111yxQyxPyxPyxP1232xx1313)(yxxy12123yax lGF（2m)域域l加法规则加法规则3 ：如果，则如果，则l加法规则加法规则6 ：l加法规则加法规则7 ：332211,yxSyxQyxPaxxx212313313)(yxxxy1212xxyy),(),(2),(,33111111yxQyxPyxPyxP3213*) 1(xxyax231121xyx ,Px y,Px xyl标

31、量乘标量乘l阶阶P是椭圆曲线是椭圆曲线E上的一点，若存在最小的正上的一点，若存在最小的正整数整数n，使得，使得nP=O，则称，则称n是点是点P的阶的阶 mPPPmPlGF（23）上椭圆曲线）上椭圆曲线 ：l设：设：l求求P1P2和和2P1132xxy10, 31P7 , 92P112)23mod1()23(mod21391071212xxyy1723mod109931122123xxx2023mod14410)173(11)(1313yxxy6424423mod123mod2050223mod281021)3(3232121yax723mod3032)6(22123xx1223mod3410)

32、73(6)(1313yxxyl椭圆曲线离散对数问题椭圆曲线离散对数问题已知椭圆曲线已知椭圆曲线E和点和点P，随机生成一个整数，随机生成一个整数d，容易计算容易计算:Q=d*P，但给定，但给定Q和和P,计算计算d就相就相对困难对困难 l选取选取:一个基域一个基域GF(p)定义在该基域上的椭圆曲线定义在该基域上的椭圆曲线Ep(a,b)E上的一个拥有素数阶上的一个拥有素数阶n的点的点Pl其中有限域其中有限域GF(p) ，椭圆曲线参数，椭圆曲线参数a,b，点点P和阶和阶n都是公开信息都是公开信息l在区间在区间1,n-1中随机选取一个整数中随机选取一个整数dl计算计算:Q=d*Pl实体的实体的公开密钥公

33、开密钥:点点Q私钥私钥:整数整数d l待发送消息：待发送消息：AB：Ml查找查找B的公开密钥：的公开密钥：Ql将消息将消息M表示成一个域元素表示成一个域元素:ml在区间在区间1, n-1中随机选取一个整数中随机选取一个整数kl计算点计算点:(x1,y1)=kPl计算点计算点:(x2,y2)=kQ，如果，如果x2=0，则返回第，则返回第(3)步步l计算计算:c=mx21.传送加密数据传送加密数据(x1,y1,c)给给B l当实体当实体B解密从解密从A收到的密文收到的密文(x1,y1,c)时，时，执行步骤：执行步骤：使用私钥使用私钥d，计算点，计算点:(x2,y2)=d (x1,y1)计算计算 ，

34、恢复出消息，恢复出消息m 12xcml任务：任务：BA：ml用户用户A选取随机数（私钥）选取随机数（私钥）dA，产生公开，产生公开密钥密钥:PA=dA*Gl用户用户B选取随机数（私钥）选取随机数（私钥）dB，并计算公，并计算公钥：钥：PB=dB*GlB计算并向计算并向A发送：发送：(PB，m+dB*PA)l用户用户A解密：解密：(m+dB*PA)dA*PBm l椭圆曲线椭圆曲线l设用户设用户A的私钥为的私钥为7，则公钥为：，则公钥为：1)设用户设用户B的消息的消息m编码后为，且选取了编码后为，且选取了随机数随机数2)用户用户B计算：，计算：，3）B向向A发送消息：发送消息：4)用户用户A计算：

35、计算：5)用户用户A计算：计算： 2213:22,133223xxyE5 ,10G21,177GPA1 ,11mP13Bd5 ,165 ,1013GdB18,2021,1713ABPd 19,1818,201 ,11ABmPdP 19,18,5 ,16 18,205 ,167 1 ,1181,2019,1818,2019,18l设设E是有限域是有限域GF(p)上的椭圆曲线，上的椭圆曲线，N为为椭圆曲线的阶，椭圆曲线的阶， 是明文空间到椭圆曲是明文空间到椭圆曲线群的嵌入线群的嵌入l用户用户A选取一个公钥选取一个公钥 ，私钥，私钥 ，满，满足，。足，。l对于消息对于消息m，用户，用户B加密消息为加密消息为 用户用户A解密过程为：解密过程为： mPm AeAdNdeAAmod1NeA1NdA1mAmPeCmmAAmAmPPdeCdP l椭圆曲线椭圆曲线 ，设消息，设消息m编编码后的信息为码后的信息为: 。可验证。可验证