RSA 解析

# 一些历史

1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法" (opens new window)。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。

这种新的加密模式被称为"非对称加密算法"。

（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。（2）甲方获取乙方的公钥，然后用它对信息加密。（3）乙方得到加密后的信息，用私钥解密。

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法 (opens new window)。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。

这种算法非常可靠 (opens new window)，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是829个二进制位。也就是说，长度超过829位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。

下面，我就进入正题，解释RSA算法的原理。文章共分成两部分，今天是第一部分，介绍要用到的四个数学概念。你可以看到，RSA算法并不难，只需要一点数论知识 (opens new window)就可以理解。

# PEM与DER格式

PEM实际上就是把DER编码的文件的二进制内容用base64编码一下，然后加上-----BEGIN label-----这样的头和-----END label-----这样的尾，中间则是DER文件的Base64编码。

# 公钥私钥的内容

RSA 描述的私钥的结构如下（其中除 n,d 之外的都是冗余信息）：

modulus: 模数 n
publicExponent: 公指数 e，固定为 65537 (0x10001)
privateExponent: 私钥指数 d
prime1: 质数 p，用于计算 n
prime2: 质数 q，用于计算 n
exponent1: 用于加速 RSA 运算的中国剩余定理指数一
exponent2: 用于加速 RSA 运算的中国剩余定理指数二
coefficient: 用于加速 RSA 运算的中国剩余定理系数

再看下 RSA 公钥的结构：

modulus: 模数
exponent: 公指数 e，固定为 65537 (0x10001)

可以看到私钥文件中就已经包含了公钥的所有参数，实际上我们也是使用

# 理解 RSA 计算原理

公开密钥算法总是要基于一个数学上的难题。比如 RSA 依据的是：给定两个素数p、q 很容易相乘得到n，而对n进行因式分解却相对困难

# 加密

RSA的加密过程可以使用一个通式来表达：

$密文=原文^D mod N$

也就是说RSA加密是对明文的E次方后除以N后求余数的过程。就这么简单？对，就是这么简单。从通式可知，只要知道E和N任何人都可以进行RSA加密了，所以说E、N是RSA加密的密钥，也就是说E和N的组合就是公钥，我们用(E,N)来表示公钥，E是加密（Encryption）的首字母，N是数字（Number）的首字母

# 解密

RSA的解密同样可以使用一个通式来表达：

$密文=原文^D mod N$

从上述可以看出RSA的加密方式和解密方式是相同的，加密是求“E次方的mod N”;解密是求“D次方的mod N” 此处D是解密（Decryption）的首字母；N是数字（Number）的首字母。

# 生成密钥对

既然公钥是（E，N），私钥是（D，N）所以密钥对即为（E，D，N）但密钥对是怎样生成的？步骤如下：

求N
求L（L为中间过程的中间数）
求E
求D

# 求 N

准备两个质数p，q。这两个数不能太小，太小则会容易破解，将p乘以q就是N

$N=p*q$

# 求 L

L 是 p－1 和 q－1的最小公倍数，可用如下表达式表示

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

# 求 E

E必须满足两个条件：E是一个比1大比L小的数，E和L的最大公约数为1 用gcd(X,Y)来表示X，Y的最大公约数则E条件如下：

$1 < E < L$

$gcd(E,L)=1$

# 求D

数D是由数E计算出来的。D、E和L之间必须满足以下关系：

$1 < D < L$

$E＊D mod L ＝ 1$

只要D满足上述2个条件，则通过E和N进行加密的密文就可以用D和N进行解密。简单地说条件2是为了保证密文解密后的数据就是明文。现在私钥自然也已经生成了，密钥对也就自然生成了。小结下：

项	公式
求N	$N＝ p ＊ q$ ；`p，q`为质数
求L	$L＝lcm（p－1，q－1）$ ；`L`为`p－1、q－1`的最小公倍数
求E	$1 < E < L$ ， $gcd（E，L）=1$ ；`E，L`最大公约数为1（`E`和`L`互质）
求D	$1 < D < L$ ， $E＊D mod L ＝ 1$

# 举个例子

p ＝ 17

