关于RSA的学习整理

作者: 0HP | 来源:发表于2022-03-20 15:27 被阅读0次

一、RSA原始模型整理

1. 基础理论：欧拉函数与欧拉定理

欧拉函数： $\phi(n)$ ，表示[1,n)中与n互素的数的个数。
显然若n为素数，那么 $\phi(n)=n-1$ 。
且欧拉函数满足以下关系：若 $n=p\cdot q$ ，有 $\phi(n)=\phi(p\cdot q)=\phi(p)\cdot \phi(q)$

欧拉定理： $m^{\phi(n)} \equiv 1(mod\ n)$

2. RSA基本原理

（1）需要参数

实现RSA需要两个大素数： $p,q$ ，且有模数 $n=p\cdot q$
求其欧拉函数： $\phi(n)=\phi(p)\cdot \phi(q)=(p-1)\cdot (q-1)$
选取公钥 $e$ (例如熟知的65537)， $e$ 需要与 $\phi(n)$ 互素，计算私钥d。
私钥d满足 $e\cdot d\equiv 1 (mod \ \phi(n))$ ，且称d是e模n的乘法逆元
（私钥d可由egcd拓展欧几里得算法计算）
上诉等式亦可写成： $k\cdot \phi(n)+1=e\cdot d$ (k为任意正整数)

（2）加解密过程

有明文 $m(m<n)$ ，用公钥加密得密文 $C\equiv m^e(mod\ n)$
用私钥解密得：
$\begin{equation} \begin{aligned} C^d &=m^{e\cdot d} mod\ n\\ &=m^{k\cdot \phi(n)+1} mod\ n\\ &=m^{k\cdot \phi(n)}\cdot m\ mod\ n\\ &=(m^{\phi(n)})^k \cdot m\ mod\ n\\ &=((m^{\phi(n)})^k\ mod\ n) \cdot (m\ mod\ n)\ mod\ n \end{aligned} \end{equation}$
由欧拉定理 $m^{\phi(n)} \equiv 1(mod\ n)$ 得
$\begin{equation} \begin{aligned} &((m^{\phi(n)})^k\ mod\ n) \cdot (m\ mod\ n)\ mod\ n\\ &=(1^k\ mod\ n)\cdot (m\ mod\ n)\ mod\ n\\ &=m\ mod\ n\\ &=m \end{aligned} \end{equation}$

3. RSA公私钥的另一种关系

最近在阅读Java的第三方开源库BouncyCastle的生成RSA密钥方法时，发现其生成的公私钥关系是不满足 $e\cdot d\equiv 1(mod\ \phi(n))$ ，而是满足以下关系: $e\cdot d\equiv 1(mod\ lcm(p-1,q-1))$ ( $lcm$ 指两个数的最小公倍数)
部分相关源码如下：

            pSub1 = p.subtract(ONE);
            qSub1 = q.subtract(ONE);
            gcd = pSub1.gcd(qSub1);
            lcm = pSub1.divide(gcd).multiply(qSub1);

            //
            // calculate the private exponent
            //
            d = e.modInverse(lcm);

包版本：gradle: org.bouncycastle:bcprov-jdk15on:1.56
类路径：org.bouncycastle.crypto.generators.RSAKeyPairGenerator
方法名：generateKeyPair()

发现这样生成的公私钥也可以做加解密计算，而且私钥d明显比原生的短许多，在做解密计算或签名时，效率必然是更快的。

在查阅部分资料后（主要来自于陈景润同志的《初等数论》(Ⅰ)第四章习题7，有兴趣者可自行查阅），我整理如下证明过程。

首先需要费马小定理： $a^{p-1}\equiv 1(mod\ p)$ (p是素数)
其实费马小定理也是特殊的欧拉定理，因为当n是素数时， $\phi(n)=n-1$

已知的RSA需要两个大素数 $(p,q)$ ，对于数 $m$ ，有以下等式
$\begin{equation} \begin{aligned} m^{p-1} &\equiv 1 (mod\ p)\\ m^{q-1}&\equiv 1 (mod\ q) \end{aligned} \end{equation}$
此时假设数
$t=lcm(p-1,q-1)$ ，即 $t$ 是 $p-1,q-1$ 的最小公倍数，
有 $t=k_1\cdot (p-1)$ ，且 $t=k_2\cdot (q-1)$ 。那么有
$\begin{equation} \begin{aligned} m^t = m^{k_1\cdot (p-1)}&\equiv 1 (mod\ p)\\ m^t = m^{k_2\cdot (q-1)}&\equiv 1 (mod\ q) \end{aligned} \end{equation}$
上诉等式亦可写成以下等式
$\begin{equation} \begin{aligned} p &| m^t-1 \mbox{或者} m^t-1=k_3\cdot p\\ q &| m^t-1 \mbox{或者} m^t-1=k_4\cdot q\\ &k_3\mbox{与}k_4为任意\mbox{正整数} \end{aligned} \end{equation}$
那么有 $lcm(p,q)|m^t-1$
即 $m^t-1=k_5\cdot lcm(p,q)$ ;
$m^t=k_5\cdot lcm(p,q)+1$ ( $k_5$ 为任意正整数)
即得到 $m^t\equiv 1(mod\ lcm(p,q))$
由于 $p,q$ 都是素数，那么有 $lcm(p,q)=p\cdot q=n$
所以有
$\begin{equation} \begin{aligned} m^t&\equiv 1(mod\ n)\\ m^{lcm(p-1,q-1)}&\equiv 1(mod\ n) \end{aligned} \end{equation}$
所以RSA的公私钥只要满足 $e\cdot d \equiv 1(mod\ lcm(p-1,q-1))$ 即可。

