RSA加密与解密

46次阅读

共计 10029 个字符，预计需要花费 26 分钟才能阅读完成。

数据信息安全对我们每个人都有很重要的意义，特别是一些敏感信息，可能一些类似于收货地址、手机号还没引起大家的注意。但是最直白的，银行卡、姓名、手机号、身份证号，如果这些信息被黑客拦截到，他就可以伪装成你，把你的钱都取走。那我们该怎么防止这样的事情发生？报文加密解密，加签验签。

我害怕什么

我害怕卡里的钱被别人取走

我害怕转账的时候，报文被黑客拦截到，篡改信息转到别人的账户。

我害怕我的敏感信息被有心人获取

做一笔游戏充值，半个小时就收到各种游戏广告，我并不能抵挡诱惑

我要做什么

  1. 交易报文不被篡改

    防止报文被篡改，需要对报文进行验签操作。

  2. 敏感信息不被读取

    防止报文被读取，则需要将敏感信息加密。

公钥和私钥

公钥和私钥，加密解密和加签验签。加解密用来保证数据安全，加签验签用来证明身份。

商户生成一对公私钥(商公，商私)，商户会把公钥给银行；银行也会生成一对公私钥(银公，银私)，银行会把公钥给商户。也就是说：商户有银行的公钥，自己的公钥和私钥。银行有商户的公钥，自己的公钥和私钥

  • 加密解密保证数据安全：

    • 商户使用自己公钥加密，银行没有商户私钥解不开报文，排除
    • 商户使用自己的私钥加密，银行使用商户公钥解密。理论上可行，然而会出现这种情况，商户和银行 1，2，3 都使用相同的公私钥，那么自己私钥加密后发送给银行 1 的报文，被银行 2 截取到也可以被解密开，违背了我们加密的目的 – 保证数据安全，排除。
    • 商户使用银行的公钥加密，让银行用自己的私钥解密。理论上可行，然而会出现这种情况，银行会和商户 A，B，C 都使用相同的公私钥，那么商户 A 和商户 B 发送过去的报文，银行都能解开，而且只有此银行的私钥可以解开，达成了我们的目的。但是新的问题出现了，这种情况假如商户 A 模拟商户 B 的报文把商户 B 的钱转移走该怎么办？所以除了加密解密，还需要加签验签。

  • 加签验签证明身份：

    • 加密已经完成，现在的问题只有怎么让银行区分这笔请求是商户 A 发的，还是商户 B 发的。想让银行区分出各个商户，拿出各个商户最独特的私钥加签即可，银行拿出对应的商户公钥验签即可。
  • 到此，报文交互形成了一个稳定且安全的循环

带上代码设计一套加解密

结构

两对 SHA1withRSA 公私钥 +DES 会话密钥。结构如下：

加密加签步骤：

  1. 使用 KeyGenerator 随机生成一个会话密钥 desKey
  2. 报文明文 + 会话密钥明文 desKey 对称加密得到加密后的密文 message。
  3. 银行的公钥 + 会话密钥 desKey 非对称加密得到加密后的会话密钥 key。
  4. 报文明文 + 商户的私钥非对称加密得到报文数字签名 sign。
  5. 将 sign 和 key 和 message 传递给银行。

解密验签步骤：

  1. 加密后的会话密钥 key+ 银行的私钥解密得到会话密钥明文 desKey
  2. 对称加密得到的密文 message+ 会话密钥明文 desKey 解密得到报文明文
  3. 得到的明文 + 商户的公钥验签，得到报文是否被中途篡改过
代码

  1. 使用 KeyGenerator 随机生成一个会话密钥 desKey

    KeyGenerator keyGenerator = KeyGenerator.getInstance("DES");
SecretKey secretKey = keyGenerator.generateKey();
return secretKey.getEncoded();

  2. 报文明文 + 会话密钥明文 desKey 对称加密得到加密后的密文 message。

    public static String encryptContext(String context, byte[] desKey) throws Exception {byte[] encryptResult = des(context.getBytes("UTF-8"), desKey, 1);
    return Hex.encodeHexString(encryptResult);
}

