密码学精简版

密码学是数学上的一个分支，同时也是计算机安全方向上很重要的一个原理，设置密码的目的是保证信息的机密性、完整性和不可抵赖性，安全方向上另外的功能——可用性则无法保证。

密码的发展也已由来已久，最早的密码可追溯到罗马时期，计算机诞生前的密码学都称为古典密码，现代密码则分为对称加密和非对称加密两两种，根本区别是解密使用的密钥，对称加密使用同一个密钥进行加密解密，非对称加密使用公钥加密，私钥解密，本文将对主流的算法进行简单介绍，基础概念可见密码算法的概念

古典密码

相关背景和知识也蛮有意思，基本是古代希腊和罗马时因为行政和战争的需要发展而来，详细可见该密码学发展简史和古典密码算法。

数学算法上的最早加密方法是凯撒加密，采用字母后移k位的方法生成密文，数学表示位a+k=m，这种方法如果知道原理其实只要暴力26次就破解了。

仿射密码采用移位密码和乘数密码的组合，字母在移位前先乘一个数，数学表示位ax+b(mod 26)=m，解密过程涉及逆元计算，仅作了解即可，详细方法见仿射密码。

弗吉尼亚密码是凯撒的改进，使用一个字符串进行加密，如code分别对应字母位置3 15 4 5，字母循环与这四个值相加加密。该方法的密钥破解有些困难，但因为密钥固定，而统计分析上句子出现字母频率的排序大致固定，如最常出现的是字母e，若统计中一个字母出现此处最多，则可推断其为e。但因为循环加密，特定字母的统计信息没有决定性作用，此时也可以通过词频统计，详细破解方法可见弗吉尼亚原理及破解。

对称密码

随着计算机的诞生，算力极大增强，古典密码用人手工来算可能很麻烦，但就几十上百种可能性对计算机来说实在是洒洒水，所以产生了保密性更强的对称密码。

DES—数据加密标准

Data Encryption Standard，即数据加密标准，是一种使用密钥加密的块算法。与流密码逐字节加密类似，DES是分组加密的应用，即将明文分成字节块，分别加密后再组合。

DES设计中使用了分组密码设计的两个原则：混淆（confusion）和扩散(diffusion)，其目的是抗击敌手对密码系统的统计分析。混淆是使密文的统计特性与密钥的取值之间的关系尽可能复杂化，以使密钥和明文以及密文之间的依赖性对密码分析者来说是无法利用的。扩散的作用就是将每一位明文的影响尽可能迅速地作用到较多的输出密文位中，以便在大量的密文中消除明文的统计结构，并且使每一位密钥的影响尽可能迅速地扩展到较多的密文位中，以防对密钥进行逐段破译。

DES将数据分为64位的数据块，与64位的密钥进行运算加密，大致流程图如下：

各步流程为：
1，明文经过IP表置换扩散；
2，分为32位的$L_0$和$R_1$；
3，$L_1=R_0$，$R_1=L_0与R_0加密结果的异或$；
4，上述过程重复16次，实现混淆目的；
5，获得$L_{1}6和R_{1}6$；
6，IP表逆置换获得密文。

详细说明如下：

明文首先经过IP置换，打乱原有顺序，即将对应序列的值移动到表的位置，置换表与逆置换表如下：

加密F函数过程如下：
1，E扩展，将32位的数据扩展为48位；
将32位数据分成8组，每行四位，每组的前后分别加上该位的上一个字符和下一个字符，就是增加两列，如图所示：

2，与48位的密钥异或运算；
3，经S盒压缩数据到32位；
将数据分为8块，每块6位数据，6进4出，每块的头尾两个数转化成十进制数作为列数，中间四个数转化为十进制数作为行数，到S盒中对应查找转化，S盒有8个，进一步增加了保密性，S1盒如下图：

这一步是算法中唯一非线性的，最直接的扩散手段。
4，P盒置换32位到32位，是再一次的混淆盒扩散过程。

再与L异或生成新的R。

最后讲密钥是如何生成的，64位密钥56位参与运算，8位校验位，分别为8，16，24，32，48，64，如何获取56位参与运算？
56位密钥先经过PC1表置换打乱顺序，前28为作为$C$后28为作为$D$，然后移位，具体不记得了，但也无伤大雅，再使用PC2表从56位中选48位用于运算。

DES折腾这么多遍，这表那表的，总结起来其实就是两个目的：
1，增加密钥复杂性，减少与密文关联性。又算又选的，让攻击者很难推出具体是那些数字受影响了，从而也就无法从密钥入手破解密文；
2，减少统计分析特征。不断从盒里选取匹配规则，明文多次打乱顺序重新组合，为的就是避免被统计分析猜出可能的字母或单词，减少统计分析破解的可能。

使用在线网站加密输出如下：

该部分详细内容可见DES核心内容。

AES—高级加密标准

在DES已经被证明不安全的情境下，创造出来替代DES的，也说明到目前为止，AES还是安全的。

