同态加密介绍 1. 同态加密（Homomorphic Encryption）概念： 密文状态下对加密消息进行计算的结果再进行同态解密后的明文结果与明文数据进行加密再解密的处理结果一致。提出时间：1978年同态加密分为半同态加密和全同态加密两种。如果一个密码学算法只满足乘法同态或者加法同态，我们就称其为半同态加密，英文称为PHE（Partially Homomorphic Encryption）。常见的乘法同态算法有RSA，ElGamal等，常见的加法同态算法有Pallier、Schorr协议等如果一个密码学算法既满足乘法同态又满足加法同态，我们就称其为全同态加密，英文称为FHE（Fully Homomorphic Encryption, FHE）。全同态目前正在发展当中，进展最为火热的全同态算法有基于理想格的全同态加密算法等。2. 研究进展1978年，Rivest、Adleman（“RSA”中的“R”和“A”）和Dertouzos提出了全同态加密的构想[1]，自此成为了密码学研究领域的一个公开难题。目前，同态加密算法主要分为半同态加密和全同态加密两大类。半同态加密主要包括以RSA算法[2]和ElGamal算法[3]为代表的乘法同态加密、以Paillier算法[4]为代表的加法同态加密以及以Boneh-Goh-Nissim方案[5]为代表的有限次数全同态加密；全同态加密算法主要包括以Gentry方案6为代表的第一代方案、以BGV方案[8]和BFV方案9为代表的第二代方案、以GSW方案[11]为代表的第三代方案以及支持浮点数近似计算的CKKS方案[12]等等。上述方案及其基本特性和应用情况总览如表1所示。表1：各类同态加密算法类型 算法时间说明实际应用半同态加密乘法同态RSA算法1977非随机化加密，具有乘法同态性的原始算法面临选择明文攻击在非同态场景中应用广泛 ElGamal算法1985随机化加密DSS数字签名标准基于ElGamal数字签名算法的变体 加法同态Paillier算法1999应用最为成熟联邦学习 有限次数全同态Boneh-Goh-Nissim方案2005仅支持1次乘法同态运算/全同态加密 Gentry方案2009第一代全同态加密，性能较差/ BGV方案2012第二代全同态加密，性能相对较好IBM HElib开源库 BFV方案2012第二代全同态加密，与BGV类似微软SEAL开源库 GSW方案2013第三代全同态加密，基于近似特征向量TFHE开源库 CKKS方案2017可实现浮点数近似计算，适合机器学习建模场景HElib和SEAL3. 主流方法1、半同态加密算法满足有限运算同态性而不满足任意运算同态性的加密算法称为半同态加密。典型的半同态加密特性包括乘法同态、加法同态、有限次数全同态等。（1）乘法同态加密算法在实际应用中，密文乘法同态性的需求场景不多，因此乘法同态性通常偶然存在于已有的经典加密算法中。满足乘法同态特性的典型加密算法包括1977年提出的RSA公钥加密算法和1985年提出的ElGamal公钥加密算法等。① RSA算法RSA算法是最为经典的公钥加密算法，至今已有40余年的历史，其安全性基于大整数分解困难问题。在实际应用中，RSA算法可采用RSA_PKCS1_PADDING、RSA_PKCS1_OAEP_PADDING等填充模式，根据密钥长度（常用1024位或2048位）对明文分组进行填充，而只有不对明文进行填充的原始RSA算法才能满足乘法同态特性。由于原始的RSA不是随机化加密算法，即加密过程中没有使用随机因子，每次用相同密钥加密相同明文的结果是固定的。因此，利用RSA的乘法同态性实现同态加密运算会存在安全弱点，攻击者可能通过选择明文攻击得到原始数据。② ElGamal算法ElGamal算法是一种基于Diffie-Hellman离散对数困难问题的公钥密码算法，可实现公钥加密和数字签名功能，同时满足乘法同态特性。ElGamal是一种随机化加密算法，即使每次用相同密钥加密相同明文得到的密文结果也不相同，因此不存在与RSA算法类似的选择明文攻击问题，是ISO同态加密国际标准中唯一指定的乘法同态加密算法。（2）加法同态加密算法Paillier算法是1999年提出的一种基于合数剩余类问题的公钥加密算法，也是目前最为常用且最具实用性的加法同态加密算法，已在众多具有同态加密需求的应用场景中实现了落地应用，同时也是ISO同态加密国际标准中唯一指定的加法同态加密算法。此外，由于支持加法同态，所以Paillier算法还可支持数乘同态，即支持密文与明文相乘。（3）有限全同态加密算法2005年提出的Boneh-Goh-Nissim方案是一种基于双线性映射的公钥密码方案，支持任意次加法同态和一次乘法同态运算。方案中的加法同态基于类似Paillier算法的思想，而一次乘法同态基于双线性映射的运算性质。由于双线性映射运算会使得密文所在的群发生变化，因此仅能支持一次乘法同态运算，但仍支持对乘法后的密文进一步作加法同态运算。2、全同态加密算法满足任意运算同态性的加密算法称为全同态加密。由于任何计算都可以通过加法和乘法门电路构造，所以加密算法只要同时满足乘法同态和加法同态特性就称其满足全同态特性。（1）主流算法全同态加密算法的发展起源于2009年Gentry提出的方案，后续方案大多基于格代数结构构造。目前已在主流同态加密开源库中得到实现的全同态加密算法包括BGV方案、BFV方案、CKKS方案等。① 第一代全同态加密方案——Gentry方案Gentry方案是一种基于电路模型的全同态加密算法，支持对每个比特进行加法和乘法同态运算。Gentry方案的基本思想是构造支持有限次同态运算的同态加密算法并引入“Bootstrapping”方法控制运算过程中的噪音增长，这也是第一代全同态加密方案的主流模型。 “Bootstrapping”方法通过将解密过程本身转化为同态运算电路，并生成新的公私钥对对原私钥和含有噪音的原密文进行加密，然后用原私钥的密文对原密文的密文进行解密过程的同态运算，即可得到不含噪音的新密文。但是，由于解密过程本身的运算十分复杂，运算过程中也会产生大量噪音，为了给必要的同态运算需求至少预留足够进行一次乘法运算的噪音增长空间，需要对预先解密电路进行压缩简化，即将解密过程的一些操作尽量提前到加密时完成。② 第二代全同态加密方案——BGV/BFV方案Gentry方案之后的第二代全同态加密方案通常基于LWE/RLWE假设，其安全性基于代数格上的困难问题，典型方案包括BGV方案和BFV方案等。BGV（Brakerski-Gentry-Vaikuntanathan）方案是目前主流的全同态加密算法中效率最高的方案。在BGV方案中，密文和密钥均以向量表示，而密文的乘积和对应的密钥乘积则为张量，因此密文乘法运算会造成密文维数的爆炸式增长，导致方案只能进行常数次的乘法运算。BGV方案采用密钥交换技术控制密文向量的维数膨胀，在进行密文计算后通过密钥交换将膨胀的密文维数恢复为原密文的维数。同时，BGV方案可采用模交换技术替代Gentry方案中的“Bootstrapping”过程，用于控制密文同态运算产生的噪声增长，而不需要通过复杂的解密电路实现。因此，在每次进行密文乘法运算后，首先需要通过密钥交换技术降低密文的维数，然后通过模交换技术降低密文的噪声，从而能够继续进行下一次计算。BFV（Brakerski/Fan-Vercauteren）方案是与BGV方案类似的另一种第二代全同态加密方案，同样可基于LWE和RLWE构造。BFV方案不需要通过模交换进行密文噪声控制，但同样需要通过密钥交换解决密文乘法带来的密文维数膨胀问题。目前，最为主流的两个全同态加密开源库HElib和SEAL分别实现了BGV方案和BFV方案。③ 第三代全同态加密方案——GSW方案GSW（Gentry-Sahai-Waters）方案是一种基于近似特征向量的全同态加密方案。该方案基于LWE并可推广至RLWE，但其的性能不如BGV方案等其他基于RLWE的方案。GSW方案的密文为矩阵的形式，而矩阵相乘并不会导致矩阵维数的改变，因此GSW方案解决了以往方案中密文向量相乘导致的密文维数膨胀问题，无需进行用于降低密文维数的密钥交换过程。④ 浮点数全同态加密方案——CKKS方案CKKS（Cheon-Kim-Kim-Song）方案是2017年提出的一种新方案，支持针对实数或复数的浮点数加法和乘法同态运算，得到的计算结果为近似值，适用于机器学习模型训练等不需要精确结果的场景。由于浮点数同态运算在特定场景的必要性，HElib和SEAL两个全同态加密开源库均支持了CKKS方案。全同态工程实现开源工具：HElibSEAL发展现状目前，全同态加密算法仍处于以学术界研究为主的发展阶段，现有方案均存在计算和存储开销大等无法规避的性能问题，距离高效的工程应用还有着难以跨越的鸿沟，同时面临国际和国内相关标准的缺失。因此，在尝试同态加密落地应用时，可考虑利用Paillier加法同态加密算法等较为成熟且性能较好的半同态加密算法，解决只存在加法或数乘同态运算需求的应用场景，或通过将复杂计算需求转化为只存在加法或数乘运算的形式实现全同态场景的近似替代。[1] Rivest R L, Adleman L, Dertouzos M L. On data banks and privacy homomorphisms[J]. Foundations of secure computation, 1978, 4(11): 169-180.[2] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.[3] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE transactions on information theory, 1985, 31(4): 469-472.[4] Paillier P. Public-key cryptosystems based on composite degree residuosity classes[C]//International conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 1999: 223-238.[5] Boneh D, Goh E J, Nissim K. Evaluating 2-DNF formulas on ciphertexts[C]//Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2005: 325-341.[6] Gentry C. Fully homomorphic encryption using ideal lattices[C]//Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009: 169-178.[7] Gentry C, Halevi S. Implementing gentry’s fully-homomorphic encryption scheme[C]//Annual international conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2011: 129-148.[8] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3): 1-36.[9] Brakerski Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2012: 868-886.[10] Fan J, Vercauteren F. Somewhat Practical Fully Homomorphic Encryption[J]. IACR Cryptology ePrint Archive, 2012, 2012: 144.[11] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2013: 75-92.[12] Cheon J H, Kim A, Kim M, et al. Homomorphic encryption for arithmetic of approximate numbers[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2017: 409-437.[13] Smart N P, Vercauteren F. Fully homomorphic SIMD operations[J]. Designs, codes and cryptography, 2014, 71(1): 57-81.[14] Gentry C, Halevi S, Smart N P. Homomorphic evaluation of the AES circuit[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2012: 850-867.

