Fork me on GitHub

加密算法初步学习(持续补充)

最近发现学的东西杂七杂八的,总是看到什么,觉得有意思,就查一下看看。像这次加密算法也是,这是个我应该不会去涉及的领域,毕竟我也不做后台数据库,也不玩python去破解什么东西,可能学了也没什么用。但兴趣来了,就学一学好了,总比整日一味刷着b站无聊的视频好多了。

最初用到加密算法,是和锎锎他们做一个英语学习平台应用,在对用户密码进行申请提交的时候,考虑到信息流安全性的问题,对密码进行了一个简单的MD5加密算法加密。我们在加密之前先在密码末尾加一串内部约定的字符串,再对密码进行加密,最后截取其中一部分字符串进行密码提交与登录匹配。这是我第一次对加密算法有了接触。后来在使用支付宝支付SDK集成的过程中,我又知道了Base64、RSA、SHA1、SHA2加密算法,前者是在提交支付信息时有进行加密,后三个则是对商户私钥公钥等的计算加密。不过,我完全不了解这些算法的加密原理和使用领域,今天来了兴趣,就查一下吧。至于加密算法代码的实现,以后再说。

前言

加密算法主要分为以下三类:

  • 对称加密算法

包括AES、DES、3DES等。加密和解密用到的密钥相同,加密速度快,适合经常发送数据的场所,但密钥传输需要格外注意。

  • 非对称加密\公钥加密算法

包括RSA、DSA、ECC等。加密和解密的密钥不同,加密方式通常采用数学难题所构造,加密速度慢,适合偶尔发送数据的场所,密钥传输方便。

  • 安全散列算法

包括MD5、SHA1、HMAC等。严格意义来说,加密算法需要满足加密与解密两个条件;而安全散列算法是不可逆的算法计算,所以其实不是加密算法之流。

Base64加密算法

第二次碰到Base64加密算法,是在金云天的个人简历博客看到的。当时不太懂,只是觉得联系方式那串字符串末尾有一个熟悉的”=”号,在查找加密算法的时候歪打正着的查到了Base64加密算法,也就有了初步的认识。起因说完了,现在就来学习一下加密原理。

加密原理

我们先拿到一个要加密的字符串,将单个字符先按照ASCII码表转换为对应的数字,再将数字转换为8位的二进制数。得到全部的二进制数后,按6位划分开来,得到一个6位二进制数的全新数列,此时,再将数列转换为10进制。转换完毕后,按照Base64索引表,将数字转换为对应的字符,这样就完成了转换。

下面我附上Base64的索引表:

加密过程

举例,以我的博客名称“QingMi”为要加密的字符串。我们先将QingMi转换为ASCII码表对应的数字:

81 105 110 103 77 105

再转换为二进制:

01010001 01101001 01101110 01100111 01001101 01101001

将这个数列按6位一组划分开来:

010100 010110 100101 101110 011001 110100 110101 101001

转为十进制:

20 22 37 46 25 52 53 41

按照Base64索引表转换为字符:

UWluZ01p

跟在线转换的网站的结果对比了一下,没有问题。

但是,这个转换过程存在一个问题:8位的二进制按6位划分的时候,最后的末尾不足6位怎么办。不急,这里还是有解决方案的。我们还是拿“QingM”来举例,接着走一遍刚才的步骤:

81 105 110 103 77
01010001 01101001 01101110 01100111 01001101
010100 010110 100101 101110 011001 110100 1101

走到这一步的时候,我们就需要在末尾补足0了。

010100 010110 100101 101110 011001 110100 110100

但是,还没有结束。我们还需要对加密的字符串的长度进行一下除3求余计算。这里长度是5,除3余2。如果余2,则在补足0后,在数列后加一个000000,但此数列不参与索引表转换,在最后只转换为”=”号;如果余1,则加两个000000

那么此时,应当添加一个000000:

010100 010110 100101 101110 011001 110100 110100 000000

转换为:

20 22 37 46 25 52 52

末尾不参与索引表字符转换,直接在末尾添加一个”=”:

UWluZ00=

ok,转换完成。

用途