该分组密码算法需要明文长度128，密钥长度可以是128、192和256，分别需要进行10、12、14轮计算。该算法将128位明文分成4×4的矩阵，每个块内8位明文，经过初始变换后经过9轮循环(字节代换、行移位、列混合、轮密钥加)，最后再经过一轮计算(字节代换、行移位、轮密钥加)后就输出密文，大致流程图如下：

下面对一些操作详细讲解：
1，初始变换。只需要将明文与密文进行异或操作。
2，字节代换。S盒代换，每个块内8位数据，高4位作为行，低4位作为列，在S盒对应位置替换。
3，行移位。左循环移位，第一行不变，第二行左移一位，第三行左移两位，第四行左移三位。
4，列混合，也称列混淆。该部分是AES中最复杂的部分，左乘一个给定矩阵，但该乘法部署矩阵点积运算，而是基于有限域的计算方法，将点积运算中的+改为异或操作，×转为二进制，即$00000010\ast (a_7,a_6...a_0)$，结果为分段函数，当$a_6{a}_5..a_{0}0，a_7=0$，$(a_6{a}_5..a_{0}0)异或(00000010),a_7=1$
5，轮密钥加。该部分主要涉及轮密钥的生成步骤，即由密钥生成10轮密钥。
原密钥分为$w_0,w_1,w_2,w_3$四个列，计算新的$w_i$使用$w_{[i]}=w_{[i-4]}异或w_{[i-1]}，当i不是4的倍数，即w_5=w_1异或w_4$，当$i是四的倍数，w_{[i]}=w[i-4]异或T(w[i-1])$，其中T函数又分为如下步骤：
字循环，4个字节上移一个字节；
字节代换，即S盒代换；
常量异或，给定常量的第j列进行异或，j为当前进行的第j轮。

到此AES密文就可以生成了，更多详细内容可见AES加密算法，写的真的hin好。

同样在线工具生成如图：

非对称加密

现在更强更神奇的算法是公钥加密，私钥解密，这种算法强度高，无需交换密钥，但是效率实在很低，比对称加密可能要慢一百倍，所以一般仅用于数字签名和密钥交换等领域。

密钥交换协议Diffie-Hellman

对称加密确实已经能保证安全了，但二者的密钥如何确定呢？密钥作为信息如果要在网上传递如何保证安全，再设置密钥保护吗？那这问题就没完没了，我猜是为了解决该问题，诞生了非对称加密。

非对称加密的图示如下：

二者公开选取素数q和原根a，并各自选取私钥$X_A和X_B$alice计算$Y_A=a^{X_A}modq$，Bob计算$Y_B=a^{X_B}modq$，二者互相发送消息，再分别计算幂次并取余，获得的就是密钥，这是二者获得的密钥相同，这是因为$(a^{x}modp{)}^{y}modp=a^{xy}modp$。

此时就算信道中有监听者获得了$Y_A，Y_B$，但因为离散对数难题，他也无法获知私钥，从而也无法获得最终的密钥K。

RSA

这应该是名气最大的一种加密算法了，几乎被人研究透了，当作学习范本再来研究一下吧。

一般流程为：
1，选择大素数p，q；
2，n=p*q；
3，n的欧拉函数，$\psi (n)=(p-1)\ast (n-1)$；
4，存在于$\psi (n)$互素的整数e，$1<e<\psi (n)$；
5，计算出e对$\psi (n)$的模反元素d；
6，公钥e，n
7，私钥d，n
明文M加密$M^{e}modn=C$，密文C解密$C^{d}modn=M$

该算法的安全性建立在离散对数难题的基础上，即$x=a^{y}modp$当p很大时很难求出y。

数学原理一个个解释，首先是欧拉函数及计算：
欧拉函数指小于n的正整数中，与n互素的数的个数，如果n为素数，$\psi (n)=n-1$，n如果能分解为两个素数之积，即$\psi(n)=\psi(pq)=\psi§\psi(q)=(p-1)*(q-1)$1

模反元素指，当e与$\psi (n)$互素，一定有一个整数d使$ed-1被\psi (n)$整除，d为e的模反元素，即$ed-1=k\psi (n)$。

证明私钥能解密：
$C^{d}modn=(M^{e}modn{)}^{d}modn=M^{ed}modnmodn=M^{k\psi (n)}Mmodn$
因为n是很大的数，如果$M^{k\psi (n)}=1$，上式取余的结果就是M，该步骤可由费马小定理证明，且涉及一些数论的知识，详细可见RSA中的数论基础，笔者作为了解，选择只记住结论。

ECC椭圆曲线

椭圆曲线指$y^2=x^3+ax+b,4a^3+27b^2!=0$的方程。

椭圆曲线困难问题

该问题与离散对数和大数分解等问题不同，椭圆曲线利用数形结合的思想建立困难问题，数学形式表达为$Q=kP$，其中P为基点，Q为公钥，k为私钥，但$kP$不是简单数乘运算，而是在椭圆曲线上先建立直线，再找对称点，A+B的示例图如下：
连接AB取与椭圆曲线的交点，再找关于x轴的对称点作为A+B的结果

