0%

RSA算法解析

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$为私密的,需要注意保密。

实例举例

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

细节分析

e的选取问题

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

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

RSA算法可靠性分析

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

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

  1. $ed \equiv 1 \pmod {φ(n)}$。即只有知道$e$和$φ(n)$,才能算出$d$。其中$e$已知
  2. $φ(n)=(p-1)(q-1)$。只有知道$p$和$q$,才能算出$φ(n)$
  3. $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想通过传统方法破解遥遥无期。

加密解密的正确性证明

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

已知:

  1. $M \equiv m^e \pmod n$
  2. $ed \equiv 1 \pmod { φ(n)}$
  3. $n=p*q, \quad φ(n)=(p-1)*(q-1)$
  4. $e\in (1,φ(n)),\quad e与φ(n)互质$
  5. $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))$

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

  1. 欧拉函数是一个积性函数。
    积性函数:若函数$f$是一个积性函数,且$a$与$b$互质,则$f(ab)=f(a)f(b)$
  2. 若$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)$ 个,表示为

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

均与$n$互质。

先证明两个推论:

  1. 若$i\not ={j}$ ,则$m_i$与$m_j$对$n$取模不同余。
  2. $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了

扩展欧几里得的代码实现

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

1
2
3
4
5
6
7
8
9
10
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;
}