RSA算法(四):RSA数学原理

原创 小赛艇  2018-06-02 21:23  阅读 759 次

4 RSA数学原理

4.1 RSA算法步骤

4.1.1 密钥生成

(1) 取两个(较大的)质数p和q,越大密钥越安全。

例 为便于演示,我们取小的质数p=31,q=47。

(2) 计算它们的乘积n=pq,则\(\varphi (n)=n(1-\frac{1}{p})(1-\frac{1}{q})=(p-1)(q-1)\)

例 n=pq=1457,\(\varphi (n)=(p-1)(q-1)=30×46=1380\)

(3) 取e<\(\varphi (n)\),且e与\(\varphi (n)\)互质,即\( (e,\varphi (n))=1\)。

通常,公开的密钥e取65537,16进制数为10001。

例 这里因为\(\varphi (n)=1380\)不到65537,取e=347。

(4) 取d使得\(de\equiv 1 \pmod {\varphi (n)}\)。

即求[e]的逆元[d],之前已经介绍过求法,即取k使\(d=\frac{k\varphi (n)+1}{e}\)为整数。

例 由上式,当k=217时,d=863。

这样,就得到了两组数(n,d)和(n,e)。公开的为(n,e),保密的为(n,d)。

例 此时公钥为(1457,347),私钥为(1457,863)

4.1.2 加密过程

(1) 需要加密的明文满足i小于n,且(i,n)=1。

例 设要加密的明文i=123。

(2) 求\(I=i^e \bmod n\),即得到密文I。

例 求得\(123^{347} \bmod 1457=898\),即密文I=898。

4.1.3 解密过程

(1) 求\(h=I^d \bmod n\),即得到明文h。

例 求得\(898^{863} \bmod 1457=123\),即明文h=123,可见与加密前的i=123相同。

4.2 可行性证明

我们要确保经过加密、解密后的明文保持不变,即解密后的h与i相等。

证明:\(h=I^d \bmod n=i\)
因为 \(I\equiv i^e \pmod n\)
所以 \(I^d\equiv (i^e)^d\equiv i^{de} \pmod n\)
又 \(de\equiv 1 \pmod {\varphi (n)}\)
由同余等价形式得 \(de=k\varphi (n)+1 (k为整数)\)
所以 \(I^d\equiv i^{de}\equiv i^{k\varphi (n)+1} \pmod n\)
根据欧拉定理,\(i^{\varphi (n)}\equiv 1 \pmod n\)
所以\(i^{k\varphi (n)}\equiv 1^k\equiv 1 \pmod n\)
所以\(i^{k\varphi (n)+1}\equiv i \pmod n\)
即\(h\equiv I^d\equiv i \pmod n\)
又因为h,i均小于n
所以h=i

所以,经过加密、解密过程,看似经过了复杂的运算,但最终原文不变。

4.3 破解方法

我们想要破解别人利用RSA算法加密的信息,即从公钥(n,e)和加密后的信息I中得出原文i,需要得出私钥d。

想要知道d,就需要解\(de\equiv 1 \pmod {\varphi (n)}\),就需要知道\(\varphi (n)\),而\(\varphi (n)=(p-1)(q-1)\),则需要对n进行质因数分解,分解成n=pq。

正是因为分解质因数是很难的,需要不断寻找x使n mod x=0,所以RSA的保密性很高,通常n取1024bit(即\(2^{1024}\))及以上的整数,非常难破解。

但是,根据数学原理,有时候也会有很容易破解的情况,比如如果两次加密使用了1个相同的质数p,通过辗转相除法计算两个n的最大公因数即可得p,就可以分解两个n,从而破解;比如如果用于加密的e取得过小,如e=3,导致\(i^e \leq n\),直接对密文I开三次方即可获得原文i。

本文地址:https://xsaiting.com/rsa-4.html
版权声明:本文为原创文章,版权归 小赛艇 所有,转载请保留出处!
喜欢请点赞/打赏/分享这篇文章哦!

发表评论


表情