Secret Sharing
Shamir门限
条件：
-
(0<kleq n<p)
-
(S<p,p)是素数
Lagrange插值公式
[f(x)=sum^{k}_{j=1}f(x_j)prod^{k}_{i=1,i
eq j}frac{x-x_i}{x_j-x_i}(mod p)\
egin{equation}egin{aligned}
S&=sum^{k}_{j=1}f(x_j)prod^{k}_{i=1,i
eq j}frac{0-x_i}{x_j-x_i}(mod p)\
&=sum^{k}_{j=1}f(x_j)prod^{k}_{i=1,i
eq j}frac{x_i}{x_i-x_j}(mod p)
end{aligned}end{equation}
]
至少要k个值才能恢复出(f(x))然后就能得到S
Ep:
(k=3,n=5,p=19,S=11)
随机选(a_1=2,a_2=7),则有(f(x)=11+2x+7x^2mod 19)
计算(f(1)=1,f(2)=5,f(3)=4,f(4)=17,f(5)=6)
已知(f(2),f(3),f(5))重构:
(f(x)=5frac{(x-3)(x-5)}{(2-3)(2-5)}+4frac{(x-2)(x-5)}{(3-2)(2-5)}+6frac{(x-2)(x-3)}{(5-2)(5-3)}=11+2x+7x^2)
Asmuth-Bloom门限
参数
(p,S,(m_1,m_2,…,m_n),N)
条件
- (p>S,p)是一个大素数
- ((m_i,m_j)=1,m_1,m_2,…,m_n)是严格递增的数((forall i,j,i eq j))
- ((p,m_i)=1(i=1,2,…,n))
- (N=prod^{k}_{i=1}m_i>pprod^{k-1}_{j=1}m_{n-j+1})
Secret分割
-
随机选取整数(A)满足(0leq Aleq [N/p]-1),公布(p,A)
-
(y=S+Ap),则有(y<p+Ap=(A+1)pleq[N/p]cdot ple N)
-
计算(y_iequiv y(mod m_i)(i=1,2,…,m),(m_i,y_i))就是一个子共享，总构成(k,n)门限
Secret恢复
给出k个子分享，建立方程组
[egin{cases}
yequiv y_{i_1}mod m_{i_1}\
yequiv y_{i_2}mod m_{i_2}\
……\
yequiv y_{i_k}mod m_{i_k}
end{cases}
]
根据中国剩余定理:(yequiv y'mod N')其中,(N'=prod^{k}_{j=1}m_{i_j}le N)
(S=y'-Ap)
Ep:
AFCTF2018 花开藏宝地
给出了5个加密zip，给出了提示
- secret1 生日字典/脑洞 19260817
- secret2 小写爆破 alice
- secret3 大写爆破 AVADA
- secret4 伪加密
- secret5 NTFS隐写
取(1,2,3)份的值，素数为题面的素数
exp:
from Crypto.Util.number import long_to_bytes
a1 =163305039963008322700958678938420655039108584848594236473036556130206292229761961459635355105529119955950769119000647821166302409987726181456624233820238004130596582552143052085826562771938653314722288583956794740182869336927141053110739981290237894112152720822014240230972011848683576402535994825309029822761855623903611335752059666683377536920052428648302389426609672118522003510398578217
d1 =347051559622463144539669950096658163425646411435797691973701513725701575100810446175849424000000075855070430240507732735393411493866540572679626172742301366146501862670272443070970511943485865887494229487420503750457974262802053722093905126235340380261828593508455621667309946361705530667957484731929151875527489478449361198648310684702574627199321092927111137398333029697068474762820813413
a2 =151758100093328024755534362157152644916689556800407091638077262152051356374687426002691308331360911658681675621180784078464300557713597658668737755275578303683512763651424490696663046659762209459401095803407234074793144034799798937463085989364658809489473016814564284374253047111285307568938011571482613761721746338619879940928380741377367381517427341679641871126076991209176935339058909863
d2 =347051559622463144539669950096658163425646411435797691973701513725701575100810446175849424000000075855070430240507732735393411493866540572679626172742301366146501862670272443070970511943485865887494229487420503750457974262802053722093905126235340380261828593508455621667309946361705530667957484731929151875527489478449361198648310684702574627199321092927111137398333029697068474762820818553
a3 = 346077592068259399350080379767941982003794373736058097723728104020814800897686828693026215723695173898771936691822530717642440410239211631306801809213192374695040232378965389612021366734818648007275332322621064659199680848745242700755440206949465953441277866419617961232234201083716216031999849609543380477085554544227121956015035672626500140341901966363694497881768843758979050832435224875
d3 =347051559622463144539669950096658163425646411435797691973701513725701575100810446175849424000000075855070430240507732735393411493866540572679626172742301366146501862670272443070970511943485865887494229487420503750457974262802053722093905126235340380261828593508455621667309946361705530667957484731929151875527489478449361198648310684702574627199321092927111137398333029697068474762820819351
dd = d1*d2*d3
t1 = pow(dd//d1,d1-2,d1)
assert(t1*d2*d3%d1 == 1)
t2 = pow(dd//d2,d2-2,d2)
assert(t2*d1*d3%d2 == 1)
t3 = pow(dd//d3,d3-2,d3)
assert(t3*d2*d1%d3 == 1)
s = a1*t1*d2*d3+a2*t2*d1*d3+a3*t3*d1*d2
p = 80804238007977405688648566160504278593148666302626415149704905628622876270862865768337953835725801963142685182510812938072115996355782396318303927020705623120652014080032809421180400984242061592520733710243483947230962631945045134540159517488288781666622635328316972979183761952842010806304748313326215619695085380586052550443025074501971925005072999275628549710915357400946408857
s %= dd
print(s)
s %= p
print(long_to_bytes(s))