椭圆曲线加密算法原理（ECC） 1. 椭圆曲线加密算法椭圆曲线加密算法，即：Elliptic Curve Cryptography，简称ECC，是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA，ECC优势是可以使用更短的密钥，来实现与RSA相当或更高的安全。据研究，160位ECC加密安全性相当于1024位RSA加密，210位ECC加密安全性相当于2048位RSA加密。椭圆曲线在密码学中的使用，是1985年由Neal Koblitz和Victor Miller分别独立提出的。2. 理论基础2.1 有限域2.1.1 域在一个整数集合中，里面的整数进行加法，减法，乘法，除法产生的结果都在这个集合中，则称这个集合为域2.1.2 有限域椭圆曲线是连续的，并不适合用于加密；所以必须把椭圆曲线变成离散的点，要把椭圆曲线定义在有限域上。而椭圆曲线密码所使用的椭圆曲线是定义在有限域内，有限域最常见的例子是有限域GFppp，指给定某质数p，由0,1,2...p-1共p个元素组成的整数集合中加法、二倍运算。例如$GF_{233}$就是$$ y^{2}=(x^{3}+7)\ mod \quad 233 $$2.2 定义椭圆曲线的运算规则2.2.1 加法过曲线上的两点A、B画一条直线，找到直线与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A+B，即为加法。如下图所示：A + B = C2.2.2 二倍运算上述方法无法解释A + A，即两点重合的情况。因此在这种情况下，将椭圆曲线在A点的切线，与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A + A，即2A，即为二倍运算。2.2.3 正负取反将A关于x轴对称位置的点定义为-A，即椭圆曲线的正负取反运算。如下图所示：2.2.4 无穷远点如果将A与-A相加，过A与-A的直线平行于y轴，可以认为直线与椭圆曲线相交于无穷远点。综上，定义了A+B、2A运算，因此给定椭圆曲线的某一点G，可以求出2G、3G（即G + 2G）、4G......。即：当给定G点时，已知x，求xG点并不困难。反之，已知xG点，求x则非常困难。此即为椭圆曲线加密算法背后的数学原理。2.3 有限域上的椭圆曲线运算椭圆曲线要形成一条光滑的曲线，要求x,y取值均为实数，即实数域上的椭圆曲线。但椭圆曲线加密算法，并非使用实数域，而是使用有限域。按数论定义，有限域GFppp指给定某个质数p，由0、1、2......p-1共p个元素组成的整数集合中定义的加减乘除运算。假设椭圆曲线为y² = x³ + x + 1，其在有限域$GF_{23}$上时，写作：$$ y2 ≡ x3 +x + 1 mod 23 \\ y^{2}\ \equiv \ x^{3}\ +x\ +\ 1\ mod 23 $$此时，椭圆曲线不再是一条光滑曲线，而是一些不连续的点，如下图所示。以点(1,7)为例，7² ≡ 1³ + 1 + 1 ≡ 3 (mod 23)。如此还有如下点：(0,1) (0,22)　　(1,7) (1,16)　　(3,10) (3,13)　　(4,0)　　(5,4) (5,19)　　(6,4) (6,19)　　(7,11) (7,12)　　(9,7) (9,16)　　(11,3) (11,20)　　等等。另外，如果P(x,y)为椭圆曲线上的点，则-P即(x,-y)也为椭圆曲线上的点。如点P(0,1)，-P=(0,-1)=(0,22)也为椭圆曲线上的点。2.3.1 计算xG相关公式如下：　　有限域GF(p)上的椭圆曲线y² = x³ + ax + b，若P(Xp, Yp), Q(Xq, Yq)，且P≠-Q，则R(Xr,Yr) = P+Q 由如下规则确定：$$ Xr\quad =\quad (λ^{2}\ -\ Xp\ -\ Xq)\ mod \quad p　　 $$$$ Yr \quad = \quad (λ(Xp\ -\ Xr)\ -\ Yp)\ mod\quad p　　 $$其中 :$$ λ = \frac{Yq - Yp} {Xq - Xp} (mod \quad p)（若P≠Q） $$$$ λ = \frac{3Xp^{2} + a} {2Yp} (mod \quad p)（若P=Q） $$因此，有限域GF(23)上的椭圆曲线y² ≡ x³ + x + 1 (mod 23)，假设以(0,1)为G点，计算2G、3G、4G...xG等等，方法如下：计算2G：λ = (3x0² + 1)/2x1 mod 23 = (1/2) mod 23 = 12　　Xr = (12² - 0 - 0) mod 23 = 6　　Yr = (12(0 - 6) - 1) mod 23 = 19　　即2G为点(6,19)计算3G：　　3G = G + 2G，即(0,1) + (6,19)　　λ = (19 - 1)/(6 - 0) mod 23 = 3　　Xr = (3² - 0 - 6) mod 23 = 3　　Yr = (3(0 - 3) - 1) mod 23 = 13　　即3G为点(3, 13)同理计算4G、5G...xG，分布如下图：　　2.3.2 关于标量乘法的计算方法根据以上，计算kG，即GF(k)很麻烦，这个时候如果用标量乘法的计算方法的话，就很简单，只需要先做倍数再做加法就可以得到结果。假设k=152，其对应的二进制是10010111，而二进制数字可以转化为：$$ 151 = 1*2^{7} + 0*2^{6} + 0*2^{5} + 1*2^{4} + 0*2^{3} + 1*2^{2} + 1*2^{1} + 1*2^{0} $$$$ 151P = 1*2^{7}P + 1*2^{4}P + 1*2^{2}P + 1*2^{1}P + 1*2^{0}P $$3. 椭圆曲线加解密算法原理选一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点作为基点P选定一个大数k作为私钥，并生成公钥:$Q=kP$加密：选择随机数r，将消息M生成密文，密文是一个点对，即:$C=(rP,M+rQ)$解密：$M=k(rP)+M+rQ $

