密码学 (第九讲) 公开密钥密码(2) 张焕国 武汉大学计算机学院
密 码 学 （第九讲） 公开密钥密码（ 公开密钥密码（2） 张焕国 武汉大学计算机学院
一、ELGamal公钥密码的基本情况 1、基本情况： ①ELGamal密码是除了RSA密码之外最有代表 性的公开密钥密码。 ②RSA密码建立在大合数分解的困难性之上。 ③ELGamali密码建立在离散对数的困难性之上
一、ELGamal ELGamal公钥密码的基本情况 公钥密码的基本情况 1、基本情况： ①ELGamal ELGamal密码是除了RSA密码之外最有代表 密码之外最有代表 性的公开密钥密码。 ②RSA密码建立在大合数分解的困难性之上。 码建立在大合数分解的困难性之上。 ③ELGamal ELGamal密码建立在离散对数的困难性之上 密码建立在离散对数的困难性之上
ELGamal公钥密码的基本情况 2、离散对数问题: ①设p为素数,则模p的剩余构成有限域 F2=101,2…,p-1 Fn的非零元构成循环群F* F*=({12…,p-1 a. a a ap 则称a为的生成元或模p的本原元。 ②求a的摸幂运算为: y= ax mod p,1≤x≤p-1
一、ELGamal ELGamal公钥密码的基本情况 公钥密码的基本情况 2、离散对数问题： ①设p为素数，则模p的剩余构成有限域： 的剩余构成有限域： Fp={0,1,2,… ,p-1} Fp 的非零元构成循环群Fp* Fp* ={1,2,… ,p-1} ={α，α2，α3，，αp-1}， 则称α为Fp*的生成元或模 p 的本原元。 ②求α的摸幂运算为: y =αx mod p，1≤x≤p-1
ELGamal公钥密码的基本情况 2、离散对数问题: 求矿数H的运算为 x= lagay,1≤x≤p-1 由于上述运算是定义在模D有限域上的,所以称为 离散对数运算。 ③从x计算是容易的。可是从y计算x就图难得多, 利用月前最好的算法,对于小心选择的将至少 需用0(8次以上的运算,只要足够大,求解 离散对数问题是相当因难的
一、ELGamal ELGamal公钥密码的基本情况 公钥密码的基本情况 2、离散对数问题： 求对数 X 的运算为 x=logαy，1≤x≤p-1 由于上述运算是定义在模 由于上述运算是定义在模p有限域上的，所以称为 离散对数运算。 ③从x计算y是容易的。可是从y计算x就困难得多， 利用目前最好的算法 利用目前最好的算法，对于小心选择的 对于小心选择的p将至少 需用O(p ½)次以上的运算，只要p足够大，求解 离散对数问题是相当困难的 问题是相当困难的
、 ELGamal公钥密码 准备:随机地选择一个大素数p,且要求p-1有 大素数因子。再选择一个模p的本原元a。将p 和a公开。 (1)密钥生成 用户随机地选择一个整数d作为自己的秘密的解 密钥,2≤d≤p-2。 计算y= ad mod p,歌为自己的公开的加密钥。 由公开钥y计算秘密钥d,必须求解离款对数, 而这是极因的
二、 ELGamal ELGamal公钥密码 • 准备：随机地选择一个大素数p，且要求p-1有 大素数因子。再选择一个模 子。再选择一个模p的本原元α。将p 和α公开。 ⑴ 密钥生成 • 用户随机地选择一个整数 随机地选择一个整数d作为自己的秘密的解 密钥，2≤d≤p-2 。 • 计算y=αd mod p，取y为自己的公开的加密钥 为自己的公开的加密钥。 • 由公开钥y 计算秘密钥d，必须求解离散对数 必须求解离散对数， 而这是极困难的 而这是极困难的
、 ELGamal公钥密码 (2)加密 将明丈消息M(0≤M≤p-1)加密成密文的过程如 下 ①随机地选取一个整数k,2≤k≤p-2 ②计算:U= yk mod p; C=ak mod p; C2=UM mod p; ③取C=(C1,C2)作为的密文
二、 ELGamal ELGamal公钥密码 ⑵ 加密 • 将明文消息M（0≤M≤p-1)加密成密文的过程如 加密成密文的过程如 下： ①随机地选取一个整数k，2≤k≤p-2。 ②计算： U ＝y k mod p； C1＝αk mod p； C2＝UM mod p； ③取 C＝（C1 ，C2）作为的密文
、 ELGamal公钥密码 ()解密 将密文(C1,C2)解密的过程如下 ①计算V=C14m0odp; ②计算M=C2V-1modp
二、 ELGamal ELGamal公钥密码 ⑶ 解密 • 将密文（C1 ，C2）解密的过程如下： 解密的过程如下： ①计算V＝C1d mod p； ②计算M＝C2 V -1 mod p
、 ELGamal公钥密码 解密的可还原性可证明如下: C2V-I mod p=(UM)V-I mod p =UM(C1 d)-I mod p -UM((ak)d)-I mod p -UM((a d)k)-l mod p =UM((y)k)-I mod p =UM (U)-I mod p =M mod p
二、 ELGamal ELGamal公钥密码 • 解密的可还原性可证明如下： C2 V-1 mod p ＝(UM)V-1 mod p ＝UM（C1 d）-1 mod p ＝UM（（αk）d）-1 mod p ＝UM（（αd）k）-1 mod p ＝UM（（y）k）-1 mod p ＝UM（U）-1 mod p ＝M mod p
、 ELGamal公钥密码 4)安全性 由于 ELGamal密码的安全性建立在GF(p)离散 对数的雅性之上,而目前尚无求解GF(p)离 散对数的有数算法,所以在p足够大时 ELGamal 密码是安全的。 为了安全应为150位以上的十进制数,而且p1 应有大素因子。 。为了安全加和签名所使用的k必须是一次性的 d和k都不能太小
二、 ELGamal ELGamal公钥密码 ⑷ 安全性 • 由于ELGamal ELGamal密码的安全性建立在 密码的安全性建立在GF（p）离散 对数的困难性之上 对数的困难性之上，而目前尚无求解 而目前尚无求解GF（p）离 散对数的有效算法 散对数的有效算法，所以在p足够大时ELGamal ELGamal 密码是安全的。 • 为了安全p应为150位以上的十进制数 位以上的十进制数，而且p-1 应有大素因子。 • 为了安全加密和签名所使用的k必须是一次性的 必须是一次性的。 • d和k都不能太小
、 ELGamal公钥密码 ()安全性 如果k不是一次性的,时间长了就可能被击 着获得。又因是公开密钥,政击者自然知道。 是项击者就可以根据U=ykm0dp计算出U 进而利用EC1id算法求出U1。又因为攻击者可 以获得密文C2,于是可根据式2=Mm0dp通 过计算C2得到明文M 设用同一个k加密两个不同的明文M和M,相应 的密文为(G1,C2)和(C',C2)。因为 C2=M/M,如果功击者知道M,则很容易 求出M
二、 ELGamal ELGamal公钥密码 ⑷ 安全性 • 如果 k不是一次性的，时间长了就可能被攻击 时间长了就可能被攻击 着获得。又因y是公开密钥，攻击者自然知道 攻击者自然知道。 于是攻击者就可以根据 于是攻击者就可以根据U＝y k mod p计算出U， 进而利用Euclid算法求出U－1。又因为攻击者可 又因为攻击者可 以获得密文C2，于是可根据式C2＝UM mod p通 过计算U－1 C2得到明文M。 • 设用同一个k加密两个不同的明文 加密两个不同的明文M和M’，相应 的密文为（ C1 ， C2）和（ C1’， C2’）。因为 C2∕C2’＝ M∕M’，如果攻击者知道 如果攻击者知道M，则很容易 求出M’