0%

仿射密码算法记录

最近写了C语言的大作业,其中有一些个人的改进,让我觉得可以写一篇博客来记录一下。

简介

大作业的要求是编程实现仿射密码的加密和解密,仿射密码是什么自行百度,这篇博客主要内容就两个

  • 求a模n的乘法拟元
  • 加解密函数的一种通用化改进

乘法逆元

a模b的乘法逆元表示如下 $(ax)%b=1$,x就是a的乘法逆元,上面式子可以变成一个方程,$ax=by+1$,求逆元就是解出x和y。

扩展欧几里得算法

已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式 $ax+by=gcd(a,b)$

如果a和b互质,上式就可以转化为$ax=-by+1$,几乎就是乘法逆元的形式了,所以可以用扩展欧几里得算法来求出x和y。

递归实现

网上几乎所有的扩展欧几里得算法都是递归实现的,而且递归的实现很不好描述,这里直接放一篇网上的文章算法学习笔记(8):拓展欧几里得

迭代实现

如果只是贴别人的文章那就太敷衍了,而且我就不会写这篇文章了,所以重点是这个。

这还得从我翻百度百科:扩展欧几里得算法的时候说起,我看见了这个
初等变换
然后思路一下就打开了,这不比用递归的方法好直观多了,只要开一个2x3的数组,然后辗转相减直到a或b变成gcd(a,b),它所在的那一列下面的两个分量就是所求的x和y,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int inv(int a,int b){
int m[2][3]={
{a,1,0},
{b,0,1}
};
for(int i=0,j=1;m[i][0];i^=1,j^=1){
int k=m[i][0]/m[j][0];
m[i][0]%=m[j][0];
m[i][1]-=k*m[j][1];
m[i][2]-=k*m[j][2];
if(m[i][0]==1)
return (m[i][1]+b)%b;
}
return -1;
}

返回-1是没有a和b不互质的情况,如果确保传入的a和b合法可以修改for的条件直接在外面返回。注意,求出来的逆元有可能是个负数,所以需要加上b之后再取余,确保是正数。

加解密函数改进

这是一个数学问题,这是我在尝试压行的时候发现的。
首先我们来看看原版的加解密函数是什么样
$$
c_i=(\alpha p_i+\beta)%n
p_i=\alpha^{-1}(c_i-\beta)%n
$$
不难发现,上面其实都是一次函数,所以可以把它们化成标准形式,加密函数已经是标准形式了,所以主要就是解密函数。这里有一点需要注意,如果$\beta$比$c_i$大,那会出现负数。
$$
p_i=\alpha^{-1}(c_i-\beta)%n
=\alpha^{-1}(c_i+(26-\beta))%n
=(\alpha^{-1}c_i+\alpha^{-1}(26-\beta))%n
$$
所以我们只需要写一个求解一次函数的函数,然后加密或者解密其实就是传入的参数不同,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int f(int a,int b,int x){
return a*x+b;
}
char trans(int a,int b,char ch){
if(ch>='A'&&ch<='Z')
return 'A'+(f(a,b,ch-'A')%26);
else if(ch>='a'&&ch<='z')
return 'a'+(f(a,b,ch-'a')%26);
return ch;
}
char C(int a,int b,char ch){
return trans(a,b,ch);
}
char P(int a,int b,char ch){
a=inv(a,26);
b=a*(26-b);
return trans(a,b,ch);
}

代码仅作为参考,我分这么多个函数只是为了看起来清晰一点,每个函数只做一件事,实际上完全可以把f和trans合起来,然加密和解密函数直接写成宏的形式,总之写法有很多,取决于每个人的风格吧。

结尾

写完这两个算法,大作业就差不多了,剩下的就是些交互程序的写法,这些都好写,之后我可能会写篇迭代版求乘法逆元的优化。