【C语言练习_1】用C语言实现仿射变换加/解密

1.什么是仿射密码？

• 由加法密码和乘法密码结合而成
• 加密算法：y≡a*x+b(mod26) //y为密文
• 解密算法：x≡a^-1 (y-b)(mod26) //x为明文
• a,b为密钥，a,b均与p互素; gcd(a,p)=1;gcd(b,p)=1
• a^-1为a在Z_m群的乘法逆元

2.代码

#include <stdio.h>
#include <string.h>

//加密
int encrypt(char* plaintext, char* ciphertext, int k1, int k2)
{
int i, z = 0;
int l = strlen(plaintext); //获取明文的长度
for (i = 0; i < l; i++)
    {
//判断大小写
if (plaintext[i] >= 'A' && plaintext[i] <= 'Z') {
ciphertext[z] = (k1 * (plaintext[i] - 'A') + k2) % 26 + 'A';
        }
else if (plaintext[i] >= 'a' && plaintext[i] <= 'z') {
ciphertext[z] = (k1 * (plaintext[i] - 'a') + k2) % 26 + 'a';
        }
else {  //判断是否是空格
ciphertext[z] = plaintext[i];
        }
z++;
    }
return 0;
}

//解密
int decrypt(char* plaintext, char* ciphertext, int k3, int k2)
{
int i, z = 0;
int l = strlen(plaintext); //获取明文的长度
for (i = 0; i < l; i++)
    {
//判断大小写
if (plaintext[i] >= 'A' && plaintext[i] <= 'Z') {
ciphertext[z] = (k3 * ((plaintext[i] - 'A') - k2)) % 26 + 'A';
if (k3 * ((plaintext[i] - 'A') - k2) < 0) {
ciphertext[z] = ciphertext[z] + 26;
            }
        }
else if (plaintext[i] >= 'a' && plaintext[i] <= 'z') {
ciphertext[z] = (k3 * ((plaintext[i] - 'a') - k2)) % 26 + 'a';
if (k3 * ((plaintext[i] - 'a') - k2) < 0) {  //处理负数
ciphertext[z] = ciphertext[z] + 26;
            }
        }
else {  //判断是否是空格
ciphertext[z] = plaintext[i];
        }
z++;
    }
return 0;
}

int main()
{
char plaintext[50] = "";
char ciphertext[50] = "";
int k1, k2, k3;
int type;
printf("请填写明文或者密文:\n");
scanf("%[^\n]", plaintext);
printf("请选择加密方式，输入1加密，输入2解密\n");
scanf("%d", &type);
if (type == 1) {
//加密
printf("请输入密钥k1\n");
scanf("%d", &k1);
printf("请输入密钥k2\n");
scanf("%d", &k2);
encrypt(plaintext, ciphertext, k1, k2);
printf("明文%s的密文为:%s\n", plaintext, ciphertext);
    }
else if (type == 2) {
//解密
printf("请输入密钥k1的逆元\n");
scanf("%d", &k3);
printf("请输入密钥k2\n");
scanf("%d", &k2);
decrypt(plaintext, ciphertext, k3, k2);
printf("密文%s的明文为:%s\n", plaintext, ciphertext);
    }
return 0;
}

运行结果：

3.什么是逆元？

(1)逆元

逆元就是在mod意义下，不能直接除以一个数，而要乘以它的逆元。

比如：a*b≡1(modp),那么a,b互为模p意义下的逆元，X/a=X*b。（a与b均与q互素）

(2)根据扩展的欧几里得算法求乘法逆元

给出正整数a和b，扩展的欧几里得算法可以计算a和b的最大公约数d，同时得到两个符号相反的整数x和y满足：d=gcd(a, b) = ax+by

若a与b互质，那么d=gcd(a, b)=1, 即 ax + by = 1, 于是 by = (-x)a+1

也即：by=1(mod a)，于是y即为b在模a意义下的乘法逆元。