RSA算法原理——(3)RSA加解密过程及公式论证

时间:2021-08-03 12:24:16

上期(RSA简介及基础数论知识)为大家介绍了:互质欧拉函数欧拉定理模反元素 这四个数论的知识点,而这四个知识点是理解RSA加密算法的基石,忘了的同学可以快速的回顾一遍。

一、目前常见加密算法简介

二、RSA算法介绍及数论知识介绍

三、RSA加解密过程及公式论证

三、RSA加解密过程及公式论证

今天的内容主要分为三个部分:

  • rsa密钥生成过程: 讲解如何生成公钥和私钥
  • rsa加解密演示: 演示加密解密的过程
  • rsa公式论证:解密公式的证明

1、rsa密钥生成过程

大家都知道rsa加密算法是一种非对称加密算法,也就意味着加密和解密是使用不同的密钥,而这不同的密钥是如何生成的呢?下面我们来模拟下小红是如何生成公钥和私钥的。

RSA算法原理——(3)RSA加解密过程及公式论证

六步生成密钥:

(1)随机选择两个不相等的质数p和q

小红随机选择选择了6153。(实际应用中,这两个质数越大,就越难破解)

(2)计算p和q的乘积n

n = 61×53 = 3233

n的长度就是密钥长度,3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。

(3)计算n的欧拉函数φ(n)

这里利用我们上篇讲到的欧拉函数求解的第四种情况:

如果n可以分解成两个互质的整数之积,即:n = p1 × p2,则φ(n) = φ(p1p2) = φ(p1)φ(p2),所以φ(3233) = φ(61x53) = φ(61)φ(53)

又因为61和53都是质数,所以可以根据欧拉函数求解的第二种情况:

如果n是质数,则 φ(n)=n-1,所以φ(3233) = φ(61x53) = φ(61)φ(53)=60x52=3120

所以 φ(n)=3120

(4)随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质

小红就在1到3120之间,随机选择了17。(实际应用中,常常选择65537)

(5)计算e对于φ(n)的模反元素d

让我们来回顾一下什么是模反元素:

所谓“模反元素”就是指有一个整数d,可以使得ed除以φ(n)的余数为1,公式表示:

ed≡1(modφ(n))ed ≡ 1 (mod φ(n))ed≡1(modφ(n))

这个公式等价于

ed–kφ(n)=1ed – kφ(n) = 1ed–kφ(n)=1

将e=17、φ(n)=3120代入得:

17d–3120k=117d – 3120k = 117d–3120k=1

设x=d、y=-k,得

17x+3120y=117x+3120y=117x+3120y=1

所以我们要求的模反元素d就是对上面的二元一次方程求解

根据扩展欧几里得算法(辗转相除法)求解:

RSA算法原理——(3)RSA加解密过程及公式论证

上图我们使用扩展欧几里得求得x=-367,所以d=x=-367,但通常我们习惯取正整数,这样方便计算,还记得我们上节讲过的模反元素的特性吗:

3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…},即如果b是a的模反元素,则 b+kn 都是a的模反元素。

所以我们取d=d+kφ(n)=-367+1x3120=2753,到这里所有的计算已经全部完毕!

(6)将n和e封装成公钥,n和d封装成私钥

让我们来回顾一下我们一共出现的6个数字:

  1. p=61; 随机数与q互质
  2. q=53;随机数与p互质
  3. n=pq=6153=3233
  4. φ(n)=φ(p*q)=φ(61x53) = φ(61)φ(53)=60x52=3120
  5. e=17; 随机数,条件是1< e < φ(n),且e与φ(n) 互质
  6. d=2753; e对于φ(n)的模反元素d

在这个例子中n=3233,e=17,d=2753,所以公钥就是 (n,e)=(3233,17),私钥就是**(n,d)=(3233, 2753)**,这样小红就将公钥公布出去,自己保存好私钥就可以啦!

至此我们公钥、私钥就生成完毕,是不是觉得并不是很难呢?是不是有点怀疑私钥会不会被人破解呢?下面我们来看看如何才能暴力破解私钥。

(7)rsa算法可靠性

回顾我们一共生成了六个数字:p q n φ(n) e d,这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。

那么,有无可能在已知n和e的情况下,推导出d?

  1. ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d
  2. φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)
  3. n=pq。只有将n因数分解,才能算出p和q

结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。

看到这里有同学可能会惊呼:原来破解RSA算法的方法这个简单???

可是,大整数的因数分解,是一件非常困难的事情。也许你可以对3233进行因数分解(61×53),但是你没办法对下面的大整数分解:

123018668453011775513049495838496272077285356959533479219732245215172640050726

365751874520219978646938995647494277406384592519255732630345373154826850791702

6122142913461670429214311602221240479274737794080665351419597459856902143413

它等于两个质素的乘积:

33478071698956898786044169

84821269081770479498371376

85689124313889828837938780

02287614711652531743087737

814467999489

×

36746043666799590428244633

79962795263227915816434308

76426760322838157396665112

