(ECDSA3).py
github网站
import math
import secrets
椭圆曲线公式和定义一个点
# Parameters for the curve function y^2 = x^3 + Ax + B
# In this case, secp256k1 is of the equation: y^2 = x^3 + 7
A = 0
B = 7
# Base point of the algorithm
BASE_X = 55066263022277343669578718895168534326250603453777594175500187360389116729240
BASE_Y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
BASE_POINT = (BASE_X, BASE_Y)
曲线素数，和基点在曲线上的阶（阶指的是基点在重复加法下产生的点的数量）
# The proven prime
P = 115792089237316195423570985008687907853269984665640564039457584007908834671663
# The order of the base point on the curve (number of points the base point generates under repeated addition)
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337
j (int): Any integer where j <= k.
k (int): Any integer.
(gcd, x, y): gcd is the greatest common divisor, x and y as the solution to jx + ky = 1
def extended_euclidean_algorithm(j, k):
if j == k:
return (j, 1, 0)
else:
i = 0
j_array = [j]
k_array = [k]
q_array = []
r_array = []
prev_r_is_zero = False
while not (prev_r_is_zero):
q_array.append(k_array[i]//j_array[i])
r_array.append(k_array[i]%j_array[i])
k_array.append(j_array[i])
j_array.append(r_array[i])
i += 1
if r_array[i-1] == 0:
prev_r_is_zero = True
i -= 1
gcd = j_array[i]
# "extended" part of the algorithm, when the algorithm iterates backwards
x_array = [1]
y_array = [0]
i -= 1
total_steps = i
while i >= 0:
y_array.append(x_array[total_steps-i])
x_array.append(y_array[total_steps-i] - q_array[i]*x_array[total_steps-i])
i -= 1
return (gcd, x_array[-1], y_array[-1])
print(extended_euclidean_algorithm(28, 161))
print(extended_euclidean_algorithm(14, 24))
此处输出的为最大公约数，x,y。满足jx+ky=1.
286+161（-1）=1
给出j,n，使用扩展的欧几里得算法来寻找j mod n的逆
def mod_inverse(j, n):
(gcd, x, y) = extended_euclidean_algorithm(j, n)
if gcd == 1:
return x%n
else:
return -1
print(mod_inverse(14, 25))
print(mod_inverse(345, 1234))
print(mod_inverse(3, 37))
print(mod_inverse(20, 5))
求的模逆的值
如果想要更好的了解，必须了解椭圆曲线的基本原理。
参考椭圆曲线公钥加密理论
在椭圆曲线上添加两个不同的点，使用两点的斜率，去寻找与图形相交的第三点，然后翻转第三点并找到与x轴对称的点，即为p+q的和。
def elliptic_add(p, q):
if p == 0 and q == 0: return 0
elif p == 0: return q
elif q == 0: return p
else:
# Swap p and q if px > qx.
if p[0] > q[0]:
temp = p
p = q
q = temp
r = []
slope = (q[1] - p[1])*mod_inverse(q[0] - p[0], P) % P
r.append((slope**2 - p[0] - q[0]) % P)
r.append((slope*(p[0] - r[0]) - p[1]) % P)
return (r[0], r[1])
print(elliptic_add(0,0))
print(elliptic_add((1,60),0))
print(elliptic_add(0,(15,7)))
print(elliptic_add((1,60),(15,7)))
p+q的和
#将椭圆曲线上的一个点添加到自身。自加p+p
def elliptic_double(p):
r = []
slope = (3*p[0]**2 + A)*mod_inverse(2*p[1], P) % P
r.append((slope**2 - 2*p[0])%P)
r.append((slope*(p[0] - r[0]) - p[1])%P)
return (r[0], r[1])
print(elliptic_double((1,5)))
print(elliptic_double(BASE_POINT))
#在椭圆曲线上用一个给定的点p进行标量乘法。在这个实现中，将包括 是一个Python的双加法的实现。
def elliptic_multiply(s, p):
n = p
r = 0 # 0 representing a point at infinity
s_binary = bin(s)[2:] # convert s to binary and remove the "0b" in the beginning
s_length = len(s_binary)
for i in reversed(range(s_length)):
if s_binary[i] == '1':
r = elliptic_add(r, n)
n = elliptic_double(n)
return r
#前两个输出判断是否相等
# Assert that 2P = P + P
print(elliptic_multiply(2, BASE_POINT) == elliptic_double(BASE_POINT))
# Assert that 4P = 3P + 1P
print(elliptic_multiply(4, BASE_POINT) == elliptic_add(elliptic_multiply(3, BASE_POINT), elliptic_multiply(1, BASE_POINT)))
print(elliptic_add(elliptic_multiply(1, BASE_POINT), elliptic_multiply(6, BASE_POINT)))
print(elliptic_multiply(7, BASE_POINT))
print(elliptic_double(elliptic_multiply(5, BASE_POINT)))
#以上是定义椭圆曲线的计算方法
import secrets
#返回的为随机的256位整数值（16进制的32个字节）
def generate_private_key():
return int(secrets.token_hex(32), 16)
#返回一个由公钥生成的私钥，其公钥是安全的，因为他的计算方法为通过将生成器的点 "乘以 "一个巨大的整数（私钥）在一个巨大的领域。产生的点 (将被压缩并作为公钥返回)将经过许多椭圆加法的处理 以至于不可能猜到乘数（也就是私钥）。
def generate_public_key(private_key):
return elliptic_multiply(private_key, BASE_POINT)
#返回一个压缩的公钥：取公钥的x值并加上 y值的奇偶校验位开始。
#判断密钥y的奇偶性
if key[1] % 2 == 0:
parity = '02'
else:
parity = '03'
return parity + hex(key[0])[2:]#hex() 用于将十进制数字转换成十六进制；key[0]为密钥的x值，前两位为校验数字，后面取从第3位开始。
#Python中的十六进制值包含一个 "0x "前缀。[2:]去掉了这个前缀
def generate_key_pair(print_flag=True):
private_key = generate_private_key()
public_key = generate_public_key(private_key)
#进行了十六进制转换。
if (print_flag):
print("Private Key: " + str(private_key))
print("Private Key (hex): " + str(hex(private_key))[2:])
print("Public Key: " + str(public_key[0]) + str(public_key[1]))
print("Public Key (hex): " + "04" + hex(public_key[0])[2:] + hex(public_key[1])[2:]) # Bitcoin adds a "04" prefix to indicate that this is an uncompressed public key.
print("Public Key (hex and compressed): " + compress_public_key(public_key))
return (private_key, generate_public_key(private_key))
(sample_private_key, sample_public_key) = generate_key_pair(True)
扩展：A[ : 2]:表示索引 0至1行；A[ :, 2]:表示所有行的第3列。
5.比特币用SHA-256对其信息内容进行双重加密from hashlib import sha256
def double_hash(message):
"""伪代码
Args:
message (str): A message to be hashed
Return:
A SHA-256 double-hashed message in decimal format, 256 bits long.
"""
hashed_message = sha256(message.encode('utf-8')).hexdigest()
hashed_message = sha256(hashed_message.encode('utf-8')).hexdigest()#双重哈希对消息进行加密
return int(hashed_message, 16)
print(double_hash("I hate COVID"))
对消息求哈希得到的结果：
扩展：
hash.digest()
返回摘要，作为二进制数据字符串值
hash.hexdigest()
返回摘要，作为十六进制数据字符串值
注意：要清楚对消息签名和对消息验证的整个流程
接下来，对消息进行签名
其中，
private_key (int): 发送者的私钥。
message (str): 一个包含交易信息的消息。
一个以元组形式存在的签名（rx, s），其中rx是一个随机点的x坐标，s是签名本身。
def sign(private_key, message):#私钥对消息签名
hashed_message = double_hash(message)#消息为上个函数计算的双重哈希的消息
# A secure random number for the signature
k = secrets.randbelow(P)#产生一个0到P的随机数，其中randbelow()为secrets包的内置函数
random_point = elliptic_multiply(k, BASE_POINT)#随机数*基点
# Only the x-value is needed, as the y can always be generated using the curve equation y^2 = x^3 + 7
rx = random_point[0] % N#随机的点有x，y的坐标，但是只取x：random_point[0]，模为N
signature_proof = mod_inverse(k, N) * (hashed_message + rx*private_key) % N#用私钥进行签名
return (rx, signature_proof)#以元组形式存在的签名
message = "Alice sends to Bob 12 Bitcoins"
signature = sign(sample_private_key, message)
print("Message: " + message)
print("Signature: ", end="")
print(signature)
验证签名是否和交易时的私钥一致。通过恢复签名函数中使用的随机点完成，查看得到的签名rx是否一致
def verify(public_key, message, signature):
(rx, s) = signature#为签名的形式
hashed_message = double_hash(message)#双重签名得到的哈希消息
inverse_s = mod_inverse(s, N)#对s求逆
# Solve for the random point
a = elliptic_multiply(hashed_message * inverse_s % N, BASE_POINT)#elliptic_multiply()为乘法
b = elliptic_multiply(rx * inverse_s % N, public_key)#公钥验证
recovered_random_point = elliptic_add(a, b)
# Check that the recovered random point matches the actual random point
return recovered_random_point[0] == rx#相等则表示验证通过
print(verify(sample_public_key, message, signature))
说输出消息，消息的签名，消息验证的结果
#接下来用于测试被篡改信息的签名和验证功能。
#被篡改的信息测试。确保消息的内容是它们所要表达的。
def tampered_message_tests():
#3条消息
message_pairs = [
["Chau sends Professor Nguyen 2 Bitcoins", "Chau sends Professor Nguyen 500 Bitcoins"],
["Hernan sends Chau 3 Bitcoins", "Hernan sends Chau 50 Bitcoins"],
["Owen sends Felix 50 Bitcoins", "Owen sends Felix 600 Bitcoins"]
]
#打印每条消息
for i in range(len(message_pairs)):
print('----------------------- Tampered Message Case ' + str(i+1) + '----------------------')
print()
#产生公私钥
#成对的列表。第一个元素是原始信息。第二个是被篡改的信息。
(priv_key, pub_key) = generate_key_pair(True)
(message, tampered_message) = message_pairs[i]
print()
print("Original Message: " + message)
print("Tampered Message: " + tampered_message)
print()
#私钥签名
signature = sign(priv_key, message)
print("Signature: ", end="")
print(signature)
print()
#公钥验证原始签名、篡改的签名
print("Original Message Verification: ", end="")
print(verify(pub_key, message, signature))
print("Tampered Message Verification: ", end="")
print(verify(pub_key, tampered_message, signature))
print()
tampered_message_tests()
接下来，测试当错误的公钥被用来 "解锁 "信息时会发生什么。
def wrong_public_key_test():
print('----------------------- Wrong Public Key Case ----------------------')
print()
#正确的公私钥和错误的公私钥
(priv_key, pub_key) = generate_key_pair(False)
(wrong_priv_key, wrong_pub_key) = generate_key_pair(False)
#原始公钥和错误公钥04开头，取公钥的x值的索引为2和之后的元素+y值的索引为2和之后的元素
print("Original Public Key: " + "04" + (hex(pub_key[0])[2:] + hex(pub_key[1])[2:]))
print("Wrong Public Key: " + "04" + (hex(wrong_pub_key[0])[2:] + hex(wrong_pub_key[1])[2:]))
message = "Satoshi sends 500 Bitcoins to Chau"
print("Message: " + message)
#用正确的私钥签名
signature = sign(priv_key, message)
print("Signature: ", end="")
print(signature)
print()
#输出正确的的公钥签名的消息的验证结果
print("With Correct Public Key: ", end="")
print(verify(pub_key, message, signature))
#输出错误的公钥签名的消息的验证结果
print("With Wrong Public Key: ", end="")
print(verify(wrong_pub_key, message, signature))
wrong_public_key_test()
接下来，测试如果一个拥有不同私钥的人试图签署同一消息会发生什么。
def wrong_private_key_test():
print('----------------------- Wrong Private Key Case ----------------------')
print()
(priv_key, pub_key) = generate_key_pair(False)
(wrong_priv_key, wrong_pub_key) = generate_key_pair(False)
message = "LeBron sends 5 Bitcoins to Dwight"
#与错误公钥不同的是，这里有错误的签名
signature = sign(priv_key, message)
wrong_signature = sign(wrong_priv_key, message) # Different signer!
print("Original User's Signature: ", end="")
print(signature)
print("Another User's Signature: ", end="")
print(wrong_signature)
print()
print("Original Signature Verification: ", end="")
print(verify(pub_key, message, signature))
print("Wrong Signature Verification: ", end="")
print(verify(pub_key, message, wrong_signature))
wrong_private_key_test()
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）