基于离散对数公钥算法同群环域的关系分析

基于离散对数公钥算法同群环域的关系分析读书报告摘要：离散对数公钥加密算法是目前最为热门的公钥加密算法，其安全性要远远高于基于大数分解的RSA算法，很多密码方案的安全性都是取决于求解离散对数问题（DiscreteLogarithmProblem,DLP）的计算复杂性，包括注明的Diffie-Hellman密钥交换方案和Elgamal加密方案。关键字：离散对数，Diffie-Hellman密钥交换方案，Elgamal加密方案，Elgamal签名方案1.引言本文将首先介绍什么是离散对数，以及离散对数的特点和单向性。以及Diffie-Hellman密钥交换方案，以及介绍以其为基础的Elgamal加密方案和针对Elgamal的攻击。这两种算法的安全性建立在有限域上的离散对数计算的困难性，ECC也是很好的基于离散对数的公钥密码体制，在本文就不做详细介绍。2．离散对数问题离散对数问题是现代非对称密码体制中的一个非常重要的单向函数，很多公钥算法都基于它，简单来说，就是给定正整数x，y，n，求出正整数k（如果存在的话），使y≡xk(modn)。基于群环域说，就是指已知有限域乘法群𝐹𝑞∗中的两个元素α、β，求取x𝜖Ζ使得𝛽=𝛼𝑥,其中𝑞=𝑝𝑛,p是域的特征，n是扩张次数。如果α生成的循环群是素数阶群，则目前其上离散对数问题的求解需要亚指数时间（IndexCaculus算法）。2.1素域内的离散对数问题基于ℤ𝑝∗的DLP：给定一个阶为𝑝−1的有限循环群ℤ𝑝∗，一个本原元𝛼𝜖ℤ𝑝∗和另一个元素𝛽𝜖ℤ𝑝∗。DLP是确定满足一下条件的整数𝑥其中1≤𝑥≤𝑝的问题：𝛼𝑥≡𝛽𝑚𝑜𝑑𝑝。即使使用很小的数字，使用蛮力攻击，也很难算出x的值，因此，为了防止Pohlig-Hellman攻击，群内DLP的基数最好是素数，由于群ℤ𝑝∗的基为𝑝−1，因此人们经常会选择ℤ𝑝∗子群中基为素数的子群内的DLP，而非直接使用群ℤ𝑝∗本身。3.Diffie-Hellman密钥交换方案Diffie-Hellman协议是基于循环群的广泛使用的密钥交换方法。我们来分析𝑍𝑝∗内Diffie-Hellman密钥交换协议的工作方式。这个协议拥有两个参与者Bob和Alice，他们将建立一个共享密钥。DHKE协议由两个协议组成：Diffie-Hellman握手协议和主要协议。Diffie-Hellman握手协议：1.选择一个大素数p2.选择一个整数𝛼𝜖{2,3,……𝑝−2}。3.公开p和aDiffie-Hellman密钥交换：AliceBob选择a=𝑘𝑝𝑟,𝐴𝜖{2,…,𝑝−2}选择𝑏=𝑘𝑝𝑟,𝐵𝜖{2,…,𝑝−2}计算𝐴=𝑘𝑝𝑢𝑏,𝐴≡𝛼𝑎𝑚𝑜𝑑𝑝计算𝐵=𝑘𝑝𝑢𝑏,𝐵≡𝛼𝑏𝑚𝑜𝑑𝑝𝑘𝑝𝑢𝑏,𝐴=𝐴𝑘𝑝𝑢𝑏,𝐵=𝐵𝑘𝐴𝐵=𝑘𝑝𝑢𝑏,𝐵𝑘𝑝𝑟,𝐴≡𝐵𝑎𝑚𝑜𝑑𝑝𝑘𝐴𝐵=𝑘𝑝𝑢𝑏,𝐴𝑘𝑝𝑟,𝐵≡𝐴𝑏𝑚𝑜𝑑𝑝Alice计算𝐵𝑎≡(𝛼𝑏)𝑎≡𝛼𝑎𝑏𝑚𝑜𝑑𝑝Bob计算𝐴𝑏≡(𝛼𝑎)𝑏≡𝛼𝑎𝑏𝑚𝑜𝑑𝑝因此Alice和Bob共享会话密钥𝑘𝐴𝐵=𝛼𝑎𝑏𝑚𝑜𝑑𝑝。这个密钥可以在Alice和Bob之间建立一个安全的通信，比如将𝑘𝐴𝐵用作类似AES或3DES等对称算法的密钥。小结：Diffie-Hellman协议很容易能推广到椭圆曲线群，进而产生椭圆曲线密码学，Elgamal加密方案也与DHKE有着紧密的关联。4.Elgamal加密方案首先介绍在Elgamal加密及很多密码学方案中都非常重要的群𝑍𝑛∗。集合𝑍𝑛∗由所有𝑖=0,1,…,𝑛−1整数构成，其中满足gcd(𝑖,𝑛)=1的元素与乘法模n操作形成了阿贝尔群，且单位元为𝑒=1。4.1Elgamal加密算法参数生成：选取大素数𝑝,和本原元𝛼𝜖𝐹𝑝∗,𝑝,𝛼是公开的系统参数。随机选取整数d,1≤𝑑≤𝑝−2,计算𝛽≡𝛼𝑑𝑚𝑜𝑑𝑝。𝛽是公开的加密密钥，d是保密的解密密钥。加密：明文空间为𝐹𝑝∗×𝐹𝑝∗。对任意明文𝑚𝜖𝐹𝑝∗,随机选取整数𝑘,1≤𝑘≤𝑝−2,密文为c=(𝑐1,𝑐2),其中𝑐1≡𝛼𝑘𝑚𝑜𝑑𝑝,𝑐2≡𝑚𝛽𝑘𝑚𝑜𝑑𝑝。解密：对收到的密文(𝑐1,𝑐2)𝜖𝐹𝑝∗×𝐹𝑝∗，明文为m≡𝑐2𝑐1−𝑑𝑚𝑜𝑑𝑝。分析算法正确性：𝑐2𝑐1−𝑑≡𝑚𝛽𝑘𝛼−𝑘𝑑𝑚𝑜𝑑𝑝≡𝑚𝛼𝑘𝑑𝛼−𝑘𝑑𝑚𝑜𝑑𝑝≡𝑚𝑚𝑜𝑑𝑝4.2Elgamal签名算法参数生成：选取大素数𝑝和本原元𝛼𝜖𝐹𝑝∗,𝑝,𝛼是公开的系统参数。随机选取整数𝑑,1≤𝑑≤𝑝−2,计算𝛽≡𝛼𝑑𝑚𝑜𝑑𝑝。𝛽是公钥，d是私钥。签名：消息空间为𝑍𝑝−1,签名空间为𝐹𝑝∗×𝑍𝑝−1。对任意消息𝑚𝜖𝑍𝑝−1,随机选取与𝑝−1互素的整数𝑘,1≤𝑘≤𝑝−2,签名为s=(𝑠1,𝑠2),其中𝑠1≡𝛼𝑘𝑚𝑜𝑑𝑝,𝑠2≡𝑘−1(𝑚−𝑑𝑠1)𝑚𝑜𝑑(𝑝−1)验证：对收到的签名(𝑠1,𝑠2)𝜖𝐹𝑝∗×𝑍𝑝−1,若𝛼𝑚≡𝑠1𝑠2𝛽𝑠1𝑚𝑜𝑑𝑝则验证通过，否则验证失败。4.3Elgamal安全性分析1.消极攻击（即只监听的攻击）通过窃听到的信息𝑝,𝛼,𝛽=𝛼𝑑,𝑘𝐸=𝛼𝑖和𝑦=𝑥∙𝛽𝑖恢复明文𝑥。1.1通过找到Bob的密钥d来恢复𝑥:𝑑=log𝛼𝛽𝑚𝑜𝑑𝑝,如果成功求解DLP，则可以解密密文𝑥≡𝑦∙(𝑘𝐸𝑑)−1𝑚𝑜𝑑𝑝1.2计算Bob的私钥指数d,恢复随机指数𝑖=log𝑎𝑘𝑚𝑜𝑑𝑝，同样的如果能成功求解DLP，就可以计算出明文：𝑥≡𝑦∙(𝛽𝑖)−1𝑚𝑜𝑑𝑝。两种情况都必须求解有限循环群𝑍𝑛∗内的DLP。因此为了保证𝑍𝑛∗内Elgamal的安全性，𝑝的长度至少为1024位。2.积极攻击（攻击者会生成和篡改消息的攻击）在此就不做详细介绍。5.读书总结学习离散对数公钥算法就没有RSA那么轻松。基于离散对数问题的公钥算法是一种比RSA更稳定，安全以及更全面的算法。它由一个古老的离散对数问题而衍生出诸多算法，而且这些算法的可靠性都是基于某类域，课上的学的枯燥乏味的群环域却在应用如此光的加密算法上有很大应用，让我收获不少，具体了解了上课老师曾让我们写过的Elgamal算法，以及他的证明和常见攻击办法，由于能力有限，其中很大一部分看不太懂，这是我需要加强的地方参考文献[1]公钥密码学.黑龙江教育出版社.曹珍富著[2]深入浅出密码学——常用加密技术原理及应用.清华大学出版社.ChristofPaar,JanPelzl著[3]公钥密码学（设计原理与可证安全）.祝跃飞张亚娟著