dpa算法
A. 关于密码算法的翻译
2.3设计Keccak式排列
设计标准为Keccak式排列是没有任何性能，可
利用捷径攻击中所用海绵建设。这是构建
作为一个迭代分组密码类似Noekeon [ 22 ]和Rijndael算法[ 23 ] ，关键时间表
取代一些简单的轮常数。在这里，我们给出的理由，其特点：
位为导向的结构攻击的钻头进行分组（例如，以字节为单位） ，如积分
密码分析和截断径或dierentials ，不适合对我们的结构。
位逻辑运算和混合轮换依赖CPU的字长是唯一
由于轮调，导致电子商务？系数使用的CPU资源，就广泛的处理器。
实施要求没有大的桌子，消除危险，表查找
基于缓存小姐攻击。他们可以编程为混合序列的指示，
提供保护，防止时间攻击。
对称性这使得有非常紧凑的代码软件（见第7.3 ）和一个非常
紧凑型协处理器电路（见第7.4.3 ）适合的环境。
并行由于其对称性和所选择的行动，设计非常适合
超快速的硬件实现和剥削的SIMD指令和
流水线处理器。
2回合程度分析，这使得对dierential和线性密码分析
容易导致相对简单（虽然大）系统的代数方程，并
允许使用的非常强大的保护措施，防止dierential功率分析
（政治部）在软件（见第7.3.4 ）和硬件（见第7.4.4 ） 。
Matryoshka结构的分析小版本有关的较大的版本（见
第5.2节） 。
在另一个篮子鸡蛋的选择和行动是非常dierent由在SHA - 1和
成员沙- 2家族一方面从AES公司的其他
B. 编辑距离问题的动态规划算法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int _Min(int a,int b,int c)
{
int min=a;
if (b <min)
min=b;
if(c <min)
min=c;
return min;
}
int ComputeDistance(char s[],char t[])
{
int n = strlen(s);
int m = strlen(t);
//int d[][] = new int[n + 1, m + 1]; // matrix
int **d = (int **)malloc((n+1) * sizeof(int *));
for(int i=0; i<=n; ++i)
{
d[i] = (int *)malloc((m+1) * sizeof(int));
}
// Step 1
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
// Step 2
for (int i = 0; i <= n; i++)
{
d[i][0] =i;
}
for (int j = 0; j <= m; d[0][j] = j++)
{
d[0][j] =j;
}
// Step 3
for (int i = 1; i <= n; i++)
{
//Step 4
for (int j = 1; j <= m; j++)
{
// Step 5
int cost = (t[j-1] == s[i-1]) ? 0 : 1;
// Step 6
d[i][j] = _Min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+cost);
}
}
// Step 7
return d[n][m];
}
int main(int argc, char *argv[])
{
char a[9999];
char b[9999];
printf("请输入字符串1\n");
scanf("%s",&a);
printf("请输入字符串2\n");
scanf("%s",&b);
int result= ComputeDistance(a,b);
printf("%d\n",result);
system("PAUSE");
return 0;
}
////////////////////
Refrence : Dynamic Programming Algorithm (DPA) for Edit-Distance
编辑距离
关于两个字符串s1,s2的差别，可以通过计算他们的最小编辑距离来决定。
所谓的编辑距离: 让s1和s2变成相同字符串需要下面操作的最小次数。
1. 把某个字符ch1变成ch2
2. 删除某个字符
3. 插入某个字符
例如 s1 = “12433” 和s2=”1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即 d(s1,s2) = 1 (进行了一次插入操作)
编辑距离的性质
计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质:
1. d(s1,””) = d(“”,s1) = |s1| d(“ch1”,”ch2”) = ch1 == ch2 ? 0 : 1;
2. d(s1+ch1,s2+ch2) = min( d(s1,s2)+ ch1==ch2 ? 0 : 1 ,
d(s1+ch1,s2),
d(s1,s2+ch2) );
第一个性质是显然的。
第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法。
于是对ch1,ch2可能的操作只有
1. 把ch1变成ch2
2. s1+ch1后删除ch1 d = (1+d(s1,s2+ch2))
3. s1+ch1后插入ch2 d = (1 + d(s1+ch1,s2))
对于2和3的操作可以等价于:
_2. s2+ch2后添加ch1 d=(1+d(s1,s2+ch2))
_3. s2+ch2后删除ch2 d=(1+d(s1+ch1,s2))
因此可以得到计算编辑距离的性质2。
复杂度分析
从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记，并假设两个串长度都为 n )
可以看到，该问题的复杂度为指数级别 3 的 n 次方，对于较长的串，时间上是无法让人忍受的。
分析: 在上面的结构中，我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。
动态规划求解
首先为了避免重复计算子问题，添加两个辅助数组。
一. 保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
二. 保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s[i] = s[j] ? 0 : 1
三. 新的计算表达式
根据性质1得到
M[ 0,0] = 0;
M[ s1i, 0 ] = |s1i|;
M[ 0, s2j ] = |s2j|;
根据性质2得到
M[ i, j ] = min( m[i-1,j-1] + E[ i, j ] ,
m[i, j-1] ,
m[i-1, j] );
复杂度
从新的计算式看出，计算过程为
i=1 -> |s1|
j=1 -> |s2|
M[i][j] = ……
因此复杂度为 O( |s1| * |s2| ) ，如果假设他们的长度都为n，则复杂度为 O(n^2)