Sma11_Tim3's Studio.

RSA

Crypto
字数统计: 1.6k阅读时长: 6 min
2018/10/28 Share

打了蛮多场CTF，每次密码学都有逃不过的RSA，是时候来总结一波了，就决定是你啦RSA。

简介RSA

RSA加密算法是一种非对称加密算法。

RSA算法涉及三个参数，n，e，d，私钥为n，d，公钥为n，e。

其中n是两个大素数p，q的乘积。

d是e模 φ(n) 的逆元， φ(n) 是n的欧拉函数。

c为密文，m为明文，则加密过程如下：

m^e ≡ c (mod N)

解密过程如下：

c^d ≡ m (mod N)

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

RSA在CTF中的类型

在CTF中，RSA在Crypto中居多，RSA作为典型的公钥加密算法，几乎在每次的CTF中都会有个一两道。当然偶尔也会在RE或者MISC中冒冒泡。

模数分解

要解决RSA的问题，最简单也是最暴力的方法就是分解n，只要能分解n，就能够得到n的欧拉函数值：

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

e、d与n的欧拉函数满足如下的关系：

e*d≡1(mod n)

即在知道e,p,q的情况下，可以解出d：

1
2
3
4
5
6
7
8
9
10
11
12
def egcd(a, b):
	if a == 0:
 		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
   		return (g, x - (b // a) * y, y)
def modinv(a, m):
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

modinv函数是求模函数，在知道e,p,q的情况下可以求得d:

1
d=modinv(e,(p-1)*(q-1))

在得到d之后不能够直接用Python中m**e%n来计算。在数值稍微大一点的情况下基本是无法算出结果的，这里我们使用一波Python中的pow()函数。使用方法如下：

1
m=pow(c,d,n)

eg:

1
2
3
4
5
p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
d = modinv(e, (p-1)*(q-1))
print d

直接给出p,q,e的情况下可直接求解d。

例题链接https://www.jarvisoj.com (very easy RSA))(进去后要先注册才能下载题目哦)

暴力直接分解n

正常情况下当n很大的时候，凭借我们的计算机是不太可能直接分解n的。但是网上有一些在线分解的网站，这些网站并不是真正的在线分解n，而是储存了一些已经成功分解的n来供我们查询。比如：http://factordb.com

通过在此类网站上查询n，如果可以分解或者之前分解成功过，那么可以直接得到p和q。然后利用前述方法求解得到密文。

判断n大小
此类问题一般是分值较小的题目，提取出n之后可以发现n的长度小于等于512bit，可以直接取分解n。如果大于512bit，建议在使用每个题目都用后面所说的方法去解题。

eg:

1
n=87924348264132406875276140514499937145050893665602592992418171647042491658461

直接利用factordb分解

利用公约数分解

如果在两次公钥的加密过程中使用的n1和n2具有相同的素因子，那么可以利用欧几里得算法直接将n1和n2分解。

通过欧几里得算法可以直接求出n1和n2的最大公约数p：

p=gcd(n1,n2)

可以得到：

n1=pq1
n2=pq2
这样就能直接分解两个不同的n值了。 欧几里得算法的时间复杂度为O(log n)。这个时间复杂度即便是4096 bit也是秒破级别。 
1
2
3
4
5
6
7
8
def gcd(a, b):
    if a < b:
     	a, b = b, a
    while b != 0:
     	temp = a % b
     	a = b
    	b = temp
    return a
此类处理方法一般是题目给了若干个n，均不相同，并且都是2048bit，4096bit级别，无法正面硬杠，并且明文都没什么联系，e也一般取65537。 eg: 在一个题目中，你拿到了两个n，e都为65537，两个n分别为： 
1
2
n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
直接分解n显然是不可能的，经过尝试发现： 
1
print gcd(n1,n2)
得到下面的结果 
1
1564859779720039565508870182569324208117555667917997801104862601098933699462849007879184203051278194180664616470669559575370868384820368930104560074538872199213236203822337186927275879139590248731148622362880471439310489228147093224418374555428793546002109
故得到了两个n的公因子p，进一步求出两个n的q，剩下的就是之前的活了。 # 如何分解n # **Fermat方法与Pollard rho方法** 介绍： 针对大整数的分解有很多种算法，性能上各有优异，有Fermat方法，Pollard rho方法，试除法，以及椭圆曲线法，连分数法，二次筛选法，数域分析法等等。其中一些方法应用在RSA的攻击上也有奇效。 在p，q的取值差异过大，或者p，q的取值过于相近的时候，Format方法与Pollard rho方法都可以很快将n分解成功。 此类分解方法有一个开源项目yafu将其自动化实现了，不论n的大小，只要p和q存在相差过大或者过近时，都可以通过yafu很快地分解成功。 在不能在线分解和不能利用公约数分解之后都可以用yafu试一试。 eg: [https://www.jarvisoj.com (Medium RSA)](https://www.jarvisoj.com (Medium RSA)) 进入yafu之后输入factor(n)即可。 ![](https://i.imgur.com/FJF3ykD.png) 两个p39就是我们要得p,q。 # 低加密指数攻击 # **简介：** 当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。 即：
m^e mod n

如果e=3，且m^e<n，那么：

c = m^e , e=3
$$m=\sqrt[3]{c}$$

如果明文的三次方比n大，但是不是足够大，那么设k，有：

c= m^e+kn

爆破k，如果 c-kn 能开三次根式，那么可以直接得到明文。

推荐在e=3的时候首先尝试这种方法。

eg:https://www.jarvisoj.com (Extremely hard RSA))

关键代码如下：此题通过不断给明文+n开三次方即可求得：

1
2
3
4
5
6
i=0
while 1:
	if(gmpy.root(c+i*N, 3)[1]==1):
		print gmpy.root(c+i*N, 3)
		break
	i=i+1

低解密指数攻击

与低加密指数相同，低解密指数可以加快解密的过程，但是者也带来了安全问题。那么一种基于连分数(一个数论当中的问题)的特殊攻击类型就可以危害RSA的安全。此时需要满足：

q

如果满足上述条件，通过Wiener Attack可以在多项式时间中分解n。

rsa-wiener-attack的攻击源码开源在了github中，采取python编写，可以很容易使用。

当e非常大时，首先尝试这种攻击方法。

万能的GitHub上当然是有源码的啦！
https://github.com/pablocelayes/rsa-wiener-attack

在RSAwienerHacker.py文件中插入一下代码就OK啦！(e和n根据题目自行修改)（SUCFT2018之it may contain ‘flag’）

1
2
3
4
5
6
7
def test_hack_RSA1():
	print("-------------------------") 
	e=160222447153262895889250928158012827757109871196102040037421857250766491575699886894325697077956068896677359953037375582060511979328323570880578946073240834317364119936983046746942944368567355131867682895196198904859001202051459879133425754080440276218324680838480108302184726980362910704693149535052743526713 		
	n=356096033429997161372356441930246707554046995590506452306084931488519008238592151695866774341246347160182054216879883209187019942641996111166252052256475412435016177136773967956292472785118669272929844214105480922945372638910276569650465033695573697459823872295312452877368652943145314840314022954151337366463
	hacked_d = hack_RSA(e, n)
	print("hacked_d = ", hacked_d)
	print("-------------------------")

得到d之后按照之前介绍的方法来求解

1
2
3
4
5
6
n=0x1fb18fb44f4449f45ea938306c47b91f64b6c176bd24dbb35aa876f73859c90f0e1677d07430a1188176bc0b901ca7b01f6a99a7df3aec3dd41c3d80f0d17292e43940295b2aa0e8e5823ffcf9f5f448a289f2d3cb27366f907ee62d1aaeba490e892dc69dacbafa941ab7be809e1f882054e26add5892b1fcf4e9f1c443d93bf
c=0xd19d63015bdcb0b61824237b5c67cb2ef09af0c6cd30e193ff9683357b1e45ab4df607b8c1e0b96cafc49a84d7e655c3ce0f71b1d217eec9ca6cdfa57dd3dc92533b79431aa8a7d6ca67ac9cdd65b178a5a96ab7ce7bf88440f4a9b9d10151b0c942a42fdab9ea2c2f0c3706e9777c91dcc9bbdee4b0fb7f5d3001719c1dd3d3
d=0xb28a1
m=pow(c,d,n)
print m
print hex(m)

平时做题目得到的明文都是一个16进制串，安利一个在线转换网站https://tool.lu/hexstr/(上面的转换工具还比较齐全，足以应付大多数情况了，实在碰到没有的就自己脚本啦！)

这里注意一个细节问题，如果在运行脚本的时候报错，请在脚本前加上：

1
2
import   sys
sys.setrecursionlimit(10000000)

共模攻击

如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密，那么就可以在不分解n的情况下还原出明文m的值。

即：

c1≡m^e1(mod n)
c2≡m^e2(mod n)

此时不需要分解n，不需要求解私钥，如果两个加密指数互素，就可以通过共模攻击在两个密文和公钥被嗅探到的情况下还原出明文m的值。

过程如下，首先两个加密指数互质：

gcd(e1,e2)=1

即存在s1,s2使得：

s1e1+s2e2=1

又因为：

c1≡m^e1(mod n)
c2≡m^e2(mod n)

通过代入化简可以得出:

(c1^s1)(c2^s2)≡m(mod n)

直接得到明文。

当若干次加密，每次n都一样，明文根据题意也一样时，即可采用这种攻击方法。

eg:https://www.jarvisoj.com (very hard RSA))

总结

好不容易写完啦！这里总结了一些CTF中比较常见的RSA套路，以后会根据做题的情况继续补充的。

本文内容参考来源：https://www.anquanke.com/post/id/84632

若转载本文请注明出处。

by Covteam-Sma11_Tim3

生活不易，多才多艺。

原文作者：Sma11_Tim3

原文链接：http://yoursite.com/2018/10/28/RSA/

发表日期：October 28th 2018, 12:25:10 pm

更新日期：December 1st 2020, 8:44:08 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 简介RSA
  2. 2. RSA在CTF中的类型
  3. 3. 模数分解
  4. 4. 暴力直接分解n
  5. 5. 利用公约数分解
  6. 6. 低解密指数攻击
  7. 7. 共模攻击
  8. 8. 总结
Total : 41
2021
2020
2019
2018
Covteam Algorithm Reverse Blockchain Daily gadgets MATLAB Pwn Crypto CTF