不得其名的白盒

分类： 格密码

  • AHSSP

    h=a*A-se mod p,行向量a,行向量xi组成的矩阵A，行向量e ,知h,e,p求s
    思路大体与HSSP相同，构造正交矩阵M,使hM=aAM-seM modp

    做如下的格：

    M1(h1 e1 1 0 0 0  0
M2 h2 e2 0 1 0 0  0
M3 h3 e3 0 0 1 0  0
M4 h4 e4

Mm hm em 0 0 0 0  1
k1 p  0  0 0 0 0  0
k2 0  p  0 0 0 0  0)=
   0  0  M1 M2 M3  Mm

    之后的处理和HSSP一样

    脚本： 
    from Crypto.Util.number import *
 
def ahssp(h:list, e:list, n:int, m:int, p:int):
    
    tmp = block_matrix([[vector(h).column(), vector(e).column()]])
    Ge = block_matrix([[tmp, identity_matrix(m)],[identity_matrix(2)*p,zero_matrix(2, m)]])
    # Ge[:,:2] *= p
    L = Ge.BKZ()
    M = L[:m-n,2:]
    A_ = M.right_kernel().matrix()
 
    e_ = matrix(ZZ, [1] * m)
    B = block_matrix([[-e_],[2*A_]])
 
    L = B.BKZ()
    assert set(flatten(list(map(list, L)))) == {-1,1}
 
    E = matrix(ZZ, [[1]*L.ncols() for _ in range(L.nrows())])
    L = (L + E) / 2
    assert set(L[0]) == {0}
 
    L = L[1:]
    space = A_.row_space()
 
    A = []
    e_ = vector(ZZ, [1] * m)
    for i in L:
        if i in space:
            A += [i]
            continue
        i = e_ - i
        if i in space:
            A += [i]
            continue
        return None
 
    A = matrix(Zmod(p), A)
    L = block_matrix(ZZ, [[vector(e).column(), matrix.identity(m)],[p, zero_matrix(1, m)]])
    L[:, :1] *= p
    L = L.LLL()
    res = []
    for row in L:
        if row[0] == 0:
            res.append(row[1:])
    M = matrix(res)
    assert all(i == 0 for i in vector(e) * M.T % p)
    
    a = (A*M.T).solve_left(vector(h)*M.T)
    s = matrix(e).solve_left(a*A-vector(h))
    assert len(s) == 1
 
    return A, a, int(s[0])
 
if __name__ == "__main__":
    p = ...
    n = ...
    m = ...
    e = ...
    h = ...
    A,a,s = ahssp(h,e,n,m,p)

  • HSSP

    基础知识前导：

    右零空间：对于一个矩阵A,存在矩阵B使A*B=0,B是A的右零空间

    特征：

    对于 h=a∗AmodMh=a*A mod M ,a是行向量，A是目标矩阵，其中一行是flag(A是二进制流）（h,M已知，a,A未知)

    思路：构造列向量u,使hu=aAu=0 mod M,具体展开得到每一行，列对应的和hiui=0 mod M

    u1(h1 1
u2 h2 0 1
u3 h3 0 0 1

um hm 0 0 0 0    1
-k M  0 0 0 0    0)=
  (0,u1,u2,     um) 
   #如此构造矩阵可以得到他的右0矩阵，当A*u=0,此时u是短向量(A是短向量）

    根据矩阵性质：这里刚刚得到的记为LX,其维数为m-n(线代知识)

    此时再用python求出他的左零空间为U,有U*t(倍数）=A

    （此时不能直接对U BKA,因为他是A的进一步线性组合）

    构造B=(b’1’（设为e),2U)的列向量，用‘1’流来控制大小

    (e∗∗T,t)∗B=(2Xi−e)(列向量）（Xi为A的每一行）(e**T,t)*B=(2Xi-e)(列向量）（Xi为A的每一行）

    这个时候可以对B LLL就可以得到（2Xi-e),恢复得到A ,转译每一行可否成为有意义bit

    示例题干： 
    from Crypto.Util.number import *
from secrets import flag
from sage.all import *
def derive_M(n):
    iota=0.035
    Mbits=int(2 * iota * n^2 + n * log(n,2))
    M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
    return Integer(M)
m = bytes_to_long(flag).bit_length()
n = 70
p = derive_M(n)
F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, list(bin(bytes_to_long(flag))[2:]))
h = x*A
with open("data.txt", "w") as file:
    file.write(str(m) + "\n")
    file.write(str(p) + "\n")
    for item in h:
        file.write(str(item) + "\n")
    解题： 
    def checkMatrix(M, wl=[-1, 1]):
    M = [list(i) for i in list(M)]
    ml = list(set(flatten(M)))
    return sorted(ml) == sorted(wl)
def hssp_solve(n,m,M,h):
    ge1 = [[0]*m for _ in range(m)]
    tmp = pow(h[0], -1, M)
    for i in range(1,m):
        ge1[i][0] = -h[i]*tmp
        ge1[i][i] = 1
    ge1[0][0] = M
    Ge1 = Matrix(ZZ,ge1)
    L1 = Ge1.BKZ()
    Lx_orthogonal = Matrix(ZZ, L1[:m-n])
    Lx = Lx_orthogonal.right_kernel(algorithm='pari').matrix()
    e = Matrix(ZZ, [1] * m)
    B = block_matrix([[-e], [2*Lx]])
    L2 = B.BKZ()
    assert checkMatrix(L2)
    E = matrix(ZZ, [[1]*L2.ncols() for _ in range(L2.nrows())])
    L2 = (L2 + E) / 2
    assert set(L2[0]) == {0}
    L2 = L2[1:]
    space = Lx.row_space()
    Lx2 = []
    e = vector(ZZ, [1] * m)
    for lx in L2:
        if lx in space:
            Lx2 += [lx]
            continue
        lx = e - lx
        if lx in space:
            Lx2 += [lx]
            continue
        return None
    Lx = matrix(Zmod(M), Lx2)
    vh = vector(Zmod(M), h)
    va = Lx.solve_left(vh)
    return Lx, va
