by mr96
For this one we’re given the following values
common_part = 581090821296317933693586537610831214024106768710093022974488362042825786477677095350272592362056161640241973209079990997920846540763147917348498786721
Secret = [(2433540313092365358498910942615091739287190301494338351018258678488932416718555674164347001675072449071289374832316621249466217351144971694400277452989036L, 10379490429112932725800525476020867148375792941644900618767976870525310215947891346374096900780789001714921833829498506828021591411760530235331835919286003L), (2262603161348726135418932740967190432585242845626488888779312128341566485277282354452876012214562566631359352738148304731959582728554256835607203231425197L, 7342469201597956175509034967124623233618829870845574781688439222933081691218704225899537135983331659871971737540220700398611027025368347105138783354976173L), (3492754970417800154420205999588295393340353056895768081040806914643671022355393817705909555093471544656712602739817729737860291247150771530739437276334536L, 3783463518648947796238532310991965471957180170807360550575038277767085146044062769485330460239260211302790479547388526187955893618468256872898858016737383L), (5339545252534280472242742310638383594901538452739451841210131676544815273328248324884529621635855444020235346537290530627519492230612306746719716960021148L, 7810530476920181982000554210844947350305708533931170749727106706830151408164755959553997101332430424617061522255248349466630265828242145686241337221093051L), (4825328812655303751234536925550835315371457930382464357564525734421020895932184792716783826884367873275483773856284827325887278426609459173620999562574774L, 5437855093996708328328099324048825805595325601466898274296243311675283452628347416193179036392625149835415876095557371227403616979377009793937256895553363L), (8624661229926683655254411870252240544902913193200615805969495945838977950606124497283973387891681974373628959722612953288481186484505784288423905884205750L, 11205985361034323967745602584439532920107173548419567454912391103067391741404908912086184510756358122763592487894419548439764378967443404278258826122535161L), (1121564545146022200101752054366322248276590219181932582571326549017234461215232323421497536894461382635314586082222852725480671211524986019821955899877615L, 7905066786107219416113543069692484270903258888539133253209314151913257354823237228357054476824521464801864635879842225506031204018136356134463361913303509L), (7947293090213596625050053248142396727423010297760649653046134262588142903664933711001583373235991690788909013347415429367440973173680006670427795429577538L, 12024880774676453668188636202118509605243465262025093321460328384766139136489442552825541437836422732170964621525371780187434816456086229802202952836220723L), (7926196731644739710108173449852692325087797722838788154868427366798722851882146096700759566617784402815052598878505576691995839630748784308155360560526195L, 8372123343604603466558819446021026865538454852031250080875021052140962881782152385383291129307903273725608779033447780512261550418095116661182748024556639L), (3904325341602542172710907632843884668890887461781548713821150871143171273341552762737833501209411305097414078525125341026103741903007835578976438792678297L, 8210422318054241965968078354433314698771586517678743336751641130673800537820126456447197115452847623544483171107559095812152332418782762640635939670146363L)]
We’ve a common part and a lot of secrets: this is obviously a secret sharing scheme. But which one? Looking closely we can see that every part is a couple of values and so, using the name of the challenge as an help, we figure out that this is the Asmuth-Bloom’s threshold secret sharing scheme. So, supposing that all the assumptions of this scheme are satisfied in the secrets generation, we have some couples \((s_i,m_i)\) and what we have to do is to solve the system of equations \(x \equiv s_i \pmod{m_i}\) and then take everything modulo the common part. This can be done easily with the following code:
from functools import reduce
from binascii import unhexlify
def long_to_bytes (val, endianness='big'):
width = val.bit_length()
width += 8 - ((width % 8) or 8)
fmt = '%%0%dx' % (width // 4)
s = unhexlify(fmt % val)
if endianness == 'little':
s = s[::-1]
return s
def chinese_remainder(n, a):
sum = 0
prod = reduce(lambda a, b: a*b, n)
for n_i, a_i in zip(n, a):
p = prod / n_i
sum += a_i * mul_inv(p, n_i) * p
return sum % prod
def mul_inv(a, b):
b0 = b
x0, x1 = 0, 1
if b == 1: return 1
while a > 1:
q = a // b
a, b = b, a%b
x0, x1 = x1 - q * x0, x0
if x1 < 0: x1 += b0
return x1
m = 581090821296317933693586537610831214024106768710093022974488362042825786477677095350272592362056161640241973209079990997920846540763147917348498786721
shares = [(2433540313092365358498910942615091739287190301494338351018258678488932416718555674164347001675072449071289374832316621249466217351144971694400277452989036L, 10379490429112932725800525476020867148375792941644900618767976870525310215947891346374096900780789001714921833829498506828021591411760530235331835919286003L), (2262603161348726135418932740967190432585242845626488888779312128341566485277282354452876012214562566631359352738148304731959582728554256835607203231425197L, 7342469201597956175509034967124623233618829870845574781688439222933081691218704225899537135983331659871971737540220700398611027025368347105138783354976173L), (3492754970417800154420205999588295393340353056895768081040806914643671022355393817705909555093471544656712602739817729737860291247150771530739437276334536L, 3783463518648947796238532310991965471957180170807360550575038277767085146044062769485330460239260211302790479547388526187955893618468256872898858016737383L), (5339545252534280472242742310638383594901538452739451841210131676544815273328248324884529621635855444020235346537290530627519492230612306746719716960021148L, 7810530476920181982000554210844947350305708533931170749727106706830151408164755959553997101332430424617061522255248349466630265828242145686241337221093051L), (4825328812655303751234536925550835315371457930382464357564525734421020895932184792716783826884367873275483773856284827325887278426609459173620999562574774L, 5437855093996708328328099324048825805595325601466898274296243311675283452628347416193179036392625149835415876095557371227403616979377009793937256895553363L), (8624661229926683655254411870252240544902913193200615805969495945838977950606124497283973387891681974373628959722612953288481186484505784288423905884205750L, 11205985361034323967745602584439532920107173548419567454912391103067391741404908912086184510756358122763592487894419548439764378967443404278258826122535161L), (1121564545146022200101752054366322248276590219181932582571326549017234461215232323421497536894461382635314586082222852725480671211524986019821955899877615L, 7905066786107219416113543069692484270903258888539133253209314151913257354823237228357054476824521464801864635879842225506031204018136356134463361913303509L), (7947293090213596625050053248142396727423010297760649653046134262588142903664933711001583373235991690788909013347415429367440973173680006670427795429577538L, 12024880774676453668188636202118509605243465262025093321460328384766139136489442552825541437836422732170964621525371780187434816456086229802202952836220723L), (7926196731644739710108173449852692325087797722838788154868427366798722851882146096700759566617784402815052598878505576691995839630748784308155360560526195L, 8372123343604603466558819446021026865538454852031250080875021052140962881782152385383291129307903273725608779033447780512261550418095116661182748024556639L), (3904325341602542172710907632843884668890887461781548713821150871143171273341552762737833501209411305097414078525125341026103741903007835578976438792678297L, 8210422318054241965968078354433314698771586517678743336751641130673800537820126456447197115452847623544483171107559095812152332418782762640635939670146363L)]
n = []
a = []
for i in range(len(shares)):
n.append(shares[i][0])
a.append(shares[i][1])
sol = chinese_remainder(a,n) % m
print(long_to_bytes(sol))
crypto secret_sharing