记第一次打酱油CTF的一道RSA题（😂）

上周末参加了集团组织的第一届CTF，因为对RSA算法感兴趣，研究了下，但是直到今天才在同事的帮助下解出来~不过还是非常开心的。拿到flag的那一刻，真是兴奋！！！哈哈哈😄

1.RSA算法了解链接：阮一峰前辈介绍，值得拥有

RSA算法原理(一),
RSA算法原理(二)

2.CTF题目：

image.png 点击Download，下载的文件是 image.png

其中，encrypted里的数据：

14761226233619930913789444725092447007613560598267346585342315453772027264412167927977755707329661392276505024453621240583362624447351938222371314669018972810255713416361723565228156367311359232833988723297469009681586000128401084727085783675600327001956247797488990161285491545910756889281566068792425724492472261816080144975111092812011003235523336908625210763606938142957083944176073970599497683544430874740263720939640031645375948163111883171958810033385293575085726496009401227983165821316892351815472499136007182227653441941290055629867880246323810810538976514884239316177241582108067917829554426524658993662096

然后weird_rsa.py里的代码：

#!/usr/bin/env python3

import binascii

e = 65537
n = 26221250500210405881132117557481723828766403943957950577451874805030106596081117375156772427206128405044267565826746522083073344532158814742511219204087934469113726393167485385378981630858737362324790588554286527642921364757519448451820127769942271309179542598449740660811048250973469013409521371791098074887056492924891157941526458248272889917641905464741404650030958545690892412495947165576458308474382558997629624440993069542093798549029729504677699266868041518498869029774178904303543559872895807099482683032802362220977267523960685985521766229201489330046455426324265875811125282379015211742752299449996253304837

def encrypt(m):
    mi = int(binascii.hexlify(m), 16)
    return pow(mi, d, n)

if __name__ == '__main__':
    import sys
    if len(sys.argv) <= 1:
        print('usage: %s <plain text message>' % sys.argv[0])
        sys.exit()
    print(encrypt(sys.argv[1].encode('ascii')))

3. 分析：

• 1. 拿到的encrypted是c，然后代码里有e, n。那么现在只需要知道d就能解出来。
     其中，c是经过m^e === c(mod n)(简书不支持Latex!)得出的加密文。
• 2. 然后我们已经拿到了n, 和e, 和c, 要得到原始数据m,需要得到d，那么该怎么算才能得到d?

当时做的时候，觉得首先是分解N嘛，分解出来p,q，然后就能知道d了，通过公式计算，但是用网上的工具分解不出来啊，那么n太大了感觉。~~~所以一直没有思路

• 3. ！！！其实，需要注意的是，题目是weird_rsa，也就是说，这个rsa算法很有可能在哪一步是不符合真正的rsa算法要求的！！！
     脑洞来了，猜想N：这个数可能根本不是两个大质数p,q相乘的积，而是一个大质数。那么N的欧拉函数是什么？是N-1啊！
• 4. 由上，得到N的欧拉函数φ(n)，此刻，根据公式 image.png 算出d.

• 5. 然后，根据公式 image.png 用pow(c, d, n)算出(c^d%n)的值m：

>>> pow(c, d, n)
38321129010645758619476701506985896445313197885910909L

• 6. 上面的数据是long int型的m,然后转换成16进制的m.

>>> hex(38321129010645758619476701506985896445313197885910909)
'0x666c61677b6169766f687365654c6f6f4c3273686f7dL'

• 7. 然后利用在线工具，将16进制数据转换为ascii码字符：终于得到了flag，啊啊啊！！！

     
     image.png
     

     好高兴！！！

PS: 查ascii表知，所有的ascii字符都可以用两位16进制数表示，而一共需要126个10进制数来表示，所以从数字转字符，最好由16进制数转ascii，这样，计算机通过2位2位一分割，才会得到正确的ASCII字符串。

2017-11-06 晚 申城