对称加密、公钥加密和RSA

引子

对于加解密，我一直处于一种知其然不知其所以然的状态，项目核心部分并不倚重加解密算法时，可以勉强对付过去，一旦需要频繁应用诸如 AES/RSA等算法，这种状态就颇令人捉急了。

是时候了解一下原理了，所以找来了这本图解密码技术给自己补补课：

在该书深入浅出的指引下，补充了一些常识，在此进行一番梳理：

对称加密算法（共享密钥）

顾名思义，对称加密就是用相同的密钥进行加密和解密。说到对称加密，异或加密又是一个不得不提的概念：

XOR（异或加密）

明文与密钥进行一次异或（记做㊉）运算将成为密文，密文再与密钥进行一次异或运算将还原为明文：

例如，字符串“Wiki”（8位ASCII：01010111 01101001 01101011 01101001）可以按如下的方式用密钥11110011进行加密：

01010111 01101001 01101011 01101001

$\oplus$ 11110011 11110011 11110011 11110011

= 10100100 10011010 10011000 10011010

此种加密方法类似对称加密，故解密的方式如下：

10100100 10011010 10011000 10011010

$\oplus$ 11110011 11110011 11110011 11110011

= 01010111 01101001 01101011 01101001

我们也可以用代码验证这一特性：

var key = 0b10110010;
var number = 22;
var encrypted = number ^ key;   // ㊉ => 密文 164
console.log(encrypted ^ key);   // ㊉ => 明文 22

var key = 0b10110010;

var number = 22;

var encrypted = number ^ key; // ㊉ => 密文 164

console.log(encrypted ^ key); // ㊉ => 明文 22

光使用XOR，就能实现最基本的对称加密，前提是选择一个合适的密钥。而其它对称加密算法如DES/AES 等，无不是在 XOR 基础上的扩展。

AES 对称加密

AES 即高级加密标准（Advanced Encryption Standard），是取代前任标准（DES）成为新标准的一种对称加密算法（DES被取代是因为其算法有缺陷，导致其能被短时间内暴力破解，所以DES被弃用，建议使用AES）。现行AES的实现算法为 Rijndael，是比利时科学家Joan Daemen 和 Vincent Rijmen 设计的分组密码算法。

分组的意思是说，AES 算法的输入是要分组的，分组长度可以在 128/196/256 比特中进行选择（即一轮可加密这么多比特的明文生成同样长度的密文，一次加密可能需要迭代多轮）。

模式

分组密码算法只能加密固定长度的分组，但是我们需要加密的明文长度可能会超过分组密码的分组长度，这时就需要对分组密码算法进行迭代，以便将一段很长的明文全部加密。而迭代的方法就称为分组密码的模式。

模式有很多种类，分组密码的主要模式有：

ECB 模式：Electronic Codebook mode （电子密码本模式）
CBC 模式：Cipher Block Channing mode（密码分组链接模式）
CFB 模式：Cipher FeedBack mode (密文反馈模式）
OFB 模式：Output FeedBack mode（输出反馈模式）
CTR 模式：CounTeR mode（计数器模式）

这几种模式的运作流程这里不做赘述，只需知道：

ECB过于简单而不安全，已被弃用；
CFB可被施以重放攻击；
OFB 和 CTR 都可被主动攻击者反转密文，而引起解密后明文中的相应比特也发生变化；CTR比之OFB，多出能支持并发计算的特性，此外CTR是流式密码；
CBC虽不支持并行计算，但是却是这些模式中最为安全的

下图为CBC模式的算法结构图：

公钥加密算法

公开密钥加密，也称为非对称加密（asymmetric cryptography），一种密码学算法类型，在这种密码学方法中，需要一对密钥，一个是私人密钥，另一个则是公开密钥。这两个密钥是数学相关，用某用户密钥加密后所得的信息，只能用该用户的解密密钥才能解密。如果知道了其中一个，并不能计算出另外一个。因此如果公开了一对密钥中的一个，并不会危害到另外一个的秘密性质。称公开的密钥为公钥；不公开的密钥为私钥。

公钥加密解决了一个对称加密的密钥配送难题：如何安全的传递解密用的密钥。方案是：不传递，加密者和解密者所持密钥不一样，特点如下：

密文发送者只需要加密密钥（公钥
密文接收者只需要解密密钥（私钥
解密密钥不可以被窃听者获取
加密密钥被窃听者获取也没有安全问题

RSA 公钥加密

RSA 是一种公钥加密算法，它的名字是用三位开发者 R. Rivest、A. Shamir 和 L. Adleman 的姓氏首字母组成。RSA 可被用于公钥密码和数字签名，算法于1983年在美国取得专利，目前该专利已过期（由于该算法在申请专利前就已经被发表了，在世界上大多数其它地区这个专利权不被承认）。

在RSA中，明文、密钥和密文都是数字，公私钥对是两对数字：

公钥是 (数E，数N)
私钥是 (数D，数N)

加密就是用明文数字的E次方求 mod N （取余）的结果，过程可以用下列公式来表达：

密文 = 明文 ^E mod N

对密文的数字的D次方求 mod N就可以得到明文，解密过程可以用如下公式来表达：

明文 = 密文 ^D mod N

生成密钥对流程

(1) 求 N

随机生成两个很大的质数 p 和 q，那么 N = p * q

(2) 求 L

临时量 L 仅被用于生成密钥对的过程中，它是 p -1 和 q – 1 的最小公倍数（least common multiple, lcm)，用lcm(X, Y) 来表示 “X和Y的最小公倍数” ，则L可用公式表示为：

