分類：書籍筆記

完美實戰安全性演算法

對於資訊安全而言，很難有一個十分嚴謹而明確的定義或標準。簡單來說，資訊安全(Information Security)的基本功能就是必須具備以下四種特性：

*秘密性(confidentiality)：表示交易相關資料必須保密，當資料傳遞時，確保資料在網路上傳送不會遭截取、窺竊而洩漏資料內容，除了被授權的人，在網路上不怕被攔截或偷窺，而損害其秘密性。
*完整性(integrity)：表示當資料送達時必須保證資料沒有被竄改的疑慮，訊息如遭竄改時，該筆訊息就會無效，例如由甲端傳至乙端的資料有沒有被竄改，乙端在收訊時，立刻知道資料是否完整無誤。
*認證性(authentication)：表示當傳送方送出資料時，就必須能確認傳送者的身分是否為冒名，例如傳送方無法冒名傳送資料，持卡人、商家、發卡行、收單行和支付閘道，都必須申請數位憑證進行身分識別。
*不可否認性(non-repudiation)：表示保證使用者無法否認他所完成過之資料傳送行為的一種機制，必須不易被複製及修改，就是指無法否認其傳送或接受訊息行為，例如收到金錢不能推說沒收到；同樣前用掉不能推收遺失，不能否認其未使用過。

11-1 輕鬆學會資料加密

將資料轉換成不具任何意義的代碼，而這個處理過程就是(加密Encrypt)。資料再加密前稱為(明文 Plain text)，經過加密後則稱為(密文 Cipher text)。
經過加密的資料在送抵目的端後，必須經過(解密 Decrypt)程序，才能將資料還原成原來的內容，而這個加/解密的機制則稱為(金鑰Key)。至於資料加密及解密的流程如下所示：

11-1-1 對稱鍵值加密系統

對稱鍵值機加密系統(Symmetrical key Encryption)又稱為單一鍵值加密系統(Single key Encryption)或秘密金鑰系統(Secret Key)。這種加密系統的運作方式，是由資料傳送者利用祕密金鑰(Secret Key)將文件加密，使文件成為一堆的亂碼後，再加以傳送。而接受者收到這個經過加密的密文後，再使用相同的祕密金鑰，將文件還原成原來的模樣。因為如果者B用這一組密碼解開文件，那麼就能確定這份文件是由使用者A加密後傳送過去，如下圖所示：

這種加密系統的運作方式較為單純，因此不論在加密及解密上的處理速度都相當快速。常見的對稱鍵值加密系統演算法有DES(Data Encryption Standard，資料加密標準)、Triple DES、IDEA(Internation Data Encryption Algorithm，國際資料加密演算法)等。

11-1-2非對稱鍵值加密系統與RSA演算法

(非對稱性加密系統)是目前較為普遍，也是金融界應用上最安全的加密系統，或稱為(雙鍵加密系統 Double key Encryption)，這種加密系統主要的運作方式，是以兩把不同的金鑰(key)來對文件進行加/解密。例如使用者A要傳送一份新的文件給文件使用者B，使用者A會利用使用者B的公開金鑰來加密，並將祕文傳送給使用者B。當使用者收到密文後，再利用自己的私密金鑰解密。如下圖所示：

例如RSA(Rivest-Shamir-Adleman)是加密演算法中是一種非對稱加密演算法，在RSA演算法之前，加密方法幾乎都是對稱型的，非對稱是因為它利用兩個不同的鑰匙，一把叫公開金鑰，另外一把較私密金鑰。1977年由Ron Rivest、Adi Shamir 和 Leonard Adleman 一起提出的，RSA就是由三人姓氏開頭字母所組成。

11-2 一學就懂得雜湊演算法

雜湊法是利用雜湊函數來計算一個鍵值所對應的位址，進而建立雜湊表格，且依賴雜湊函數來搜尋找到個鍵值存放在表格中的位址，搜尋速度與資料多少無關，在沒有碰撞和溢位下，一次讀取即可，更包括保密性高，因為不事先知道雜湊函數就無法搜尋的優點。
選擇雜湊函數時，要特別注意不宜過於複雜，設計原則上至少必須符合計算速度快與碰撞頻率盡量小兩項特點。常見的雜湊法有除法、中間平方法、摺疊法及數位分析法。

11-2-1  除法

