RSA算法原理解析

计算机安全作业要求，围绕RSA做了一些原理解析。

RSA的算法流程非常简单，而主要针对背后的相关数学和算法原理做了一些阐述。对大部分涉及到的数学定理及公式，涉及算法做了证明。

待填坑：

欧拉函数是一个积性函数的证明
裴蜀定理的证明

RSA算法基本介绍

RSA加密算法是一种非对称加密算法，被广泛用于安全数据传输，数字签名等。
RSA是计算机通信安全的基石，保证了加密数据不会被破解。
对RSA破解需要对一个大整数做质因数分解，由于分解缺少有效手段，RSA的安全性得到相当程度的保障。

算法流程

选取两个质数 $ p \quad q $
记 $ n = p*q $，并求出n的欧拉函数值:$φ(n)$。欧拉函数参考下文相关部分。此处$φ(n)=(p-1)*(q-1)$
在区间$(1，φ(n))$中选取一个与 $φ(n)$ 互质的数$e$， $n$和$e$组成为我们所选取的公钥
求出模 $φ(n)$ 意义下 $e $的乘法逆元 $d$ ，记$d=e^{-1} \pmod {φ(n)}$， $n$和$d$为我们所选取的私钥。三者有性质 $ed\equiv1 \pmod {φ(n)}$，乘法逆元参考下文相关部分
对于一个消息$m$ ($m < n$)，加密算法为 $m^e \% n$
对于一个加密过的消息$M$，解密算法为 $M^d \% n$
可验证$M$解密后与原消息$m$相等

其中$n$和$e$为公开的，即任何有需要的人都可以从第三方受信机构获取。
而$d$为私密的，需要注意保密。

实例举例

$p,q$选取为$7, 17$
$n=7*17=119$， $φ(n)=(7-1)*(17-1)=96$
在$(1,96)$中选取与$96$互质的数$e=5$
求出$5$模$96$意义下的乘法逆元$77$, $(5*77)\%96=385\%96=1$
对于消息$19$（小于$119$),$19^5\%119=66$
对于加密后的消息$66$，$66^{77}\%119=19$

细节分析

e的选取问题

在$e$的选取要求中为 $e\in(1,φ(n))$且要求$e$与$φ(n)$互质。

其中小于$φ(n)$的原因是方便选取，因为在模$n$意义下，两个同余的数是等价的,如$1$与$n+1$在计算中等价。
同余参考下文相关内容
$e$与$φ(n)$互质的原因是模$φ(n)$意义下$e$的乘法逆元不一定存在，即$d$不一定存在。
由裴蜀定理可得一推论：模$n$意义下,$a$的乘法逆元存在的充要条件为$a$与$n$互质。
裴蜀定理相关内容参考下文相关内容

RSA算法可靠性分析

RSA算法的可靠性取决于有无可能在已知$n$和$e$的情况下求出$d$

我们在整个算法流程中出现的数有 $p, q, n, φ(n), e, d, m, M$。

$ed \equiv 1 \pmod {φ(n)}$。即只有知道$e$和$φ(n)$，才能算出$d$。其中$e$已知
$φ(n)=(p-1)(q-1)$。只有知道$p$和$q$，才能算出$φ(n)$
$n=pq$。只有将$n$因数分解，才能算出$p$和$q$

ps:
欧拉函数公式：$φ(n) = n * \prod (\frac{1}{p} *(p-1))$ ,
欧拉函数性质：若$p$为质数，则$φ(p)=p-1$;若$p$与$q$互质，则$φ(pq)=φ(p)φ(q)$
其中$p$为$n$的所有质因数 ,我们所使用的$n=p*q$,所以 $φ(n)=(p-1)(q-1)$

欧拉函数公式的证明参考下文相关部分。

结论：如果$n$可以被因数分解,就可以算出$d$，即被破解。

n的大小的选取

RSA的可靠性取决于对于$n$进行因数分解的难度。即对大整数做因数分解越困难，RSA算法越可靠。但大整数的因数分解，是一件非常困难的事情。目前除了暴力破解还没有发现别的有效方法。(量子计算机相关实现前)

参考wiki，目前已经公布的最大破解的一组RSA长度为768位(2进制)（参考RSA加密算法-维基百科）破解时间2009年。其10进制如下：

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

=
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
×
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

所以从目前来看1024位级别的RSA加密受到了一定程度的挑战，而2048位级别的RSA想通过传统方法破解遥遥无期。

加密解密的正确性证明

这里将证明用私钥解密加密消息一定可以正确地得到原消息。

已知：

$M \equiv m^e \pmod n$
$ed \equiv 1 \pmod { φ(n)}$
$n=p*q, \quad φ(n)=(p-1)*(q-1)$
$e\in (1,φ(n)),\quad e与φ(n)互质$
$m < n$