q ＝ 19

N ＝ p ＊ q ＝ 323

// 为了计算方便，p q 的值取小一旦，假设：p ＝ 17，q ＝ 19，
int p = 17;
int q = 19;
// （1）求N：N ＝ p ＊ q ＝ 323；
int n = 323;
// （2）求L：L ＝ lcm（p－1， q－1）＝ lcm(16，18） ＝ 144，144为16和18对最小公倍数；
int l = 144;
// （3）求E：1 < E < L ，gcd（E，L）=1，即1 < E < 144，gcd（E，144） ＝ 1，E和144互为质数，E = 5显然满足上述2个条件，故E ＝ 5
int e = 5;
// （4）求D：求D也必须满足2个条件：1 < D < L，E＊D mod L ＝ 1，即1 < D < 144，5 ＊ D mod 144 ＝ 1，显然当D＝ 29 时满足上述两个条件。
int d = 29;
// （5）加密：准备的明文必须是小于N的数，因为加密或者解密都要 mod N，其结果必须小于N。
// 假设明文 ＝ 123，则 密文＝（123的5次方）mod 323=225
int original = 123;
int secret = new BigInteger(original + "").pow(e).mod(new BigInteger(n + "")).intValue();
// （6）解密：明文＝（225的29次方）mod 323 =123，所以解密后的明文为123。
int decrypt = new BigInteger(secret + "").pow(d).mod(new BigInteger(n + "")).intValue();
System.out.println("=====公钥加密私钥解密======");
System.out.println(secret);
System.out.println(decrypt);
System.out.println(decrypt == original);

secret = new BigInteger(original + "").pow(d).mod(new BigInteger(n + "")).intValue();
decrypt = new BigInteger(secret + "").pow(e).mod(new BigInteger(n + "")).intValue();
System.out.println("=====私钥加密公钥解密======");
System.out.println(secret);
System.out.println(decrypt);
System.out.println(decrypt == original);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

=====公钥加密私钥解密======
225
123
true
=====私钥加密公钥解密======
157
123
true

1
2
3
4
5
6
7
8

更加详细的计算原理可见阮一峰的网络日志:

# openssl

# 生成私钥

openssl-genrsa (opens new window)

# 生成 2048 字节长度的 pkcs#1 格式加密的私钥 （未加密）
openssl genrsa -out pkcs1.pem 2048

# 生成加密的私钥
openssl genrsa -aes256 -passout pass:unclezs -out id_ras_aes.key 2048

# 无密私钥加密
openssl rsa -in id_ras.key -aes256 -passout pass:unclezs -out rsa_aes_private.key

# 有密私钥转无密
openssl rsa -in id_ras_aes.key -passin pass:unclezs -out id_ras.key

# 将 pkcs#1 转化为 pkcs#8 格式加密的私钥
openssl pkcs8 -topk8 -inform PEM -in pkcs1.pem -outform PEM -nocrypt -out pkcs8.pem

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 私钥生成公钥

openssl-rsa (opens new window)

# 生成 RSA 格式的公钥
openssl rsa -in pkcs1.pem -out pkcs1.pub.pem -pubout -RSAPublicKey_out

# 指定密码生成公钥
openssl rsa -in pkcs1.pem -out pkcs1.pub.pem -passin pass:unclezs -pubout -RSAPublicKey_out

# 查看私钥的各个字段信息
openssl rsa -in pkcs1.pem -text -noout

# 查看公钥的各个字段的信息
openssl rsa -in pkcs1.pub.pem -pubin -RSAPublicKey_in -text -noout

1
2
3
4
5
6
7
8
9
10
11

# DER 与 PEM 互转

# PEM 转 DER
openssl rsa -in pkcs8.pem -out pkcs8.der -outform DER

# DRE 转 PEM
openssl rsa -in pkcs8.der -inform DER -out pkcs8.pem -outform PEM

1
2
3
4
5

# 代码实现

package com.unclezs.samples.crypto;

import sun.misc.BASE64Decoder;
import sun.misc.BASE64Encoder;

