《公钥密码-5.3-基于离散对数问题的公钥密码ppt课件.ppt》由会员分享，可在线阅读，更多相关《公钥密码-5.3-基于离散对数问题的公钥密码ppt课件.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、密码学密码学第五章第五章 公钥密码公钥密码5.3 基于离散对数问题的公钥密码基于离散对数问题的公钥密码离散对数问题离散对数问题1Diffie-Hellman密钥交换协议密钥交换协议2ElGamal公钥密码算法公钥密码算法35.3 基于离散对数问题的公钥密码基于离散对数问题的公钥密码 在实数域中，取幂运算在实数域中，取幂运算(计算计算bx到一定精度到一定精度)不不比它的逆运算比它的逆运算(求对数求对数logbx到一定精度到一定精度)容易很多。容易很多。 而对有限域，其中的取幂运算而对有限域，其中的取幂运算(计算计算bx的值的值)很很容易，但它的逆运算容易，但它的逆运算(求离散对数求离散对数log
2、bx)则是一个非则是一个非常困难的问题。常困难的问题。一一、离散对数问题离散对数问题有限域有限域Fp上的离散对数问题上的离散对数问题 ：给定一个素数给定一个素数p和和Fp上的一个本原元上的一个本原元g，对，对 ，求整数求整数x， ，使得，使得 成立成立.*pFy20pxpgyxmod 通常用通常用 x = loggy 来表示，并称来表示，并称x为为y的以的以g为为底关于模底关于模 p 的离散对数。的离散对数。 一一、离散对数问题离散对数问题 对于等式对于等式 ，给定，给定g、x和和p，计算，计算 y是容易的。是容易的。 反过来，若已知反过来，若已知y、g和和p，当，当p是大素数时，是大素数时，
3、找到一个找到一个x，使，使 成立是困难的。成立是困难的。 pgyxmodpgyxmod对大素数对大素数p，模，模 p 指数运算是一个单向函数。指数运算是一个单向函数。 一一、离散对数问题离散对数问题离散对数问题离散对数问题是是NP问题问题。)log(log)(log1 (exp2121ppoc按目前的最好算法按目前的最好算法,求解素域求解素域Fp上的离散对数的计上的离散对数的计算复杂性为算复杂性为但当但当p较小时较小时, 求解非素域求解非素域Fpn上的离散对数的计算上的离散对数的计算复杂性为复杂性为 因此因此, 在利用有限域上的离散对数问题时在利用有限域上的离散对数问题时,多将有多将有限域选为
4、素域限域选为素域Fp.)log(log)(log1 (exp3231qqoc 1332/91.5262c 其中一一、离散对数问题离散对数问题离散对数问题的求解难度：离散对数问题的求解难度：与离散对数密切相关的是与离散对数密切相关的是Diffie-Hellman问题问题Diffie-Hellman问题问题(DHP)： Fp*中的中的Diffie-Hellman问题可以在多项式时问题可以在多项式时间内转化为离散对数问题。间内转化为离散对数问题。一一、离散对数问题离散对数问题给定一个素数给定一个素数p和和Fp上的一个本原元上的一个本原元 g及及ga mod p和和 gb mod p ，求，求gab
5、mod p. Diffie-Hellman密钥交换协议是密钥交换协议是Whitefield Diffie和和Martin Hellman在在1976年提出的。年提出的。安全性基础：安全性基础：离散对数问题的难解性。离散对数问题的难解性。人工手动分配密钥人工手动分配密钥: 问题问题效率低效率低成本高成本高每个用户要存储与所有用户通信的密钥每个用户要存储与所有用户通信的密钥安全性差安全性差机器自动分配密钥机器自动分配密钥: 要求要求任何两个用户能独立计算他们之间的秘密密钥任何两个用户能独立计算他们之间的秘密密钥传输量小传输量小存储量小存储量小任何一个任何一个(或多个或多个)用户不能计算出其他用户之
6、用户不能计算出其他用户之间的秘密密钥间的秘密密钥D-H密钥交换协议背景密钥交换协议背景: 密钥分配密钥分配UVmoduxgpmodvxgpD-H密钥交换协议基本模式密钥交换协议基本模式Diffie-Hellman 密钥交换协议具体描述密钥交换协议具体描述: 设计过程设计过程: : Step1 选取安全的大素数选取安全的大素数 p, ,再选取再选取 g 是是 Fp 的一的一个本原元，并将个本原元，并将 p 和和 g 公开，全网公用；公开，全网公用； Step2 用户用户U随机选取整数随机选取整数 xu：1xup-2, ,并计算并计算出出 ，将，将 明传给用户明传给用户V, ,并暂时保留并暂时保留
7、xu；moduxgpmoduxgp 用户用户V算出算出(mod)moduvxxkgpp Step4 用户用户U算出算出(mod)modvuxxkgpp之后，将之后，将 k 作为双方协商的密钥，同时不再保留作为双方协商的密钥，同时不再保留 xu 和和xv 。 Step3 用户用户V随机选取整数随机选取整数 xv：1xvp-2, ,并计算并计算出出 ，将，将 明传给用户明传给用户U，并暂时并暂时保留保留xv；modvxgpmodvxgp优点：优点： (1) (1) 任何两个人都可协商出会话密钥，不需事任何两个人都可协商出会话密钥，不需事先拥有对方的公开或秘密的信息；先拥有对方的公开或秘密的信息；
8、(2) (2) 每次密钥交换后不必再保留秘密信息，减每次密钥交换后不必再保留秘密信息，减少了保密的负担。少了保密的负担。前提条件前提条件: : 必须进行身份认证，确保不是与假冒的用户进必须进行身份认证，确保不是与假冒的用户进行密钥交换行密钥交换, ,否则不能抵抗否则不能抵抗中间人攻击中间人攻击. .中间人攻击中间人攻击: : 攻击者攻击者W在信道中间：假冒在信道中间：假冒U，与，与V进行密钥交进行密钥交换；同时假冒换；同时假冒V，与，与U进行密钥交换。致使看似进行密钥交换。致使看似U与与V交换的密钥，实际上都是与攻击者交换的密钥。交换的密钥，实际上都是与攻击者交换的密钥。 中间人攻击基本模式中
9、间人攻击基本模式UVWpuxmodpvxmodpwxmod1pwxmod2中间人攻击方案中间人攻击方案 Step1 攻击者攻击者W首先截获首先截获 ，然后随机，然后随机选取整数选取整数 xw：1xwp-2, ,并算出并算出 后，将后，将 其其明传给用户明传给用户V，同时暂时保留同时暂时保留xw；moduxgpmodwxgp Step2 攻击者攻击者W再截获再截获 ，然后将，然后将 明传给用户明传给用户U；modvxgpmodwxgp Step3 用户用户U算出算出(mod)modwuxxwukgpp 用户用户V算出算出 攻击者攻击者W算出算出 和和(mod)modwvxxwvkgpp(mod)
10、moduwxxwukgpp(mod)modvwxxwvkgpp Step4 攻击者攻击者W截获用户截获用户U发给发给V的密文后，不的密文后，不传给用户传给用户V，而是解读出明文后再将明文用，而是解读出明文后再将明文用W与与V的的密钥加密后传给密钥加密后传给V。对付中间人攻击的方法对付中间人攻击的方法: : 中间人攻击利用了中间人攻击利用了D-H协议中与双方的身份协议中与双方的身份信息无关这个缺点，因而必须利用对方的身份信信息无关这个缺点，因而必须利用对方的身份信息对之进行身份认证。息对之进行身份认证。 ElGamal公钥密码体制是公钥密码体制是ElGamal 在在1985年提年提出的。出的。安
11、全性基础：安全性基础：有限域上离散对数问题的难解性。有限域上离散对数问题的难解性。Step2 随机选取整数随机选取整数x：1 x p-2 ,并计算出并计算出用户用户A的密钥生成过程的密钥生成过程:modxygp用户用户A的公钥是的公钥是(p, g, gx); 私钥是私钥是x。ElGamal公钥密码算法描述公钥密码算法描述: Step1 选取安全的大素数选取安全的大素数 p, ,再选取再选取 g 是是 Fp*的一个的一个本原元；本原元；B加密加密: B秘密选择一个整数则密文为其中*12( ,)ppcc cFF12modmodkkcgpcmyp21:pkk121()modxmccp*21),(pp
12、ZZcccA脱密脱密: 对任意密文明文为 假定假定B加密信息加密信息m Fp 给给A，A解密。解密。加、脱密变换加、脱密变换: 例例1：生成密钥：用户生成密钥：用户A选取素数选取素数p=11及及F11*的生的生成元成元 g=2，并选取私钥，并选取私钥x=5, 计算计算y = gx mod p =10用户用户A的的公钥公钥是是( p=11, g=2, gxmodp=10); 私钥私钥是是 x=5B加密加密：为加密信息 m=7，秘密选择一个整数k=3,并计算12mod8mod4kkcgpcmyp(8,4)c A脱密脱密: 对密文明文为m=4(85)1mod11=7例例2：生成密钥：用户生成密钥：用
13、户A选取素数选取素数p=2579及及F2579*的生成元的生成元 g=2，并选取私钥，并选取私钥x=765,计算计算y=gxmodp=949B加密加密：为加密信息m=1299，秘密选择一个整数k=853.并计算12mod435mod2396kkcgpcmypA脱密脱密: 对密文明文为m=2396(435765)-1mod2579=1299)2396,435(c用户用户A的的公钥公钥是是( p=2579, g=2, gxmodp=949); 私钥私钥是是 x=765为何密文需要扩展为何密文需要扩展1 1倍倍? ? 这涉及其设计思想问题。这涉及其设计思想问题。特点：特点： (1) (1) 密文长度
14、扩展密文长度扩展1 1倍倍 ； (2) (2) 只利用了有限域的乘法群的性质，即只使只利用了有限域的乘法群的性质，即只使用了乘法运算和求乘法逆的运算，并没有用到加法用了乘法运算和求乘法逆的运算，并没有用到加法运算。运算。设计思想设计思想(1)利用利用Diffie-Hellman密钥交换协议生成双方加密密钥交换协议生成双方加密用的密钥，此时用的密钥，此时yk mod p = (gx)k mod p =gkx mod p 不同之处在于已将不同之处在于已将 y = gx mod p 作为公开密钥公作为公开密钥公布布, 不需每次发送。不需每次发送。(2) 采取了一次一密的加密思想。采取了一次一密的加密思想。 将将yk mod p作为双方交换的密钥，利用它对明文作为双方交换的密钥，利用它对明文进行加脱密。进行加脱密。参数选取原则参数选取原则(1) p的位数应在的位数应在1024比特以上；比特以上；(2) p-1必须具有大的素因子。必须具有大的素因子。