L = lcm(p-1, q-1)

(3) 求E

E 和 L 之间存在如下关系：

1 < E < L

gcd(E, L) = 1 E 和 L 的最大公约数为1 （E 和 L 互质）

要找出满足 gcd(E, L) = 1 的数，还是要使用伪随机数生成器。通过伪随机数生成器在 1 < E < L 的范围内生成 E 的候选数，然后再判断其是否满足 gcd(E, L) = 1 这个条件。

(4) 求D

数D 是由数 E 计算得到的。D、E 和 L 之间必须具备如下关系：

1 < D < L

E * D mod L = 1

只要数 D 满足上述条件，则通过 (数E，数N) 加密的密文，都可以通过 (数D，数N) 进行解密。

模拟实践

用较小的数来实践一把RSA的密钥生成和加解密：

(1) 求N

选择两个质数，比如： p = 17 和 q = 19

N = 17 * 19 = 323

(2) 求 L

L = lcm (p-1, q-1) = lcm(16, 18) = 144

(3) 求 E

E 和 L 的最大公约数必须是1：

gcd(E, L) = 1

满足条件的数 E有很多，100以内的质数有：

5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

我们挑一个，比如 5 作为E，那么 公钥对就是(E=5, N=323)

(4) 求 D

D 必须满足：

E * D mod L = 1

在 E = 3 的情况下，D = 59 是满足的，因为：

5 * 29 mod 144 = 1

所以 私钥对就是(D=29, N=323)

公/私钥对都有了，就可用于加解密了，假设有明文 42：

(5) 加密

密文 = 明文 ^E mod N => 42 ⁵ mod 323 = 264

(6) 解密

明文 = 密文 ^D mod N => 264 ²⁹ mod 323 => 数比较大，可分解求幂：

(264 ¹⁰ mod 323) * (264 ¹⁰ mod 323) * (264 ⁹ mod 323) mod 323 = 42

RSA 的算法原理

想了解更多RSA背后的数学知识，可以参考阮一峰的 RSA算法原理(一) 和 (二)

AES和RSA的应用

混合密码系统

通过比较，我们知道：

RSA 比 AES 更难破解，因为它不需要担心密钥在传递过程中有泄露，只存在暴力破解一种可能；
AES的优势是以分组为轮，加解密速度非常快，一般而言，AES 速度上数百倍于 RSA

所以在实际应用中，我们会混合应用AES和RSA，比如需要加密一个尺寸不小的文件，可能会这么干：

生成一个一次性随机密钥，算法上采用 AES 的CBC模式 aes-256-cbc（加密分组为256比特）对文件进行加密
加密完成后，为了安全的传递这个一次性随机密钥，我们使用接收方的RSA公钥对其进行加密，随加密后的文件一起发送
接收方使用私钥进行解密，得到AES密钥原文，并用其解密文件

例子

以上场景的应用，比如在 Node.js 中，可以这么实现：

(1) 生成 AES 随机密钥：

var passwdLength = 256;  // 初始化随机向量长度
var aesPassword = require('crypto').randomBytes(passwdLength);
require('fs').writeFileSync('aesPassword', aesPassword); // 写入文件供openssl使用

var passwdLength = 256; // 初始化随机向量长度

var aesPassword = require('crypto').randomBytes(passwdLength);

require('fs').writeFileSync('aesPassword', aesPassword); // 写入文件供openssl使用

(2) 使用openssl aes 加密 filename代表的文件：

openssl enc -aes-256-cbc -kfile aesPassword -in filename -out filename.out

1	openssl enc -aes-256-cbc -kfile aesPassword -in filename -out filename.out

(3) 使用open rsa 加密密钥

openssl enc rsautl -encrypt -pubin -inkey id_rsa.pub -in aespassword 
                                                -out aespassword.out

1 2	openssl enc rsautl -encrypt -pubin -inkey id_rsa.pub -in aespassword -out aespassword.out

将 filename.out 和 aespassword.out 一并发给对方即可，接收方使用openssl 进行一次逆操作即可实现解密。

参考

openssl 命令手册：http://netkiller.github.io/cryptography/openssl/index.html
Node-RSA: https://github.com/rzcoder/node-rsa

打赏作者

您的支持将激励我继续创作！

去打赏

Mo Ye

A Conservative

Published

June 14, 2015

Mo Ye in Algorithm | June 14, 2015