# Intended Solution to Crypto Problems in VN Open Competition

## CRT

### Intended Solution 1

• 构造证明
• 递归证明

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69  import hashlib def egcd(a, b): ''' Extended Euclidean Algorithm. returns x, y, gcd(a,b) such that ax + by = gcd(a,b). ''' u, u1 = 1, 0 v, v1 = 0, 1 while b: q, r = divmod(a, b) u, u1 = u1, u - q * u1 v, v1 = v1, v - q * v1 a, b = b, r return u, v, a def gcd(a,b): ''' Calculate the Greatest Common Divisor of a, b. ''' # a, b = (b, a) if a < b else (a, b) while b: a, b = b, a % b return a def LinearCongruenceSolver(a, c, m): ''' Solve x such that a * x ≡ c (mod m), returns all the possible *x*s (mod m), None if no solution. ''' g = gcd(a, m) if c % g: return None u0 = egcd(a, m)[0] return [(c * u0 + k * m) // g % m for k in range(g)] def CRT(ai, mi): ''' Chinese Remainder Theorem. solve x such that x ≡ ai[0] (mod mi[0]) .... ''' assert(isinstance(mi, list) and isinstance(ai, list)) a_s, m = set([ai[0]]), mi[0] for a1, m1 in zip(ai[1:], mi[1:]): # print(f"m1: {m1}") new_as = set() for a in a_s: ks = LinearCongruenceSolver(m, a1 - a, m1) if not ks: continue for k in ks: new_as.add(a + k*m) a_s = new_as m = m * m1 return a_s, m ms = [284461942441737992421992210219060544764, 218436209063777179204189567410606431578, 288673438109933649911276214358963643204, 239232622368515797881077917549177081575, 206264514127207567149705234795160750411, 338915547568169045185589241329271490503, 246545359356590592172327146579550739141, 219686182542160835171493232381209438048] cs = [273520784183505348818648859874365852523, 128223029008039086716133583343107528289, 5111091025406771271167772696866083419, 33462335595116820423587878784664448439, 145377705960376589843356778052388633917, 128158421725856807614557926615949143594, 230664008267846531848877293149791626711, 94549019966480959688919233343793910003] sol = CRT(cs, ms) for x in sol[0]: if "4b93deeb" in hashlib.sha256(str(x).encode()).hexdigest(): print(x) flag = "flag{" + hashlib.sha256(str(x).encode()).hexdigest() + "}" print(flag) break 

### Intended Solution 2

$x \pmod{n_{lcm}}$肯定就只有1解，假如说是$x_{lcm}$。

wtcl。

## Fast

$$g^{p-1} \equiv 1 \pmod{p}$$ 那么， $$g_1 = g^{r_1(p-1)} \equiv 1 \pmod{p}$$ 因此， $$g^{r_1(p-1)} - 1 = k\cdot p$$ 只要 $$\gcd(g_1 - 1, N)$$ 即可分解出$p$，再用$N$整除下$p$即可得到$q$。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  from Crypto.Util.number import * N = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283 g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208 c1, c2 = (3976514029543484086411168675941075541422870678409709261442618832911574665848843566949154289825219682094719766762966082440586568781997199077781276145091509192208487682443007457513002005089654365915817414921574344557570444253187757317116858499013550050579856269915915792827620535138057468531410166908365364129001407147467636145589396570815405571923148902993581000542566387654639930651683044853608873583911638108204074537952317056718986683846742909366072461130053275195290631718363272923316002049685111871888148244026652658482359335651889139243735138819453744763293112267738369048641158946411500606588429007794613880534, 18524535479582837341745231233387403662294605513261199630593257391163433751052467785080620993007681605662927226603747560698627838567782891522546977611597418150309028806158429831471152782211111046118637630899456903846057977815397285171313888516791822545633820066408276065732715348834255021260666966934592884548856831383262013360819013814149529393178712576141627031723067564594282618223686778534522328204603249125537258294561872667849498796757523663858312311082034700705599706428944071848443463999351872482644584735305157234751806369172212650596041534643187402820399145288902719434158798638116870325144146218568810928344) p = GCD(N, g1 - 1) q = N // p def decrypt(c1, c2): xp = c1 % p xq = c2 % q # Chinese Remainder Theorem m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N return m m = decrypt(c1, c2) print(long_to_bytes(m)) # flag{1CE9514E-12AF-49BE-B002-6A3D7E6078FA} 

## Backtrace

• EIS 2019

• Byte CTF 2019

• GXYCTF 2019

Cryptopals 上也有一个叫你去日MT19937种子的任务。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70  def unBitShiftRightXor(value, shift): i = 0 while i * shift < 32: part_mask = ((0xffffffff << (32 - shift)) & 0xffffffff) >> (i * shift) part = value & part_mask value ^= part >> shift i += 1 return value def unBitShiftLeftXor(value, shift, mask): i = 0 while i * shift < 32: part_mask = ((0xffffffff >> (32 - shift)) & 0xffffffff) << (i * shift) part = value & part_mask value ^= (part << shift) & mask i += 1 return value def getState(number): number = unBitShiftRightXor(number, 18) number = unBitShiftLeftXor(number, 15, 0xefc60000) number = unBitShiftLeftXor(number, 7, 0x9d2c5680) number = unBitShiftRightXor(number, 11) return number def backtrace(numbers): """ Returns the initial state of the MT PRNG based on list of the output numbers """ # assert(len(numbers) == 624) state = [] for number in numbers: state.append(getState(number)) return state def getOldStates(states): for i in range(3, -1, -1): tmp = states[i + 624] ^ states[i + 397] if tmp & 0x80000000 == 0x80000000: tmp ^= 0x9908b0df res = (tmp & 0x40000000) << 1 tmp = states[i - 1 + 624] ^ states[i + 396] if tmp & 0x80000000 == 0x80000000: tmp ^= 0x9908b0df res |= 1 res |= (tmp & 0x3fffffff) << 1 # assert(res == states[i]) states[i] = res def next(states, i): y = (states[i] & 0x80000000) + (states[(i+1) % 624] & 0x7FFFFFFF) n = 0x9908b0df if y & 1 else 0 res = states[(i+397) % 624] ^ (y >> 1) ^ n return res with open('output.txt', 'r') as f: data = f.read() outputs = [int(output) for output in data.split('\n')[:-1]] states = [0]*4 + backtrace(outputs) getOldStates(states) import random random.setstate(tuple([3, tuple(states[:624] + [0]), None])) flag = "flag{" + ''.join(str(random.getrandbits(32)) for _ in range(4)) + "}" print(flag) # flag{1886737465387686573924175753923879771350}