求证：$M^d \equiv m \pmod n$

由（1）式得

$M = m^e + k_1n$

带入求证式，即求证

${(m^e + k_1n)}^d \equiv m \pmod n$

即求证

${(m^e)}^d \equiv m \pmod n$

由(2)式,有

$ed = k_2φ(n)+1 $

即求证

$m^{k_2φ(n)+1} \equiv m \pmod n$

当m与n互质时

由欧拉定理得，　$m^{φ(n)}≡ 1 \pmod n$,有

$m^{k_2φ(n)+1} = m * m^{k_2φ(n)} = m*1^{k_2} = m \pmod n$

则证得。

当m与n不互质时

因为$n$只有两个质因子$p$和$q$，则m必为p的倍数或q的倍数。即$m=kp$ 或者 $m =kq$。
假设$m=kp$，则$k$与$q$必互质。

ps:
1). 若$k$是$q$的倍数,则$m$为$n$的倍数，与$m$小于$n$矛盾
2). 又$q$为质数，若$k$不为$q$的倍数，则$k$与$q$必互质

由$k$与$q$互质，$p$与$q$互质，根据欧拉定理得：

$(kp)^{φ(q)} \equiv 1 \pmod q$

又$q$为质数，有$φ(q)=q-1$

$(kp)^{q-1} \equiv 1 \pmod q$

又右式为1，则左式取任意次幂结果不变,取$k_2(p-1)$次幂有：

$((kp)^{q-1})^{k_2(p-1)} \equiv 1 \pmod q$

左右式同乘以$kp$有:

$(kp)^{k_2(q-1)(p-1)} * kp\equiv kp \pmod q$

带入$φ(n)=(p-1)*(q-1)$有：

$(kp)^{k_2φ(n)+1} \equiv kp \pmod q$

带入$k_2φ(n)+1 = ed$有：

$ (kp)^{ed} \equiv kp \pmod q$

化解如下有:

$(kp)^{ed} \equiv kp + k_3q$

满足该等式的情况下，且$k$与$q$互质。则$k_3$ 必为$p$的倍数
设$k_3 = k_4p$有：

$(kp)^{ed} \equiv kp + k_4pq$

带入 $kp=m, pq=n$有:

$m^{ed} =m + k_4n $

左右对n进行取模有：

$m^{ed-1} = m \pmod n$

则证得。

所需的数学和算法知识

同余和模意义下的乘法逆元

同余:若$a\%n = b\%n$,则称 $a$与$b$在模$n$意义下同余，记为 $a\equiv b \pmod n$

乘法逆元:若$a*b\equiv 1 \pmod n$, 则称b为a模n意义下的乘法逆元。记为 $b=a^{-1} \pmod n$

乘法逆元的求法

当模数$n$为质数时，根据欧拉定理/费马小定理可以快速求乘法逆元。