(我本不想讲用途的,但一想到以后若是与人谈论加密算法,却不知道用途,未免也太尴尬了些)

Base64编码在Java的Hibernate中有应用,也可用于HTTP环境下传递标识信息,但碍于”/“与”+”号在URL中会发生形式变化,不利于数据库数据的存储,所以有一些改进的Base64编码将最后的”/“与”+”号替换为”-“与”_”等。

RSA加密算法

在查RSA加密算法之前,我绝没有想到它竟然是如此重量级的安全加密算法。它的加密原理,跟我上一个查过的Base64加密算法原理相差如此之大,涉及了很多高数的算法,让我这个高数一般的人学起来简直头大的不行。但既然已经查了,那我就把看来的东西整理一下。

首先要学习RSA用到的四个数学概念。

理论知识准备

1、互质

如果两个正整数,没有除1以外的公约数,则这两个数是互质关系。并不一定只有质数之间才是互质关系,比如8和9,也是互质关系。

2、欧拉函数

给定一个正整数n,求在小于等于n的正整数之中,与n构成互质关系的数的个数。计算这个数的函数称作欧拉函数,公式用Φ(n)表示。

  • n=1时,$Φ(n)=1$

  • n是质数,则$Φ(n)=n-1$

  • n是质数的某一个次方,则$Φ(p^k)=p^k-p^(k-1)=p^k(1-\cfrac{1}{p})$

  • n可以分解为两互质整数之积,如$n=p_1p_2$,则$Φ(n)=Φ(p_1p_2)=Φ(p_1)Φ(p_2)$

  • 因为任意一个大于1的正整数,都可以写成一系列质数的积,即$n=p_1p_2……p_r$;

转换为$Φ(n)=Φ(p_1)Φ(p_2)……Φ(p_r)$;

最后得出$Φ(n)=n(1-\cfrac{1}{p_1})(1-\cfrac{1}{p_2})……(1-\cfrac{1}{p_r})$。

such as:$Φ(1323)=Φ(3^3*7^2)=1323(1-\cfrac{1}{3})(1-\cfrac{1}{7})=756$

3、欧拉定理

如果两个正整数a与n互质,则满足以下等式:

$a^Φ(n)≡1(mod n)$

这个等式的意思是,a的Φ(n)次方被n除的余数为1,或者说,a的Φ(n)次方减去1可以被n整除。

当两者互质,且n为质数的时候,欧拉定理又可以写成:

$a^(p-1)≡1(mod p)$

这个等式又可以成为费马小定理。

4、模反元素

如果两个正整数a和n互质,那么一定可以找到整数b,使得ab-1被n整除,即:

$ab≡1(mod n)$

此时b就成为a的模反元素。比如4与7互质,那么4的模反元素就是2+7k(k为整数)。欧拉定理有计算函数如下:

$a^Φ(n)=a*a^(Φ(n)-1)≡1(mod n)$

所以,$a^(Φ(n)-1)$就是a的模反元素。

秘钥生成步骤

1、随机选择两个不相等的质数,p与q

此处取59和83

2、计算这两个数的乘积n

59 * 83 = 4897

3、计算乘积的欧拉函数Φ(n)

Φ(4897)=58 * 82 = 4756

4、随机选择一个整数e,条件是1<e<Φ(n),且e与Φ(n)互质

此处取23

5、计算e与Φ(n)的模反元素d

$ed≡1(mod Φ(n))$

等价于 $ed - 1 = kΦ(n)$

得到 $ed + kΦ(n) = 1$ (不用在意k转换前后的符号,计算的时候代入符号转换即可)

代入数,得到 23d + 4756k = 1

采用扩展欧几里得算法求解,过程如下:

先用类似辗转相除法,做以下计算:

4756=23*206+18
23=18*1+5
18=5*3+3
5=3*1+2
3=2*1+1

然后改写成“余数等于”的形式:

18=4756+23*(-206)    //式1
5=23+18*(-1)        //式2
3=18+5*(-3)            //式3
2=5+3*(-1)            //式4
1=3+2*(-1)

然后开始“倒回来:计算:

