hill演算法

Ⅰ 為什麼說加法密碼、乘法密碼、仿射密碼、置換密碼、Hill密碼以及Vigenere密碼

加法密碼就是真典密碼學中的愷撒密碼格式是：密文=(明文+密鑰)mod26,剩法密碼是愷撒密碼發展出來，格式是：密文=明文x實鑰mon26；置換密碼就是在簡單的縱行換位密碼中，明文以固定的寬度水平的寫在一張圖表紙上，密文按垂直方向讀出，解密就是密文按相同的寬度垂直的寫在圖表紙上，然後水平的讀出明文。希爾密碼（Hill Cipher）是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果MOD26；Vigenere是愷撒密碼演變而來。使用一系列凱撒密碼組成密碼字母表的加密演算法，屬於多表密碼的一種簡單形式。
有興趣可以了解一下古典密碼學，這裡面都有。

Ⅱ 希爾密碼原理

希爾密碼（Hill Cipher）是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果MOD26。

中文名
希爾密碼
外文名
Hill Cipher
原理
基本矩陣論
類別
替換密碼
提出者
Lester S. Hill
快速
導航
產生原因

原理

安全性分析

例子
簡介
希爾密碼是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。
每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果模26。
注意用作加密的矩陣（即密匙）在必須是可逆的，否則就不可能解碼。只有矩陣的行列式和26互質，才是可逆的。
產生原因
隨著科技的日新月異和人們對信用卡、計算機的依賴性的加強，密碼學顯得愈來愈重要。密碼學是一門關於加密和解密、密文和明文的學科。若將原本的符號代換成另一種符號，即可稱之為廣義的密碼。狹義的密碼主要是為了保密，是一種防止竊文者得知內容而設的另一種符號文字，也是一般人所熟知的密碼。
使用信用卡、網路賬號及密碼、電子信箱、電子簽名等都需要密碼。為了方便記憶，許多人用生日、電話號碼、門牌號碼記做密碼，但是這樣安全性較差。
為了使密碼更加復雜，更難解密，產生了許多不同形式的密碼。密碼的函數特性是明文對密碼為一對一或一對多的關系，即明文是密碼的函數。傳統密碼中有一種叫移位法，移位法基本型態是加法加密系統C=P+s(mod m)。一般來說，我們以1表示A，2表示B，……，25表示Y，26表示Z，以此類推。由於s=0時相當於未加密，而0≤s≤m-1（s≥m都可用0≤s≤m-1取代），因此，整個系統只有m-1種變化。換言之，只要試過m-1次，機密的信息就會泄漏出去。
由此看來，日常生活中的密碼和傳統的密碼的可靠性較差，我們有必要尋求一種容易將字母的自然頻度隱蔽或均勻化，從而有利於統計分析的安全可靠的加密方法。希爾密碼能基本滿足這一要求。
原理
希爾加密演算法的基本思想是，將d個明文字母通過線性變換將它們轉換為d個密文字母。解密只要作一次逆變換就可以了，密鑰就是變換矩陣本身。[1]
希爾密碼是多字母代換密碼的一種。多字母代換密碼可以利用矩陣變換方便地描述，有時又稱為矩陣變換密碼。令明文字母表為Z，若採用L個字母為單位進行代換，則多碼代換是映射f：Z→Z。若映射是線性的，則f是線性變換，可以用Z上的L×L矩陣K表示。若是滿秩的，則變換為一一映射，且存在有逆變換K。將L個字母的數字表示為Z上的L維矢量m，相應的密文矢量c，且mK=c，以K作為解密矩陣，可由c恢復出相應的明文c·K=m。
在軍事通訊中，常將字元（信息）與數字對應（為方便起見，我們將字元和數字按原有的順序對應，事實上這種對應規則是極易被破解的）：
abcde…x y z
12345…242526
如信息「NOSLEEPPING」對應著一組編碼14,15,19,12,5,5,16,16,9,14,7。但如果按這種方式直接傳輸出去，則很容易被敵方破譯。於是必須採取加密措施，即用一個約定的加密矩陣K乘以原信號B，傳輸信號為C=KB（加密），收到信號的一方再將信號還原（破譯）為B=KC。

