# sosig:Crypto:70ptsOh man, RSA is so cool. But I don't trust the professionals, I do things MY WAY. And I'll make my encryption EXTRA secure with an extra thicc e! You'll never crack [it](out.txt)!  
# Solution配布されたout.txtを見ると以下のようであった。  ```text:out.txtn: 14750066592102758338439084633102741562223591219203189630943672052966621000303456154519803347515025343887382895947775102026034724963378796748540962761394976640342952864739817208825060998189863895968377311649727387838842768794907298646858817890355227417112558852941256395099287929105321231423843497683829478037738006465714535962975416749856785131866597896785844920331956408044840947794833607105618537636218805733376160227327430999385381100775206216452873601027657796973537738599486407175485512639216962928342599015083119118427698674651617214613899357676204734972902992520821894997178904380464872430366181367264392613853e: 1565336867050084418175648255951787385210447426053509940604773714920538186626599544205650930290507488101084406133534952824870574206657001772499200054242869433576997083771681292767883558741035048709147361410374583497093789053796608379349251534173712598809610768827399960892633213891294284028207199214376738821461246246104062752066758753923394299202917181866781416802075330591787701014530384229203479804290513752235720665571406786263275104965317187989010499908261009845580404540057576978451123220079829779640248363439352875353251089877469182322877181082071530177910308044934497618710160920546552403519187122388217521799c: 13067887214770834859882729083096183414253591114054566867778732927981528109240197732278980637604409077279483576044261261729124748363294247239690562657430782584224122004420301931314936928578830644763492538873493641682521021685732927424356100927290745782276353158739656810783035098550906086848009045459212837777421406519491289258493280923664889713969077391608901130021239064013366080972266795084345524051559582852664261180284051680377362774381414766499086654799238570091955607718664190238379695293781279636807925927079984771290764386461437633167913864077783899895902667170959671987557815445816604741675326291681074212227```RSAでeが大きい場合、Wiener's attackが知られている。  以下のwa.pyで実行する。  ```python:wa.py# -*- coding: utf-8 -*-# https://yocchin.hatenablog.com/entry/2017/03/05/192000よりfrom fractions import Fraction
def continued_fractions(n,e):    cf = [0]    while e != 0:        cf.append(int(n/e))        N = n        n = e        e = N%e    return cf
def calcKD(cf):    kd = list()    for i in range(1,len(cf)+1):        tmp = Fraction(0)        for j in cf[1:i][::-1]:            tmp = 1/(tmp+j)        kd.append((tmp.numerator,tmp.denominator))    return kd
def int_sqrt(n):    def f(prev):        while True:            m = (prev + n/prev)/2            if m >= prev:                return prev            prev = m    return f(n)
def calcPQ(a,b):    if a*a < 4*b or a < 0:        return None    c = int_sqrt(a*a-4*b)    p = (a + c) /2    q = (a - c) /2    if p + q == a and p * q == b:        return (p,q)    else:        return None
def wiener(n,e):    kd = calcKD(continued_fractions(n,e))    for (k,d) in kd:        if k == 0:            continue        if (e*d-1) % k != 0:            continue        phin = (e*d-1) / k        if phin >= n:            continue        ans = calcPQ(n-phin+1,n)        if ans is None:            continue        return (ans[0],ans[1])
n = 14750066592102758338439084633102741562223591219203189630943672052966621000303456154519803347515025343887382895947775102026034724963378796748540962761394976640342952864739817208825060998189863895968377311649727387838842768794907298646858817890355227417112558852941256395099287929105321231423843497683829478037738006465714535962975416749856785131866597896785844920331956408044840947794833607105618537636218805733376160227327430999385381100775206216452873601027657796973537738599486407175485512639216962928342599015083119118427698674651617214613899357676204734972902992520821894997178904380464872430366181367264392613853e = 1565336867050084418175648255951787385210447426053509940604773714920538186626599544205650930290507488101084406133534952824870574206657001772499200054242869433576997083771681292767883558741035048709147361410374583497093789053796608379349251534173712598809610768827399960892633213891294284028207199214376738821461246246104062752066758753923394299202917181866781416802075330591787701014530384229203479804290513752235720665571406786263275104965317187989010499908261009845580404540057576978451123220079829779640248363439352875353251089877469182322877181082071530177910308044934497618710160920546552403519187122388217521799
(p,q) = wiener(n,e)
print 'p = ', str(p)print 'q = ', str(q)```実行すると素数が得られた。  ```bash$ python2 wa.pyp =  128492410950654872001754818372751471227090063855833681574938088880503157691538748201946630518213794418274696316199318770451524663771258425569832321955651721320572306775923895573430031233522425368323141762665857788148189517919670087870657927204463889670604784945106039367955599815202555170174030185574626093699q =  114793289992568105259243952247810662219227283817412230700343905680426540175503049211790228524234722231480483290184285517008546908588534934976456806645370618468232506120632142533312406493650231725291499768631732343302501728812874256317928494857305947135683846349816655828497281995629123361154466482144256790047```これを使い、以下のrsadec.pyで復号する。  ```python:rsadec.py# -*- coding: utf-8 -*-# http://ctf.publog.jp/archives/1074444084.htmlよりdef exgcd(m, n):    if n>0:        y,x,d = exgcd(n, m%n)        return x, y-m/n*x, d    else:        return 1, 0, m
n = 14750066592102758338439084633102741562223591219203189630943672052966621000303456154519803347515025343887382895947775102026034724963378796748540962761394976640342952864739817208825060998189863895968377311649727387838842768794907298646858817890355227417112558852941256395099287929105321231423843497683829478037738006465714535962975416749856785131866597896785844920331956408044840947794833607105618537636218805733376160227327430999385381100775206216452873601027657796973537738599486407175485512639216962928342599015083119118427698674651617214613899357676204734972902992520821894997178904380464872430366181367264392613853e = 1565336867050084418175648255951787385210447426053509940604773714920538186626599544205650930290507488101084406133534952824870574206657001772499200054242869433576997083771681292767883558741035048709147361410374583497093789053796608379349251534173712598809610768827399960892633213891294284028207199214376738821461246246104062752066758753923394299202917181866781416802075330591787701014530384229203479804290513752235720665571406786263275104965317187989010499908261009845580404540057576978451123220079829779640248363439352875353251089877469182322877181082071530177910308044934497618710160920546552403519187122388217521799c = 13067887214770834859882729083096183414253591114054566867778732927981528109240197732278980637604409077279483576044261261729124748363294247239690562657430782584224122004420301931314936928578830644763492538873493641682521021685732927424356100927290745782276353158739656810783035098550906086848009045459212837777421406519491289258493280923664889713969077391608901130021239064013366080972266795084345524051559582852664261180284051680377362774381414766499086654799238570091955607718664190238379695293781279636807925927079984771290764386461437633167913864077783899895902667170959671987557815445816604741675326291681074212227
p =  128492410950654872001754818372751471227090063855833681574938088880503157691538748201946630518213794418274696316199318770451524663771258425569832321955651721320572306775923895573430031233522425368323141762665857788148189517919670087870657927204463889670604784945106039367955599815202555170174030185574626093699q =  114793289992568105259243952247810662219227283817412230700343905680426540175503049211790228524234722231480483290184285517008546908588534934976456806645370618468232506120632142533312406493650231725291499768631732343302501728812874256317928494857305947135683846349816655828497281995629123361154466482144256790047d = exgcd(e, (p-1)*(q-1))[0] % ((p-1)*(q-1))s = pow(c, d, n)h = format(s, 'x')f = ''for i in range(0, len(h), 2):    f += chr(int(h[i:i+2], 16))print(f)```実行する。  ```bash$ python2 rsadec.pyactf{d0ggy!!!111!1}```flagが得られた。  
## actf{d0ggy!!!111!1}