1=3+2*(-1)
 =3+[5+3*(-1)]*(-1)                //代入式4
 =3*2+5*(-1)
 =[18+5*(-3)]*2+5*(-1)            //代入式3
 =18*2+5*(-7)
 =18*2+[23+18*(-1)]*(-7)        //代入式2
 =18*9+23*(-1)
 =[4756+23*(-206)]*9+23*(-7)    //代入式1
 =4756*9+23*(-1861)

到此可以得出,d=-1861,k=9。

(这方法对整数形式的二元一次方程真是一个万能解,流弊)

6、将n和e封装成公钥,n和d封装成私钥

先回顾一下我们算过的所有有用的数:p=59,q=83,n=4897,Φ(4897)=4756,e=23,d=-1861

公钥用(n,e)表达,私钥用(n,d)表达,那么计算出来的公钥就是(4897,23),私钥为(4897,-1861)

7、加密与解密

费心费力的算了半天,还不知道这公钥私钥怎么用,我都感觉自己差不多白学了,所以这里就讲一下怎么用。

  • 加密

假设A向B发送信息m,A用公钥(n,e)进行加密。注意,m必须是证书且m<n。而加密,就是要算出下式的c:

$m^e=c(mod n)$

公钥是(4897,23),取m为7,则式为: $7^(23)≡c(mod 4897)$

计算得出:c=3855。那么3855就是加密后的数字,A把它给了B。

(这里我只能取个比较小的数。最开始取了个101,然后,101的23次方,计算器炸了,,,,,)

  • 解密

B拿到了3855,又有私钥(4897,-1861),那要怎么解密呢?代入以下等式计算:

$c^d=m(mod n)$

代入得 $3855^(-1861)≡m(mod 4897)$

emmmmmmm,等等,3855的-1861次方,这尼玛怎么算,等等,参考的博客是2790的2753次方,他怎么算的?芽儿哟,这怎么解啊。。。。。。这特么尴尬了,举了个例子结果有私钥都没法算,嗯……这大概就是RSA的安全性所在吧。。。。。

8、RSA的算法可靠性

维基百科这样说:“对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。”但维基百科又报道,到目前为止,并没有一种固定可靠的算法可以破解RSA算法。尽管如此,曾有暴力破解的方式破解过768位的秘钥,但花费时间漫长,从破解512位到768位花了漫长的10年。不过,普遍建议应将秘钥从1024位升级到2048位。

至于算法的安全性证明,我就不看了,光是上面这个次方计算都有点头疼。我知道有些算法可以优化次方运算,不过那是以后学习其他算法的事情了。原理明白就行了。想看安全性证明的,我在这里挂上参考博客链接。

RSA算法原理

MD5摘要算法

好吧,看来是Base64算法过于简单,让我产生了一部分算法都是简单的符号映射的错觉。在查阅MD5加密算法的资料过程中,MD5算法的过程运算让我更加头大。嘛,行吧,加密算法不难的话怎么能称为加密算法呢。

MD5算法是经由MD2、MD3、MD4发展而来。它的最大特点是,可以将任意长度的字节串变换成定长的字符串,现目前流行的有16位与32位。

原理

MD5算法是将输入的不定长度信息,输出固定长度为128-bits的算法。

数据填充

MD5算法对数据填充分两个步骤:

  • 1、填充信息至信息长度对512取模得448

填充方法:在信息后面填充一个1与无数个0,直至满足第一个条件

  • 2、在信息末尾添加信息长度的信息

看起来很绕,其实就是在上一步填充完的信息后,添加一个64位长度的二进制位数信息。这样一来,448+64=512,整个信息的长度还是可以被512整除的。这样做的话,在后面处理信息的时候也比较方便。

MD5会把信息以512位分组,再将每一分组划分为16个32位子分组。

数据计算

  • 四个被称作链接变量的常数:A=0x67452301,B=0xEFCDAB89,C=0x98BADCFE,D=0x10325476

分别赋予小写a、b、c、d

(常数值与部分博客有出入,但观察一下,发现四个常数值的数字顺序是有规律的颠倒放置,至于原因还不知道)

  • 四个非线性函数

F(X,Y,Z) = (X & Y) | (~X & Z)

G(X,Y,Z) = (X & Z) | (Y & ~Z)

