-
-
[旧帖] 动态规划用于加密初探（1）（2） 0.00雪花
-
发表于: 2010-3-4 12:21
-
|
|
|---|---|
|
|
|
|
|
2.使用LIS的算法太简单，O(n^2)的DP，哪怕是反汇编也一眼就看完了，建议可以改进成O(nlogn)的LIS算法(有DP和贪心两种)。并且可以考虑把LIS计算过程中的方案也求出来，并用到加密上，就会强大许多。
----------------------这个学习了。----------------  您们搞破解，我来学加密。
/*
Name: 动态规划用于软件加密初探（2）
Copyright: @Green Tsai
Author: Green Tsai
Date: 04-03-10 13:09
Description:
1，思路与思想：本程序试图将动态规划算法用于软件加密，主要涉及动态规划中的字符串编辑距离与相似度判定。
2，本程序中的编辑代价函数与相似度判定函数均可调整来增加加密强度与逆向难度。
3，示例姓名：kanxue,序列号：90yxop。
参考文档：《挑战编程》 Steven S.Skiena著 刘汝佳 译
*/
#include <cstdlib>
#include <iostream>
using namespace std;
#define MAXLEN 35
#define MATCH 0 // enumerated type symbol for match
#define INSERT 1
#define DELETE 2
typedef struct
{
int cost; // cost of reaching this cell
int parent; // parent cell
}cell;
cell m[MAXLEN+1][MAXLEN+1]; // dynamic programming table
// 代价函数
int match(char c,char d);
int indel(char c);
// 初始化与目标格
void row_init(int i);
void column_init(int i);
void goal_cell(char *s,char *t,int *i,int *j);
// 编辑距离
int string_compare(char *s,char *t);
// 相似度判定
bool same(char *s,char *t);
int main()
{
bool ok=false;
while(ok==false)
{
char name[31],serial[31];
name[0]=serial[0]='!';
cout<<"Please input your name:"<<endl;
cin>>&name[1];
cout<<"Please input your serial number:"<<endl;
cin>>&serial[1];
// cout<<strlen(name)<<" "<<strlen(serial)<<endl;
// cout<<string_compare(name,serial)<<endl;
if( strlen(name)>=4 && ( strlen(name)==strlen(serial) ) && same(name,serial) && string_compare(name,serial)==5 )
{
ok=true;
cout<<"Congratulations!"<<endl;
cout<<endl;
}
else
{
cout<<"Sorry!"<<endl;
cout<<endl;
}
}
system("PAUSE");
return 0;
system("PAUSE");
return 0;
}
int match(char c,char d)
{
if(c==d)
return 0;
else
return 1;
}
int indel(char c)
{
return 1;
}
void row_init(int i)
{
m[0][i].cost=i;
if(i>0) m[0][i].parent=INSERT;
else m[0][i].parent=-1;
}
void column_init(int i)
{
m[i][0].cost=i;
if(i>0)
m[i][0].parent=DELETE;
else
m[0][i].parent=-1;
}
void goal_cell(char *s,char *t,int *i,int *j)
{
*i=strlen(s)-1;
*j=strlen(t)-1;
}
int string_compare(char *s,char *t)
{
int i,j,k; // counter
int opt[3]; // cost of the three options
for(i=0;i<MAXLEN;i++)
{
row_init(i);
column_init(i);
}
for(i=1;i<strlen(s);i++)
{
for(j=1;j<strlen(t);j++)
{
opt[MATCH]=m[i-1][j-1].cost+match(s[i],t[j]);
opt[INSERT]=m[i][j-1].cost+indel(t[j]);
opt[DELETE]=m[i-1][j].cost+indel(s[i]);
m[i][j].cost=opt[MATCH];
m[i][j].parent=MATCH;
for(k=INSERT;k<=DELETE;k++)
{
if(opt[k]<m[i][j].cost)
{
m[i][j].cost=opt[k];
m[i][j].parent=k;
}
}
}
}
goal_cell(s,t,&i,&j);
return m[i][j].cost;
}
bool same(char *s,char *t)
{
// 相似度小于50%,返回true
int count=0;
for(int i=1;i<strlen(s);i++)
{
if(s[i]==t[i])
count++;
}
if(count<=strlen(s)/2)
return true;
else
return false;
}
|
|
|
|
|
|
|
|
|
这么大的秘密，竟然被你看出来了。。。
早知道我把编辑代价和相似度搞的复杂点了。。。
|