Ⅲ c語言編寫hill密碼

// 希爾演算法的加密與解密
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <ctype.h>
#include <memory.h>// nDime為全部變數，可逆矩陣的維數
int nDime;
int index = 0;// MAXN為明文的最大長度
const int MAXN = 256;// 矩陣相乘，a是一個列為1的矩陣
void MultiplyMatrix(int a[], int b[][10], int *text)
{
int i, j, t; for (i = 0; i < nDime; i++)
{
t = 0;
for (j = 0;j < nDime; j++)
t += b[i][j] * a[j];
text[index++] = t;
}
}// 求行列式的值
int determinant(int m[][10], int size)
{
int row, column;
int temp1[10], temp2[10], t; for (column = 0; column < size; column++)
{
temp1[column] = m[0][column];
temp2[column] = m[0][column];
}
for (row = 1; row < size; row++)
{
for (column = 0; column < size; column++)
{
int diff = column - row;
int sum = column + row;
if (diff < 0)
diff += size;
if (sum >= size)
sum %= size;
temp1[diff] *= m[row][column];
temp2[sum] *= m[row][column];
}
}
t = 0;
for (row = 0; row < size; row++)
t += temp1[row] - temp2[row]; return t;
}// 求矩陣中某一元素的代數餘子式
int func(int matrix[][10], const int i, const int j)
{
int row, column, m, n;
int NewMatrix[10][10]; m = n = 0;
for (row = 0; row < nDime; row++)
{
if (i == row)
continue;
for (column = 0; column < nDime; column++)
{
if (j == column)
continue;
NewMatrix[m++][n++] = matrix[row][column];
}
}

printf ("New Array:\n");
for (row = 0; row < nDime - 1; row++)
{
for (column = 0; column < nDime - 1; column++)
printf("%d ", NewMatrix[row][column]);
printf("\n");
} int sign = (!((i + j) % 2)) ? 1 : -1;
return sign * determinant(NewMatrix, nDime - 1);
}// 對矩陣求逆，cm矩陣與m矩陣互逆
void ConverseMatrix(int m[][10], int cm[][10])
{
// 矩陣求逆，利用數學公式A（逆）= (1 / |A|)乘以A*
// 其中，|A|表示行列式A的值，而A*表示矩陣A的伴隨矩陣
int row, column;
int StarMat[10][10]; // StarMat表示m的伴隨矩陣
int t; // 初始化伴隨矩陣
for (row = 0; row < 10; row++)
for (column = 0; column < 10; column++)
StarMat[row][column] = 0; // 求伴隨矩陣
for (row = 0; row < nDime; row++)
for (column = 0; column < nDime; column++)
{
StarMat[row][column] = func(m, row, column);
printf("伴隨矩陣：%d", StarMat[row][column]);
} // 求行列式的值
t = determinant(m, nDime); // 求出逆向矩陣
for (row = 0; row < nDime; row++)
for (column = 0; column < nDime; column++)
cm[row][column] = StarMat[row][column] / t;
// 輸出逆向矩陣
for (row = 0; row < nDime; row++)
for (column = 0; column < nDime; column++)
printf("%d ", cm[row][column]);
printf("\n");
}// 希爾加密及解密演算法
void ShellPassword(int *OText, int TextLen, int matrix[][10], int *text)
{
int i, j, n, a[10];

// 判斷要將OText分成幾部分
n = TextLen / nDime;
if (TextLen % nDime)
n++; // 矩陣相乘
// 將OText分成的幾部分分別與matrix矩陣相乘
for (i = 0; i < n; i++)
{
for (j = 0; j < 10; j++)
a[j] = 0;
for (j = 0; j < nDime; j++)
a[j] = OText[i * nDime + j];
MultiplyMatrix(a, matrix, text);
}
}
int main(void)
{
int i, temp, row, column;
// matrix存放加密或解密矩陣，Password為加密後的結果
// OText存放原文轉換為普通數字，如A~1，Z~26
int matrix[10][10], ConMatrix[10][10], OText[MAXN], Password[MAXN], OriText[MAXN];
char text[MAXN];
char sel; printf("=================================================\n");
putchar('\n');
printf(" SHELL加密解密器\n");
putchar('\n');
printf("=================================================\n"); while (1)
{
// 初始化矩陣
for (row = 0; row < 10; row++)
for (column = 0; column < 10; column++)
matrix[row][column] = 0; putchar('\n');
printf("1.加密\n");
printf("2.解密\n");
printf("0.退出\n");
printf("請輸入你的選擇:\n");
sel = getche(); switch (sel)
{
case '1':
printf("\n請輸入原文:\n");
memset(text, '\0', sizeof(text) / sizeof(char));
memset(Password, 0, sizeof(Password) / sizeof(int));
gets(text); printf("輸入加密矩陣的維數，維數不能超過10維:\n");
scanf("%d", &nDime);
printf("輸入矩陣，該矩陣必須為可逆矩陣，否則將不能進行解密:\n");
// 可逆矩陣即，設A為n階矩陣，如果存n在階矩陣B使得AB=BA=1
// 則矩陣A是可逆的，稱B是A的逆矩陣
for (row = 0; row < nDime; row++)
for (column = 0; column < nDime; column++)
scanf("%d", &matrix[row][column]);
// 將小寫字母轉換為大寫字母
for (i = 0; text[i] != '\0'; i++)
if (islower(text[i]))
text[i] |= 0x20;
// OText存放將字母轉換為相應數，如A~1，Z~26
for (i = 0; i < MAXN; i++)
OText[i] = 0;
for (i = 0; text[i] != '\0'; i++)
OText[i] = text[i] - 'A' + 1;
// 加密
ShellPassword(OText, strlen(text), matrix, Password);
// 將加密後的內容列印出來
printf("加密後的內容為:\n");
for (i = 0; i < strlen(text); i++)
printf("%d ", Password[i]);
putchar('\n');
break;
case '2':
break;
case '0':
return 0;
default:
break;
}
getchar();
} return 0;
} 解碼演算法我會在明天上傳上來，你的加密密鑰是一個三階的數組，密文C是：1729 2514 811 1659 2472 858 1739 2514 849 1902 2736 905 1659 2472 858

