一、實驗目的

?1、通過實現簡單的古典密碼算法，理解密碼學的相關概念

??2、理解明文、密文、加密密鑰、解密密鑰、加密算法、解密算法、流密碼與分組密碼等。

二、實驗內容

1、題目內容描述

①定義分組字符長度

②隨機生成加密密鑰，并驗證密鑰的可行性

③從plain文件讀入待加密明文

④判斷明文長度是否需要填充

⑤進行希爾密碼加密

⑥將加密后得到的密文放入cipher文件

⑦根據加密密鑰計算解密密鑰

⑧進行解密運算

⑨將解密后的文本放入plain_decrypted文件，與明文進行對比

⑩仿射密碼與希爾密碼的異同

1. 關鍵代碼的設計、實現與執行

設計思路：

在最開始以宏定義的方式定義分組字符長度，關鍵代碼：
#define M 2 //定義最大分組長度

先以時間產生隨機數作為加密密鑰矩陣enkey，但是這里要通過求最大公因數的方式來驗證加密密鑰enkey的可行性，即密鑰矩陣enkey的行列式detb和N的最大公因數為1，即detb，N互質（其中N為定義在Zn上的N）：

下面代碼是運用Euclid算法計算最大公因數的關鍵代碼：

srand(time(NULL));//以時間取隨機數

do {

for (int i = 0; i < M; i++) {

for (int j = 0; j < M; j++) {

enkey[i][j] = rand() % N;//隨機生成密鑰矩陣

}

}

detb = enkey[0][0] * enkey[1][1] - enkey[0][1] * enkey[1][0];//計算加密矩陣的行列式

} while (gcd(detb, N) != 1);//檢驗密鑰的可行性，也就是行列式與N是否互質，能否得到行列式的逆元

得到加密密鑰后，從文件讀入已經準備好的加密明文（也可通過記事本修改），下面代碼是以讀的方式打開文件，并判斷是否在文件夾中存在命名的文件的關鍵代碼部分：

?FILE *plain_file = fopen("plain.txt", "r");//以讀的方式打開

????if (plain_file == NULL) {

????????printf("無法打開明文文件！\n");//判斷無法打開給出提示

????????exit(1);//無法打開只能以異常終止結束運行

}

得到明文后，先調用read_palinfile()函數，統計其長度，看是或否剛好為M的倍數，若不是就進行填充，此處對于剩余需要填充的部分都填的x，再重新計算需要加密解密的文本長度，于是有msize = msize + M - r，關鍵代碼部分如下：

int msize = read_plainfile(plain_file, &plain_text[0]);

int r = msize % M;//判斷是否需要填充

if (r < 0)

r += M;

if (r > 0)//如需填充，都填為0，加密后統一得到x

{

for (int i = msize; i < msize + M - r; i++)

plain_text[i] = 23;//x的ASCII碼為120，'a'-'x'=120-97=23

msize = msize + M - r;//重新得到加密或解密文本新的長度

}

在得到明文文件后，調用函數read_plainflie(),將明文文件里的有效內容（即字母）放入字符數組，方便后續分組，且可以有效字符的長度，關鍵代碼部分如下：

while ((ch = getc(plain_file)) != EOF)//getc（）用于在打開文件中獲取一個字符

{

if (ch >= 'a' && ch <= 'z')

*plain = ch - 97;//ASCII碼轉換

else if (ch >= 'A' && ch <= 'Z')

*plain = ch - 65;//ASCII碼轉換

else continue;

i++;//計數有效字符數量

*plain++;//指針加加，字符數組向下移一位，好存放下一次的字符

}

return i;//返回文件中有效字符的數量，以方便后續分組

以M為分組數量單位，進行加密，其中運用了二階矩陣的運算，并判斷得到的新的是否有負數，如有，加模，使其轉化為正數，再加上’a’的ASCII碼，使其統一為大寫字母，*cipher++，指向下一次計算得到的字符存放的地址，關鍵代碼部分如下：

for (i = 0; i < M; i++)//矩陣乘法