import java.nio.charset.StandardCharsets;
import java.security.InvalidAlgorithmParameterException;
import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.NoSuchAlgorithmException;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.RSAKeyGenParameterSpec;
import java.security.spec.X509EncodedKeySpec;

import javax.crypto.Cipher;

/**
 * @author blog.unclezs.com
 * @since 2022/5/17 10:49
 */
public class RSASample {

  public static final String RSA = "RSA";

  public static void main(String[] args) throws Exception {
    SimpleKeyPair simpleKeyPair = generatePublicKeyAndPrivateKey();
    PrivateKey privateKey = parsePrivateKey(simpleKeyPair.getPrivateKey());
    PublicKey publicKey = parsePublicKey(simpleKeyPair.getPublicKey());
    byte[] encrypted = encrypt(publicKey, "mydata");
    byte[] decrypted = decrypt(privateKey, encrypted);
    System.out.println(new String(decrypted));
  }

  /**
   * 生成公钥和私钥
   *
   * @throws NoSuchAlgorithmException           没有这样算法异常
   * @throws InvalidAlgorithmParameterException 无效算法参数异常
   */
  public static SimpleKeyPair generatePublicKeyAndPrivateKey()
      throws NoSuchAlgorithmException, InvalidAlgorithmParameterException {
    // 获取指定算法的密钥对生成器
    KeyPairGenerator generator = KeyPairGenerator.getInstance(RSA);
    // 初始化密钥对生成器（指定密钥长度, 使用默认的安全随机数源）
    generator.initialize(new RSAKeyGenParameterSpec(2048, RSAKeyGenParameterSpec.F4));
    // 随机生成一对密钥（包含公钥和私钥）
    KeyPair keyPair = generator.generateKeyPair();
    // 获取 公钥 和 私钥
    PublicKey pubKey = keyPair.getPublic();
    PrivateKey priKey = keyPair.getPrivate();
    // 获取 公钥和私钥 的 编码格式（通过该 编码格式 可以反过来 生成公钥和私钥对象）
    byte[] pubEncBytes = pubKey.getEncoded();
    byte[] priEncBytes = priKey.getEncoded();
    // 把 公钥和私钥 的 编码格式 转换为 Base64文本 方便保存
    String pubEncBase64 = new BASE64Encoder().encode(pubEncBytes);
    String priEncBase64 = new BASE64Encoder().encode(priEncBytes);
    return new SimpleKeyPair(pubEncBase64, priEncBase64);
  }

  /**
   * 解析公钥
   *
   * @param publicKeyBase64 公钥base64
   * @return {@link PublicKey}
   * @throws Exception 异常
   */
  public static PublicKey parsePublicKey(String publicKeyBase64) throws Exception {
    byte[] keyBytes = new BASE64Decoder().decodeBuffer(publicKeyBase64);
    // 创建 已编码的公钥规格
    X509EncodedKeySpec encPubKeySpec = new X509EncodedKeySpec(keyBytes);
    // 获取指定算法的密钥工厂, 根据 已编码的公钥规格, 生成公钥对象
    return KeyFactory.getInstance(RSA).generatePublic(encPubKeySpec);
  }

  /**
   * 解析私钥
   *
   * @param privateKeyBase64 私钥base64
   * @return {@link PrivateKey}
   * @throws Exception 异常
   */
  public static PrivateKey parsePrivateKey(String privateKeyBase64) throws Exception {
    byte[] keyBytes = new BASE64Decoder().decodeBuffer(privateKeyBase64);
    // 创建 已编码的公钥规格
    PKCS8EncodedKeySpec encPubKeySpec = new PKCS8EncodedKeySpec(keyBytes);
    // 获取指定算法的密钥工厂, 根据 已编码的公钥规格, 生成公钥对象
    return KeyFactory.getInstance(RSA).generatePrivate(encPubKeySpec);
  }

