# L3HCTF2021 > 阿巴阿巴，周末白天忙了一整天学校的事，晚上挂机跑了一晚还是没跑出来捏 ## EzECDSA This challenge use SECP256k1 curve to generate the generator ec system we get 100 sets of signatures and the task.py tells us the low-8bits of K leak：$kp = K\;mod\;256$ and [question-44644 on stackexchange](https://crypto.stackexchange.com/questions/44644/how-does-the-biased-k-attack-on-ecdsa-work) says its a problem of [Elliptic Curve Digital Signature Algorithm with Partially Known Nonces](https://pdfs.semanticscholar.org/0eb1/8a42b623dd8e7cdd4221085a6fd5503708ea.pdf) In there，known nonce is low-8bits >The idea is to convert the determination of a private key from biased k nonces in several ECDSA signatures into instances of the hidden number problem (HNP), and then solve the HNP as a reduction to the closest vector problem(CVP). At least ,we kwon we can turn sequence S into a Linear structure and the answer also tells us,how to turn the equation in a HNP you can write k as $k = a + 2^\ell b$ then perfect,without any problem Define  and you have $xt = u + b$ construct sequence  Then,construct a matrix out of basis vectors: which from this [article](https://eprint.iacr.org/2019/023.pdf) ![](https://gitee.com/ljahum/images/raw/master/img/20211115110741.png) so,we should to find a beautiful B ,Then make $S_T=B/p$ $S_U=B$ and if you are palying with a good luck most likely, you'll see the next-to-last entry of next-to-last row containing a dA or -dA --- unfortunately，the lattice in paper seems not very efficient and [@BitLogiK](https://github.com/bitlogik/lattice-attack) gives a efficient way to make the boundary valid His way of constructing denotation: $T_i=2\cdot2^{\ell}\cdot \frac{R_i}{2^{\ell}\cdot S_i} \;mod\;n$ $U_i=(2\cdot 2^{\ell}\cdot \frac{KP_i-H_i}{2^{\ell}\cdot S_i} \;mod\;n)+n$ $Q'=2\cdot 2^{\ell}\cdot n$ $C_t=1$ $C_u=q$ new lattice looks like this:  then,the privacy will lay in next-to-last col Obviously,I python def test_result(mat, target_pubkey, curve): mod_n = ecdsa_lib.curve_n(curve) for row in mat: candidate = row[-2] % mod_n if candidate > 0: cand1 = candidate cand2 = mod_n - candidate if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand1, curve): return cand1 if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand2, curve): return cand2 return 0  ### solve > recv data into a jsonfile and set lattice_attack.py options > and get flag by hand > > or copy others code to have a happy day 😀 python #! python3 import icecream import string from icecream import * from pwnlib.util.iters import mbruteforce from pwn import * from hashlib import sha256 from tqdm import tqdm from rich.progress import track from rich.traceback import install install() # ----------------------------------- table = string.ascii_letters+string.digits from Crypto.Util.number import * io = remote('0.0.0.0',23331) def gopow(): s=io.recvuntil("XXXX+".encode("utf-8")) s=io.recvuntil(")".encode("utf-8")) suffix=s[:-1] s=io.recvuntil("==".encode("utf-8")) s=io.recvuntil("\n".encode("utf-8")) cipher=s[1:-1].decode() ic(cipher) ic(suffix) # ic("AAAA".encode() + suffix) # ic(sha256("AAAA".encode() + suffix).hexdigest()) proof = mbruteforce(lambda x: sha256(x.encode() + suffix).hexdigest() == cipher, table, length=4, method='fixed') ic(proof) io.sendlineafter("Give me XXXX:", proof) gopow() pubkey=eval(io.recvline()) data={} from tqdm import tqdm from os import system data["curve"]="SECP256K1" data["public_key"]=[pubkey,pubkey] #data["message"]="0".encode("utf-8") data["known_type"]="LSB" data["known_bits"]=8 data["signatures"]=[] for i in tqdm(range(100)): io.recvuntil("ge:".encode("utf-8")) io.sendline("0".encode("utf-8")) io.recvuntil("r =".encode("utf-8")) ( ()) r=int(io.recvline()) io.recvuntil("s =".encode("utf-8")) s=int(io.recvline()) io.recvuntil("kp =".encode("utf-8")) kp=int(io.recvline()) io.recvuntil("hash =".encode("utf-8")) hsh=int(io.recvline()) (data["signatures"]).append({"r":r,"s":s,"kp":kp,"hash":hsh}) f=open("data.json","w") import json f.write(json.dumps(data)) f.close() system("python3 lattice_attack.py -f data.json") d=eval(input("plz input the ans\n")) io.sendline(str(d).encode("utf-8")) io.interactive()  ![](https://gitee.com/ljahum/images/raw/master/img/20211118165619.png) ### The curse of ECDSA nonces In the [question-44644 on stackexchange](https://crypto.stackexchange.com/questions/44644/how-does-the-biased-k-attack-on-ecdsa-work) we know how to solve HNP of **bias nonce ecdsa** And [Minerva: The curse of ECDSA nonces](https://eprint.iacr.org/2020/728.pdf) shows us the attack in detail ![](https://gitee.com/ljahum/images/raw/master/img/20211118163035.png) Obviously，the primitives is not what we should focus on --- ![](https://gitee.com/ljahum/images/raw/master/img/20211118163842.png) > remove U to raise speed？ - So mul $2^\ell$to T and U to - add a N to U So，we make make an effort to make the boundary valid? :D