定理如下：
费马小定理:如果$p$是一个质数，而整数$a$不是$p$的倍数，则有$a^{(p-1）}\equiv 1 \pmod p$
欧拉定理：若$n,a$为正整数，且$n,a$互质，则: $a^{φ(n)}\equiv 1 \pmod n$
费马小定理是欧拉定理的特殊情况。
欧拉定理的证明可参考下文欧拉定理的证明

当n不为质数时，根据扩展欧几里得算法求乘法逆元。

在RSA中，$φ(n)$一定不为质数，故使用此办法来求。具体内容参考扩展欧几里得算法下文相关部分。

欧拉函数和欧拉定理

欧拉函数：对于正整数$n$，记欧拉函数为$φ(n)$表示的是小于等于$n$并且与$n$互质的数的个数。
有$φ(n)=1$; $φ(p)=p-1(p为质数)$。
欧拉函数公式: $φ(n) = n * \prod (\frac{1}{p} *(p-1))$

欧拉定理：若$n,a$为正整数，且$n,a$互质，则: $a^{φ(n)}\equiv 1 \pmod n0$

欧拉函数公式的证明

求证：$φ(n) = n * \prod (\frac{1}{p} *(p-1))$

欧拉函数公式的证明需要一个前置知识与一个推论：

欧拉函数是一个积性函数。
积性函数:若函数$f$是一个积性函数,且$a$与$b$互质，则$f(ab)=f(a)f(b)$
若$n= p ^ k$ ($p$为质数), 有$φ(n)=p^k -p^{k-1}$

欧拉函数是一个积性函数的证明这里没有给出。
推论的证明如下：

若$n= p ^ k$ (p为质数), 即$n$的质因数只含有$p$。那么在区间$[1,n]$中，
与$n$不互质的数必为$p$的倍数：$p,2p,3p…,(p^{k-1}-1)*p,p^{k-1}*p$。
最后一个数就是$n$自己。则明显与$n$不互质的数有$p^{k-1}$个。
则有$φ(n)=p^k -p^{k-1}$。

公式证明：
将$n$表示为质因数指数之积的形式,其中$p_i$表示$n$的第$i$个质因数，$a_i$表示该质因数的指数：

$n= \prod p_i^{a_i}$

由欧拉函数是个积性函数,且 $p_i^{a_i}$ 必与 $p_j^{a_j}$互质($i\not ={j}$时)有

$ φ(n)=\prod {φ(p_i^{a_i})} $

根据推论有

$φ(p_i^{a_i}) =p_i ^{a_i} - p_i ^{a_i-1} $

则

$ φ(n)=\prod {(p_i ^{a_i} - p_i ^{a_i-1})} $
$ \quad\quad=\prod {((p-1) * p_i ^{a_i-1})} $
$\quad\quad=n * \prod (\frac{1}{p} *(p-1)) $

欧拉定理的证明

求证：
若$n,a$为正整数，且$n,a$互质，则: $a^{φ(n)}\equiv 1 \pmod n$

由欧拉函数，在$[1,n]$中与$n$互质的数有$ \varphi (n)$ 个,表示为

$x_1, x_2 \dots x_{φ(n)}$

设$a$与$n$互质,记 $m_i= a * x_i $,有

$m_1, m_2\dots m_{φ(n)}$

均与$n$互质。

先证明两个推论：

若$i\not ={j}$ ,则$m_i$与$m_j$对$n$取模不同余。
$m_i$模$n$的余数与$n$互质

推论1证明如下：

假设$i\not ={j}$ ,存在$m_i$与$m_j$对$n$取模同余。
即 $m_i-m_j\equiv 0 \pmod n$
则 $a*(x_i-x_j)\equiv 0 \pmod n$
有 $a*(x_i-x_j)\equiv kn$
又a与n互质，则$(x_i-x_j)$必为$n$的倍数
有$x_i-x_j\equiv 0 \pmod n$
并不可能，故证得推论1。

推论2证明如下：

$m_i$与$n$互质,则根据欧几里得辗转相除法有 $gcd(m_i,n)=gcd(n,m_i\%n)=1$
则证得推论2。

由两个推论,$m_i\% n$不同余且与n互质（$m_i\%n < n)$。则$m_i \% n$组成的集合与$x_i$组成的集合必完全相同。

在模$n$意义下：
则 $\prod m_i \% n \equiv\prod m_i \pmod n$
有 $\prod m_i \equiv\prod x_i \pmod n$
有 $a^{φ(n)} \prod x_i \equiv \prod x_i \pmod n$
有 $a^{φ(n)} \equiv 1 \pmod n$
则证得。

裴蜀定理及其推论

裴蜀定理又称贝祖定理。其内容为:若$a,b$是整数,有$gcd(a,b)=d$，那么对于任意的整数$x,y$,有$ax+by$都一定是$d$的倍数，特别地，一定存在整数$x,y$，使$ax+by=d$成立。

推论：当$d=1$时，即$a$与$b$互质，则有一定存在$ax+by=1$，则有$ax \equiv 1 \pmod b$。

则可有推论：当a与b互质时,a模b意义下的乘法逆元一定存在，这就是$e$选取与$φ(n)$互质的原因

扩展欧几里得算法

欧几里得算法是用来求最大公因数的算法，即辗转相除法。
即$gcd(a,b) = {}gcd(b,a\%b)$

扩展欧几里得算法在其基础上做了一定扩展，用途是求$ax+by=gcd(a,b)$的解。
很明显当$a$与$b$互质时，即$gcd(a,b)=1$时,有$ax= 1-by$，有$ax \equiv 1 \pmod b$。

欧几里得算法的证明

若$a$与$b$互质，$gcd(a,b)=gcd(b,a\%b)=1$。
由裴蜀定理，可得存在$x_0,y_0,x_1,y_1$使以下等式成立。

$ax_0+by_0=bx_1+(a\%b)y_1=1$

带入$a\%b=a-\lfloor a/b \rfloor*b$ 得到

$ax_0+by_0 = bx_1 + (a-\lfloor a/b \rfloor*b)y_1$
$ax_0+by_0=bx_1 + ay_1 – \lfloor a/b \rfloor by_1$
$ax_0+by_0= ay_1 + b(x_1 – \lfloor a/b \rfloor y_1)$

则可得到$x_0,y_0,x_1,y_1$的关系

$y_0=x_1-\lfloor a/b \rfloor*y_1$
$x_0=y_1$

辗转相除法进行到底部时即当$b=0，a=gcd(a,b)$时，明显有$a1+b0=gcd(a,b)，x=1,y=0$。此时的a，b不是我们最初的a，b了

扩展欧几里得的代码实现

扩展欧几里得的代码比较简单，展示如下：

void exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}