密码学--希尔密码
一、实验目的
1、通过实现简单的古典密码算法，理解密码学的相关概念
2、理解明文、密文、加密密钥、解密密钥、加密算法、解密算法、流密码与分组密码等。
二、实验内容
1、题目内容描述
①定义分组字符长度
②随机生成加密密钥，并验证密钥的可行性
③从plain文件读入待加密明文
④判断明文长度是否需要填充
⑤进行希尔密码加密
⑥将加密后得到的密文放入cipher文件
⑦根据加密密钥计算解密密钥
⑧进行解密运算
⑨将解密后的文本放入plain_decrypted文件，与明文进行对比
⑩仿射密码与希尔密码的异同
- 关键代码的设计、实现与执行
设计思路：
在最开始以宏定义的方式定义分组字符长度，关键代码：
#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文件里的东西直接进行解密，导致解密出来的的文本与明文一直不匹配，经过不断看看，分析代码，发现问题进行修改后解密出来的文本终于能够和原明文匹配。
通过此次实验使我加深了对希尔密码的理解，清晰了希尔密码加密解密每一步的原理，也知道了希尔密码和仿射密码的区别和相同点，同时加强了我自己的代码能力。
- 回答实验指导书最后提出的问题
①对合密钥是一种弱密钥，不应该在实际加密中使用，这是为什么？
对合密钥使用了相同的密钥进行加密解密，这意味着加密和解密在同一个用户之间进行，这使得对合密钥的安全性受到很大的限制，因为如果一个用户失去了对合密钥的控制，他也将无法保护自己的信息；而如果两个用户使用同一个对合密钥进行加密和解密操作，那么他们的信息很容易被第三方窃取。这是因为他们涉及一个公共密钥，这意味着第三方也可以用这个公共密钥进行通信，从而获得敏感信息。
②若仿射密码定义在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的对合密钥的数量。
以上是对合密钥数量的计算过程及代码运行结果。