三、椭圆曲线密码.PPT

密 码 学 （第九讲） 公开密钥密码（2） 张焕国 武汉大学计算机学院 目 录 1、密码学的基本概念 2、古典密码 3、数据加密标准（DES） 4、高级数据加密标准（AES） 5、中国商用密码（SMS4） 6、分组密码的应用技术 7、序列密码 8、习题课：复习对称密码 9、公开密钥密码（1） 目 录 10、公开密钥密码（2） 11、数字签名（1） 12、数字签名（2） 13、HASH函数 14、认证 15、密钥管理 16、PKI技术 17、习题课：复习公钥密码 18、总复习/检查：综合实验 一、ELGamal公钥密码的基本情况 1、基本情况： ①ELGamal密码是除了RSA密码之外最有代表性的公开密钥密码。 ②RSA密码建立在大合数分解的困难性之上。 ③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、离散对数问题： 求对数 X 的运算为 x=logαy，1≤x≤p-1 由于上述运算是定义在模p有限域上的，所以称为离散对数运算。 ③从x计算y是容易的。可是从y计算x就困难得多，利用目前最好的算法，对于小心选择的p将至少需用O(p ?)次以上的运算，只要p足够大，求解离散对数问题是相当困难的。 二、 ELGamal公钥密码 准备：随机地选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。 ⑴ 密钥生成 用户随机地选择一个整数d作为自己的秘密的解密钥，2≤d≤p-2 。 计算y=αd mod p，取y为自己的公开的加密钥。 由公开钥y 计算秘密钥d，必须求解离散对数，而这是极困难的。 二、 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＝C1 d mod p； ②计算M＝C2 V -1 mod p。 二、 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公钥密码 ⑷ 安全性 由于ELGamal密码的安全性建立在GF（p）离散对数的困难性之上，而目前尚无求解GF（p）离散对数的有效算法，所以在p足够大时ELGamal密码是安全的。 为了安全p应为150位以上的十进制数，而且p-1应有大素因子。 为了安全加密和签名所使用的k必须是一次性的。 d和k都不能太小。 二、 ELGamal公钥密码 ⑷ 安全性 如果 k不是一次性的，时间长了就可能被攻击着获得。又因y是公开密钥，攻击者自然知道。于是攻击者就可以根据U＝y k mod p计算出U，进而利用Euclid算法求出U－1。又因为攻击者可以获得密文C2，于是可根据式C2＝UM mod p通过计算U－1C2得到明文M。 设用同一个k加密两个不同的明文M和M’，相应的密文为（C1 ，C2）和（C1’，C2’）。因为C2∕C2’＝ M∕M’，如果攻击者知道M，则很容易求出M’。 二、 ELGamal公钥密码 ⑸ ELGamal密码的应用 由于ELGamal密码的安全性得到世界公认，所以得到广泛的应用。著名的美国数字签名标准DSS，采用了ELGamal密码的一种变形。 为了适应不同的应用，人们在应用中总结出18种不同的ELGamal密码的变形。 二、 ELGamal公钥密码 ⑸ ELGamal密码的应用 ①加解密速度快 由于实际应用