Created
May 8, 2023 05:08
-
-
Save maple3142/4fa423ead1da50af5500dc091ac00cd0 to your computer and use it in GitHub Desktop.
Cryptoverse CTF 2023 - picochip2
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from sage.all import crt, lcm, reduce | |
| from Crypto.Util.number import * | |
| import csv | |
| # fmt: off | |
| pico_r = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547] | |
| # fmt: on | |
| def solve_eqs(eqs): | |
| if len(eqs) < 2: | |
| return 0, 0 | |
| ms = [-k for k, _ in eqs] | |
| ps = [p for _, p in eqs] | |
| L = reduce(lcm, ps) | |
| res = crt(ms, ps) | |
| return L, res | |
| def solve(st, N, t): | |
| eqs = [] | |
| k = 0 | |
| idx = 0 | |
| while idx < len(st): | |
| for i, s in enumerate(st[idx : idx + N]): | |
| idx += 1 | |
| if s == 0: | |
| eqs.append((k, pico_r[i])) | |
| # assert (vp + k) % pico.r[i] == 0 | |
| k += 2 | |
| break | |
| else: | |
| L, cur_vv = solve_eqs(eqs) | |
| if L: | |
| print(f"{k = }") | |
| print(f"{L = }", L.bit_length()) | |
| print(f"{cur_vv = }") | |
| print(len(st), idx) | |
| print() | |
| for s in st[idx : idx + t]: | |
| idx += 1 | |
| if s == 0: | |
| k += 2 | |
| break | |
| # if isPrime(cur_vv + k): | |
| # print("FOUND1", cur_vv + k) | |
| # return cur_vv + k, st[idx:] | |
| with open("power_states.csv") as f: | |
| reader = csv.reader(f, delimiter=",") | |
| next(reader) | |
| st = [int(y) for x, y in reader] | |
| try: | |
| print("get p mod") | |
| solve(st[100:], 100, 10) | |
| except: | |
| pass | |
| try: | |
| print("get q mod") | |
| solve(st[5540:], 100, 10) | |
| except: | |
| pass |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from Crypto.Util.number import * | |
| from tqdm import tqdm | |
| import random | |
| from lbc_toolkit import small_roots | |
| N = 130242563655857624894400945577596726349342500250110028576899185041437457270571385988775800707021082684571500938230335838572343683077030043170929464612371476956037213483889197399888953059037490955052374761877827022364642118001281744384383425614733953384975007872647643383223846078326219496054222658506664194809 | |
| e = 65537 | |
| ct = 105907761990378066226415220707780642346253492128869807523331608442629667283774856771483475721417798409391047173653877895381454531056957845466445503946203117753779878926970882151071816334395199925843076844258607834225532144320120475312185170491128333893223806872578843356036259570319998389877610989110147615590 | |
| # get this with `get_mod.py` | |
| Lq = 110771048542294008655567252323407263021635384906342218910220956868946703113415 | |
| qmLq = 46507139167438726023448101260439823591848326066022505845258905249241953906242 | |
| Lp = 1487051625896473568251626796657514782188841738792655155038905673165 | |
| pmLp = 72663085590708489175312897469020819802613550944383864132672454215 | |
| L = gcd(Lq, Lp) | |
| qL = qmLq % L | |
| pL = pmLp % L | |
| # qmLq, pmLq is not actually q (mod Lq) and p (mod Lp) | |
| # instead, it is the initial output of `v0 = random.randint(2**(self.k-1), 2**self.k); v = v0 + 1 - v0 % 2` | |
| # I am not sure the `k` value found in `get_mod.py` is correct | |
| # so just test it with coppermsith | |
| x, y = Zmod(L)["x,y"].gens() | |
| f = (qL + x) * (pL + y) - N | |
| x, y = small_roots(f, (2**10, 2**10))[0] | |
| qmLq += x | |
| pmLp += y | |
| # unfortunately, neither Lp and Lq are big enough to apply coppersmith here | |
| # but we can use the fact that n=pq to get more bits of q (mod Lq/gcd(Lq,Lp)) and p (mod Lp/gcd(Lq,Lp)) | |
| L2 = Lp // L | |
| qmL2 = N / pmLp % L2 | |
| L3 = Lq // L | |
| pmL3 = N / qmLq % L3 | |
| LL = Lq * L2 | |
| qmLL = crt([qmLq, qmL2], [Lq, L2]) | |
| pmLL = crt([pmLp, pmL3], [Lp, L3]) | |
| assert qmLL * pmLL % LL == N % LL | |
| # let's coppersmith | |
| x = Zmod(N)["x"].gen() | |
| for _ in range(100): | |
| ps = [p for p, _ in factor(LL)] | |
| # we are not sure it is always correct | |
| # try remove some primes and apply coppersmith until it works | |
| pps = set(ps) - set(random.sample(ps, 8)) | |
| Lsub = prod(pps) | |
| print("trying", Lsub, Lsub.bit_length()) | |
| qmLsub = qmLL % Lsub | |
| f = (qmLsub + x * Lsub).monic() | |
| rs = f.small_roots(X=2 ** (512 - Lsub.bit_length()), beta=0.49, epsilon=0.1) | |
| if rs: | |
| sol = rs[0] | |
| print("yay", sol) | |
| break | |
| q = ZZ(qmLsub + sol * Lsub) | |
| p = ZZ(N // q) | |
| assert p * q == N | |
| phi = (p - 1) * (q - 1) | |
| d = inverse_mod(e, phi) | |
| m = pow(ct, d, N) | |
| print(long_to_bytes(m)) | |
| # cvctf{jU57_4_s1MpL3_s1d3_ch4nn3L_ch1p@_@} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment