信息计算19级2班26号何祥宝

何祥宝

  ECC-椭圆曲线加密算法

K（K为公开密钥），G（G为基点）为椭圆曲线ep（a,b）上一点，K=kg，n为G的阶，k为小于n的整数（K<n为私有密钥），则给定的k和G，根据加法法则，计算K很容易。

通信加密过程为：

a选定一条椭圆曲线，并选取曲线上一点作为基点

a选择一个私有密钥，并生成一个公开密钥

a将椭圆曲线，基点和公开密钥发给b

b收到信息后，将待传输明文编码到椭圆曲线上一点，并产生一个随机整数

b计算一个点并传给a，a根据信息解出的结果是b选择曲线上的点，再对这个点解码就可以得到明文

1. def get_inverse(mu, p):
   
2.     for i in range(1, p):
   
3.         if (i * mu) % p == 1:
   
4.             return i
   
5.     return 2
   
6. def get_gcd(zi, mu):
   
7.     if mu:
   
8.         return get_gcd(mu, zi % mu)
   
9.     else:
   
10.         return zi
    
11. def get_np(x1, y1, x2, y2, a, p):
    
12.     flag = 1  # 定义符号位（+/-）
    
13.     # 如果 p=q  k=(3x2+a)/2y1mod p
    
14.     if x1 == x2 and y1 == y2:
    
15.         zi = 3 * (x1 ** 2) + a  # 计算分子      【求导】
    
16.         mu = 2 * y1  # 计算分母
    
17.     # 若P≠Q，则k=(y2-y1)/(x2-x1) mod p
    
18.     else:
    
19.         zi = y2 - y1
    
20.         mu = x2 - x1
    
21.         if zi * mu < 0:
    
22.             flag = 0  # 符号0为-（负数）
    
23.             zi = abs(zi)
    
24.             mu = abs(mu)
    
25.     # 将分子和分母化为最简
    
26.     gcd_value = get_gcd(zi, mu)  # 最大公約數
    
27.     zi = zi // gcd_value  # 整除
    
28.     mu = mu // gcd_value
    
29.     inverse_value = get_inverse(mu, p)
    
30.     k = (zi * inverse_value)
    
31.     if flag == 0:  # 斜率负数 flag==0
    
32.         k = -k
    
33.     k = k % p
    
34.     x3 = (k ** 2 - x1 - x2) % p
    
35.     y3 = (k * (x1 - x3) - y1) % p
    
36.     return x3, y3
    
37. def get_rank(x0, y0, a, b, p):
    
38.     x1 = x0  # -p的x坐标
    
39.     y1 = (-1 * y0) % p  # -p的y坐标
    
40.     tempX = x0
    
41.     tempY = y0
    
42.     n = 1
    
43.     while True:
    
44.         n += 1
    
45.         # 求p+q的和，得到n*p，直到求出阶
    
46.         p_x, p_y = get_np(tempX, tempY, x0, y0, a, p)
    
47.         # 如果 == -p,那么阶数+1，返回
    
48.         if p_x == x1 and p_y == y1:
    
49.             return n + 1
    
50.         tempX = p_x
    
51.         tempY = p_y
    
52. def get_param(x0, a, b, p):
    
53.     y0 = -1
    
54.     for i in range(p):
    
55.         # 满足取模约束条件，椭圆曲线Ep(a,b)，p为质数，x,y∈[0,p-1]
    
56.         if i ** 2 % p == (x0 ** 3 + a * x0 + b) % p:
    
57.             y0 = i
    
58.             break
    
59.     # 如果y0没有，返回false
    
60.     if y0 == -1:
    
61.         return False
    
62.     # 计算-y（负数取模）
    
63.     x1 = x0
    
64.     y1 = (-1 * y0) % p
    
65.     return x0, y0, x1, y1
    
66. def get_graph(a, b, p):
    
67.     x_y = []
    
68.     # 初始化二维数组
    
69.     for i in range(p):
    
70.         x_y.append(['-' for i in range(p)])
    
71.     for i in range(p):
    