private static byte[] des(byte[] inputBytes, byte[] keyBytes, int mode) throws Exception {DESKeySpec desKeySpec = new DESKeySpec(keyBytes);
    SecretKeyFactory keyFactory = SecretKeyFactory.getInstance("DES");
    SecretKey secretKey = keyFactory.generateSecret(desKeySpec);
    IvParameterSpec iv = new IvParameterSpec(keyBytes);
    Cipher cipher = Cipher.getInstance("DES/CBC/PKCS5Padding");
    cipher.init(mode, secretKey, iv);
    return cipher.doFinal(inputBytes);
}

  3. 银行的公钥 + 会话密钥 desKey 非对称加密得到加密后的会话密钥 key

    /**
 * RAS 加密
 * 
 * @return byte[]
*/

public byte[] encryptRSA(byte[] plainBytes, boolean useBase64Code, String charset)

     throws Exception {
  String CIPHER_ALGORITHM = "RSA/ECB/PKCS1Padding"; // 加密 block 需要预留 11 字节
  int KEYBIT = 2048;
  int RESERVEBYTES = 11;
  Cipher cipher = Cipher.getInstance(CIPHER_ALGORITHM);
  int decryptBlock = KEYBIT / 8; // 256 bytes
  int encryptBlock = decryptBlock - RESERVEBYTES; // 245 bytes
  // 计算分段加密的 block 数 (向上取整)
  int nBlock = (plainBytes.length / encryptBlock);
  if ((plainBytes.length % encryptBlock) != 0) { // 余数非 0，block 数再加 1
     nBlock += 1;
  }
  // 输出 buffer, 大小为 nBlock 个 decryptBlock
  ByteArrayOutputStream outbuf = new ByteArrayOutputStream(nBlock * decryptBlock);
  cipher.init(Cipher.ENCRYPT_MODE, peerPubKey);
  // 分段加密
  for (int offset = 0; offset < plainBytes.length; offset += encryptBlock) {
     // block 大小: encryptBlock 或 剩余字节数
     int inputLen = (plainBytes.length - offset);
     if (inputLen > encryptBlock) {inputLen = encryptBlock;}
     // 得到分段加密结果
     byte[] encryptedBlock = cipher.doFinal(plainBytes, offset, inputLen);
     // 追加结果到输出 buffer 中
     outbuf.write(encryptedBlock);
  }
  // 如果是 Base64 编码，则返回 Base64 编码后的数组
  if (useBase64Code) {return Base64.encodeBase64String(outbuf.toByteArray()).getBytes(charset);
  } else {return outbuf.toByteArray(); // ciphertext
  }

}


4. 报文明文 + 商户的私钥非对称加密得到报文数字签名 sign。

/**

* RSA 签名
* 
* @return byte[]
* @throws Exception
*/

public byte[] signRSA(byte[] plainBytes, boolean useBase64Code, String charset) throws Exception {

  Signature signature = Signature.getInstance("SHA1withRSA");
  signature.initSign(localPrivKey);
  signature.update(plainBytes);
  // 如果是 Base64 编码的话，需要对签名后的数组以 Base64 编码
  if (useBase64Code) {return Base64.encodeBase64String(signature.sign()).getBytes(charset);
  } else {return signature.sign();
  }

}


5. 加密后的会话密钥 key+ 银行的私钥解密得到会话密钥明文 desKey；对称加密得到的密文 message+ 会话密钥明文 desKey 解密得到报文明文

/**

* RSA 解密
* 
* @param cryptedBytes
*            待解密信息
* @return byte[]
* @throws Exception
*/

