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)