# Writeup for Share in CNSS Summer Camp 2019

## TL;DR

Solve a modified RSA problem, which used the product of 3 primes chosen from 6 randomly-generated primes, by recovering every prime (actually only 3 are needed if we want to calculate the m, e.g. flag) through writing congruences as equations.

## File

Share.py

  1 2 3 4 5 6 7 8 9 10 11 12 13 14  from Crypto.Util.number import getPrime from FLAG import flag flag = int(flag.hex(), 16) num = 6 e = 0x10001 p = [getPrime(1024) for _ in range(num)] f = open('cipherlist.txt', 'w') for i in range(num): for j in range(i + 1, num): for k in range(j + 1, num): n = p[i] * p[j] * p[k] f.write(hex(pow(flag, e, n)) + '\n') 

cipherlist.txt

0x8f83bbd164fea268a30bcb4715045d83aa8ff882795f19149a19edeeb5543c845b09669c1448047722dfba93160e1b1b9513439808d2dcc898980b5fcaca8e103033b64faf3670448ad03e8c4929c5b381f2b5f8068c97612d04d819ad2bdbeb7fe1aa39cf569a19c3e6e400a8f7d239187df89f1325d8b38e487a183cca7a95295b5bf9f59ade348c338da8430ec1bcf45870898e458d7a07de5a55748f2eb94b357f878c6ef14198839615ec71a7bfdd6de265144a016f26d816d7d5838f750a26416559095acf7def0407fb01ee0198dad1088ad0eccad9342f21a4e02c5bbe2b53813db060bc7d6c134835af8cae696ceab3483820704a28548ba109127d42b197f97a242a84eca20ff2e495eabd52be86d6fcf1cefbdcdebc2b533e9dc7b2f10eef53dbef2237edfc2a47de4e2e1fee555440ae39136cfdb24a643772e536901091607abf030aa83894fb95c8076885e41282098ac82c5c7666bbc387ab6b64c87c10dad611ce3c4d8c884e52254b031fc4fd4931d0e9540a5cab1aa9f4
0x38cf70f149fbe50b1a8892ebed5834696bd79781e3238a8331481c870fb4536e25f6bf4c7571b478a01389c8bd8c77614958c1a2953a39960174b4b60ded7de06d179a4a93e1ab48438b4a4c8273e4fc716119d4f4e9e5687a5d6001a8de1486b6db5a5344172504b63180b92ef0a487cfb57487b9e7201c5c39c17a23ccd8f0168a184ec31d184b24a5de4a4f13050b4312c251e99dcd57982f4eba5d6095bd1fd7d7cc62bccb6935212153623673e227b06e2c9b083cb2351a5cbf886d7d70c5823705a5027b03436c228d9bebd85f31465bc82e7ea85eeafaf45b847a57d9951f4d8fab0f8e3009d58778bca9b747feeba09f858f988c27e6dde7c643c01b2ec79c94cddcf94b73d6523a45f1170c817f30f1c3ba8bcdd9abdb3e4d68be20450dbfc9d3b2e271a77371c22f8a02dc30f530f31a755d496e5e9f7a64e5418fb8a803d66b15120679271596b74bdb176123cdbe1c6b0eee9bc072a04cced59b6e8a920430d9a91ac0bdee6b2b00dd4965c7b3941c728f4e03acff0067bdb476
0x4fa377d624afca3fc0003df5d117d79e9f951d2f47d3b90c7e254fd120f7cae34915b251f629b182bfee2977213e68a8c9f6be698d15ab8fa82c7e26b5d7890d2eeb4cfde4eab5e85ef6e9f6a8b9bcda7036f1a8af6846a620c64cc1555ff1824579bbfd4e51f0aebb825e652195a10f792acf69c347fae73a53cafd986d2262b8e7e1acd6b42a1f995558e44c2a025b96a0f61f594e44ebed1918d9e788370c69b7c73eff8ddb4f4c386258093dc8263567fa69702f745d9ae33bee7b76976a7a8b5548be810b50d08f24b5ce251cd7c9af42a8cf46ebb48106ba8dea9e0a12377ac075613b70ea321a677ae5a44548cf5485ee85290445c748bef9e1e339f9a4457225028d4ea08dca676eda38cd0525b1dbfb7a41bd38eee6cb9be654e867d75a9b7150c3c0b31a3c5355db45a7daf9eff8849b1acf8c2697452301e65673c719972a9d9e240050508bee598f4829d8af04b57de2199ee6fedf91f7771a746321edd09b044c636b7de0bdb15d74346e1f32ec3626173e4afbdfbf84055393
0x400e86bd60fc7d01cb8331e87b4c7bd6b303731c9b4e8d245d34e564769810a251a341a5aa70e7370f0f641b0c62f16f0d8fef61dface09e297916dc65a60608f4ca02ac4be88dc6331f6ed2a091707d2ebc31c3cb0e734d7b3264c4aa389f0ef03a95035b934be0c10388784641dceee4fab0f5e6cc21435e7674cfb3a85ecb90b8e1e214280312be8eced167dffa3f3ce3c6a2bd918622c6d5f4cd622673da5989bdb1db2d21af0f45ca6be3c580592da7a92619aee5efdde462a1a8a2417b5abeedff1c166ddeae0b570cba48bf44b3e7299ac4a358dc30d9dc69dc2ab7077271392ef643f0fb2c0015afa33f06eb09e12c719c26977a49d71794e885fae866d15f1e96cf12b8b9dc9d5afa1f19b896babb35fc09f765c0bb4d6109bf49c6a72a85ba6239c4dccde553198c4a3a7ba004092975a707a872416f23485af19f50bc591b4593190a620d1de9dd983190a1fc7b4f3cf558057d4f342fdca9d765977f116620f140f72203d3b797d0d09f30fef3ba8bb0e1fe528338f57c1ab408