H(X,Y,Z) = X ^ Y ^ Z

I(X,Y,Z) = Y ^ (X | ~Z)

准备完毕,下面就开始讲计算过程。

计算过程主要是四轮循环运算;每轮循环运算的次数,是512位信息分组的数目,即多少个32位信息组;每次运算,对a、b、c和d的其中三个做一次非线性函数运算,然后将所得结果加上第四个变量,文本信息的一个子分组,一个常数,将结果向右移一个不定的数,加上a、b、c、d其中之一,并用结果取代a、b、c、d之一。听起来很糊涂,那就看一下算式:

$F(a,b,c,d,M_j,s,t_i)表示a=b+(a+F(b,c,d)+M_j+t_i)<<$

其中$M_j$指文本信息子分组,$t_i$是常数,至于s,我猜是位移的数吧

这样经过几轮计算之后,将最后计算出来的a、b、c、d输出,就是最后的MD5值了。32位的MD5值是完整的计算结果,而16位的MD5值是截取的32位值的9~24位。

用途

1、常用作文件下载的核对,用于校验文件在下载过程中是否遭到不法程序篡改。

2、很多网站用来存储用户的密码,鉴于MD5算法的不可逆性,很难算出密码原文内容,所以经常用来做用户注册时密码的存储与登录时密码的核对。

3、数字签名。MD5也经常用作第三方认证机构的文件摘要信息比对,称“数字签名”。

PS:MD5算法现在已经不再完全可靠,已经有国内的科学院研究者破解了MD5的碰撞抵抗。

AES加密算法

查阅资料的时候,发现DES算法因已遭到破解,不再是安全的加密算法,所以又改换成学习AES加密算法。因为我实在看的有些困难,所以先贴上我参考的两篇比较好的详解博客。

AES加密算法的详细介绍与实现

密码算法详解——AES

加密原理

AES是一种区块加密算法,即分组加密,将明文分成多个等长的模块,直至加密完所有明文。AES标准规范中,分组只能是128位,即每个分组为16个字节。但密钥的长度可以选择128位、192位或256位,每个选择对应的推荐加密轮数也不同,如下所示:

加密步骤

因为过程很长,所以我先对整个过程做一个概要阐述:以AES-128举例,AES算法先将明文分组,每组被分为16个字节,用4x4的明文矩阵表示;然后将每组的明文矩阵转换为状态矩阵;然后进入AES的10轮加密,每轮加密均需要依次进行4个步骤,字节代换、行移位、列混合、轮密钥加(第一轮加密之前需先进行一次轮密钥加,最后一轮加密不需进行列混合);最后,将输出的加密过后的状态矩阵替换为字符串,得到的即是密文。解密的过程,则是将上述的加密过程逆向进行即可。流程如下图所示:

矩阵预处理

假设明文已被分好,第一组如下所示:

$$
\left[
\begin{matrix}
a & e & i & m \\
b & f & j & n \\
c & g & k & o \\
d & h & l & p
\end{matrix}
\right] \tag{1}
$$

先将矩阵转换为状态矩阵,方法是只需将字符串转换为对应的十六进制即可:

$$
\left[
\begin{matrix}
0x61 & 0x65 & 0x69 & 0x6D \\
0x62 & 0x66 & 0x6A & 0x6E \\
0x63 & 0x67 & 0x6B & 0x6F \\
0x64 & 0x68 & 0x6C & 0x70
\end{matrix}
\right] \tag{2}
$$

接下来该进行轮密钥加了。但考虑到我没办法进行10次加密运算,只能将每个步骤的计算方法讲清楚就行了,所以我把轮密钥加放在每轮的加密步骤中讲解。

字节代换

字节代换其实是一个查表替换字符的操作,AES算法为此定义了一个S盒和逆S盒(S盒与逆S盒的字符位置是固定的,是按照公式$$GF(2^8) = GF(2)[x]/(x^8 + x^4 + x^3 + x + 1)$$计算来的,有兴趣的可以去查一下)。表如下所示:

替换规则其实很简单:将原文的高4位作为行值,低4位作为列值,找到对应的元素,输出即可:

