RSA 加密算法主要公式 草稿(加密运算公式)
RSA 加密算法主要公式 草稿(加密运算公式)
从一道计算题开始了解 RSA 非对称加密算法的主要公式。
下面是一道关于 RSA 计算的问题，比较简单，从这道题来学习和了解关于 RSA 非对称加密算法的相关知识，当然，具体关于 RSA 加密算法的知识不能仅限于以下问题，应该更全面的了解相关的知识。但是下面的问题已经把其中的重点算法的表现出来了。
下面是关于 RSA 的主要数学公式：
n = p * q
ø(n) = (p - 1) * (q - 1)
ed ≡ 1 mod ø(n)
c = m e mod n
m = c d mod n
其中两个 ** 是次方的意思
ed ≡ 1 mod ø(n)
3 * 7 ≡ 1 mod ø(n)
21 ≡ 1 mod ø(n)
ø(n) = 20
ø(n) = 2 * 10 = (p - 1) * (q - 1)
p, q = 3, 11
n = p * q = 3 * 11 = 3
c = m**e mod n = 6 ** 3 mod 33
6 ** 3
3 = 1 * (2 ** 0) + 1 * (2 ** 1)
t0 = 6 mod 33 = 6
t1 = 6 ** 2 mod 33 = 3
t0 * t1 mod n = 6 * 3 mod 33 = 18
因此 明文 6 的密文是 18
m = c ** d mod n = 18 ** 7 mod 33
t0 = 18 mod 33 = 18
t1 = 18 ** 2 mod 33 = 27
t2 = 27 ** 2 mod 33 = 3
t0 * t1 * t2 mod n = 18 * 27 * 3 mod 33 = 6
因此，密文 18 解密后是 6
前几天看到一句话，“我们中的很多人把一生中最灿烂的笑容大部分都献给了手机和电脑屏幕”。心中一惊，这说明了什么？手机和电脑已经成为了我们生活中的一部分，所以才会有最懂你的不是你，也不是你男朋友，而是大数据。
如此重要的个人数据，怎样才能保证其在互联网上的安全传输呢？当然要靠各种加密算法。说起加密算法，大家都知道有哈希、对称加密和非对称加密了。哈希是一个散列函数，具有不可逆操作；对称加密即加密和解密使用同一个密钥，而非对称加密加密和解密自然就是两个密钥了。稍微深入一些的，还要说出非对称加密算法有DES、3DES、RC4等，非对称加密算法自然就是RSA了。那么当我们聊起RSA时，我们又在聊些什么呢？今天笔者和大家一起探讨一下，有不足的地方，还望各位朋友多多提意见，共同进步。
RSA简介：1976年由麻省理工学院三位数学家共同提出的，为了纪念这一里程碑式的成就，就用他们三个人的名字首字母作为算法的命名。即 罗纳德·李维斯特 （Ron Rivest）、 阿迪·萨莫尔 （Adi Shamir）和 伦纳德·阿德曼 （Leonard Adleman）。
公钥：用于加密，验签。
私钥：解密，加签。
通常知道了公钥和私钥的用途以后，即可满足基本的聊天需求了。但是我们今天的主要任务是来探究一下RSA加解密的原理。
说起加密算法的原理部分，肯定与数学知识脱不了关系。
我们先来回忆几个数学知识：
φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。
这个公式主要是用来计算给定一个任意的正整数n，在小于等于n的正整数中，有多少个与n构成互质的关系。
其中n=A*B，A与B互为质数，但A与B本身并不要求为质数，可以继续展开，直至都为质数。
在最终分解完成后，即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之后，p1，p2，p3都是质数。又用到了欧拉函数的另一个特点，即当p是质数的时候，φp = p - 1。所以有了上面给出的欧拉定理公式。
举例看一下：
计算15的欧拉函数，因为15比较小，我们可以直接看一下，小于15的正整数有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互质的数有1、2、4、7、8、11、13、14一共四个。
对照我们刚才的欧拉定理： 。
其他感兴趣的，大家可以自己验证。
之所以要在这里介绍欧拉函数，我们在计算公钥和私钥时候，会用到。
如果两个正整数m 和 n 互质，那么m 的 φn 次方减1，可以被n整除。
其中 .
其中当n为质数时，那么 上面看到的公式就变成了
mod n 1.
这个公式也就是著名的 费马小定理 了。
如果两个正整数e和x互为质数，那么一定存在一个整数d，不止一个，使得 e*d - 1 可以被x整除，即 e * d mode x 1。则称 d 是 e 相对于 x的模反元素。
了解了上面所讲的欧拉函数、欧拉定理和模反元素后，就要来一些化学反应了，请看图：
上面这幅图的公式变化有没有没看明白的，没看明白的咱们评论区见哈。
最终我们得到了最重要的第5个公式的变形，即红色箭头后面的：
mod n m。
其中有几个关系，需要搞明白，m 与 n 互为质数，φn = x，d 是e相对于x的模反元素。
有没有看到一些加解密的雏形。
从 m 到 m。 这中间涵盖了从加密到解密的整个过程，但是缺少了我们想要的密文整个过程。
OK，下面引入本文的第四个数学公式：
我们来看一下整个交换流程：
1、客户端有一个数字13，服务端有一个数字15;
2、客户端通过计算 3的13次方 对 17 取余，得到数字12; 将12发送给服务端；同时服务端通过计算3的15次方，对17取余，得到数字6，将6发送给客户端。至此，整个交换过程完成。
3、服务端收到数字12以后，继续计算，12的15次方 对 17取余，得到 数字10。
4、客户端收到数字 6以后，继续计算，6的13次方 对 17 取余，得到数字 10。
有没有发现双方，最终得到了相同的内容10。但是这个数字10从来没有在网络过程中出现过。
好，讲到这里，可能有些人已经恍然大悟，这就是加密过程了，但是也有人会产生疑问，为什么要取数字3 和 17 呢，这里还牵涉到另一个数学知识，原根的问题。即3是17的原根。看图
有没有发现规律，3的1~16次方，对17取余，得到的整数是从1~16。这时我们称3为17的原根。也就是说上面的计算过程中有一组原根的关系。这是最早的迪菲赫尔曼秘钥交换算法。
解决了为什么取3和17的问题后，下面继续来看最终的RSA是如何产生的：
还记得我们上面提到的欧拉定理吗，其中 m 与 n 互为质数，n为质数，d 是 e 相对于 φn的模反元素。
当迪菲赫尔曼密钥交换算法碰上欧拉定理会产生什么呢？
我们得到下面的推论：
好，到这里我们是不是已经看到了整个的加密和解密过程了。
其中 m 是明文；c 是密文； n 和 e 为公钥；d 和 n 为私钥 。
其中几组数字的关系一定要明确：
1、d是e 相对于 φn 的模反元素，φn = n-1，即 e * d mod n = 1.
2、m 小于 n，上面在讲迪菲赫尔曼密钥交换算法时，提到原根的问题，在RSA加密算法中，对m和n并没有原根条件的约束。只要满足m与n互为质数，n为质数，且m n就可以了。
OK，上面就是RSA加密算法的原理了，经过上面几个数学公式的狂轰乱炸，是不是有点迷乱了，给大家一些时间理一下，后面会和大家一起来验证RSA算法以及RSA为什么安全。
我们以AES加密举例
AES简介
高级加密标准(AES,Advanced Encryption Standard)为最常见的对称加密算法(微信小程序加密传输就是用这个加密算法的)。对称加密算法也就是加密和解密用相同的密钥，具体的加密流程如下图：
下面简单介绍下各个部分的作用与意义：
明文P
没有经过加密的数据。
密钥K
用来加密明文的密码，在对称加密算法中，加密与解密的密钥是相同的。密钥为接收方与发送方协商产生，但不可以直接在网络上传输，否则会导致密钥泄漏，通常是通过非对称加密算法加密密钥，然后再通过网络传输给对方，或者直接面对面商量密钥。密钥是绝对不可以泄漏的，否则会被攻击者还原密文，窃取机密数据。
AES加密函数
设AES加密函数为E，则 C = E(K, P),其中P为明文，K为密钥，C为密文。也就是说，把明文P和密钥K作为加密函数的参数输入，则加密函数E会输出密文C。
密文C
经加密函数处理后的数据
AES解密函数
设AES解密函数为D，则 P = D(K, C),其中C为密文，K为密钥，P为明文。也就是说，把密文C和密钥K作为解密函数的参数输入，则解密函数会输出明文P。
在这里简单介绍下对称加密算法与非对称加密算法的区别。
对称加密算法
加密和解密用到的密钥是相同的，这种加密方式加密速度非常快，适合经常发送数据的场合。缺点是密钥的传输比较麻烦。
非对称加密算法
加密和解密用的密钥是不同的，这种加密方式是用数学上的难解问题构造的，通常加密解密的速度比较慢，适合偶尔发送数据的场合。优点是密钥传输方便。常见的非对称加密算法为RSA、ECC和EIGamal。
实际中，一般是通过RSA加密AES的密钥，传输到接收方，接收方解密得到AES密钥，然后发送方和接收方用AES密钥来通信。
本文下面AES原理的介绍参考自《现代密码学教程》，AES的实现在介绍完原理后开始。
AES的基本结构
AES为分组密码，分组密码也就是把明文分成一组一组的，每组长度相等，每次加密一组数据，直到加密完整个明文。在AES标准规范中，分组长度只能是128位，也就是说，每个分组为16个字节（每个字节8位）。密钥的长度可以使用128位、192位或256位。密钥的长度不同，推荐加密轮数也不同，如下表所示：
AES
密钥长度（32位比特字)
分组长度(32位比特字)
加密轮数
AES-128 4 4 10
AES-192 6 4 12
AES-256 8 4 14
轮数在下面介绍，这里实现的是AES-128，也就是密钥的长度为128位，加密轮数为10轮。
上面说到，AES的加密公式为C = E(K,P)，在加密函数E中，会执行一个轮函数，并且执行10次这个轮函数，这个轮函数的前9次执行的操作是一样的，只有第10次有所不同。也就是说，一个明文分组会被加密10轮。AES的核心就是实现一轮中的所有操作。
AES的处理单位是字节，128位的输入明文分组P和输入密钥K都被分成16个字节，分别记为P = P0 P1 … P15 和 K = K0 K1 … K15。如，明文分组为P = abcdefghijklmnop,其中的字符a对应P0，p对应P15。一般地，明文分组用字节为单位的正方形矩阵描述，称为状态矩阵。在算法的每一轮中，状态矩阵的内容不断发生变化，最后的结果作为密文输出。该矩阵中字节的排列顺序为从上到下、从左至右依次排列，如下图所示：
请点击输入图片描述
现在假设明文分组P为”abcdefghijklmnop”，则对应上面生成的状态矩阵图如下：
上图中，0x61为字符a的十六进制表示。可以看到，明文经过AES加密后，已经面目全非。
请点击输入图片描述
类似地，128位密钥也是用字节为单位的矩阵表示，矩阵的每一列被称为1个32位比特字。通过密钥编排函数该密钥矩阵被扩展成一个44个字组成的序列W[0],W[1], … ,W[43],该序列的前4个元素W[0],W[1],W[2],W[3]是原始密钥，用于加密运算中的初始密钥加（下面介绍）;后面40个字分为10组，每组4个字（128比特）分别用于10轮加密运算中的轮密钥加，如下图所示：
上图中，设K = “abcdefghijklmnop”，则K0 = a, K15 = p, W[0] = K0 K1 K2 K3 = “abcd”。
请点击输入图片描述
AES的整体结构如下图所示，其中的W[0,3]是指W[0]、W[1]、W[2]和W[3]串联组成的128位密钥。加密的第1轮到第9轮的轮函数一样，包括4个操作：字节代换、行位移、列混合和轮密钥加。最后一轮迭代不执行列混合。另外，在第一轮迭代之前，先将明文和原始密钥进行一次异或加密操作。
上图也展示了AES解密过程，解密过程仍为10轮，每一轮的操作是加密操作的逆操作。由于AES的4个轮操作都是可逆的，因此，解密操作的一轮就是顺序执行逆行移位、逆字节代换、轮密钥加和逆列混合。同加密操作类似，最后一轮不执行逆列混合，在第1轮解密之前，要执行1次密钥加操作。
请点击输入图片描述
下面分别介绍AES中一轮的4个操作阶段，这4分操作阶段使输入位得到充分的混淆。
一、字节代换
1.字节代换操作
AES的字节代换其实就是一个简单的查表操作。AES定义了一个S盒和一个逆S盒。
AES的S盒：
行/列
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0 0x63 0x7c 0x77 0x7b 0xf2 0x6b 0x6f 0xc5 0x30 0x01 0x67 0x2b 0xfe 0xd7 0xab 0x76
1 0xca 0x82 0xc9 0x7d 0xfa 0x59 0x47 0xf0 0xad 0xd4 0xa2 0xaf 0x9c 0xa4 0x72 0xc0
2 0xb7 0xfd 0x93 0x26 0x36 0x3f 0xf7 0xcc 0x34 0xa5 0xe5 0xf1 0x71 0xd8 0x31 0x15
3 0x04 0xc7 0x23 0xc3 0x18 0x96 0x05 0x9a 0x07 0x12 0x80 0xe2 0xeb 0x27 0xb2 0x75
4 0x09 0x83 0x2c 0x1a 0x1b 0x6e 0x5a 0xa0 0x52 0x3b 0xd6 0xb3 0x29 0xe3 0x2f 0x84
5 0x53 0xd1 0x00 0xed 0x20 0xfc 0xb1 0x5b 0x6a 0xcb 0xbe 0x39 0x4a 0x4c 0x58 0xcf
6 0xd0 0xef 0xaa 0xfb 0x43 0x4d 0x33 0x85 0x45 0xf9 0x02 0x7f 0x50 0x3c 0x9f 0xa8
7 0x51 0xa3 0x40 0x8f 0x92 0x9d 0x38 0xf5 0xbc 0xb6 0xda 0x21 0x10 0xff 0xf3 0xd2
8 0xcd 0x0c 0x13 0xec 0x5f 0x97 0x44 0x17 0xc4 0xa7 0x7e 0x3d 0x64 0x5d 0x19 0x73
9 0x60 0x81 0x4f 0xdc 0x22 0x2a 0x90 0x88 0x46 0xee 0xb8 0x14 0xde 0x5e 0x0b 0xdb
A 0xe0 0x32 0x3a 0x0a 0x49 0x06 0x24 0x5c 0xc2 0xd3 0xac 0x62 0x91 0x95 0xe4 0x79
B 0xe7 0xc8 0x37 0x6d 0x8d 0xd5 0x4e 0xa9 0x6c 0x56 0xf4 0xea 0x65 0x7a 0xae 0x08
C 0xba 0x78 0x25 0x2e 0x1c 0xa6 0xb4 0xc6 0xe8 0xdd 0x74 0x1f 0x4b 0xbd 0x8b 0x8a
D 0x70 0x3e 0xb5 0x66 0x48 0x03 0xf6 0x0e 0x61 0x35 0x57 0xb9 0x86 0xc1 0x1d 0x9e
E 0xe1 0xf8 0x98 0x11 0x69 0xd9 0x8e 0x94 0x9b 0x1e 0x87 0xe9 0xce 0x55 0x28 0xdf
F 0x8c 0xa1 0x89 0x0d 0xbf 0xe6 0x42 0x68 0x41 0x99 0x2d 0x0f 0xb0 0x54 0xbb 0x16
状态矩阵中的元素按照下面的方式映射为一个新的字节：把该字节的高4位作为行值，低4位作为列值，取出S盒或者逆S盒中对应的行的元素作为输出。例如，加密时，输出的字节S1为0x12,则查S盒的第0x01行和0x02列，得到值0xc9,然后替换S1原有的0x12为0xc9。状态矩阵经字节代换后的图如下：
(第二个字符0xAB查表后应该是转换成0x62的，感谢细心的朋友指出，有空再重新画图更正了)
请点击输入图片描述
2.字节代换逆操作
逆字节代换也就是查逆S盒来变换，逆S盒如下：
行/列
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0 0x52 0x09 0x6a 0xd5 0x30 0x36 0xa5 0x38 0xbf 0x40 0xa3 0x9e 0x81 0xf3 0xd7 0xfb
1 0x7c 0xe3 0x39 0x82 0x9b 0x2f 0xff 0x87 0x34 0x8e 0x43 0x44 0xc4 0xde 0xe9 0xcb
2 0x54 0x7b 0x94 0x32 0xa6 0xc2 0x23 0x3d 0xee 0x4c 0x95 0x0b 0x42 0xfa 0xc3 0x4e
3 0x08 0x2e 0xa1 0x66 0x28 0xd9 0x24 0xb2 0x76 0x5b 0xa2 0x49 0x6d 0x8b 0xd1 0x25
4 0x72 0xf8 0xf6 0x64 0x86 0x68 0x98 0x16 0xd4 0xa4 0x5c 0xcc 0x5d 0x65 0xb6 0x92
5 0x6c 0x70 0x48 0x50 0xfd 0xed 0xb9 0xda 0x5e 0x15 0x46 0x57 0xa7 0x8d 0x9d 0x84
6 0x90 0xd8 0xab 0x00 0x8c 0xbc 0xd3 0x0a 0xf7 0xe4 0x58 0x05 0xb8 0xb3 0x45 0x06
7 0xd0 0x2c 0x1e 0x8f 0xca 0x3f 0x0f 0x02 0xc1 0xaf 0xbd 0x03 0x01 0x13 0x8a 0x6b
8 0x3a 0x91 0x11 0x41 0x4f 0x67 0xdc 0xea 0x97 0xf2 0xcf 0xce 0xf0 0xb4 0xe6 0x73
9 0x96 0xac 0x74 0x22 0xe7 0xad 0x35 0x85 0xe2 0xf9 0x37 0xe8 0x1c 0x75 0xdf 0x6e
A 0x47 0xf1 0x1a 0x71 0x1d 0x29 0xc5 0x89 0x6f 0xb7 0x62 0x0e 0xaa 0x18 0xbe 0x1b
B 0xfc 0x56 0x3e 0x4b 0xc6 0xd2 0x79 0x20 0x9a 0xdb 0xc0 0xfe 0x78 0xcd 0x5a 0xf4
C 0x1f 0xdd 0xa8 0x33 0x88 0x07 0xc7 0x31 0xb1 0x12 0x10 0x59 0x27 0x80 0xec 0x5f
D 0x60 0x51 0x7f 0xa9 0x19 0xb5 0x4a 0x0d 0x2d 0xe5 0x7a 0x9f 0x93 0xc9 0x9c 0xef
E 0xa0 0xe0 0x3b 0x4d 0xae 0x2a 0xf5 0xb0 0xc8 0xeb 0xbb 0x3c 0x83 0x53 0x99 0x61
F 0x17 0x2b 0x04 0x7e 0xba 0x77 0xd6 0x26 0xe1 0x69 0x14 0x63 0x55 0x21 0x0c 0x7d
二、行移位
1.行移位操作
行移位是一个简单的左循环移位操作。当密钥长度为128比特时，状态矩阵的第0行左移0字节，第1行左移1字节，第2行左移2字节，第3行左移3字节，如下图所示：
请点击输入图片描述
2.行移位的逆变换
行移位的逆变换是将状态矩阵中的每一行执行相反的移位操作，例如AES-128中，状态矩阵的第0行右移0字节，第1行右移1字节，第2行右移2字节，第3行右移3字节。
三、列混合
1.列混合操作
列混合变换是通过矩阵相乘来实现的，经行移位后的状态矩阵与固定的矩阵相乘，得到混淆后的状态矩阵，如下图的公式所示：
请点击输入图片描述
状态矩阵中的第j列(0 ≤j≤3)的列混合可以表示为下图所示：
请点击输入图片描述
其中，矩阵元素的乘法和加法都是定义在基于GF(2^8)上的二元运算,并不是通常意义上的乘法和加法。这里涉及到一些信息安全上的数学知识，不过不懂这些知识也行。其实这种二元运算的加法等价于两个字节的异或，乘法则复杂一点。对于一个8位的二进制数来说，使用域上的乘法乘以(00000010)等价于左移1位(低位补0)后，再根据情况同(00011011)进行异或运算，设S1 = (a7 a6 a5 a4 a3 a2 a1 a0)，刚0x02 * S1如下图所示：
也就是说，如果a7为1，则进行异或运算，否则不进行。
类似地，乘以(00000100)可以拆分成两次乘以(00000010)的运算：
乘以(0000 0011)可以拆分成先分别乘以(0000 0001)和(0000 0010)，再将两个乘积异或：
因此，我们只需要实现乘以2的函数，其他数值的乘法都可以通过组合来实现。
下面举个具体的例子,输入的状态矩阵如下：
请点击输入图片描述
C9 E5 FD 2B
7A F2 78 6E
63 9C 26 67
B0 A7 82 E5
下面，进行列混合运算：
以第一列的运算为例：
其它列的计算就不列举了，列混合后生成的新状态矩阵如下：
请点击输入图片描述
D4 E7 CD 66
28 02 E5 BB
BE C6 D6 BF
22 0F DF A5
2.列混合逆运算
逆向列混合变换可由下图的矩阵乘法定义：
可以验证，逆变换矩阵同正变换矩阵的乘积恰好为单位矩阵。
请点击输入图片描述
四、轮密钥加
轮密钥加是将128位轮密钥Ki同状态矩阵中的数据进行逐位异或操作，如下图所示。其中，密钥Ki中每个字W[4i],W[4i+1],W[4i+2],W[4i+3]为32位比特字，包含4个字节，他们的生成算法下面在下面介绍。轮密钥加过程可以看成是字逐位异或的结果，也可以看成字节级别或者位级别的操作。也就是说，可以看成S0 S1 S2 S3 组成的32位字与W[4i]的异或运算。
轮密钥加的逆运算同正向的轮密钥加运算完全一致，这是因为异或的逆操作是其自身。轮密钥加非常简单，但却能够影响S数组中的每一位。
请点击输入图片描述
密钥扩展
AES首先将初始密钥输入到一个4*4的状态矩阵中，如下图所示。
这个4*4矩阵的每一列的4个字节组成一个字，矩阵4列的4个字依次命名为W[0]、W[1]、W[2]和W[3]，它们构成一个以字为单位的数组W。例如，设密钥K为”abcdefghijklmnop”,则K0 = ‘a’,K1 = ‘b’, K2 = ‘c’,K3 = ‘d’,W[0] = “abcd”。
接着，对W数组扩充40个新列，构成总共44列的扩展密钥数组。新列以如下的递归方式产生：
1.如果i不是4的倍数，那么第i列由如下等式确定：
W[i]=W[i-4]⨁W[i-1]
2.如果i是4的倍数，那么第i列由如下等式确定：
W[i]=W[i-4]⨁T(W[i-1])
其中，T是一个有点复杂的函数。
函数T由3部分组成：字循环、字节代换和轮常量异或，这3部分的作用分别如下。
a.字循环：将1个字中的4个字节循环左移1个字节。即将输入字[b0, b1, b2, b3]变换成[b1,b2,b3,b0]。
b.字节代换：对字循环的结果使用S盒进行字节代换。
c.轮常量异或：将前两步的结果同轮常量Rcon[j]进行异或，其中j表示轮数。
轮常量Rcon[j]是一个字，其值见下表。
请点击输入图片描述
j
1
2
3
4
5
Rcon[j] 01 00 00 00 02 00 00 00 04 00 00 00 08 00 00 00 10 00 00 00
j 6 7 8 9 10
Rcon[j] 20 00 00 00 40 00 00 00 80 00 00 00 1B 00 00 00 36 00 00 00
下面举个例子：
设初始的128位密钥为：
3C A1 0B 21 57 F0 19 16 90 2E 13 80 AC C1 07 BD
那么4个初始值为：
W[0] = 3C A1 0B 21
W[1] = 57 F0 19 16
W[2] = 90 2E 13 80
W[3] = AC C1 07 BD
下面求扩展的第1轮的子密钥(W[4],W[5],W[6],W[7])。
由于4是4的倍数，所以：
W[4] = W[0] ⨁ T(W[3])
T(W[3])的计算步骤如下：
1. 循环地将W[3]的元素移位：AC C1 07 BD变成C1 07 BD AC;
2. 将 C1 07 BD AC 作为S盒的输入，输出为78 C5 7A 91;
3. 将78 C5 7A 91与第一轮轮常量Rcon[1]进行异或运算，将得到79 C5 7A 91，因此，T(W[3])=79 C5 7A 91，故
W[4] = 3C A1 0B 21 ⨁ 79 C5 7A 91 = 45 64 71 B0
其余的3个子密钥段的计算如下：
W[5] = W[1] ⨁ W[4] = 57 F0 19 16 ⨁ 45 64 71 B0 = 12 94 68 A6
W[6] = W[2] ⨁ W[5] =90 2E 13 80 ⨁ 12 94 68 A6 = 82 BA 7B 26
W[7] = W[3] ⨁ W[6] = AC C1 07 BD ⨁ 82 BA 7B 26 = 2E 7B 7C 9B
所以，第一轮的密钥为 45 64 71 B0 12 94 68 A6 82 BA 7B 26 2E 7B 7C 9B。
AES解密
在文章开始的图中，有AES解密的流程图，可以对应那个流程图来进行解密。下面介绍的是另一种等价的解密模式，流程图如下图所示。这种等价的解密模式使得解密过程各个变换的使用顺序同加密过程的顺序一致，只是用逆变换取代原来的变换。
请点击输入图片描述
在 《Hello，密码学：第二部分，对称密码算法》 中讲述了对称密码的概念，以及DES和AES两种经典的对称密码算法原理。既然有对称密码的说法，自然也就有非对称密码，也叫做公钥密码算法。 对称密码和非对称密码两种算法的本质区别在于，加密密钥和解密密钥是否相同 ：
公钥密码产生的初衷就是为了解决 密钥配送 的问题。
Alice 给远方的 Bob 写了一封情意慢慢的信，并使用强悍的 AES-256 进行了加密，但她很快就意识到，光加密内容不行，必须要想一个安全的方法将加密密钥告诉 Bob，如果将密钥也通过网络发送，很可能被技术高手+偷窥癖的 Eve 窃听到。
既要发送密钥，又不能发送密钥，这就是对称密码算法下的“密钥配送问题” 。
解决密钥配送问题可能有这样几种方法：
这种方法比较高效，但有局限性：
与方法一不同，密钥不再由通信个体来保存，而由密钥分配中心（KDC）负责统一的管理和分配。 双方需要加密通信时，由 KDC 生成一个用于本次通信的通信密钥交由双方，通信双方只要与 KDC 事先共享密钥即可 。这样就大大减少密钥的存储和管理问题。
因此，KDC 涉及两类密钥：
领略下 KDC 的过程：
KDC 通过中心化的手段，确实能够有效的解决方法一的密钥管理和分配问题，安全性也还不错。但也存在两个显著的问题：
使用公钥密码，加密密钥和解密密钥不同，只要拥有加密密钥，所有人都能进行加密，但只有拥有解密密钥的人才能进行解密。于是就出现了这个过程：
密钥配送的问题天然被解决了。当然，解密密钥丢失而导致信息泄密，这不属于密钥配送的问题。
下面，再详细看下这个过程。
公钥密码流程的核心，可以用如下四句话来概述：
既然加密密钥是公开的，因此也叫做 “公钥（Public Key）” 。
既然解密密钥是私有的，因此也叫做 “私钥（Private Key） 。
公钥和私钥是一一对应的，称为 “密钥对” ，他们好比相互纠缠的量子对， 彼此之间通过严密的数学计算关系进行关联 ，不能分别单独生成。
在公钥密码体系下，再看看 Alice 如何同 Bob 进行通信。
在公钥密码体系下，通信过程是由 Bob 开始启动的：
过程看起来非常简单，但为什么即使公钥被窃取也没有关系？这就涉及了上文提到的严密的数学计算关系了。如果上一篇文章对称密钥的 DES 和 AES 算法进行概述，下面一节也会对公钥体系的数学原理进行简要说明。
自从 Diffie 和 Hellman 在1976年提出公钥密码的设计思想后，1978年，Ron Rivest、Adi Shamir 和 Reonard Adleman 共同发表了一种公钥密码算法，就是大名鼎鼎的 RSA，这也是当今公钥密码算法事实上的标准。其实，公钥密码算法还包括ElGamal、Rabin、椭圆曲线等多种算法，这一节主要讲述 RSA 算法的基本数学原理。
一堆符号，解释下，E 代表 Encryption，D 代表 Decryption，N 代表 Number。
从公式种能够看出来，RSA的加解密数学公式非常简单（即非常美妙）。 RSA 最复杂的并非加解密运算，而是如何生成密钥对 ，这和对称密钥算法是不太一样的。 而所谓的严密的数学计算关系，就是指 E 和 D 不是随便选择的 。
密钥对的生成，是 RSA 最核心的问题，RSA 的美妙与奥秘也藏在这里面。
1. 求N
求 N 公式：N = p × q
其中， p 和 q 是两个质数 ，而且应该是很大又不是极大的质数。如果太小的话，密码就容易被破解；如果极大的话，计算时间就会很长。比如 512 比特的长度（155 位的十进制数字）就比较合适。
这样的质数是如何找出来的呢？ 需要通过 “伪随机数生成器（PRNG）” 进行生成，然后再判断其是否为质数 。如果不是，就需要重新生成，重新判断。
2. 求L
求 L 公式：L = lcm(p-1, q-1)
lcm 代表 “最小公倍数（least common multiple）” 。注意，L 在加解密时都不需要， 仅出现在生成密钥对的过程中 。
3. 求E
E 要满足两个条件：
1）1 E L
2）gcd(E,L) = 1
gcd 代表 “最大公约数（greatest common divisor）” 。gcd(E,L) = 1 就代表 “E 和 L 的最大公约数为1，也就是说， E 和 L 互质 ”。
L 在第二步已经计算出来，而为了找到满足条件的 E， 第二次用到 “伪随机数生成器（PRNG）” ，在 1 和 L 之间生成 E 的候选，判断其是否满足 “gcd(E,L) = 1” 的条件。
经过前三步，已经能够得到密钥对种的 “公钥：{E, N}” 了。
4. 求D
D 要满足两个条件：
1）1 D L
2）E × D mod L = 1
只要 D 满足上面的两个条件，使用 {E, N} 进行加密的报文，就能够使用 {D, N} 进行解密。
至此，N、L、E、D 都已经计算出来，再整理一下
模拟实践的过程包括两部分，第一部分是生成密钥对，第二部分是对数据进行加解密。为了方便计算，都使用了较小的数字。
第一部分：生成密钥对
1. 求N
准备两个质数，p = 5，q = 7，N = 5 × 7 = 35
2. 求L
L = lcm(p-1, q-1) = lcm (4, 6) = 12
3. 求E
gcd(E, L) = 1，即 E 和 L 互质，而且 1 E L，满足条件的 E 有多个备选：5、7、11，选择最小的 5 即可。于是，公钥 = {E, N} = {5, 35}
4. 求D
E × D mod L = 1，即 5 × D mod 12 = 1，满足条件的 D 也有多个备选：5、17、41，选择 17 作为 D（如果选择 5 恰好公私钥一致了，这样不太直观），于是，私钥 = {D, N} = {17, 35}
至此，我们得到了公私钥对：
第二部分：模拟加解密
明文我们也使用一个比较小的数字 -- 4，利用 RSA 的加密公式：
密文 = 明文 ^ E mod N = 4 ^ 5 mod 35 = 9
明文 = 密文 ^ D mod N = 9 ^ 17 mod 35 = 4
从这个模拟的小例子能够看出，即使我们用了很小的数字，计算的中间结果也是超级大。如果再加上伪随机数生成器生成一个数字，判断其是否为质数等，这个过程想想脑仁儿就疼。还好，现代芯片技术，让计算机有了足够的运算速度。然而，相对于普通的逻辑运算，这类数学运算仍然是相当缓慢的。这也是一些非对称密码卡/套件中，很关键的性能规格就是密钥对的生成速度
公钥密码体系中，用公钥加密，用私钥解密，公钥公开，私钥隐藏。因此：
加密公式为：密文 = 明文 ^ E mod N
破译的过程就是对该公式进行逆运算。由于除了对明文进行幂次运算外， 还加上了“模运算” ，因此在数学上， 该逆运算就不再是简单的对数问题，而是求离散对数问题，目前已经在数学领域达成共识，尚未发现求离散对数的高效算法 。
暴力破解的本质就是逐个尝试。当前主流的 RSA 算法中，使用的 p 和 q 都是 1024 位以上，这样 N 的长度就是 2048 位以上。而 E 和 D 的长度和 N 差不多，因此要找出 D，就需要进行 2048 位以上的暴力破解。即使上文那个简单的例子，算出（ 蒙出 ） “9 ^ D mod 35 = 4” 中的 D 也要好久吧。
因为 E 和 N 是已知的，而 D 和 E 在数学上又紧密相关（通过中间数 L），能否通过一种反向的算法来求解 D 呢？
从这个地方能够看出，p 和 q 是极为关键的，这两个数字不泄密，几乎无法通过公式反向计算出 D。也就是说， 对于 RSA 算法，质数 p 和 q 绝不能被黑客获取，否则等价于交出私钥 。
既然不能靠抢，N = p × q，N是已知的，能不能通过 “质因数分解” 来推导 p 和 q 呢？或者说， 一旦找到一种高效的 “质因数分解” 算法，就能够破解 RSA 算法了 。
幸运的是，这和上述的“离散对数求解”一样，当下在数学上还没有找到这种算法，当然，也无法证明“质因数分解”是否真的是一个困难问题 。因此只能靠硬算，只是当前的算力无法在可现实的时间内完成。 这也是很多人都提到过的，“量子时代来临，当前的加密体系就会崩溃”，从算力的角度看，或许如此吧 。
既不能抢，也不能算，能不能猜呢？也就是通过 “推测 p 和 q 进行破解” 。
p 和 q 是通过 PRNG（伪随机数生成器）生成的，于是，又一个关键因素，就是采用的 伪随机数生成器算法要足够随机 。
随机数对于密码学极为重要，后面会专门写一篇笔记 。
前三种攻击方式，都是基于 “硬碰硬” 的思路，而 “中间人攻击” 则换了一种迂回的思路，不去尝试破解密码算法，而是欺骗通信双方，从而获取明文。具体来说，就是： 主动攻击者 Mallory 混入发送者和接收者之间，面对发送者伪装成接收者，面对接收者伪装成发送者。
这个过程可以重复多次。需要注意的是，中间人攻击方式不仅能够针对 RSA，还可以针对任何公钥密码。能够看到，整个过程中，公钥密码并没有被破译，密码体系也在正常运转，但机密性却出现了问题，即 Alice 和 Bob 之间失去了机密性，却在 Alice 和 Mallory 以及 Mallory 和 Bob 之间保持了机密性。即使公钥密码强度再强大 N 倍也无济于事。也就是说，仅仅依靠密码算法本身，无法防御中间人攻击 。
而能够抵御中间人攻击的，就需要用到密码工具箱的另一种武器 -- 认证 。在下面一篇笔记中，就将涉及这个话题。
好了，以上就是公钥密码的基本知识了。
公钥密码体系能够完美的解决对称密码体系中 “密钥配送” 这个关键问题，但是抛开 “中间人攻击” 问题不谈，公钥密码自己也有个严重的问题：
公钥密码处理速度远远低于对称密码。不仅体现在密钥对的生成上，也体现在加解密运算处理上。
因此，在实际应用场景下，往往会将对称密码和公钥密码的优势相结合，构建一个 “混合密码体系” 。简单来说： 首先用相对高效的对称密码对消息进行加密，保证消息的机密性；然后用公钥密码加密对称密码的密钥，保证密钥的机密性。
下面是混合密码体系的加解密流程图。整个体系分为左右两个部分：左半部分加密会话密钥的过程，右半部分是加密原始消息的过程。原始消息一般较长，使用对称密码算法会比较高效；会话密钥一般比较短（十几个到几十个字节），即使公钥密码算法运算效率较低，对会话密钥的加解密处理也不会非常耗时。
著名的密码软件 PGP、SSL/TLS、视频监控公共联网安全建设规范（GB35114） 等应用，都运用了混合密码系统。
好了，以上就是公钥密码算法的全部内容了，拖更了很久，以后还要更加勤奋一些。
为了避免被傻啦吧唧的审核机器人处理，后面就不再附漂亮姑娘的照片（也是为了你们的健康），改成我的摄影作品，希望不要对收视率产生影响，虽然很多小伙儿就是冲着姑娘来的。
就从喀纳斯之旅开始吧。
椭圆曲线加密算法，即：Elliptic Curve Cryptography，简称ECC，是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA，ECC优势是可以使用更短的密钥，来实现与RSA相当或更高的安全。据研究，160位ECC加密安全性相当于1024位RSA加密，210位ECC加密安全性相当于2048位RSA加密。
椭圆曲线在密码学中的使用，是1985年由Neal Koblitz和Victor Miller分别独立提出的。
一般情况下，椭圆曲线可用下列方程式来表示，其中a,b,c,d为系数。
例如，当a=1,b=0,c=-2,d=4时，所得到的椭圆曲线为:
该椭圆曲线E的图像如图X-1所示，可以看出根本就不是椭圆形。
过曲线上的两点A、B画一条直线，找到直线与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A+B，即为加法。如下图所示：A + B = C
上述方法无法解释A + A，即两点重合的情况。因此在这种情况下，将椭圆曲线在A点的切线，与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A + A，即2A，即为二倍运算。
将A关于x轴对称位置的点定义为-A，即椭圆曲线的正负取反运算。如下图所示：
如果将A与-A相加，过A与-A的直线平行于y轴，可以认为直线与椭圆曲线相交于无穷远点。
综上，定义了A+B、2A运算，因此给定椭圆曲线的某一点G，可以求出2G、3G（即G + 2G）、4G......。即：当给定G点时，已知x，求xG点并不困难。反之，已知xG点，求x则非常困难。此即为椭圆曲线加密算法背后的数学原理。
椭圆曲线要形成一条光滑的曲线，要求x,y取值均为实数，即实数域上的椭圆曲线。但椭圆曲线加密算法，并非使用实数域，而是使用有限域。按数论定义，有限域GF(p)指给定某个质数p，由0、1、2......p-1共p个元素组成的整数集合中定义的加减乘除运算。
假设椭圆曲线为y² = x³ + x + 1，其在有限域GF(23)上时，写作：y² ≡ x³ + x + 1 (mod 23)
此时，椭圆曲线不再是一条光滑曲线，而是一些不连续的点，如下图所示。以点(1,7)为例，7² ≡ 1³ + 1 + 1 ≡ 3 (mod 23)。如此还有如下点：
(0,1) (0,22)(1,7) (1,16)(3,10) (3,13)(4,0)(5,4) (5,19)(6,4) (6,19)(7,11) (7,12)(9,7) (9,16)(11,3) (11,20)等等。
另外，如果P(x,y)为椭圆曲线上的点，则-P即(x,-y)也为椭圆曲线上的点。如点P(0,1)，-P=(0,-1)=(0,22)也为椭圆曲线上的点。
相关公式如下：有限域GF(p)上的椭圆曲线y² = x³ + ax + b，若P(Xp, Yp), Q(Xq, Yq)，且P≠-Q，则R(Xr,Yr) = P+Q 由如下规则确定：
Xr = (λ² - Xp - Xq) mod pYr = (λ(Xp - Xr) - Yp) mod p其中λ = (Yq - Yp)/(Xq - Xp) mod p（若P≠Q）, λ = (3Xp² + a)/2Yp mod p（若P=Q）
因此，有限域GF(23)上的椭圆曲线y² ≡ x³ + x + 1 (mod 23)，假设以(0,1)为G点，计算2G、3G、4G...xG等等，方法如下：
计算2G：λ = (3x0² + 1)/2x1 mod 23 = (1/2) mod 23 = 12Xr = (12² - 0 - 0) mod 23 = 6Yr = (12(0 - 6) - 1) mod 23 = 19即2G为点(6,19)
计算3G：3G = G + 2G，即(0,1) + (6,19)λ = (19 - 1)/(6 - 0) mod 23 = 3Xr = (3² - 0 - 6) mod 23 = 3Yr = (3(0 - 3) - 1) mod 23 = 13即3G为点(3, 13)
建立基于椭圆曲线的加密机制，需要找到类似RSA质因子分解或其他求离散对数这样的难题。而椭圆曲线上的已知G和xG求x，是非常困难的，此即为椭圆曲线上的的离散对数问题。此处x即为私钥，xG即为公钥。
椭圆曲线加密算法原理如下：
设私钥、公钥分别为k、K，即K = kG，其中G为G点。
公钥加密：选择随机数r，将消息M生成密文C，该密文是一个点对，即：C = {rG, M+rK}，其中K为公钥
私钥解密：M + rK - k(rG) = M + r(kG) - k(rG) = M其中k、K分别为私钥、公钥。
椭圆曲线签名算法，即ECDSA。设私钥、公钥分别为k、K，即K = kG，其中G为G点。
私钥签名：1、选择随机数r，计算点rG(x, y)。2、根据随机数r、消息M的哈希h、私钥k，计算s = (h + kx)/r。3、将消息M、和签名{rG, s}发给接收方。
公钥验证签名：1、接收方收到消息M、以及签名{rG=(x,y), s}。2、根据消息求哈希h。3、使用发送方公钥K计算：hG/s + xK/s，并与rG比较，如相等即验签成功。
原理如下：hG/s + xK/s = hG/s + x(kG)/s = (h+xk)G/s= r(h+xk)G / (h+kx) = rG
假设要签名的消息是一个字符串：“Hello World!”。DSA签名的第一个步骤是对待签名的消息生成一个消息摘要。不同的签名算法使用不同的消息摘要算法。而ECDSA256使用SHA256生成256比特的摘要。
摘要生成结束后，应用签名算法对摘要进行签名：
产生一个随机数k
利用随机数k，计算出两个大数r和s。将r和s拼在一起就构成了对消息摘要的签名。
这里需要注意的是，因为随机数k的存在，对于同一条消息，使用同一个算法，产生的签名是不一样的。从函数的角度来理解，签名函数对同样的输入会产生不同的输出。因为函数内部会将随机值混入签名的过程。
关于验证过程，这里不讨论它的算法细节。从宏观上看，消息的接收方从签名中分离出r和s，然后利用公开的密钥信息和s计算出r。如果计算出的r和接收到的r值相同，则表示验证成功。否则，表示验证失败。