public byte[] decryptRSA(byte[] cryptedBytes, boolean useBase64Code,

     String charset) throws Exception {
  String CIPHER_ALGORITHM = "RSA/ECB/PKCS1Padding"; // 加密 block 需要预留 11 字节
  byte[] data = null;
  // 如果是 Base64 编码的话，则要 Base64 解码
  if (useBase64Code) {data = Base64.decodeBase64(new String(cryptedBytes, charset));
  } else {data = cryptedBytes;}
  int KEYBIT = 2048;
  int RESERVEBYTES = 11;
  Cipher cipher = Cipher.getInstance(CIPHER_ALGORITHM);
  int decryptBlock = KEYBIT / 8; // 256 bytes
  int encryptBlock = decryptBlock - RESERVEBYTES; // 245 bytes
  // 计算分段解密的 block 数 (理论上应该能整除)
  int nBlock = (data.length / decryptBlock);
  // 输出 buffer, , 大小为 nBlock 个 encryptBlock
  ByteArrayOutputStream outbuf = new ByteArrayOutputStream(nBlock * encryptBlock);
  cipher.init(Cipher.DECRYPT_MODE, localPrivKey);
  // 分段解密
  for (int offset = 0; offset < data.length; offset += decryptBlock) {
     // block 大小: decryptBlock 或 剩余字节数
     int inputLen = (data.length - offset);
     if (inputLen > decryptBlock) {inputLen = decryptBlock;}
     // 得到分段解密结果
     byte[] decryptedBlock = cipher.doFinal(data, offset, inputLen);
     // 追加结果到输出 buffer 中
     outbuf.write(decryptedBlock);
  }
  outbuf.flush();
  outbuf.close();
  return outbuf.toByteArray();

}


6. 得到的明文 + 商户的公钥验签，得到报文是否被中途篡改过

public boolean verifyRSA(byte[] plainBytes, byte[] signBytes,

     boolean useBase64Code, String charset) throws Exception {Signature signature = Signature.getInstance("SHA1withRSA");
  signature.initVerify(peerPubKey);
  signature.update(plainBytes);
  // 如果是 Base64 编码的话，需要对验签的数组以 Base64 解码
  if (useBase64Code) {return  signature.verify(Base64.decodeBase64(new String(signBytes, charset)));
  } else {return signature.verify(signBytes);
  }

}


