《密码学》05-3 基于离散对数问题的公钥密码

密码学第五章公钥密码5.3

基于离散对数问题的公钥密码离散对数问题1Diffie-Hellman密钥交换协议2ElGamal公钥密码算法35.3

基于离散对数问题的公钥密码

在实数域中，取幂运算(计算bx到一定精度)不比它的逆运算(求对数logbx到一定精度)容易很多。

而对有限域，其中的取幂运算(计算bx的值)很容易，但它的逆运算(求离散对数logbx)则是一个非常困难的问题。一、离散对数问题有限域Fp上的离散对数问题：给定一个素数p和Fp上的一个本原元g，对，求整数x，，使得成立.通常用x=loggy

来表示，并称x为y的以g为底关于模p的离散对数。一、离散对数问题

对于等式，给定g、x和p，计算y是容易的。反过来，若已知y、g和p，当p是大素数时，找到一个x，使成立是困难的。对大素数p，模p指数运算是一个单向函数。一、离散对数问题离散对数问题是NP问题。按目前的最好算法,求解素域Fp上的离散对数的计算复杂性为但当p较小时,求解非素域Fpn上的离散对数的计算复杂性为因此,在利用有限域上的离散对数问题时,多将有限域选为素域Fp.其中一、离散对数问题离散对数问题的求解难度：与离散对数密切相关的是Diffie-Hellman问题Diffie-Hellman问题(DHP)：

Fp*中的Diffie-Hellman问题可以在多项式时间内转化为离散对数问题。一、离散对数问题给定一个素数p和Fp上的一个本原元g及ga

modp和

gb

modp

，求gabmodp.

Diffie-Hellman密钥交换协议是WhitefieldDiffie和MartinHellman在1976年提出的。安全性基础：离散对数问题的难解性。二、Diffie-Hellman密钥交换协议人工手动分配密钥:问题效率低成本高每个用户要存储与所有用户通信的密钥安全性差机器自动分配密钥:要求任何两个用户能独立计算他们之间的秘密密钥传输量小存储量小任何一个(或多个)用户不能计算出其他用户之间的秘密密钥二、Diffie-Hellman密钥交换协议D-H密钥交换协议背景:密钥分配UV二、Diffie-Hellman密钥交换协议D-H密钥交换协议基本模式Diffie-Hellman密钥交换协议具体描述:

设计过程:

Step1

选取安全的大素数

p,再选取g是Fp

的一个本原元，并将p和g公开，全网公用；

Step2

用户U随机选取整数xu：1≤xu≤p-2,并计算出，将明传给用户V,并暂时保留xu；二、Diffie-Hellman密钥交换协议

用户V算出

Step4

用户U算出之后，将k作为双方协商的密钥，同时不再保留xu

和xv

。

Step3

用户V随机选取整数xv：1≤xv≤p-2,并计算出，将明传给用户U，并暂时保留xv；二、Diffie-Hellman密钥交换协议优点：

(1)任何两个人都可协商出会话密钥，不需事先拥有对方的公开或秘密的信息；(2)每次密钥交换后不必再保留秘密信息，减少了保密的负担。二、Diffie-Hellman密钥交换协议前提条件:必须进行身份认证，确保不是与假冒的用户进行密钥交换,否则不能抵抗中间人攻击.中间人攻击:攻击者W在信道中间：假冒U，与V进行密钥交换；同时假冒V，与U进行密钥交换。致使看似U与V交换的密钥，实际上都是与攻击者交换的密钥。

二、Diffie-Hellman密钥交换协议二、Diffie-Hellman密钥交换协议中间人攻击基本模式UVW中间人攻击方案

Step1

攻击者W首先截获，然后随机选取整数xw：1≤xw≤p-2,并算出后，将其明传给用户V，同时暂时保留xw；

Step2

攻击者W再截获，然后将

明传给用户U；

Step3

用户U算出

用户V算出攻击者W算出和二、Diffie-Hellman密钥交换协议Step4

攻击者W截获用户U发给V的密文后，不传给用户V，而是解读出明文后再将明文用W与V的密钥加密后传给V。二、Diffie-Hellman密钥交换协议对付中间人攻击的方法:中间人攻击利用了D-H协议中与双方的身份信息无关这个缺点，因而必须利用对方的身份信息对之进行身份认证。二、Diffie-Hellman密钥交换协议

ElGamal公钥密码体制是ElGamal在1985年提出的。安全性基础：有限域上离散对数问题的难解性。三、ElGamal公钥密码算法Step2随机选取整数x：1xp-2

,并计算出用户A的密钥生成过程:用户A的公钥是(p,g,gx);私钥是x。三、ElGamal公钥密码算法ElGamal公钥密码算法描述:

Step1

选取安全的大素数

p,再选取g是Fp*的一个本原元；B加密:B秘密选择一个整数则密文为其中A脱密:

对任意密文明文为假定B加密信息mFp给A，A解密。三、ElGamal公钥密码算法加、脱密变换:

例1：生成密钥：用户A选取素数p=11及F11*的生成元g=2，并选取私钥x=5,计算y=gx

modp=10用户A的公钥是(p=11,g=2,gxmodp=10);

私钥是x=5B加密：为加密信息m=7，秘密选择一个整数k=3,并计算A脱密:

对密文明文为m=4(85)1mod11=7三、ElGamal公钥密码算法例2：生成密钥：用户A选取素数p=2579及F2579*的生成元g=2，并选取私钥x=765,计算y=gxmodp=949B加密：为加密信息m=1299，秘密选择一个整数k=853.并计算A脱密:

对密文明文为m=2396(435765)-1mod2579=1299三、ElGamal公钥密码算法用户A的公钥是(p=2579,g=2,gxmodp=949);

私钥是x=765为何密文需要扩展1倍?这涉及其设计思想问题。三、ElGamal公钥密码算法特点：

(1)密文长度扩展1倍

；(2)只利用了有限域的乘法群的性质，即只使用了乘法运算和求乘法逆的运算，并没有用到加法运算。三、ElGamal公钥密码算法设计思想利用Diffie-Hellman密钥交换协议生成双方加密用的密钥，此时yk

modp=(gx)k

modp=gkx

modp