n = ?
m = ?
M = ?
h = ?
A,a = hssp_solve(n,m,M,h)
for row in A:
    ans = "".join(str(i) for i in row)
    try:
        print(long_to_bytes(int(ans,2)).decode())
    except:
        None

  • LCG STATE 高位

    题干： 
    from Crypto.Util.number import *
from secret import seed,flag
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()
assert flag == '0xGame{' + MD5(seed) + '}'
assert seed.bit_length() == 256

class LCG:
    def __init__(self,bits:int,seed:int):
        self.m = getPrime(bits+1)
        self.a = getPrime(bits)
        self.b = getPrime(bits)
        self.cur = ( self.a * seed + self.b ) % self.m
 
    def extract(self):
        ret=self.cur >> 115#截断低位，等价于%2**n，输出流截断（r0+k*2**115=c0)
        self.cur = ( self.a * self.cur + self.b ) % self.m
        return ret
 
lcg=LCG(bits=256,seed=seed)
 
out = []
for _ in range(20):
    out.append(lcg.extract())
 
print(f'm = {lcg.m}')
print(f'a = {lcg.a}')
print(f'b = {lcg.b}')
print(f'out = {out}')
'''
m = 181261975027495237253637490821967974838107429001673555664278471721008386281743
a = 80470362380817459255864867107210711412685230469402969278321951982944620399953
b = 108319759370236783814626433000766721111334570586873607708322790512240104190351
out = [2466192191260213775762623965067957944241015, 1889892785439654571742121335995798632991977, 1996504406563642240453971359031130059982231, 1368301121255830077201589128570528735229741, 3999315855035985269059282518365581428161659, 3490328920889554119780944952082309497051942, 2702734706305439681672702336041879391921064, 2326204581109089646336478471073693577206507, 3428994964289708222751294105726231092393919, 1323508022833004639996954642684521266184999, 2208533770063829989401955757064784165178629, 1477750588164311737782430929424416735436445, 973459098712495505430270020597437829126313, 1849038140302190287389664531813595944725351, 1172797063262026799163573955315738964605214, 1754102136634863587048191504998276360927339, 113488301052880487370840486361933702579704, 2862768938858887304461616362462448055940670, 3625957906056311712594439963134739423933712, 3922085695888226389856345959634471608310638]
'''
    解题：

    #模型：c0=a*seed+b,r0=c0*2**115,ci+1=a*ci+b modm,ri=ci*2**115
    #转换成真正的模型：C0=a*seed+b omdm,Ci+1=a*Ci+b mod m,但每一个得到的Ci截断
    #目标C0,其实还是ECDSA的那种类型,r0是小量
    #每一个输出泄露257-115=142bit，142*20=2840
    #隐藏20*115+seed.bit_length=2556,符合信息论

    from Crypto.Util.number import *
from hashlib import md5
 
def MD5(m):return md5(str(m).encode()).hexdigest()
m = 181261975027495237253637490821967974838107429001673555664278471721008386281743
a = 80470362380817459255864867107210711412685230469402969278321951982944620399953
b = 108319759370236783814626433000766721111334570586873607708322790512240104190351
c = [2466192191260213775762623965067957944241015, 1889892785439654571742121335995798632991977, 1996504406563642240453971359031130059982231, 1368301121255830077201589128570528735229741, 3999315855035985269059282518365581428161659, 3490328920889554119780944952082309497051942, 2702734706305439681672702336041879391921064, 2326204581109089646336478471073693577206507, 3428994964289708222751294105726231092393919, 1323508022833004639996954642684521266184999, 2208533770063829989401955757064784165178629, 1477750588164311737782430929424416735436445, 973459098712495505430270020597437829126313, 1849038140302190287389664531813595944725351, 1172797063262026799163573955315738964605214, 1754102136634863587048191504998276360927339, 113488301052880487370840486361933702579704, 2862768938858887304461616362462448055940670, 3625957906056311712594439963134739423933712, 3922085695888226389856345959634471608310638]
 
ge = [[0]*21 for i in range(21)]
#画图更好理解
for i in range(19):
    ge[i][i] = m
ge[-2][-2],ge[-1][-1] = 1,1
ge[-2][0], ge[-1][0]  = a,a*(c[0]<<115)+b-(c[1]<<115)
for i in range(1,19):
    ge[-2][i]=a^(i+1)
    ge[-1][i]=ge[-1][i-1]*a+a*(c[i]<<115)+b-(c[i+1]<<115)
 
Ge = Matrix(ZZ,ge)
Ge = Ge.LLL()
assert Ge[0][-1] == 1
state = abs(Ge[0][-2])+(c[0]<<115)
seed = pow(a,-1,m)*(state-b)%m
print(seed)
print('0xGame{' + MD5(seed) + '}')
 
# 101639613050544872292192629515273562035022699788445344858455157668840828973361
# '0xGame{459049e068d93f6d70f1ea0da705264a}'

    这道题的变形控制是最难的，这道题结束后HNP就差不多理解了

  • LCG HNP

    题干： 
    from Crypto.Util.number import getPrime, inverse
from secret import seed, flag
from hashlib import md5
 
def MD5(m):return md5(str(m).encode()).hexdigest()
assert flag == '0xGame{' + MD5(seed) + '}'
assert seed.bit_length() == 510
 