最簡單的雜湊法是將資料除以某一個常數後，取餘數來當索引。例如在一個有13個位置的陣列中，只使用到7個位址，值分別是12,65,70,99,33,67,48。那我們就可以把陣列內的值除以13，並以其餘數來當索引，我們可以用下例式子來表示：

h(key)=key mod B

在這個例子中，我們所使用的B=13。一般而言，會建議各位在選擇B時，B最好是質數。而上例所建立出來的雜奏表如所示：

以下我們將用除法作為雜湊函數，將下列數字儲存在11空間：323,458,340,28,969,77，請問其雜湊表外觀為何？
令雜湊函數為h(key)=key mod B，其中B=11為一質數，這個函數的計算結果介於0-10之間(包括0及10二數)，則h(323)=4、h(458)=7、h(25)=3、h(340)=10、h(28)=6、h(969)=1、h(77)=0。

11-2-2 中間平方法

中間平方法和除法相當類似，它是把資料乘以自己，之後再取中間的某段數字做索引。在下例中我們用中間平方法，並將它放在100個位址空間，其操作步驟如下：

1. 將12,65,70,99,33,67,51平方後如下：

144,4225,4900,9801,1089,4489,2601

2.我們取百位數及十位數作為鍵值，分別為：

14,22,90,80,08,48,60

上述這7個數字的數列就是對應原先12,65,70,99,33,67,51等7個數字存放在100個位址空間的索引鍵值，即

f(14)=12
f(22)=65
f(90)=70
f(80)=99
f(08)=33
f(48)=67
f(60)=51

10-5-2 Folyd演算法

由於Dijkstra的方法只能求出某一點到其他頂點的最短距離，如果要求圖形中任意兩點甚至所有頂點間最短距離，就必須使用Floyd演算法。

Folyd演算法定義：

這樣看起來似乎覺得Floyd演算法相當複雜難懂，我們將直接以實例說明它的演算法則。例如試以Floyd演算法求得各頂點間的最短路徑：

完成：所有頂點間的最短路徑為矩陣A3所示。

由上例可知，一個加權圖形若有n個頂點，則此方法必須執行n次迴圈，逐一產生A1,A2,A3,……….Ak個矩陣。但因Folyd演算法較為複雜，讀者也可以用上一小節所討論的Dijlstra演算法，依序以各頂點為起始頂點，如此一來可以得到相同結果。

JS                 floyd.js

const SIZE=7;
const NUMBER=6;
const INFINITE=99999;
var Graph_Matrix=[[0,0,0,0,0,0,0],
					[0,0,0,0,0,0,0],
					[0,0,0,0,0,0,0],
					[0,0,0,0,0,0,0],
					[0,0,0,0,0,0,0],
					[0,0,0,0,0,0,0],
					[0,0,0,0,0,0,0]];
var distance=[];
for (let i=0; i<SIZE; i++) {
	distance[i]=new Array();
	for (let j=0; j<SIZE; j++)
		distance[i][j]=0;
}

var BuildGraph_Matrix=(Path_Cost)=> {
	for (let i=1; i<SIZE; i++) {
		for (let j=1; j<SIZE; j++) {
			if (i==j)
				Graph_Matrix[i][j]=0;
			else
				Graph_Matrix[i][j]=INFINITE;
		}
	}
	let i=0;
	while (i<SIZE) {
		Start_Point=Path_Cost[i][0];
		End_Point=Path_Cost[i][1];
		Graph_Matrix[Start_Point][End_Point]=Path_Cost[i][2];
		i+=1;
	}
}

var shortestPath=(vertex_total)=> {
	for (let i=1; i<vertex_total+1; i++) {
		for (let j=1; j<vertex_total+1; j++) {
			distance[i][j]=Graph_Matrix[i][j];
			distance[j][i]=Graph_Matrix[j][i];
		}
	}

	for (let k=1; k<vertex_total+1; k++) {
		for (let i=1; i<vertex_total+1; i++) {
			for (let j=1; j<vertex_total+1; j++) {
				if (distance[i][k]+distance[k][j]<distance[i][j])
					distance[i][j]=distance[i][k]+distance[k][j];
			}
		}
	}
}

Path_Cost=[[1,2,20],[2,3,30],[2,4,25],
			[3,5,28],[4,5,32],[4,6,95],[5,6,67]];
