この大会は2019/5/3 2:00(JST)～2019/5/6 1:30(JST)に開催されました。
今回もチームで参戦。結果は2841点で765チーム中7位でした。
自分で解けた問題をWriteupとして書いておきます。
Sanity (Misc 1)
問題にフラグが書いてあった。
INSA{Welcome}
Telegram (Misc 50)
Telegramのリンク先にアクセスすると、フラグが書かれている。
INSA{is_e2e_8annEd_1n_Russi4_too}
Dashlame - Part 1 (Reverse 50)
Easy Python Decompilerでpycをデコンパイルする。
from Crypto.Cipher import AES
import os
import random
import sys
import sqlite3
import time
import zlib
HEADER = " /.m.\\\n /.mnnm.\\ ___\n |.mmnvvnm.\\. .,,,/`mmm.\\\n |.mmnnvvnm.\\:;,. ..,,;;;/.mmnnnmm.\\\n \\ mmnnnvvnm.\\::;;, .,;;;;;;;;/.mmmnnvvnnm.|\n \\`mmnnnvvnm.\\::;::.sSSs sSSs ,;;;;;;;;;;/.mmmnnvvvnnmm'/\n \\`mmnnnvnm.\\:::::SSSS,,,,,,SSSS:::::::;;;/.mmmnnvvvnnmmm'/\n \\`mnvvnm.\\::%%%;;;;;;;;;;;%%%%:::::;/.mnnvvvvnnmmmmm'/\n \\`mmmm.%%;;;;;%%%%%%%%%%%%%%%::/.mnnvvvnnmmmmm'/ '\n \\`%%;;;;%%%%s&&&&&&&&&s%%%%mmmnnnmmmmmm'/ '\n | `%;;;%%%%s&&.%%%%%%.%&&%mmmmmmmmmm'/ '\n\\ | / %;;%%%%&&.%;` '%.&&%%%////// '\n \\ | / %%%%%%s&.%% x %.&&%%%%%//%\n \\ .:::::. ,;%%%%s&&&&.%; ;.&&%%%%%%%%/,\n-!!!- ::#:::::%%%%%%s&&&&&&&&&&&&&&&&&%%%%%%%%%%%\n / :##:::::&&&&&&&&&&&&&&&&&&&&&%%%%%%%%%%%%%%,\n / | `:#:::&&&&&&&&&&&&&&&&&&&&&&&&%%%%%%%%%%%%%\n | `&&&&&&&&&,&&&&&&&&&&&&SS%%%%%%%%%%%%%\n `~~~~~'~~ SSSSSSS%%%%%%%%%%%%%\n SSSSSSSS%%%%%%%%%%%%%%\n SSSSSSSSSS%%%%%%%%%%%%%.\n SSSSSSSSSSSS%%%%%%%%%%%%%%\n SSSSSSSSSSSSS%%%%%%%%%%%%%%%.\n SSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%\n SSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%.\n SSSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%%%\n SSSSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%%%%.\n\n WELCOME TO DASHLAME\n"
PEARSON_TABLE = [199,
229,
151,
178,
53,
6,
131,
42,
248,
110,
39,
28,
51,
216,
32,
14,
77,
34,
166,
213,
157,
150,
115,
197,
228,
221,
254,
172,
84,
27,
36,
156,
69,
96,
12,
220,
225,
137,
246,
141,
44,
208,
191,
109,
163,
21,
173,
250,
98,
227,
203,
162,
188,
3,
105,
171,
215,
15,
207,
218,
234,
56,
136,
235,
97,
79,
189,
102,
134,
11,
224,
117,
177,
222,
100,
129,
78,
18,
130,
187,
9,
184,
99,
108,
202,
13,
238,
17,
94,
70,
180,
144,
185,
168,
123,
71,
176,
91,
4,
153,
103,
242,
80,
127,
198,
82,
169,
148,
48,
120,
59,
55,
230,
209,
50,
73,
31,
49,
142,
149,
167,
249,
116,
1,
7,
86,
143,
101,
29,
52,
114,
154,
160,
128,
19,
170,
46,
214,
38,
67,
186,
252,
181,
145,
212,
183,
22,
231,
107,
43,
47,
122,
251,
217,
5,
62,
88,
244,
200,
93,
240,
219,
124,
58,
161,
89,
211,
158,
247,
60,
236,
65,
106,
113,
66,
81,
165,
194,
223,
40,
233,
126,
139,
72,
132,
61,
135,
57,
87,
182,
164,
35,
159,
118,
8,
83,
210,
243,
104,
76,
75,
119,
90,
138,
20,
206,
95,
16,
74,
33,
245,
237,
111,
64,
253,
125,
23,
232,
193,
37,
175,
92,
30,
241,
255,
133,
0,
140,
2,
155,
85,
10,
146,
179,
25,
26,
226,
201,
195,
121,
190,
63,
68,
152,
45,
147,
41,
204,
192,
205,
196,
54,
174,
239,
112,
24]
def pad(s):
mark = chr(16 - len(s) % 16)
while len(s) % 16 != 15:
s += chr(random.randint(0, 255))
return s + mark
def unpad(s):
return s[:-ord(s[-1])]
def get_random_passphrase():
sys.stdout.write('Getting random data from atmospheric noise and mouse movements')
sys.stdout.flush()
for i in range(10):
sys.stdout.write('.')
sys.stdout.flush()
time.sleep(random.randint(1, 20) / 10.0)
print ''
with open('wordlist.txt', 'rb') as fi:
passwords = fi.read().strip().split('\n')
return (random.choice(passwords), random.choice(passwords))
def get_pearson_hash(passphrase):
key, iv = ('', '')
for i in range(32):
h = (i + ord(passphrase[0])) % 256
for c in passphrase[1:]:
h = PEARSON_TABLE[h ^ ord(c)]
if i < 16:
key += chr(h)
else:
iv += chr(h)
return (key, iv)
def encrypt_stream(data, passphrase):
key, iv = get_pearson_hash(passphrase)
aes = AES.new(key, AES.MODE_CBC, iv)
data = pad(data)
return aes.encrypt(data)
def decrypt_stream(data, passphrase):
key, iv = get_pearson_hash(passphrase)
aes = AES.new(key, AES.MODE_CBC, iv)
data = unpad(aes.decrypt(data))
return data
def encrypt_archive(archive_filename, passphraseA, passphraseB):
with open(archive_filename, 'rb') as db_fd:
with open(archive_filename.replace('.db', '.dla'), 'wb') as dla_fd:
enc1 = encrypt_stream(db_fd.read(), passphraseA)
enc2 = encrypt_stream(enc1, passphraseB)
dla_fd.write(enc2)
os.unlink(archive_filename)
def decrypt_archive(archive_filename, passphraseA, passphraseB):
with open(archive_filename, 'rb') as dla_fd:
with open(archive_filename.replace('.dla', '.db'), 'wb') as db_fd:
dec1 = decrypt_stream(dla_fd.read(), passphraseB)
dec2 = decrypt_stream(dec1, passphraseA)
db_fd.write(dec2)
os.unlink(archive_filename)
def createArchive():
archive_name = raw_input('Please enter your archive name: ')
passphraseA, passphraseB = get_random_passphrase()
print 'This is your passphrase :', passphraseA, passphraseB
print 'Please remember it or you will lose all your passwords.'
archive_filename = archive_name + '.db'
with open(archive_filename, 'wb') as db_fd:
db_fd.write(zlib.decompress('x\x9c\x0b\x0e\xf4\xc9,IUH\xcb/\xcaM,Q0f`a`ddpPP````\x82b\x18`\x04b\x164>!\xc0\xc4\xa0\xfb\x8c\x9b\x17\xa4\x98y.\x03\x10\x8d\x82Q0\n\x88\x05\x89\x8c\xec\xe2\xf2\xf2\x8c\x8d\x82%\x89I9\xa9\x01\x89\xc5\xc5\xe5\xf9E)\xc5p\x06\x93s\x90\xabc\x88\xabB\x88\xa3\x93\x8f\xab\x02\\X\xa3<5\xa9\x18\x94\xabC\\#Bt\x14J\x8bS\x8b\xf2\x12sa\xdc\x02\xa820W\x13\x927\xcf0\x00\xd1(\x18\x05\xa3`\x08\x03#F\x16mYkh\xe6\x8fO\xadH\xcc-\xc8I\x85\xe5~O\xbf`\xc7\xea\x90\xcc\xe2\xf8\xa4\xd0\x92\xf8\xc4\xf8`\xe7"\x93\x92\xe4\x8cZ\x00\xa8&=\x8f'))
encrypt_archive(archive_filename, passphraseA, passphraseB)
print 'Archive created successfully.'
def updateArchive():
archive_name = raw_input('Please enter your archive name: ')
passphrase = raw_input('Please enter your passphrase: ')
passphraseA, passphraseB = passphrase.split()
website = raw_input('Website: ')
username = raw_input('Username: ')
password = raw_input('Password: ')
dla_filename = archive_name + '.dla'
db_filename = archive_name + '.db'
decrypt_archive(dla_filename, passphraseA, passphraseB)
conn = sqlite3.connect(db_filename)
cur = conn.cursor()
cur.execute('INSERT INTO Passwords VALUES(?,?,?)', (website, username, password))
conn.commit()
conn.close()
encrypt_archive(db_filename, passphraseA, passphraseB)
print 'Update done.'
def accessArchive():
archive_name = raw_input('Please enter your archive name: ')
passphrase = raw_input('Please enter your passphrase: ')
passphraseA, passphraseB = passphrase.split()
website = raw_input('Website: ')
dla_filename = archive_name + '.dla'
db_filename = archive_name + '.db'
decrypt_archive(dla_filename, passphraseA, passphraseB)
conn = sqlite3.connect(db_filename)
cur = conn.cursor()
cur.execute('SELECT Username, Password FROM Passwords WHERE Website=?', (website,))
results = cur.fetchall()
conn.close()
encrypt_archive(db_filename, passphraseA, passphraseB)
if len(results) == 0:
print 'No results.'
else:
for result in results:
print result[0], ':', result[1]
if __name__ == '__main__':
print HEADER
print '1. Create a new password archive'
print '2. Add a password to an archive'
print '3. Access a password from an existing archive'
try:
res = raw_input()
if res == '1':
createArchive()
elif res == '2':
updateArchive()
elif res == '3':
accessArchive()
else:
print 'Wrong choice'
except:
print 'Error.'
dbを暗号化してdlaを作成したあと、dbを削除している。dbを削除する処理をコメントアウトして実行してみる。
$ python dashlame.py
/.m.\
/.mnnm.\ ___
|.mmnvvnm.\. .,,,/`mmm.\
|.mmnnvvnm.\:;,. ..,,;;;/.mmnnnmm.\
\ mmnnnvvnm.\::;;, .,;;;;;;;;/.mmmnnvvnnm.|
\`mmnnnvvnm.\::;::.sSSs sSSs ,;;;;;;;;;;/.mmmnnvvvnnmm'/
\`mmnnnvnm.\:::::SSSS,,,,,,SSSS:::::::;;;/.mmmnnvvvnnmmm'/
\`mnvvnm.\::%%%;;;;;;;;;;;%%%%:::::;/.mnnvvvvnnmmmmm'/
\`mmmm.%%;;;;;%%%%%%%%%%%%%%%::/.mnnvvvnnmmmmm'/ '
\`%%;;;;%%%%s&&&&&&&&&s%%%%mmmnnnmmmmmm'/ '
| `%;;;%%%%s&&.%%%%%%.%&&%mmmmmmmmmm'/ '
\ | / %;;%%%%&&.%;` '%.&&%%%////// '
\ | / %%%%%%s&.%% x %.&&%%%%%//%
\ .:::::. ,;%%%%s&&&&.%; ;.&&%%%%%%%%/,
-!!!- ::#:::::%%%%%%s&&&&&&&&&&&&&&&&&%%%%%%%%%%%
/ :##:::::&&&&&&&&&&&&&&&&&&&&&%%%%%%%%%%%%%%,
/ | `:#:::&&&&&&&&&&&&&&&&&&&&&&&&%%%%%%%%%%%%%
| `&&&&&&&&&,&&&&&&&&&&&&SS%%%%%%%%%%%%%
`~~~~~'~~ SSSSSSS%%%%%%%%%%%%%
SSSSSSSS%%%%%%%%%%%%%%
SSSSSSSSSS%%%%%%%%%%%%%.
SSSSSSSSSSSS%%%%%%%%%%%%%%
SSSSSSSSSSSSS%%%%%%%%%%%%%%%.
SSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%
SSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%.
SSSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%%%
SSSSSSSSSSSSSSSSSS%%%%%%%%%%%%%%%%%%%%.
WELCOME TO DASHLAME
1. Create a new password archive
2. Add a password to an archive
3. Access a password from an existing archive
1
Please enter your archive name: nora
Getting random data from atmospheric noise and mouse movements..........
This is your passphrase : foundationalist oudated
Please remember it or you will lose all your passwords.
Archive created successfully.
作成されたdbをDB Browserで開き、Passwordsテーブルを見ると、フラグが格納されていた。
INSA{Tis_bUt_a_SCr4tch}
Dashlame - Part 2 (Crypto 400)
暗号化の処理概要は以下の通り。
・パスフレーズ2つをwordlist.txtから選択
・DBファイルを生成
・パスフレーズAでAES暗号化、さらにパスフレーズBでAES暗号化
ブルートフォースでパスフレーズを探り、復号してSQLiteファイルのヘッダ部になるよう復号する。
from Crypto.Cipher import AES
import random
PEARSON_TABLE = [199,
229,
151,
178,
53,
6,
131,
42,
248,
110,
39,
28,
51,
216,
32,
14,
77,
34,
166,
213,
157,
150,
115,
197,
228,
221,
254,
172,
84,
27,
36,
156,
69,
96,
12,
220,
225,
137,
246,
141,
44,
208,
191,
109,
163,
21,
173,
250,
98,
227,
203,
162,
188,
3,
105,
171,
215,
15,
207,
218,
234,
56,
136,
235,
97,
79,
189,
102,
134,
11,
224,
117,
177,
222,
100,
129,
78,
18,
130,
187,
9,
184,
99,
108,
202,
13,
238,
17,
94,
70,
180,
144,
185,
168,
123,
71,
176,
91,
4,
153,
103,
242,
80,
127,
198,
82,
169,
148,
48,
120,
59,
55,
230,
209,
50,
73,
31,
49,
142,
149,
167,
249,
116,
1,
7,
86,
143,
101,
29,
52,
114,
154,
160,
128,
19,
170,
46,
214,
38,
67,
186,
252,
181,
145,
212,
183,
22,
231,
107,
43,
47,
122,
251,
217,
5,
62,
88,
244,
200,
93,
240,
219,
124,
58,
161,
89,
211,
158,
247,
60,
236,
65,
106,
113,
66,
81,
165,
194,
223,
40,
233,
126,
139,
72,
132,
61,
135,
57,
87,
182,
164,
35,
159,
118,
8,
83,
210,
243,
104,
76,
75,
119,
90,
138,
20,
206,
95,
16,
74,
33,
245,
237,
111,
64,
253,
125,
23,
232,
193,
37,
175,
92,
30,
241,
255,
133,
0,
140,
2,
155,
85,
10,
146,
179,
25,
26,
226,
201,
195,
121,
190,
63,
68,
152,
45,
147,
41,
204,
192,
205,
196,
54,
174,
239,
112,
24]
def pad(s):
mark = chr(16 - len(s) % 16)
while len(s) % 16 != 15:
s += chr(random.randint(0, 255))
return s + mark
def unpad(s):
return s[:-ord(s[-1])]
def get_pearson_hash(passphrase):
key, iv = ('', '')
for i in range(32):
h = (i + ord(passphrase[0])) % 256
for c in passphrase[1:]:
h = PEARSON_TABLE[h ^ ord(c)]
if i < 16:
key += chr(h)
else:
iv += chr(h)
return (key, iv)
def encrypt_stream(data, passphrase):
key, iv = get_pearson_hash(passphrase)
aes = AES.new(key, AES.MODE_CBC, iv)
data = pad(data)
return aes.encrypt(data)
def decrypt_stream(data, passphrase):
key, iv = get_pearson_hash(passphrase)
aes = AES.new(key, AES.MODE_CBC, iv)
data = unpad(aes.decrypt(data))
return data
with open('admin.dla', 'rb') as f:
dla = f.read()
with open('wordlist.txt', 'r') as f:
wl = f.read()
words = wl.split('\n')[:-1]
SQLITE_HEADER = 'SQLite format 3\x00'
enc_list = {}
for word in words:
enc = encrypt_stream(SQLITE_HEADER, word)
enc_list[enc[:16]] = word
for word in words:
dec1 = decrypt_stream(dla, word)
if dec1[:16] in enc_list:
word2 = enc_list[dec1[:16]]
print word2, word
dec2 = decrypt_stream(dec1, word2)
break
with open('admin.db', 'wb') as f:
f.write(dec2)
復号を試した結果、以下のパスフレーズで暗号化したことがわかる。
spanish inquisition
復号したdbをDB Browserで開き、Passwordsテーブルを見ると、フラグが格納されていた。
INSA{D0_you_f1nD_it_Risible_wh3N_I_s4y_th3_name}
Jean-Sébastien Bash (Crypto 500)
コマンドをAES-CBC暗号化したものを指定すると、そのコマンドが実行される。例としてls -l の暗号化データのみがわかっている。flag.txtがあるので、その内容を見ることができればよい。いろいろ試した結果、CBC Oracle Padding Attackで2ブロック目でcat flag.txtに復号できるような暗号データを割り出すことができればフラグが得られそう。
本来はプログラムでやりたいところだが、SSHでこのttyに接続する方法がわからず、手動でCBC Oracle Padding Attackを実行する。
$ ssh -i ~/.ssh/id_inshack -p 2227 user@jean-sebastien-bash.ctf.insecurity-insa.fr
The authenticity of host '[jean-sebastien-bash.ctf.insecurity-insa.fr]:2227 ([51.83.110.181]:2227)' can't be established.
ECDSA key fingerprint is SHA256:Hp/VF/ZZ75+zXkpM05kpIoN/0YXe5Fqlt+pTr3O/kVE.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '[jean-sebastien-bash.ctf.insecurity-insa.fr]:2227,[51.83.110.181]:2227' (ECDSA) to the list of known hosts.
___ _ _ _ ____ ___ _ ___
|_ _|_ __ ___| | | | __ _ ___| | __ |___ \ / _ \/ |/ _ \
| || '_ \/ __| |_| |/ _` |/ __| |/ / __) | | | | | (_) |
| || | | \__ \ _ | (_| | (__| < / __/| |_| | |\__, |
|___|_| |_|___/_| |_|\__,_|\___|_|\_\ |_____|\___/|_| /_/
===========================================================
You are accessing a sandbox challenge over SSH
This sandbox will be killed soon enough.
Please wait while we launch your sandbox...
===========================================================
Welcome on my server. /help for help
>/help
This is a tool so that only me can execute commands on my server
(without all the GNU/Linux mess around users and rights).
- /help for help
- /exit to quit
- /cmd <encrypted> to execute a command
Notes (TODO REMOVE THAT) ---------------------------
Ex:
/cmd AES(key, CBC, iv).encrypt(my_command)
/cmd 7bcfab368dc137d4628dcf45d41f8885
>/cmd 7bcfab368dc137d4628dcf45d41f8885
Running b'ls -l'
total 8
-rw-r--r-- 1 root root 21 Apr 25 21:18 flag.txt
-rwxr-xr-x 1 root root 2066 Apr 25 21:50 server.py
/cmd 7bcfab368dc137d4628dcf45d41f88007bcfab368dc137d4628dcf45d41f8885
What do you mean?!
/cmd 7bcfab368dc137d4628dcf45d41f88017bcfab368dc137d4628dcf45d41f8885
What do you mean?!
/cmd 7bcfab368dc137d4628dcf45d41f88027bcfab368dc137d4628dcf45d41f8885
What do you mean?!
/cmd 7bcfab368dc137d4628dcf45d41f88037bcfab368dc137d4628dcf45d41f8885
What do you mean?!
/cmd 7bcfab368dc137d4628dcf45d41f88047bcfab368dc137d4628dcf45d41f8885
What do you mean?!
/cmd 7bcfab368dc137d4628dcf45d41f88057bcfab368dc137d4628dcf45d41f8885
What do you mean?!
/cmd 7bcfab368dc137d4628dcf45d41f88067bcfab368dc137d4628dcf45d41f8885
What do you mean?!
/cmd 7bcfab368dc137d4628dcf45d41f88077bcfab368dc137d4628dcf45d41f8885
Running b'\x1c\x01\xae\xa8\x95\x1b\x02\xa4\x1b{\xe8\x152,\xcb\xf96\xe6\xba]\xda\xe7\x0c\x86\x02\xd6\xa1-\xe3r\xcc'
sh: 1: ����{�2,��6��]��
�֡-�r�: not found
これでXORする前の7bcfab368dc137d4628dcf45d41f8885の復号したデータがわかった。あとは前がどんな文字列であっても2ブロック目が ; cat flag.txtに復号できる暗号データを計算してやる。
def str_xor(s1, s2):
return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s1, s2))
def pad(s):
p = 16 - len(s) % 16
return s + chr(p) * p
ct1 = '7bcfab368dc137d4628dcf45d41f88077bcfab368dc137d4628dcf45d41f8885'.decode('hex')
pt1 = '\x1c\x01\xae\xa8\x95\x1b\x02\xa4\x1b{\xe8\x152,\xcb\xf96\xe6\xba]\xda\xe7\x0c\x86\x02\xd6\xa1-\xe3r\xcc'
ct1_1 = ct1[:16]
pt1_2 = pad(pt1[16:])
pt2_2 = pad(' ; cat flag.txt')
ct2_1 = str_xor(str_xor(ct1_1, pt1_2), pt2_2)
ct2_2 = ct1[16:]
ct2 = (ct2_1 + ct2_2).encode('hex')
print ct2
この結果、暗号データは以下のようになる。
6d12310836521b340c3a0946431530077bcfab368dc137d4628dcf45d41f8885
>/cmd 6d12310836521b340c3a0946431530077bcfab368dc137d4628dcf45d41f8885
Running b'.\x15\xabh\xa1\x18\xd2\x88\xbeF\x7f\xdb\x12\xf9\xc4\xd7 ; cat flag.txt'
sh: 1: .�h�҈�F����: not found
INSA{or4cle_P4dd1ng}
INSA{or4cle_P4dd1ng}
Yet Another RSA Challenge - Part 1 (Crypto 500)
RSA暗号で、N、e、pの16進表記で'9F'を'FC'に置換したものと、cがわかっている。pの'FC'の一部を'9F'に置換することをブルートフォースで試して、Nを割り切れるものを探す。pがわかれば、qもわかり復号することができる。
from Crypto.Util.number import *
import itertools
def gen_p(str_p, t):
p = str_p
for e in t:
p = p[:e] + '9F' + p[e + 2:]
return eval(p)
with open('output.txt', 'r') as f:
N = int(f.readline().rstrip())
str_p_rep = f.readline().rstrip()
c = int(f.readline().rstrip())
e = 65537
idxes = []
index = 0
while True:
index = str_p_rep.find('FC', index)
if index < 0:
break
idxes.append(index)
index += 1
found = False
for i in range(1, len(idxes) + 1):
for j in list(itertools.combinations(idxes, i)):
p = gen_p(str_p_rep, j)
if N % p == 0:
found = True
break
if found:
break
assert N % p == 0
q = N / p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m)
print flag
INSA{I_w1ll_us3_OTp_n3xT_T1M3}
Yet Another RSA Challenge - Part 2 (Programming 222)
Part1と同様の問題。ただ、pが複数の文字のセットを置換しているので、難易度が上がっている。解き方は同様だが、プログラムとしては複雑化しているので、さまざまな箇所で注意が必要。
from Crypto.Util.number import *
import itertools
def get_idx(str_p, to_str):
idxes = []
index = 0
while True:
index = str_p.find(to_str, index)
if index < 0:
break
idxes.append(index)
index += 1
return idxes
def gen_p(str_p, t, from_str):
p = str_p
for e in t:
p = p[:e] + from_str + p[e + 2:]
return p
with open('output.txt', 'r') as f:
N = int(f.readline().rstrip())
str_p_rep = f.readline().rstrip()
c = int(f.readline().rstrip())
e = 65537
found = False
str_p = str_p_rep
idx0 = get_idx(str_p, '3E')
for i0 in range(1, len(idx0) + 1):
for c0 in list(itertools.combinations(idx0, i0)):
str_p0 = gen_p(str_p, c0, '59')
idx1 = get_idx(str_p0, 'E0')
for i1 in range(0, len(idx1) + 1):
for c1 in list(itertools.combinations(idx1, i1)):
str_p1 = gen_p(str_p0, c1, '9E')
idx2 = get_idx(str_p1, '89')
for i2 in range(0, len(idx2) + 1):
for c2 in list(itertools.combinations(idx2, i2)):
str_p2 = gen_p(str_p1, c2, '6B')
idx3 = get_idx(str_p2, '38')
for i3 in range(0, len(idx3) + 1):
for c3 in list(itertools.combinations(idx3, i3)):
str_p3 = gen_p(str_p2, c3, 'E4')
idx4 = get_idx(str_p3, '95')
for i4 in range(0, len(idx4) + 1):
for c4 in list(itertools.combinations(idx4, i4)):
str_p4 = gen_p(str_p3, c4, '09')
idx5 = get_idx(str_p4, 'FF')
for i5 in range(0, len(idx5) + 1):
for c5 in list(itertools.combinations(idx5, i5)):
str_p5 = gen_p(str_p4, c5, '5E')
idx6 = get_idx(str_p5, 'D4')
for i6 in range(0, len(idx6) + 1):
for c6 in list(itertools.combinations(idx6, i6)):
str_p6 = gen_p(str_p5, c6, '33')
idx7 = get_idx(str_p6, '8D')
for i7 in range(0, len(idx7) + 1):
for c7 in list(itertools.combinations(idx7, i7)):
str_p7 = gen_p(str_p6, c7, '12')
p = eval(str_p7)
if N % p == 0:
found = True
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
if found:
break
assert N % p == 0
q = N / p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m)
print flag
INSA{Uh_never_give_4w4y_your_Pr1mes_I_m34n_duhhh}
