Rating:
# sosig:Crypto:70pts
Oh 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.txt
n: 14750066592102758338439084633102741562223591219203189630943672052966621000303456154519803347515025343887382895947775102026034724963378796748540962761394976640342952864739817208825060998189863895968377311649727387838842768794907298646858817890355227417112558852941256395099287929105321231423843497683829478037738006465714535962975416749856785131866597896785844920331956408044840947794833607105618537636218805733376160227327430999385381100775206216452873601027657796973537738599486407175485512639216962928342599015083119118427698674651617214613899357676204734972902992520821894997178904380464872430366181367264392613853
e: 1565336867050084418175648255951787385210447426053509940604773714920538186626599544205650930290507488101084406133534952824870574206657001772499200054242869433576997083771681292767883558741035048709147361410374583497093789053796608379349251534173712598809610768827399960892633213891294284028207199214376738821461246246104062752066758753923394299202917181866781416802075330591787701014530384229203479804290513752235720665571406786263275104965317187989010499908261009845580404540057576978451123220079829779640248363439352875353251089877469182322877181082071530177910308044934497618710160920546552403519187122388217521799
c: 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 = 14750066592102758338439084633102741562223591219203189630943672052966621000303456154519803347515025343887382895947775102026034724963378796748540962761394976640342952864739817208825060998189863895968377311649727387838842768794907298646858817890355227417112558852941256395099287929105321231423843497683829478037738006465714535962975416749856785131866597896785844920331956408044840947794833607105618537636218805733376160227327430999385381100775206216452873601027657796973537738599486407175485512639216962928342599015083119118427698674651617214613899357676204734972902992520821894997178904380464872430366181367264392613853
e = 1565336867050084418175648255951787385210447426053509940604773714920538186626599544205650930290507488101084406133534952824870574206657001772499200054242869433576997083771681292767883558741035048709147361410374583497093789053796608379349251534173712598809610768827399960892633213891294284028207199214376738821461246246104062752066758753923394299202917181866781416802075330591787701014530384229203479804290513752235720665571406786263275104965317187989010499908261009845580404540057576978451123220079829779640248363439352875353251089877469182322877181082071530177910308044934497618710160920546552403519187122388217521799
(p,q) = wiener(n,e)
print 'p = ', str(p)
print 'q = ', str(q)
```
実行すると素数が得られた。
```bash
$ python2 wa.py
p = 128492410950654872001754818372751471227090063855833681574938088880503157691538748201946630518213794418274696316199318770451524663771258425569832321955651721320572306775923895573430031233522425368323141762665857788148189517919670087870657927204463889670604784945106039367955599815202555170174030185574626093699
q = 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 = 14750066592102758338439084633102741562223591219203189630943672052966621000303456154519803347515025343887382895947775102026034724963378796748540962761394976640342952864739817208825060998189863895968377311649727387838842768794907298646858817890355227417112558852941256395099287929105321231423843497683829478037738006465714535962975416749856785131866597896785844920331956408044840947794833607105618537636218805733376160227327430999385381100775206216452873601027657796973537738599486407175485512639216962928342599015083119118427698674651617214613899357676204734972902992520821894997178904380464872430366181367264392613853
e = 1565336867050084418175648255951787385210447426053509940604773714920538186626599544205650930290507488101084406133534952824870574206657001772499200054242869433576997083771681292767883558741035048709147361410374583497093789053796608379349251534173712598809610768827399960892633213891294284028207199214376738821461246246104062752066758753923394299202917181866781416802075330591787701014530384229203479804290513752235720665571406786263275104965317187989010499908261009845580404540057576978451123220079829779640248363439352875353251089877469182322877181082071530177910308044934497618710160920546552403519187122388217521799
c = 13067887214770834859882729083096183414253591114054566867778732927981528109240197732278980637604409077279483576044261261729124748363294247239690562657430782584224122004420301931314936928578830644763492538873493641682521021685732927424356100927290745782276353158739656810783035098550906086848009045459212837777421406519491289258493280923664889713969077391608901130021239064013366080972266795084345524051559582852664261180284051680377362774381414766499086654799238570091955607718664190238379695293781279636807925927079984771290764386461437633167913864077783899895902667170959671987557815445816604741675326291681074212227
p = 128492410950654872001754818372751471227090063855833681574938088880503157691538748201946630518213794418274696316199318770451524663771258425569832321955651721320572306775923895573430031233522425368323141762665857788148189517919670087870657927204463889670604784945106039367955599815202555170174030185574626093699
q = 114793289992568105259243952247810662219227283817412230700343905680426540175503049211790228524234722231480483290184285517008546908588534934976456806645370618468232506120632142533312406493650231725291499768631732343302501728812874256317928494857305947135683846349816655828497281995629123361154466482144256790047
d = 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.py
actf{d0ggy!!!111!1}
```
flagが得られた。
## actf{d0ggy!!!111!1}