代码只给出了一部分重要的加解密，加验签逻辑。还有一些逻辑都贴出来有点乱，就放在仓库里了，具体用法查看 README 即可，[更详细的参考放在 demo 里](https://gitee.com/metabolism/decry_eencrypt_mock)

### 思考：为什么 RSA 公钥加密的值一定只有私钥才能解开，不能暴力破解？？其实 RSA 的原理很简单，运用了数学的一个难题：两个大的质数相乘，难以在短时间内将其因式分解。原理很简单，但实际上操作真的很难。##### 时间复杂度 --O

我们都知道计算机的计算速度非常快，计算几十位数的加减法都是秒出。然而，虽然计算机很快，但再快也是有上限的。比如我电脑的 CPU 主频是 2.30GHz，也就是说我的电脑每秒可以进行 2300000000 次最基本的运行。![](https://image-static.segmentfault.com/121/362/1213624279-5dd4d4d083d21_articlex)

计算机的计算能力有限，就算是超级计算机“天河二号”，每秒也只能算 3.39 亿亿 (这里多了个亿，给大佬跪了 orz) 次。对应的，我们有一个参数来衡量一个程序的耗时，叫做时间复杂度：| 多项式量级                                                   | 不严格的通俗例子(输入规模![[公式]](https://www.zhihu.com/equation?tex=n%3D10%5E9)) |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| 常量阶 ![O(1)](https://math.jianshu.com/math?formula=O(1))   | 只用 1 次运算, 普通电脑 ![[公式]](https://www.zhihu.com/equation?tex=10%5E%7B-9%7D) 秒就能算完。|
| 对数阶 ![O(\log{n})](https://math.jianshu.com/math?formula=O(%5Clog%7Bn%7D)) | 大约会用 30 次计算，普通电脑 ![[公式]](https://www.zhihu.com/equation?tex=10%5E%7B-8%7D) 秒算完 |
| 线性阶 ![O(n)](https://math.jianshu.com/math?formula=O(n))   | ![[公式]](https://www.zhihu.com/equation?tex=10%5E9) 次计算，普通电脑需要一秒左右 |
| 线性对数阶 ![O(n log n)](https://math.jianshu.com/math?formula=O(n%20log%20n)) |                                                              |
| 平方阶 ![O(n^{2})](https://math.jianshu.com/math?formula=O(n%5E%7B2%7D)), 立方阶 ![O(n^{3})](https://math.jianshu.com/math?formula=O(n%5E%7B3%7D)) | 大约是 ![[公式]](https://www.zhihu.com/equation?tex=10%5E%7B18%7D) 次计算，普通电脑大概要 30 年。|

| 非多项式量级                                                 | 不严格的通俗例子(输入规模![[公式]](https://www.zhihu.com/equation?tex=n%3D10%5E9)) |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| 指数阶 ![2^{n}](https://math.jianshu.com/math?formula=2%5E%7Bn%7D) | 大约 2^1000000000 次计算，心态崩了                             |
| 阶乘阶 n！| 人类所有电脑加在一起，等太阳炸了都算不完                     |

算法复杂度有各种各样的，有 ![[公式]](https://www.zhihu.com/equation?tex=O%281%29)，![[公式]](https://www.zhihu.com/equation?tex=O%28logn%29), ![[公式]](https://www.zhihu.com/equation?tex=O%28n%29), ![[公式]](https://www.zhihu.com/equation?tex=O%28n%5E2%29), ![[公式]](https://www.zhihu.com/equation?tex=O%282%5En%29)……上述几个复杂度的算法一个比一个慢。通俗的讲，大 O 后面括号里面 ** 函数的增长速度越快，算法越耗时 **。总的来说，RSA 之所以理论上非常安全，是因为破解 RSA 所要付出地计算成本远远高于使用 RSA 进行加密的计算成本。* 使用 RSA 的私钥进行解密，耗用的时间复杂度是 ** 多项式级 **。* 不使用 RSA 私钥，暴力破解，需要分解质因数，他的时间复杂度是 ** 非多项式级 ** 的 ** 指数级 **。* 也就是有私钥解密只要一秒，暴力破解出结果时，人类可能已经毁灭了(不严格)。##### RSA 生成公私钥数学计算流程：1. 商户随机生成了一些非常非常大的整数，并用 Miller-Rabin 算法检测它们是不是质数，直到找到两个大质数——![[公式]](https://www.zhihu.com/equation?tex=p_1) 和 ![[公式]](https://www.zhihu.com/equation?tex=p_2)。（随机数生成：多项式时间；Miller-Rabin: 多项式时间）2. 商户计算两个质数的乘积 ![[公式]](https://www.zhihu.com/equation?tex=n%3Dp_1p_2)（乘法: 多项式时间）3. 商户计算 φ(n) = (p1 - 1)(p2 - 1)（乘法: 多项式时间），这一步难以被破解，因为 n 太大了，分解质因数需要指数级时间复杂度。人类毁灭前是根据 n 推算出 φ(n)可能性极小。* ** 欧拉函数：φ(n)表示：小于 n 的正整数中与 n 互质的数的数目。**（互质表示公因数为 1）比如想要知道 φ(10)的话，我们就可以看 [1, 10) 中和 10 互质的整数，也就是 1、3、7、9 这四个数。（2、4、6、8 和 10 有公因数 2，而 5 和 10 有公因数 10）。所以 φ(10)=4。比如想要知道 φ(21)的话，我们就可以看 [1, 21) 中和 21 互质的整数，也就是 1、2、4、5、8、10、11、13、16、17、19、20 这 12 个数。（3、6、9、12、15、18 和 21 有公因数 3，而 7、14 和 21 有公因数 7）。所以 φ(21)=12。4. 商户构造了一个比 1 大、比 φ(n)小、不等于 ![[公式]](https://www.zhihu.com/equation?tex=p_1) 或 ![[公式]](https://www.zhihu.com/equation?tex=p_2) 的整数 e。（随机数：多项式时间）5. 商户求出了 e 对于 φ(n)的乘法逆元 d，也就是说 **ed ≡ 1（mod φ(n)）**，也就是说 ed=kφ(n)+1 (扩展欧几里得，多项式时间)

6. ** 请注意！现在神奇的事情发生了！对于一个与 n 互质的数 a：**

因为 ![[公式]](https://www.zhihu.com/equation?tex=a%5E%7B%CF%86%28n%29%7D%E2%89%A11+) (mod n)

所以 ![[公式]](https://www.zhihu.com/equation?tex=a%5E%7Bk%CF%86%28n%29%7D%E2%89%A11)  (mod n)

所以 ![[公式]](https://www.zhihu.com/equation?tex=a%5E%7Bk%CF%86%28n%29%2B1%7D%E2%89%A1a) (mod n)

所以 ![[公式]](https://www.zhihu.com/equation?tex=a%5E%7Bed%7D%E2%89%A1a) (mod n)

所以，若 ![[公式]](https://www.zhihu.com/equation?tex=c%5Cequiv+a%5Ee) (mod n), 则![[公式]](https://www.zhihu.com/equation?tex=c%5Ed%5Cequiv+a%5E%7Bed%7D+%5Cequiv+a)（mod n）** 到这里，两把钥匙构造完成！ㄟ (≧◇≦) ㄏ **

** 公钥：（n, e）**

** 密钥：（n, d）**

##### RSA 公私钥加密解密

商户想要生成一对公私钥的时候：* 首先随意选择两个大的质数 p 和 q，p 不等于 q，计算 N =pq。* 根据欧拉函数，求得 r = (p-1)(q-1)
* 选择一个小于 r 的整数 e，求得 e 关于模 r 的模反元素，命名为 d。（模反元素存在，当且仅当 e 与 r 互质）* 将 p 和 q 的记录销毁。* (N,e)是公钥，(N,d)是私钥。商户将她的公钥 (N,e) 传给银行，而将自己的私钥 (N,d) 藏起来。商户进行加密的时候：* 假设商户想给银行送一个消息 m，他知道银行的公钥，换句话说是银行公钥的 N 和 e。他使用起先与银行约好的格式将 m 转换为一个小于 N 的整数 n，比如他可以将每一个字转换为这个字的 Unicode 码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为 n。用下面这个公式他可以将 n 加密为 c：​        ne ≡ c (mod N)
  计算 c 并不复杂。商户算出 c 后就可以将它传递给银行，也就是密文啦。银行想要解密的时候：* 银行得到商户的密文消息 c(商户使用银行公钥加密后的密文)后就可以利用他的私钥 d 来解码。他可以用以下这个公式来将 c 转换为 n：cd ≡ n (mod N)
  得到 n 后，他可以将原来的信息 m 重新复原。### 其他的概念

##### 素数

素数又称质数，指在一个大于 1 的自然数中，除了 1 和此整数自身外，不能被其他自然数整除的数

##### 互质数

互质，又称互素。若 N 个整数的最大公因子是 1，则称这 N 个整数互质。##### 指数运算

指数运算又称乘方计算，计算结果称为幂。nm 指将 n 自乘 m 次。把 nm 看作乘方的结果，叫做”n 的 m 次幂”或”n 的 m 次方”。其中，n 称为“底数”，m 称为“指数”。##### 模运算

模运算即求余运算。##### 同余

当两个整数除以同一个正整数，若得相同余数，则二整数同余。##### 会话密钥

前提：对称加密速度要比非对称加密快速。会话密钥是一个随机生成的对称式加密密钥，举个例子：A 和 B 交互，A 随机挑了一个字符串，用 B 的公钥加密发给了 B，告诉 B 这个随机字符串就是他们之间用来交流的密钥了，之后 A 和 B 的报文就可以不用公私钥非对称加密，直接用这个密钥对称加密即可。对称式加密算法有很多：AES/DES 等。SSH 通信的数据就是用 AES 之类的对称式加密算法加密的。(在 SSH 协商密钥的过程中，还会使用专门的 ** 密钥协商算法（Key Exchange Algorithm）**，确保窃听者无法偷听到密钥的内容)

##### 中间人攻击

即当商户发送公钥给银行的时候，黑客截取了商户的公钥，同时把自己公钥发给银行，这样一直在与银行通信的并不是商户。##### CA 认证中心

专门提供网络身份认证服务的机构或团体

### 总结

数学的魅力在于将这个世界变得井井有条，试想当计算机的运行速度越来越快，RSA 会被破解吗？不见得，1999 年 N(两个大质数的乘积)位数是 512，后面发展成了位数是 1024 和 2048 位，计算机速度变快之后，每台电脑能处理的位数也会越来越大，我相信我们会见到更长位数的 N，十万，甚至百万....

浩瀚世界，自己真渺小


----

正文完
发表至： java
2019-11-20
 0
关于java:老大让我优化数据库我上来就分库分表他过来就是一jio
你不知道的浏览器页面渲染机制
关于java:特殊空格分隔符
关于java:做了5年后端研发靠着这份面试题跟答案我从12K变成了30K