e=0x3or3

##ctf.show

#easyrsa4

题目

e = 3
n = 18970053728616609366458286067731288749022264959158403758357985915393383117963693827568809925770679353765624810804904382278845526498981422346319417938434861558291366738542079165169736232558687821709937346503480756281489775859439254614472425017554051177725143068122185961552670646275229009531528678548251873421076691650827507829859299300272683223959267661288601619845954466365134077547699819734465321345758416957265682175864227273506250707311775797983409090702086309946790711995796789417222274776215167450093735639202974148778183667502150202265175471213833685988445568819612085268917780718945472573765365588163945754761
c = 150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661

1、一看到e=3（低加密指数攻击），马上想到了我曾经收藏的脚本。

【注：假设e=3, 公钥中的加密指数e很小，但是模数n很大

有RSA加密公式： C=M^e % n (C密文，M明文)

则：当M^e < n 时，

C = M^e ，所以对C开方就能得到M
当M^e ＞ n 时，此时用爆破的方法
假设我们　 Ｍ^e / n 的商为 k 余数为C，
则Ｍ^e = kn + C，对K进行爆破，只要k满足 kn + C能够开e次方就可以得明文】

2、上脚本

from gmpy2 import iroot
import libnum
e = 3
n = 18970053728616609366458286067731288749022264959158403758357985915393383117963693827568809925770679353765624810804904382278845526498981422346319417938434861558291366738542079165169736232558687821709937346503480756281489775859439254614472425017554051177725143068122185961552670646275229009531528678548251873421076691650827507829859299300272683223959267661288601619845954466365134077547699819734465321345758416957265682175864227273506250707311775797983409090702086309946790711995796789417222274776215167450093735639202974148778183667502150202265175471213833685988445568819612085268917780718945472573765365588163945754761
c = 150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661
k = 0
while 1:
    res = iroot(c+k*n,e)  
    if(res[1] == True):
        print(libnum.n2s(int(res[0]))) 
        break
    k=k+1

3、解得：flag{Sm4ll_eee}