De1CTF 2020 Writeup May 6, 2020 # Crypto ## NLFSR 可以发现输出是1时，ao是1的概率有75%。可以枚举前19个ao，解方程得到a的初始值，再枚举c和d的初始值，可以得到b的若干状态，最后解方程得到b，再检验。 ```cpp #include<bits/stdc++.h> typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef std::pair<int,int> pii; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;} template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;} template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}} template<typename T> inline T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define I __attribute__((always_inline))inline #define mset(a,b) memset(a,b,sizeof(a)) #define mcpy(a,b) memcpy(a,b,sizeof(a)) #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) #define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) #define fd0(i,n) for(int i=(n)-1;~i;i--) #define fd1(i,n) for(int i=n;i;i--) #define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--) #define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i) #define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i) struct Cg{I char operator()(){return getchar();}}; struct Cp{I void operator()(char x){putchar(x);}}; #define OP operator #define RT return *this; #define UC unsigned char #define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\ if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0' #define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x #define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0' #define TR *this,x;return x; I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x) {RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x) {for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS (t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf() {llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in; #define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0') #define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\ x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5); #define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0') template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT} I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP() (ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT} I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out; struct bits { uint s[19]; void lfsr(uint m) { uint t=0; fo0(i,19)if(m>>i&1)t^=s[i]; fd0(i,18)s[i+1]=s[i]; s[0]=t; } void init() { fo0(i,19)s[i]=1<<i; } }; uint c,f[19],v[19]; void clear() { c=0; fo0(i,19)f[i]=v[i]=0; } int addc(uint a,uint b) { fo0(i,19)if(a>>i&1) { if(!f[i]) { f[i]=a; v[i]=b; c++; return c==19?1:0; } a^=f[i]; b^=v[i]; } return b?2:0; } uint sol() { fo0(i,19)fo(j,i+1,18)if(f[i]>>j&1) { f[i]^=f[j]; v[i]^=v[j]; } uint r=0; fo0(i,19)r+=v[i]<<i; return r; } template<const uint m>void lfsr(uint&r) { r=(r<<1)^__builtin_parity(r&m); } char data[1<<20]; int main() { freopen("data","r",stdin); fo0(i,1<<20)in,data[i]; fo0(i,1<<20)data[i]-=48; fo0(adb,19)fo0(ad,1<<19)if(__builtin_popcount(ad)==adb) { bits t;t.init();clear(); fo0(j,19) { t.lfsr(0x505a1); addc(t.s[0],(ad>>j&1)^data[j]); } uint ia=sol(); if(!(ia>>18))continue; fo(ic,1<<12,(1<<13)-1)fo(id,1<<5,(1<<6)-1) { bool flag=1; uint a=ia,c=ic,d=id; for(int u=0;u<10;u++) { lfsr<0x505a1>(a); lfsr<0x1f02>(c); lfsr<0x31>(d); if(!((a^c^d)&1)&&(((c^d)&1)^data[u])) { flag=0; break; } } if(!flag)continue; a=ia,c=ic,d=id; t.init();clear(); for(int u=0;;u++) { lfsr<0x505a1>(a); lfsr<0x1f02>(c); lfsr<0x31>(d); t.lfsr(0x40f3f); uint oa=a&1,oc=c&1,od=d&1; if(oa^oc^od) { uint req=oc^od^data[u]; if(addc(t.s[0],req))break; } else { if(oc^od^data[u]) { flag=0; break; } } } if(!flag)continue; uint ib=sol(),b=ib; a=ia,c=ic,d=id; fo0(u,100) { lfsr<0x505a1>(a); lfsr<0x40f3f>(b); lfsr<0x1f02>(c); lfsr<0x31>(d); uint cur=((a&b)^(b&c)^(b&d)^c^d)&1; if(cur!=data[u]) { flag=0; break; } } if(flag) { out,"possible solution:",ia,' ',ib,' ',ic,' ',id,'\n'; return 0; } } } } ``` ## Mini Purε Plus View English edition at https://oj.ci/blogof/mcfx/blog/30 搜索到 De1CTF2019 的 Mini Purε 一题，本题和该题大致相同，只是已知的明文连续，并且轮数从 6 增加到了 16。同样考虑插值，但是本题中需要插值的多项式达到了 $$3^{14}$$ 次，$$n^2$$ 的算法无法通过，并且插值和求 key 需要分开进行。通过找规律可以发现 （实际上把拉格朗日插值的式子化一下也能得到相同结果） ，对于函数 $$F$$，若 $$F$$ 的次数不超过 $$k-1$$（$$k$$ 是 $$2$$ 的幂），则 $$F(n)=\sum\_{i=0}^{k-1} F(i)\frac{\prod\_{j=0,j\neq i}^{k-1}n \oplus j}{(k-1)!}$$（$$\oplus$$ 表示异或，乘法是这个域下的（即 F.Multiply），阶乘指这个域下的 1,2,...,k-1 相乘）。这个式子右边的系数可以 $$O(k)$$ 求出所有 n^j 的乘积后，再每次除以对应的 n^j 算出。把最后一个 key 设为未知数，然后再套用这个公式，即可得到一个 key 满足的三次方程（实际上三次项系数恒为 0）。可以枚举 key 来解出这个方程。需要找多个 n，求出解的交集，才能保证唯一性。 ```cpp #include<bits/stdc++.h> typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef std::pair<int,int> pii; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;} template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;} template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}} template<typename T> inline T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define I __attribute__((always_inline))inline #define mset(a,b) memset(a,b,sizeof(a)) #define mcpy(a,b) memcpy(a,b,sizeof(a)) #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) #define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) #define fd0(i,n) for(int i=(n)-1;~i;i--) #define fd1(i,n) for(int i=n;i;i--) #define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--) #define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i) #define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i) #define BSZ 131072 template<const char*fn>struct FCg{char t[BSZ+1],*o,*e;FILE*f;FCg(){f=fopen(fn,"r");e=o=t+BSZ;}I char operator()(){if(o==e)fread(o=t,1,BSZ,f);return *o++;}}; struct Cg{I char operator()(){return getchar();}}; struct Cp{I void operator()(char x){putchar(x);}}; #define OP operator #define RT return *this; #define UC unsigned char #define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\ if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0' #define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x #define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0' #define TR *this,x;return x; I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x) {RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x) {for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS (t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf() {llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in; #define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0') #define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\ x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5); #define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0') template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT} I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP() (ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT} I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out; ull mul(ull a,ull b) { ull r=0; fo0(i,64)if(a>>i&1)r^=b<<i; return r; } ull divn(ull a,ull b) { ull r=0; fd0(i,60-std::__lg(b))if((a^(b<<i))<a)r^=1ull<<i,a^=b<<i; return r; } ull mod(ull a,ull b) { ull r=0; fd0(i,60-std::__lg(b))if((a^(b<<i))<a)r^=1ull<<i,a^=b<<i; return a; } pii divmod(ull a,ull b) { ull r=0; fd0(i,25)if((a^(b<<i))<a)r^=1ull<<i,a^=b<<i; return mp(r,a); } void exgcd(ull a,ull b,ull&x,ull&y) { if(!b) { x=1,y=0; return; } exgcd(b,mod(a,b),y,x); y^=mul(divn(a,b),x); } ull inv_(ull a,ull b) { ull x,y; exgcd(a,b,x,y); assert(mod(mul(a,x),b)==1); return x; } const int P=16901801; uint mulm(uint x,uint y) { ull a=0; fo0(i,24)if(x>>i&1)a^=ull(y)<<i; fd(i,46,24)if(a>>i&1)a^=16901801ull<<(i-24); return a; } uint mulm8(uint x,uint y) { ull a=0; fo0(i,25)if(x>>i&1)a^=ull(y)<<i; fd(i,50,24)if(a>>i&1)a^=16901801ull<<(i-24); return a; } uint modx(uint x) { if(x>>24)return x^P;return x; } const int N=1<<24; const uint EL=0x777777; uint sl[N],sr[N]; constexpr char F_PT[]="pt.txt",F_CT[]="ct.txt"; uint hex1(char x) { if(x<=57)return x-48; return x-87; } uint dehex(char*s) { uint r=0; fo0(i,6)r=r*16+hex1(s[i]); return r; } uint fbox3(uint x) { ull a=0,b=0,t[4]={0,x,x<<1,x^(x<<1)}; for(ull i=0;i<24;i+=2)a^=t[x>>i&3]<<i; fd(i,46,41)if(a>>i&1)a^=16901801ull<<(i-24); t[3]=(t[1]=a)^(t[2]=a<<=1); for(ull i=0;i<24;i+=2)b^=t[x>>i&3]<<i; fd(i,63,24)if(b>>i&1)b^=16901801ull<<(i-24); return b; } uint get_interpolate_coeff(int n,int rx) { uint tt=1,vv=1; fo0(i,n)tt=mulm(tt,rx^i); fo1(i,n-1)vv=mulm(vv,i); return mulm(tt,inv_(vv,P)); } uint inv[N]; int main() { inv[1]=1; fo(i,2,N-1) { pii t=divmod(P,i); inv[i]=mulm8(P^t.xx,inv[t.yy]); } out,"pre inv ok\n"; Fr<FCg<F_PT>>in_pt; Fr<FCg<F_CT>>in_ct; fo0(i,N) { char a[13],b[13]; in_pt,a; in_ct,b; uint x=dehex(a+6),y=dehex(b),z=dehex(b+6); sl[x]=z,sr[x]=y;//swapped } out,"read file ok\n"; int keys[16]; for(int keypos=15;keypos>=2;keypos--) { out,"solving key ",keypos,'\n'; int keyr=pow(3,keypos-1); int n=1<<1+std::__lg(keyr); std::set<int>real_valid; for(int rx=n;;rx++) { out,"n ",n,", try rx ",rx,'\n'; uint tt=get_interpolate_coeff(n,rx); out,"get interpolate coef ok\n"; uint coef[4]; mset(coef,0); fo0(i,n) { // l , r = r , l ^ fbox(keys[i] ^ r) // oldl = r ^ fbox(key ^ l) uint a=sl[i],b=mulm(a,a),c=mulm(a,b),v=mulm(tt,inv[rx^i]); coef[0]^=mulm(sr[i]^c,v); coef[1]^=mulm(b,v); coef[2]^=mulm(a,v); coef[3]^=v; } { uint a=sl[rx],b=mulm(a,a),c=mulm(a,b); coef[0]^=sr[rx]^c; coef[1]^=b; coef[2]^=a; coef[3]^=1; } out,"get coef ok\n"; out,"coef:";fo0(i,4)out,coef[i],' ';out,'\n'; std::set<int>valid; fo0(i,N) { uint a=i,b=mulm(a,a),c=mulm(a,b); if(!modx(mulm(coef[3],c)^mulm(coef[2],b)^mulm(coef[1],a)^coef[0]))valid.insert(i); } if(!real_valid.size()) { real_valid=valid; } else { std::set<int>nxt; for(int x:valid)if(real_valid.count(x))nxt.insert(x); real_valid=nxt; if(real_valid.size()==1)break; assert(real_valid.size()); } out,"possible keys:";for(int x:real_valid)out,x,' ';out,'\n'; } int key=*real_valid.begin(); keys[keypos]=key; out,"key ",keypos,": ",key,'\n'; fo0(i,N) { uint l=sl[i],r=sr[i]; uint oldl=r^fbox3(key^l); r=l; l=oldl; sl[i]=l,sr[i]=r; } out,"decrypted\n"; } fo0(i,N)if((EL^fbox3(i))==sl[0]&&(EL^fbox3(i^1))==sl[1])keys[0]=i; fo0(i,N)if(fbox3(sl[0]^i)==sr[0]&&(1^fbox3(sl[1]^i))==sr[1])keys[1]=i; out,"keys: ";fo0(i,16)out,keys[i],", ";out,'\n'; } ``` ## ECDH 程序中没有对公钥进行校验，可以用不在曲线上的点。枚举一些 $$b$$，找一些阶有小因子的曲线，对这些小因子可以暴力求出离散对数的余数，然后使用中国剩余定理合并。 下面两个脚本，第一个脚本是枚举 $$b$$ 的，第二个是和服务器交互的。 ```python from sage.all import * from sympy.ntheory import sqrt_mod from gmpy2 import * import random q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa #b = 0x56cbc73d8d2ad00e22f12b930d1d685136357d692fa705dae25c66bee23157b8 b=3 def timeout(func, args=(), kwargs={}, timeout_duration=10): @fork(timeout=timeout_duration, verbose=True) def my_new_func(): return func(*args, **kwargs) return my_new_func() def fac1(n): t=timeout(factor,(n,),{},3) if type(t) is str: return [(n,1)] return list(t) zero=(0,0) def add(p1,p2): if p1 == zero: return p2 if p2 == zero: return p1 (p1x,p1y),(p2x,p2y) = p1,p2 if p1x == p2x and (p1y != p2y or p1y == 0): return zero if p1x == p2x: tmp = (3 * p1x * p1x + a) * invert(2 * p1y , q) % q #print(tmp,invert(2 * p1y , q),(3*p1x*p1x+a)%q) else: tmp = (p2y - p1y) * invert(p2x - p1x , q) % q #print('tmp:',tmp) x = (tmp * tmp - p1x - p2x) % q y = (tmp * (p1x - x) - p1y) % q return (int(x),int(y)) def mul(n,p): r = zero tmp = p while 0 < n: if n & 1 == 1: r = add(r,tmp) n, tmp = n >> 1, add(tmp,tmp) return r F=FiniteField(q) f={} while True: E=EllipticCurve(F,[a,b]) o=E.order() print b,o t=fac1(o) print(t) for x,y in t: if x**y<10000 and (x not in f or f[x][0]<y): r=int(o)//x**y #while True: t2=False for i in range(x**y*3): ux=random.randint(0,q-1) uy=sqrt_mod((ux**3+ux*a+b)%q,q) #print(ux,uy) if uy is not None: od=E.point((ux,uy)).order() if od % x**y == 0: t2=mul(int(od)//x**y,(ux,uy)) break if t2==False: print(x,y,'skip') continue print(x,y,t2) assert(E.point(t2).order()==x**y) f[x]=(y,t2) u=1 for x in f: u*=x**f[x][0] print 'u:',u if u>q: break b+=1 for x in f: print(x,f[x][0],f[x][1]) ``` ```python import os,random,sys,string from hashlib import sha256 from gmpy2 import invert from binascii import unhexlify from pwn import * context.log_level='debug' table=[(2, 6, (15515261289492000636723716832530474441073793179820253654344161846899397174163, 70732673780185253533560312981065425697374855122155226842361189468006993016608)), (3, 4, (60644430586292500807468800471222459463635175483477838721990697739818739099186, 16849390271247056396316169242269790248390887059915425051633208890222288732308)), (5, 3, (5528529652585034540224644062864754084219932471810717108295409545601068117245, 51758490718562369829013860973372210155698131711621237886181135191530362849794)), (7, 4, (40392338877400485203078176081718688614099837261220989485738369786640826232054, 91153592734846614636469144647462767082263205384560870269434577477306773979891)), (11, 1, (26468109550543433678994725852332470419860078736495236337093765517625052146217, 30030378315449445421642742996042765533105249598547875770169791334902801551576)), (13, 1, (95295478088788933512826351457131936019556851795692390283786723909538384825602, 97278701628009650441905889580352351278736310561880101391071560781416283458962)), (17, 1, (65837680812938494455375972222216255836369326737529398552707397639739049723703, 33208520506802012808461386954426139890984796376331927142382609600245216288494)), (131, 1, (75413644696437288380416125222340362010683706114954647219476351446822453348076, 83702919061607667358054206436481921059620150651200302096596829041453951506443)), (5657, 1, (70499678082099959151425588974046571307561218806076877159661239835817348455787, 11505825114646650622194943383898280302683645307270959404836704168921936777413)), (9241, 1, (13469916461975726791324477068741305127538951745273261934754783046892205243425, 625147783966158809929549276916984877707259429146400534321490899006477322266)), (4621, 1, (10076941876862741784977155613763400255220273193889689786141182250956528935919, 49406921986921091899525425340592596515650819043238308774041397214839183276000)), (2333, 1, (71880145504007257203966204065686225216236958299194853057697944529309264988346, 8677894132577051961756730904145989744695974306667223198269180132628421781789)), (31, 1, (71042727689323597341291894219177126947616248823335274140949335289544392720824, 45772930136487189798938708075768675400376691242082880401294458476052354873898)), (37, 1, (24118287569188964318275888822817421880450904526350392166501002900611917829565, 3680190950398616974070833403166614986350330478918223384476799013369032031851)), (1009, 1, (92187640513637539408296220568909716964516433202612852987221284345725680872609, 26260904735235128781738570562562721709781352309940097086267361653176966173676)), (41, 1, (3066999177232399566508055021243130941665805183592135288208622116033265288444, 92393733619593491765990163126745077862875965784039641959544220857159656474086)), (43, 1, (97228779193481048069285040598986324767912386297638779341714456628677381491695, 18759417200485761166946170090462910796186262281394965842860629726771509917917)), (47, 1, (57180193262500956333203171862406674004642936568084724246042508084678517575640, 70162295479900913971593701336814638490133667924284548274495009809941170069250)), (53, 1, (15579788653108424130263940051632273201909924510914880066303214667923223073219, 76263745719636011547585341737098104188635706224250254064457670665325932374031)), (311, 1, (950329615975590747523806576462151877961103821569268241790171963348349791909, 76543211939132548291393704246697102389659652088494495704582204879372361098723)), (6073, 1, (25016342617497682964438693423273111600168741895722086513717109106463747542427, 57768715347881292141064126576258017798037475015634531788352982807876997221251)), (1567, 1, (74058700877346832479128967774152612928000983436457734350068032120895529216497, 1708279924881167680901068917743327624896568244136802468165850058989229161145)), (1973, 1, (54729816429035730894822772247154366967107036508315733382573253360968405034799, 81429716748913679974061130364821817487515206212180922370900847048231930941763)), (1291, 1, (74980927490098396683015872123990216016037302378390964998804014735849997412469, 82625687252178165025928010201289023441868160811044396968885376008215748852604)), (709, 1, (92955163666272498635446824256806680531972012111577971243736656488139632096882, 66922942483051868447068386260718042684834251247583246641977579031995329864591)), (719, 1, (71799262452972755571855429182036975429508040858823728850004489395747854471701, 73681861832673181257393813284559219372405590409965081777800968576795832942512)), (853, 1, (64908313140867893143216336630963136039584606786189601019828694727341243414171, 33085867585019942469263918716669571228794418949740146064880473153645942681676)), (59, 1, (36996626633099586579662722926353853127782282780590288372280652930641604528707, 45917233308318199676044676117838944021278139827386480013081783161258801905500)), (103, 1, (77849788044807298207880916948872226371255754702212393500094336975351126048340, 27542826819935558516725818290967078863217407852992402818731591102209581497613)), (2281, 1, (97969541276731315447885157282376106483991961866722142348413628177302083792895, 45798677383348696990666008407246194680327854507649706700191958988885151615672)), (29, 1, (77531461761763053544962150909546436954079293162821864080798209972546114789501, 48703099908339279581300847939211968945332330876286076427798555180633398400191)), (881, 1, (24317548779522198821247428992771511674292061765522152455774057311652520808085, 38960104630988783750463951363466493085599734114544363489258672557054552709942))] q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa zero = (0,0) def add(p1,p2): if p1 == zero: return p2 if p2 == zero: return p1 (p1x,p1y),(p2x,p2y) = p1,p2 if p1x == p2x and (p1y != p2y or p1y == 0): return zero if p1x == p2x: tmp = (3 * p1x * p1x + a) * invert(2 * p1y , q) % q else: tmp = (p2y - p1y) * invert(p2x - p1x , q) % q x = (tmp * tmp - p1x - p2x) % q y = (tmp * (p1x - x) - p1y) % q return (int(x),int(y)) def mul(n,p): r = zero tmp = p while 0 < n: if n & 1 == 1: r = add(r,tmp) n, tmp = n >> 1, add(tmp,tmp) return r s=[] for x,y,z in table: t=x**y assert mul(t,z)==zero s.append((t,z)) print('s:',len(s)) n=1 for x,y in s: n*=x inv=[] for x,y in s: inv.append(invert(n//x,x)) r=remote('134.175.225.42',8848) def work_hash(): r.recvuntil('sha256(XXXX+') p=r.recv(16).decode() r.recvuntil('== ') h=r.recvuntil('\n').strip().decode() r.recvuntil('Give me XXXX:') st=string.ascii_letters+string.digits o=None for a in st: for b in st: for c in st: for d in st: if hashlib.sha256((a+b+c+d+p).encode()).hexdigest()==h: o=a+b+c+d break if o is not None: break if o is not None: break if o is not None: break r.send(o+'\n') work_hash() def leak(x,y,first): if not first: r.recvuntil('Tell me your choice:\n') r.send('Exchange\n') r.recvuntil('X:\n') r.send(str(x)+'\n') r.recvuntil('Y:\n') r.send(str(y)+'\n') r.recvuntil('Exchange success\n') r.recvuntil('Tell me your choice:\n') r.send('Encrypt\n') r.recvuntil('Give me your message(hex):\n') r.send('f'*128+'\n') r.recvuntil('The result is:\n') a=r.recvuntil('\n').strip() assert len(a)==128 a=unhexlify(a) print(a) b=[] for i in a: b.append(i^0xff) c=int.from_bytes(bytes(b),'big') return c>>256,c&(2**256-1) rv=0 for i in range(len(s)): c=s[i][0] x,y=s[i][1] res=leak(x,y,i==0) print(res) t=-1 cur=zero for j in range(c): if cur==res: t=j break cur=add(cur,(x,y)) print(i,t) assert t!=-1 rv=(rv+t*inv[i]*(n//c))%n r.recvuntil('Tell me your choice:\n') r.send('Backdoor\n') r.recvuntil('Give me the secret:\n') r.send(str(rv)+'\n') r.interactive() ``` ## Homomorphic 正如题目名所说，题目中的加密是同态的，给密文乘 x，则原文也会乘 x，所以只需要给 flag 的密文都乘上 x 再询问就可以绕过了。 ```python from pwn import * import time r=remote('106.52.180.168',8848) def work_hash(): r.recvuntil('sha256(XXXX+') p=r.recv(16).decode() r.recvuntil('== ') h=r.recvuntil('\n').strip().decode() r.recvuntil('Give me XXXX:') st=string.ascii_letters+string.digits o=None for a in st: for b in st: for c in st: for d in st: if hashlib.sha256((a+b+c+d+p).encode()).hexdigest()==h: o=a+b+c+d break if o is not None: break if o is not None: break if o is not None: break r.send(o+'\n') work_hash() r.recvuntil('The enc flag is: \n') s=[] for i in range(88): s.append(eval(r.recvuntil('\n'))) for i in range(0,88,2): r.send('Decrypt\n') r.recvuntil('Please input c0(Separated by commas):\n') r.send(','.join(map(str,[0]+s[i]))+'\n') r.recvuntil('Please input c1(Separated by commas):\n') r.send(','.join(map(str,[0]+s[i+1]))+'\n') r.recvuntil('The index:\n') r.send('1\n') #r.interactive() r.recvuntil('The result is: \n') print(chr(int(r.recvuntil('\n'))),end='') ``` ## mc_noisemap 网站会根据当前时间生成一些随机数，和 flag 异或，把每两个字节处理成一个 16 位的数，然后根据这些数生成若干图片。可以访问 `/map?seed=xxx` 生成原始图片，而网站本身的图片是加过水印的。 基本的思想是生成出所有图片，然后和网站上的匹配。注意到雪地在加水印之后颜色不变，可以以此作为标准来匹配。可以找出雪地相差不超过 10 块的图片，如果这样的图片超过 10 个，则可能原图根本没有雪地，这种情况可以直接忽略（因为网站可以多次生成）最后多跑一段时间，然后看看得到的 flag 哪种最多就好了。 下面这个脚本是生成图片信息用的： ```python from math import floor,cos,pi,sqrt PERLIN_YWRAPB = 4 PERLIN_YWRAP = 1 << PERLIN_YWRAPB PERLIN_ZWRAPB = 8 PERLIN_ZWRAP = 1 << PERLIN_ZWRAPB PERLIN_SIZE = 4095 perlin_octaves = 4 perlin_amp_falloff = 0.5 perlin=[0]*(PERLIN_SIZE+1) def scaled_cosine(i): return 0.5 * (1.0 - cos(i * pi)); def noiseSeed(seed): m=4294967296 a=1664525 c=1013904223 z=seed for i in range(PERLIN_SIZE+1): z=(a*z+c)%m perlin[i]=z/m def noise(x,y=0,z=0): if x<0: x=-x if y<0: y=-y if z<0: z=-z xi=floor(x) yi=floor(y) zi=floor(z) xf=x-xi yf=y-yi zf=z-zi r=0 ampl=0.5 for o in range(perlin_octaves): of = xi + (yi << PERLIN_YWRAPB) + (zi << PERLIN_ZWRAPB); rxf = scaled_cosine(xf); ryf = scaled_cosine(yf); n1 = perlin[of & PERLIN_SIZE]; n1 += rxf * (perlin[(of + 1) & PERLIN_SIZE] - n1); n2 = perlin[(of + PERLIN_YWRAP) & PERLIN_SIZE]; n2 += rxf * (perlin[(of + PERLIN_YWRAP + 1) & PERLIN_SIZE] - n2); n1 += ryf * (n2 - n1); of += PERLIN_ZWRAP; n2 = perlin[of & PERLIN_SIZE]; n2 += rxf * (perlin[(of + 1) & PERLIN_SIZE] - n2); n3 = perlin[(of + PERLIN_YWRAP) & PERLIN_SIZE]; n3 += rxf * (perlin[(of + PERLIN_YWRAP + 1) & PERLIN_SIZE] - n3); n2 += ryf * (n3 - n2); n1 += scaled_cosine(zf) * (n2 - n1); r += n1 * ampl; ampl *= perlin_amp_falloff; xi <<= 1; xf *= 2; yi <<= 1; yf *= 2; zi <<= 1; zf *= 2; if xf >= 1.0: xi+=1 xf-=1 if yf >= 1.0: yi+=1 yf-=1 if zf >= 1.0: zi+=1 zf-=1 return r heights=[.13,.23,.26,.36,.49,.6] map_height=174 map_width=50 hexagon_size=5 noise_mod=1 noise_scale=.01 island_size=.62 width=504 height=500 def get(seed): f=[[0]*map_width for i in range(map_height)] noiseSeed(seed) for i in range(map_height): y = i * (.86 * hexagon_size) for j in range(map_width): if i%2==0: x = j * (hexagon_size * 3) else: x = (hexagon_size * 1.5) + j * (hexagon_size * 3) noiseVal = noise((x / noise_mod)*noise_scale, (y / noise_mod)*noise_scale) dist = sqrt(pow((x - width/2), 2) + pow((y - height/2), 2)) grad = dist / (island_size * min(width, height)) noiseVal -= pow(grad, 3) noiseVal = max(noiseVal, 0) t=0 while t<6 and int(noiseVal*255)>=heights[t]*255: t+=1 f[i][j]=t return f def encstr(f): o='' for i in f: for j in i: o+=str(j) return o for i in range(0,65536,16): print('gen %d'%i) r='' for j in range(i,i+16): r+='%d '%j+encstr(get(j))+'\n' open('known/%d.txt'%i,'w').write(r[:-1]) ``` 下面这个是匹配图片用的： ```cpp #include<bits/stdc++.h> typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef std::pair<int,int> pii; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;} template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;} template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}} template<typename T> inline T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define I __attribute__((always_inline))inline #define mset(a,b) memset(a,b,sizeof(a)) #define mcpy(a,b) memcpy(a,b,sizeof(a)) #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) #define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) #define fd0(i,n) for(int i=(n)-1;~i;i--) #define fd1(i,n) for(int i=n;i;i--) #define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--) #define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i) #define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i) struct Cg{I char operator()(){return getchar();}}; struct Cp{I void operator()(char x){putchar(x);}}; #define OP operator #define RT return *this; #define UC unsigned char #define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\ if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0' #define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x #define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0' #define TR *this,x;return x; I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x) {RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x) {for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS (t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf() {llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in; #define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0') #define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\ x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5); #define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0') template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT} I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP() (ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT} I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out; const int N=65536; char fn[20],buf[174*50+10]; std::bitset<174*50>f[N],mask,cur; void readf(int id) { sprintf(fn,"known/%d.txt",id); FILE*f=fopen(fn,"r"); fo0(i,16) { int x; fscanf(f,"%d",&x); assert(x==id+i); fscanf(f,"%s",buf); fo0(j,174*50)::f[id+i][j]=buf[j]=='6'; ::f[id+i]&=mask; } fclose(f); } int main() { const int hexagon_size=5; fo0(i,174) { int x,y=i * (.86 * hexagon_size); fo0(j,50) { if(i%2==0)x = j * (hexagon_size * 3); else x = (hexagon_size * 1.5) + j * (hexagon_size * 3); mask[i*50+j]=x>=0&&x<504&&y>=0&&y<500; } } const int CN=31056; for(int i=0;i<CN;i+=16)readf(i); fo0(id,32) { sprintf(fn,"fs/%d.txt",id); FILE*fl=fopen(fn,"r"); fscanf(fl,"%s",buf); fclose(fl); fo0(j,174*50)cur[j]=buf[j]=='6'; int u; std::vector<int>ok; fo0(i,CN)if((u=(f[i]^cur).count())<10)ok.pb(i); if(ok.size()>10)ok.clear(); out,id;foe(i,ok)out,' ',*i;out,'\n'; } } ``` 下面这个是下载图片，调用匹配程序，再写入结果的： ```python from PIL import Image import os,time,requests,traceback import random_seed colors=[[120, 120, 225],[150, 150, 255],[237, 201, 175],[207, 241, 135],[167, 201, 135],[170, 170, 170],[255, 255, 255]] heights=[.13,.23,.26,.36,.49,.6] map_height=174 map_width=50 hexagon_size=5 noise_mod=1 noise_scale=.01 island_size=.62 width=504 height=500 def encstr(f): o='' for i in f: for j in i: o+=str(j) return o f=[[0]*map_width for i in range(map_height)] requests.get('http://134.175.230.10:6002/') curt=int(time.time()) seqs=[] for i in range(-30,0): seqs.append(random_seed.getseq(curt+i)) print('time:',curt) for id in range(32): print('process',id) fold=open('fs/%d.webp'%id,'rb').read() while True: try: open('fs/%d.webp'%id,'wb').write(requests.get('http://134.175.230.10:6002/maps/%d.webp'%id).content) im=Image.open('fs/%d.webp'%id) break except: traceback.print_exc() time.sleep(0.5) fnew=open('fs/%d.webp'%id,'rb').read() if fold==fnew: print('file not changed') continue #print(im.getpixel((499,503))) for i in range(map_height): y = i * (.86 * hexagon_size) y=int(y) for j in range(map_width): if i%2==0: x = j * (hexagon_size * 3) else: x = (hexagon_size * 1.5) + j * (hexagon_size * 3) x=int(x) if x>=0 and x<width and y>=0 and y<height: #print(x,y,im.getpixel((y,x))) #if list(im.getpixel((x+8,y+8))) not in colors: # print(x,y,(im.getpixel((x+8,y+8)))) cnt=0 for ux in range(-1,2): for uy in range(-1,2): t=im.getpixel((x+8+ux,y+8+uy)) if t[0]>250 and t[1]>250 and t[2]>250: cnt+=1 if cnt==9: #print(i,j,x,y) f[i][j]=6 else: f[i][j]='x' else: f[i][j]='x' open('fs/%d.txt'%id,'w').write(encstr(f)) for i in range(0,25): seqs.append(random_seed.getseq(curt+i)) def add(s,y): if y not in s: s[y]=1 else: s[y]+=1 print('run cpp') os.system('a.exe>aout.txt') print('run cpp ok') if not os.path.exists('pb.txt'): pb=[{}for i in range(32)] else: pb=eval(open('pb.txt').read()) cur=0 for i in open('aout.txt').readlines(): t=list(map(int,i.split())) assert t[0]==cur//2 t=t[1:] for k in t: high=k>>8 low=k&255 #a,b a+b==high b-a==low #b*2==high+low t=high+low if t&1: continue for b in [t>>1,(t>>1)+128&255]: a=(high-b)&255 assert ((a+b)&255)==high and ((b-a)&255)==low for j in seqs: add(pb[cur//2],(j[cur]^a,j[cur+1]^b)) cur+=2 open('pb.txt','w').write(str(pb)) ``` 最后跑了十几分钟，每两个字节出现大于三次的情况基本都是对了的，人工筛选一下可以得到 secret：`Minecraft Noise Secret is: De1CTF{MCerrr_L0v3_P3r1iN_N0IsE-M4p?}`。 # Reverse ## parser flag 里可以有字母、数字和 `_+`。对于 `+` 分割的两块，程序会把他们的处理结果连起来，以 pad(`De1CTF`) 为 key 做 aes 加密；其次对于 `_` 分割的，会连起来做 des；最后对于单块的字母数字，会做 rc4。最后得到的结果会和内置串进行比较。可以尝试对当前串解密，然后判断 pad（或者是不是字母数字），如果是就递归搜索。 ```python from Crypto.Cipher import AES,DES,ARC4 import string req=b"\xe7\xa43L\xd3\x11\xe7\x85hV\x97\x11\xee\xd2\xf8\xd9>p\xc9N\x94\xa02Z'\x98\x00\x1d\xd5\xd7\x11\x1d\xf4\x85a\xac\x0c\x80'@\xbd\xdd\x1f\x0b\xb4\x97\x1f`[T\xcb\xc5\xa8\xb7\x11\x90\xc9\xb5\x81eS\x0f~\x7f" def xor_str(x,y): return bytes(map(lambda x,y:x^y,x,y)) def dec1(s): key=b'De1CTF\n\n\n\n\n\n\n\n\n\n' return AES.new(key,AES.MODE_CBC,key).decrypt(s) def dec2(s): key=b'De1CTF\x02\x02' return DES.new(key,DES.MODE_CBC,key).decrypt(s) def dec3(s): key=b'De1CTF' return ARC4.new(key).decrypt(s) def checkpad(s,n): t=s[-1] if t==0 or t>n: return False return s[-t:]==bytes([t]*t) def unpad(s): return s[:-s[-1]] def valid1(s): return checkpad(s,16) def valid2(s): return checkpad(s,8) def valid3(s): t=(string.ascii_letters+string.digits).encode() for i in s: if i not in t: return False return True def work(s): res=[] res2=[] if len(s)%16==0 and valid1(dec1(s)): res.append((unpad(dec1(s)),1)) if len(s)%8==0 and valid2(dec2(s)): res.append((unpad(dec2(s)),2)) if valid3(dec3(s)): res2.append(dec3(s)) return res,res2 def dfss(t,more,lvl): b=dfs(t,True) if more: for j in range(1,len(t)): x=dfss(t[:j],False,lvl) if len(x)==0: continue y=dfss(t[j:],True,lvl) for u in x: for v in y: b.append(u+(b'+' if lvl==1 else b'_')+v) return b def dfs(s,more): a,b=work(s) for t,lvl in a: b+=dfss(t,True,lvl) return b print(b'De1CTF{'+dfs(req,True)[-1]+b'}') ``` ## little_elves 动态调试，flag 被拿去做了很多次操作。每次操作 flag 中的一位被拿出，在一个 lfsr 中循环 8 次，再根据一些内置的数组决定要不要异或进去。把每一位的这些值全部异或起来，再拿去和另一个数比较，如果全部正确则返回 0。可以解析文件拿到这些数组和比较值的位置，然后高消。 ```python bin=open('little_elves','rb').read() s=[] cur=0 while True: cur=bin.find(b'\x8a\x97',cur+2) if cur==-1: break pos=int.from_bytes(bin[cur+2:cur+6],'little')-0x888000 m=bin[pos:pos+44] pos=bin.find(bin[0x117:0x11a],cur) assert bin[pos+5:pos+7]==b'\x81\xfb' or bin[pos+5:pos+7]==b'\x83\xfb' r=bin[pos+7] s.append((m,r)) N=44*8 M=44 def xor(a,b): return list(map(lambda x,y:x^y,a,b)) def xor2(a,b): return list(map(lambda x,y:xor(x,y),a,b)) def lfsr(x): res=[[0]*N]+x[:-1] t=x[-1] for i in range(8): if 0x39>>i&1: res[i]=xor(res[i],t) return res o=[] for mask,res in s: b=[[0 for k in range(N)]for j in range(8)] for i in range(M): c=[[i*8+j==k for k in range(N)]for j in range(8)] d=mask[i] for j in range(8): if d&1: b=xor2(b,c) c=lfsr(c) d>>=1 for i in range(8): o.append(b[i]+[res>>i&1]) s=o for i in range(N): t=i while not s[t][i]: t+=1 if t!=i: s[i],s[t]=s[t],s[i] for j in range(N): if j!=i and s[j][i]: s[j]=xor(s[j],s[i]) res=0 for i in range(M): t=0 for j in range(8): t+=s[i*8+j][N]<<j print(chr(t),end='') ```