非对称密码-RSA

本章内容主要为RSA密码的原理以及定位

分组密码在应用和协议的加解密中比较常用，非对称加密RSA因为加密效率的原因更多的用在密钥的分发方面

非对称密码中的RSA在当前互联网时代被广泛使用（网站、app、协议、桌面应用、服务器等等）。RSA加密算法是公钥密码体制中的一种，改算法基于数学理论而不是对称密码中的混淆和扩散。RSA密码算法当中加密和解密使用的是不同的密钥，因此被称为非对称密码。RSA是1977年由罗纳德·里维斯特、阿迪·萨莫尔和伦纳德·阿德曼一起提出的。RSA就是他们三人姓氏开头字母拼在一起的。

RSA原理来自数论相关知识。RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

找素数

• 选取两个大的随机素数

计算模n和Euler函数φ(n)

• $n = pq$
• $φ(n) = (p-1)(q-1)$

找$ed ≡ 1 mod φ(n)$

• 随机取一个数e（与φ(n)互素），用扩展Euclid算法求d即可

发布

• d保密，（d，n）是私钥$K_s$
• 发布（e，n），这是公钥$K_p$
• 销毁p、q

加密

​ $c = m^e ,mod ,n$

解密

​ $m = c^d,mod,n$

明文分组m为整数且必须小于n

消息发送的流程

1. 随机选择两个不相等的质数p和q例如61和53

2. 计算p和q的乘积n，$n = 61 ✖️ 53 = 3233$，3233写成二进制是110010100001，一共有12位，即这个密钥就是12位

3. 计算n的欧拉函数$φ(n)$

   根据公式：$φ(n) = (p-1)(q-1)$ 算出$φ(3233)$等于60✖️52，即3120

4. 选择一个整数e，条件是$1 < e < φ(n)$，且e与φ(n)互质。在1到3120之间，随机选择了17（实际应用中，常常选择65537）

5. 计算e对于φ(n)的模反元素d

   所谓“模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1

   ​ $ed ≡ 1(mod,φ(n))$

   ​ 等价于

   ​ $ed -1 = kφ(n)$

   于是，找到模反元素d，实质上就是对下面这个二元一次方程求解

   ​ $ex + φ(n)y = 1$

   已知$e = 17$ $φ(n) = 3120$

   ​ $17x + 3120y = 1$

   这个方程可以用“扩展欧几里得算法”求解，此处省略具体过程。总之，算出一组整数解为$(x, y) = (2753, -15)$，即$d = 2753$

6. 将n和e封装成公钥，n和d封装成私钥

   例如：n = 3233，e = 17， d = 2753，所以公钥就是（3233， 17），私钥就是（3233， 2753）。有了公钥和私钥，就能进行加密和解密了。

下面具体过程可以参考这篇帖子

安全性

对极大整数做因式分解的难度决定了RSA算法的可靠性。到目前为止公开的被破解的最长RSA密钥是768位。实际应用中一般情况下用1024位，重要场合2048位还都是安全的。

如何加密长信息

公钥（n，e）只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种“对称加密算法（例如：DES）”，用这种算法的密钥加密信息，再用RSA公钥加密DES密钥

因为RSA的加密效率原因，通常会采用第二种方式

RSA中的填充

在之前的分组加密中，Padding只是用来填充数据到指定的长度，而RSA通常不会加密特别长的数据，因此没有分组模式的概念，对于RSA来说Padding是既有分组模式的概念又有随机数的概念。即RSA的Padding包含了将数据填充到RSA密钥位数的长度的方法，还有填充随机数到RSA原文的方法

RSA算法的本质就是大数运算

​ $m^e ≡ c(mod\ n)$

​ $c^d ≡ c(mod\ n)$

其中m是原文，c是密文。如果使用原始的RSA做加解密操作，则并不包含随机数，相同的密文会生成相同的明文。同时由于大部分情况下m相比n小很多，甚至$m^e$都比n要小，这时候很容易通过枚举倍数破解明文。因此RSA加解密算法很需要有效的Padding算法讲明文填充到足够长保证不容易被暴力破解，这也就是加入随机因子保证密文的随机性的一个原因。

查看RSA密钥

用openssl生成一个RSA的key来看一下

生成

openssl genrsa -out pv.key 1024

从私钥中获取p、q、n、e、d信息

实现RSA

在C/C++中使用RSA：不得不提的OpenSSL

OpenSSL开源库中针对当前流行密码学领域相关算法都进行了实现，其中就包含有非对称密码中的RSA算法。对于开发人员来说，很难去自己实现一个兼顾鲁棒性和效率的RSA加解密代码，因此也就一般都直接使用OpenSSL开源库。Google创建了OpenSSL分支：BoringSSL，但Google不打算取代OpenSSL，使用BoringSSL的代码不能保证API或ABI的稳定性，他们会继续向OpenSSL递交bug修正，继续资助相关的开源基金会。

hook和定位RSA

对于Java层的RSA还是和之前DES、AES一样，都是调用cipher实现的，所以还是同样的hook方式

对于so层来说，它的实现基本都是直接使用openssl的公开库，直接调用的。因此对于它的识别只需要使用ida插件快速定位到openssl库就可以了

定位RSA算法主要有：识别常量表、控制流、重放、识别OpenSSL库的版本制作签名库几种方法。