72.         val = get_param(i, a, b, p)  # 椭圆曲线上的点
    
73.         if val:
    
74.             x0, y0, x1, y1 = val
    
75.             x_y[x0][y0] = 1
    
76.             x_y[x1][y1] = 1
    
77.     print("椭圆曲线的散列图为：")
    
78.     for i in range(p):  # i= 0-> p-1
    
79.         temp = p - 1 - i  # 倒序
    
80.         # 格式化输出1/2位数，y坐标轴
    
81.         if temp >= 10:
    
82.             print(temp, end=" ")
    
83.         else:
    
84.             print(temp, end="  ")
    
85.         # 输出具体坐标的值，一行
    
86.         for j in range(p):
    
87.             print(x_y[j][temp], end="  ")
    
88.         print("")  # 换行
    
89.     # 输出 x 坐标轴
    
90.     print("   ", end="")
    
91.     for i in range(p):
    
92.         if i >= 10:
    
93.             print(i, end=" ")
    
94.         else:
    
95.             print(i, end="  ")
    
96.     print('\n')
    
97. def get_ng(G_x, G_y, key, a, p):
    
98.     temp_x = G_x
    
99.     temp_y = G_y
    
100.     while key != 1:
     
101.         temp_x, temp_y = get_np(temp_x, temp_y, G_x, G_y, a, p)
     
102.         key -= 1
     
103.     return temp_x, temp_y
     
104. def ecc_main():
     
105.     while True:
     
106.         a = int(input("请输入椭圆曲线参数a(a>0)的值："))
     
107.         b = int(input("请输入椭圆曲线参数b(b>0)的值："))
     
108.         p = int(input("请输入椭圆曲线参数p(p为素数)的值："))  # 用作模运算
     
109.         # 条件满足判断
     
110.         if (4 * (a ** 3) + 27 * (b ** 2)) % p == 0:
     
111.             print("输入的参数有误\n")
     
112.         else:
     
113.             break
     
114.     # 输出椭圆曲线散点图
     
115.     get_graph(a, b, p)
     
116.     # 选点作为G点
     
117.     G_x = int(input("请输入选取数字的x坐标值："))
     
118.     G_y = int(input("请输入选取数字的y坐标值："))
     
119.     # 获取椭圆曲线的阶
     
120.     n = get_rank(G_x, G_y, a, b, p)
     
121.     # user1生成私钥，小key
     
122.     key = int(input("请输入私钥小key（<{}）：".format(n)))
     
123.     # user1生成公钥，大KEY
     
124.     KEY_x, kEY_y = get_ng(G_x, G_y, key, a, p)
     
125.     # 加密准备
     
126.     k = int(input("请输入一个整数k（<{}）用于求kG和kQ：".format(n)))
     
127.     k_G_x, k_G_y = get_ng(G_x, G_y, k, a, p)  # kG
     
128.     k_Q_x, k_Q_y = get_ng(KEY_x, kEY_y, k, a, p)  # kQ
     
129.     # 加密
     
130.     plain_text = input("请输入需要加密的字符串:")
     
131.     plain_text = plain_text.strip()
     
132.     # plain_text = int(input("user1：请输入需要加密的密文："))
     
133.     c = []
     
134.     print("密文为：", end="")
     
135.     for char in plain_text:
     
136.         intchar = ord(char)
     
137.         cipher_text = intchar * k_Q_x
     
138.         c.append([k_G_x, k_G_y, cipher_text])
     
139.         print("({},{}),{}".format(k_G_x, k_G_y, cipher_text), end="-")
     
140.     # 知道 k_G_x,k_G_y，key情况下，求解k_Q_x,k_Q_y是容易的，然后plain_text = cipher_text/k_Q_x
     
141.     print("\n解密得到明文：", end="")
     
142.     for charArr in c:
     
143.         decrypto_text_x, decrypto_text_y = get_ng(charArr[0], charArr[1], key, a, p)
     
144.         print(chr(charArr[2] // decrypto_text_x), end="")
     
145. if __name__ == "__main__":
     
146.     ecc_main()

复制代码