【WC2015】混淆与破解 （Goldreich-Levin 算法）

这个嘛= =直接贴VFK的题解就行了吧，感觉自己还是差别人太多

http://vfleaking.blog.uoj.ac/blog/104

讲得挺明白了的说，但还是挺难理解的说，中间实现部分简直不要太难懂= =（其实也不会代码顺序看正常点就行了）讲一下代码实现的细节吧（这点VFK就没说了~~~）

首先我们先随机生成很多个输入并把答案计算出来备用= =（计算答案时每32个输入进行一次运算用int来存就行了（想用bitset结果老调不出来QAQ））

然后就是算法的精髓了，生成s 个线性无关的向量 v1,…,vs，然后对于一个基，可以将其与这s个向量点积形成一个s维的向量，那么怎么求这个分量（就是一个可行的有效信息吧）呢?枚举每一个 U 中的向量 u，然后用“强制点积为 0”、“强制点积为 1” 这两种操作来把 f 变成只含 u 所对应的那个分量，再对 f 每一个输入变量反转下带进去看结果是否反转来知道这个分量中究竟含哪些变量。（VFK原话）这个我也不知道怎么说得清楚，看下代码理解下吧，反正我是看着看着就懂的QAQ，然后实现方面，我们可以先把该求的输入先预处理求出答案在进行计算，然后就能得到一个可能的分量了。

接下来呢，我们可以用一堆输入与这个分量进行比较来得到这个分量的系数，若这个系数较大就有可能是答案了（具体看wc ppt） 然后就得到一个有效信息了(当然，要与之前求得的线性无关)

接下来就容易了，用一堆输入求得每个输入对应的输出是0还是1（取概率较大的）就做完了

总体看起来也就是VFK用一句话说出来的东西比较难懂了（我比较渣QAQ）其他应该还可以理解

我把过程都注释到代码里了大家可以看看

然后就没了~~~

最近终于不堪于百度终于准备转博客园了，这是我在这里写的最后一篇博文了，翻翻一开始的文章，发现我变了很多，也挺有感触的，努力吧，相信成功只给有准备的人的！！！

CODE：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define R 10

#define S 4

int n,m,l,q;

#define maxk 50000

#define maxn 1030

#define pb push_back

int u[maxn],v[maxn],s[maxn],d[maxn],e[maxn];

typedef unsigned long long ull;

typedef unsigned int uint;

inline ull llrand() {

ull ans=(ull)rand()<<32|rand();

if (n<64) ans&=(1ull<<n)-1;

return ans;

}

vector<ull> x,ans;

vector<bool>x_res;

inline bool get(ull x,ull y){return x&(1ull<<y);}

inline void calc(vector<ull> &x,vector<bool> &res) {

res.clear();

static uint b[256];

for (int i=0;i<x.size();i+=32) {

memset(b,0,sizeof(b));

int r=min(int(x.size()-i),32);

for (int j=0;j<r;j++)

for (int k=0;k<n;k++) b[k]|=(ull)get(x[i+j],k)<<j;

for (int j=1;j<=q;j++) b[u[j]]=(~(b[v[j]]&b[s[j]]))^b[d[j]]^b[e[j]];

for (int j=0;j<r;j++) res.pb(get(b[0],j));

}

}

inline void set(ull &x,int y,int z) {

if (get(x,y)!=z) x^=1ull<<y;

}

inline void getans(){

static vector<ull> v,w;

int s=min(S,n);//生成s 个线性无关的向量

while (1) {

v.clear();w.clear();

bool flag=1;

for (int i=0;i<s;i++){

ull tmp=llrand();

v.pb(tmp);w.pb(tmp);

for (int j=0;j<i;j++)

if (w[i]&(w[j]&-w[j])) w[i]^=w[j];

if (!w[i]) {flag=0;break;}

}

if (flag) break;

}

static vector<ull> tx;

static vector<bool> tx_res;

tx.clear();//把该求的输入先预处理求出答案

for (int i=0;i<n;i++)

for (int j=0;j<R;j++) {

ull tmp=llrand();

for (int z=0;z<=1;z++) {

set(tmp,i,z);

for (int a=0;a<(1<<s);a++) {

ull temp=tmp;

for (int k=0;k<s;k++) if (a&(1<<k)) temp^=v[k];

tx.pb(temp);

}

}

}

calc(tx,tx_res);

for (int a=0;a<(1<<s);a++) {//枚举每一个 U 中的向量 u

ull tmp=0;

int l=0;

for (int i=0;i<n;i++) {//对 f 每一个输入变量反转下带进去看结果是否反转

int sum=0;

for (int j=0;j<R;j++) {

int cnt[2]={0,0};

for (int z=0;z<=1;z++)

for (int b=0;b<(1<<s);b++)

cnt[z]+=tx_res[l++]==__builtin_parity(a&b) ? 1: -1;

sum+=(cnt[0]>0)!=(cnt[1]>0);

}

if (sum>R/2) tmp|=1ull<<i;

}

int sum=0;

for (int i=0;i<maxk;i++) {//用一堆输入与这个分量进行比较来得到这个分量的系数

sum+=x_res[i]==__builtin_parityll(tmp&x[i])?1:-1;

}

if (abs(sum)>=maxk*0.02) {

for (int i=0;i<ans.size();i++)

if (tmp&(ans[i]&(-ans[i]))) tmp^=ans[i];

if (tmp) ans.pb(tmp);

}

}

}

int main(){

scanf("%d%d%d%d",&n,&m,&l,&q);

for (int i=1;i<=q;i++) scanf("%d%d%d%d%d",u+i,v+i,s+i,d+i,e+i);

for (int i=0;i<maxk;i++) x.pb(llrand());

calc(x,x_res);//随机生成很多个输入并把答案计算出来备用

while (ans.size()<m) getans();

for (int i=0;i<m;i++,putchar(‘\n’))

for (int j=0;j<n;j++) putchar(‘0’+get(ans[i],j));

static int h[1<<S][2];

for (int i=0;i<maxk;i++) {//一堆输入求得每个输入对应的输出是0还是1

ull tmp=0;

for (int j=0;j<m;j++) tmp=(tmp<<1) | __builtin_parityll(x[i]&ans[j]);

h[tmp][x_res[i]]++;

}

for (int i=0;i<(1<<m);i++) putchar(‘0’+(h[i][0]<h[i][1]));

return 0;

}