Sercet sharing

时间：2022-05-11 23:46:04

Secret Sharing
Shamir门限

条件：

  1. (0<kleq n<p)

  2. (S<p,p)是素数

Lagrange插值公式
[ f(x)=sum^{k}_{j=1}f(x_j)prod^{k}_{i=1,ineq j}frac{x-x_i}{x_j-x_i}(bmod p)\begin{equation}begin{aligned} S&=sum^{k}_{j=1}f(x_j)prod^{k}_{i=1,ineq j}frac{0-x_i}{x_j-x_i}(bmod p)&=sum^{k}_{j=1}f(x_j)prod^{k}_{i=1,ineq j}frac{x_i}{x_i-x_j}(bmod 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^2bmod 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

条件

  1. (p>S,p)是一个大素数
  2. ((m_i,m_j)=1,m_1,m_2,…,m_n)是严格递增的数((forall i,j,ineq j))
  3. ((p,m_i)=1(i=1,2,…,n))
  4. (N=prod^{k}_{i=1}m_i>pprod^{k-1}_{j=1}m_{n-j 1})

Secret分割

  1. 随机选取整数(A)满足(0leq Aleq [N/p]-1),公布(p,A)

  2. (y=S Ap),则有(y<p Ap=(A 1)pleq[N/p]cdot ple N)

  3. 计算(y_iequiv y(bmod m_i)(i=1,2,…,m),(m_i,y_i))就是一个子共享，总构成(k,n)门限

Secret恢复

给出k个子分享，建立方程组
[ begin{cases} yequiv y_{i_1}bmod m_{i_1}yequiv y_{i_2}bmod m_{i_2}……yequiv y_{i_k}bmod m_{i_k} end{cases} ]
根据中国剩余定理:(yequiv y'bmod N')其中,(N'=prod^{k}_{j=1}m_{i_j}le N)

(S=y'-Ap)

Ep:

AFCTF2018 花开藏宝地

给出了5个加密zip，给出了提示

  1. secret1 生日字典/脑洞 19260817
  2. secret2 小写爆破 alice
  3. secret3 大写爆破 AVADA
  4. secret4 伪加密
  5. 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

相关文章