$$
\left[
\begin{matrix}
0xEF & 0x4D & 0xF9 & 0x3C \\
0xAA & 0x33 & 0x02 & 0x9F \\
0xFB & 0x85 & 0x7F & 0xA8 \\
0x43 & 0x45 & 0x50 & 0x51
\end{matrix}
\right] \tag{3}
$$

逆向解密则从逆S盒取值即可。

行移位

行移位是一个左循环移位操作。密钥长度为128位时,加密时,矩阵第0行左移0位,第1行左移1位,第2行左移2位,第3行左移3位。同理,解密时逆向即可。

$$
\left[
\begin{matrix}
0xEF & 0x4D & 0xF9 & 0x3C \\
0x33 & 0x02 & 0x9F & 0xAA \\
0x7F & 0xA8 & 0xFB & 0x85 \\
0x51 & 0x43 & 0x45 & 0x50
\end{matrix}
\right] \tag{4}
$$

列混合

列混合运算是将移位后的状态矩阵与固定的壶镇相乘,得到计算后的状态矩阵。固定矩阵如下:

$$
\left[
\begin{matrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02
\end{matrix}
\right] \tag{5}
$$

比如第一行第一列的元素的计算:

S=(20xEF)^0x4D^0xF9^(30x3C)

运算规则:1、对于2进制来说,乘以2即是将数左移一位。如果原数最高位为1,则需要在移位后再同(0001 1011)进行异或运算,比如2*0xEF:

EF转换为二进制即为:1110 1111

乘2左移一位:1101 1110

因原最高位为1,故与0001 1011进行异或运算,得到:

1100 0101

这就是2*0xEF的运算结果。

2、对于乘3运算,需要用分配率来进行运算,如3*0x3C:

30x3C=(2+1)0011 1100=0111 1000^0011 1100=0100 0100

3、这样一来,就只剩下异或运算了,这就不用多说了吧:

1100 0101
0100 1101
1111 1001
0100 0100

得到结果:0011 0101

转换为十六进制即为:0x35

计算的过程如果手算那就太麻烦了,所以尽管可能多花了点时间,我还是写了点Java代码来实现计算:

public class Main {

    public static void main(String[] args) {

        //存放状态矩阵
        int a[][] = new int[][]{{0xEF,0x4D,0xF9,0x3C},{0x33,0x02,0x9F,0xAA},{0x7F,0xA8,0xFB,0x85},{0x51,0x43,0x45,0x50}};

        //存放要相乘的固定矩阵
        int b[][] = new int[][]{{2,3,1,1},{1,2,3,1},{1,1,2,3},{3,1,1,2}};

        //存放计算后的状态矩阵
        int c[][] = new int[4][4];

        //先将后状态矩阵赋值为0
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                c[i][j]=0;
            }
        }

        Main main = new Main();

        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                //为方便理解下面的循环,在这里列出16次计算时每次计算的公式
                //c[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j]+a[i][2]*c[2][j]+a[i][3]*b[3][j];
                int res = 0;
                for(int k=0;k<4;k++){
                    if(b[k][j]==2){
                        res = res ^ main.doubleCal(a[i][k]);
                    }else if(b[k][j]==3){
                        res = res ^ main.tripleCal(a[i][k]);
                    }else {
                        res = res ^ a[i][k];
                    }
                }
                c[i][j]=res;
            }
        }

        //输出计算后的状态矩阵
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                //Integer.toHexString方法,可将十进制转化为十六进制输出;十六进制转化为十进制则为Integer.parseInt方法
                System.out.print(Integer.toHexString(c[i][j])+"  ");
            }
            System.out.println("\n");
        }

    }

    //乘2运算的情况处理
    public int doubleCal(int a){
        //若a的最高位为1,即a大于127,则先移位,但移位不减值,故再减去超出8位的值,再与0001 1011,即27,进行异或运算
        if(a>127){
            a = a << 1;
            a -= 256;
            a = a ^ 27;
            return a;
        }else {
            a = a << 1;
            return a;
        }
    }

    //乘3运算的情况处理
    public int tripleCal(int a){
        a = doubleCal(a) ^ a;
        return a;
    }

}

最后计算出的结果是:

