名词解释：什么是WAPI？（中国无线局域网安全强制性标准）

WAPI是WLAN Authentication and Privacy Infrastructure的英文缩写。它像红外线、蓝牙、GPRS、CDMA1X等协议一样，是无线传输协议的一种，只不过跟它们不同的是它是无线局域网（WLAN）中的一种传输协议而已，它与现行的802.11B传输协议比较相近。

那么，为什么制定传输协议的标准呢？我们知道，不同的传输协议将数据包在两台以上的电子设备间进行传输所用的原理和实现的手段是不同的，它们多数都不兼容，如果不制定无线传输协议的标准的话，无线电子设备的通用性就会受到很大的限制，例如，你的笔记本电脑在A地方也许可以无线上网，但去到了B地方，可能就会由于传输协议不统一而无法实现无线上网了，而如果所有的无线产品都使用同一种传输协议的话，那么，你的笔记本电脑无论走到哪里，只要有WLAN信号的地方都可以轻松实现无线上网了。

资料2：

中美谈判结果揭晓,WAPI无限延期

中美两国于美国当地时间星期三宣布，两国经过谈判，已就广泛的贸易与技术问题达成协定。根据协定，中方将缓和强制建立自己的Wi-Fi安全标准的做法，并且将采取更加严厉的防止盗版的政策。

　　据了解谈判过程的消息灵通人士透露，中方同意美方提出的要求，不在6月1日最后期限到来之时强制实施WAPI技术标准，并将无限期推迟实施WAPI技术标准的时间。与此同时，中方将与国际标准组织IEEE(电气与电子工程师协会)协作，对WAPI技术标准进行修改和完善。

　　根据双方达成的版权保护协定，中方将开展旨在打击以CD和其他载体为媒介的盗版行为的活动、支持司法机关对盗版者提起刑事诉讼并努力使中国的法律与国际间防止互联网盗版的版权保护公约接轨。

　　星期三宣布的协定有助于缓解中美之间因科技问题而出现紧张的商贸气氛。例如，WAPI问题就是此次中美之间爆发商贸争端的一个核心问题。

资料3：

#include "stdafx.h"
#include "basicmatcher.h"

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define STRING_NUM 10000

//素数(Prime Number)产生器，这里利用讲义中提供的7素数分类，而非自行产生
//PNM is short for "Prime Number Matrix"
namespace PNM{
 //不同范围内的素数矩阵
 int pnm[6][7]={
  {211,223,227,229,233,239,241},
  {461,463,467,479,487,491,499},
  {953,967,971,977,983,991,997},
  {4957,4967,4969,4973,4987,4993,4999},
  {9923,9929,9931,9941,9949,9967,9973},
  {100003,100019,100043,100049,100057,100069,100103}
 };

 //根据m、n的大小确定M，并随机抽取一个适当的素数
 //注意在全局调用前应使用srand((unsigned)time(NULL));
 int Generate(const CmpStrPair& csp){
  int m=csp.second.second,n=csp.first.second;
  int M=2*m*n*n;  //M=2*m*n*n
  int N=rand()%7;  //N为随机数(0<=N<=6)
  if(M>0 && M<=250) return pnm[0][N];
  else if(M>250 && M<=500) return pnm[1][N];
  else if(M>500 && M<=1000) return pnm[2][N];
  else if(M>1000 && M<=5000) return pnm[3][N];
  else if(M>5000 && M<=10000) return pnm[4][N];
  else return pnm[5][N];
 }
};

//计时器变量
clock_t start,step;
//计时结果
double total_time,run_time;

int _tmain(int argc, _TCHAR* argv[])
{
 //产生大于5000组的随机串
 CmpStrVector csv;
 Romdomizer rmd;
 for(int i=0;i<STRING_NUM;i++){
  rmd.Romdomize(csv);
 }
 
 //就上述产生的随机串进行各类匹配操作
 
 //KMP
 KMP kmp(csv[0]);
 start=clock();
 for(int i=0;i<STRING_NUM;i++){
  kmp.ReSet(csv[i]);
  kmp.FastFind();
 }
 step=clock();
 total_time=double(step-start)/CLOCKS_PER_SEC;
 run_time=total_time/STRING_NUM;
 cout<<"KMP Approach :"<<endl;
 cout<<"Total Time : "<<total_time<<endl
  <<"Run Time : "<<run_time<<endl<<endl
  <<"--------------------------------"<<endl<<endl;

 //Monte Carlo
 MonteCarlo mc(csv[0]);
 start=clock();
 for(int i=0;i<STRING_NUM;i++){
  mc.ReSet(csv[i]);
  mc.Compare(PNM::Generate(csv[i]));
 }
 step=clock();
 total_time=double(step-start)/CLOCKS_PER_SEC;
 run_time=total_time/STRING_NUM;
 cout<<"Monte Carlo Approach :"<<endl;
 cout<<"Total Time : "<<total_time<<endl
  <<"Run Time : "<<run_time<<endl<<endl
  <<"--------------------------------"<<endl<<endl;
 
 //Las Vegas
 LasVegas lv(csv[0]);
 start=clock();
 for(int i=0;i<STRING_NUM;i++){
  lv.ReSet(csv[i]);
  lv.Compare(PNM::Generate(csv[i]));
 }
 step=clock();
 total_time=double(step-start)/CLOCKS_PER_SEC;
 run_time=total_time/STRING_NUM;
 cout<<"Las Vegas Approach :"<<endl;
 cout<<"Total Time : "<<total_time<<endl
  <<"Run Time : "<<run_time<<endl<<endl
  <<"--------------------------------"<<endl<<endl;

 cout<<"Monte Carlo Approach's Mistake-Rate Is :"
  <<1-float(lv.match_num)/float(mc.match_num)<<endl;
 
 return 0;
}

//Utility.h : 辅助工具的定义

#include<iostream>
#include<string>
#include<bitset>
#include<limits>
#include<vector>
#include<utility>

using namespace std;

//程序中用到的一些预定义和函数
namespace def{
 //比特流原型，包含了比特流的数值信息
 typedef bitset<numeric_limits<unsigned long>::digits> Bits;
 //比特流模拟串：后项为串实际长度（前截断）
 typedef pair<Bits,unsigned int> BitString;
 //比较串对：前项为源串，后项为目标串
 typedef pair<BitString,BitString> CmpStrPair;
 //比较串对向量：用来存储已经生成的比较串对序列
 typedef vector<CmpStrPair> CmpStrVector;
 //打印比特串BitString
 ostream& operator << (ostream& os,BitString& b_str);
};

using namespace def;

//随机数列产生器类
class Romdomizer{
public:
 Romdomizer();
 //将生成的比较串对送到待处理序列中
 void Print(ostream& os=cout){
  os<<"Source : "<<source<<endl
    <<"Target : "<<target<<endl;
 }
 bool Romdomize(CmpStrVector&);
 void Romdomize();  //随机生成新比较串对
private:
 void Create(long& v,unsigned int& s,bool isSource); //随机产生比特串的必要构成：v,比特串值、s：比特串长

 BitString source;  //比较源串X：x1,...,xn
 BitString target;  //比较目标串Y：y1,...,ym
};

//Utility.cpp : 辅助工具的实现

#include "stdafx.h"
#include "Utility.h"

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

//---------------------------------------------------------------------------------------------

namespace def{
 ostream& operator << (ostream& os,BitString& b_str){
  for(int i=b_str.second-1;i>=0;i--)
   os<<b_str.first[i];
  return os;
 }
};

//---------------------------------------------------------------------------------------------

Romdomizer::Romdomizer(){
 //根据时间设置随机
 srand((unsigned)time(NULL));
}

void Romdomizer::Create(long& v,unsigned int& s,bool isSource){
 //串长度的最大值（目标串的最大长度应为源串的长度，根据isSource是否成真确定是否为源串）
 size_t size_max;
 long value_max=1;  //根据随即产生的串长度决定串值可能取的最大值
 
 //计算串长度的最大值
 if(isSource){
  size_max=numeric_limits<unsigned long>::digits;
 }
 else
  size_max=static_cast<size_t>(3*s/4+1);//为了增加成功率，假设目标串较短，长度不到源串3/4
 //产生随机串长度
 s=rand()%size_max+1;
 //根据串长计算串值的最大值
 for(int i=static_cast<int>(s);i>0;i--)
  value_max*=2;
 value_max--;
 //产生随机串值
 v=value_max*(float(rand())/float(RAND_MAX));
}

void Romdomizer::Romdomize(){
 long t_value=0;   //临时串值
 unsigned int t_size=0; //临时串长度
 //随机生成源串
 Create(t_value,t_size,true);
 source=make_pair(Bits(t_value),t_size);
 //随机生成目标串
 Create(t_value,t_size,false);
 target=make_pair(Bits(t_value),t_size);
}

bool Romdomizer::Romdomize(CmpStrVector& v){
 if(v.size()<v.max_size()){
  Romdomize();
  CmpStrPair t_p(source,target);
  v.push_back(t_p);
  return true;
 }
 return false;
}

// BasicMatcher.h : 基本匹配函数的定义

#include "Utility.h"

//说明：这里使用BitString特殊表现形式，以下方法采用反向匹配机制
//即ym,...,y1与xn,...,x1匹配，如果成功，则原先的正向串也必然匹配
//反之，则原先的正向串必然不匹配

class KMP{
public:
 KMP(CmpStrPair& csp):p_source(&csp.first),p_target(&csp.second){
  for(int i=0;i<numeric_limits<unsigned long>::digits;i++)
   fail[i]=-2;
  Fail();
 }
 inline void ReSet(CmpStrPair& csp){
  p_source=&csp.first;
  p_target=&csp.second;
  for(int i=0;i<numeric_limits<unsigned long>::digits;i++)
   fail[i]=-2;
  Fail();
 }
 int FastFind();     //KMP的主匹配函数
private:
 void Fail();     //失效函数
 BitString* p_source;   //源串的引用
 BitString* p_target;   //目标串的引用
 int fail[numeric_limits<unsigned long>::digits];
};

class MonteCarlo{
public:
 MonteCarlo(CmpStrPair& csp):p_source(&csp.first),p_target(&csp.second),match_num(0){;}
 inline void ReSet(CmpStrPair& csp){
  p_source=&csp.first;
  p_target=&csp.second;
 }

 //Monte Carlo的匹配主函数
 //p:随机产生的素数
 int Compare(int p);
 int match_num;
private:
 BitString* p_source;   //源串的引用
 BitString* p_target;   //目标串的引用
};

class LasVegas{
public:
 LasVegas(CmpStrPair& csp):p_source(&csp.first),p_target(&csp.second),match_num(0){;}
 inline void ReSet(CmpStrPair& csp){
  p_source=&csp.first;
  p_target=&csp.second;
 }

 //Last Vegas的匹配主函数
 //p:随机产生的素数
 bool Verify(int pos);
 int Compare(int p);
 int match_num;
private:
 BitString* p_source;   //源串的引用
 BitString* p_target;   //目标串的引用
};

//BasicMatcher.cpp : 基本匹配函数的实现

#include "stdafx.h"
#include "BasicMatcher.h"

void KMP::Fail(){
 int length=p_target->second;
 fail[0]=-1;
 for(int j=1;j<length;j++){
  int i=fail[j-1];
  while(p_target->first[j]!=p_target->first[i+1] && i>=0) i=fail[i];
  if(p_target->first[j]==p_target->first[i+1]) fail[j]=i+1;
  else fail[j]=-1;
 }
}

int KMP::FastFind(){
 int posS=0,posT=0;
 int lenS=p_source->second,lenT=p_target->second;
 while(posT<lenT && posS<lenS)
  if(p_target->first[posT]==p_source->first[posS]){
   posT++;
   posS++;
  }
  else if(posT==0) posS++;
  else posT=fail[posT-1]+1;
 if(posT<lenT)
  return 0;
 else return posS-lenT+1;//方向匹配结果
}

int MonteCarlo::Compare(int p){
 int n=p_source->second,m=p_target->second;
 int j=0;
 int temp=1;  //用以求得2的m次方
 for(int i=0;i<m;i++)
  temp*=2;
 int Wp=temp % p;
 //求源串指纹
 //先求以X0开头m位的数值value作为递推的起点;
 long value=0;
 for(int i=0;i<m;i++){
  value*=2;
  int bit=p_source->first[i]?1:0;
  value+=bit;
 }
 int Ipx=value % p;
 int Ipy=p_target->first.to_ulong() % p; //求目标串指纹
 while(j<n-m){
  if(Ipx==Ipy){
   match_num++;
   return j+1;
  }
  //根据公式计算Ipx
  int t1=p_source->first[j]?1:0;
  int t2=p_source->first[j+m]?1:0;
  Ipx=(2*Ipx+t1*Wp+t2) % p;
  j++;
 }
 return 0;
}

bool LasVegas::Verify(int pos){
 for(int i=0;i<p_target->second;i++){
  if(p_target->first[i]!=p_source->first[pos+i])
   return false;
 }
 return true;
}

int LasVegas::Compare(int p){
 int n=p_source->second,m=p_target->second;
 int j=0;
 int temp=1;  //用以求得2的m次方
 for(int i=0;i<m;i++)
  temp*=2;
 int Wp=temp % p;
 long value=0;
 for(int i=0;i<m;i++){
  value*=2;
  int bit=p_source->first[i]?1:0;
  value+=bit;
 }
 int Ipx=value % p;
 int Ipy=p_target->first.to_ulong() % p; //求目标串指纹
 while(j<n-m){
  //加入了验证环节
  if(Ipx==Ipy && Verify(j)) {
   match_num++;
   return j+1;
  }
  //根据公式计算Ipx
  int t1=p_source->first[j]?1:0;
  int t2=p_source->first[j+m]?1:0;
  Ipx=(2*Ipx+t1*Wp+t2) % p;
  j++;
 }
 return 0;
}