ELGamal公钥体制加密加签

发表于 更新于 分类于
密码学的最后一次作业，大概

ELGamal公钥体制加密加签

第4章 公钥密码体制.ppt 下载

第7章 数字签名.ppt 下载

安全性

注意事项：（关于ElGamal数字签名体制的参数p）

  • p的选择与在Zp中计算离散对数的算法有直接关系。从目前的计算水平来看，p至少应该是二进制512位的素数，从长期安全性考虑，应使用1024位或更长的素数。

  • p-1最好有大的素因子

  • 私钥x最好是Zp的素数阶子群的生成元。

关键点：

  • 不要泄露随机数k，否则，根据：

$$
s\equiv(M-x*r)k^{-1}\pmod{p-1}
$$

​ 可以计算出私钥
$$
x\equiv(M-x*k)r^{-1}\pmod{p-1}
$$

  • 不要使用同一个随机数k给两个不同的消息签名

大素数生成

知识点：

  • Miller-Rabin 素性检测

  • Miller-Rabin 测试

function.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import math
import random


def fastExpMod(b, e, m):
    """
    模N大数的幂乘的快速算法
    b底数，e幂，m大数N
    """
    result = 1
    e = int(e)
    while e != 0:
        if e % 2 != 0:  # 按位与
            e -= 1
            result = (result * b) % m
            continue
        e >>= 1
        b = (b * b) % m
    return result
    # 测试案例
    # c = fastExpMod(3,22,12)
    # print(c) 9


def miller_rabin_test(n):
    """针对随机取得p的素性检测"""
    p = n - 1  # p为要检验得数
    r = 0
    while p % 2 == 0:  # 最后得到为奇数的p(即m)
        r += 1
        p /= 2
    b = random.randint(2, n - 2)  # 随机取b=（0.n）
    # 如果情况1    b得p次方  与1  同余  mod n
    if fastExpMod(b, int(p), n) == 1:
        return True  # 通过测试,可能为素数
    # 情况2  b得（2^r  *p）次方  与-1 (n-1) 同余  mod n
    for i in range(0, 7):  # 检验六次
        if fastExpMod(b, (2 ** i) * p, n) == n - 1:
            return True  # 如果该数可能为素数，
    return False  # 不可能是素数


def create_prime_num(start, end):
    """生成大素数 start-end为素数取值区间"""
    while True:
        n = random.randint(start, end)
        if n % 2 != 0:
            found = True
            # 如果经过10次素性检测，那么很大概率上，这个数就是素数
            for i in range(0, 10):
                if miller_rabin_test(n):
                    pass
                else:
                    found = False
                    break
            if found:
                return n


def ex_gcd(a, mod):
    """扩展欧几里德算法，内置"""
    if math.gcd(a, mod) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, mod
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % mod

加密

ELGamal.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from funtion import *


def get_key():
    """生成密钥，p和g的随机范围可调整"""
    # todo 可选：0<m<p用为ascii码表表长为255，此处将start初始化为255
    start = 255  # ascii长度为起始，保证输入数m一定小于p
    end = 1024  # p的最大取值范围
    p = create_prime_num(start, end)
    # todo 可选：g的随机取值范围
    g = random.randint(0, 100)  # g是一个本原元
    x = random.randint(0, p)
    y = g ** x % p
    return {'pk': (p, g, y), 'sk': (p, g, y, x)}


def encode(m, pk):
    """加密算法0<m<p"""
    p, g, y = pk
    k = random.randint(0, p)
    c1 = g ** k % p
    c2 = (m * (y ** k)) % p
    return c1, c2


def decode(c, sk):
    """解密算法"""
    c1, c2 = c
    p, g, y, x = sk
    m = c2 * ex_gcd(c1 ** x, p) % p
    return m


if __name__ == "__main__":
    """主函数"""
    k = get_key()
    print(k)
    raw_m = input("请输入待加密字符串：\n> ")
    m = list(map(ord, raw_m))
    c = []
    for i in m:
        c_unit = encode(i, k['pk'])
        c.append(c_unit)
    print('密文', c)
    m = []
    for i in c:
        m_unit = decode(i, k['sk'])
        m.append(m_unit)
    print('明文', m)
    print(''.join(list(map(chr, m))))

运行

1
2
3
4
5
6
7
8
9
"G:\python environment\python.exe" "G:/Code/IntelliJ Pycharm/Cryptology/ElGamal/ELGamal.py"
{'pk': (829, 89, 795), 'sk': (829, 89, 795, 579)}
请输入待加密字符串：
> mednight4
密文 [(221, 605), (131, 383), (269, 346), (688, 505), (597, 77), (394, 485), (223, 178), (89, 201), (616, 665)]
明文 [109, 101, 100, 110, 105, 103, 104, 116, 52]
mednight4

Process finished with exit code 0

加签

ELGamal_sig.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from funtion import *


def get_key():
    """生成加签的私钥和公钥，p和g的随机范围可调整"""
    # todo 可选：p和g的随机取值范围
    p = create_prime_num(0, 1024)
    g = random.randint(0, p)
    x = random.randint(1, p - 1)
    y = g ** x % p
    return {'pk': (p, g, y), 'sk': (p, g, y, x)}


def value_k(p):
    """选择k时，k应该与p-1互素，否则没有逆元"""
    k_list = []
    for i in range(1, p - 1):
        if math.gcd(i, p - 1) == 1:
            k_list.append(i)
    return k_list


def sig(m, sk):
    """签名算法"""
    p, g, y, x = sk
    k = random.choice(value_k(p))
    r = (g ** k) % p
    s = ((m - x * r) * ex_gcd(k, p - 1)) % (p - 1)
    return r, s


def check(m, sig, pk):
    r, s = sig
    p, g, y = pk
    return (y ** r) * (r ** s) % p == g ** m % p


if __name__ == "__main__":
    """主函数"""
    print("{'pk': (p, g, y), 'sk': (p, g, y, x)}")
    k = get_key()
    print(k)
    raw_m = input("请输入待签名字符串：\n> ")
    m = list(map(ord, raw_m))
    sign = []
    for i in m:
        sign_unit = sig(i, k['sk'])
        sign.append(sign_unit)
    print('签名', sign)
    tip = '验签成功'
    for i,s in zip(m,sign):
        if not check(i, s, k['pk']):
            tip = '验签失败'
            break
    print(tip)

运行

1
2
3
4
5
6
7
8
9
"G:\python environment\python.exe" "G:/Code/IntelliJ Pycharm/Cryptology/ElGamal/ELGamal_sig.py"
{'pk': (p, g, y), 'sk': (p, g, y, x)}
{'pk': (101, 31, 58), 'sk': (101, 31, 58, 63)}
请输入待签名字符串：
> mednight4
签名 [(54, 11), (24, 83), (19, 37), (78, 24), (37, 86), (25, 24), (81, 59), (24, 88), (88, 92)]
验签成功

Process finished with exit code 0