0x01 简介

1978年,MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman用数论构造双钥密码的方法，称作MIT体制，后被广泛称为RSA体制，易懂且易于实现，是目前仍然安全并且应用最广泛的公钥密码算法。

RSA的安全性基于数论中大整数分解的困难性。

0x02 原理

1. 密钥的产生

1. 选择两个素数p和q，计算：

   • N = p * q

   • φ ( N ) = φ (p) * φ (q) = (p-1) * (q-1)

   质数(prime number)：又称素数，为在大于1的自然数中，除了1和它本身以外不再有其他因数。

   互质关系：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。

   φ(N)：叫做欧拉函数，是指任意给定正整数N，在小于等于N的正整数之中，有多少个与N构成互质关系。

   • 如果n是质数，则 φ(n)=n-1。
   • 如果n可以分解成两个互质的整数之积， φ(n) = φ(p1p2) = φ(p1)φ(p2)。即积的欧拉函数等于各个因子的欧拉函数之积。

2. 选择整数e，满足以下条件：

   • e 和 φ(N)互质，即 gcd(Φ(n),e)=1
   • 1< e < φ(N)

   常使用65537=2¹⁶+1。用二进制表示：10000000000000001，只有两个1，代码只有两次需要执行if语句的乘法，很大限度地提高了运算使用公钥的运算速度。但实际应用实现中参数的选择需要仔细斟酌。

3. 计算整数d，使d满足以下方程：

   d=e^-1mod Φ(n)

4. 密钥

   • 公钥：(N, e)
   • 私钥：(N, d)

2. 加密过程

明文： M < N

密文： C = M^e mod N

3. 解密过程

密文： C

明文： M = C^d mod N

4. RSA填充方式

PKCS全称Public Key Cryptography Standers, 是RSA信息安全公司与其合作伙伴共同制定的，被信息界的产业广泛认同。

RSA加密常用的填充模式有三种：

RSA_NO_PADDING

当用户选择RSA_NO_PADDING填充模式时，如果明文不够128字节，加密的时候会在明文前面填充若干数据0，直至达到128字节。

解密后的明文也会包括前面填充的零，用户需要注意把解密后的字段前向填充的零去掉，才是真正的明文。

RSA_PKCS1_PADDING

当你选择RSA_PKCS1_PADDING填充模式时，如果明文不够128字节，加密的时候会在明文中随机填充一些数据，所以会导致对同样的明文每次加密后的结果都不一样。

这种方式是Java库中默认采用的填充方式，格式

EB = 00 || BT || PS || 00 || D

第一部分默认为00

第二部分BT（The block type块类型）：00 表示签名， 01 表示加解密

第三部分PS（The padding string填充字符串）：

• BT=00，PS由00组成；

• BT=01，PS由FF组成；

• BT=02，PS由伪随机生成，且非零；

• PS长度为Len(EB) - 3 - Len(D)，最少是8字节。

不同公钥大小能加密的明文最大长度：

1024: (1024 - 11 * 8) / 8 = 117
2048: (2048 - 11 * 8) / 8 = 245
4096: (4096 - 11 * 8) / 8 = 501

RSA_PKCS1_OAEP_PADDING

最优非对称加密填充（Optimal Asymmetric Encrypt Padding）简称OAEP。

RSA_PKCS1_OAEP_PADDING填充模式是PKCS#1推出的新填充方式，安全性最高，和前面RSA_PKCS1_PADDING的区别就是加密前的编码方式不一样。

5. RSA安全性

RSA算法有以下攻击方式（其实不只是RSA，其他密钥体系也可能有）：

1. 穷举攻击
2. 数学攻击
3. 计时攻击
4. 基于硬件故障分析
5. 选择密文攻击

穷举攻击

通过穷举所有的可能数据来猜测密钥或者密文。
当然RSA参数比较小的时候，可以使用该方法奏效。
例如用户公钥n = 35, e = 5 密文C = 10 被截获后，由于C=M**e mod n=M5 mod 35=10, 计算循环1到35，很容易破解原始消息M = 5.

抵抗该种攻击的方式是使用大密钥空间，公私钥均为很长比特位，如2048位等

数学攻击

数学攻击的方法实质是试图分解两个素数的乘积，根据RSA原理