Ⅳ 爬山演算法（Hill Climbing）解決旅行商問題（TSP）

旅行商問題 TSP（Travelling Salesman Problem）是數學領域中著名問題之一。

TSP問題被證明是 NP完全問題 ，這類問題不者寬腔能用精確演算法實現，而需要使用相似演算法。

TSP問題分為兩類： 對稱TSP （Symmetric TSP）以及 非對稱TSP （Asymmetric TSP）

本文解決的是對稱TSP
假設：A表示城市A，B表示城市B，D(A->B)為城市A到城市B的距離，同理D(B->A)為城市B到城市A的距離
對稱TSP中，D(A->B) = D(B->A)，城巧升市間形成無向圖
非對稱TSP中，D(A->B) ≠ D(B->A)，城市間形成有向圖

現實生活中，可能出現單行線、交通事故、機票往返價格不同等情況，均可以打破對稱性。

爬山演算法是一種局部擇優的方法，採用啟發式方法。直觀的解釋如下圖：

爬山演算法，顧名思義就是 爬山 ，找到第一個山峰的時候就停止，作為演算法的輸出結果。所以，爬首衫山演算法容易把局部最優解A作為演算法的輸出，而我們的目的是找到全局最優解B。

如下圖所示，盡管在這個圖中的許多局部極大值，仍然可以使用 模擬退火演算法（Simulated Annealing） 發現全局最大值。