  /**
   * 加密
   *
   * @param pubKey    酒吧关键
   * @param plainData 简单数据
   * @return {@link byte[]}
   * @throws Exception 异常
   */
  public static byte[] encrypt(PublicKey pubKey, String plainData) throws Exception {
    // 获取指定算法的密码器
    Cipher cipher = Cipher.getInstance("RSA");
    // 初始化密码器（公钥加密模型）
    cipher.init(Cipher.ENCRYPT_MODE, pubKey);
    // 加密数据, 返回加密后的密文
    return cipher.doFinal(plainData.getBytes(StandardCharsets.UTF_8));
  }

  /**
   * 解密
   *
   * @param priKey     革命制度党关键
   * @param cipherData 密码数据
   * @return {@link byte[]}
   * @throws Exception 异常
   */
  private static byte[] decrypt(PrivateKey priKey, byte[] cipherData) throws Exception {
    // 获取指定算法的密码器
    Cipher cipher = Cipher.getInstance("RSA");
    // 初始化密码器（私钥解密模型）
    cipher.init(Cipher.DECRYPT_MODE, priKey);
    // 解密数据, 返回解密后的明文
    return cipher.doFinal(cipherData);
  }

  public static class SimpleKeyPair {
    private String publicKey;
    private String privateKey;

    public SimpleKeyPair(String publicKey, String privateKey) {
      this.publicKey = publicKey;
      this.privateKey = privateKey;
    }

    public String getPublicKey() {
      return publicKey;
    }

    public void setPublicKey(String publicKey) {
      this.publicKey = publicKey;
    }

    public String getPrivateKey() {
      return privateKey;
    }