关于分数和负数的求模方法 1. 分数的求模1.1 计算方法$$ \frac{a}{b} (mod N) $$$$ c ≡ \frac{a}{b} (mod N) $$$$ c * b (mod N) ≡ a$$1.2 例子比如计算：$\frac{1}{3}\ mod\ 4$，即令$c\ \equiv \frac{1}{3}\ mod\ 4$，两边相乘3，得：$$3c\ mod\ 4\ \equiv \ 1$$所以c等于32. 负数的求模2.1 计算方法比如A mod B,其中A为负数即:$A(modB) == A-B\lfloor \frac{A}{B} \rfloor$2.2 例子比如$a\ =\ -73\ mod\ 23 $即：$a = -72 - 23\lfloor \frac{-73}{23}\rfloor$其中-73/23 = -3.17,所以-73/23向下取整等于-4所以a等于-72 + 4*23 == 19

密码学加密算法 1. 什么是加密算法? 它的应用领域和应用地位是什么？算法加密是目前信息互联行业前后端开发必须应用的算法，它的目的就是信息在传输和解读上提高安全性，让设定的群体读到我传递的内容，而不被别人窃取到我的传递信息。算法加密和数字签名是前后端开发绕不开的技术问题。它要解决的是用户登入、交易、信息通讯、oauth等应用场景提出的技术问题，给使用者提供更完善的服务。2. 现代加密算法2.1 数字签名数字签名目前可以使用两种方法，分别是对称密码学和公钥密码学，消息认证码（MAC）使用对称密钥中，比较知名的应该就是消息认证码（MAC），其签名方式就是：消息在发送之前，通过一个单向函数和一个密钥（hash值=hash(data,key)），生成一个hash值（这个hash值就是消息认证码MAC），然后将信息和hash值一起发送出去，接收者通过相同的单向hash函数和密钥进行加密，比较接收到的hash与加密后得到的hash值是否相同。数字证书签名（CA证书）数字证书签名涉及到PKI公钥基础设施，其中CA进行证书的签发数字证书，发送者通过用一个hash函数对信息进行加密得到hash值（hash值=hash(data)），然后用自己的私钥对hash值进行加密，得到一个签名序列C1，最后发送者将信息和这个签名序列一起发送出去，接收者通过CA根，获得发送者的数字证书，（数字证书是一个由用户身份和这个用户的公钥组成的），接收者通过相同的hash函数对信息进行加密得到hash值，然后将这个hash值与发送者的公钥进行加密得到签名序列C2，然后对比C1和C2是否相同2.2 对称加密算法对称加密算法就是加密密钥和解密密钥是相同的，这种加密技术目前被广泛采用。常见的对称加密算法则包含DES、3DES、AES等。 也可以根据对称密码的加密原理分为分组加密和流密码加密。 对称式加密使用便捷，效率高，但也有其缺陷：密钥长度不够，推荐1024Bit或更高。明文存储密使用弱随机数，攻击者很容易猜测。密钥分发困难，难以保证在传输中密钥不被泄露（可使用公钥传输对称密钥或者使用密钥协商算法生成密钥）3、非对称加密算法与区块链非对称加密算法非对称加密(也称为公钥加密)，Public-key Cryptography)就是加密和解密所使用的不是同一个密钥，通常有两个密钥，称为公钥(publickey)和私钥(privatekey)，它们两个必需配对使用，否则不能打开加密文件。这里的“公钥”指的是公共密钥可以公布的，“私钥”不仅可以通过持有人了解。这就是优点所在，因为如果加密文件是通过网络传输的，对称加密可能很难告诉它的密钥，而且任何人都可以窃听它，不管使用什么方法。非对称加密方法有两个密钥，并且“公钥”可以公开，因此接收者只能在解密时使用他的私钥。这样就避免了密钥传输的安全问题。区块链加密算法运用了 哈希函数 和 椭圆曲线公钥密码技术 在内的大量现代密码学技术。这些密码学技术被用于设计基于工作量证明的共识算法并识别用户。哈希函数 ：是一类数学函数，可以在有限合理的时间内，将任意长度的消息压缩为固定长度的二进制串，其输出值称为哈希值，也称为散列值。　以哈希函数为基础构造的哈希算法，在现代密码学中扮演着重要的角色，常用于实现数据完整性和实体认证，同时也构成多种密码体制和协议的安全保障。碰撞是与哈希函数相关的重要概念，体现着哈希函数的安全性，所谓碰撞是指两个不同的消息在同一个哈希函数作用下，具有相同的哈希值。哈希函数的安全性是指在现有的计算资源(包括时间、空间、资金等)下，找到一个碰撞是不可行的。常见的此类算法有RSA、ECC等。值得一提的是RSA基于素数因式分解数学理论的困难度，安全性非常高。但是此类算法安全性虽高，但是读取速度慢，只适用小数据量的加密存取。在量子计算机面前，对于大整数分解这样的难题可能只需要几天或者几年就可以破解，所以在以后这样的公钥加密算法可能是不安全的4、散列加密算法是一个密码散列函数家族，是FIPS所认证的安全散列算法。能计算出一个数字消息所对应到的，长度固定的字符串(又称消息摘要)的算法。且若输入的消息不同，它们对应到不同字符串的机率很高。代表算法即是SHA算法系列和MD5等。由于算法的特殊性，哈希算法多用于验证加密信息的完整性。加密手段1、同态加密全同态加密是2009年IBM的Craig Gentry首次提出了一种基于理想格的全同态算法，如果一个算法既能满足加法同态，也能满足乘法同态，就称为全同态算法。同态加密是一种特殊的加密方法，它允许对密文进行处理，结果仍然是加密的，即直接处理密文，其结果与明文相同。从代数的角度讲，即同态性。在代数中，同态包括加法、乘法、减法和除法四种。如果同时满足加法同态和乘同态，则表示代数同态。同时满足四个同态称为算术同态。 同态加密最早是1978年，由Ron Rivest、Leonard Adleman和Michael L德图佐斯提出，但直到2009年，第一个“全同态”算法，才被克雷格(Craig Gentry)证明。常见的算法中，Paillier算法和Benaloh算法仅满足加法同态，RSA算法和ElGamal算法只满足乘法同态的算法。而Gentry算法则是全同态的。 云时代同态加密的重要性非常显着。它真的从根本上解决问题，当数据和业务保密委托给第三方，如各种云计算应用。目前，从安全角度来看，用户不敢将敏感信息直接放在第三方云上进行处理。如果您有一种更实用的同态加密技术，那么您可以放心地使用各种云服务。2、函数加密同态加密保护的是数据本身，而函数加密顾名思义保护的是处理函数本身，即让第三方看不到处理过程的前提下，对数据进行处理。函数加密的方法是：任何人可以使用公钥PK对明文m进行加密得到密文Enc(m)，密钥的持有者对某个函数 F 颁发一个KEY, 任何拥有KEY和密文Enc(m)的一方，都可以计算F(m), 但是除了F(m)外不能获得关于m的任何信息。

