非对称密码-RSA

  • 密钥配送问题
  • RSA密码(Tivest-Shamir-Adleman)
  • RSA手算
  • RSA密码的破解
  • CTF的RSA题怎么解

1.  密钥配送问题:

通信时,若使用对称密码,通信发送方必须将密钥发送给接收方,不然发送方将加密的数据发过去后,接收方无法给通信数据解密。但是这个密钥又不能发送,因为密钥存在泄漏的风险。

如果发送密钥的时候,给密钥上一层加密再发送呢?那发送者也得同时发送这一层用于加密密钥的解密密钥,这样接受者才能通过这个解密密钥 解密得到数据的解密密钥,但是这个解密密钥的密钥也存在泄漏的风险。(套娃了属于是

总结就是:为了正常通信,发送者必须发送密钥,但因为有泄漏风险所以又不能发送。(发了但没完全发?啊笑死

对于上述密钥配送问题怎么解决?有下面这几种想法。

(1)通过事先共享密钥来解决

1对1通信时,如果两个人就在互相身边,那就直接告诉对方密钥完事,很简单,也不会泄露。(除非被三体的智子监视

1对1通信时,如果两个人网恋是网友,玩儿蛋,还是得发送密钥,还是存在泄漏风险。

就算不考虑泄漏风险问题,N对N通信时,则需要n×(n-1)的密钥数,我要和100个网友通信,就得保存99个密钥,这不现实。

(2)通过密钥分配中心来解决

c为密钥分配中心,c保存了a和b的各自的密钥。

当a向b通信时使用临时密钥来对通话数据进行加密,该临时密钥通过C生成。C生成临时密钥后将该临时密钥发送给a和b,但是发送临时密钥给a和b时会有临时密钥泄露的风险,所以在C在发送临时密钥给a的时候会使用a的密钥来对临时密钥进行加密,从而保证只有a能获取到临时密钥,C在发送临时密钥给B时同理。当通信结束时,临时密钥就被销毁。

缺点:万一密钥分配中心寄了,整个通信系统就寄了,鸡蛋放到一个篮子里了属于是,不是很保险。

(3)通过Diffie-Hellman密钥交换来解决

这个要另开一篇讲

(4)公钥密码

公钥密码可以解决密钥配送问题。

但是有两个不足:

  • 公钥认证问题(中间人攻击)
  • 公钥密码处理速度只有对密码的百分之一

2.RSA密码(Tivest-Shamir-Adleman)

2.1 RSA密码概述

先看RSA怎么加密和解密的。

RSA加密公式:

$$
\text { 密文 }=\text { 明文 }{ }^{E} \bmod N
$$
公式1

RSA解密公式:

$$
\text { 明文 }=\text { 密文 }{ }^{D} \bmod N
$$
公式2

就很简单,对于想使用RSA密码的人来说,只要用到E、N、D这三个数就可以进行RSA的加密和解密了。其中:

  • E(Encryption)和N(Number)就是加密的密钥,即E和N的组合就是公钥。
  • D(Decryption)和N(Number)就是解密的密钥,即D和N的组合就是私钥。

A只要将公钥(E,N)发送给B,C,D,E,……,那么B,C,D,E,……这些人想给A发信息的时候,就可以通过公钥(E,N)按照公式1来对通信的数据进行加密,就算通信过程中公钥(E,N)被泄露,坏人只知道公钥(E,N)的情况下也不能对加密的通信数据进行解密,因为解密需要公示2中的数字D。当A接收到来自B,C,D,E,……的通信数据后,A就可以通过私钥(D,N)来进行解密了。

总结就是:公钥可以随便给别人,别人想对你发送加密数据的时候就用公钥进行加密。私钥一定只能自己拿着,因为别人通过公钥加密的发给你的数据,只能被自己的私钥解密。

那么问题来了,E、N、D这三个数当然不能随便取,需要按照一定的方法来取才能正常的进行加密解密。

2.1 如何获取密钥对(E,N,D)

获取用于RSA密码的密钥对(E,N,D)简单可划分为如下步骤:

  1. 求N
  2. 求L(生成密钥对的过程中的中间产物)
  3. 求E
  4. 求D

一个步骤一个步骤的来讲。

(1) 求N

取两个质数p和q(随机数数然后判断是不是质数),这两个质数要很大,否则很容易被破解。(为什么呢,不到啊,证明太长了我也就扫了一眼..)

求N的公式如下:

$$
N= p \times q
$$
公式3

(2) 求L(生成密钥对的过程中的中间产物)

L只出现在生成密钥对的过程中。L是(p-1)和(q-1)的最小公倍数(least common multiple,lcm)。用lcm(X+Y)来表示“X和Y的最小公倍数”。

求L的公式:

$$
L=\operatorname{lcm}(p-1, q-1)
$$
公式4

(3) 求E

E必须比1大,比L小,另外E和L的最大公约数必须为1(互质)。

用公式表达的话,如下:

$$
\begin{gathered}
1<E<L \\
\operatorname{gcd}(E, L)=1
\end{gathered}
$$

即在1<E<L范围中随机取数,使用辗转相除法判断是否gcd(E,L)=1,如果符合条件则得到可用的E。gcd(E,L)=1这个条件可以保证一定存在可以用于解密的D。

(4) 求D

通过E和L求得D,D满足条件如下:

$$
\begin{aligned}
&1<D<L \\
&E \times D \bmod L=1
\end{aligned}
$$

即在1<D<L范围中取数,取到的D与E的乘积与L取余,余数为1,那么这个D就得到了。

3.RSA手算

看的有点迷没关系,来手推一个RSA密钥对,然后进行一次加密和解密就懂了。

步骤和上一节是一样的。

(1) 求N

随便准备两个质数,比如p=17,q=19两个质数。

根据公式1算N:

$$
\begin{aligned}
N &=p \times q \\
&=17 \times 19 \\
&=323
\end{aligned}
$$

得到N = 323

(2) 求L

L是(p-1)和(q-1)的最小公倍数(least common multiple,lcm)。

$$
\begin{aligned}
L &=\operatorname{lcm}(p-1, q-1) \\
&=\operatorname{lcm}(16 \times 18) \\
&=144
\end{aligned}
$$

得到L=144

(3) 求E

$$
\begin{gathered}
1<E<L \\
\operatorname{gcd}(E, L)=1
\end{gathered}
$$

随便取一个满足上述条件的,比如取E=5。

(4) 求D
$$
\begin{aligned}
&1<D<L \\
&E \times D \bmod L=1
\end{aligned}
$$

随便选一个满足上述条件的数,取D=29。

至此获取RSA密钥对完成,密钥对如下:

  • 私钥为:(29,323)
  • 公钥为:(5,323)

其中公钥(5,323)是可以随便发给别人用的,是可以公开的;私钥(29,323)必须自己保管,不能泄露。

(5) 加密

测试一下加密解密效果,随便编一个故事背景。

贝拉根据自己的聪明才智,自己算了一个RSA的密钥对,即私钥(29,323)、公钥为(5,323)。贝拉将公钥(5,323)交给乃琳,并告诉乃琳以后想办事,就用这个公钥进行RSA加密,然后再把密文发给自己,这样就算被其他成员看到也不知道是什么意思。

这一天,乃琳想告诉拉姐凌晨1点来5号小黑屋办事,那么乃琳根据公式1和贝拉的公钥(5,323)把要发送的“15”进行加密。

$$
\begin{aligned}
\text { 密文 } &=\text { 明文 }^{E} \bmod N \\
&=15^{5} \bmod 323 \\
&=2
\end{aligned}
$$

这样,乃琳得到密文“2”

(6) 解密

乃琳在某次团播的时候,大声对拉姐喊着“2!2!2!”,拉姐点点头表示“收到收到收到!”,其他成员还以为乃琳在夸拉姐大聪明呢~

于是贝拉收到了密文2,团播结束后回到房间开始根据公式2和私钥(29,323)进行解密工作:

$$
\begin{aligned}
\text { 明文 } &=\text { 宓文 }^{D} \bmod N \\
&=2^{29} \bmod 323 \\
&=15
\end{aligned}
$$

聪明的贝拉花了24个小时很快的就解开了密文,发现乃琳想给自己传达的信息是“15”,意思就是“凌晨1点来5号小黑屋办事”。解开密文的贝拉非常高兴并感慨到“我真是太聪明了”,于是开开心心的出门了。

(收收味儿)

4.攻击RSA密码

“乃琳和贝拉这是怎么了?”。

嘉然最近觉得很奇怪,因为最近总是看到贝拉、乃琳大半夜偷偷摸摸的出门,还刚刚好错开一天。

嘉然觉得很不对劲。

半个月后的某天凌晨,在恼羞成怒的贝拉一把抱起被子中的乃琳夺门而出后,嘉然意识到她的机会来了,她行动了。

腿长1米8的嘉然一个健步就迈到了最上铺,摇了摇口水浸满床梯的大头,半天没有动静,于是嘉然又一个健步回到了自己的下铺。瞟了一眼仍在熟睡的珈乐,嘉然长舒一口气,然后又睡下了,她决定再等等。

又是半个月后的某天凌晨,窗外时不时传来几声狼嚎,在恼羞成怒的贝拉又一次抱起乃琳夺门而出后,嘉然意识到她的机会来了,她又行动了。

嘉然摇了摇身边躺在1米8大床上的大头,精疲力尽的向晚半天没有动静。“是我攻击性太强了吗”,嘉然过意不去的想到。

于是嘉然决定独自去寻找原因。

不知怎么的,嘉然突然就在火锅底部发现了一张纸条,上面写着:

我对你的爱就像是拖拉机下山,叮铃乓啷啪啦啪啦彭。
以后用(5,323)加密了再给我发消息,别人就不知道我们之间的关系了。
我真聪明!!

嘉然恍然大悟,这是RSA密码!!嘉然又恍然大悟,“拉姐,你把秘密都写纸上了!”。

聪明(真)的嘉然开始思考如何破译RSA密码。

4.1   通过密文,E,N求得明文(×):

根据解密公式:

$$
\text { 密文 }=\text { 明文 }{ }^{E} \bmod N
$$
公式1

如果没有mod N的话,那么根据已知密文和明文的情况下求得D很好求,只是一个求对数的问题。

但是mod N丢不得,不然就绝杀。丢不得的话,就变成了求离散对数的问题,现在还没有高效的算法算这个。

4.2   暴力破解D(×):

暴力破解D。但是实际上N为2048bit以上,因此D的长度和N相近,暴力破解D不现实

4.3  通过质因数分解N来求得p和q

获取ESA密钥对的第一步就是获取两个质数q和p,然后通过p×q来得到N。

既然如此,在N不大的情况下可以使用质因数分解在对N进行攻击,虽然现在没有针对大整数的质因数分解的高效算法,但是大整数质因数分解的工作一直在进行着。2048bit的RSA能用到2031年(查资料看到的)

5.CTF中的RSA题目怎么解

例题:

一看题目,RSA,已知了N,公钥中的E和密文C。

直接对N进行质因数分解,如果能分解则可以通过公式计算出L,再利用L通过公式计算出私钥中的D,有了D就可以直接解密了。

解密公式:

$$
\text { 明文 }=\text { 密文 }^{D} \bmod N
$$

这里用到FactorDB,FactorDB存储了已经知道的整数的拆分。FactorDB官网:https://pypi.org/project/factordb-pycli/,里面有教程。安装命令:pip install factordb-pycli。

得到分解后的质因数为:

  • 782758164865345954251810941
  • 810971978554706690040814093
  • 1108609086364627583447802163

能分解出来就好办了,现在根据分解出来的质因数通过如下公式求得L。此处先不求最小公倍数,的意思是最小公倍数,那就直接三个数字减去1然后相乘。

$$
L=\operatorname{lcm}(p-1, q-1, r-1)
$$

得到L的值为:

703739435902178622788120834660633835967683693970968792399227984308068678503129760

现在已知了E和L,根据如下条件可进行逆模运算求得D的值。

$$
E \times D \bmod L=1
$$

得到D的值为: 362843528015826034116250472435616782986296050195278657613571087702035376387404519

得到D的值后,就可以通过如下解密公式来对密文c进行解密了

$$
\text { 明文 }=\text { 密文 }^{D} \bmod N
$$

输出解密后的十进制与十六进制数据,可以看到,根据经验数据开头的0x666c6167对应的ascii是“flag”,找到flag成功。

最后将数据转为ascii码即可。

最后的flag为:flag{1e257b39a25c6a7c4d66e197}

尾声

嘉然思考了1秒钟,又心算了1秒钟,很快就根据上述流程算出了解密密钥D为29。

解决了难度为24贝拉的问题后,嘉然心情舒畅,于是她又轻手轻脚地回到了自己房间。

站在床边的嘉然伸了伸懒腰,注视着被五花大绑但仍在熟睡的晚晚,脸上渐渐弥漫上了些许小恶魔的笑容。突然,嘉然一把掀开裹着晚晚的被子,说道“谁还没几个众所周知的秘密呢,你说是吧,晚晚~”。

这时,窗外又传来了几声狼嚎,仔细听狼嚎中还夹杂着些许虚弱的跑操声。

今晚,注定是个不眠之夜x5啊。

发表评论

您的电子邮箱地址不会被公开。