熵密杯2026初始谜题一
题目让伪造出一组可以验签通过的摘要和签名，方法为绕过公钥。
1、分析verify代码，可以发现当r+s=n时，公钥不发挥作用，而r，s是签名值，使s=1，r=n-1，构造sign = "FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D541220000000000000000000000000000000000000000000000000000000000000001"。
2、通过判定条件r == ((e + x) % int(default_table['n'], base=16))，得到e=(r-x)%n
在verify中使用print('%064x' % ((r - x) % int(default_table['n'], base=16)))得到e
原代码中%064x表示格式化为 64 位宽的十六进制（小写），前面补零
default_table = {
'n': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',
'p': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',
'g': '32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7'
'bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',
'a': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',
'b': '28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',
}
class Crypt():
def __init__(self, private_key, public_key, mode=0):
self.private_key = private_key
if public_key.startswith("04"):
self.public_key = public_key[2:]
else:
self.public_key = public_key
self.para_len = len(default_table['n'])
self.ecc_a3 = (
int(default_table['a'], base=16) + 3) % int(default_table['p'], base=16)
assert mode in (0, 1), 'mode must be one of (0, 1)'
self.mode = mode
def _kg(self, k, Point): # kP运算
if k == 0:
return None#无穷远点
Point = '%s%s' % (Point, '1')
mask_str = '8'
for i in range(self.para_len - 1):
mask_str += '0'
mask = int(mask_str, 16)
Temp = Point
flag = False
for n in range(self.para_len * 4):
if (flag):
Temp = self._double_point(Temp)
if (k & mask) != 0:
if (flag):
Temp = self._add_point(Temp, Point)
else:
flag = True
Temp = Point
k = k << 1
return self._convert_jacb_to_nor(Temp)
def _double_point(self, Point): # 倍点
if Point is None:
return None
l = len(Point)
len_2 = 2 * self.para_len
if l < self.para_len * 2:
return None
else:
x1 = int(Point[0:self.para_len], 16)
y1 = int(Point[self.para_len:len_2], 16)
if l == len_2:
z1 = 1
else:
z1 = int(Point[len_2:], 16)
T6 = (z1 * z1) % int(default_table['p'], base=16)
T2 = (y1 * y1) % int(default_table['p'], base=16)
T3 = (x1 + T6) % int(default_table['p'], base=16)
T4 = (x1 - T6) % int(default_table['p'], base=16)
T1 = (T3 * T4) % int(default_table['p'], base=16)
T3 = (y1 * z1) % int(default_table['p'], base=16)
T4 = (T2 * 8) % int(default_table['p'], base=16)
T5 = (x1 * T4) % int(default_table['p'], base=16)
T1 = (T1 * 3) % int(default_table['p'], base=16)
T6 = (T6 * T6) % int(default_table['p'], base=16)
T6 = (self.ecc_a3 * T6) % int(default_table['p'], base=16)
T1 = (T1 + T6) % int(default_table['p'], base=16)
z3 = (T3 + T3) % int(default_table['p'], base=16)
T3 = (T1 * T1) % int(default_table['p'], base=16)
T2 = (T2 * T4) % int(default_table['p'], base=16)
x3 = (T3 - T5) % int(default_table['p'], base=16)
if (T5 % 2) == 1:
T4 = (T5 + ((T5 + int(default_table['p'], base=16)) >> 1) - T3) % int(
default_table['p'], base=16)
else:
T4 = (T5 + (T5 >> 1) - T3) % int(default_table['p'], base=16)
T1 = (T1 * T4) % int(default_table['p'], base=16)
y3 = (T1 - T2) % int(default_table['p'], base=16)
form = '%%0%dx' % self.para_len
form = form * 3
return form % (x3, y3, z3)
def _add_point(self, P1, P2): # 点加函数，P2点为仿射坐标即z=1，P1为Jacobian加重射影坐标
if P1 is None:
return P2
if P2 is None:
return P1
len_2 = 2 * self.para_len
l1 = len(P1)
l2 = len(P2)
if (l1 < len_2) or (l2 < len_2):
return None
else:
X1 = int(P1[0:self.para_len], 16)
Y1 = int(P1[self.para_len:len_2], 16)
if (l1 == len_2):
Z1 = 1
else:
Z1 = int(P1[len_2:], 16)
x2 = int(P2[0:self.para_len], 16)
y2 = int(P2[self.para_len:len_2], 16)
T1 = (Z1 * Z1) % int(default_table['p'], base=16)
T2 = (y2 * Z1) % int(default_table['p'], base=16)
T3 = (x2 * T1) % int(default_table['p'], base=16)
T1 = (T1 * T2) % int(default_table['p'], base=16)
T2 = (T3 - X1) % int(default_table['p'], base=16)
T3 = (T3 + X1) % int(default_table['p'], base=16)
T4 = (T2 * T2) % int(default_table['p'], base=16)
T1 = (T1 - Y1) % int(default_table['p'], base=16)
Z3 = (Z1 * T2) % int(default_table['p'], base=16)
T2 = (T2 * T4) % int(default_table['p'], base=16)
T3 = (T3 * T4) % int(default_table['p'], base=16)
T5 = (T1 * T1) % int(default_table['p'], base=16)
T4 = (X1 * T4) % int(default_table['p'], base=16)
X3 = (T5 - T3) % int(default_table['p'], base=16)
T2 = (Y1 * T2) % int(default_table['p'], base=16)
T3 = (T4 - X3) % int(default_table['p'], base=16)
T1 = (T1 * T3) % int(default_table['p'], base=16)
Y3 = (T1 - T2) % int(default_table['p'], base=16)
form = '%%0%dx' % self.para_len
form = form * 3
return form % (X3, Y3, Z3)
def _convert_jacb_to_nor(self, Point): # Jacobian加重射影坐标转换成仿射坐标
if Point is None:
return None
len_2 = 2 * self.para_len
x = int(Point[0:self.para_len], 16)
y = int(Point[self.para_len:len_2], 16)
z = int(Point[len_2:], 16)
z_inv = pow(
z, int(default_table['p'], base=16) - 2, int(default_table['p'], base=16))
z_invSquar = (z_inv * z_inv) % int(default_table['p'], base=16)
z_invQube = (z_invSquar * z_inv) % int(default_table['p'], base=16)
x_new = (x * z_invSquar) % int(default_table['p'], base=16)
y_new = (y * z_invQube) % int(default_table['p'], base=16)
z_new = (z * z_inv) % int(default_table['p'], base=16)
if z_new == 1:
form = '%%0%dx' % self.para_len
form = form * 2
return form % (x_new, y_new)
else:
return None
def verify(self, Sign, data):
if Sign is None or Sign == '':
return None
r = int(Sign[0:self.para_len], 16)
s = int(Sign[self.para_len:2*self.para_len], 16)
e = int(data.hex(), 16)
# 参数合法性
if not (1 <= r < int(default_table['n'], base=16) and 1 <= s < int(default_table['n'], base=16)):
return False
t = r + s
if t == 0:
return False
else:
t = t % int(default_table['n'], base=16)
# if self.public_key is None or self.public_key == '':
# return None
P1 = self._kg(s, default_table['g'])
# print(P1)
if P1 is None:
return False
P2 = self._kg(t, self.public_key)
if P1 == P2:
P1 = '%s%s' % (P1, 1)
P1 = self._double_point(P1)
else:
P1 = '%s%s' % (P1, 1)
P1 = self._add_point(P1, P2)
P1 = self._convert_jacb_to_nor(P1)
x = int(P1[0:self.para_len], 16)
# print(x)
print('%064x' % ((r - x) % int(default_table['n'], base=16)))
return r == ((e + x) % int(default_table['n'], base=16))
def sign(self, data):
k = 1
k = secrets.randbelow(int(default_table['n'], 16) - 1) + 1
if not (1 <= k <= int(default_table['n'], base=16)- 1):
return None
E = data.hex()
e = int(E, 16)
if self.private_key is None or self.private_key == '':
return None
d = int(self.private_key, 16)
P1 = self._kg(k, default_table['g'])
x = int(P1[0:self.para_len], 16)
A = ((e + x) % int(default_table['n'], base=16))
if A == 0 or A + k == int(default_table['n'], base=16):
return None
d_1 = pow(
d+1, int(default_table['n'], base=16) - 2, int(default_table['n'], base=16))
B = (d_1*(k + A) - A) % int(default_table['n'], base=16)
# print('%064x' % ((A-x)%int(default_table['n'], base=16)))
if B == 0:
return None
else:
return '%064x%064x' % (A, B)
if __name__ == '__main__':
crypt = Crypt(
# 公钥格式为64字节的16进制字符串
public_key='',
# 私钥格式为32字节的16进制字符串
private_key=''
)
data = 'cd3b51d2e0e67ee6a066fbb995c6366ae220d3ab2f5ff949e261ae800688cc5b'
# sign = crypt.sign(bytes.fromhex(data))
sign = "FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D541220000000000000000000000000000000000000000000000000000000000000001"
verify = crypt.verify(sign,bytes.fromhex(data))
print(verify)
评论