class LuanGao:
    def __init__(self, bits:int, seed:int):
        self.bits = bits
        self.m = getPrime(self.bits)
        self.a = getPrime(self.bits // 2)
        self.cur = (self.a * seed) % self.m
 
    def extract(self):
        ret = self.cur
        b = getPrime(self.bits // 4)
        self.cur = ( self.a * self.cur + b ) % self.m
        return ret
 
C = LuanGao(512, seed)
Cs = [C.extract() for _ in range(5)]
 
print(f'Cs = {Cs}')
print(f'C.m = {C.m}')
 
'''
Cs = [11804527453299586684489593808016317337345238230165321056832279785591503368758306671170625597063579251464905729051049524014502008954170088604924368057540940, 4930922884306486570759661288602557428608315558804950537470100263019228888817481617065454705843164809506859574053884206133344549895853064735361336486560981, 5380263856446165449531647111260010594620416730932539097782399557603420658350407080366132490174060420530708293564252852668431923560882648691392446521188465, 10746696290782998433216934286282230556131938525513632178308443345441147075710552571129957873399395862207656161609046567289600084193860244770966610161184627, 2195032957511830992558961021566904850278796737316238566513837995297394215638259916944087623923636789312134734949452839561765171446217520081402769962517110]
C.m = 12813864523019740432913161815051292412705285817864701047922722497269479288096574264414061282833203433542813637861620032851255308640850882149603687035724753
'''
#题干解读：C为未知，a未知，有4条方程，Ci+1=a*Ci+bi mod m,有4组方程（Ci循环生成）
    解题： 
    #注意量级，b的量级比其他的量级小，这时b是泄露，4条b的bit量和a相同，符合信息论
#还原式子：Ci+1=a*Ci+bi mod m,其中C0就是a*seed%m,想要还原C0,要还原出a
#其实这个时候就已经可以套公式知道是HNP了，标准构造
from Crypto.Util.number import *
from hashlib import md5
def MD5(m):return md5(str(m).encode()).hexdigest()
m = 12813864523019740432913161815051292412705285817864701047922722497269479288096574264414061282833203433542813637861620032851255308640850882149603687035724753
c = [11804527453299586684489593808016317337345238230165321056832279785591503368758306671170625597063579251464905729051049524014502008954170088604924368057540940, 4930922884306486570759661288602557428608315558804950537470100263019228888817481617065454705843164809506859574053884206133344549895853064735361336486560981, 5380263856446165449531647111260010594620416730932539097782399557603420658350407080366132490174060420530708293564252852668431923560882648691392446521188465, 10746696290782998433216934286282230556131938525513632178308443345441147075710552571129957873399395862207656161609046567289600084193860244770966610161184627, 2195032957511830992558961021566904850278796737316238566513837995297394215638259916944087623923636789312134734949452839561765171446217520081402769962517110]
ge = [
[m,0,0,0,0,0],
[0,m,0,0,0,0],
[0,0,m,0,0,0],
[0,0,0,m,0,0],
[c[0],c[1],c[2],c[3],1,0],#这里构造少许不同，有2行C，因为式子是C-C
[c[1],c[2],c[3],c[4],0,1]]#依然是竖解，最后得到（b,b,b,b,-a,1)
Ge = Matrix(ZZ,ge)
L = Ge.LLL()
a = abs(L[0][-2])#取得a
seed = c[0]*inverse(a,m)%m
print(seed)
print('0xGame{' + MD5(seed) + '}')
# '0xGame{2db84757dd4197f9b9441be25f35bfd5}'
# 2512273436977220996062855314655393786244910444920037228737234078954182704102442213664768806368325362960908940985195233026259876194811260795362098878115082

    这道题核心是新的变形构造方式，不过也很好理解（有2行C，因为式子是C-C）

  • ECDSA HNP

    示例题干： 
    from hashlib import *
from secrets import randbelow
from ecdsa import SigningKey, SECP160r1, util

leak = 3
total = 61
mask = (1 << leak) - 1

def main():
    sk = SigningKey.generate(curve=SECP160r1)
    vk = sk.verifying_key
    q = SECP160r1.order
    print(hex(vk.pubkey.point.x()))
    print(hex(vk.pubkey.point.y()))
    d = sk.privkey.secret_multiplier
    flag = "DesCTF{" + md5(str(d).encode()).hexdigest() + "}"
    for i in range(total):
        msg = f"msg-{i}".encode()
        digest = sha1(msg).digest()
        h = int.from_bytes(digest, "big") % q
        k = randbelow(q - 1) + 1
        sig = sk.sign_digest(digest, sigencode=util.sigencode_string, k=k)
        r, s = util.sigdecode_string(sig, q)
        print(f"({hex(h)}, {hex(int(r))}, {hex(int(s))}, {hex(k & mask)}),")


if __name__ == "__main__":
    main()
"""
0x8e0a0071e8cf437efec4233ff8444a4ff8adba2f
0xa869fce702b70799c443b450a4d41cc4f65b3eee
(0x525931a9ff8ef95025939a57275ecedc2730421f, 0x5288ed7146c188ebda9b6c8909726c3d6f957891, 0x334c301c2d861fa8cceecabc542a5cb7dd7df7d9, 0x6),
(0x4b21047e1112dbfee487b4f23471f2fb438e268, 0x82878368ef18996109bf10adae81e1acaeb9fa25, 0xd4d9ec1faa9534a3fa4ff0fe78488ebf175cdfec, 0x4),
(0xdd2e98102508e178fdf1e289ac8342250da6408f, 0x38069b3213a57a077a38938d082a7590d0a21b95, 0xcff1f76af8f15422bb288c8af372332cc6ace970, 0x1),
(0xecb8547ea2a68788665e01a7025093c47f2b45de, 0x6f7155ce9da5434227e48554a0bef7d7492cadb, 0x53f6e1a52554436620b392dea75738b5f670d2b2, 0x2),
(0xefb887600edf8d279f3cca868ef641e9284ae769, 0x9caea57dd4681d1ab53029cf631a47277386bc72, 0xce7743df557c732daff4595d8430ea8485ab3aca, 0x3),
(0x957ec8b7a53dea95d53a5c94d595b834c2be61ca, 0x1b24031194de7dac370a2f7c9be316dc14cbe3f2, 0xc40b5c4c674d1f4cb99891bf342f8acebca9258b, 0x5),
(0x8ba1946c16b7c8d98c6e01836ae0d791ecae07d9, 0x6daec7923c03c56a18d764d9497c39871912fb1a, 0x717b2cf60cc5416eb3f1666e79f30d538f5c9038, 0x5),
(0x72337b25f3486e8518d8f3a4da21724cf3977246, 0xff88c0ddcdcdfb98ca50b68c035434ee2e81cd1d, 0x748e1c374d1efdcb3b9bd7b3c812213ddc1ab940, 0x4),
(0xa71275186b7bbc9747c5831b1e4c75f1bd3eae7a, 0x43b995ded8fddfa6365a51d547456376c8f79b88, 0x6c9a0e390dc7d40900f412313dfe0deb8a5cbb45, 0x6),
(0x926bff0ea87d5c1e8c9da39ceb01a10d1b3c0709, 0xaeb5012cbaf479dd3c2d297ba3a80d344ab22f57, 0xa3eff29dffaed0371d860e291c8f65eb287918ce, 0x3),
(0xdc9e51d365f8a827988cf70c4913d987343dc74a, 0xa6940f2d3f38d0d4b20c36b24f4f91b5bdee59c1, 0xb3a7373eeaf10e449aca7e3cc00f6f554ff0473f, 0x4),
(0x2bcbef8732ab1e591dff595cb1c979f90ebadf0c, 0x3b629a50ab44f67f762dff710653c1fa995863c1, 0x7425a16af106e5eba3a0f751baba95708ead3c0, 0x1),
(0x6a0eadeed0b9e7e900df27d5e253968c30f0f6bd, 0x47e22a97f4dfee66b8b04983bbfbfe0374fa917d, 0xfadb3f2a5b347b9fa8cfdaeddecb1215f19ec707, 0x7),
(0x884675226091712e22a0fbf1fa3c0de95fa09dae, 0x6549eabd7fd5bc6832e2ab061fb02d0f1df6b19a, 0xb660a3baf9d96985c3b8d420259003b8fc0a4410, 0x2),
(0x2a81e382054ed9523f5e4d2a966252b51046325d, 0x81f663abbd508d6df460a1d5a857829834a969ac, 0xe51bcf400dd3fddb5b9f13fd0403b3af011f9fc6, 0x4),
(0x25f6147e13fc52aaf92b1622134c52dff9ec282d, 0x76e457adf428f8a1a82711584e336c0b3b70e94e, 0x6af1ced8354c4bdf84fc55fef847848d4dad83e6, 0x3),
(0xfe0eba650a95051d8fa04f43824d465fdad34493, 0xadd5339288e5527a394a602a2f4e891dbdf8d7aa, 0x169a5d1b893fa66e35ec2620bc96f73d067c9460, 0x3),
(0xb8914a5d41cdd7ff1f0eed7e6eab2e79fabfde5b, 0xf6673ed83fe9731508921bfc12773a19980e5345, 0x83710a069298113cfc91d716a38e1584b2606033, 0x5),
(0xae25b8812cc4f7fec5a14f4174328be0a254cc26, 0x16381c71aa45674488d8b1a10ff0a16d4fd6c997, 0xa947337c2f9d0efe9e69f3a5332c7d0887937643, 0x0),
(0xd8bc55b669d86fe42448a83063aea36251b5fe75, 0x8050afa80843f0162c7fa5323cf19f4f194f90ec, 0x9207917cde2804eb97708cb3392610f716e8c5c, 0x4),
(0xabf778fe7279f34fe6f883d56b938ec46bafb21, 0xf1e96791da0ebc0981eb60fae9509f3c973d5df7, 0xf3f07a604cde6a2164601357cfde0c4b2200fb44, 0x5),
(0x8bbc50d04d2841668fc639c0a0f5ae2cd9f13e03, 0xfa4107e471bd396a25b3853ec09a56c49343cfa3, 0xaf2d6a8142fcf028ce8aabc31377c6d7c63bc9c3, 0x7),
(0xd3db7034072a88a03f7a632fdc3f5a07846c79c3, 0x463871a92ceba68a12ab4d02759ff1aec24c9355, 0xc61b3931ecf8330d4b26b9175efa8690161d25b4, 0x4),
(0x5d5672957260b5794e305ee24bccc07f8dd34d94, 0x7c27bdada7014240c904d42c5a1a1e5f38ea9826, 0x779a7fcc0582e3d901494a98b8d9aa1b8d5f5840, 0x7),
(0x1d197eefd0a6c59ea8f3cfc69c066ce92d7f6e96, 0x665a2ba8a286880c09e2c9ea9adb7479d5bc123d, 0x6377c18c0cf75070627ef9613af864be815eeed6, 0x4),
(0x9c7975f4b345048f7e2d3614d5fdcf162be0d920, 0xf2142d01b4b7c2a5585c8458366c716729ee3329, 0x1dd8903dafda53bfe000f606bceee5b31816f683, 0x7),
(0x5062cb7d6e3b50df1820f5996962b5b8b1fc4617, 0xaa47856eecf23e8ef0f212ed3a978f4d5564d650, 0xa02ffbb157a74b3f105895cbe487c6e1da411070, 0x0),
(0xcdfcb6ff93ca01a2755c0c8f0ad8ee04118e1b9e, 0x1fdc78b5968fbd65351406a0e7cb6f45d9f26a01, 0xcec3c44ec773a31fd3785a998e3526624a504705, 0x3),
(0x65fc356da2a36d35d88c5c5792661d8fe152821c, 0x20a49731ddf37504876ed4303cf8ee52426abbbe, 0xf974613f265ced476f0ad2548eecffcf4b648a9e, 0x7),
(0x59544b829fa1f696558ea62792b85e114e397433, 0x23645dd35469fd873a73db34f1018f08ae7f2c24, 0xe5a23255d9760df1f8d6c8ce1652e0480beb0b7d, 0x2),
(0x8ef11fdbed1a2f64faca70aea2cac44dadd8c14c, 0x640d24c485e9e04b9af2355c07cf7ad430c7ca58, 0x20f0e050124bd754c13b8c2e86dbebaee2132bec, 0x1),
(0x1b5ac91240f6450de7fc5208f0762501790e28b7, 0x7991d2db2512b6463c201f0523ed863ce2a670e8, 0xebf64515f997f18b726cd11a24276ef26505a409, 0x6),
(0xba35a8c66a894fae013ac56c9d6ba538d8cbcf0b, 0xcea24619e5bdd3418da925e3aebd5a3c6f64ef03, 0xb9216f67fe0aa26e374b92ecf4b0c8545522785e, 0x0),
(0xe4e86fdd765bc4d98bc807e3f56ad2f2ef8dbd15, 0x67a9d34b95c25764e1026fd64a0cdadc4f894ef, 0x57f0a006eb1ddbae5b7aaaa3e5a2740c1401c9e2, 0x6),
(0xe582d66c85dda020da90ce0248057e9dff2a0120, 0x8f261523dad715ddc7c992972d8cdab39a0e8920, 0x2bcd65226ab00e4e1117a90b735ea287a921641a, 0x2),
(0x62ac7d9437e54969456ae056289adeaefaccd6bb, 0xe7a23830bdccf8e24a6aa1d84d94cff498f3958a, 0x13d192adc3f46a9a2b624a3a93e6faf243e2120f, 0x7),
(0xd24bfd231c4e6b4b3fe46ec642392e59bf1b7358, 0x51b756a681426525f7194a66375a35185d529813, 0x57a86c9d1fe7fe8ad9b05ea21239cd42bce93ca6, 0x2),
(0xeb0501d2e40edeb6ecad416cfb5d12459de1f32a, 0xc5a4cacf614bc7519130e6727126823d77b51c85, 0xd86708d496f4e4265526247c79931bbc0351237c, 0x0),
(0xb41393d8fe5adbe01ec1ae88aacf8030f990c260, 0xb6997c03f903bc1add14cb98e8741647a60c62ad, 0x2fa481db8208ccfa161e791631d91cc012bff387, 0x5),
(0x851a5f6a1ff9ad28e22858aded0abe1d927f8f47, 0xa35a9a8b26bcbf0a639efd5583c9830aa2834a61, 0x71ed5887fc9b53af96793aa25285227e679923d0, 0x6),
(0x36d5d74fdbb34184f56989136c19526a1e66f284, 0xe2636b99dd8277a5bdf411a2ab44688704682b8b, 0x8fa686e14e0c8c40f507b8e4cc8abf2d8391e13e, 0x3),
(0x136e1685ce0dd8fa72c17db7f71ad3ec08201b0f, 0xf8715b24f37af56cd40108e12d4cd65dfe47b18a, 0x447eb0b48cd17036c130d2c9814df4452645562e, 0x3),
(0x442cd9850919eef698ad67aad25dac1e609042cc, 0x8879c395e3021c4c8e1d4cf3ed7556ddcfe88c98, 0xaf3310936f1bf6f93698081b581b362aa4432c2f, 0x0),
(0xe788598a42acba0d0b7b1f6ec9b230b44a477aad, 0xad119581e7a04cf0b3b1f5197bc27d9684813b36, 0x774ad198691047f7a63714bc633ebf66aa7d2e9d, 0x0),
(0x96db72fa75d1f4ef567ae6b0a6a9b67b6eb925, 0xb2a2d5c2c26fdf25b4ccc5981beff2fbce544bf1, 0x259ef89bfdf867a25f2a45ba31e3b8f01d15ac98, 0x6),
(0xfe84f3657569c6b2f6a820fe72ae29980bb3d3b6, 0x81f40f3434d8a526ae3bdd9229e3b91436c195f2, 0xd9ad8ce4bae25a93282b2d585a3ccc9f76c3cfd2, 0x0),
(0xbd38a3ba51b95b74301f1a375039aadf45cf9500, 0x981371c31ca751800cd9554d120390faa176f90, 0xc687f4008be79d2f747d0d3d373d2908dc99f863, 0x0),
(0x5cf2a3d05d937cb49929f7a5420c77a510f9b9db, 0x43b40c9c33d53a2c03193c499ef7f99c19d36ed2, 0x6efe5e9f33a99b6d6e2b072c52923bbbc6050ee0, 0x4),
(0xb3096421f5e4056f23b5bab000b764a049bff24d, 0x8f826e2bce70b6aa6ec454bc8e9e8cd851ebb165, 0xbb9e3082a3a1bd77fd66bb03772219a944f03e29, 0x7),
(0x3dd4cead2e79dcf86cc7917a579a2dba900bb099, 0x7f75439b0103ed40729a24e7f9846b7c2ca3558, 0x2ebb76dc34c83a60571f14cdf6f8261988a902bd, 0x7),
(0x3180aeb53046ca485f501895ed61e57e8ed27b7, 0x7efbf45c158b115885fb00e2ac5b5df85eef468a, 0x7c97ef4e278686bce1a424a92471b21fcf3658b6, 0x3),
(0x559fa993834a40f6fd31f8a3a2f83da980b2ef84, 0x8785d04f6d97d688f90af33140889e4c7201382a, 0x779f8d284898ca25426208f3a6c3b9455c70eb0d, 0x7),
(0x49a0f529e86a638d1cb71dbd948357d390646128, 0xc5c72505c3807890a11502cfc0286fdf40c924bd, 0xdc242283b58e5d98803c067a4633590e5d1e5d9e, 0x1),
(0xef75ace89af3a7791034ae6161e608384984eb34, 0x61a4d32ca6bdf4f8559cf15bc9be41721575650, 0x8fd9e8a6cdd86a2d960409b124453245b1c92f09, 0x5),
(0xcf0cf859a451378f576de4e10b918fa70b0d0e02, 0x66a7f51a86fe0cd0db57d2025464c1d95384c6c0, 0xcc4673380c3a3cc4545e5644ebaad0ee2205af36, 0x5),
(0xa973fdecf97847abfadc76a530cfaa51a544992f, 0x64ebd081e1e5be70904723e1a786d9581ad4e5a5, 0x58c16e616268863fce12b920e281ad4b1d9d2881, 0x1),
(0x9bbcfa5f87bea52e4df986ecdb89dadf9fe7242b, 0x520b4e89d3e3cd032e5c8c9cfab3f706fe49ca8c, 0x198aa5c2cab8d22845c4f3ea8f710becaba98d13, 0x3),
(0x42abe9b2d14ec440b51362694f93116cf4a8980d, 0x38c3965c6f9c9699476239ea669acc598bf748b6, 0xb47208202e92dbc5ed3d4319dd9e4ceeb21e9ec8, 0x5),
(0x334732df257a5c08e42c56dcd31f3be5cfaa196e, 0xe6387cab10b4e3bff5c72b7a8c47bf3f73812e0c, 0x315e28210455bc5535e6f2a6dcf5a76732ad8c88, 0x3),
(0x825347e82b6ecb7c40353d9282daf9804088f22b, 0xced5ac7b578c4a95a177a283f60437a70232ff0, 0xb647c743e3b4ce3ca95c586bdd14afc41d91ad09, 0x4),
(0xf862df8e80ded401998ce913668155e078f5863f, 0xa73fe4db4136c28cbfc6ee73c800548a0bd463e2, 0xff0395bc6b17d90c38ba263488be5987e3b44890, 0x7),
"""
      解题：

      先回顾一下ECDSA的基础知识，sk是私钥对象G，vk是公钥对象Q，d是私钥（G*d=Q)，h是hash处理后的信息，随机数k,x%q=r,invert(k,q)(h+rd)%q=s是签名对

      这里看到泄露多组数据（达到信息论要求），并且泄露可以用a*x+b表示，识别HNP

      from sage.all import *
from hashlib import md5
q = 0x100000000000000000001f4c8f927aed3ca752257
pubx = 0x8e0a0071e8cf437efec4233ff8444a4ff8adba2f
puby = 0xa869fce702b70799c443b450a4d41cc4f65b3eee
leak = 3
B = 2^leak
data = [
(0x525931a9ff8ef95025939a57275ecedc2730421f,0x5288ed7146c188ebda9b6c8909726c3d6f957891,0x334c301c2d861fa8cceecabc542a5cb7dd7df7d9,0x6),
(0x4b21047e1112dbfee487b4f23471f2fb438e268,0x82878368ef18996109bf10adae81e1acaeb9fa25,0xd4d9ec1faa9534a3fa4ff0fe78488ebf175cdfec,0x4),
(0xdd2e98102508e178fdf1e289ac8342250da6408f,0x38069b3213a57a077a38938d082a7590d0a21b95,0xcff1f76af8f15422bb288c8af372332cc6ace970,0x1),
(0xecb8547ea2a68788665e01a7025093c47f2b45de,0x6f7155ce9da5434227e48554a0bef7d7492cadb,0x53f6e1a52554436620b392dea75738b5f670d2b2,0x2),
(0xefb887600edf8d279f3cca868ef641e9284ae769,0x9caea57dd4681d1ab53029cf631a47277386bc72,0xce7743df557c732daff4595d8430ea8485ab3aca,0x3),
(0x957ec8b7a53dea95d53a5c94d595b834c2be61ca,0x1b24031194de7dac370a2f7c9be316dc14cbe3f2,0xc40b5c4c674d1f4cb99891bf342f8acebca9258b,0x5),
(0x8ba1946c16b7c8d98c6e01836ae0d791ecae07d9,0x6daec7923c03c56a18d764d9497c39871912fb1a,0x717b2cf60cc5416eb3f1666e79f30d538f5c9038,0x5),
(0x72337b25f3486e8518d8f3a4da21724cf3977246,0xff88c0ddcdcdfb98ca50b68c035434ee2e81cd1d,0x748e1c374d1efdcb3b9bd7b3c812213ddc1ab940,0x4),
(0xa71275186b7bbc9747c5831b1e4c75f1bd3eae7a,0x43b995ded8fddfa6365a51d547456376c8f79b88,0x6c9a0e390dc7d40900f412313dfe0deb8a5cbb45,0x6),
(0x926bff0ea87d5c1e8c9da39ceb01a10d1b3c0709,0xaeb5012cbaf479dd3c2d297ba3a80d344ab22f57,0xa3eff29dffaed0371d860e291c8f65eb287918ce,0x3),
(0xdc9e51d365f8a827988cf70c4913d987343dc74a,0xa6940f2d3f38d0d4b20c36b24f4f91b5bdee59c1,0xb3a7373eeaf10e449aca7e3cc00f6f554ff0473f,0x4),
(0x2bcbef8732ab1e591dff595cb1c979f90ebadf0c,0x3b629a50ab44f67f762dff710653c1fa995863c1,0x7425a16af106e5eba3a0f751baba95708ead3c0,0x1),
(0x6a0eadeed0b9e7e900df27d5e253968c30f0f6bd,0x47e22a97f4dfee66b8b04983bbfbfe0374fa917d,0xfadb3f2a5b347b9fa8cfdaeddecb1215f19ec707,0x7),
(0x884675226091712e22a0fbf1fa3c0de95fa09dae,0x6549eabd7fd5bc6832e2ab061fb02d0f1df6b19a,0xb660a3baf9d96985c3b8d420259003b8fc0a4410,0x2),
(0x2a81e382054ed9523f5e4d2a966252b51046325d,0x81f663abbd508d6df460a1d5a857829834a969ac,0xe51bcf400dd3fddb5b9f13fd0403b3af011f9fc6,0x4),
(0x25f6147e13fc52aaf92b1622134c52dff9ec282d,0x76e457adf428f8a1a82711584e336c0b3b70e94e,0x6af1ced8354c4bdf84fc55fef847848d4dad83e6,0x3),
(0xfe0eba650a95051d8fa04f43824d465fdad34493,0xadd5339288e5527a394a602a2f4e891dbdf8d7aa,0x169a5d1b893fa66e35ec2620bc96f73d067c9460,0x3),
(0xb8914a5d41cdd7ff1f0eed7e6eab2e79fabfde5b,0xf6673ed83fe9731508921bfc12773a19980e5345,0x83710a069298113cfc91d716a38e1584b2606033,0x5),
(0xae25b8812cc4f7fec5a14f4174328be0a254cc26,0x16381c71aa45674488d8b1a10ff0a16d4fd6c997,0xa947337c2f9d0efe9e69f3a5332c7d0887937643,0x0),
(0xd8bc55b669d86fe42448a83063aea36251b5fe75,0x8050afa80843f0162c7fa5323cf19f4f194f90ec,0x9207917cde2804eb97708cb3392610f716e8c5c,0x4),
(0xabf778fe7279f34fe6f883d56b938ec46bafb21,0xf1e96791da0ebc0981eb60fae9509f3c973d5df7,0xf3f07a604cde6a2164601357cfde0c4b2200fb44,0x5),
(0x8bbc50d04d2841668fc639c0a0f5ae2cd9f13e03,0xfa4107e471bd396a25b3853ec09a56c49343cfa3,0xaf2d6a8142fcf028ce8aabc31377c6d7c63bc9c3,0x7),
(0xd3db7034072a88a03f7a632fdc3f5a07846c79c3,0x463871a92ceba68a12ab4d02759ff1aec24c9355,0xc61b3931ecf8330d4b26b9175efa8690161d25b4,0x4),
(0x5d5672957260b5794e305ee24bccc07f8dd34d94,0x7c27bdada7014240c904d42c5a1a1e5f38ea9826,0x779a7fcc0582e3d901494a98b8d9aa1b8d5f5840,0x7),
(0x1d197eefd0a6c59ea8f3cfc69c066ce92d7f6e96,0x665a2ba8a286880c09e2c9ea9adb7479d5bc123d,0x6377c18c0cf75070627ef9613af864be815eeed6,0x4),
(0x9c7975f4b345048f7e2d3614d5fdcf162be0d920,0xf2142d01b4b7c2a5585c8458366c716729ee3329,0x1dd8903dafda53bfe000f606bceee5b31816f683,0x7),
(0x5062cb7d6e3b50df1820f5996962b5b8b1fc4617,0xaa47856eecf23e8ef0f212ed3a978f4d5564d650,0xa02ffbb157a74b3f105895cbe487c6e1da411070,0x0),
(0xcdfcb6ff93ca01a2755c0c8f0ad8ee04118e1b9e,0x1fdc78b5968fbd65351406a0e7cb6f45d9f26a01,0xcec3c44ec773a31fd3785a998e3526624a504705,0x3),
(0x65fc356da2a36d35d88c5c5792661d8fe152821c,0x20a49731ddf37504876ed4303cf8ee52426abbbe,0xf974613f265ced476f0ad2548eecffcf4b648a9e,0x7),
(0x59544b829fa1f696558ea62792b85e114e397433,0x23645dd35469fd873a73db34f1018f08ae7f2c24,0xe5a23255d9760df1f8d6c8ce1652e0480beb0b7d,0x2),
(0x8ef11fdbed1a2f64faca70aea2cac44dadd8c14c,0x640d24c485e9e04b9af2355c07cf7ad430c7ca58,0x20f0e050124bd754c13b8c2e86dbebaee2132bec,0x1),
(0x1b5ac91240f6450de7fc5208f0762501790e28b7,0x7991d2db2512b6463c201f0523ed863ce2a670e8,0xebf64515f997f18b726cd11a24276ef26505a409,0x6),
(0xba35a8c66a894fae013ac56c9d6ba538d8cbcf0b,0xcea24619e5bdd3418da925e3aebd5a3c6f64ef03,0xb9216f67fe0aa26e374b92ecf4b0c8545522785e,0x0),
(0xe4e86fdd765bc4d98bc807e3f56ad2f2ef8dbd15,0x67a9d34b95c25764e1026fd64a0cdadc4f894ef,0x57f0a006eb1ddbae5b7aaaa3e5a2740c1401c9e2,0x6),
(0xe582d66c85dda020da90ce0248057e9dff2a0120,0x8f261523dad715ddc7c992972d8cdab39a0e8920,0x2bcd65226ab00e4e1117a90b735ea287a921641a,0x2),
(0x62ac7d9437e54969456ae056289adeaefaccd6bb,0xe7a23830bdccf8e24a6aa1d84d94cff498f3958a,0x13d192adc3f46a9a2b624a3a93e6faf243e2120f,0x7),
(0xd24bfd231c4e6b4b3fe46ec642392e59bf1b7358,0x51b756a681426525f7194a66375a35185d529813,0x57a86c9d1fe7fe8ad9b05ea21239cd42bce93ca6,0x2),
(0xeb0501d2e40edeb6ecad416cfb5d12459de1f32a,0xc5a4cacf614bc7519130e6727126823d77b51c85,0xd86708d496f4e4265526247c79931bbc0351237c,0x0),
(0xb41393d8fe5adbe01ec1ae88aacf8030f990c260,0xb6997c03f903bc1add14cb98e8741647a60c62ad,0x2fa481db8208ccfa161e791631d91cc012bff387,0x5),
(0x851a5f6a1ff9ad28e22858aded0abe1d927f8f47,0xa35a9a8b26bcbf0a639efd5583c9830aa2834a61,0x71ed5887fc9b53af96793aa25285227e679923d0,0x6),
(0x36d5d74fdbb34184f56989136c19526a1e66f284,0xe2636b99dd8277a5bdf411a2ab44688704682b8b,0x8fa686e14e0c8c40f507b8e4cc8abf2d8391e13e,0x3),
(0x136e1685ce0dd8fa72c17db7f71ad3ec08201b0f,0xf8715b24f37af56cd40108e12d4cd65dfe47b18a,0x447eb0b48cd17036c130d2c9814df4452645562e,0x3),
(0x442cd9850919eef698ad67aad25dac1e609042cc,0x8879c395e3021c4c8e1d4cf3ed7556ddcfe88c98,0xaf3310936f1bf6f93698081b581b362aa4432c2f,0x0),
(0xe788598a42acba0d0b7b1f6ec9b230b44a477aad,0xad119581e7a04cf0b3b1f5197bc27d9684813b36,0x774ad198691047f7a63714bc633ebf66aa7d2e9d,0x0),
(0x96db72fa75d1f4ef567ae6b0a6a9b67b6eb925,0xb2a2d5c2c26fdf25b4ccc5981beff2fbce544bf1,0x259ef89bfdf867a25f2a45ba31e3b8f01d15ac98,0x6),
(0xfe84f3657569c6b2f6a820fe72ae29980bb3d3b6,0x81f40f3434d8a526ae3bdd9229e3b91436c195f2,0xd9ad8ce4bae25a93282b2d585a3ccc9f76c3cfd2,0x0),
(0xbd38a3ba51b95b74301f1a375039aadf45cf9500,0x981371c31ca751800cd9554d120390faa176f90,0xc687f4008be79d2f747d0d3d373d2908dc99f863,0x0),
(0x5cf2a3d05d937cb49929f7a5420c77a510f9b9db,0x43b40c9c33d53a2c03193c499ef7f99c19d36ed2,0x6efe5e9f33a99b6d6e2b072c52923bbbc6050ee0,0x4),
(0xb3096421f5e4056f23b5bab000b764a049bff24d,0x8f826e2bce70b6aa6ec454bc8e9e8cd851ebb165,0xbb9e3082a3a1bd77fd66bb03772219a944f03e29,0x7),
(0x3dd4cead2e79dcf86cc7917a579a2dba900bb099,0x7f75439b0103ed40729a24e7f9846b7c2ca3558,0x2ebb76dc34c83a60571f14cdf6f8261988a902bd,0x7),
(0x3180aeb53046ca485f501895ed61e57e8ed27b7,0x7efbf45c158b115885fb00e2ac5b5df85eef468a,0x7c97ef4e278686bce1a424a92471b21fcf3658b6,0x3),
(0x559fa993834a40f6fd31f8a3a2f83da980b2ef84,0x8785d04f6d97d688f90af33140889e4c7201382a,0x779f8d284898ca25426208f3a6c3b9455c70eb0d,0x7),
(0x49a0f529e86a638d1cb71dbd948357d390646128,0xc5c72505c3807890a11502cfc0286fdf40c924bd,0xdc242283b58e5d98803c067a4633590e5d1e5d9e,0x1),
(0xef75ace89af3a7791034ae6161e608384984eb34,0x61a4d32ca6bdf4f8559cf15bc9be41721575650,0x8fd9e8a6cdd86a2d960409b124453245b1c92f09,0x5),
(0xcf0cf859a451378f576de4e10b918fa70b0d0e02,0x66a7f51a86fe0cd0db57d2025464c1d95384c6c0,0xcc4673380c3a3cc4545e5644ebaad0ee2205af36,0x5),
(0xa973fdecf97847abfadc76a530cfaa51a544992f,0x64ebd081e1e5be70904723e1a786d9581ad4e5a5,0x58c16e616268863fce12b920e281ad4b1d9d2881,0x1),
(0x9bbcfa5f87bea52e4df986ecdb89dadf9fe7242b,0x520b4e89d3e3cd032e5c8c9cfab3f706fe49ca8c,0x198aa5c2cab8d22845c4f3ea8f710becaba98d13,0x3),
(0x42abe9b2d14ec440b51362694f93116cf4a8980d,0x38c3965c6f9c9699476239ea669acc598bf748b6,0xb47208202e92dbc5ed3d4319dd9e4ceeb21e9ec8,0x5),
(0x334732df257a5c08e42c56dcd31f3be5cfaa196e,0xe6387cab10b4e3bff5c72b7a8c47bf3f73812e0c,0x315e28210455bc5535e6f2a6dcf5a76732ad8c88,0x3),
(0x825347e82b6ecb7c40353d9282daf9804088f22b,0xced5ac7b578c4a95a177a283f60437a70232ff0,0xb647c743e3b4ce3ca95c586bdd14afc41d91ad09,0x4),
(0xf862df8e80ded401998ce913668155e078f5863f,0xa73fe4db4136c28cbfc6ee73c800548a0bd463e2,0xff0395bc6b17d90c38ba263488be5987e3b44890,0x7)
]
n=len(data)
A=[]
C=[]
for h,r,s,b in data:
    s_inv=inverse_mod(s,q)
    A.append((r*s_inv)%q)
    C.append(((h-b*s)*s_inv)%q)#HNP化简
M=Matrix(ZZ,n+1,n+1)
for i in range(n):
    M[i,i]=q
for i in range(n):
    M[n,i]=A[i]
M[n,n]=B
target=vector(C+[0])
M=M.stack(target)#这里表示把这行加到底下
print("[*] running LLL")
L=M.LLL()
for row in L:
    d=int(row[-1])%q
    if d==0:
        continue
    from ecdsa import SigningKey,SECP160r1
    try:
        sk=SigningKey.from_secret_exponent(d,curve=SECP160r1)
        vk=sk.verifying_key
#这里是检查，用G&自己算出来的d的x,y是否符合题上提供的x,y
        if vk.pubkey.point.x()==pubx and vk.pubkey.point.y()==puby:
            print("d =",d)
           flag="DesCTF{"+md5(str(d).encode()).hexdigest()+"}"
            print("FLAG =",flag)
            break
    except:
        pass

      实际上学下来掌握了基础理解和变形控制，信息论确认，以及多组数据处理变性就差不多了(见LCG）

    • HNP的基础认知

      首先是特征，类似a∗x−b=cmodna*x-b=c modn,要求x, c未知是小数（相对n小也是），有多组数据使得可以求x
      求解基础：一般一组数据得到（x,k,1)时不能确认x,k比例关系使x不正确，这时多组数据在信息论的支撑下，比如这里c是8t时，一次泄露3bit,x如果是150bit,50组数据可以恢复x
      这里用ECDSA的公式s=invert(k,q)(h+dr)modq举例，假设有50组数据，一组泄露k=8*t+b,t未知，b已知
      第一步化简至标准形式：invert(s,q)h-b+drinvert(s,q)=8t mod n

      设invert(s,q)h-b为C,invert(s,q)r为A，得到Ad-C-kq=8*t

      为什么短：8*t相对于q,2157比2160，零头
      第二步，利用i个方程得到一个包含d的短向量，这里方便只显示3组A1,A2,A3

      -k1 (q 0 0 0
      -k2 0 q 0 0
      -k3 0 0 q 0
      d A1 A2 A3 8
      -1 C1 C2 C3 0) 竖着计算

      8t1 8t2 8t3 8d

      这时LLL取row[-1]%q得到8*d（实则是t1,t2,t3,d,这样更短