    public void setPrivateKey(String privateKey) {
      this.privateKey = privateKey;
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

# Java中使用 RSA 必须知项

# 加密三方库

https://www.bouncycastle.org/ (opens new window)

<dependency>
    <groupId>org.bouncycastle</groupId>
    <artifactId>bcprov-jdk15on</artifactId>
    <version>1.70</version>
</dependency>

1
2
3
4
5

# 质数的选择

首先要使用概率算法来验证随机产生的大的整数是否是质数，这样的算法比较快而且可以消除掉大多数非质数。假如有一个数通过了这个测试的话，那么要使用一个精确的测试来保证它的确是一个质数。除此之外这样找到的p和q还要满足一定的要求，首先它们不能太靠近，此外p-1或q-1的因子不能太小，否则的话N也可以被很快地分解。

寻找质数的算法不能给攻击者任何信息，比如这些质数是怎样找到的？尤其产生随机数的软件必须非常好。要求是随机和不可预测。这两个要求并不相同。一个随机过程可能可以产生一个不相关的数的系列，但假如有人能够预测出（或部分地预测出）这个系列的话，那么它就已经不可靠了。比如有一些非常好的随机数算法，但它们都已经被发表，因此它们不能被使用，因为假如一个攻击者可以猜出p和q一半的位的话，那么他们就已经可以轻而易举地推算出另一半。

# RSA加密算法的缺点

（1）产生密钥很麻烦，受到质数产生技术的限制，因而难以做到一次一密；

（2）运算速度慢：由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现，速度一直是RSA的缺陷，所以一般只用于少量数据的加密。RSA的速度是对应同样安全级别的对称密码算法的1/1000左右。

一般使用对称算法来加密数据，然后用RSA来加密对称密钥，然后将用RSA加密的对称密钥和用对称算法加密的消息发送出去。这样一来对随机数的要求就更高了，尤其对产生对称密码的要求非常高，因为否则的话可以越过RSA来直接攻击对称密码。

# 加密的系统不要具备解密的功能，否则 RSA 可能不太合适

公钥加密，私钥解密。加密的系统和解密的系统分开部署，加密的系统不应该同时具备解密的功能，这样即使黑客攻破了加密系统，他拿到的也只是一堆无法破解的密文数据。否则的话，你就要考虑你的场景是否有必要用 RSA 了。

# 可以通过修改生成密钥的长度来调整密文长度

生成密文的长度等于密钥长度。密钥长度越大，生成密文的长度也就越大，加密的速度也就越慢，而密文也就越难被破解掉。我们必须通过定义密钥的长度在"安全"和"加解密效率"之间做出一个平衡的选择。

# 生成密文的长度和明文长度无关，但明文长度不能超过密钥长度

不管明文长度是多少，RSA 生成的密文长度总是固定的。但是明文长度不能超过密钥长度。

比如 Java 默认的 RSA 加密实现不允许明文长度超过密钥长度减去 11(单位是字节，也就是 byte)。也就是说，如果我们定义的密钥(我们可以通过 java.security.KeyPairGenerator.initialize(int keysize) 来定义密钥长度)长度为 1024(单位是位，也就是 bit)，生成的密钥长度就是 1024位 / 8位/字节 = 128字节，那么我们需要加密的明文长度不能超过 128字节 -11 字节 = 117字节。也就是说，我们最大能将 117 字节长度的明文进行加密，否则会出问题(抛诸如 javax.crypto.IllegalBlockSizeException: Data must not be longer than 53 bytes 的异常)。

# 可以通过调整算法提供者来减小密文长度

Java 默认的 RSA 实现 "RSA/None/PKCS1Padding" 要求最小密钥长度为 512 位(否则会报 java.security.InvalidParameterException: RSA keys must be at least 512 bits long 异常)，也就是说生成的密钥、密文长度最小为 64 个字节。如果你还嫌大，可以通过调整算法提供者来减小密文长度：

Security.addProvider(new org.bouncycastle.jce.provider.BouncyCastleProvider());
final KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA", "BC");
keyGen.initialize(128);

1
2
3

如此这般得到的密文长度为 128 位(16 个字节)。但是这么干之前请先回顾一下上面第 4 点所述。

# 字符串用以保存文本信息，字节数组用以保存二进制数据

java.lang.String 保存明文，byte 数组保存二进制密文，在 java.lang.String 和 byte[] 之间不应该具备互相转换。如果你确实必须得使用 java.lang.String 来持有这些二进制数据的话，最安全的方式是使用 Base64(推荐 Apache 的 commons-codec 库的 org.apache.commons.codec.binary.Base64)：

  // use String to hold cipher binary data
  Base64 base64 = new Base64(); 
  String cipherTextBase64 = base64.encodeToString(cipherText);
  
  // get cipher binary data back from String
  byte[] cipherTextArray = base64.decode(cipherTextBase64);

1
2
3
4
5
6

# 每次生成的密文都不一致证明你选用的加密算法很安全

一个优秀的加密必须每次生成的密文都不一致，即使每次你的明文一样、使用同一个公钥。因为这样才能把明文信息更安全地隐藏起来。

Java 默认的 RSA 实现是 "RSA/None/PKCS1Padding"(比如 Cipher cipher = Cipher.getInstance("RSA");句，这个 Cipher 生成的密文总是不一致的)，Bouncy Castle 的默认 RSA 实现是 "RSA/None/NoPadding"。

为什么 Java 默认的 RSA 实现每次生成的密文都不一致呢，即使每次使用同一个明文、同一个公钥？这是因为 RSA 的 PKCS #1 padding 方案在加密前对明文信息进行了随机数填充。

你可以使用以下办法让同一个明文、同一个公钥每次生成同一个密文，但是你必须意识到你这么做付出的代价是什么。比如，你可能使用 RSA 来加密传输，但是由于你的同一明文每次生成的同一密文，攻击者能够据此识别到同一个信息都是何时被发送。

Security.addProvider(new org.bouncycastle.jce.provider.BouncyCastleProvider());
final Cipher cipher = Cipher.getInstance("RSA/None/NoPadding", "BC");

1
2

# Cipher 是有状态的，而且是线程不安全的

javax.crypto.Cipher 是有状态的，不要把 Cipher 当做一个静态变量，除非你的程序是单线程的，也就是说你能够保证同一时刻只有一个线程在调用 Cipher。否则可能会遇到 java.lang.ArrayIndexOutOfBoundsException: too much data for RSA block 异常。遇见这个异常，你需要先确定你给 Cipher 加密的明文(或者需要解密的密文)是否过长；排除掉明文(或者密文)过长的情况，你需要考虑是不是你的 Cipher 线程不安全了。

在 GitHub 编辑此页

上次更新: 2024/02/25, 12:11:11

← 公开秘钥基础知识 ECC 与 SM2→