X-MAS CTF 2018 - Santa's Secret B(i)smuth

crypto
,

For this one we’re given the following values

1
2
common_part = 581090821296317933693586537610831214024106768710093022974488362042825786477677095350272592362056161640241973209079990997920846540763147917348498786721
Secret = [(2433540313092365358498910942615091739287190301494338351018258678488932416718555674164347001675072449071289374832316621249466217351144971694400277452989036L, 10379490429112932725800525476020867148375792941644900618767976870525310215947891346374096900780789001714921833829498506828021591411760530235331835919286003L), (2262603161348726135418932740967190432585242845626488888779312128341566485277282354452876012214562566631359352738148304731959582728554256835607203231425197L, 7342469201597956175509034967124623233618829870845574781688439222933081691218704225899537135983331659871971737540220700398611027025368347105138783354976173L), (3492754970417800154420205999588295393340353056895768081040806914643671022355393817705909555093471544656712602739817729737860291247150771530739437276334536L, 3783463518648947796238532310991965471957180170807360550575038277767085146044062769485330460239260211302790479547388526187955893618468256872898858016737383L), (5339545252534280472242742310638383594901538452739451841210131676544815273328248324884529621635855444020235346537290530627519492230612306746719716960021148L, 7810530476920181982000554210844947350305708533931170749727106706830151408164755959553997101332430424617061522255248349466630265828242145686241337221093051L), (4825328812655303751234536925550835315371457930382464357564525734421020895932184792716783826884367873275483773856284827325887278426609459173620999562574774L, 5437855093996708328328099324048825805595325601466898274296243311675283452628347416193179036392625149835415876095557371227403616979377009793937256895553363L), (8624661229926683655254411870252240544902913193200615805969495945838977950606124497283973387891681974373628959722612953288481186484505784288423905884205750L, 11205985361034323967745602584439532920107173548419567454912391103067391741404908912086184510756358122763592487894419548439764378967443404278258826122535161L), (1121564545146022200101752054366322248276590219181932582571326549017234461215232323421497536894461382635314586082222852725480671211524986019821955899877615L, 7905066786107219416113543069692484270903258888539133253209314151913257354823237228357054476824521464801864635879842225506031204018136356134463361913303509L), (7947293090213596625050053248142396727423010297760649653046134262588142903664933711001583373235991690788909013347415429367440973173680006670427795429577538L, 12024880774676453668188636202118509605243465262025093321460328384766139136489442552825541437836422732170964621525371780187434816456086229802202952836220723L), (7926196731644739710108173449852692325087797722838788154868427366798722851882146096700759566617784402815052598878505576691995839630748784308155360560526195L, 8372123343604603466558819446021026865538454852031250080875021052140962881782152385383291129307903273725608779033447780512261550418095116661182748024556639L), (3904325341602542172710907632843884668890887461781548713821150871143171273341552762737833501209411305097414078525125341026103741903007835578976438792678297L, 8210422318054241965968078354433314698771586517678743336751641130673800537820126456447197115452847623544483171107559095812152332418782762640635939670146363L)]

Solution

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 and what we have to do is to solve the system of equations and then take everything modulo the common part. This can be done easily with the following code:

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
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))