如果是A+A时就是A点的切线与椭圆曲线的交点，n个A求和时，下一个落点并没有什么规律，也就是已知A计算nA是简单的，但已知nA求n是复杂的，这是椭圆曲线密码安全性的基础，部分落点展示如下图：

椭圆曲线加解密过程

1，选取椭圆曲线$Ep(a,b)$上的一个点作为基点
2，选大数k作为私钥，生成公钥$Q=kP$
3，选取随机数r，密文C明文M，加密$C=(rP，M+rQ)$，密文是一个点对
4，解密$M+rQ-k(rP)=M+r(kP)-k(rP)=M$

后续还有复杂的数学理论知识，感兴趣可以看椭圆曲线加密算法。

SM2

SM2是我国根据椭圆曲线制定的国家密码标准，相关文件链接可见密码管理局，具体包括数字签名协议，密钥交换协议和公钥密码算法，本文将介绍公钥密码算法。

SM2的私钥为$d_B$，公钥$p_B=[d_B]G$，klen为明文长度，G为基点，该方法正向易求，反向难求$d_B$，加密过程如下：
1，密文$C=C_1||C_3||C_2$，即三部分的拼接，明文M，下面将分别计算$C_i$
2，$C_1=[k]G$
3，$C_3=Hash(x||M||y),(x,y)=[k]p_B$，拼接一段hash值
4，$C_2=M\oplus t，t=KDF(x||y||klen)$，KDF为密钥派生函数，用于共享秘密比特串中派生出密钥数据，该函数又需要使用密码杂凑算法$H_2$，具体见下图文件：

详细方法都在官方文档中，有兴趣可进一步研究。

哈希函数—SHA1

英文为hash，音译为哈希，也称作散列函数，目的是将不等长的数据转化为等长输出，详细原理可见常见的hash算法及原理。简单来说就是将数据通过哈希函数，映射到类似数组结构的哈希表上，因为数据多可能产生同样的序号，如何处理冲突的哈希值是哈希函数的关键。

通常的哈希是不需要密钥的，只根据消息计算摘要，而几乎不可能逆向推出原消息，可用于验证完整性，该方法还可用于签名等安全机制，消息或文件先进行哈希计算摘要，再使用私钥加密哈希值，接收者公钥解密，重新计算哈希值并比较，一致则说明未被修改过。

MD5易产生碰撞，产生了SHA1，但其安全性还不够，有了更安全但也更慢的SHA2，随着量子计算机的发展，SHA3甚至说可以应对量子计算机的威胁，这都太前端了，民用领域SHA1应该就很足够用了，所以笔者稍微学习了一下该算法。

SHA1中文名安全散列算法，输入一个0到$2^{64}$位的消息，固定输出160bit的消息摘要。

首先将明文进行补位，SHA1运算基于长度为512的明文分组，所以需要先将明文M补至512的整数倍，就算消息已经是512的倍数也需要补，直到满足$Lmod512=448$，余64位用于存消息长度。
具体补的形式是最后一位加1，其余位补足够的0。计算时使用多个512分组散列生成160bit摘要，并参与下一次运算，直到最后，类似链式计算，结构如下图：

具体运算需要4轮×20个步骤，产生160bit结果存于5个32位的连接变量中，a、b、c、d、e。详细步骤如下：

1，512位的块分为16×32的向量，$M[0]...M[15]$扩充到80×32的$W[0]...W[79]$。具体扩充方法为：
$W_t=M_t,0<t\le 15$
$W_t=ROT{L}^1(W_{t-3}\oplus W_{t-8}\oplus W_{t-14}\oplus W_{t-16}),16\le t\le 79$，即异或后左移一位。

2，89轮运算

for t=0 to 79{
	T=a左移+f(b,c,d)+kt+wt
	e=d
	d=c
	c=b左移30位
	b=a
	a=T
	}

其中kt是常量，对应t不同取值不同，ft为分段函数运算。最终$H_i=a/b/c..+H_i$实现更新迭代。

总结

本章学习了密码学的两大分类，对称密码和非对称密码，对称密码现在就用AES，非对称最安全的是椭圆曲线，详细实现过程这换那换的其实很麻烦，非数学专业很难理解也记不住，学习算法特性和应用场景即可。

对称密码基本能实现信息的保护，但因为密钥作为信息也要在网络中传递，为了保证密钥的安全，需要使用非对称密码，此外非对称密码还可以实现数字签名鉴权过程。不同于加密过程，散列将不等长消息输出等长摘要，可用于验证完整性。

虽然说是第二次学，但这次零零散散也算折腾八小时，很多算法的具体步骤和原理并没有搞清楚，涉及到较为深入的数论知识实在让人头大。作为一般的程序开发者，甚至安全人员的从业者了解到这也基本够了。