敲写一段利用了离散数学知识的200行代码
时间: 2024-01-08 19:03:49 浏览: 38
以下是一个利用了离散数学知识的200行代码示例,实现了一个简单的Elliptic Curve加密算法:
```python
import random
class Point:
"""
椭圆曲线上的点
"""
def __init__(self, x, y, a, b):
self.x = x
self.y = y
self.a = a
self.b = b
if self.x is None and self.y is None:
return
if self.y**2 != self.x**3 + a * x + b:
raise ValueError("点不在椭圆曲线上")
def __eq__(self, other):
"""
判断两个点是否相等
"""
return self.x == other.x and self.y == other.y and self.a == other.a and self.b == other.b
def __ne__(self, other):
"""
判断两个点是否不相等
"""
return not (self == other)
def __str__(self):
"""
返回点的字符串表示
"""
if self.x is None and self.y is None:
return "Point(infinity)"
else:
return "Point({},{})_{}".format(self.x, self.y, self.b)
def __add__(self, other):
"""
计算两个点的加法
"""
if self.a != other.a or self.b != other.b:
raise ValueError("两个点不在同一条椭圆曲线上")
# 计算斜率
if self.x is None:
return other
elif other.x is None:
return self
elif self.x == other.x and self.y != other.y:
return Point(None, None, self.a, self.b)
elif self.x == other.x:
s = (3 * self.x**2 + self.a) / (2 * self.y)
else:
s = (other.y - self.y) / (other.x - self.x)
# 计算新点的坐标
x = s**2 - self.x - other.x
y = s * (self.x - x) - self.y
return Point(x, y, self.a, self.b)
def __rmul__(self, k):
"""
计算一个点乘以一个整数k的结果
"""
result = Point(None, None, self.a, self.b)
current = self
while k:
if k & 1:
result += current
current += current
k >>= 1
return result
class EllipticCurve:
"""
椭圆曲线
"""
def __init__(self, a, b):
self.a = a
self.b = b
# 判断曲线是否为非奇异曲线
if 4 * a**3 + 27 * b**2 == 0:
raise ValueError("a和b的值不能构成非奇异曲线")
def contains_point(self, x, y):
"""
判断点(x, y)是否在椭圆曲线上
"""
return y**2 == x**3 + self.a * x + self.b
def random_point(self):
"""
随机生成一点在椭圆曲线上的点
"""
while True:
x = random.randint(0, p - 1)
y = random.randint(0, p - 1)
if self.contains_point(x, y):
return Point(x, y, self.a, self.b)
def gcd(a, b):
"""
求a和b的最大公约数
"""
if b == 0:
return a
return gcd(b, a % b)
def mod_inverse(a, m):
"""
计算a在模m意义下的逆元,不存在则返回None
"""
if gcd(a, m) != 1:
return None
return pow(a, -1, m)
def is_prime(n):
"""
判断n是否为质数
"""
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
if __name__ == '__main__':
# 选择椭圆曲线y^2 = x^3 + ax + b
a = 0
b = 7
curve = EllipticCurve(a, b)
# 选择一个大质数p
p = 2**256 - 2**32 - 977
# 判断p是否为质数
if not is_prime(p):
raise ValueError("p必须是质数")
# 随机生成一点G在椭圆曲线上
G = curve.random_point()
# 选择一个私钥d
d = random.randint(1, p - 1)
# 计算公钥Q
Q = d * G
# 明文m
m = 123456789
# 加密明文m
k = random.randint(1, p - 1)
C1 = k * G
C2 = m * Q + k * C1
print("密文:", C1, C2)
# 解密密文
m = (C2 - d * C1).y // C1.y
print("明文:", m)
```
该代码利用了离散数学中的椭圆曲线、点的加法、点的倍乘等知识,实现了一个简单的Elliptic Curve加密算法。其中,生成随机点和随机整数时利用了随机化的思想,加密和解密时利用了椭圆曲线上的点运算,避免了大数运算的耗时问题。整个算法的安全性基于椭圆曲线上的离散对数问题,是一种比RSA更加安全的公钥加密算法。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![m](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)