BuildGraph_Matrix(Path_Cost);
process.stdout.write('========================================\n');
process.stdout.write('  所有頂點兩兩之間的最短距離： \n');
process.stdout.write('========================================\n');
shortestPath(NUMBER);
process.stdout.write('\t頂點1\t頂點2\t頂點3\t頂點4\t頂點5\t頂點6\n');
for (let i=1; i<NUMBER+1; i++) {
	process.stdout.write('頂點'+i+'\t');
	for (let j=1; j<NUMBER+1; j++) {
		process.stdout.write(distance[i][j]+'\t');
	}
	process.stdout.write('\n');
}
process.stdout.write('=========================================\n');

範例程式有問題！
上半部是跟書一樣，下半部跟書不一樣

10-4-2 Kruskal 演算法

Kruskal 演算法是將各邊緣線依權值大小由小到大排列，接著從權值最低的邊緣開始架構最小成本擴張樹，如果加入的邊線會造成迴路則捨棄不用，直到加入了n-1個邊線為止。

這方法看起來似乎不難，我們直接來看如何以K氏法得到範例下圖中最小成本擴張樹：

步驟一： 把所有邊線的成本列出並由小到大排序。

步驟二： 選擇成本最低的一條邊線作為架構最小成本擴張樹的起點。

步驟三： 依步驟一所建立的表格，依序加入邊線。

步驟四： C-D加入會形成迴路，所以直接跳過。

完成圖

Kruskal 法的演算法

const VERTS=6;
class edge {
	constructor() {
		this.start=0;
		this.to=0;
		this.find=0;
		this.val=0;
		this.next=null;
	}
}

v=[];
for (let i=0; i<VERTS+1; i++) v[i]=0;
var findmincost=(head)=> {
	minval=100;
	let ptr=head;
	while (ptr!=null) {
		if (ptr.val<minval && ptr.find==0) {
			minval=ptr.val;
			retptr=ptr;
		}
		ptr=ptr.next;
	}
	retptr.find=1;
	return retptr;
}
var mintree=(head)=> {
	let result=0;
	let ptr=0;
	for (let i=0; i<VERTS; i++)
		v[i]=0;
	while (ptr!=null) {
		mceptr=findmincost(head);
		v[mceptr.start]=v[mceptr.start]+1;
		v[mceptr.to]=v[mceptr.to]+1;
		if (v[mceptr.start]>1 && v[mceptr.to]>1) {
			v[mceptr.start]=v[mceptr.start]-1;
			v[mceptr.to]=v[mceptr.to]-1;
			result=1;
		}
		else
			result=0;
		if (result==0) {
			process.stdout.write('起點頂點 ['+mceptr.start+'] -> 終止頂點 [' + mceptr.to+'] -> 路徑長度 ['+mceptr.val+']\n');
		}
		ptr=ptr.next;
	}
}

JS                  kruskal.js

const VERTS=6;
class edge {
	constructor() {
		this.start=0;
		this.to=0;
		this.find=0;
		this.val=0;
		this.next=null;
	}
}

v=[];
for (let i=0; i<VERTS+1; i++) v[i]=0;
var findmincost=(head)=> {
	minval=100;
	let ptr=head;
	while (ptr!=null) {
		if (ptr.val<minval && ptr.find==0) {
			minval=ptr.val;
			retptr=ptr;
		}
		ptr=ptr.next;
	}
	retptr.find=1;
	return retptr;
}
var mintree=(head)=> {
	let result=0;
	let ptr=head;
	for (let i=0; i<VERTS; i++)
		v[i]=0;
	while (ptr!=null) {
		mceptr=findmincost(head);
		v[mceptr.start]=v[mceptr.start]+1;
		v[mceptr.to]=v[mceptr.to]+1;
		if (v[mceptr.start]>1 && v[mceptr.to]>1) {
			v[mceptr.start]=v[mceptr.start]-1;
			v[mceptr.to]=v[mceptr.to]-1;
			result=1;
		}
		else
			result=0;
		if (result==0) {
			process.stdout.write('起點頂點 ['+mceptr.start+'] -> 終止頂點 [' +
				mceptr.to+'] -> 路徑長度 ['+mceptr.val+']\n');
		}
		ptr=ptr.next;
	}
}

data=[[1,2,6],[1,6,12],[1,5,10],[2,3,3],
		[2,4,5],[2,6,8],[3,4,7],[4,6,11],
		[4,5,9],[5,5,16]];