EIGamal加密算法 1. ElGamal算法简介ElGamal算法是由Tather ElGamal在1985年提出的，它是一种基于离散对数难题的加密体系，与RAS算法一样，既能用于数据加密，也能用于数字签名。ElGamal算法是基于因数分解，而ElGamal算法是基于离散对数问题。与RSA算法相比，ElGamal算法哪怕是使用相同的私钥，对相同的明文进行加密，每次加密后得到的签名也各不相同，有效的防止了网络中可能出现的重放攻击。2. ElGamal算法原理2.1 ElGamal密钥生成（1）随机选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。模p的本原元就是满足：${\alpha}^{\phi(p)}\equiv 1 \ mod \ p$（2）随机选择一个d作为私钥密钥,d为整数，1≤d≤p-1 。（3）计算:$ \beta=\alpha^d\ mod\ p $ 取β为公钥。2.2 ElGamal加密（1）对于明文M加密，随机地选取一个整数k，1≤k≤p-2（2）$ C1\ ＝\ α^k\ mod\ p $（3）$ C2\ ＝\ Mβ^k\ mod\ p $（4）密文为（C1,C2）2.3 ElGamal解密由密文可得明文M:$ M\ =\ \frac{C2}{C1^d}\ mod\ p $3. 算法实现3.1 Python程序import random # 欧拉函数 def phi(n): listN = [] #符合条件的质因子 for i in range(2,n+1): if n%i == 0: # n = 16 i = 2，4，6，8，16 flag = True for j in range(2,i): if i%j == 0: flag = False break if flag: listN.append(i) # 当i是质数就存入列表 # 返回值 result = n for i in range(len(listN)): result *= 1-(1/listN[i]) return int(result) # 求分数的模p同余 a/b mod p def mod(a,b,n): """ 分数0<a/b<1 求解a/b mod n的结果 """ # 统一b为正数 if b < 0: b = -b a = -a # 统一a为非负数 while a < 0: a += p a = a % p i = 1 while True: if i*b % n == a: return i i += 1 def get_a(p:int): result_list = [] for a in range(0,p): # print("a:",a) if a**phi(p)%p == 1: result_list.append(a) # print(result_list) return result_list[random.randint(0,len(result_list)-1)] def gen_EIGamal_key(p): a = get_a(p) # alphi d = random.randint(1,p-1) b = a**d % p # beta return b,d,a #公钥和私钥 def EIGamal_encode(p:int,a:int,public_key:int,M:int): k = random.randint(1,p-2) # 加密随机数 随机选取一个整数k,使得1<=k<=p-2 C1 = int(a**k) % p C2 = int(M*int(public_key**k)) % p return (C1,C2) def EIGamal_decode(p:int,private_key:int,C:int): decode = mod(C[1],C[0]**private_key,p) return decode p = 1235 M1 = 1231 public_key,private_key,a = gen_EIGamal_key(p) C = EIGamal_encode(p,a,public_key,M1) M = EIGamal_decode(p,private_key,C) print("密文：",C) print("明文：",M)3.2 算法输出结果

