零基础完全理解EIG加密算法

mlsily

0. 前言
上一篇写的太长了，这篇尽量短些方便阅读。
1. 算法简介

EIG加密是一种脱胎于DH加密的交换密钥加密算法。对计网有了解的对DH应该不陌生。
2.前置知识：
与RSA相同。
3. 算法原理
取质数q
取整数a,1<a<q,且a是q的原根（下方给出定义）。
取整数d,1<d<q-1
计算e=a^d mod q
公钥 kp = {q,a,e}
私钥 ks = d
加密过程
随机得到整数r 0<r<q
c1 = a^r mod q
c2 = e^r *m mod q
密文为（c1 ,c2）
由加密过程可以看出，明文内容只与c2的值有关，c1作为被加密的密钥传输，这是与DH加密算法相似的地方
解密过程
由c2 得到 m = (e^r)^-1 c2 mod q = ((a^d mod q )^r)^-1 c2 mod q = ((a^r)^d)^-1 c2 mod q = c1^-d c2 mod q

原根：对于正整数m,整数a，a和m互质，使a^k mod m = 1 成立的最小正整数k称为a模m的指数。记为ord m (a) ,若ord m(a)= φ(m),则a为模m的原根。
若a,m不互质，规定ordm(a) =0
由定义可知，a模m的指数即群（Zm*,×）x × y =xy mod m    中a 的阶，所以指数也叫阶。（输入不了完整符号，只能简单表示）
（Zm*,×）的阶为 φ(m)，根据拉格朗日定理，元素a的阶必然整除群的阶，即a的阶最大为φ(m)。这意味着a是群（Zm*,×）的生成元。
由此可知，若a 不是q的原根，将导致c1 c2的取值空间减小。

4. 生成原根
想要寻找原根用暴力枚举方法固然可行，但在实际使用中这是相当不效率的，我们可以使用一种更快速的方法来实现。
由生成元的性质可知定理：设p是奇素数，(a,p)=1， a是模p的原根的充要条件是：a^p-1/pi mod p != 1, i=1,2,...，k,其中pi 为p-1的不同素因子。
因为p是奇素数，p-1即为φ(p),对φ(p)进行素因式分解，φ(p)=x^n * y^m  
根据定理，计算a^φ(p)/y mod p 和 a^φ(p)/x mod p ，当两式都不等于1时，则a是 模p的原根。（可以有多个素因子，只要相应增加计算的式子个数即可）
已知a是模p的原根，计算a^k mod p k= 1,2,...k-1。
根据公式：ordp(a^k)=ordp(a)/(k,ordp(a)),若a是原根，当ordp(a)与k互质时，ordp(a^k)也是原根。由此可以得出其他所有的原根。

5. EIG的安全性
EIG的安全性基于离散对数方程的解只能由生成的离散对数表的方式得到，相当于遍历整个密钥空间，这是困难的。具体方法这里不给出了。
6. python语言实现EIG加密
为了增强代码的可读性，以及缩短篇幅，我们把代码分成几个部分。
我们假设已经得到了素数p。（生成方法参考RSA篇）
第一步，找到原根：
def find_prime_factors(p):                 #首先对φ(p)进行素因式分解，返回φ(p)的所有素因子
    factors = set()
    d = 2
    while d * d <= n:
        while (n % d) == 0:
            factors.add(d)
            n //= d
        d += 1
    if n > 1:
        factors.add(n)
    return factors

def generate_primitive_root(p):       #生成原根
    if p == 2:
        return 1
    phi = p - 1                                  #phi 即 φ(p)
    factors = find_prime_factors(phi)        #得到素因子
   
    for g in range(2, p):
        if all(pow(g, phi // factor, p) != 1 for factor in factors):                 #生成原根的核心部分，即检测a^φ(p)/y mod p 和 a^φ(p)/x mod p    都！=1，返回的g即是原根
            return g
    return None                                                                  #如果找不到原根则重新调用生成素数P的代码。（p是伪素数的情况）

def generate_keys(p, g):              #生成密钥
    x = random.randint(1, p-2)           # 随机生成一个整数d，即私钥。随机数生成算法比较简单，不做详细介绍，这里直接调用库函数      
    y = pow(g, x, p)             #计算公钥，即公钥 kp = {q,a,e}  此处y值即上面的e
    return (x, (p, g, y))


def encrypt(public_key,m):        #加密过程  输入参数上面返回的公钥 和明文m
    p, g, y = public_key                              
    r = random.randint(1, p-2)         #取随机数r
    c1 = pow(g, r, p)                             #c1=a^r mod q
    c2 = (m * pow(y, k, p)) % p     #c2 = e^r *m mod q
    return (c1, c2)


def decrypt(private_key, public_key, ciphertext):   #解密过程
    p, g, y = public_key               
    x = private_key                          #私钥d
    c1, c2 = ciphertext
    s = pow(c1, x, p)                    
    s_inv = mod_inverse(s, p)                   #求d的模逆，扩展欧几里得算法，上一篇有详细解释，这里直接用库函数
    m = (c2 * s_inv) % p                    # 根据c1^-d c2 mod q 解密出明文m  
    return m

7.后记
在实际的使用中，我们还需要添加一些内存处理方面的代码。例如对要加密的文本进行填充，分组等操作。在解密之后解决一些去除填充字节的问题。这并不包括在加密算法之内，这里不多赘述。

小甲鱼

内容不错丫，排版仍需努力~