79233373417143396810270092

798736308917

这也是目前*记录的人类分解的最大整数(232个十进制位,768个二进制位),除了暴力破解,还没有发现别的有效方法。所以限制人类分解大整数的是计算机的计算能力,相信如果有一天真正的量子计算机问世后,又会引发一轮安全加密竞赛!

  • 1999年,RSA-155 (512 bits)被成功分解,花了五个月时间(约8000 MIPS年)和224 CPU hours在一台有3.2G*内存的Cray C916计算机上完成。
  • 2009年12月12日,编号为RSA-768(768 bits, 232 digits)数也被成功分解[10]。这一事件威胁了现通行的1024-bit密钥的安全性,普遍认为用户应尽快升级到2048-bit或以上。

2、rsa加解密演示

小红有了公钥和私钥这样就可以进行加解密了,于是小红拉着小明一起来测试一下!

(1)加密要用公钥 (n,e)

假设小明先测试性的给小红发一个字母m=“A”,我们都知道在通信传输中只能传输0和1,所以我们先将“A”转ascii码为65,所以m=65,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。

所谓”加密”,就是使用下面的加密公式算出下式的密文c:

me≡c(modn)m^e ≡ c (mod n)me≡c(modn)

小明得到的公钥是(n,e)=(3233, 17),m=65,那么得到下面的等式:

6517≡c(mod3233) 65^{17} ≡ c (mod 3233) 6517≡c(mod3233)

小明通过计算器一算c=2790,所以他就把2790发给小红了。

(2)解密要用私钥(n,d)

小红拿到小明发过来的密文c=2790,就用下面的公式进行解密出明文m:

cd≡m(modn) c^d ≡ m (mod n) cd≡m(modn)

而小红的私钥为:(n,d) = (3233,2753),所以得到下面的等式:

27902753≡m(mod3233) 2790^{2753} ≡ m (mod 3233) 27902753≡m(mod3233)

小红通过计算器一算,得m=65,然后小红对照着ascii码表得出65对应得字母为A。

至此,整个加解密过程就演示完了,我们来总结一下:

  1. 小明获取到小红的公钥(n,e)=(3233,17)
  2. 小明选取发送的消息m=A=65,注意m要小于n,如果消息大于n,则可以分段加密!
  3. 小明通过加密公式:m^e ≡ c (mod n) 算出密文c=2790
  4. 小红获取到小明的密文c=2790
  5. 小红使用解密公式:c^d ≡ m (mod n) 算法明文m=65=A

我们可以看到,其实RSA加密算法最核心的就是用公式来加解密,那么我们会有个疑问?为什么解密公式一定可以得到明文m呢?也就是说这个公式是怎么推导出来的?公式一定成立吗?

感兴趣的同学我们可以来一起证明一下解密公式,这也是整个RSA加密算法的最后最核心的一个知识点了。这里我会一步一步的推理,尽可能通俗易懂;

3、rsa公式论证

首先让我们再来回顾一下我们一共出现的8个数字

  1. p: 随机数与q互质
  2. q:随机数与p互质
  3. n=p*q
  4. φ(n)=φ(p*q)=φ§*φ(q)=(p-1)(q-1)
  5. e: 随机数,条件是1< e < φ(n),且e与φ(n) 互质
  6. d:e对于φ(n)的模反元素d:ed≡1 (mod φ(n))
  7. m:小明发送的明文
  8. c:小明用公钥加密后的密文

验证rsa算法成立,主要就是验证解密公式成立:

解密公式:cd≡m(modn)解密公式: c^d ≡ m (mod n) 解密公式:cd≡m(modn)

根据加密公式:

加密公式:me≡c(modn)→c=me–kn加密公式:m^e ≡ c (mod n) → c = m^e – kn加密公式:me≡c(modn)→c=me–kn

将c代入要我们要证明的那个解密公式:

(me–kn)d≡m(modn) (m^e – kn)^d ≡ m (mod n) (me–kn)d≡m(modn)

上式等同于下面的公式,原因如下

med≡m(modn)m^{ed} ≡ m (mod n)med≡m(modn)

原因:我们都知道下面的二元一次方程分解,只有第一项不包含n,而所有包含n的项在对n 取余 的操作中都可以消掉。因此得出了上面那个结论

(2–2n)2=4−8n+4n2 (2 – 2n)^2 = 4-8n+4n^2 (2–2n)2=4−8n+4n2

又因为生成密钥的第五步中我们取e并求了他对φ(n)的模反元素d:

ed≡1(modφ(n))→ed=hφ(n)+1 ed ≡ 1 (mod φ(n)) → ed = hφ(n)+1ed≡1(modφ(n))→ed=hφ(n)+1

所以将ed代入上式得

mhφ(n)+1≡m(modn) m^{hφ(n)+1} ≡ m (mod n) mhφ(n)+1≡m(modn)

所以,我们只要证明这个公式成立,就证明解密公式的成立,也就证明了RSA算法的成立。

下面我们分两种情况来验证上面的例子

