信息计算2019级1班6号马璐

马璐

马璐

马璐

1. import math
   
2. import random
   
3. 
   
4. 
   
5. def mess2long(message):
   
6.         return int(message,16)
   
7. 
   
8. def long2mess(long_num):
   
9.     long_mess = hex(long_num)[2:].replace("L","")
   
10.     if len(long_mess) % 2 != 0: long_mess = '0' + long_mess
    
11.     return long_mess
    
12. 
    
13. def gcd(a, b):
    
14.     if a > b: a, b = b, a
    
15.     while b != 0:
    
16.         a, b = b, a%b
    
17.     return a
    
18. 
    
19. def isPrime(n):
    
20. 
    
21.     if n <= 1:
    
22.         return False
    
23.     for i in range(2, int(math.sqrt(n)) + 1):
    
24.         if n % i== 0:
    
25.             return False
    
26.     return True
    
27. 
    
28. def generate_key(key_len):
    
29. 
    
30.     p = random_prime(key_len // 2)
    
31.     q = random_prime(key_len // 2)
    
32.     n  = p * q
    
33.     ph_n = (p -1) * (q -1)
    
34.     e = 65537
    
35.     d = generate_d(ph_n, e)
    
36.     return (n ,e, d)
    
37. 
    
38. def random_prime(half_len):
    
39.     while True:
    
40.         n = random.randint(0, 1 << half_len)
    
41.         if n % 2 != 0:
    
42.             found = True
    
43.             for i in range(0, 5):
    
44.                 if prime_test(n) == False:
    
45.                     found = False
    
46.                     break
    
47.             if found == True:
    
48.                 return n
    
49. 
    
50. def prime_test(n):
    
51.         q = n - 1
    
52.         k = 0
    
53.         while q % 2 == 0:
    
54.             k += 1
    
55.             q = q // 2
    
56.         a = random.randint(2, n - 2)
    
57.         if fast_mod(a, q, n) == 1:
    
58.             return True
    
59.         for j in range(0, k):
    
60.             if fast_mod(a, (2 ** j) * q, n) == n - 1:
    
61.                 return True
    
62.         return False
    
63. 
    
64. def ext_gcd(a, b):
    
65.     if b == 0:
    
66.         return 1, 0, a
    
67.     else:
    
68.         x, y, q = ext_gcd(b, a % b)
    
69.         x, y = y, (x - (a // b) * y)
    
70.         return x, y, q
    
71. 
    
72. 
    
73. def fast_mod(b, n, m):
    
74. 
    
75.     ret = 1
    
76.     tmp = b
    
77.     while n:
    
78.         if n & 0x1:
    
79.             ret = ret * tmp % m
    
80.         tmp = tmp * tmp % m
    
81.         n >>= 1
    
82.     return ret
    
83. 
    
84. def generate_d(ph_n, e):
    
85.     (x, y, r) = ext_gcd(ph_n, e)
    
86.     if y < 0:
    
87.         return y + ph_n  
    
88.     return y
    
89. 
    
90. if __name__ == '__main__':
    
91.     message = input("input your message:\n")
    
92.     mess_num = mess2long(message)
    
93.     mess_num_length = len(str(mess_num))
    
94.     (n, e, d) = generate_key(mess_num_length*15)
    
95.     cipher = fast_mod(mess_num,e, n)
    
96.     print("-----------------------------------------------------------------")
    
97.     print("cipher:"+str(cipher))
    
98. 
    
99. 
    
100. 
     
101. 
     
102. 
     
103. import math
     
104. import random
     
105. 
     
106. 
     
107. def mess2long(message):
     
108.         return int(message,16)
     
109. 
     
110. def long2mess(long_num):
     
111.     long_mess = hex(long_num)[2:].replace("L","")
     
112.     if len(long_mess) % 2 != 0: long_mess = '0' + long_mess
     
113.     return long_mess
     
114. 
     
115. def gcd(a, b):
     
116.     if a > b: a, b = b, a
     
117.     while b != 0:
     
118.         a, b = b, a%b
     
119.     return a
     
120. 
     
121. def isPrime(n):
     
122. 
     
123.     if n <= 1:
     
124.         return False
     
125.     for i in range(2, int(math.sqrt(n)) + 1):
     
126.         if n % i== 0:
     
127.             return False
     
128.     return True
     
129. 
     
130. def generate_key(key_len):
     
131. 
     
132.     p = random_prime(key_len // 2)
     
133.     q = random_prime(key_len // 2)
     
134.     n  = p * q
     
135.     ph_n = (p -1) * (q -1)
     
136.     e = 65537
     
137.     d = generate_d(ph_n, e)
     
138.     return (n ,e, d)
     
139. 
     
140. def random_prime(half_len):
     
141.     while True:
     
142.         n = random.randint(0, 1 << half_len)
     
143.         if n % 2 != 0:
     
144.             found = True
     
145.             for i in range(0, 5):
     
146.                 if prime_test(n) == False:
     
147.                     found = False
     
148.                     break
     
149.             if found == True:
     
150.                 return n
     
151. 
     
152. def prime_test(n):
     
153.         q = n - 1
     
154.         k = 0
     
155.         while q % 2 == 0:
     
156.             k += 1
     
157.             q = q // 2
     
158.         a = random.randint(2, n - 2)
     
159.         if fast_mod(a, q, n) == 1:
     
160.             return True
     
161.         for j in range(0, k):
     
162.             if fast_mod(a, (2 ** j) * q, n) == n - 1:
     
163.                 return True
     
164.         return False
     
165. 
     
166. def ext_gcd(a, b):
     
167.     if b == 0:
     
168.         return 1, 0, a
     
169.     else:
     
170.         x, y, q = ext_gcd(b, a % b)
     
171.         x, y = y, (x - (a // b) * y)
     
172.         return x, y, q
     
173. 
     
174. 
     
175. def fast_mod(b, n, m):
     
176. 
     
177.     ret = 1
     
178.     tmp = b
     
179.     while n:
     
180.         if n & 0x1:
     
181.             ret = ret * tmp % m
     
182.         tmp = tmp * tmp % m
     
183.         n >>= 1
     
184.     return ret
     
185. 
     
186. def generate_d(ph_n, e):
     
187.     (x, y, r) = ext_gcd(ph_n, e)
     
188.     if y < 0:
     
189.         return y + ph_n  
     
190.     return y
     
191. 
     
192. if __name__ == '__main__':
     
193.     message = input("input your message:\n")
     
194.     mess_num = mess2long(message)
     
195.     mess_num_length = len(str(mess_num))
     
196.     (n, e, d) = generate_key(mess_num_length*15)
     
197.     cipher = fast_mod(mess_num,e, n)
     
198.     print("-----------------------------------------------------------------")
     
199.     print("cipher:"+str(cipher))
     
200. 
     
201. 
     
202. 
     
203. 
     
204. 
     
205. 
     
206. 
     
207. 
     
208. 
     
209. 
     
210. 
     

复制代码

马璐

马璐

ECC加密原理： 1、用户A选定一条适合加密的椭圆曲线Ep(a,b)(如:y2=x3+ax+b)，并取椭圆曲线上一点，作为基点G。 　2、用户A选择一个私有密钥k，并生成公开密钥K=kG。 　3、用户A将Ep(a,b)和点K，G传给用户B。 　4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M，并产生一个随机整数r（r<n）。 　5、用户B计算点C1=M+rK；C2=rG。 　6、用户B将C1、C2传给用户A。 　7、用户A接到信息后，计算C1-kC2，结果就是点M。因为           C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M 　　　再对点M进行解码就可以得到明文。   密码学中，描述一条Fp上的椭圆曲线，常用到六个参量： T=(p,a,b,G,n,h)。 　　（p 、a 、b 用来确定一条椭圆曲线，G为基点，n为点G的阶，h 是椭圆曲线上所有点的个数m与n相除的整数部分） 　　这几个参量取值的选择，直接影响了加密的安全性。参量值一般要求满足以下几个条件： 　　1、p 当然越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求； 　　2、p≠n×h； 　　3、pt≠1 (mod n)，1≤t<20； 　　4、4a3+27b2≠0 (mod p)； 　　5、n 为素数； 　　6、h≤4；

马璐

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

复制代码