$$
\left[
\begin{matrix}
0x35 & 0x75 & 0xED & 0xCA \\
0x1E & 0x64 & 0xBA & 0xC4 \\
0x39 & 0xB4 & 0xF4 & 0xD0 \\
0x54 & 0x60 & 0x4E & 0x7D
\end{matrix}
\right] \tag{6}
$$

逆运算的话,则是乘以上述固定矩阵的逆矩阵即可,该逆矩阵如下:

$$
\left[
\begin{matrix}
0x0E & 0x0B & 0x0D & 0x09 \\
0x09 & 0x0E & 0x0B & 0x0D \\
0x0D & 0x09 & 0x0E & 0x0B \\
0x0B & 0x0D & 0x09 & 0x0E
\end{matrix}
\right] \tag{7}
$$

轮密钥加

轮密钥加则是将128位轮密钥同状态矩阵中的数据进行异或运算。密钥分成4组,每组32位字,状态矩阵取每列四个元素组成的32位字,依次对应进行异或运算,得到加密后的新状态矩阵。

在逆运算时,密钥不需改变,因为异或运算的特性,再次运算即可得到加密前的矩阵。

密钥扩展

有一项事情需要注意:每一轮异或运算的密钥是在不断变化的。接下来就是了解一下,密钥变化的规律。

假设密钥Key为”abcdefghijklmnop”,则有W[0]=”abcd”,W[1]=”efgh”,W[2]=”ijkl”,w[3]=”mnop”。这是在进行10轮加密之前,最初的加密密钥。而接下来10轮所用到的40个新列W[i],则以以下的规律计算:

1、如果i不是4的倍数

W[i]=W[i-4]^W[i-1]

2、如果i是4的倍数

W[i]=w[i-4]^T(W[i-1])

这里,T是一个由3部分组成的函数,包括字循环、字节代换和轮常量异或,分别如下:

a.字循环:将字节循环左移1个字节,如”abcd”变为”bcda”。

b.字节代换:这个不用多说,使用表为S盒。

c.轮常量异或:将值与轮常量进行异或,每一轮异或的值均不同,其表如下:

比如上述密钥可转化为”61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F 70”。那么4个初始值为:

W[0]=61 62 63 64

W[1]=65 66 67 68

W[2]=69 6A 6B 6C

W[3]=6D 6E 6F 70

求W[4]、W[5]、W[6]、W[7]

W[4]=w[0]^T(W[3])

T(W[3])计算步骤:

1、6D 6E 6F 70输出变为6E 6F 70 6D

2、在S盒中找到对应字节,输出9F A8 51 3C

3、第一轮加密异或的数组为01 00 00 00,运算后输出9E A8 51 3C。

所以T(W[3])=9E A8 51 3C。

所以 W[4]=61 62 63 64 ^ 9E A8 51 3C=FF CA 32 58

W[5]=W[1]^W[4]=65 66 67 68 ^ FF CA 32 58=99 AC 55 30

W[6]=W[2]^W[5]=69 6A 6B 6C ^ 99 AC 55 30=F0 C6 3E 5C

W[7]=W[3]^W[6]=6D 6E 6F 70 ^ F0 C6 3E 5C=9D A8 51 2C

将所有结果组合起来,即为第一轮的密钥:FF CA 32 58 99 AC 55 30 F0 C6 3E 5C 9D A8 51 2C

用途

介于DES算法已被破解的事实,很多文件开始向3DES和AES加密靠拢。AES加密算法也并非牢不可破,目前已有成功的对AES算法的尝试攻击,不过距离算法的正式破解,还有一些难度。此外也有一些不针对算法,而针对算法系统或是安全系统的旁道攻击,不过这些攻击,就都是算法研究的题外话了。

(哇,终于把这个AES写完了,累死了。)

后记

这几章算法我均只讲解了初步原理。在查询及亲自使用在线加密算法的时候,深感每个算法均有很多不同的模式,而这些模式在原理讲解的博客中均未提及,可能是在代码实现的过程中有所差异?不过鉴于目前我还不会过度深入代码的实现,所以就点到为止。

-------------本文结束感谢您的阅读-------------