必要解釋詳見注釋

此處根據經緯度計算城市間距離的公式，請參考 Calculate distance between two latitude-longitude points? (Haversine formula)

此處初始化數據源可以使用 TSPLIB 中所提供的數據，此程序大致闡述爬山演算法的實現。

編寫於一個失眠夜

菜鳥一枚，歡迎評論區相互交流，加速你我成長•ᴗ•。

Ⅳ 傳統的加密方法有哪些

本文只是概述幾種簡單的傳統加密演算法，沒有DES,沒有RSA，沒有想像中的高端大氣上檔次的東東。。。但是都是很傳統很經典的一些演算法

首先，提到加密，比如加密一段文字，讓其不可讀，一般人首先會想到的是將其中的各個字元用其他一些特定的字元代替，比如，講所有的A用C來表示，所有的C用E表示等等…其中早的代替演算法就是由Julius Caesar發明的Caesar，它是用字母表中每個字母的之後的第三個字母來代替其本身的（C=E(3，p)=（p+3) mod 26)，但是，這種加密方式，很容易可以用窮舉演算法來破解，畢竟只有25種可能的情況..

為了改進上訴演算法，增加其破解的難度，我們不用簡單的有序的替代方式，我們讓替代無序化，用其中字母表的一個置換（置換：有限元素的集合S的置換就是S的所有元素的有序排列，且每個元素就出現一次，如S={a,b}其置換就只有兩種:ab,ba），這樣的話，就有26！種方式，大大的增加了破解的難度，但是這個世界聰明人太多，雖然26！很多，但是語言本身有一定的特性，每個字母在語言中出現的相對頻率可以統計出來的，這樣子，只要密文有了一定數量，就可以從統計學的角度，得到准確的字母匹配了。

上面的演算法我們稱之為單表代替，其實單表代替密碼之所以較容易被攻破，因為它帶有原始字母使用頻率的一些統計學特徵。有兩種主要的方法可以減少代替密碼里明文結構在密文中的殘留度，一種是對明文中的多個字母一起加密，另一種是採用多表代替密碼。

先說多字母代替吧，最著名的就是playfair密碼，它把明文中的雙字母音節作為一個單元並將其轉換成密文的雙字母音節，它是一個基於由密鑰詞構成的5*5的字母矩陣中的，一個例子，如密鑰為monarchy，將其從左往右從上往下填入後，將剩餘的字母依次填入剩下的空格，其中I/J填入同一個空格:

對明文加密規則如下：
1 若p1 p2在同一行，對應密文c1 c2分別是緊靠p1 p2 右端的字母。其中第一列被看做是最後一列的右方。
2 若p1 p2在同一列，對應密文c1 c2分別是緊靠p1 p2 下方的字母。其中第一行被看做是最後一行的下方。
3 若p1 p2不在同一行，不在同一列，則c1 c2是由p1 p2確定的矩形的其他兩角的字母，並且c1和p1， c2和p2同行。
4 若p1 p2相同，則插入一個事先約定的字母，比如Q 。
5 若明文字母數為奇數時，則在明文的末端添加某個事先約定的字母作為填充。

雖然相對簡單加密，安全性有所提高，但是還是保留了明文語言的大部分結構特徵，依舊可以破解出來，另一個有意思的多表代替密碼是Hill密碼，由數學家Lester Hill提出來的，其實就是利用了線性代數中的可逆矩陣，一個矩陣乘以它的逆矩陣得到單位矩陣，那麼假設我們對密文每m個字母進行加密，那麼將這m個字母在字母表中的序號寫成矩陣形式設為P（如abc，[1,2,3])，密鑰就是一個m階的矩陣K，則C=P*K mod26，，解密的時候只要將密文乘上K的逆矩陣模26就可以了。該方法大大的增加了安全性。