(1) m与n互质

根据欧拉定理:如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:

aφ(n)≡1(modn)a^{φ(n)} ≡ 1 (mod n)aφ(n)≡1(modn)

证明:因为m与n互质,得

mφ(n)≡1(modn)→mφ(n)=1+kn→(mφ(n))h=(1+kn)hm^{φ(n)} ≡ 1 (mod n) → m^{φ(n)} = 1 + kn → (m^{φ(n)})^h = (1 + kn)^hmφ(n)≡1(modn)→mφ(n)=1+kn→(mφ(n))h=(1+kn)h

而(1 + kn)^h对n取模为1,因为对(1 + kn)^h拆分只有第一项1不含有n,所以有

(mφ(n))h=(1+kn)h≡1(modn) (m^{φ(n)})^h = (1 + kn)^h ≡ 1 (mod n) (mφ(n))h=(1+kn)h≡1(modn)

同理

(mφ(n))h≡1(modn)→(mφ(n))h=1+kn→(mφ(n))h∗m=(1+kn)∗m (m^{φ(n)})^h ≡ 1 (mod n) → (m^{φ(n)})^h = 1 + kn → (m^{φ(n)})^h*m = (1 + kn)*m(mφ(n))h≡1(modn)→(mφ(n))h=1+kn→(mφ(n))h∗m=(1+kn)∗m

而 (1 + kn)*m对n取模为m,因为前面说过0 < m < n,所以有

(mφ(n))h∗m=(1+kn)∗m≡m(modn)→mhφ(n)+1≡m(modn) (m^{φ(n)})^h*m = (1 + kn)*m ≡ m (mod n) → m^{hφ(n)+1} ≡ m (mod n)(mφ(n))h∗m=(1+kn)∗m≡m(modn)→mhφ(n)+1≡m(modn)

当m与n互质时,证明原式成功!!!

(2) m与n不是互质关系

此时m与n不互质,所以m与n必定有除1以外的公因子,而又因为n等于质数p质数q的乘积,所以m必然等于kpkq

m = kp为例,考虑到这时m与质数q必然互质,则根据欧拉定理和欧拉函数(第二种:当q为质数,则φ(q)=q-1)使下面的式子成立:

(kp)φ(q)≡1(modq)→(kp)q−1≡1(modq)(kp)^{φ(q)} ≡ 1 (mod q) → (kp)^{q-1} ≡ 1 (mod q) (kp)φ(q)≡1(modq)→(kp)q−1≡1(modq)

同上(m与n互质中)证明原理可得:

[(kp)q−1]h(p−1)×kp≡kp(modq)→(kp)h(p−1)(q−1)+1≡kp(modq) [(kp)^{q-1}]^{h(p-1)} × kp ≡ kp (mod q) → (kp)^{h(p-1)(q-1)+1} ≡ kp (mod q) [(kp)q−1]h(p−1)×kp≡kp(modq)→(kp)h(p−1)(q−1)+1≡kp(modq)

又因为

ed≡1(modφ(n))→ed=hφ(n)+1→ed=h(p−1)(q−1)+1 ed≡1 (mod φ(n)) → ed = hφ(n) + 1 → ed = h(p-1)(q-1) + 1ed≡1(modφ(n))→ed=hφ(n)+1→ed=h(p−1)(q−1)+1

将ed代入上式

(kp)ed≡kp(modq)→(kp)ed=tq+kp(kp)^{ed} ≡ kp (mod q) → (kp)^{ed} = tq + kp(kp)ed≡kp(modq)→(kp)ed=tq+kp

上式中,等式左边(kp)^ed对p取模为0,右边kp对p取模也为0,所以tq一定能整除p,但q是与p互质的,所以t必然能整除p,设t=rp,得

(kp)ed=rpq+kp(kp)^{ed} = rpq + kp(kp)ed=rpq+kp

因为 m=kp,n=pq,所以

med=rn+m→med≡m(modn) m^{ed} = rn + m → m^{ed} ≡ m (mod n)med=rn+m→med≡m(modn)

又因为生成密钥的第五步中我们取e并求了他对φ(n)的模反元素d:

ed≡1(modφ(n))→ed=hφ(n)+1 ed ≡ 1 (mod φ(n)) → ed = hφ(n)+1ed≡1(modφ(n))→ed=hφ(n)+1

将ed代入上式得:

mhφ(n)+1≡m(modn) m^{hφ(n)+1} ≡ m (mod n)mhφ(n)+1≡m(modn)

当m与n不互质时,证明原式成功!!!

附手稿:

RSA算法原理——(3)RSA加解密过程及公式论证

RSA算法原理——(3)RSA加解密过程及公式论证

RSA算法原理——(3)RSA加解密过程及公式论证

RSA算法原理——(3)RSA加解密过程及公式论证

RSA算法原理——(3)RSA加解密过程及公式论证

感兴趣的同学可以扫描下方二维码关注我的微信公众号:裸睡的猪

RSA算法原理——(3)RSA加解密过程及公式论证