密码学基础--仿射密码

 在仿射密码中，加密函数定义为：
e（x）=（ax+b）mod26
a，bZ。因为这样的函数被称为仿射函数，所以这样的密码体制也称为仿射密码（可以看出，当a=1时，其对应的正是移位密码）。

---

为了能对密文进行解密，必须保证所选用的仿射函数是一个单射函数。换句话说，对任意的Y∈Z，如下同余方程：
 ax+b≡y(mod26)
有唯一解。上述同余方程等价于
 ax≡y-b(mod26)
当y遍历Z~26~时，显然y-b亦遍历Z~26~，我们只需要研究同余方程ax≡y(mod26)即可（yZ）。
我们断言，以上同余方程有唯一解的充分必要条件是gcd(a，26）=1（这里的gcd表示最大公约数）。首先，假设gcd(a，26)=d>1。则同余方程ax≡0(mod26)至少有两个解，分别为x=0和x=26/d。这种情况下，加密函数不是一个单射函数，因此不能用来作为一个有效的加密函数。

---

定理：
设a∈Z，对任意的bZ，同余方程ax≡b(mod m)有唯一解x∈Z~m~的充分必要条件是gcd（a，m）=1。
因为26=2×13，故所有的与26互素的数为a=1,3,5，7,9，11,15,17,19,21,23，25。b的取值可为Z~26~中的任何一个数。因此，仿射密码的密钥空间为12×26=312（当然，这个密钥空间还是太小的）。

---

定义   设a>=1，m>=2且均为整数。如果gcd（a，m）=1，则称a与m互素。Z中所有与m互素的数的个数使用φ（m）来表示（这个函数称为欧拉函数）
和欧拉函数有关的一个数论中的著名结果是m的素数幂分解的形式给出φ（m）的值（一个整数p称为素数，如果它没有除1和p之外的因子。任一整数m>1都可以用唯一的方式分解成素数幂的乘积。例如60=2^2^×3×5和98=2×7^2^）

---

下面定理给出φ（m）值的计算公式。
定理 假定

m =  ()

这里均为素数且各不相同，>0，1in。则

φ（m）=  ( - )

由上面关于欧拉函数φ(m）值得计算公式可以推出，仿射密码的密钥空间的大小是mφ(m）。例如，如果m=60，φ(60）=2×2×4=16，那么仿射密码的密钥空间大小是60×16=960。

---

下面分析仿射密码在模26情形下的解密过程。已知有gcd（a，26）=1，解密的过程就是解同余方程y≡ax+b（mod26）。由此前的讨论，此同余方程在上只有唯一解，但是还需要有效的方法找出这个解。

首先，我们先给出乘法逆的概念。

定义    设a，若存在a'  ，使得aa'a'a=1(mod m)，则a'称为a在Z上的乘法逆，将其记为mod m。在m是固定的情形下，也可将其简记为。

可证明，a在Z上存在乘法逆，当且仅当gcd(a，m)=1，并且其逆如果存在，则必唯一。如果p为素数，则Z上任一非零元均有乘法逆存在，一个【环】如果满足这条性质，将其称为域。

考虑同余方程yax+b(mod26)。其等价于如下同余方程：

            axy-b(mod26)

因为gcd(a，26)=1，故a在上存在乘法逆元,有

            (ax)x(y-b)mod26(a)x1xx(mod26)

故有，x=（y-b）mod26。因此相应的解密变换为

            d(y)=(y-b)mod26

下面给出乘法逆的算法：(扩展的欧几里得算法）

例  求5关于模14的乘法逆元

辗转相除：14=5×2+4；5=4+1

逆推：1=5-4=5-（14-5×2）=5×3-14

因此，5关于模14的乘法逆元为3

来总结一下方法，假设要求a关于模m的乘法逆元，由定义进行辗转相除直到取到1，然后将等式化为1=a×b+/-m×c，其中b，c为整数。

---

密码体制 -- 仿射密码（Affine Cipher）

令P=C=Z，且

                       K={（a,b）Z×Z：gcd(a，26)=1}

对任意的K=（a，b）K，x，yZ，定义

                     e(x)=(ax+b)mod 26

和 

                     d(y)=(y-b)mod 26

---

例    设密钥K（7,3）。上述已知mod26=15。加密函数为

          e(x)=7x+3

相应的解密函数为

          d(y)=15(y-3)=15y-19

以上运算均是在Z上完成。下面来验证对任意的xZ，都有 d(e(x))=x：

          d(e(x))= d(7x+3)=15(7x+3)-19=x+45-19=x

使用上面的密钥，我们来加密明文hot。首先转换字母爱h，o，t为对应的模26下的数，分别为7,14,19.分别加密如下：

          （7×7+3）mod26=52mod26=0

          （7×14+3）mod26=101mod26=23

          （7×19+3）mod26=136mod26=6

所以三个密文字符为0,23,6，相应的密文应为AXG。 

---

仿射密码的密码分析

让我们首先看一个如何利用统计数据来尽心改密码分析的简单例子：仿射密码的分析。假设Oscar已经截获到了下列密文：

FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH

这条密文的频数分析表如下：

密文中出现的26字母的频数统计

字母	频数	字母	频数
A	2	N	1
B	1	O	1
C	0	P	2
D	7	Q	0
E	5	R	8
F	4	S	3
G	0	T	0
H	5	U	2
I	0	V	4
J	0	W	0
K	5	X	2
L	2	Y	1
M	2	Z	0

 

这条密文只有57个字母，但是已经可以分析仿射密码，最大频数字母是：R（8次），D（7次），E，H，K（各5次），S，F，V（各4次）。首先，我们猜想R是e的加密，而D是t的加密，因为e和t是英文字母表统计表出现频数最高的字母（详细表见另一篇博文“密码学基础--代换密码”）。以数字表达即为e(4)=17和e(19)=3，可得以下方程组：

            4a+b=17

           19a+b=13

解这个方程组可得唯一解a=6，b=19，但这是一个不合法的密钥，因为gcd(a，26）=2>1。

我们再猜测R是e的加密，而E是t的加密，同上计算得a=13，也不合法。

继续进行，我们猜测R是e的加密，K是t的加密，则有a=3，b=5，密钥合法，接下来我们来验证是否能得到有意义的明文串，解密得：

algorithmsarequitegeneraldefinitionsofarrithmeticprocesses

至此，我们得出了正确的密钥。