想起来很久没写博客了，刚好今天要写实验报告，随便把之前的也完成吧
1.椭圆曲线概念
椭圆曲线在经过化解后，可以用这条式子表达：E：y2=x3+ax+b
其背后的密码学原理，是基于椭圆曲线离散对数问题，比RSA算法更有安全且运算速度更快。
在看上面的式子，我们知道构造一个椭圆曲线，需要a，b两个参数
而在有限域GF(p)上的椭圆曲线，则还需要一个参数p，它的表达式为E：y2≡x3+ax+b(mod p)
椭圆曲线的运算是符合Abel群的
如
1.0+0=0(0是加法单位元)
2.对所有点P=(x,y)∈E(a,b),有P+0=0+P=P
3.对所有点P=(x,y)∈E(a,b),有P+(-P)=0,点P的逆为(x,-y)
4.两点加法(重要)，令P(x1,y1)∈E(a,b),Q(x2,y2)∈E(a,b)
则P+Q=R=(x3,y3)∈E(a,b)
x3=(lada)3-x1-x2
y3=lada(x1-x3)-y1
其中lada分为两种情况
一是P不等于Q，lada=(y2-y1)/(x2-x1)
二是P等于Q(倍点规则)，lada=(3(x1)2+a)/2y1
5.对所有点P和Q∈E(a,b),满足加法交换侓，P+Q=Q+P
6.对所有点P和Q∈E(a,b),满足加法结合率，P+(Q+R)=(P+Q)+R
7.乘法，KP相当于K个P相加
2.椭圆曲线加解密
了解完椭圆曲线这些概念就可以进行加解密了
1.user2输入需要加密的明文
2.user2待传输的明文以某种编码方式编码到椭圆曲线上一点M
3.user2秘密选择k进行加密，计算点C1=kP；C2=M+kQ,传给user1
4.user1选定一条椭圆曲线=(a,b,p)，公开参数a,b,p，
5.user1选择素阶点P
6.user1选择一个私有密钥d，并生成公开密钥Q=dP
7.user1将得到的密文用d进行解密，M=C2-dC1
原理C2-C1=M+kQ-d(kP)=M+K(dP)-d(kP)=M
再对点M进行解码就可以得到明文。
函数功能：
1.从明文消息中的第一个字符开始，使用基于ASCII字符码的明文嵌入方法映射，直到最后一个字符。从而，将明文消息字符编码为椭圆曲线E点。
参数为p点坐标，以及明文，a，b，p椭圆曲线参数，作为才发现后面竟然有给出代码
点击查看代码
def message_to_point(P_x, P_y, message, a, b, p): points = [] n = 1 for char in message: k = ord(char) + 1 print(k) x, y = tuoyuan_cheng(P_x, P_y, k, a, b, p) points.append((x, y)) print("{}=>({},{})".format(n, x, y)) n += 1 return points
2.此处应用了拓展欧几里得求逆元，在椭圆曲线加法处用到
点击查看代码
def extend_gcd(a, b): if b == 0: return a, 1, 0 else: g, y, x = extend_gcd(b, a % b) return g, x, y - (a // b) * xdef niyuan(a, b): # 计算a模b的逆元， g, x, y = extend_gcd(a, b) if g != 1: print("a和b不互素，因此不存在逆元") return None else: return x % b
3.椭圆曲线中的加法，因为除后取模很麻烦，此处就用了逆元的思想
实现了
两点加法，令P(x1,y1)∈E(a,b),Q(x2,y2)∈E(a,b)
则P+Q=R=(x3,y3)∈E(a,b)
x3=(lada)3-x1-x2
y3=lada(x1-x3)-y1
点击查看代码
def tuoyuan_jia(P_x, P_y, Q_x, Q_y, a, b, p): # 椭圆曲线中的加法 if P_x == Q_x and P_y == Q_y: lada = ((3 * (P_x ** 2) + a) * niyuan(2 * P_y, p)) % p x3 = (lada ** 2 - P_x - Q_x) % p y3 = (lada * (P_x - x3) - P_y) % p return x3, y3 elif P_x != Q_x: lada = ((Q_y - P_y) * niyuan(Q_x - P_x, p)) % p x3 = (lada ** 2 - P_x - Q_x) % p y3 = (lada * (P_x - x3) - P_y) % p return x3, y3 elif P_x == Q_x and P_y != Q_y: return 0, 0
4.椭圆曲线中的乘法
乘法，KP相当于K个P相加
点击查看代码
def tuoyuan_cheng(P_x, P_y, k, a, b, p): # 椭圆曲线中的乘法，这里的k为乘于几，乘几那么就相当于几个点相加 k = int(k) # 确保k是整数类型 new_x, new_y = P_x, P_y for i in range(k - 1): new_x, new_y = tuoyuan_jia(new_x, new_y, P_x, P_y, a, b, p)return new_x, new_y
5.计算椭圆曲线的阶
点击查看代码
def cal_jie(P_x, P_y, a, b, p): fuP_x = P_x fuP_y = -P_y % p new_x, new_y = P_x, P_y n = 1 # 初始化n while True: n += 1 new_x, new_y = tuoyuan_jia(new_x, new_y, P_x, P_y, a, b, p) if new_x == fuP_x and new_y == fuP_y: return n + 1
6.椭圆曲线加密
实现了k进行加密，计算点C1=kP；C2=M+kQ
点击查看代码
def encode(P_x, P_y, Q_x, Q_y, k, points, a, b, p): poointsC1 = [] poointsC2 = [] kP_x, kP_y = tuoyuan_cheng(P_x, P_y, k, a, b, p) poointsC1.append((kP_x, kP_y)) print("计算得密文为") print("c1") print(poointsC1) kQ_x, kQ_y = tuoyuan_cheng(Q_x, Q_y, k, a, b, p) for point in points: x = point[0] y = point[1] x = int(x) y = int(y) newkQ_x, newkQ_y = tuoyuan_jia(kQ_x, kQ_y, x, y, a, b, p) poointsC2.append((newkQ_x, newkQ_y)) print("c2") print(poointsC2) return poointsC1, poointsC2
7.椭圆曲线解密
将得到的密文用d进行解密，M=C2-dC1
原理C2-C1=M+kQ-d(kP)=M+K(dP)-d(kP)=M
点击查看代码
def decode(poointsC1, poointsC2, d, a, b, p): points = [] C1 = poointsC1[0] C1_x = C1[0] C1_y = C1[1] inv_dC1_x, inv_dC1_y = tuoyuan_cheng(C1_x, C1_y,d,a, b, p) inv_dC1_y=-inv_dC1_y for point in poointsC2: C2_x = point[0] C2_y = point[1] #M_x=(C2_x-inv_dC1_x)%p #M_y=(C2_y-inv_dC1_y)%p M_x, M_y = tuoyuan_jia(C2_x, C2_y, inv_dC1_x, inv_dC1_y, a, b, p) points.append((M_x, M_y)) print(points) return points
8.将点转化成明文
此处我没有运用现代密码学教程的思想
而是想着让点不断地加上逆P，使得每次n+1，等到最后点与P相等时，得到n
点击查看代码
def points_to_message(P_x, P_y,points,a, b, p): message = "" for point in points: x = point[0] y = point[1] fuP_x=P_x fuP_y=-P_y n=0 while x!=P_x and y!=P_y: x , y=tuoyuan_jia(x, y, fuP_x, fuP_y, a, b, p) n+=1 char=chr(n) message+=char print("解密后的字符串"+message) return message
python
代码(附带注销)：
import mathimport randomdef extend_gcd(a, b): if b == 0: return a, 1, 0 else: g, y, x = extend_gcd(b, a % b) return g, x, y - (a // b) * xdef niyuan(a, b): # 计算a模b的逆元 g, x, y = extend_gcd(a, b) if g != 1: print("a和b不互素，因此不存在逆元") return None else: return x % bdef tuoyuan_jia(P_x, P_y, Q_x, Q_y, a, b, p): # 椭圆曲线中的加法 if P_x == Q_x and P_y == Q_y: lada = ((3 * (P_x ** 2) + a) * niyuan(2 * P_y, p)) % p x3 = (lada ** 2 - P_x - Q_x) % p y3 = (lada * (P_x - x3) - P_y) % p return x3, y3 elif P_x != Q_x: lada = ((Q_y - P_y) * niyuan(Q_x - P_x, p)) % p x3 = (lada ** 2 - P_x - Q_x) % p y3 = (lada * (P_x - x3) - P_y) % p return x3, y3 elif P_x == Q_x and P_y != Q_y: return 0, 0def tuoyuan_cheng(P_x, P_y, k, a, b, p): # 椭圆曲线中的乘法，这里的k为乘于几，乘几那么就相当于几个点相加 k = int(k) # 确保k是整数类型 new_x, new_y = P_x, P_y for i in range(k - 1): new_x, new_y = tuoyuan_jia(new_x, new_y, P_x, P_y, a, b, p) return new_x, new_ydef message_to_point(P_x, P_y, message, a, b, p): points = [] n = 1 for char in message: k = ord(char) + 1 print(k) x, y = tuoyuan_cheng(P_x, P_y, k, a, b, p) points.append((x, y)) print("{}=>({},{})".format(n, x, y)) n += 1 return pointsdef points_to_message(P_x, P_y,points,a, b, p): message = "" for point in points: x = point[0] y = point[1] fuP_x=P_x fuP_y=-P_y n=0 while x!=P_x and y!=P_y: x , y=tuoyuan_jia(x, y, fuP_x, fuP_y, a, b, p) n+=1 char=chr(n) message+=char print("解密后的字符串"+message) return messagedef cal_jie(P_x, P_y, a, b, p): fuP_x = P_x fuP_y = -P_y % p new_x, new_y = P_x, P_y n = 1 # 初始化n while True: n += 1 new_x, new_y = tuoyuan_jia(new_x, new_y, P_x, P_y, a, b, p) if new_x == fuP_x and new_y == fuP_y: return n + 1def encode(P_x, P_y, Q_x, Q_y, k, points, a, b, p): poointsC1 = [] poointsC2 = [] kP_x, kP_y = tuoyuan_cheng(P_x, P_y, k, a, b, p) poointsC1.append((kP_x, kP_y)) print("计算得密文为") print("c1") print(poointsC1) kQ_x, kQ_y = tuoyuan_cheng(Q_x, Q_y, k, a, b, p) for point in points: x = point[0] y = point[1] x = int(x) y = int(y) newkQ_x, newkQ_y = tuoyuan_jia(kQ_x, kQ_y, x, y, a, b, p) poointsC2.append((newkQ_x, newkQ_y)) print("c2") print(poointsC2) return poointsC1, poointsC2def decode(poointsC1, poointsC2, d, a, b, p): points = [] C1 = poointsC1[0] C1_x = C1[0] C1_y = C1[1] inv_dC1_x, inv_dC1_y = tuoyuan_cheng(C1_x, C1_y,d,a, b, p) inv_dC1_y=-inv_dC1_y for point in poointsC2: C2_x = point[0] C2_y = point[1] #M_x=(C2_x-inv_dC1_x)%p #M_y=(C2_y-inv_dC1_y)%p M_x, M_y = tuoyuan_jia(C2_x, C2_y, inv_dC1_x, inv_dC1_y, a, b, p) points.append((M_x, M_y)) print(points) return pointsdef main(): print("****ECC椭圆曲线加解密****") while True: a = int(input("请输入椭圆曲线参数a(a>0)的值：")) b = int(input("请输入椭圆曲线参数b(b>0)的值：")) p = int(input("请输入椭圆曲线参数p(a>0)的值：")) if 4 * (a ** 3) - 27 * (b ** 2) % p == 0: print("输入的参数有误，请重新输入") else: break print("user1：在如上坐标系中选一个素阶点P") P_x = int(input("请输入选取的x坐标值：")) P_y = int(input("请输入选取的y坐标值：")) n = cal_jie(P_x, P_y, a, b, p) d = int(input(("user1：请输入用于生成公钥的私钥d(<{})：".format(n)))) Q_x, Q_y = tuoyuan_cheng(P_x, P_y, d, a, b, p) print(" 计算Q=d*P得公钥Q为(" + str(Q_x) + "," + str(Q_y) + ")") mingwen = input("user2：请输入需要加密的字符串：") mingwen = mingwen.strip() # 通过strip()方法可以去除字符串两端的空格 print("明文映射的点为：") points1 = message_to_point(P_x, P_y, mingwen, a, b, p) k = input("user2：请输入秘密选择的k(<{})：".format(n)) # 这一步我们不用，我们选择用随机数 # k = random.randint(1, n) # 生成1到阶n之间的随机整数,用于计算kP,kQ print("user2:计算得密文为") poointsC1, poointsC2 = encode(P_x, P_y, Q_x, Q_y, k, points1, a, b, p) print("user1解密得到明文映射的点为:") points2=decode(poointsC1, poointsC2, d, a, b, p) points_to_message(P_x, P_y,points2,a, b, p)if __name__ == "__main__": # 函数入口 main()
3.原始输入输出
欢迎指正
经验首页