一个博客

随便写写

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合起来，然加密和解密函数直接写成宏的形式，总之写法有很多，取决于每个人的风格吧。

结尾

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