密码学基础 -- 走进RSA(放弃数学原理版)

lixinfu

目录

1. 密钥对的使用时机

2. RSA测试

2.1 加解密实验

2.2 签名验签测试

3. RSA原理简介

4.小结

---

在讲RSA原理时，咱们先来思考非对称算法的几个问题。

使用RSA对数据进行加密时，应该使用公钥还是私钥？那解密的时候呢？使用RSA对Hash进行签名时，应该使用公钥还是私钥？那验签的时候呢？做安全启动时，大家是否对RSA验签实现里各种奇奇怪怪的字母感到困惑？例如n、e、d；

那么我们带着问题动手撸撸代码来熟悉RSA。
1. 密钥对的使用时机

非对称算法的特性在于加密过程和解密过程使用的是不同的密钥，其中可以对外公开的密钥叫做公钥，只能自己保管的密钥叫做私钥，这两个密钥共同构成密钥对；由于RSA算法本身的数学属性(单向陷门原理)，密钥对有这样一种巧妙的关联(先记住它)：

使用公钥加密数据，则只能通过私钥进行解密；使用私钥进行加密，则需通过公钥进行解密。

上述过程我们可以请出老朋友Bob和Alice来进行演示，具体如下图：

Bob想要给Alice写信，但又不想让别人知道信的内容，因此他用Alice给的公钥对信的内容继续加密；Alice拿到加密后的内容后，使用自己的私钥解密，从而得到"Hello Alice”。这就回答了今天的第1个问题，当想要加密时，应该选择对应公钥进行加密；其他几种情况都不能满足信息安全的要求：

如果Bob用自己的公钥加密，那么就只能他自己用私钥解密，Alice拿到密文也没有用；如果Bob用自己的私钥加密，那么所有获得他公钥的人都可以解密。

那么签名又应该如何使用密钥呢？我们先搞懂什么是签名，一般来说，所谓签名就是用来证明自己身份的机制，具体到细节其实就是用非对称算法对消息摘要做加密。既然要证明我就是我，思考一下，在非对称算法里什么是私密的呢？毫无疑问就是自己的私钥；因此在签名过程中，应当使用自己的私钥对消息摘要进行签名，那么所有获得公钥的人都可以验证签名；而由于私钥的私密性，他人基本无法冒充，从而证明了我就是我。老规矩，Bob要向Alice证明消息就是他发的，如下图：

Bob使用Hash函数对"Hello Alice"计算出摘要；Bob为了证明消息是自己发的，用自己的私钥对摘要进行加密，也即签名；并把消息和签名同时发送给Alice；Alice拿到数据后，首先对"Hello Alice”使用同样Hash函数进行摘要计算，得到消息原始Hash值；使用Bob对外公开的公钥，对签名进行解密得到待校验的Hash值；将上述Hash进行比对，如果值一致，则证明是Bob发送的消息。

同样的，如果用其他的密钥进行签名会出现什么情况呢？

如果Bob使用自己的公钥签名，那只有自己才能验，Alice不知道是谁发的；如果Bob用Alice的公钥签名，虽然只有Alice能验证，但是由于只要是获得了Alice公钥的人都可以签名，不能证明是Bob发的

---

2. RSA测试

我们从一个具体的RSA签名试验开始认识其原理。在之前文章，我们已经生成了基于RSA的密钥对，格式如下：



但是这一堆乱码简直没办法分析，所以我们通过openssl将密钥对hex数据打印出来，如下：

公钥Hex数据



私钥Hex数据公钥里包含了模数(Modulus)、指数(Exponent)；私钥包含了模数(Modulus)、私钥指数(privateExponent)、公钥指数(publicExponent)、prime(质数)1\2、exponent(指数)1\2、系数(coefficient).根据RFC8017定义，并结合示例，可以总结公私钥的构成如下：

2.1 加解密实验

首先使用openssl对demo.txt进行加密，生成密文文件demo.en，如下：

然后使用私钥进行解密，得到demo_enc.txt，如下：

2.2 签名验签测试

首先使用openssl对文档signDemo.txt进行签名，得到签名hex，如下：

然后进行验签，得到验签结果，如下：


3. RSA原理简介

有了上述测试，我们对RSA有了感性认识，接下来就讲点纯理论的东西。RSA是由麻省理工的Rivest、Shamir和Adleman在1978年提出，其数学基础用到了欧拉定理，安全性由大因子分解十分困难保证，利用了单向陷门函数的原理，具体如下：

其中{e,n}表示公钥，{d,n}表示私钥。该算法安全在哪里呢？在于私钥难以被破解。 该算法生成密钥的过程如下：

选择两个大素数p和q（通常要求每个素数均大于10的100次方）计算一个 n = p * q ，φ(n) = (p-1)*(q-1)在（1，φ(n)）之间找到一个整数e，该数与φ(n)互质；e作为公钥根据e和φ(n)计算出私钥d，必须满足 e*d mod φ(n) = 1；密钥对 {{e，n} , {d，n}}将明文划分成块，记为m，保证每个明文的长度 len(m) < n加密过程：c = m^e mod n  (加密需要公钥e 和 n)解密过程：m = c^d mod n   (解密需要私钥d 和 n)

以上述为例：攻击者可以容易获取到的数据有密文c、模数n和公钥e，几乎不能获取私钥d；解密需要私钥d，d是根据e和φ(n)计算得来，n有p和q计算得出 因此需要对n进行因子分解，找出两个素数p和q 例如 21，很容易得出两个素数3 和7，但如果n为2048bit的整数，目前从数学角度难解决。

---

4.小结

上面文章，我们讲述了非对称算法的加解密、签名验签的原理，并做了相关测试工作；从数学角度讲述了RSA密钥生成原理，并且详细阐述了RSA中每个字母的含义。这对基于硬件密码加速引擎实现非对称算法具有非常强的参考意义。一般来讲，HSM所能提供的非对称算法的硬件加速功能通常只包含数学运算，例如加减乘除、模数运算等等，我们要实现RSAES、RSASSA、ECDSA等算法，是需要利用这些运算加速来实现公式的，举个例子，假设要实现RSA签名工作，首先需要调用Hash加速器来生成摘要，然后通过调用模幂运算来对摘要进行加密，这就需要我们理解模数、指数应该分别放到指定的寄存器里以供非对称引擎调用。

---

往期回顾：

1.汽车标定精选
汽车标定技术--标定概念详解
汽车标定技术--Bypass的前世今生
万字长文：汽车标定技术--XCP概述

2.AUTOSAR精选
AUTOSAR CryptoStack--CSM Job夹带了哪些私货
AUTOSAR 诊断栈分析(一)
AUTOSAR OS概述（一）

3.汽车网络安全精选
汽车信息安全--MCU启动常用密码算法
汽车网络安全方案需求分析
汽车信息安全--常见车规MCU安全启动方案
车载信息安全场景概述

4.汽车功能安全精选

5.汽车虚拟化精选

    汽车ECU虚拟化技术初探(一)

    汽车ECU虚拟化技术(二)--U2A虚拟化功能

6.杂七杂八

    Flash模拟EEPROM原理浅析

    征途漫漫:汽车MCU的国产替代往事

    车规MCU应用场景及国产替代进展