TetCTF 2020-yaecc
题目描述如下：Who knows the backdoor wins!nc 207.148.119.58 7777审计代码可知，题目模拟了一版ECDSA（NIST-p256 曲线）的实现，我们的任务是根据若干消息/签名对来求私钥，为了便于描述我们先描述一下本题用到的符号系统：(R,S):签名
a:私钥
k:nonce
H:msg的哈希值
N:曲线的点群阶在ECDSA中，有如下表达式成立：R*a − S*k + H ≡ 0 (mod N)根据ECDSA算法，当对消息进行签名时，nonce应当随机均匀的从区间CVP问题。假设我们已经收集了D对消息/签名对，此时有：Ri*a − Si*ki + Hi ≡ 0 (mod N) i=1,2,3,...,D等式两边乘上Si的逆，得：(Si^(-1))*Ri*a − ki + (Si^(-1))*Hi ≡ 0 (mod N)设Ai = (Si^(-1))*Ri，Bi = -(Si^(-1))*Hi，整理得：Ai*a ≡ Bi + ki (mod N)即：Ai*a - li*N = Bi + ki （li为整数）将方程用向量形式表示如下：其中(1/2**16)是根据256（a的比特数）-240（k的比特数）= 16计算而来。对于每一个表达式Ri*a − Si*ki + Hi ≡ 0 (mod N)来讲，一对消息/签名对就可以提供私钥的16比特的信息，因此理论上来讲D（即消息/签名对的对数）= 256/16 = 16即可，在写脚本时我们收集的数量比这一理论值略多一些即可。将上述推导写成SageMath代码形式如下：from sage.all import *
from pwn import *
from hashlib import sha256
import os
from Crypto.Util.number import bytes_to_long
EC = EllipticCurve(
GF(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff),
[-3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b]
)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
Zn = Zmod(n)
G = EC((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))
P = G
Q = EC((0xc97445f45cdef9f0d3e05e1e585fc297235b82b5be8ff3efca67c59852018192,
0xb28ef557ba31dfcbdd21ac46e2a91e3c304f44cb87058ada2cb815151e610046))
pubkey = EC((50590195252452518804028762265927043036734617153869060607666882619539230027822,
36611353725619757431858072740028832533174535444901899686884685372270344860185))
class DualEcDrbg(object):
def __init__(self, seed):
self.s = ZZ(bytes_to_long(seed))
def next_bits(self):
self.s = ZZ((self.s * P))
return ZZ((self.s * Q)) & (2 ** 240 - 1)
def sign(private_key, message, rand):
z = Zn(ZZ(sha256(message).hexdigest(), 16))
k = Zn(rand.next_bits())
assert k != 0
K = ZZ(k) * G
r = Zn(K)
assert r != 0
s = (z + r * private_key) / k
assert s != 0
return r, s
data = []
for _ in range(50):
s = remote("207.148.119.58", 7777)
m = eval(s.recvline())
sig = eval(s.recvline())
data.append((m, sig))
s.close()
print len(data)
print data
with open("data.txt", "w") as f:
f.write(str(data))
size = 20
m = []
Ai = [-1]
Bi =
r0, s0 = map(Zn, data)
z0 = Zn(ZZ(sha256(str(data)).hexdigest(), 16))
for i in range(size):
message, sig = data
ri, si = map(Zn, sig)
zi = z = Zn(ZZ(sha256(str(message)).hexdigest(), 16))
A = - (s0 * ri) / (r0 * si)
B = (z0 * ri) / (si * r0) - zi / si
Ai.append(A)
Bi.append(B)
Ai.append(0)
Bi.append(n//2^16)
m.append(Ai)
for i in range(size):
m.append(*(i+1) + + *(size-i))
m.append(Bi)
m = Matrix(ZZ, m)
mLLL = m.LLL()
for irow, row in enumerate(mLLL):
k0 = Zn(row)
d = (s0*k0-z0)/r0
if pubkey == ZZ(d)*G:
print d
break
k0 = Zn(-row)
d = (s0*k0-z0)/r0
if pubkey == ZZ(d)*G:
print d
break
msg2 = b"I am admin"
rand = DualEcDrbg(os.urandom(16))
sig = sign(ZZ(d), msg2, rand)
s = remote("207.148.119.58", 7777)
s.sendline(str(sig))
ret = s.recvline()
print ret执行脚本即可得到flag：TetCTF{_0oops____Sm4ll_k_ru1n3d_th3_p4rty_}
支持学逆向论坛，资源不错！
页:
[1]