Diffie-Hellman密钥协商算法 1. 概述Diffie-Hellman密钥协商算法主要解决秘钥配送问题，本身并非用来加密用的；该算法其背后有对应数学理论做支撑，简单来讲就是构造一个复杂的计算难题，使得对该问题的求解在现实的时间内无法快速有效的求解（computationally infeasible ）。理解Diffie-Hellman密钥协商的原理并不困难，只需要一点数论方面的知识既可以理解，主要会用到简单的 模算术运算、本原根、费马小定理、离散对数 等基础数论的知识。在现代密码学中的基础数论知识梳理中已经对这些知识做了必要的总结。2. 从何而来DH密钥协商算法在1976年在Whitfield Diffie和Martin Hellman两人合著的论文New Directions in Cryptography（Section Ⅲ PUBLIC KEY CRYPTOGRAPHY）中被作为一种公开秘钥分发系统(public key distribution system)被提出来。原文的叙述过程比较简单，但基本阐述了算法的原理以及其可行性。在该论文中实际上提出了一些在当时很有创新性的思想。原论文重点讨论两个话题：（1）在公网通道上如何进行安全的秘钥分派。（2）认证（可以细分为消息认证和用户认证）。为了解决第一个问题，原文提出两种方法：公钥加密系统(public key cryptosystem)和秘钥分发系统(public key distribution system)。对于公钥加密系统，原文只是勾画了一种比较抽象的公钥加密系统的概念模型，重点是加解密采用不同的秘钥，并总结了该系统应该满足的一些特性，相当于是一种思想实验，并没有给出具体的算法实现途径，但这在当时应该来说已经足够吸引人。后来RSA三人组（Ron Rivest、Adi Shamir 和 Leonard Adleman）受此启发，经过许多轮失败的尝试后，于第二年在论文A Method for Obtaining Digital Signatures and Public-Key Cryptosystems中提出了切实可行且很具体的公钥加密算法--RSA公钥加密算法。而对于秘钥分发系统，就是本文的DH秘钥协商算法。为了解决第二个问题，原文通过单向函数（one-way function）来解决，这就是单向认证的问题。另外作者还讨论了这些密码学问题之间的关联性以及如何相互转化。比如一个安全的密码系统（可以防御明文攻击）可以用来生成一个的单向函数、公钥加密系统可以用来作为单向认证、陷门密码系统可以用来生成一个公钥加密系统。数学难题的计算复杂度被当成一种保障密码学安全问题的有效工具被利用起来，这一重要思想贯穿现代密码学的许多加密算法。3.密钥的产生过程假设由A、B、C想协商产生一个共用的密钥，首先三方需要协商确定一个大的素数n和一个整数g（这两个数可以公开）根据协商密钥的主体数量，可以确定需要协商的轮数，有N个主体，需要协商N-1轮。3.1 第一轮信息交换A选取一个大的随机整数x，并且发送$X\ =\ g^x\ mod\ n $给B B选取一个大的随机整数y，并且发送$Y\ =\ g^y\ mod\ n $给C C选取一个大的随机整数z，并且发送$Z\ =\ g^z\ mod\ n $给A3.2 第二轮信息交换A计算$X1\ =\ Z^x\ mod\ n $给B B计算$Y1\ =\ X^y\ mod\ n $给C C计算$Z1\ =\ Y^z\ mod\ n $给A3.3 计算密钥A计算$k1\ =\ Z1^x\ mod\ n$ B计算$k2\ =\ X1^y\ mod\ n$ C计算$k3\ =\ Y1^z\ mod\ n$ $Key\ =\ k1\ =\ k2\ =\ k3$，为共同协商出来的密钥，A、B、C将用协商好的密钥进行数据加密通信。4.算法的实现import random def diffie_hellman(): n = 173 g = random.randint(1,10) x = random.randint(1,10) y = random.randint(1,10) z = random.randint(1,10) X = g**x % n Y = g**y % n Z = g**z % n X1 = Z**x % n Y1 = X**y % n Z1 = Y**z % n k1 = Z1**x % n k2 = X1**y % n k3 = Y1**z % n print('n g x y z:',n,g,x,y,z) print("A 要给 B 发送的数据 X:",X) print("B 要给 C 发送的数据 Y:",Y) print("C 要给 A 发送的数据 Z:",Z) print("A 要给 B 发送的数据 X1:",X1) print("B 要给 C 发送的数据 Y1:",Y1) print("B 要给 C 发送的数据 Z1:",Z1) print(k1,k2,k3) diffie_hellman()输出n g x y z: 173 3 9 4 10 A 要给 B 发送的数据 X: 134 B 要给 C 发送的数据 Y: 81 C 要给 A 发送的数据 Z: 56 A 要给 B 发送的数据 X1: 92 B 要给 C 发送的数据 Y1: 85 B 要给 C 发送的数据 Z1: 138 169 169 169A、B、C共同协商出来的密钥为8D-H算法不足之处Diffie-Hellman算法并不能防止假冒攻击，当主体存在篡改时，密钥将会被泄露，所以Diffie-Hellman算法不是一个完美的密钥协商算法，这个时候可以使用EKE协议进行密钥的协商。