最近做 secure boot 涉及到 image 的 签名和加密，用到最重要的算法之一就是RSA算法。今天就简单聊一下RSA算法。

炸裂的RSA！

RSA算法在密码界拥有绝对的地位，原因很简单：

• 历史悠久： RSA算法是1977年由麻省理工的Ron Rivest，Adi Shamir，Leonard Adleman 共同提出，RSA来自于三个人的姓氏首字母，历经三十多年经久不衰。
• 原理简单： 基本上密码学都脱胎于数学，RSA算法虽然难以破解，但在数学上可以算得上十分简洁优美。它的原理十分简单：计算两个大素数的乘积很容易，但是将这个乘积重新分解为两个大素数非常难。
• 有效：RSA算法虽然很有历史，原理也十分简单，却经住了时间的考验，至今没有有效的攻击方式，属于ISO加密标准的一部分。
• 应用广泛： RSA算法是第一种既可以用于加密也可以用于签名的算法，简单的说就是既可以用来保护我的信息内容不被别人看见，又可以用来证明这个东西确实是我写的，不同场合都可以灵活使用。

所以说不管你从哪个方向入门密码学，RSA算法都是当之无愧的经典必学。

介绍RSA算法之前，先来介绍两组常用的概念。

对称与非对称

介绍任何一种加密算法，都会首先说明该算法是属于对称加密，还是属于非对称加密，RSA算法就是一种非对称加密算法。对称与非对称是密码算法中的一种分类方式，最直白的解释就是对称加密算法的密钥只有一个，这个密钥必须得到很好的保护，不能泄露；而非对称加密算法的密钥有两个，一个叫公钥，公开可见，用于加密，一个叫私钥，需要保密，用于解密。
最简单的对称加密的例子就是密码本，发送方按照密码本先把明文翻译成密文，接收方再对着密码本翻译一遍就知道内容了。坏处就是一旦密码本被偷，整个加密过程就没意义了。
非对称加密的简单例子就是钥匙和锁，接收方有一把锁和一把钥匙，把锁给发送方，钥匙自己留着，发送方拿锁把东西锁上，路上谁拿走都没用，只有接收方的钥匙才能打开锁拿东西。这里的锁就是密码学意义上的公钥，钥匙就是密码学意义上的私钥。既然RSA算法是非对称加密算法，那么也就意味着RSA算法需要生成一公一私两个密钥。
对称加密算法虽然在安全性上没有非对称加密算法高，但是这两种算法之间并没有绝对的好坏之分。对称加密的效率远高于非对称加密，在实际应用场景中，会根据使用环境和数据的特点将两种算法结合使用，达到安全和效率的统一。

加密与签名

加密和签名本身的概念很好理解，加密是为了防止信息被别人看到，而签名则是为了证明信息确实为本人所发。通常来说我们发送各种数据，一般会有以下要求：

• 保密性：发送的内容不会被无关的人看到；
• 完整性：发送的内容不会被无关的人篡改；
• 合法性：发送内容的来源是合法有效的。

要做到保密性，就是对传递的数据进行加密，使用非对称加密算法加密的一般流程是：

1. 接收数据方首先准备生成一对RSA密钥，将公钥发布，保留私钥；
2. 发送数据方拿接收方的公钥对数据加密，然后发给接收方；
3. 接收方拿自己的私钥进行解密，查看数据内容。

而签名则可以用来验证数据的合法性和完整性。以软件安装升级包为例，采用非对称加密算法做校验的简化流程是：

1. 软件发布方准备好package，首先计算package的 hash，将 hash 和 package 一起用软件发布方的私钥签名，发布加密后的 package 和发布方的公钥；
2. 用户接收到发布方的更新后，首先拿发布方的公钥对 package 进行解密，如果成功解密证明该 package 确实来自合法的发布方，然后对 package 也进行一次 hash 计算，与发布方的 hash 做对比，验证 package 是否被篡改。

简而言之，公钥加密私钥解密的过程称之为加密解密，私钥加密公钥解密的过程称之为签名验证。而在一套方案中同时考虑保密性，完整性和合法性，就需要设计更为复杂的签密方案，对RSA算法来说，一般就需要两个密钥对共同完成了。

一个思考：如果 hacker 劫持发布方的 package 和 公钥，解密并修改了 packet 的内容植入病毒或者木马，然后用自己的私钥加密数据，发布自己的公钥和 packet 给用户，用户要如何才能识别呢？

其实这就是所谓的中间人攻击，也就是数字证书的存在意义了，简单说就是用数字证书证明发布方公钥的有效性，而能够颁布数字证书的通常就是官方认可的证书授权中心，简称CA机构，类似于能够颁发身份证的公安机关。
可见加密和签名本身的概念虽然并不复杂，但为了抵抗各类攻击设计出的安全策略实在可以写出厚厚一本书。

公钥和私钥的区别

在签名和加密的过程中，一会使用公钥加密数据，一会使用私钥加密数据，那么公钥和私钥的区别到底是什么呢。
事实上，从数学的角度来说，公钥和私钥的地位是同等的，用其中任意一个加密，另外一个都可以拿来解密。公私之分，完全取决于选择公开哪一个。虽然在数学上两者没有严格的区分，但是在实际应用中，选择公开哪一个却并不是随便选的。在生成密钥的过程中，我们既要保证密钥的长度，也要考虑到计算的复杂性，所以我们一般会选择长度较短的作为公钥，长度较长的保留为私钥。在RSA算法生成密钥的过程中，选取65537作为公钥几乎是一个惯例，所以说公钥和私钥并不是随便选一个公开或保留就可以的。

RSA算法逻辑

很多安全相关的开源库，例如openssl，boringssl，libtomcrypt 等等，都有完善的 RSA算法实现，一般来说都分为密钥的生成，加密，解密三个部分，下面简单介绍一下这三个部分的数学逻辑，这样能更好的理解代码。

密钥的生成

参考代码：https://github.com/libtom/libtomcrypt/blob/develop/src/pk/rsa/rsa_make_key.c
这部分代码其实非常好懂，首先通过伪随机数计算出两个大素数 p 和 q，计算 p 和 q 的乘积 N，然后计算 （p-1）和 （q-1）的最小公倍数 L。在 1 和 L 之间选一个数 E（约定俗成 E = 65537），（N, E）就是公钥。
最后计算私钥 D，D 满足如下条件：E＊D mod L ＝ 1，那么（N，D）就是私钥了。

用公钥加密

参考代码：https://github.com/libtom/libtomcrypt/blob/develop/src/pk/rsa/rsa_encrypt_key.c
加密过程只需要计算以下公式即可：

encrypt.png

用私钥解密

参考代码：https://github.com/libtom/libtomcrypt/blob/develop/src/pk/rsa/rsa_decrypt_key.c
解密过程只需要计算以下公式即可：

decrypt.png

以上可以看出RSA算法真的是具有简洁的数学美感。
只是软件实现上，RSA算法的运算代价很高，在长密钥大数据的情况下，计算真的是非常的缓慢 ：）
以上就是RSA算法的简单介绍了，其实也真的蛮简单的~