import secrets
from Crypto.Cipher import AES
from hashlib import sha256
import math
FLAG = b'flag{**************}'
def compute_polynomial_value(coefficients, x_point):
    result = 0
    for power, coeff in enumerate(coefficients):
        result += coeff * (x_point ** power)
    return result

def check_pairwise_coprime(numbers):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if math.gcd(numbers[i], numbers[j]) != 1:
                return False
    return True

POLY_DEGREE = 128
NUM_SHARES = 8
polynomial_coeffs = [secrets.randbits(64) for _ in range(POLY_DEGREE + 1)]
selected_x_values = []
while len(selected_x_values) < NUM_SHARES:
    candidate_x = secrets.randbits(16)
    if all(math.gcd(candidate_x, existing_x) == 1 for existing_x in selected_x_values):
        selected_x_values.append(candidate_x)
secret_shares = []
for x_val in selected_x_values:
    y_val = compute_polynomial_value(polynomial_coeffs, x_val)
    secret_shares.append((x_val, y_val))
print("shares=", secret_shares)

secret_value = compute_polynomial_value(polynomial_coeffs, 0xd8cb)
encryption_key = sha256(str(secret_value).encode()).digest()[:16]

cipher_instance = AES.new(encryption_key, AES.MODE_CTR)
encrypted_flag = cipher_instance.encrypt(FLAG)
nonce_value = cipher_instance.nonce

print("enc=", encrypted_flag)
print("nonce=", nonce_value)
'''
shares= [(44271, 71577044593197649725921885083512733548537247527042086801113062684208077003484534987345242898487169996958639498999332201603538542171270699930576873889033112186090007464777855154233785997438604903333918156921179018701102983858577689705009075373111822291389043437229345253533179176084639102858950294407917752759784523583063534331272460981842946323012105363486308093451865130210720506659006104690587154229593675806958494637159947006549732932778379514934743491441220530198861508160262592420912014717517360485680883764257654488937903922297709087563836271438661365495980870970679386570599001144669576449115121077818738962), (17879, 282772733532233178051905445316131875340561195163355252708902138614705241996485433375408645815641483276184250443409292838928454004400355965251974121072744051295760141963660603194415287787154779616238234662583012321008368647425039988847018305916721715779728986366936109942744727445427270352477597088355164484544389611993970200050303835020239577466000041687379136690736165061539732142546451529526963800610061109771821797512526039070672594021731484685340600240304420792840653075870588317417647509052790027003086439392977108355415667260421506521077744379558265807001530), (5011, 5518896479553595337396667890548726721080603319546898469377956761976285763633819031165542549914551528987394011253542257473379525244646089163747994936847962016978278269024204108976543795871887997234522385036933764819670926576996067952929838346363111183507719227950984371159955726390634510472285657628167075740845824930033877619770832940055765550062431531737035742149841073181017747942209960365623718121262564317781114575407868555367016056053124263849201136295787799664779820127535379214561477222), (33875, 94634897457153282007803472963298997579582943957763615814269580546363423998925536719446063320862552734719858297042580274054680125043500654240810521712675218408964301752218904487717161400337648621295097403123745700613358678878476266067023402721249823812553465130447790195323159932746971755053359311290677167443345734311836672503660872057953640436857967065794734717861769578655874432154058694861993306090576113201498759108416569286707223998320516548055585762562062351639302136979746530754020310790258551149020877187440192366943524884556614600790830015338662669524955064918208049151746698024085780909350), (9007, 2176580836992530009075605445930122712115303778621233934967929341498170964020730955431820850039241414213019455392364081839393306573006611865448925331690038360919642025086834769355968368852029509869372627660617953557563394462239064271922596850530746971600774386332191801876542628176120980512874208695772941435241539219024219021979470071614755509154606447428140277558315876913717060391956745242138672165458212831447707078742963270034869907146237434090209790991286431275231442267910191867252533430294507133218804986695926400796498), (49633, 162228156169800847575117611756008985679366841295607093483018905996670628555164498458146023326298338225879502373094432731726415498321316400415382232075717380411485940027234519716419131846238558848031437303598126682637209727963784606305375356267720354574179045527855325486739680858673016912723938049117233632715475333980408214667313890894616872363625413634489797072472604655130467565010887187870598175891595716459980061758524933737205124934260164862008850387506486767663093977568221026883883382609029325023171489695199429737272595338666900911136674219445742665603981965834820439434422278808325476730752597529272737120059568), (52274, 123615401436712420631793264435145240714121321883914808208947076444352074684561675012130314436570967979522990302245594772320974862282275297736587043786920436346862808429825730376043568553763419036553821609985282366886163241160088685303467761328433967090517540948692286505521187512049031962672086529658722599236235733036557695613964141362945855489814856819579147429697978920979583611595064411577355742973265614697592941938428942801694000855761581590761834157141463799952819528547426926260160018701634048176901212913618944463816397603479015547174669951038844289813533241392866229566314992306289734373665200384669955245082349615), (27803, 989085721199628115877899358954734763529815424054134145560236908987752342354351771760449351744322858896343160491546759146586537938685148362838678054873185387261167491073684091404724523312368288327136307395155279441681926024054869370868153603992212181341044424141093151616941036328839892802663593233665873304346236828921517604459274007831615829068115038673903833042764888798146666198062271720797348400314902706817651708526362870291571362973853629561721952174796672497915237012581221853076455543197425913531343728087940011778996635042343792619935443343641836381243436788418745034876092796398)]
enc= b'\x95*\x9exSe?\xbc\x9c\xbb\xfd\xf7\xd4;V\xc5\xab\x96T\xf9\xad\x02Q37lL\xb2\xb7\x99\x82\x85!\x19\xa0A\x0b\xeb3\xe9'
nonce= b' n8\xc7\xa2\xeec\x9e'
'''