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)$ 个,表示为
设$a$与$n$互质,记 $m_i= a * x_i $,有
均与$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了
扩展欧几里得的代码实现
扩展欧几里得的代码比较简单,展示如下:
1 | void exgcd(ll a, ll b, ll &x, ll &y) |