关于RSA的学习整理

一、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$
整理完毕，明天照常搬砖。

参考文档

[1] 《初等数论》(Ⅰ) 第四章习题7，陈景润著。
[2] Java第三方开源库BouncyCastle
[3] 开源程序openssl
[4] RFC 2437
[5] http://jianiau.blogspot.com/2014/05/rsa-decrypt-with-crt.html
[6] 2018年数论课鄙记
[7] 2019计算机安全学鄙记

最后编辑于：2022.03.22 00:06:04

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,544评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,430评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,764评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,193评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,216评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,182评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,063评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,917评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,329评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,543评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,722评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,425评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,019评论 3赞 326
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,671评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,825评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,729评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,614评论 2赞 353