curve = NIST256p n = curve.order print(f"Curve order n: {n}") private_key = SigningKey.from_secret_exponent(random.randrange(1, n), curve=curve) d = private_key.privkey.secret_multiplier public_key = private_key.get_verifying_key()
messages = [ b"Hello player, welcome to L3HCTF 2025!", b"This is a crypto challenge, as you can probably tell.", b"It's about ECDSA, a very... robust algorithm.", b"I'm sure there are no implementation flaws whatsoever.", b"Anyway, here are your signatures. Good luck!", f"Oh, and the flag is L3HCTF{{{d}}}. Don't tell anyone!".encode(), ] nonce_generator = FlawedNonceGenerator(n) f = open('signatures.txt', 'w')
for i inrange(6): k = nonce_generator.generate_nonce() message = messages[i] h = int.from_bytes(hashlib.sha256(message).digest(), 'big') R = k * curve.generator r = R.x() % n s_inv = pow(k, -1, n) s = (s_inv * (h + d * r)) % n f.write(f"h: {h}, r: {r}, s: {s}\n")
#sage from ecdsa import NIST256p import re n = NIST256p.order
withopen("signatures.txt") as f: lines = f.readlines()
hs, rs, ss = [], [], [] for line in lines: h = int(re.search(r"h: (\d+)", line).group(1)) r = int(re.search(r"r: (\d+)", line).group(1)) s = int(re.search(r"s: (\d+)", line).group(1)) hs.append(h) rs.append(r) ss.append(s)
whileTrue: p = random_prime(2**(p_bits), lbound=2**(p_bits-1)) q = random_prime(2**(q_bits), lbound=2**(q_bits-1)) if p != q and p > q and p < 2*q:#q<p<2*q break
N = p * q phi = (p**4 - 1) * (q**4 - 1)
d_bits = 1024 d_bound = 2**d_bits
whileTrue: d_small = randint(2, d_bound) d = phi - d_small if gcd(d, phi) == 1: if d_small.bit_length() == 1021: break
e = inverse_mod(d, phi)
return N, e
defencrypt(m, N, e): n = 4 r = 2 R = Integers(N) P = PolynomialRing(R, 't') t = P.gen() Q = P.quotient(t**n - r)
m_poly = Q([m, 0, 0, 0])
c_poly = m_poly ** e
return c_poly.lift()
if __name__ == "__main__": N, e = generate_vulnerable_key() m = int.from_bytes(flag, 'big') c = encrypt(m, N, e)
# N = 99697845285265879829811232968100099666254250525000506525475952592468738395250956460890611762459685140661035795964867321445992110528627232335703962897072608767840783176553829502743629914407970206513639916759403399986924602596286330464348286080258986075962271511105387188070309852907253486162504945490429185609 # e = 74900336437853271512557457581304251523854378376434438153117909482138661618901386551154807447783262736408028580620771857416463085746907317126876189023636958838207330193074215769008709076254356539808209005917645822989554532710565445155350102802675594603406077862472881027575871589046600011223990947361848608637247276816477996863812313225929441545045479384803449990623969591150979899801722841101938868710054151839628803383603849632857020369527380816687165487370957857737696187061619496102857237814447790678611448197153594917852504509869007597997670022501500067854210261136878917620198551551460145853528269270832725348151160651020188255399136483482428499340574623409209151124687319668989144444549871527949104436734300277004316939985015286758651969045396343970037328043635061226100170529991733947365830164811844853806681198818875837903563263114249814483901121700854712406832325690101810786429930813776784979083590353027191492894890551838308899148551566437532914838098811643805243593419063566975400775134981190248113477610235165151367913498299241375039256652674679958159505112725441797566678743542054295794919839551675786573113798857814005058856054462008797386322048089657472710775620574463924678367455233801970310210504653908307254926827 # c = 98460941530646528059934657633016619266170844887697553075379408285596784682803952762901219607460711533547279478564732097775812539176991062440097573591978613933775149262760936643842229597070673855940231912579258721734434631479496590694499265794576610924303262676255858387586947276246725949970866534023718638879
defdecrypt(c_poly, N, d): R = Integers(N) P = PolynomialRing(R, 't') t = P.gen() Q = P.quotient(t**4 - 2)
c = Q(c_poly) m_poly = c ** d return m_poly.lift()[0]
defattack_d(N, e, c): N = Integer(N) e = Integer(e) N4 = N ^ 4 cf = (e / N4).continued_fraction().convergents()
for conv in cf: k = conv.numerator() d_small = conv.denominator()
if d_small < 2^1020or d_small >= 2^1021: continue
if (e * d_small + 1) % k != 0: continue phi_candidate = (e * d_small + 1) // k #print("phi=",phi_candidate) d = phi_candidate - d_small return d
print("Failed to find d") returnNone, None
N = 99697845285265879829811232968100099666254250525000506525475952592468738395250956460890611762459685140661035795964867321445992110528627232335703962897072608767840783176553829502743629914407970206513639916759403399986924602596286330464348286080258986075962271511105387188070309852907253486162504945490429185609 e = 74900336437853271512557457581304251523854378376434438153117909482138661618901386551154807447783262736408028580620771857416463085746907317126876189023636958838207330193074215769008709076254356539808209005917645822989554532710565445155350102802675594603406077862472881027575871589046600011223990947361848608637247276816477996863812313225929441545045479384803449990623969591150979899801722841101938868710054151839628803383603849632857020369527380816687165487370957857737696187061619496102857237814447790678611448197153594917852504509869007597997670022501500067854210261136878917620198551551460145853528269270832725348151160651020188255399136483482428499340574623409209151124687319668989144444549871527949104436734300277004316939985015286758651969045396343970037328043635061226100170529991733947365830164811844853806681198818875837903563263114249814483901121700854712406832325690101810786429930813776784979083590353027191492894890551838308899148551566437532914838098811643805243593419063566975400775134981190248113477610235165151367913498299241375039256652674679958159505112725441797566678743542054295794919839551675786573113798857814005058856054462008797386322048089657472710775620574463924678367455233801970310210504653908307254926827 c = 98460941530646528059934657633016619266170844887697553075379408285596784682803952762901219607460711533547279478564732097775812539176991062440097573591978613933775149262760936643842229597070673855940231912579258721734434631479496590694499265794576610924303262676255858387586947276246725949970866534023718638879
d = attack_d(N, e, c) ans = long_to_bytes(int(decrypt(c,N,d))) print(ans)
1. The content of flag is: come on little brave fox. 2. Replace letter O with number 0, letter L with number 1. 3. Replace letter A with symbol at(@). 4. Make every letter E uppercase. 5. Use underline to link each word.