# WCO3

from Crypto.Util.number import *
import os

BITS = 256
d = 30

def poly(x):
    return sum([coeffs[i] * x ** i for i in range(d + 1)])

FLAG = b'W1{???????????????????????????}'
FLAG = bytes_to_long(FLAG)

coeffs = [FLAG] + [bytes_to_long(os.urandom(BITS // 8)) for _ in range(d)]

shares = []
x = []
for i in range(19):
    p = getPrime(15)
    x.append(p)
    shares.append(poly(p))

print(x)
print(shares)

[26393, 19963, 23143, 17597, 20431, 21491, 25609, 22303, 20731, 20089, 24917, 24077, 23311, 28723, 29633, 30091, 17387, 27689, 17117]
[470052453276710913590884000637065532192951152129287277929048863994297555640633167497875776608770892368004814480410574859920782303668568579783882908584863353195555131355868008726368228777854589570524255577036023, 108208063845813827193827950448988875225663735831813712495701058348853068956640236868019475056096617023355171452385887588940389539604262629535367627773328926956319364826345132557465472503721530180063451739613, 9121663569090632747362575526496297012661693057297025180600743186337701808759793697153787573433445312554810845245537236358157269546025496916887686954021584631114850862498812366965828305346302548685890290678273, 2458359857277691714186825297324363730273505071697371352591545239139008765666077472930295047178021717074162026288802477095758472995407588128623770223056005530544316421892026538158701862276689667982220947827, 216857259365133168016784238113757253980050999849708198594118756511583804613047272770375822040713416680599517470663928784589318554775319850977838179943702716005539948942590084827427483609026941750215412224825, 988971128975293632010016494986007367736236066796838211450690015342838643174737367592193886825753342594136982402701313087766589438346379813178980135221476245605340527484731146876202981682159634736580923599045, 190222711962329907598692197553972694932488704239080312084360672570158788172202643613021979965121064163583719784866944905388834964826073596206024198494731372617776127694678042701151921038523012218571981053714567, 3008729648679134648846837742942330501073802525468181425292395926404136589229537930962362837994928145949766042155806177023299209974773420978572972108648128879399314097133075210327414269773296345073020559985193, 335809280104727388227678134005184844577783024023525641703493438586861740012634491387089974183510476228858556568021339603126259128967429920022446997187594526823341326614797169227620175637223283370802378632925, 130687767482256032667713636298705514932248453742707841814844689594948799772698936431838156070579177196646902120616033571915909687106178775938523484961994462830428540224309455326542453304543579610574413370007, 83628921063354983501989009871390429484123713118131080689724852697440758109331791584456463982748979014631056503431507230272923791883394468444354492640539969911680061605449502095121668079789835838572294476310427, 29892023904040389570213401198288720270840340136466988868146154304483425398742606502584838336484084996202031690621204422566555026174102390241587368642745174040000088450725394657084206779125838967236700403877027, 11332128073810380552973517384464067881705242543000877044422824347736186423949856865569095174481729179186816898010922752003903173640811382067755305052269304030144780861822002025991725535267611915813619919220985, 5948083767075113941087485337635051912763358374965098206186249064513593833137895266542747505178753465020833306845135040168592345754947863195682628178319355907882446024051823227268942836397101842504010258458937733, 15161829183195694623745962413476361888595878396948631349466998162481024196749536335789258479134675449843445320927200933023533371062496096666790377043777294274501956021570430691549157849165164222700088408069445903, 24020470629843510720865885495461208880763008294039805389676231999869765359992810099945135798367263187547799321699104418847438524070706312709508204984992594708534617159750251535539194454277306935779294078850703245, 1714850093041510232731006420859654325301207896329106072486575161881560263976539964777887654128283166700333080644318596159013602301116469586793847916566467746425170746728806924140533150903297027795923708077, 1980165381139141433672537408645283918135078340271034392002457875398631280016622374721048052261544792318993927018283167542741522430596588484205763971917361534206767123521302405889367521211092798344668569631528807, 1072299723298481483908351317332467976965558084472199570048606753255208333466679676783002994953050067769845110631258458301209719564414908147697664070561612468121856454884604377857725040223534031654988345427]

## Solution

Ta thấy hàm poly sẽ cho ta được kết quả như sau:

$$poly(x) = \mathrm{FLAG} + a_1 x + a_2 x^2 + \dots + a_{30} x^{30}$$

Ta có thể rút ra được nhận xét như sau:

$$\begin{cases}
poly(p_1) = \mathrm{FLAG} \mod{p_1} \\
poly(p_2) = \mathrm{FLAG} \mod{p_1} \\
\dots \\
poly(p_k) = \mathrm{FLAG} \mod{p_k} \\
\end{cases}$$

Từ đây ta có thể sử dụng Chinese Remainder Theorem (CRT) để tìm lại FLAG:

from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt

x = [26393, 19963, 23143, 17597, 20431, 21491, 25609, 22303, 20731, 20089, 24917, 24077, 23311, 28723, 29633, 30091, 17387, 27689, 17117]
shares = [470052453276710913590884000637065532192951152129287277929048863994297555640633167497875776608770892368004814480410574859920782303668568579783882908584863353195555131355868008726368228777854589570524255577036023, 108208063845813827193827950448988875225663735831813712495701058348853068956640236868019475056096617023355171452385887588940389539604262629535367627773328926956319364826345132557465472503721530180063451739613, 9121663569090632747362575526496297012661693057297025180600743186337701808759793697153787573433445312554810845245537236358157269546025496916887686954021584631114850862498812366965828305346302548685890290678273, 2458359857277691714186825297324363730273505071697371352591545239139008765666077472930295047178021717074162026288802477095758472995407588128623770223056005530544316421892026538158701862276689667982220947827, 216857259365133168016784238113757253980050999849708198594118756511583804613047272770375822040713416680599517470663928784589318554775319850977838179943702716005539948942590084827427483609026941750215412224825, 988971128975293632010016494986007367736236066796838211450690015342838643174737367592193886825753342594136982402701313087766589438346379813178980135221476245605340527484731146876202981682159634736580923599045, 190222711962329907598692197553972694932488704239080312084360672570158788172202643613021979965121064163583719784866944905388834964826073596206024198494731372617776127694678042701151921038523012218571981053714567, 3008729648679134648846837742942330501073802525468181425292395926404136589229537930962362837994928145949766042155806177023299209974773420978572972108648128879399314097133075210327414269773296345073020559985193, 335809280104727388227678134005184844577783024023525641703493438586861740012634491387089974183510476228858556568021339603126259128967429920022446997187594526823341326614797169227620175637223283370802378632925, 130687767482256032667713636298705514932248453742707841814844689594948799772698936431838156070579177196646902120616033571915909687106178775938523484961994462830428540224309455326542453304543579610574413370007, 83628921063354983501989009871390429484123713118131080689724852697440758109331791584456463982748979014631056503431507230272923791883394468444354492640539969911680061605449502095121668079789835838572294476310427, 29892023904040389570213401198288720270840340136466988868146154304483425398742606502584838336484084996202031690621204422566555026174102390241587368642745174040000088450725394657084206779125838967236700403877027, 11332128073810380552973517384464067881705242543000877044422824347736186423949856865569095174481729179186816898010922752003903173640811382067755305052269304030144780861822002025991725535267611915813619919220985, 5948083767075113941087485337635051912763358374965098206186249064513593833137895266542747505178753465020833306845135040168592345754947863195682628178319355907882446024051823227268942836397101842504010258458937733, 15161829183195694623745962413476361888595878396948631349466998162481024196749536335789258479134675449843445320927200933023533371062496096666790377043777294274501956021570430691549157849165164222700088408069445903, 24020470629843510720865885495461208880763008294039805389676231999869765359992810099945135798367263187547799321699104418847438524070706312709508204984992594708534617159750251535539194454277306935779294078850703245, 1714850093041510232731006420859654325301207896329106072486575161881560263976539964777887654128283166700333080644318596159013602301116469586793847916566467746425170746728806924140533150903297027795923708077, 1980165381139141433672537408645283918135078340271034392002457875398631280016622374721048052261544792318993927018283167542741522430596588484205763971917361534206767123521302405889367521211092798344668569631528807, 1072299723298481483908351317332467976965558084472199570048606753255208333466679676783002994953050067769845110631258458301209719564414908147697664070561612468121856454884604377857725040223534031654988345427]

print(long_to_bytes(crt(x, shares)[0]))

W1{chinese_remainder_theorem}