1. 欧几里得算法

1.1 分析算法的实现原理

      欧几里德（Euclid）算法，也既常说的“辗转相除法”，公式为gcd(m, n) { return gcd(n, m%n); }，对于任意两个正整数m、n，每次求的一个数字r = m % n，然后把n放到m的位置，把r放到n的位置，递归调用。当 m%n == 0的时候停止。

1.2 代码

#include<stdio.h>
int main()
{int m,n,r=0;printf("请输入两个正整数:");scanf("%d%d",&m,&n);while(n!=0){r=m%n;m=n;n=r;}	printf("最大公因子是:%d\n",m);return m;
}

1.3 运行结果

2. 扩展欧几里得算法

 2.1 扩展欧几里得原理

1. 初始化：
   • 设定两个整数a和b，以及两个变量x和y，初始时x和y的值与欧几里得算法中的迭代过程相关。
   • 通常，当b为0时，设定x=1，y=0，因为此时a和0的最大公约数是a本身。
2. 迭代计算：
   • 使用欧几里得算法计算a和b的商q和余数r。
   • 更新a和b的值，使a=b，b=r。
   • 同时，根据扩展欧几里得算法的推导式更新x和y的值。通常这一步骤涉及到递归或迭代地求解上一轮ax + by = gcd(a, b)的解x'和y'，然后用它们来计算当前轮的解x和y。
3. 终止条件：
   • 当b为0时，算法终止。此时a的值即为a和b的最大公约数，而x和y则是一组满足贝祖等式的整数解。

2.2 代码

