应用密码学—(扩展)欧几里得、DES、RSA、SHA-1算法

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 扩展欧几里得原理

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

加密流程：

初始置换（Initial Permutation, IP）：首先，对明文块进行一个固定的置换，将64位明文按照一定规则重新排列。
循环迭代（Round）：接下来，数据块经过16轮完全相同的迭代运算，每轮包括以下步骤：
- 分组：将数据分为左右两半，每半32位。
- 扩展置换（Expansion）：左半部分经过扩展置换变为48位。
- 密钥混淆（Key Mixing）：扩展后的数据与经过密钥调度产生的本轮子密钥（48位）进行异或操作。
- S盒变换（Substitution）：结果被分割成8组6位数据，每组通过查S盒（替代盒）转换为4位，实现非线性变换。
- P盒变换（Permutation）：上述32位结果经过P盒进行重新排列。
- 左右合并：上述得到的32位结果与原始右半部分进行交换，然后与原始左半部分合并，准备进入下一轮迭代。
最终置换（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转四位string
 
string 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）置换，得P0
        it = exchange(it, P, P_SIZE);
 
        //P0与L0进行异或，得J0
        it = XOR(it, L[i-1]);
 
        //左右交换位置，即R1 = J0; L1 = R0
        L[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）置换，得P0
        it = exchange(it, P, P_SIZE);
 
        //P0与L0进行异或，得J0
        it = XOR(it, L[i-1]);
 
        //左右交换位置，即R1 = J0; L1 = R0
        L[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();
	else
		ch = *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，否则为1
		return 0;
	else
		return 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;
		}
		else
			c = 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;
			}
			else
				c = 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，否则为1
		is_first = 0;  //第一分组录入结束设为0
		jiami(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();
}