Tags: crypto chinese-remainder

Rating:

## Solution

Initially I thought this was related to the [bismuth project](https://github.com/hclivess/Bismuth), and that the secret is related to ECC, however this was a rabbit hole and a complete waste of time. Eventually, my teammate said this might be related to _Bloom-Asmuth secret sharing_.

With that, the solution is fairly straightforward. We just had to implement the algorithm described in the [wikipedia page](https://en.wikipedia.org/wiki/Secret_sharing_using_the_Chinese_remainder_theorem#Asmuth-Bloom's_threshold_secret_sharing_scheme).

python
#sagemath
from Crypto.Util.number import *

m0 = 581090821296317933693586537610831214024106768710093022974488362042825786477677095350272592362056161640241973209079990997920846540763147917348498786721

ms = [
(2433540313092365358498910942615091739287190301494338351018258678488932416718555674164347001675072449071289374832316621249466217351144971694400277452989036L, 10379490429112932725800525476020867148375792941644900618767976870525310215947891346374096900780789001714921833829498506828021591411760530235331835919286003L),
...
]

secrets = zip(*ms)
flag = CRT(list(secrets[0]), list(secrets[1]))%m0

print(long_to_bytes(flag))


Original writeup (https://github.com/pberba/ctf-solutions/tree/master/20181223_xmasctf/crypto-486-santas_secret_b(i)smuth).