CTF之RSA加密算法

原创 时间 2017-10-27  追风小组-muhe 神月资讯

1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。

0x01   摘要

每次碰到RSA题都是一脸蒙逼,这次专门来撸一撸RSA加密算法。

0x02   前言

CTF里考RSA算法是比较常见的。可惜每次碰到都一脸蒙逼,最心酸的是Writeup就摆在那里,不离不弃,而我的智商摆在那里,不高不低。

0x03   理解RSA

最重要一步,当然是理解RSA算法,理解了,就什么都不难了。

微信图片_20171102160341.jpg

1977年,三位数学家RivestShamir  Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。

这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。

举例子的时候一般出现的人物都是BobAlice

比如有两个用户AliceBobAlice想把一段明文通过双钥加密的技术发送给BobBob有一对公钥和私钥,那么加密解密的过程如下:

  1. Bob将他的公开密钥传送给Alice

  2. AliceBob的公开密钥加密她的消息,然后传送给Bob

  3. Bob用他的私人密钥解密Alice的消息。

上面的过程可以用下图表示,Bob先生成公钥和私钥,Alice使用Bob的公钥进行加密,Bob用自己的私钥进行解密。

微信图片_20171102160507.jpg

总结:

公钥和私钥是成对的,它们互相解密。

公钥加密,私钥解密。

私钥数字签名,公钥验证。

0x03.1.2  数学概念

要看算法了,还是先温习一下基本的概念吧,哈哈,忘的人可以看看,大神可以跳过。

0x03.1.2.1       互质关系

如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,1532没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。

关于互质关系,不难得到以下结论:

1.任意两个质数构成互质关系,比如1361

2.一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如310

3.如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如9757

4.1和任意一个自然数是都是互质关系,比如199

5.p是大于1的整数,则pp-1构成互质关系,比如5756

6.p是大于1的奇数,则pp-2构成互质关系,比如1715

0x03.1.2.2       欧拉函数

欧拉函数求的是什么呢?

即:任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在18之中,有多少个数与8构成互质关系?)

其中,在18之中,与8形成互质关系的是1357,所以 φ(n) = 4

常用的运算过程有:

  •  

φ(n)= φ(p×q)=φ(p)φ(q)=(p-1)(q-1)

  •  

欧拉公式:

微信图片_20171102160520.jpg



例子:

微信图片_20171102160524.jpg


1323的欧拉函数就是756


0x03.1.2.3       欧拉定理

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

微信图片_20171102160529.jpg

也就是说,aφ(n)次方被n除的余数为1。或者说,aφ(n)次方减去1,可以被n整除。

比如,37互质,而7的欧拉函数φ(7)等于6,所以36次方(729)减去1,可以被7整除(728/7=104)。

0x03.1.2.4       费马小定理

假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成:

微信图片_20171102160533.jpg



0x03.1.2.5       模反元素

如果两个正整数an互质,那么一定可以找到整数b,使得 ab-1 n整除,或者说abn除的余数是1

微信图片_20171102160537.jpg

这时,b就叫做a"模反元素"

而我们的RSA中,eb就互为模反元素。

0x03.1.3  算法

RSA算法涉及三个参数,ned,私钥为(nd),公钥为(ne)。

其中n是两个大素数pq的乘积。

de的模反元素,φ(n)n的欧拉函数。

c为密文,m为明文,则加密过程如下:

微信图片_20171102160542.jpg

解密过程如下:

微信图片_20171102160546.jpg

ne是公开的情况下,想要知道d的值,必须要将n分解计算出n的欧拉函数值,而n是两个大素数pq的乘积,将其分解是困难的。

上面的内容可以用一个图表示:

微信图片_20171102160558.jpg


0x03.1.4  举例

看一遍运算过程,知道怎么用是最快的学习方法哈哈。假设用户A需要将明文“key”通过RSA加密后传递给用户B

0x03.1.4.1       设计公私钥(ne),(nd

1)pqn

p=3q=11,得出n=p×q=3×11=33;(质数pq越大越难破解,n转成二进制后的长度就是密钥长度)

2)φ(n)

φ(n)=(p-1)(q-1)=2×10=20

3ed

选一个1到φ(n)之间的质数,这里取e=3,(320互质)则e×d1 (modφ(n)),即3×d1(mod 20)。令x=d20的倍数为-y,则3x-20y=1。求解得:x=7y=1

因此,当d=7时,e×d1 modφ(n)同余等式成立。从而我们可以设计出一对公私密钥,加密密钥(公钥)为:KU=(n,e)=(33,3),解密密钥(私钥)为:KR=(n,d)=(33,7)

0x03.1.4.2       英文数字化

将明文信息数字化,并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值,即:

微信图片_20171102160604.jpg


则得到分组后的key的明文信息为:110525

0x03.1.4.3       明文加密

用户加密密钥(33,3) 将数字化明文分组信息加密成密文。由CMe(mod n)得:

微信图片_20171102160611.jpg

  因此,得到相应的密文信息为:113116

0x03.1.4.4       密文解密

用户B收到密文,若将其解密,只需要计算,即:

微信图片_20171102160615.jpg

用户B得到明文信息为:110525。根据上面的编码表将其转换为英文,我们又得到了恢复后的原文“key”。

0x04   问题与思考

0x04.1      问题1:已经公钥(ne),如何破解私钥(nd)?

  • e*d1 (mod φ(n))。只有知道e和φ(n),才能算出d

  • φ(n)=(p-1)(q-1)。只有知道pq,才能算出φ(n)

  • n=pq。只有将n因数分解,才能算出pq

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

0x04.2      问题2:为什么n越大,就越难破解?

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

人类已经分解的最大整数(232个十进制位,768个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。

0x04.3      问题3:为什么用n加密的明文长度要小于n,如果长度大于n如何加密?

根据互质关系第三条,如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如9757

所以只要m<n,因为n为质数,mn互质。

如果m>n,则将m分解成位数小于n的分组进行加密,解密后再组合起来。

0x05   CTF

下面列举了个CTF题,做着做着就会啦。目前只列举一道,当然还有其它很多攻击方法,像维纳攻击、广播攻击等等,就不班门弄斧了,进一步了解和学习可以看参考文章哈哈。

0x05.1      RSA Roll

例题来自【https://www.52pojie.cn/forum.php?mod=viewthread&tid=490769

题目:

微信图片_20171102160632.jpg


解答:

从上面可以看出,给出的是(ne=92013971319)和分组的密文。而这里的n明显不大,因此是可以破解的。

在线因数分解:【http://factordb.com/index.php?query=920139713】得到p=18443q=49891

欧拉函数:φ(n) = (p-1)(q-1)=(49891-1)*(18443-1)=920071380

由此e=19, φ(n)= 920071380e*d=1(modφ(n))920071380x + 19y = 1

求解d

微信图片_20171102160640.jpg


d=96849619,即(nd=92013971396849619),可以解那些密文了。

用【BigInt】求解:

微信图片_20171102160645.jpg


如密文【704796792


可以知道102ascii码对应的是f,因此明文为f。其它的可以依次求解出来。

0x06   参考

RSA算法原理:

https://www.kancloud.cn/kancloud/rsa_algorithm/48484

欧拉函数:

https://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0

CTFRSA的常见攻击方法:

http://bobao.360.cn/learning/detail/3058.html

CTFCrypto练习之RSA算法:

http://blog.csdn.net/qq_18661257/article/details/54563017

因数分解:

http://factordb.com/

用实例给新手讲解RSA加密算法:

http://bank.hexun.com/2009-06-24/118958531.html

底部画条图片.jpg


下一篇>>