{

tmp = 0;

for (j = 0; j < M; j++)

tmp = tmp + plain[j] * enkey[j][i];// 分組加密計算

tmp %= N;//模N

if (tmp < 0)

tmp += N;//負數轉正數

*cipher = tmp + 97;//統一轉換為大寫字母

*cipher++;

將字符數組分組，并調用分組加密的函數進行加密。tmpplain，tmpcipher是以M為單位長度的字符數組，將需要加密的文本分組放入tmpplain，再調用encrypt_block進行以M為單位長度的分組加密，得到的結果返回給同樣是長度為M的tmpcipher字符數組，再依此傳給cipher，關鍵代碼部分如下：

for (i = 0; i < msize; i = i + M)//依此從字符數組中取M個字符，調用分組函數encrypt_block（）進行加密或解密

{

for (j = 0; j < M; j++)

tmpplain[j] = plain[i + j];//在要加密或者解密的文件中連續截取M個字符放入存放M個字符的數組進行加密或解密

encrypt_block(tmpplain, enkey, &tmpcipher[0]);//調用分組加密函數

for (j = 0; j < M; j++)//將加密或者解密后得到的字母依次放入cipher數組

{

*cipher = tmpcipher[j];//賦值

*cipher++;//指針后移，下依此循環存放新的字幕

}

}

計算解密矩陣，由于計算矩陣的逆矩陣，是行列式的倒數（也就是此處的逆元）*伴隨矩陣，二階矩陣的伴隨矩陣直接用口訣主對調，副變號即可，過程即是先調用inverse_a（）計算行列式逆元，并判斷其是否為負數，如是，加上N，使其轉化成正數，再通過公式計算出解密矩陣，并判斷矩陣中每個數是否為負數，如是，加上N使其轉化成正數，得到解密所需的解密矩陣，以下是關鍵代碼部分：

int a1 = inverse_a(detb);//計算加密矩陣行列式的逆元

if (a1 < 0)

a1 += N;

dekey[0][0] = enkey[1][1] * a1 % N;//主對調，副變號

dekey[0][1] = (-enkey[0][1] * a1) % N;

dekey[1][0] = (-enkey[1][0] * a1) % N;

dekey[1][1] = enkey[0][0] * a1 % N;

for (int i = 0; i < M; i++)//遍歷檢查解密矩陣中是否有負數，如有，加N，轉換成正數

{

for (int j = 0; j < M; j++)

{

if (dekey[i][j] < 0)

dekey[i][j] += N;//加N

}

}

結果截圖如下：

3、實驗結果分析

多測幾組后實驗得到結果下：

由以上結果即分析可知加密的時候程序自動跳過了空格即字符進行了加密解密，且最后全部由小寫字母輸出，當然也可全部由大寫字母輸出，只需要將+97換成+65即可，因為分別對應著小寫字母‘a’的ASCII碼和大寫字母‘A’的ASCII碼

而在第二個實驗的結果和第三個實驗的結果發現多出了x，這是因為在以2分組時，會有剩余，于是由x進行了填充。

對于仿射密碼和希爾密碼的異同：
綜上可知，希爾密碼和仿射密碼都是需要求逆元，只是仿射密碼是直接對密鑰求逆元得到的就是解密的密鑰，而希爾是對加密矩陣的行列式求逆元，得到的也只是行列式的逆元，而還需要*加密矩陣的伴隨矩陣，得到的新的矩陣才是解密的矩陣

在代碼中也可以看到，希爾密碼和仿射密碼一樣解密和加密幾乎一樣只是密鑰矩陣不一樣，步驟一樣，所以可以直接調用一個函數，只是傳參不一樣。

不同的是，仿射密碼是直接對明文的每個字符進行依此進行加密解密，而希爾密碼需要對對需要加密或者解密問文本進行分組，每M個一組一起進行加密或者解密，如是在n個M組以后還有剩余不夠M個，即進行填充，可以以任何形式進行填充，在此次實驗中，我選擇了小寫字母x，因為在一般情況下，其出現頻率最小。

三、實驗思考

1、實驗過程總結

在此次實驗中，直接在仿射密碼的代碼上進行修改，就簡單很多，只需要將不同的地方進行修改即可，如最大公因式函數、求逆元函數、以及文件打開等部分都保持不變，但在隨機生成函數部分，由一個改成一個矩陣，然后就是分組進行加密解密部分進行修改。

但是在代碼實現過程中由于編程能力問題，傳參部分一直出現問題，最終經過查詢相關知識得以解決，此外，在解密過程中，一開始沒有調用read_plainfile()函數，讀cipher文件里的東西直接進行解密，導致解密出來的的文本與明文一直不匹配，經過不斷看看，分析代碼，發現問題進行修改后解密出來的文本終于能夠和原明文匹配。

通過此次實驗使我加深了對希爾密碼的理解，清晰了希爾密碼加密解密每一步的原理，也知道了希爾密碼和仿射密碼的區別和相同點，同時加強了我自己的代碼能力。

1. 回答實驗指導書最后提出的問題

①對合密鑰是一種弱密鑰，不應該在實際加密中使用，這是為什么？

對合密鑰使用了相同的密鑰進行加密解密，這意味著加密和解密在同一個用戶之間進行，這使得對合密鑰的安全性受到很大的限制，因為如果一個用戶失去了對合密鑰的控制，他也將無法保護自己的信息；而如果兩個用戶使用同一個對合密鑰進行加密和解密操作，那么他們的信息很容易被第三方竊取。這是因為他們涉及一個公共密鑰，這意味著第三方也可以用這個公共密鑰進行通信，從而獲得敏感信息。

②若仿射密碼定義在Z26上，其對合密鑰有多少個？

仿射密碼的加密函數為E(x) = (ax + b) mod 26，解密函數為D(x) = a^-1(x - b) mod 26，其中a和b為密鑰，a^-1為a的模26乘法逆元。

由于對合函數要求f(f(x))=x，即E(E(x))=x，則有(E(E(x))) mod 26 = x，即((a(ax + b) + b) mod 26) mod 26 = x。解方程得到a^2x + ab + b = x，整理得到(a^2 - 1)x = (1 - ab) mod 26。

因為a^2 - 1必須是26的乘法逆元，所以a^2 - 1的因子必須是26的因子，即a^2 - 1必須是2或13的倍數，即a^2與26互質。根據這個條件，可以求出滿足條件的a的取值，而對b沒有什么限制，最后計算出滿足條件的對合密鑰的數量，代碼計算結果如下：

③若2×2的希爾密碼定義在Z26上，其對合密鑰有多少個？

希爾密碼的加密函數為E(x) = Kx mod 26，其中K為2×2的密鑰矩陣，解密函數為D(x) = K^-1x mod 26，其中K^-1為K的模26乘法逆元的矩陣。

對合函數要求f(f(x))=x，即E(E(x))=x，則有(E(E(x))) mod 26 = x，即((KKx) mod 26) mod 26 = x。解方程得到(KKx) mod 26 = x，即K*K是26n的單位矩陣[1，0;0，1]。根據這個條件，可以求出滿足條件的2×2的對合密鑰的數量。

以上是對合密鑰數量的計算過程及代碼運行結果。