var head=null;
for (i=0; i<10; i++) {
	for (j=1; j<=VERTS+1; j++) {
		if (data[i][0]==j) {
			newnode=new edge();
			newnode.start=data[i][0];
			newnode.to=data[i][1];
			newnode.val=data[i][2];
			newnode.find=0;
			newnode.next=null;
			if (head==null) {
				head=newnode;
				head.next=null;
				ptr=head;
			}
			else {
				ptr.next=newnode;
				ptr=ptr.next;
			}
		}
	}
}

process.stdout.write('--------------------------------------------------\n');
process.stdout.write('建立最小成本擴張樹：\n');
process.stdout.write('--------------------------------------------------\n');
mintree(head);

10-5 圖形最短路徑演算法

在一個有向圖形G=(V,E)，G中每一個邊都有一個比例常數W(Weight)與之對應，如果想求G圖形中某一個頂點V0到其他頂點的最少W總和之值，這類問題就稱為最短路徑問題(The Shortest Path Problem)。由於交通運輸工具的便利與普及，所以兩地之間有發生運送或者資訊的傳遞下，最短路徑(Shortest Path)的問題隨時都可能因應需求而產生，簡單來說，就是找出兩個端點間可行的捷徑。

我們在上捷中所說明的花費最少擴張樹(MST)，是計算聯繫網路中每一個頂點所需的最少花費，但連繫樹中任何倆頂點的路徑不一定是一條花費最少的路徑，這也是本節將研究最短路徑問題的主要理由。以下是在討論最短路徑常見的演算法。

10-5-1 Dijlstra 演算法與A*演算法

從上述的演算法我們可以推演出如下步驟：

由頂點5到其他各頂點的最短距離為：
頂點5-頂點0：26
頂點5-頂點1：12
頂點5-頂點2：18
頂點5-頂點3：20
頂點5-頂點4：14

JS                     dijkstra.js

const SIZE=7;
const NUMBER=6;
const INFINITE=99999; //無窮大
var Graph_Matrix=[[0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0]];
var distance=[];
for (let i=0; i<SIZE; i++) distance[i]=0;

var BuildGraph_Matrix=(Path_Cost)=> {
	for (let i=1; i<SIZE; i++) {
		for (let j=1; j<SIZE; j++) {
			if (i==j)
				Graph_Matrix[i][j]=0;
			else
				Graph_Matrix[i][j]=INFINITE;
		}
	}
	i=0;
	while (i<SIZE) {
		Start_Point=Path_Cost[i][0];
		End_Point=Path_Cost[i][1];
		Graph_Matrix[Start_Point][End_Point]=Path_Cost[i][2];
		i+=1;
	}
}

var shortestPath=(vertexl, vertex_total)=> {
	let shortest_vertex=1;
	let goal=[];
	for (let i=1; i<vertex_total+1; i++) {
		goal[i]=0;
		distance[i]=Graph_Matrix[vertexl][i];
	}
	goal[vertexl]=1;
	distance[vertexl]=0;
	process.stdout.write('\n');

	for (let i=1; i<vertex_total; i++) {
		shortest_distance=INFINITE;
		for (let j=1; j<vertex_total+1; j++) {
			if (goal[j]==0 && shortest_distance>distance[j]) {
				shortest_distance=distance[j];
				shortest_vertex=j;
			}
		}
		goal[shortest_vertex]=1;

		for (let j=1; j<vertex_total+1; j++) {
			if (goal[j]==0 && 
				distance[shortest_vertex]+Graph_Matrix[shortest_vertex]
											[j]<distance[j]){
				distance[j]=distance[shortest_vertex]+Graph_Matrix[shortest_vertex][j];
			}
		}
	}
}

Path_Cost=[[1,2,29],[2,3,30],[2,4,35],
			[3,5,28],[3,6,87],[4,5,42],
			[4,6,75],[5,6,97]];
BuildGraph_Matrix(Path_Cost);
shortestPath(1,NUMBER);
process.stdout.write('------------------------------\n');
process.stdout.write('頂點1到各頂點最短距離的最終結果\n');
process.stdout.write('------------------------------\n');
for (let j=1; j<SIZE; j++) {
	process.stdout.write('頂點1到頂點'+j+'的做短距離='+distance[j]+'\n');
}
process.stdout.write('------------------------------\n');