4. 结合中国剩余定理的RSA计算方法

在使用openssl生成RSA密钥时，发现其私钥文件，除了公钥(e:publicExponent)，私钥(d:privateExponent)，模数(n:modulus)，模数的两个素因子(p:prime1,q:prime2)之外，还有三个参数，分别是exponent1,exponent2,coefficient.
在BouncyCastle中，也发现类似的类参数，在查阅RFC标准是，也发现相关方法RFC 2437

public class RSAPrivateCrtKeyParameters
    extends RSAKeyParameters
{
    private BigInteger  e;
    private BigInteger  p;
    private BigInteger  q;
    private BigInteger  dP;
    private BigInteger  dQ;
    private BigInteger  qInv;
}

包版本：gradle: org.bouncycastle:bcprov-jdk15on:1.56
类路径：org.bouncycastle.crypto.params.RSAPrivateCrtKeyParameters

在查阅部分资料后(主要来自博客http://jianiau.blogspot.com/2014/05/rsa-decrypt-with-crt.html)，发现用私钥结合中国剩余定理(CRT)来做计算(解密或签名)，效率会更高。
首先解释上诉参数的含义：

    private BigInteger  e;//公钥
    private BigInteger  p;//模数的素因子
    private BigInteger  q;//模数的素因子
    private BigInteger  dP;//d mod p-1
    private BigInteger  dQ;//d mod q-1
    private BigInteger  qInv;//q模p的乘法逆元,即qInv *q = 1 (mod p)

(1)计算过程（以解密计算为例）

有密文 $C$ ，得
$\begin{equation} \begin{aligned} m_1&=C^{d_p}\ mod\ p\\ m_2&=C^{d_q}\ mod\ q\\ m&=m_2+((m_1-m_2)\cdot q^{-1}\ mod\ p)\cdot q \end{aligned} \end{equation}$
第一次看的时候我直呼what's up.这么牛X.
在一顿搜索和演算之后，整理以下推导过程.

(2)推导过程

从用私钥计算的原始公式 $m=C^d\ mod\ n(n=p \cdot q)$ ,再由中国剩余定理(CRT)拆解得，计算一下等式：
$\begin{equation} \begin{aligned} m_1&=C^d mod\ p\\ m_2&=C^d mod\ q \end{aligned} \end{equation}$
由于 $d_p=d\ mod\ (p-1)$ 即 $d=k(p-1)+d_p$ (k为任意正整数)
那么 $C^d mod\ p=C^{k(p-1)+d_p}\ mod\ p$
由费马小定理 $a^{p-1}\equiv 1(mod\ p)$
得 $C^{k(p-1)+d_p}\ mod\ p=C^{d_p}mod\ p$
所以 $m_1,m_2$ 可写成
$\begin{equation} \begin{aligned} m_1&=C^d=C^{d_p} mod\ p\\ m_2&=C^d=C^{d_q} mod\ q\\ d_p&=d\ mod\ (p-1)\\ d_q&=d\ mod\ (q-1)\\ \end{aligned} \end{equation}$
将d拆解为 $d_p,d_q$ 去计算,明显数字的位数短许多，在做指数运算的时候，效率更高。
然后，现在的问题在于，如何用 $m_1,m_2$ 来计算明文结果 $m$ .
由于 $m_1,m_2$ 分别 $m$ 模 $p,q$ 的结果，
即
$\begin{equation} \begin{aligned} m&\equiv m_1\ mod\ p\\ m&\equiv m_2\ mod\ q\\ \end{aligned} \end{equation}$
要从 $m_1,m_2$ 来计算构造(凑出) $m$ ，
首先以第二条等式为前提假设 $m=m_2+k\cdot q$ ， $k$ 为任意整数
满足第一条等式：
$\begin{equation} \begin{aligned} m_2+k\cdot q&\equiv m_1\ (mod\ p)\\ k\cdot q&\equiv m_1-m_2\ (mod\ p)\\ k\cdot q \cdot q^{-1} &\equiv (m_1-m_2)\cdot q^{-1}(mod\ p)\\ k &\equiv (m_1-m_2)\cdot q^{-1}(mod\ p)\\ \end{aligned} \end{equation}$
经过一顿操作之后得到 $k=(m_1-m_2)\cdot q^{-1}\ mod\ p$ ， $q^{-1}$ 是q模p的乘法逆元。
所以明文得
$m=m_2+((m_1-m_2)\cdot q^{-1}\ mod\ p)\cdot q$
整理完毕，明天照常搬砖。