#include <stdio.h>// 扩展欧几里得算法
void extendedEuclid(int a, int b, int *x, int *y, int *gcd) {if (b == 0) {*x = 1;*y = 0;*gcd = a;} else {int x1, y1;extendedEuclid(b, a % b, &x1, &y1, gcd);// 更新x和y的值*x = y1;*y = x1 - (a / b) * y1;}
}int main() {int a , b ;int x, y, gcd;printf("请输入两个不为0的整数：\n");scanf("%d %d",&a,&b); // 调用函数extendedEuclid(a, b, &x, &y, &gcd);printf("%d 和 %d 的最大公约数是： %d\n", a, b, gcd);printf("\n此时，x = %d, y = %d\n", x, y);// 验证结果if (a*x + b*y == gcd) {printf("方程 %dx + %dy = %d 成立.\n", a, b, gcd);} else {printf("这个等式不成立，请检查执行情况。\n");}return 0;
}

2.3 运行结果

3. DES算法

    DES（Data Encryption Standard，数据加密标准）是一种对称密钥加密算法，由IBM公司研发并在1977年被美国政府采用为联邦信息处理标准。DES算法主要应用于保证数据的机密性，尽管现在因其密钥长度较短而逐渐被AES（Advanced Encryption Standard，高级加密标准）取代，但其基本原理仍然是密码学中的一个重要基础。

 3.1 DES算法原理

    DES算法基于Feistel结构，其核心是一个分组密码，即它以固定长度的块（64位）对数据进行加密，常见的块大小为64位，而密钥长度为56位（实际密钥输入为64位，其中有8位用于奇偶校验，因此有效密钥长度为56位）。DES加密和解密过程非常相似，解密时使用的是与加密时相同的密钥，但密钥的使用顺序相反。

    DES算法将输入的明文分为64位的数据分组（最后一个分组不足64位则补0），使用一个56+8 (第8i位为奇偶校验位，i=1,2,…)=64位的密钥进行变换，每个64位明文分组数据经过初始置换、16次迭代和逆初始置换3个主要阶段，最后输出得到64位密文。

加密流程：

1. 初始置换（Initial Permutation, IP）：首先，对明文块进行一个固定的置换，将64位明文按照一定规则重新排列。

2. 循环迭代（Round）：接下来，数据块经过16轮完全相同的迭代运算，每轮包括以下步骤：

   • 分组：将数据分为左右两半，每半32位。
   • 扩展置换（Expansion）：左半部分经过扩展置换变为48位。
   • 密钥混淆（Key Mixing）：扩展后的数据与经过密钥调度产生的本轮子密钥（48位）进行异或操作。
   • S盒变换（Substitution）：结果被分割成8组6位数据，每组通过查S盒（替代盒）转换为4位，实现非线性变换。
   • P盒变换（Permutation）：上述32位结果经过P盒进行重新排列。
   • 左右合并：上述得到的32位结果与原始右半部分进行交换，然后与原始左半部分合并，准备进入下一轮迭代。

3. 最终置换（Final Permutation, FP）：经过16轮迭代后，最后一次的左右部分合并后，再进行一次与初始置换相反的置换，得到最终的密文。

密钥调度：

    在DES算法中，一个主密钥通过一个密钥调度算法被扩展并转化为16个不同的子密钥，每轮迭代使用一个子密钥。这一过程增强了安全性，使得直接从密文推算密钥更为困难。

3.2 代码

#include <iostream>
#include <bitset>
#include <string>
#include <cmath>
#include<stdlib.h>
#include <cstdlib>
using namespace std;
/**
*函数声明
*/
string hexToTwo(string str);  //十六进制转二进制string int2BinString(int n);  //int转四位stringstring exchange(string str, int rule[], int x);  //置换string circleMove(string str, int j);  //单步移位string spiltShift(string str, int j);  // 左右分别移位string XOR(string str1, string str2);  //异或string SBoxWork(string str, int SBox[][4][16]);  //S盒工作int binToDec(string bin);  //二进制转十进制string Bin2Hex(string strBin);   //二进制转十六进制int str2Dec(string str);  // string字符串转十进制void printMenu();  //打印功能菜单void controller();  //功能控制器void encryption(); //加密void decryption(); //解密/**
*全局变量
*/
const int Key_SIZE = 16;/**
*8张表
*/
//交换规则表（8*7）
const int ExchangeRules_SIZE = 56;
int ExchangeRules[56] =
{57, 49, 41, 33, 25, 17,  9,1, 58, 50, 42, 34, 26, 18,10,  2, 59, 51, 43, 35, 27,19, 11,  3, 60, 52, 44, 36,63, 55, 47, 39, 31, 23, 15,7, 62, 54, 46, 38, 30, 22,14,  6, 61, 53, 45, 37, 29,21, 13,  5, 28, 20, 12,  4
};
//移位表
const int ShiftTable_SIZE = 16;
int ShiftTable[16] =
{1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
//PC-2（8*6）
const int PC_2_SIZE = 48;
int PC_2[48] =
{14, 17, 11, 24,  1,  5,3, 28, 15,  6, 21, 10,23, 19, 12,  4, 26,  8,16,  7, 27, 20, 13,  2,41, 52, 31, 37, 47, 55,30, 40, 51, 45, 33, 48,44, 49, 39, 56, 34, 53,46, 42, 50, 36, 29, 32
};
//IP（8*8）
const int IP_SIZE = 64;
int IP[64] =
{58, 50, 42, 34, 26, 18, 10,  2,60, 52, 44, 36, 28, 20, 12,  4,62, 54, 46, 38, 30, 22, 14,  6,64, 56, 48, 40, 32, 24, 16,  8,57, 49, 41, 33, 25, 17,  9,  1,59, 51, 43, 35, 27, 19, 11,  3,61, 53, 45, 37, 29, 21, 13,  5,63, 55, 47, 39, 31, 23, 15,  7
};
//扩展置换E（8*6）
const int E_SIZE = 48;
int E[48] =
{32,  1,  2,  3,  4,  5,4,  5,  6,  7,  8,  9,8,  9, 10, 11, 12, 13,12, 13, 14, 15, 16, 17,16, 17, 18, 19, 20, 21,20, 21, 22, 23, 24, 25,24, 25, 26, 27, 28, 29,28, 29, 30, 31, 32,  1
};
//S盒
int SBox[8][4][16] =
{{{14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7},{0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8},{4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0},{15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13}},{{15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10},{3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5},{0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15},{13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9}},{{10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8},{13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1},{13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7},{1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12}},{{7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15},{13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9},{10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4},{3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14}},{{2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9},{14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6},{4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14},{11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3}},{{12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11},{10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8},{9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6},{4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13}},{{4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1},{13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6},{1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2},{6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12}},{{13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7},{1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2},{7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8},{2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11}}
};
//P盒（8*4）
const int P_SIZE = 32;
int P[32] =
{16,  7, 20, 21,29, 12, 28, 17,1, 15, 23, 26,5, 18, 31, 10,2,  8, 24, 14,32, 27,  3,  9,19, 13, 30,  6,22, 11,  4, 25
};
//IP-1（8*8）
const int IP_1_SIZE = 64;
int IP_1[64] =
{40, 8, 48, 16, 56, 24, 64, 32,39, 7, 47, 15, 55, 23, 63, 31,38, 6, 46, 14, 54, 22, 62, 30,37, 5, 45, 13, 53, 21, 61, 29,36, 4, 44, 12, 52, 20, 60, 28,35, 3, 43, 11, 51, 19, 59, 27,34, 2, 42, 10, 50, 18, 58, 26,33, 1, 41,  9, 49, 17, 57, 25
};
int main()
{printMenu();return 0;
}
/**
*打印功能菜单
**/
void printMenu()
{cout<<"欢迎来到DES加密解密系统！ "<<endl;cout<<"请选择系统功能："<<endl;cout<<"1. 加密"<<endl;cout<<"2. 解密"<<endl;cout<<"3. 退出系统"<<endl;controller();
}
/**
*功能控制器
**/
void controller()
{cout<<"———————————————————— "<<endl;int choice;cin>>choice;if(choice == 1) encryption();else if(choice == 2) decryption();else if(choice == 3) {cout<<"感谢您的使用，再见!"<<endl;exit(0);}else{cout<<"错误！未知选项，请重新选择："<<endl;controller();}
}/**
*加密
**/
void encryption()
{/***初始条件**//* 输入明文MingWen（十六进制），密钥Key（十六进制） */string MingWen ;string Key;cout<<"输入明文: "<<endl;cin>>MingWen;cout<<"输入密钥: "<<endl;cin>>Key;string M = hexToTwo(MingWen);string K = hexToTwo(Key);/***处理密钥，生成16个子密钥 **//* 利用规则交换表（8*7）将K转换成 K0 ;  K0(56位) = C0(28位) + D0(28位) */string KKK = exchange(K, ExchangeRules, ExchangeRules_SIZE);/* 利用移位表转换得C1D1----C16D16,存入K_arr */int i = 0;string K_arr[Key_SIZE+1];K_arr[0] = KKK;for(i=1; i<=Key_SIZE; i++){K_arr[i] = spiltShift(K_arr[i-1], ShiftTable[i-1]);}/* Kn（48位）= PC-2（8*6）处理 CnDn得16个子密钥，存入Key_arr */string Key_arr[Key_SIZE];for(i=0; i<Key_SIZE; i++){Key_arr[i] = exchange(K_arr[i+1], PC_2, PC_2_SIZE);}/*** 用子密钥对明文加密**//* 通过IP（8*8）处理M得L0（32位）  R0（32位） */string IP_M = exchange(M, IP, IP_SIZE);/* Ln= R(n-1); Rn= L(n-1) + f(R(n- 1); Kn)迭代16次 */string L[Key_SIZE+1];string R[Key_SIZE+1];L[0] = IP_M.substr(0, M.length()/2);R[0] = IP_M.substr(M.length()/2);string it = "";for(i=1; i<=Key_SIZE; i++){//将R0通过扩展置换E（8*6）从32位扩展到48位it = exchange(R[i-1], E, E_SIZE);//R0（48位）与 K1异或得E0（48位）it = XOR(it, Key_arr[i-1]);//将E0（48位）通过S盒转换成32位it = SBoxWork(it, SBox);//P盒（8*4）置换，得P0it = exchange(it, P, P_SIZE);//P0与L0进行异或，得J0it = XOR(it, L[i-1]);//左右交换位置，即R1 = J0; L1 = R0L[i] = R[i-1];R[i] = it;}/* 对R16 L16进行一次IP-1（8*8）排序得密文 */string res = "";res += R[16];res += L[16];string finalRes = Bin2Hex(exchange(res, IP_1, IP_1_SIZE));cout<<"得到的密文如下: "<<endl;cout<<finalRes<<endl;cout<<"------------------------"<<endl;printMenu();
}/**
*解密
**/
void decryption()
{string MiWen;string Key;cout<<"输入密文: "<<endl;cin>>MiWen;cout<<"输入密钥: "<<endl;cin>>Key;string M = hexToTwo(MiWen);string K = hexToTwo(Key);/***处理密钥，生成16个子密钥 **//* 利用规则交换表（8*7）将K转换成 K0 ; K0(56位) = C0(28位) + D0(28位) */string KKK = exchange(K, ExchangeRules, ExchangeRules_SIZE);/* 利用移位表转换得C1D1----C16D16,存入K_arr */int i = 0;string K_arr[Key_SIZE+1];K_arr[0] = KKK;for(i=1; i<=Key_SIZE; i++){K_arr[i] = spiltShift(K_arr[i-1], ShiftTable[i-1]);}/* Kn（48位）= PC-2（8*6）处理 CnDn得16个子密钥，存入Key_arr */string Key_arr[Key_SIZE];for(i=0; i<Key_SIZE; i++){Key_arr[i] = exchange(K_arr[i+1], PC_2, PC_2_SIZE);}/*** 用子密钥对明文加密**//* 通过IP（8*8）处理M得L0（32位）  R0（32位） */string IP_M = exchange(M, IP, IP_SIZE);/* Ln= R(n-1); Rn= L(n-1) + f(R(n- 1); Kn)迭代16次 */string L[Key_SIZE+1];string R[Key_SIZE+1];L[0] = IP_M.substr(0, M.length()/2);R[0] = IP_M.substr(M.length()/2);string it = "";for(i=1; i<=Key_SIZE; i++){//将R0通过扩展置换E（8*6）从32位扩展到48位it = exchange(R[i-1], E, E_SIZE);//R0（48位）与 K1异或得E0（48位）it = XOR(it, Key_arr[16-i]);//将E0（48位）通过S盒转换成32位it = SBoxWork(it, SBox);//P盒（8*4）置换，得P0it = exchange(it, P, P_SIZE);//P0与L0进行异或，得J0it = XOR(it, L[i-1]);//左右交换位置，即R1 = J0; L1 = R0L[i] = R[i-1];R[i] = it;}/* 对R16 L16进行一次IP-1（8*8）排序得密文 */string res = "";res += R[16];res += L[16];string finalRes = Bin2Hex(exchange(res, IP_1, IP_1_SIZE));cout<<"得到的明文如下: "<<endl;cout<<finalRes<<endl;cout<<"------------------------"<<endl;printMenu();}/**
*int转四位string  +  int十进制转string二进制
**/
string int2BinString(int n)
{bitset<4> bit(n);return bit.to_string();
}
/**
*string十六进制转string二进制
**/
string hexToTwo(string str)
{string twoBin = "";int i;for(i=0; i<16; i++){if(str[i]>='0'&&str[i]<='9')twoBin.append(int2BinString(str[i]));else if(str[i]>='A'&&str[i]<='Z')twoBin.append(int2BinString(str[i]-'A'+10));else if(str[i]>='a'&&str[i]<='z')twoBin.append(int2BinString(str[i]-'a'+10));}return twoBin;
}
/**
* string二进制转int十进制
**/
int binToDec(string bin)
{int sum = 0;for(int i=0; i<bin.size(); i++){if(bin[i]=='0' || bin[i]=='1'){sum += (bin[i]-'0') * pow(2, bin.size()-i-1);}else{cout<<"非法二进制字符！"<<endl;return 0;}}return sum;
}/**
* 01字符转十进制
**/
int str2Dec(string str)
{bitset<64> bst(str);return (int)bst.to_ulong();
}
/**
* 64位密文转十六进制
**/
//Bin2Hex转换表
const static string Bin_Hex[16]
{"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"
};
string Bin2Hex(string strBin)
{string hex;int a = strBin.length()/4;string trans;for(int i = 0; i < a; i++){trans.clear();trans = strBin.substr(i*4, 4);hex += Bin_Hex[str2Dec(trans)];}return hex;
}/**
*利用交换表进行置换
**/
string exchange(string str, int rule[], int x)
{string exchangedStr = "";int i, temp;for(i=0; i<x; i++){temp = rule[i]-1;exchangedStr.append(1, str[temp]);}return exchangedStr;
}/**
*依据移位表进行移位
**/
string circleMove(string str, int j)
{string targetString = "";targetString.append(str.substr(j));targetString.append(str.substr(0, j));return targetString;
}
/**
*左右两部分移位
**/
string spiltShift(string str, int j)
{string targetStr = "";string leftString = str.substr(0, str.length()/2);string rightString = str.substr(str.length()/2);targetStr.append(circleMove(leftString, j));targetStr.append(circleMove(rightString, j));return targetStr;
}
/**
* string 异或
**/
string XOR(string str1, string str2)
{string targetString = "";for(int j=0; j<str1.length(); j++){targetString += ((str1[j] - '0') ^ (str2[j] - '0')) + '0';}return targetString;
}
/**
* S盒工作
**/
string SBoxWork(string str, int SBox[][4][16])
{string targetString = "";string temp = "";string x = "", y = "";int col = 0, row = 0;for(int i=0; i<str.size()/6; i++){temp = str.substr(6*i, 6);x = temp.substr(0, 1)+temp.substr(5, 1);y = temp.substr(1, 4);row = binToDec(x);col = binToDec(y);targetString.append(int2BinString(SBox[i][row][col]));}return targetString;
}

3.3 运行结果

4. RSA算法

    RSA算法是一种非对称加密算法，由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年提出，广泛应用于现代信息安全体系中，特别是在数据加密、数字签名和安全认证等领域。

    RSA算法作为一种国际标准算法，广泛应用于信息安全领域。其优点主要表现在以下几个方面：首先，RSA算法是一种非对称加密算法，公钥和私钥不同，公钥可以公开，但私钥只有拥有者才能使用，这样可以有效地保护通信的安全性；其次，由于RSA是国际标准算法，因此相对来说它会更为普及，也不容易受到其他问题的限制。

    然而，RSA算法也存在一些缺点。最主要的一点就是加解密速度较慢，因为进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。这使得RSA一般只适用于少量数据的加密。另外，虽然私钥的安全由用户自行保管可以在一定程度上防止信息泄露，但如果私钥在使用过程中被泄露，那么对应的信息也将处于极大的风险之中。

 4.1 RSA算法原理

密钥对的生成：

（1）选取两个大素数p和q（目前两个数的长度都接近512bit是安全的）

（2）计算乘积n=p*q，Φ(n)=(p-1)(q-1)，其中Φ(n)为n的欧拉函数（因为两素数乘积的欧拉函数等于两数分别减一后的乘积）

（3）随机选取整数e（1<e<Φ(n)）作为公钥d，要求满足e与Φ(n)的最大公约数为1，即两者互素

（4）用Euclid扩展算法计算私钥d，已满足d * e ≡ 1 (mod Φ(n))，即d ≡ e^(-1) (mod Φ(n))。则e与n是公钥，d是私钥

注意：e与n应公开，两个素数p和q不再需要，可销毁，但绝不可泄露。

加密过程：

将接收到的明文转换成特定的编码方式。如p=43，q=59，e=2，明文为majiaqizuisuai， 

按照如上英文字母表的顺序进行编码后为1200090800160825200818200008。

   然后将转码后的字符串分块，分组要求：每个分组对应的十进制数小于0。上文字符串分组如下1200 0908 0016 0825 2008 1820 0008。每一分组的数都小于n（2537），而2537能接受的最大的数为2525（也就是‘zz’的情况），所以是4位1组，即两字符一组。这样一来，m1=1200，m2=0908，... ，m6=0008

    现在可以加密了，加密算法就是这个式子----ci ≡ mi^e (mod n)，如第一分组 1200^2 ≡ mod 2537 ≡ 1521=c1,第二组0908^2 ≡ mod 2537 ≡ 2476=c2……

 4.2 代码

#include<stdio.h>
#include<stdlib.h>/* 函数申明 */
int long_n(int n);
int shuru(char *arr, int k, char *wei, int is_first);
void jiami(char *arr, int k, int e, int n);int primeNum(int num)   //判断素数
{int i =2;if (num == 1 || num == 0){return 0;}for (i = 2; i <= num-1; i++){if (num % i == 0){printf("输入的值不是素数\n");return 0;}}printf("输入的值为素数，请继续...\n");
}
int coprime(int a, int b)  //判断互质
{int t=0,c=a,d=b;if (a < b){t = a; a = b; b = t;}while (a % b){t = b;b = a % b;a = t;}printf("(p-1)*(q-1)与e互质，请继续...\n");
}int shuru(char *arr, int k, char *wei, int is_first)//获取明文并分组 
{int i;char ch;/*判断是否为第一分组的输入，如果是则获取输入的字符，否则就将上一分组最后获取的字符作为这一分组的第一个字符*/if (is_first == 1)    ch = getchar();elsech = *wei;for (i = 0; (i < k) && (ch != '\n');i++)  //获取字符直到获取到回车符为止{arr[i] = ch;ch = getchar();}*wei = ch;  //最后获取到的字符准备作为下一分组的第一个字符for (i = i; i < k; i++)arr[i] = 0;  //输入不够一组个数的整数倍则补零if (ch == '\n')  //接收到回车符返回0，否则为1return 0;elsereturn 1;
}int v=0;
void jiami(char *arr, int k, int e, int n)//加密 
{	while(v==0) {printf("\n密文为：\n");v++;}	int m = 0,c=1, i, j,t=0, shu,temp,num=0;int *array;for (i = 0; i < k; i++)     /*Mi赋值过程*/{temp = 1;for (j = 0; j < (k-i-1)*2; j++)temp = temp * 10;shu = (int)arr[i] - 97;m = m + temp * shu;}temp = e;do{	        /*获取e的二进制表达形式的位数*/temp = temp / 2;num++;} while (temp != 0);array = (int *)malloc(sizeof(int)*k);   //申请动态数组temp = e;for (i = 0; i < num; i++)	/*动态数组存储e的二进制表达形式*/{array[i] = temp % 2;temp = temp / 2;}for (i = num - 1; i >= 0; i--) //快速取模算法，避免出现天文数字{	t = t * 2;temp = c*c;if (temp > n){	for (j = 0; temp - n*j >= 0; j++);j--;c = temp - n*j;}elsec = temp;if (array[i] == 1){	t = t + 1;temp = c*m;if (temp > n){	for (j = 0; temp - n*j >= 0; j++);j--;c = temp - n*j;}elsec = temp;		}	e = e / 2;}temp = c;i = 0;do{	      /*c的位数小于分组长度则在前补零*/temp = temp / 10;i++;} while (temp != 0);for (i; i < num; i++)printf("0");printf("%d", c);
}int long_n(int n)//获取分组的长度
{int temp,i,j,k,shi,comp=0;temp = n;for (i = 1; temp / 10 != 0; i++)	/*获取n的位数*/{temp = temp / 10;}temp = i;if (i % 2 != 0)	/*若n的位数为基数*/{i = i - 1;return i;}else	/*若位数为偶数*/{for (j = 0; j < i/2; j++){shi = 1;for (k = 0; k < temp - 2; k++)shi = shi * 10;comp = comp + shi * 25;temp = temp - 2;}if (comp <= n)return i;else{i = i - 2;return i;}}
}/*主函数*/
int main()
{int p, q, e, d, n, fai_n, k, i,is_first=1;char ch,*arr,wei='a';printf("请输入两个不相等的素数p、q值:\n");scanf_s("%d", &p); primeNum(p);scanf_s("%d", &q); primeNum(q); n = p*q;  fai_n = (p-1)*(q-1);   //Φ(n)printf("\n请输入e值:\n");scanf_s("%d", &e);  coprime(fai_n,e);for (k = 0; (k*n + 1) % e != 0; k++);if ((k*n + 1) % e == 0)d = (k*n + 1) / e;  //d * e ≡ 1 (mod Φ(n))k = long_n(n);k = k / 2;  //分组的长度ch = getchar(); //缓冲回车符arr = (char *)malloc(sizeof(char)*k);  //申请动态数组printf("\n请输入明文：\n");while (1){i=shuru(arr,k,&wei,is_first);  //调用输入字符的函数，接收到回车符返回0，否则为1is_first = 0;  //第一分组录入结束设为0jiami(arr,k,e,n);  //调用加密函数if (i == 0)  //接收到返回值为0跳出循环break;}printf("\n");return 0;
}

4.3 运行结果

5. SHA-1算法

 5.1 SHA-1算法原理

    安全哈希算法（Secure Hash Algorithm）主要适用于数字签名标准（Digital Signature Standard DSS）里面定义的数字签名算法（Digital Signature Algorithm DSA）。对于长度小于2^64位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。

    SHA-1算法，全称Secure Hash Algorithm 1，是一种密码散列函数，由美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦资料处理标准（FIPS）。它可以生成一个被称为消息摘要的160位（20字节）散列值，通常以40个十六进制数的形式呈现。

    优点：①安全性较高：SHA-1算法的哈希函数具有不可逆性，因此被广泛应用于数字签名和数据完整性校验等领域。②哈希速度较快：由于SHA-1算法中的运算相对简单，其哈希速度相对较快。

    缺点：①安全性不足：近年来，SHA-1算法的安全性受到了挑战。据报道，SHA-1算法存在多个漏洞，可能会被攻击者利用。②容易受到碰撞攻击：碰撞攻击是指两个不同的输入通过哈希函数得到相同的输出。SHA-1算法虽然相对抵抗碰撞攻击，但并非完全免疫。

5.2 代码

#include<stdio.h>
#include <string.h>
#include <conio.h>
#include <wtypes.h>
void creat_w(unsigned char input[64],unsigned long w[80])//分组处理 
{int i,j;unsigned long temp,temp1;for(i=0;i<16;i++)//将 Mi 分成16个32bit数据 W0, W1, … , W15。 {j=4*i;w[i]=((long)input[j])<<24 |((long)input[1+j])<<16|((long)input[2+j])<<8|((long)input[3+j])<<0;}for(i=16;i<80;i++)//对于 t=16到79 令 Wt=S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16).{w[i]=w[i-16]^w[i-14]^w[i-8]^w[i-3];temp=w[i]<<1;temp1=w[i]>>31;w[i]=temp|temp1;}
}
char ms_len(long a,char intput[64]) 
{unsigned long temp3,p1;  int i,j;temp3=0;p1=~(~temp3<<8);for(i=0;i<4;i++){j=8*i;intput[63-i]=(char)((a&(p1<<j))>>j);}return '0';
}
int main(int argc, int* argv[])//计算消息摘要
{unsigned long H0=0x67452301,H1=0xefcdab89,//5个寄存器的缓冲区初始化 H2=0x98badcfe,H3=0x10325476,H4=0xc3d2e1f0;unsigned long A,B,C,D,E,temp,temp1,temp2,temp3,k,f;int i,flag;unsigned long w[80];unsigned char input[64]; long x;int n;printf("input message:\n");scanf("%s",input);n=strlen((LPSTR)input);if(n<57)//字符串扩充 {x=n*8;ms_len(x,(char*)input);if(n==56)for(i=n;i<60;i++)input[i]=0;else{input[n]=128;for(i=n+1;i<60;i++)input[i]=0;}}creat_w(input,w);printf("\n");A=H0;B=H1;C=H2;D=H3;E=H4;for(i=0;i<80;i++)//每次循环开始将H寄存器数据拷贝到ABCDE寄存器，计算结束后累加到H寄存器，然后进入下一轮计算，{flag=i/20;switch(flag)//在SHA1中需要一系列的函数 Ft(0<=t<= 79)都操作32位数据B，C，D并且产生32位数据作为输出。 {case 0: k=0x5a827999;f=(B&C)|(~B&D);break;case 1: k=0x6ed9eba1;f=B^C^D;break;case 2: k=0x8f1bbcdc;f=(B&C)|(B&D)|(C&D);break;case 3: k=0xca62c1d6;f=B^C^D;break;}temp1=A<<5;temp2=A>>27;temp3=temp1|temp2;temp=temp3+f+E+w[i]+k;//循环计算 E=D;D=C;temp1=B<<30;temp2=B>>2;C=temp1|temp2;B=A;A=temp;}H0=H0+A;  H1=H1+B;  H2=H2+C;  H3=H3+D;  H4=H4+E;printf("output hash value:\n");printf("%lx%lx%lx%lx%lx",H0,H1,H2,H3,H4);getch();
}

5.3 运行结果

与SHA-1在线加密工具的结果做对比：