密码学笔记（一）古典密码

密码学的阶段划分

密码学的发展按照其对算法和秘钥的保密程度大致可以分为如下三个阶段。

• 古典密码阶段（1949年前）
  在这个阶段算法和秘钥都是保密的，秘钥空间较小，信息的安全性主要依赖于对于加密和解密算法的保密。
• 对称密码阶段（1949-1975年）
  在这之后就进入到了现代密码学的阶段，和古典密码阶段的主要区别在于这个阶段的加密和解密算法无需保密，信息的安全性主要依赖于对秘钥的保密。需要解决的主要问题是在不可信信道下的秘钥传输问题。
• 公钥密码阶段（1976年-至今）
  在公钥密码阶段，加密秘钥（公钥）可以公开，仅对解密秘钥（私钥）保密，基于一些数学难题保证很难通过公钥推出私钥。

数学知识

• 整除与约简
• 同余
• 素数的相关性质
  每一个正整数都可以分解为一系列素数的乘积，且这种分解是唯一的。

$n=p_1^{e_1}+p_2^{e_2}...p_m^{e_m}\quad e_i>0,i=1,2,....m$

• 欧几里得算法和拓展欧几里得算法
  欧几里得算法（辗转相除法）略
  在学拓展欧几里得算法的时候遇到了一些困难就多记一下了。
  先说一条定理：对于任意x和y不同时为0的整数，x和y的最大公因子（x，y）是以$ax+by$表示的最小整数。
  而拓展欧几里得算法就是用来求这个a和b的。下图是计算方法的推导过程：
  
  通过上面的推导可以写出下面这样的一个式子：

$\left[ \begin{matrix} 0 & 1 \\ 1 & -q_n \\ \end{matrix} \right] \left[ \begin{matrix} 0 & 1 \\ 1 & -q_{n-1} \\ \end{matrix} \right] ... \left[ \begin{matrix} 0 & 1 \\ 1 & -q_1 \\ \end{matrix} \right] \left[ \begin{matrix} x \\ y\\ \end{matrix} \right] = \left[ \begin{matrix} gcd(x,y)\\ 0 \\ \end{matrix} \right]$

将矩阵相乘即可求得a，b，根据求解方向的不同可以得到递归和非递归的算法，矩阵从左向右算为递归算法（从左向右也可以写成非递归算法，不过需要一个数组记录$q_n$），矩阵从右向左算法为非递归算法。
递归算法实现：

void exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return;
}

非递归算法一实现

void exgcd(int m,int n,int &x,int &y)
{
    int r=1;
    vector<int> qList;
    while (r!=0){          //循环计算q并放入vector中
        r=m%n;
        int q=m/n;
        qList.push_back(q);
        m=n;
        n=r;
    }
    int listSize=qList.size();
    x=0;
    y=1;
    for(int i=listSize-2;i>=0;--i){ //计算x，y
        int tempX=x;
        x=y;
        y=tempX-y*qList[i];
    }
}

非递归算法二实现：

void exgcd(int m,int n,int &x,int &y)
{
    int x1,y1,x0,y0;
    x0=1; y0=0;
    x1=0; y1=1;
    x=0; y=1;
    int r=m%n;
    int q=(m-r)/n;
    while(r)
    {
        x=x0-q*x1; y=y0-q*y1;
        x0=x1; y0=y1;
        x1=x; y1=y;
        m=n; n=r; r=m%n;
        q=(m-r)/n;
    }
}

• 乘法逆元
  定义：n模m的乘法逆t记做（$n^{-1}\%m$）满足nt%m=1
  乘法逆存在的条件：（n，m）=1
  简单证明：
  nt%m=1 =>nt=km+1
  (km+1,km)=1 => (km+1,m)=1 =>(nt,m)=1
  (n*t,m)=1 =>(n,m)=1
  得证
  计算乘法逆的方法：使用拓展欧几里得算法求得an+bm=1,则a为其乘法逆。

古典密码学-代替密码

密码学中对信息进行处理的主要方式有两种换位和代替，顾名思义换位就是将原有的明文字符的顺序打乱，而代替则是按照一定的规律将明文字符替换成一些其他的字符。按照处理方式的不同，具体的分类如下图所示（盗的上课ppt上的图(◔◡◔)）：
　　
　　下面就分别介绍一些常见的古典密码的实现。

Caesar 密码

Caesar 密码非常简单，它的一般表达式如下所示：

$\begin{array}{l} y=f(x)=(x+k) \% 26 \text { (加密 }) \\ x=f(y)=(y-k) \% 26 \text { (解密 }) \end{array}$

Caesar密码的加密秘钥k和解密秘钥是相同的，同时秘钥空间的大小为25，通过不断尝试k的数值我们可以非常轻易的得到秘钥。

仿射密码

由于Caesar 密码的秘钥空间较小，通过增加参数提升秘钥空间大小就得到了仿射密码。

$\begin{array}{c} y=E_{a, b}(x)=(a x+b) \% 26 \text { (加密 }) \\ y=D_{a, b}=\left(a^{-1} y-a^{-1} b\right) \% 26 \text { ( 解密 }) \end{array}$

通过分析我们可以知道其秘钥空间大小为311，其计算公式为12*26-1。12表示的是a的可能性，因为a模26的乘法逆必须存在，所以其值为φ(26)，26为b的可能性，减一是a=1，b=0的特殊情况。仿射密码的秘钥长度虽然得到扩大但是依然有限，同时其本质上依然为单表代替密码，密文中依然保留着明文中字符的统计规律，易被破解。

Vignere密码

Vignere的多表代替密码中最著名的也是最简单，它本质上不过是多个Caesar密码组合，每隔一位就换一个Caesar密码的秘钥，直到结束又开始循环，其秘钥序列表示为：$K=k_0,K_1,K_2,...K_{m-1}$，可以看出Caesar密码是Vignere密码秘钥长度为1时的特殊情况，具体加解密公式如下：

$\begin{array}{l} y_{i}=\left(x_{i}+k_{i \% m}\right) \% 26 \text { (加密) } \\ x_{i}=\left(y_{i}-k_{i \% m}\right) \% 26 \text { (解密 }) \end{array}$

可以看出Vignere密码的秘钥空间为$26^m$,秘钥空间可以说是非常大了，但是因为其还是保留许多频率分布的特征，通过Kasiski测试法和重合指数攻击在秘钥不大长的情况下可以比较简单的进行破解，对多表替代密码的攻击方式下次再写。

OTP密码（一次一密密码）

算法原理：加密的秘钥和明文一样长，而且秘钥本身只使用一次。具体的加密方式可以任意可以是Vignere密码也可以是Vernam密码。
　　一次一密密码在理论上保证了信息的完全安全，因为任意一段有意义的明文都会对于一段唯一的秘钥，而攻击者如果采用穷举攻击的方式，将会得到大量有意义的明文，攻击者将无法判断哪个才是正确的。缺点：大规模随机秘钥的产生非常困难，同时更为麻烦的是秘钥的分发和保存。

古典密码-换位密码

换位密码顾名思义就是不改变明文中的字母仅改变明文中字母的次序，常见的方式有列移位加密，具体方式如下图所示：
　　
　　解密方式和加密方式类似。