密码学 (第九讲) 公开密钥密码(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，必须求解离散对数 必须求解离散对数， 而这是极困难的 而这是极困难的