## Recon

$$\begin{split} m^e &\equiv c_0 \quad &(mod\ p_0p_1p_2)\ m^e &\equiv c_1 \quad &(mod\ p_0p_1p_3)\ &…\ m^e &\equiv c_{19} \quad &(mod\ p_3p_4p_5)\ \end{split}$$

  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  count = 0 for i in range(6): for j in range(i + 1, 6): for k in range(j + 1, 6): print(f"{count:2d}: {i:2d} {j:2d} {k:2d}") count += 1 # # output: # 0: 0 1 2 # 1: 0 1 3 # 2: 0 1 4 # 3: 0 1 5 # 4: 0 2 3 # 5: 0 2 4 # 6: 0 2 5 # 7: 0 3 4 # 8: 0 3 5 # 9: 0 4 5 # 10: 1 2 3 # 11: 1 2 4 # 12: 1 2 5 # 13: 1 3 4 # 14: 1 3 5 # 15: 1 4 5 # 16: 2 3 4 # 17: 2 3 5 # 18: 2 4 5 # 19: 3 4 5 

## Exploit

$$\begin{split} m^e &= c_0 &+\ k_0\cdot p_0p_1p_2\ m^e &= c_1 &+\ k_1\cdot p_0p_1p_3\ &…\ m^e &= c_{19} &+\ k_{19}\cdot p_3p_4p_5 \end{split}$$

$$\begin{split} m^e - m^e &= c_0 + k_0\cdot p_0p_1p_2 - (c_1 + k_1\cdot p_0p_1p_3)\ c_1 - c_0 &= k_0\cdot p_0p_1p_2 - k_1\cdot p_0p_1p_3\ c_1 - c_0 &= p_0p_1(k_0p_2 - k_1p_3) \end{split}$$

$$c_3 - c_2 = p_0p_1(k_2p_4 - k_3p_5)$$

## Script

  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  # 0: 0 1 2 # 1: 0 1 3 # 2: 0 1 4 # 3: 0 1 5 # 4: 0 2 3 # 5: 0 2 4 # 6: 0 2 5 # 7: 0 3 4 # 8: 0 3 5 # 9: 0 4 5 # 10: 1 2 3 # 11: 1 2 4 # 12: 1 2 5 # 13: 1 3 4 # 14: 1 3 5 # 15: 1 4 5 # 16: 2 3 4 # 17: 2 3 5 # 18: 2 4 5 # 19: 3 4 5 from Crypto.Util.number import * with open('cipherlist.txt') as f: ciphers = f.read() c = [] for cipher in ciphers.split('\n')[:-1]: c.append(int(cipher, 16)) p0 = GCD(c[3] - c[4], c[6] - c[7]) assert(isPrime(p0)) p1 = GCD(c[0] - c[15], c[2] - c[12]) assert(isPrime(p1)) p2 = GCD(c[0] - c[17], c[4] - c[11]) // 4 # factordb.com assert(isPrime(p2)) p3 = GCD(c[1] - c[16], c[4] - c[19]) assert(isPrime(p3)) p4 = GCD(c[2] - c[16], c[5] - c[19]) assert(isPrime(p4)) p5 = GCD(c[3] - c[17], c[6] - c[14]) assert(isPrime(p5)) N_012 = p0 * p1 * p2 phi_012 = (p0 - 1) * (p1 - 1) * (p2 - 1) e = 0x10001 assert(GCD(e, phi_012) == 1) d = inverse(e, phi_012) m = pow(c[0], d, N_012) flag = bytes.fromhex(hex(m)[2:]) print(flag) # b'cnss{Shar1ng_Prime_1z_Dan8erou5}' # (p0, p1, p2, p3, p4, p5) = # (177304879050333551776343860783076913000427102527188500840715464140010698844842835299190701847891781739300987077568541585369514970314051812200740938014996001750073210393068360124254486224833896088415593840580890258145758717471076717409517143322203320102372547426869957602303311721945479530782305397175250602643, # 119645681381628146011902256693940867125453580799419325372785077552123523103473163699736651194110579933863386879119089895255069215489258925503404468239893965701321221532139408923594329309336302479215591228210351341183070466867074661162860746463288087453157590440658022835232240758264061900163591944740912499513, # 179373542506561829194974889818444042734137695401667380750515018416052794964521133723808905996016609496683279256002175275511413703788693050396215119343308972004584336387459140250554225666319369063669244445902895494966205441352250626558617493456902583645316124764866501940305192122019244761649967689001185902717, # 149290165591379682575125833004788457369492113232039504608217060477695761862559298411435879740793219106685159527303061598218721588225103172245461381649753544713326382994225730820238540297730801032547884791785723906376045268252778724253643174436033919863486394025860523829034378404781397173309380167911723074659, # 112578603517527755751185035881323548618010735635726409237980550631674273604861886769505142567396678750653637599850432017841395087638059940264169744617948461842957920839103366365783819355538023530548578540764441439726473115616051358327778556162649360618615219156658953296355989175350497667452923301838076216447, # 165662264644197770353023368706316773895872263104901495492709210410139622545700598428978201602479122247134397970490477811805425600864339810593429968361601617955051875019532938861969217445581419405017415570207316631518058784129821751924467921009903863228465259371932738347366806206771747428532807462024790065003) 

## Flag

cnss{Shar1ng_Prime_1z_Dan8erou5}

## Summary

In addition to being a theorem and an algorithm, we would suggest to the reader that the Chinese remainder theorem is also a state of mind.