1. はじめに
2021/5/22(土) 14:00 JST ～ 2021/5/23(日) 14:00 JST に開催された、SECCON Beginners CTF 2021 に参加し、3081 点（得点を得た 943 チーム中 31 位）でした。
4/30 ～ 5/2 に参加した WaniCTF での反省を生かしたため Crypto は全完、また苦手な Web も壊滅は免れましたが、各分野ともまだまだ修行が足りないと実感しました。
以下、Crypto 全問の Writeup を公開します。
2. Writeup
2-1. simple_RSA (Crypto, 75点, 想定難易度 = Beginner)
設問
Let's encrypt it with RSA!
problem.py
from Crypto.Util.number import *
from flag import flag
flag = bytes_to_long(flag.encode("utf-8"))
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 3
assert 2046 < n.bit_length()
assert 375 == flag.bit_length()
print("n =", n)
print("e =", e)
print("c =", pow(flag, e, n))
output.txt
n = 17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e = 3
c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613
攻略方針
$p$ と $q$ はそれぞれ $1024$bit、フラグは $375$bit ですから、フラグは $c$ の $3$ 乗根となるはずです。そこで、gmpy2 の iroot 関数を使って $c$ の $3$ 乗根を計算し、それをバイト列経由で文字列に変換します。
ソルバ＆フラグ
solve.py
from Crypto.Util.number import *
import gmpy2
n = 17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e = 3
c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613
m = gmpy2.iroot(c,3)[0]
print(long_to_bytes(int(m)).decode())
ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}
2-2. Logical_SEESAW (Crypto, 118点, 想定難易度 = Easy)
設問
We have an innovative seesaw!
problem.py
from Crypto.Util.number import *
from random import random, getrandbits
from flag import flag
flag = bytes_to_long(flag.encode("utf-8"))
length = flag.bit_length()
key = getrandbits(length)
while not length == key.bit_length():
key = getrandbits(length)
flag = list(bin(flag)[2:])
key = list(bin(key)[2:])
cipher_L = []
for _ in range(16):
cipher = flag[:]
m = 0.5
for i in range(length):
n = random()
if n > m:
cipher[i] = str(eval(cipher[i] + "&" + key[i]))
cipher_L.append("".join(cipher))
print("cipher =", cipher_L)
output.txt
cipher = ['11000010111010000100110001000000010001001011010000000110000100000100011010111110000010100110000001101110100110100100100010000110001001101000101010000010101000100000001010100010010010001011110001101010110100000010000010111110000010100010100011010010100010001001111001101010011000000101100', '11000110110010000100110001000000010001001111010010000110110000000110011010101110011010100110000010100110101100000100000000001110001001001000101000001010101001100000001010101010010110001001110001101010110100000110011010010110011000000100100011010000110010001001011001101010011000001101100', '11000010110010000100110001101000010001001111001000000110000100000110011000111110010010100110000000101110101101100000000010010110001001101000101010000010101000100000001000101110000010001001111001101010110100000010011010010110011000100000100011010010100010001001111001101010011000001101100', '11000110110010001100110000101000110001000111000000000110000000000110011010101110011000100110000010100110101101100100100010000100101001001000101010000010101000100000001010100110010010001001110001101010110000000110000010110110000000000000100011010010110010001011011001101010001000000111101', '11000110100010001100110000000000010001000111001010000110110100000110011010111110001010100110100011101110101110100010000000110100001001101000101010000010101001101000001000101000010010001001111001101010110000000010000010111110000000000010000011010010100010001001011001101010011000001111101', '11000010110010001100110001001000010001000011000000100110000000000110011010101110000010100110100011100110101110100010000000101100101001101000101010000010101001101000001010100010000010001011111001101010110100000110001010010110001010100100000011010010110010001011111001101010011000000101100', '11000110110010000100110001101000110001001011010000100110110000000110011000101110010000100110100001100110100110000000100010000110101001001000101010000010101001100000001000101110010010001011111001101010110000000010001010110110001010100110000011010000110010001011111001101010011000000101100', '11000010110010000100110000100000010001000111011000100110100000000110011000111110000010100110000001101110101111100100000010111110001001001000101000001010101001101000001000101010000110001011110001101010110000000110001010011110000010100010100011010010110010000011011001101010001000000111100', '11000010101010000100110001001000010001000011000000100110010000000100011000111110011000100110000001100110100101000010000000011100101001101000101000001010101001101000001010101110010110001001110001101010110000000010010010110110011000000010100011010000100010001011111001101010001000000101100', '11000010101010001100110000100000010001001111001010000110000000000100011010101110011000100110000011100110100111100110100000000110001001001000101010000010101000100000001000101100010010001011110001101010110000000110011010010110011010000000000011010010100010001011011001101010011000001101101', '11000010101010001100110001000000010001001011010010000110010100000100011000111110011000100110000010100110100111000100000000000100101001101000101010001010101000100000001000100000000110001001111001101010110000000110011010010110000010000100100011010000110010000011011001101010001000001101100', '11000110101010001100110001000000110001001111001010000110110000000110011010101110011000100110100001100110101111000100100010011110101001001000101010001010101000101000001000101100000110001011111001101010110100000010011010011110001000000100100011010010100010000001011001101010011000001111100', '11000110100010001100110001000000010001001011011010100110000000000100011000101110001000100110100001101110101101000110100010001100101001001000101010000010101000100000001010101100000010001001111001101010110100000110011010010110010000100110100011010010110010001001111001101010011000001101101', '11000110101010000100110000000000010001001111001010100110100100000100011010111110001000100110100001101110101100000000100000111110001001101000101000001010101001101000001010100110010010001011110001101010110100000110000010010110001010000010100011010010110010001001011001101010001000000101100', '11000010101010000100110000000000110001001011011010100110110000000110011000101110010010100110100000100110101111000010000000100100001001001000101000001010101001100000001000100000000010001011110001101010110000000010011010011110001010000000000011010010100010001001011001101010001000000101101', '11000110101010001100110001000000110001001111011000000110010100000100011000101110001010100110000001101110101110000100100000101110101001101000101000000010101000100000001010101010000010001011110001101010110000000010000010010110001000100100100011010000100010000001011001101010001000001111101']
攻略方針
フラグを $2$ 進法で表し、各ビット$50$パーセントの確率でキーの当該ビットと論理積をとる操作を $16$ 回行った結果リストが暗号文です。
平文のビットが $0$ であれば暗号文のビットは必ず $0$ であり、逆に平文のビットが $1$ であるにもかかわらず暗号文に $1$ が一度も出ない確率はキー側のビットが $1$ ならばゼロ、$0$ でも $1/2^{16}$ ですからほぼゼロとみなし、「$16$ 個の暗号文の当該ビットに少なくとも一つ $1$ が存在するかどうか」で平文の当該ビットの値を推測できてしまいます。
ソルバ＆フラグ
solve.py
from Crypto.Util.number import *
from output import cipher #rename: output.txt => output.py
L = len(cipher[0])
LL = len(cipher)
plain = "0b"
for l in range(L):
tmp = '0'
for i in range(LL):
if cipher[i][l] == '1' :
tmp = '1'
break
plain += tmp
print(long_to_bytes(int(plain,2)).decode())
ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}
2-3. GFM (Crypto, 222点, 想定難易度 = Easy)
設問
Github Flavored Markdown
Google Facebook Microsoft
And...?
problem.sage
FLAG = b'<censored>'
SIZE = 8
p = random_prime(2^128)
MS = MatrixSpace(GF(p), SIZE)
key = MS.random_element()
while key.rank() != SIZE:
key = MS.random_element()
M = copy(MS.zero())
for i in range(SIZE):
for j in range(SIZE):
n = i * SIZE + j
if n < len(FLAG):
M[i, j] = FLAG[n]
else:
M[i, j] = GF(p).random_element()
enc = key * M * key
print('p:', p)
print('key:', key)
print('enc:', enc)
output.txt
p: 331941721759386740446055265418196301559
key: [116401981595413622233973439379928029316 198484395131713718904460590157431383741 210254590341158275155666088591861364763 63363928577909853981431532626692827712 85569529885869484584091358025414174710 149985744539791485007500878301645174953 257210132141810272397357205004383952828 184416684170101286497942970370929735721]
[ 42252147300048722312776731465252376713 199389697784043521236349156255232274966 310381139154247583447362894923363190365 275829263070032604189578502497555966953 292320824376999192958281274988868304895 324921185626193898653263976562484937554 22686717162639254526255826052697393472 214359781769812072321753087702746129144]
[211396100900282889480535670184972456058 210886344415694355400093466459574370742 186128182857385981551625460291114850318 13624871690241067814493032554025486106 255739890982289281987567847525614569368 134368979399364142708704178059411420318 277933069920652939075272826105665044075 61427573037868265485473537350981407215]
[282725280056297471271813862105110111601 183133899330619127259299349651040866360 275965964963191627114681536924910494932 290264213613308908413657414549659883232 140491946080825343356483570739103790896 115945320124815235263392576250349309769 240154953119196334314982419578825033800 33183533431462037262108359622963646719]
[ 53797381941014407784987148858765520206 136359308345749561387923094784792612816 26225195574024986849888325702082920826 262047729451988373970843409716956598743 170482654414447157611638420335396499834 270894666257247100850080625998081047879 91361079178051929124422796293638533509 34320536938591553179352522156012709152]
[266361407811039627958670918210300057324 40603082064365173791090924799619398850 253357188908081828561984991424432114534 322939245175391203579369607678957356656 63315415224740483660852444003806482951 224451355249970249493628425010262408466 80574507596932581147177946123110074284 135660472191299636620089835364724566497]
[147031054061160640084051220440591645233 286143152686211719101923153591621514114 330366815640573974797084150543488528130 144943808947651161283902116225593922999 205798118501774672701619077143286382731 317326656225121941341827388220018201533 14319175936916841467976601008623679266 112709661623759566156255015500851204670]
[306746575224464214911885995766809188593 35156534122767743923667417474200538878 35608800809152761271316580867239668942 259728427797578488375863755690441758142 29823482469997458858051644485250558639 137507773879704381525141121774823729991 29893063272339035080311541822496817623 292327683738678589950939775184752636265]
enc: [133156758362160693874249080602263044484 293052519705504374237314478781574255411 72149359944851514746901936133544542235 56884023532130350649269153560305458687 67693140194970657150958369664873936730 227562364727203645742246559359263307899 98490363636066788474326997841084979092 323336812987530088571937131837711189774]
[244725074927901230757605861090949184139 63515536426726760809658259528128105864 297175420762447340692787685976316634653 279269959863745528135624660183844601533 203893759503830977666718848163034645395 163047775389856094351865609811169485260 103694284536703795013187648629904551283 322381436721457334707426033205713602738]
[ 17450567396702585206498315474651164931 105594468721844292976534833206893170749 10757192948155933023940228740097574294 132150825033376621961227714966632294973 329990437240515073537637876706291805678 57236499879418458740541896196911064438 265417446675313880790999752931267955356 73326674854571685938542290353559382428]
[270340230065315856318168332917483593198 217815152309418487303753027816544751231 55738850736330060752843300854983855505 236064119692146789532532278818003671413 104963107909414684818161043267471013832 234439803801976616706759524848279829319 173296466130000392237506831379251781235 34841816336429947760241770816424911200]
[140341979141710030301381984850572416509 248997512418753861458272855046627447638 58382380514192982462591686716543036965 188097853050327328682574670122723990784 125356457137904871005571726686232857387 55692122688357412528950240580072267902 21322427002782861702906398261504812439 97855599554699774346719832323235463339]
[298368319184145017709393597751160602769 311011298046021018241748692366798498529 165888963658945943429480232453040964455 240099237723525827201004876223575456211 306939673050020405511805882694537774846 7035607106089764511604627683661079229 198278981512146990284619915272219052007 255750707476361671578970680702422436637]
[ 45315424384273600868106606292238082349 22526147579041711876519945055798051695 15778025992115319312591851693766890019 318446611756066795522259881812628512448 269954638404267367913546070681612869355 205423708248276366495211174184786418791 92563824983279921050396256326760929563 209843107530597179583072730783030298674]
[ 662653811932836620608984350667151180 304181885849319274230319044357612000272 280045476178732891877948766225904840517 216340293591880460916317821948025035163 79726526647684009633247003110463447210 36010610538790393011235704307570914178 284067290617158853279270464803256026349 45816877317461535723616457939953776625]
攻略方針
設問では有限体上で正方行列（$8$×$8$）を使った「暗号化」が行われておりますが、key が与えられているため復号は容易なはずです。
実際、key の逆行列は（存在すれば） key.inverse() で求められるので、それを左右から乗じれば元の行列 M が求められます。
ソルバ＆フラグ
solve.sage
SIZE = 8
p = 331941721759386740446055265418196301559
MS = MatrixSpace(GF(p), SIZE)
key = [[116401981595413622233973439379928029316,198484395131713718904460590157431383741,210254590341158275155666088591861364763,63363928577909853981431532626692827712,85569529885869484584091358025414174710,149985744539791485007500878301645174953,257210132141810272397357205004383952828,184416684170101286497942970370929735721],
[42252147300048722312776731465252376713,199389697784043521236349156255232274966,310381139154247583447362894923363190365,275829263070032604189578502497555966953,292320824376999192958281274988868304895,324921185626193898653263976562484937554,22686717162639254526255826052697393472,214359781769812072321753087702746129144],
[211396100900282889480535670184972456058,210886344415694355400093466459574370742,186128182857385981551625460291114850318,13624871690241067814493032554025486106,255739890982289281987567847525614569368,134368979399364142708704178059411420318,277933069920652939075272826105665044075,61427573037868265485473537350981407215],
[282725280056297471271813862105110111601,183133899330619127259299349651040866360,275965964963191627114681536924910494932,290264213613308908413657414549659883232,140491946080825343356483570739103790896,115945320124815235263392576250349309769,240154953119196334314982419578825033800,33183533431462037262108359622963646719],
[53797381941014407784987148858765520206,136359308345749561387923094784792612816,26225195574024986849888325702082920826,262047729451988373970843409716956598743,170482654414447157611638420335396499834,270894666257247100850080625998081047879,91361079178051929124422796293638533509,34320536938591553179352522156012709152],
[266361407811039627958670918210300057324,40603082064365173791090924799619398850,253357188908081828561984991424432114534,322939245175391203579369607678957356656,63315415224740483660852444003806482951,224451355249970249493628425010262408466,80574507596932581147177946123110074284,135660472191299636620089835364724566497],
[147031054061160640084051220440591645233,286143152686211719101923153591621514114,330366815640573974797084150543488528130,144943808947651161283902116225593922999,205798118501774672701619077143286382731,317326656225121941341827388220018201533,14319175936916841467976601008623679266,112709661623759566156255015500851204670],
[306746575224464214911885995766809188593,35156534122767743923667417474200538878,35608800809152761271316580867239668942,259728427797578488375863755690441758142,29823482469997458858051644485250558639,137507773879704381525141121774823729991,29893063272339035080311541822496817623,292327683738678589950939775184752636265]]
enc = [[133156758362160693874249080602263044484,293052519705504374237314478781574255411,72149359944851514746901936133544542235,56884023532130350649269153560305458687,67693140194970657150958369664873936730,227562364727203645742246559359263307899,98490363636066788474326997841084979092,323336812987530088571937131837711189774],
[244725074927901230757605861090949184139,63515536426726760809658259528128105864,297175420762447340692787685976316634653,279269959863745528135624660183844601533,203893759503830977666718848163034645395,163047775389856094351865609811169485260,103694284536703795013187648629904551283,322381436721457334707426033205713602738],
[17450567396702585206498315474651164931,105594468721844292976534833206893170749,10757192948155933023940228740097574294,132150825033376621961227714966632294973,329990437240515073537637876706291805678,57236499879418458740541896196911064438,265417446675313880790999752931267955356,73326674854571685938542290353559382428],
[270340230065315856318168332917483593198,217815152309418487303753027816544751231,55738850736330060752843300854983855505,236064119692146789532532278818003671413,104963107909414684818161043267471013832,234439803801976616706759524848279829319,173296466130000392237506831379251781235,34841816336429947760241770816424911200],
[140341979141710030301381984850572416509,248997512418753861458272855046627447638,58382380514192982462591686716543036965,188097853050327328682574670122723990784,125356457137904871005571726686232857387,55692122688357412528950240580072267902,21322427002782861702906398261504812439,97855599554699774346719832323235463339],
[298368319184145017709393597751160602769,311011298046021018241748692366798498529,165888963658945943429480232453040964455,240099237723525827201004876223575456211,306939673050020405511805882694537774846,7035607106089764511604627683661079229,198278981512146990284619915272219052007,255750707476361671578970680702422436637],
[45315424384273600868106606292238082349,22526147579041711876519945055798051695,15778025992115319312591851693766890019,318446611756066795522259881812628512448,269954638404267367913546070681612869355,205423708248276366495211174184786418791,92563824983279921050396256326760929563,209843107530597179583072730783030298674],
[662653811932836620608984350667151180,304181885849319274230319044357612000272,280045476178732891877948766225904840517,216340293591880460916317821948025035163,79726526647684009633247003110463447210,36010610538790393011235704307570914178,284067290617158853279270464803256026349,45816877317461535723616457939953776625]]
key = MS(key)
enc = MS(enc)
key_inv = key.inverse()
dec = key_inv * enc * key_inv
print(dec)
flg = ""
for i in range(SIZE):
for j in range(SIZE):
n = i * SIZE + j
if(dec[i, j]<128):
flg += chr(dec[i, j])
print(flg)
ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}
個人的には、「Galois Field イコール Galois 拡大体」という印象が強いので、有限体を Galois Field と呼ぶのには不慣れです。。。
2-4. Imaginary (Crypto, 264点, 想定難易度 = Medium)
虚数は好きですか？
app.py
import json
import os
from socketserver import ThreadingTCPServer, BaseRequestHandler
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from secret import flag, key
class ImaginaryService(BaseRequestHandler):
def handle(self):
try:
self.request.sendall(b'Welcome to Secret IMAGINARY NUMBER Store!\n')
self.numbers = {}
while True:
num = self._menu()
if num == 1:
self._save()
elif num == 2:
self._show()
elif num == 3:
self._import()
elif num == 4:
self._export()
elif num == 5:
self._secret()
else:
break
except Exception as e:
try:
self.request.sendall(f'ERR: {e}\n'.encode())
except Exception:
pass
def _menu(self):
self.request.sendall(b'1. Save a number\n')
self.request.sendall(b'2. Show numbers\n')
self.request.sendall(b'3. Import numbers\n')
self.request.sendall(b'4. Export numbers\n')
self.request.sendall(b'0. Exit\n')
self.request.sendall(b'> ')
try:
return int(self.request.recv(128).strip())
except ValueError:
return 0
def _save(self):
try:
self.request.sendall(b'Real part> ')
re = int(self.request.recv(128).strip())
self.request.sendall(b'Imaginary part> ')
im = int(self.request.recv(128).strip())
name = f'{re} + {im}i'
self.numbers[name] = [re, im]
except ValueError:
pass
def _show(self):
self.request.sendall(b'-' * 50 + b'\n')
for name in self.numbers:
re, im = self.numbers[name]
self.request.sendall(f'{name}: ({re}, {im})\n'.encode())
self.request.sendall(b'-' * 50 + b'\n')
def _import(self):
self.request.sendall(b'Exported String> ')
data = self.request.recv(1024).strip().decode()
enc = bytes.fromhex(data)
cipher = AES.new(key, AES.MODE_ECB)
plaintext = unpad(cipher.decrypt(enc), AES.block_size)
self.numbers = json.loads(plaintext.decode())
self.request.sendall(b'Imported.\n')
self._show()
def _export(self):
cipher = AES.new(key, AES.MODE_ECB)
dump = pad(json.dumps(self.numbers).encode(), AES.block_size)
self.request.sendall(dump + b'\n')
enc = cipher.encrypt(dump)
self.request.sendall(b'Exported:\n')
self.request.sendall(enc.hex().encode() + b'\n')
def _secret(self):
if '1337i' in self.numbers:
self.request.sendall(b'Congratulations!\n')
self.request.sendall(f'The flag is {flag}\n'.encode())
if __name__ == '__main__':
host = os.getenv('CTF4B_HOST')
port = os.getenv('CTF4B_PORT')
if not host:
host = 'localhost'
if not port:
port = '1337'
ThreadingTCPServer.allow_reuse_address = True
server = ThreadingTCPServer((host, int(port)), ImaginaryService)
print(f'Start server at {host}:{port}')
server.serve_forever()
攻略方針
サーバは、複素数の「登録」「表示」「エクスポート（暗号化して出力）」「インポート（復号して入力）」と、隠し機能としてフラグの表示をしてくれます。
ただし、フラグの表示は複素数を登録した辞書の中に「1337i」なるがいるときだけです。しかし、複素数の登録時には実部と虚部を入力し、実部が$0$のときはキーが「0 + 虚部i」の形式となるため、「1337i」を登録しようとすると「0 + 1337i」となってしまいます。
そこで、エクスポート機能やインポート機能の活用を考えます。幸いなるかな、エクスポート・インポートで使う AES は ECB モードなので、ブロック単位での順番の入れ替えとか中抜きとか色々細工ができそうです。
また、出力対象の平文は json.dumps の挙動に依存するので、あらかじめスペースの入り方などを確認をしておきます。これらを踏まえ、うまくキー「1337i」を生み出す方法を仕込みます。
具体的には、ある平文ブロックの末端が「"」で終わり、後のいずれかの平文ブロックの先頭が「1337i:」で始まるようにできれば、「エクスポート」→「中間ブロックを中抜き」→「インポート」で目的を達成できそうです。
攻略＆フラグ
競技では、次の $3$ つの複素数
9999 + 9999i
888 + 888i
777 + 1337i
を登録しました。このとき、エクスポート対象のデータ（平文）は、
{"9999 + 9999i": [9999, 9999], "888 + 888i": [888, 888], "777 + 1337i": [777, 1337]}
となります。先頭$32$バイト（$2$ ブロック）から後の$32$バイト（$2$ ブロック）を取り除くと
{"9999 + 9999i": [9999, 9999], "1337i": [777, 1337]}
となるので、これに対応する暗号文をインポートすれば目的を達成できます。
実際やってみると、エクスポートの結果として
efba3722581a53248df83b090cd27e23904899e8dd09215ad5991cab2ad458cb96b3aa2afda4efe4da0acba2a5551bf8bca2c698340c6f2d08690b7bad0509af78b6f4cb824f6bc76a139a04e4d7b2bfc87c6c78bfe4f9fe4556a8517be0ec1f
が出力されたので、平文の中間 $2$ ブロック分を除去した
efba3722581a53248df83b090cd27e23904899e8dd09215ad5991cab2ad458cb78b6f4cb824f6bc76a139a04e4d7b2bfc87c6c78bfe4f9fe4556a8517be0ec1f
をインポートして、隠しメニュー（$5$）を実行するとフラグが表示されました。
ctf4b{yeah_you_are_a_member_of_imaginary_number_club}
2-5. Field_trip (Crypto, 394点, 想定難易度 = Medium)
Someone is getting ready for a field trip.
problem.py
from Crypto.Util.number import *
from random import getrandbits
from flag import flag
flag = bytes_to_long(flag.encode("utf-8"))
flag = bin(flag)[2:]
length = len(flag)
A = []
a, b = 0, 0
for _ in range(length):
a += getrandbits(32) + b
b += a
A.append(a)
p = getStrongPrime(512)
q = getStrongPrime(512)
assert q > sum(A)
pub_key = [a * p % q for a in A]
cipher = sum([int(flag[i]) * pub_key[i] for i in range(length)])
f = open("output.txt", "w")
f.write("pub_key = " + str(pub_key) + "\n")
f.write("cipher = " + str(cipher) + "\n")
f.close()
output.txt
pub_key = [1627727230910376679190305250495462377673127325457772051463473603239280851247844857775094804468541458382943793317239787693930638537905012556126829098198853, 11390077915029058809550131014512708496324218365383793403681859478983277851788559377973666759678894435638593981031042225181697704452107123180828946159773515, 8179148350749291474514716907983121255146115753248586194447416551426945499482207275600097490935543753034574160607266468264368850157525750760264486882342004, 10941812031082272057798702874172927467797501065302416966001023128384698906928085390135010716098940533908593173515390255250462556662539593195364174183111378, 3614745341275480428658319936106342479447545475997102535381861144548202616710068200734103360803941309632252623075660097928171614636575252144104941167875823, 823178354506932008674641402551278888372261897630495965386060191754392263016108442664620321118524856044971184623847186758394463971043188530296897451771186, 6126448477839481210946440528787637248330004648968502621267179732866433426925983876878526325407025084527441161833253484921016836135453814544622972372789122, 7466110955532217718350434679985113267727029661150471938943244057893689660733974538173921362412025690616586611377720710981300593198085731197422760123486823, 8494763827840222748734700648979436004399105472251068803766808893440611752185480154140145100605542790978072404829682982969121103538123360622748789468463235, 11189720630530432372988722422207131896593163626212669159020725119617893436033981396794415249303994853786917522131094575897127888600143225647812363683556711, 1715148450280854136862317182605666023423823213970399964487054641958918804151884265498646179998842243400236338074592006759506277918874694729594147582035223, 5540431799313225600289987101975658390666115836842131612473239501357335750526216599306611213275093940185339830230979569745307094862150569297375944630143685, 6065288708774786746551562482382919833260656987958350973874133802701002919726540869583838838759287884702711861900261459529790522631020994523440533144502775, 7234486161196695664277498569820928727263659579862329533231742765775361673322113762206501017047056413054134570841827024859772736445100885511621826030636721, 5790466157587780811391418203868871988082506102567632509545303269169653572768191738557448523974150628231236540920327049499163032154806889411357922070960923, 614487011969781591950160360975242589085019947676643049152128264494968822101147186721613098402364118730615692871650144954496839040414405067974702421023905, 2278335646833352836053675691559323543806718574568397090218657707516163081796224967487437830189535674711866517339720796812479305160299543957122930902733680, 134879407361379889128094711300170056598390106523526115878191161673136372971584663792937617159109985222609270062841930765578765868002121297161450924875670, 9519287056894525158582578864977452979099306021811340603346876269211863740542948640369599220180050455648379571390554225127442591697808606219706674595426234, 8402285089367247619745011222681496327228844899382581802919813910782074703470238610758895365966927878107041275900491204851884282695630780037206677089073743, 5406457121320262339650448405765205909738170940504528472739736687195948514104117332533865686024659827591710796087546713263642562769582609048315709994928120, 3801142902357168548686125964812533589729813463183268403565815227989154972362571932731819983704767934865803934241215040857671291683075724662922338415917182, 5436947858801618770870878269048974285422847359285195936610682423767931295811884290027916455982229786770673284249525164815726004308812462166914799567512132, 3815052792278989714677334168820537877167491234877274326563177152219263932218376863319752340985935154603585067421571719480783708315218297849199545235122158, 7027654996878753275961749122684655552094983534693747937102146760033187963841168663352245494579053154889790710851894666675012966264073470852357878798185461, 1902120513092875903338226046347919002820646057582844141644280347474263924997621676201569803130224359726311851288100274056706312976734099927488849060865100, 11761048354354487182165243290860187512062141561289470397986167013898235429358707127696368115069038004916028536939325487876797540965691324574012326619996716, 9757529573128395073155274559294819779368946395358435204233094762544296369601908201919613288263346489553542399982377228944641012976067072706476767936937491, 2453946098113482646488949231406349598804639726542182990917700647199960018577504360015030201773257233191736013580250768440614299316063045659162111320187018, 9319706037803173583171999553640056770008389931059980211073835507260771807765054342788152787019226685278576061693822692868824482538539619437423931723867638, 2415898081000285885317495095869472168214386057550401076099272996668473089357177847144038836740891535925645870811083042646884362664103196192764729813731836, 6831371739629516878762522327702302241691133397282458321594420516244457682248807904681947662649834044913983745000847132408435191823193733626430289939177704, 8911487453444536593323920821809421883218471526912139746762963559650262957593522887117811194390719914863010957953813489075136297325877225195754168400092143, 10827165969679594628739062220054978610293037445161650396571452340162805594515879042614168001849163738612474327713960410907001062746512950632119899645486165, 704502156006234895839438994186203068165985741674000184830486957231155986311282679180631398966930213171517941820858545126492495344870861094407012184640823, 4290415868027081329996593194887552166008805715995986555372686051077953073250496320908121226211705000105956461168744315858180066368242874040891532657113169, 10545064273500469407002351635866768900216078230158001025925896743623392315718385811101431137913336305418674086955813416589952935610377379991777656464560904, 222038761397496749360785916329206840697038382632411616626840724191778442228487034550449387870944140465498765132320783016190199911880849496664880021486811, 1441186128607304956019821803029517117342542746331149661877318328445155144327519269434552605831697245827929704875263722242762828396110183771144964459394537, 6262035322760676455872259557860354851246503548034172638052912261395035948982118234312601487324050800839022328905285373880135361896745345697099469992851131, 4524184613244291795109754414667150818999629856838115549409097166729848395081524481473123941545320222662731732155390386071843025802825179816381298820729824, 5283966263613790830455133450578806522976393376747821388280595897660468710659040194781402893846259456267710256514673635793738636888433235312976117540997670, 734269568748111640052090946231180906652495087236442702545338576377208172123085276589342632556585327179776362520321678519591781841790141214498484270905176, 9451656806863570616172924236279721588970386798009311529339115014539046020513297990270343561908720603044124605812085133334217197137400578937155121179082520, 3051642371650657054700521038491519744705758620980094104902981323717627057520029747610177450175370083995813698968822095618298179968058178062764130608659423, 7138952449752237733780319852689997148652360533005590188952403508900689828377062768778919668480243722079246374005954390574613559146429228635500313866647830, 338855726414699556488111033893516095818452279804805254966111715246104055445804382690731870669031649972111753917285671926417016391990572580298041758371253, 9434338110989485656020470689018936204735538469042920590064694759331237737230785701304245293791165210985574378910680725501788497370867036347820422455861008, 11743357680578349359162842808973807055764041927045206000202223764225228589230152100644412242832121778126080931892859490461297768718139167127509484426935516, 10809477666198375316415855765052746110763351926084144990851771467019653102707561871201368035835499988211685995329231458471783072292334735121148934257474481, 8361290012462548161951254835930186683493837370922544617362025529237532210142924359445724137459698924851513253914440872353889163895924265960022186220544709, 9110331121231523509307877539206254496672950206166437894520019335519961179869340990239003361109383043974388021961851540679419112950782472645836218947069184, 10393081243233784801735338636405290390807650076446916623218248492311682427662136868388090954521461644084639834083277464607638024855738147795387101337574226, 8635144191933378357854933636265474571012056586049858041465470568749464263500256261392037808005866345720862774122069273582266436367817433458956532049780774, 4418352683953086382401924269854964217677896486679104773071252777228873262401683489714714052284264053149769016874563276933086640659387489800484854697533082, 11405236243645314277535277368602821528967628188171456747788000113810218023475667423693365373226884179614448925519215120109302962469860586286886119774049347, 2771015879550163030165657530654451086641677020792616747235577420773494369048734442366451848062127222028674614372620701644053503582161481006114727140581880, 9898040106597885401583759646390295107361734996622402136464938780239784598493749472168979827154809586241421519720993011993090134889937532355080074694914236, 5777113427214185313997366187449136632797879082988812318910143048720548368905732814341066506919809935796023024351923191808765189492249761422655292085807672, 629078785533612849316912686429345503590958550796433801577651410881398124391524995844450352946049732397726053930432847836219823262977515490137563736301854, 10801401295641411092684548694395594070024865629243283117987852161404597651908799260812686233176670601757986605943575400167658544559357084608391881834446315, 230070532084711979714073115090944140276333108429708057888154566997156763934572283796043255414920534623439966012683795418379115522344166096620802666822158, 2653141234649791159270555987752178497577182383710867439287180210805265047951979750613536416122211396079337182535060893836409041761200653941413783366601647, 9819385030911488229711423422290746871860893626170080234281491318242107780563809621339193314159985954076683835744606911808745839075685015953738930366461504, 10787755099446585851067558577389646651361480328446469420228814545570006340103348743933813554961768885774075313271971611985063086273746596057549133130286996, 10263252536258338191094138495727374812304043040018874292736338983366473600613438579330512622405111321614329014124397343691422153751941094425939148115419144, 8264896351960310713538344637075442139532971304017521357074393238425679130058257615139742072920826381868768043200623504461528962772634922574219204008611446, 2147098598151809758012396937896797587780500058011635682566222787994691651248284456431917338694337594118487127099227127261521149212812046027401283431626653, 835919714553401942404334437551365593064566099647192274874446759913634276581629201627681467376279981880841428500989955273531853693899249169333824801078750, 3137791999402738811435798454665497017869650524841428289369351443750201278747862575707706000714058324362992205288888567315278677490077727774835379088436006, 1349083629045995316048152731789283957044698996027937078185713363080897115381735648010571340344037922487894330206612400451771128607496786215899669980572631, 7151470156920468764362424494490172229163475650617111710841057240618925425354832625922496799292567847545183967966217669595274609257135294729383362095738774, 969214900808450132888751546918076429566821040071276149919254643349125098280414720732281136532422094620745562927599642733412626063657268885891539827291347, 6837332378607129931141030022171984123309503518721395037825344337090610567350813310712435580992877616537619887480522470873869606202135747709672130000907665, 8364995496256554616029977590294874242060213310040785018239136897992699511676399955908119484626044885062103507697132148339409250907597810483796867399165984, 11150349307177473530307176249702818877580126605366046220776402492478240524483158185915502079277290319184145846124682470893997182480458282506949040910499392, 1658289696192983790897943272438520487042075314752724083703126291291970666851342327974958388331127028328164897980277317490557958037865872463479747423524926, 9131362533429004401441350892122360841764586109487383276247013461128740601257141642707756754491618871428100079351302334977304105019443858133126184771545043, 9330397298855941369542973735462725696662687125148526787140181659060684716824505001027119473890099274372275476966877359227102525263938755962082724482518050, 10253738743836159588621071259178219022563765128400530571588761301542176945143921956862350468019119752368079008322471485199577898502308114141549691485328119, 11600594703900902422866629561800220560103998368093720941938164737980026015168964844534647856810134441227007791139257922310172433764469537384240765031240277, 2244615925157610777383156726581397246130116260122731876532858274705570510773554286422504200282490618833439009494062776847822891629410146208293931139019598, 9733004403706149967520978404543771261324511435667728541178207212979721154676382281225409760729300022193360065470568452825325123972934958237623605165978375, 254354500603048544344274289207513537562120915759345747274593609495132631100017756321505502767286130589730909912096517138306900867943453650871702051139820, 8370794524988243638695092359570003691661556745490662742148202903860415924783217755602807126418561604959238898020252625472585689205979031497593592055937411, 8794340191988240556017659906713384748965043778452355164633928970799666465022803989063363371175889737930849051628085913544959957566363686438835153843412939, 5332480590532842430323558618578543509309546254138522597994235482505696944206135906595816348986471057105575982103534851867035705911825105890554636399117959, 3950651369214765379669331091209846132473398609747032844881769499832818398279627204457821432880778469543121042120812033753781942045800062715602362551437446, 8764597745555787966301901389786365105087694140863727334245233470132110641169237259387203997461935069288656230569502194991969216616783525833400312149135717, 10893671311442357810344005102450557175906931304022699347689646165105262580304776183017675980891676148589951193879822475240682617753093939204073908090934123, 9279851910251720350566986284138542667714345125643347097239195337905126099452241423018671935749811042002501428789486379723371928823690546158499167561377363, 7467311785687010437555773880658735452282769858571517461749051862992815684658577766003123130545826154620513903602757430481744043605817836120355235645161971, 5108725545796520008985875560900754734992617221769641586339788732236758184078757049778190729232684046606028473386534748941226434872542329986204159374865318, 11867699353985069790536624225866578465253057547038747367192323201103495572410886289392307344367210629571626846502738311475794548637804314691361883633660854, 3307955753584481516914855590837996820524452980430232447056686239509247300748140903481811349702734702088092190468590865868219632872299773637242697461456553, 10198102385245501857792898248520943901262126311232584209734399129163853603686024999279049967928201510400871689285418724239616764378384016527780204413216674, 8228299095729026478677409017032361626919004386605335618535716218424202290478453122140182082896822897053196677144530584164608155945616171423914566350006168, 5112786368092391279903606929743330066336471986263730056133931970470350367734928619591357871627106533582770983308703750603891628446704447489958729107713715, 10469735493230359064821542968197039289870670760006858877107911033538981312661996508702709711101453750156345711233887576764596618880116679535070758686367835, 9196198524335526563875694798089709262412006598320807967509365313289345737999012223767852725432769548784378062829358869705294718633979410353031005678221802, 6683277380933096532362852252484564886247729619973370408526339212096381484171620318859617374568197001310631889191807697663323642106913958849690224925461694, 9529613981769374073447341366884871937833846177760706872163980387662932372533823749575103833419092123484129940660046036074238463645988110467224610841798396, 2266794669069907087687293539109983357111262788594707965340396512153714241039180932421689734859164235712168843370543545431747673801363827867496870372125336, 1866657295458158454881522810715564591136349581564835527057025586296173873670918151349885379247546649061814138440749434231115994040006915887222214832216793, 9148338051604628974249176335472004157326441570701111334833644249222513670344916886670861683334321358810579899657217206257613558265823876085505454588007968, 3150970195117521652874271187992011688081846017889819628953971423349119288736936005559152214262722455740251518841347209225787560336272283302792820677155456, 2654815978280349195745421700490321540189264095484815485625765415487938591288435811537239820689235000000161324407221020096227903798822533164408384845279219, 10613712470437968081140979473098189731268139640670987306626304368616232817231479865616941989006606100283262512680880271451166161316286745812304949833618532, 584771700542193176410575206781719730381455972184594687314858310873745548037581699189913439808225843016877940196620523275735084018626160581660280994642977, 7752227206782612731330946605694126516789657852557775310044628700046190614760547318085553165126745983752673912673179603938501945102414356429679923126279635, 6181114125680462568335637321427121237211288385454147219539532450576260468665546332121469615286892296528834796051391696892578291511969538036639317451275393, 9135050673473900291782130971149267435204316475664597051965244543275596770270798810469766060093645817494350474433396115526366874458378951375630266775342673, 10823484837094701160540558686227927842943057819522139544135134044387262556730658594806349353577086449873005218586065819838718307881055159834974985844681301, 9983072533960933746418223838369711407232082297937881132317170649759456192810500555555337035974971942717934370671547654549936811199706777826630199849997893, 9496860292179603670920445704807780801671759827403400028732735007396868161785125605066594722355616018953537321578676302542059539384517799908274423326672419, 1703385660623950359050969801655519572699157230875334655419427425211519057467450009673619270811656302454948012601207060423808873812556848095400818203864, 1124824934298417769296957031482302153675496794359839176778073940948277366770010987547411988487713939288525606195470668176368430409031376391243742928188737, 3229481917557768819829086515377643522962590749891024608854142700316113763497423916549064184792610168714433142930480984048981188717417434429561511671863340, 8294104032436327777486159971264402767334649287841961190030297139466131416369517365641129837491598616986084921647405266807970727164692073754656655602529261, 10841558702848626512201447043784390704658214933053467482697472164169627348933072901533434861934797167954203691251466593055982136720490185778511573725463091, 3178930784687138843088596584997903179579922587867410882667347234930875487458734591193687966659517370268916417823125671401884196339836390571169682168714634, 7454151195962571505291413229201537150280824884428852910895643182678249719784935336643779191181482778848818993208221255258132534583411781119205078130090493, 2015156865486836120778682378960560170098671955237858754748152131638573845290736893280308181218687853014604174145816633360273506979314685066746558185772213, 7518280147605752377356085467400615547824826179564770315069235526007505409683817948956679988243512932507522237221929606038316891387806953147114552195723037, 2024819075929565623167333132137655283846300903116425428839619347379614001726638635657985601976090872185635173118822397894048579095835679930797308966510161, 6215993704628241793832033783162789293924516338030608992171516163123272062860326445636293235015378684705933988212973591046212191958652259015996841348525233, 10721074643733864954970318017687419861549782195881708432332255884413370619291750997381857646366632973722794738669419561902209255528214363399300572318598976, 11051099778413936201588813479333950625696456591449077944829525186174150306810041964709311295480133149976157065280899311313708649194744567649855692630214364, 1688310516465382129824706766300320323086828782213510237597315430363470883127564821837914550530086658434882374985922949368294443247364921794573340486906238, 3192364479471168028710837283899918625935362325330335301033556406770563105461096419504116373286876626652315031493543268384008485267512339959435053933841313, 10572194847482440812332986591051630462883201860708366563698662854481883222498284684687782612499400666528966898408853346133591660937905688329633621416854553, 3947736123018809396047345259826555348314283757126565484195977099646537310353904000152697460719528310696082204835098702895122864267256319395558913520116392, 11182766638391936877995854197520085129151384977709217790829422656082419193097932980148237939707803168327610358370853571892812158944282257498680855767229677, 3785005419673190260210131419611296437580991153996528806706953071932484677468263744891384933085989064774778069519276028906778427000799962507340099134917935, 5080917081750594708323405365145453207238012111759111382500875071859284459953169985334929889554817530710648209427731938198054042780871188922340543142924939, 4048618658491596677603187303911377706030641697591465631347400097836527581077675625158162761353955215178164330226108795767011183973412955473474219799087197, 10756640002316419897851435267941668380681904604159814743578516612294764433749019434802471420890142162949979364053015555721098798895592890837753394402601600, 9576566069431525883762715341983732560085629671089897559307942342017237423144442133049657728319197511124149519512976698322385517896297503762943044451831682, 7165568955290222509156785556616132982441722968221047749287853532522706162989495783845174854505888062434423314563689608447591958198763443599582520354403262, 4886305788841254495561906932817366567996456189096683440102055315067086182866905742486434971809212556403255604320990070575999450589283865669827032247378026, 7974570179507384046793957867326714371457957470114044411785079610018843160599140562038134667373750144719208045822373607909523650049764790454624533560094438, 4699399884541021847518656224539601167184097708756378716924596672912033629859806682769146527434005646171138846377909985611374237928982199839841484034595124, 284699436285137586151623117958887854384067390251467180741921703094848380911015079304006363413374407709029807303242873481239873129968266824381074061576781, 7424603511991768566970306812540965037304046015506639020124822754523996481221874622779988256386434795599778401964853467233299073228923733026307559753461753, 10204802163769309817146573619091345092885022518990654924014656950712859972992223551924164346235264566717972681978724897809251721761375877244325753782176857, 9438420831957673445603305728093735430853841298036258989011836327310515846466591187953907621823894906525289199249629125784422458200828675239244266235272346, 10890020912636917421687599720986965506018026168566001306712363618691959621006154914816267736938077225993112076739368505752571167457735320815453253378863503, 7612905558494937122786907665601018921881673472453283960241071713931932464659066013897727134859798086411171769879216045995689241333798042462244230212212984, 6550836530141701911622212575637172610040961303781916329326618809093764882252631974098246519703546676024381344519501504247292099463026478299004729842120794, 810463246670448806288456723577253991309434245269230870268065162161683791423034382984779736398143238385314386270683813736785640795616980760740211633626680, 7987182793636123387405676060009070849539867837366546908532424481956731048800366776798314558709408103425915728898034756937642304986810890072970609409560920, 7214351975158893076759227293921988348242566545977916782340607663706728189002123227844454484007467068046595059915519900187040379326564702309329878614144193, 11014878924638095287994257524709668434779725530794695530401129023156413550436897097358726050238680106826431375584530778605250124880702844280402008225394872, 6027887507568715893917001583622263960984925990340905403518345783740595181396031310602841240588909634580493242079149694551634238251017289222201905339455410, 416347896819517370094008870355298145260975680342177838528189406107683995143464927834127034596304824694484130253280370972827705469927428341950098126774907, 11163457967473117384909170091800080756098465652817504823829957246101519582406623920562879665741186067843806160145308672039236647314452825448974599553726514, 9053783100187331404171412931836385824515184111948767809413867380276679820649936390889334178130847227206809033839795986237398002538596094506862090790079370, 9819981805416004420939228090848428270273275315135728420672592580587456849727183520386676637280961225785470170028563422457684520710033836815957352641076656, 9099422152831608846445523884690686488729801810193179742928892208927495088869678721490572756945304623223593124143301850937075818103925239158419916092455832, 4423577950698286460626059676874777666863173105923291070406075608137350484265775306538076488967427903876263455370640828955831433683427915837489787681571104, 8756602113276572584327515563541785021885156596606825926384196017746588797560380054132379478133281808160622488923734499010823093056004931483459821079878584, 333126719900068218649984650898276581721876314324829547579365535415969541796750123020026055084245123391225191139147600319762747033880097952001528586613619, 7369702367521762727060275952126910129673008169982509956632808176742772738596846920777046904811187475688291150543995266534651134952974656031439986139640279, 2082799199108465498916580083784704029374798612211554268896160342266763106031569342542856087063877321514991732991254030062209651901743851475358154981091336, 8372258715871921984711084318371475306529362956110229335731717773030170640559593876258151246392797433258993127356247484151533876227372092507704978818762299, 11363939608613542162316118345022960798510877466323811731267325707620939632567030190215087390814765739175622571243027333413495842968402118709843171345209057, 3369719356483561545444940792209404189671394809909673685150113895593885526741601117980579861293222360031506015395948410107943057618465847851857629017021337, 3891507040973395370891557095282687378471080702589144672203318739556917713281013957214254764662956395750402238983505175330658129247692117209748428646988979, 4841437298113170733673811622315491999860260018197250450712753745063206624775276093082643398955242651840094676440631824725064149754775763109535437072598329, 5285163136257383594317771821481380172518348255388334236768828515368456565257150986678782783096670986106218219974638745661030434504183981097992990683389834, 7244116929896986409152403472296524576447775663505970094108789986102399989798939651538136211134583253147368128866311176849015387662060018429204373203882917, 7148506525887590405588915139400704234523641207593915972629337111053532230604043569291551513966362985886466513012302064587708085238549323074532238261929105, 9963569892216434098358658807251534860655159021141499917379945920250313978770919657650973084221026686207963270148354989236871921037008125320635811012429562, 4083231038473288903981795364527141098698470950916969669140777386661810905824053818094335667187521576982089894722121785936689098719720641047141775887885619, 2783788314467957767626366294911171310778689255399742535622249802506963607071489599250401846151948395505808426552847045942384003413532965612237381621803281, 9480491617103309579842630556508755350939077789372196051463181228494854894713982210404024973543443376963252760676054552352172548702910903277458343177156566, 3635429364237267158097629083423075371334216134912102395399443587668365674217468957824903594013330904699195406402865693233751839584364352027341368755854935, 10512981667787343474434123766399499997477931436681258061313671140829123476643229877218327020307534330562667672313170203756349669502382157014339683250964247, 9523260882926982368319161046924327498415945065442619931245103165210783676690576930491155298561540325169832005257298960723638671214008183533978109799943226, 8821529840762200230987342601372713314571576667046848202753835140978481743059025729341547664906327089784889179309805528352373783300015409440694498526802453, 3889011833429464584665382058129163296830025770986703817534403311481298622682949913268185847076341119959231106603819499559066684839808723190986345797294730, 6297833894994750508332367344339230109576795350737018003925458747380227258991762309042244773127464626474655334235127595180446112677686417583728900997000407, 1760580993763018538952442776136678506892159758376177668343574661932032517138571264664041285910343183567929592789229684581190582868840885043494028059145548, 1878349075050149698900567649931858097059976052165743708683218061733003305198473269136227375120889463183154947939758601333339524877223521121998759362189694, 1153881028955172548796413995891509447158808154001092914831702555572321224472153757269063442351457270745992276168611327881189379302990513606066403785037397, 1354358223850339886669589906081771646741444582933245990266741503788401468880301111475162932826849753299053269048808168611803883992487116859632452934337117, 2543377884923981424206502982559952756662944312446884306172193873371281396271026877421637622091903368826348654608641732603862340627036661889590442947531927, 11180070331634863421659326942954695855354411135806527591627639434182163636572574833713806184536037752699260808146541362264028865594295761466526576972822841, 1876044157639270095152731171181080065397794949339134253513517014818122966068827775030685216937939154007734964960492393433966781954313208696759345941096572, 10371430099994185472204699548408748044905813408067850241238238375805107275941350946511274188710313819596480556092765947208731899524618164738003278717300827, 11062773114779865261456167102313685917798343978846196446106343403832714394829785645472593554347810116685987941912922522999627132764032557020449831422203646, 10054072863070251371743882375307803093121932615191109140649824301459981488908599582245204018730319415235637278900632334082353686886849433443418405120003345, 11899130436532794506852251375418519516682965538478411626134165694080477666467891621837514385290629527954317340066073791969068384836623478676900518078492144, 3800279300556347862463102798984354928617374220518396876660726722145475720924549768399286700699390419995192400567218086102399360340221316874256916817269786, 1454947148349065856463673503402856502963580434612167600249860095631651888047663819039861980434456089663660230397115050479224033897345798648510977653561999, 2042470330662475573678989377098661429766022525672425312136276901388618218130280731245706624788119897930174958967595406027605059992960882778388524742722706, 1234466316196775376839414369545576872418957414559143172775038206383525000927730516952675718815486990989447248421995842318819533894488233801079449620739194, 9271029179787872970578591499796305060434913207434694840381590014888853464622436665409168097643583816031775853388603609072558269628091676020362129748533199, 4774006049363181543707013424043619624722110752475263766809952707315716132555412365539258234954892899737076119368604420130439903122534513533911949833743235, 623110557039911730730761834817043413841225662260405544713333348288325346206246696815306384870033925067051567408116233686600986656157873843902741673267719, 2069564772459439803719938786548180498693262686543372238863965419552080267984035520909550576789640672747255124939459370750757373319167495387965403174747875, 7009930087547627207463341159618322389574790808227199206178856629902591585272159790554326172427287447472376543486549214941749592725452858178087430338966770, 1949579642601550445176938316267401962008340575271606619055456197313569922910186952978532646082714333411065815595963623697989602613867680323849962329445328, 11473102336200916747844954216116155097772201756920091057358990979985199603080222884336057264448248212309791104537148189404198070915699582464690841703029405, 1149619512535738601211196767922880108257082979896142736945084581216263253245359015735818442104694183806457438676420946219043390360617857622541114743356625, 2728451593413071164353755775705571417160504975979542074503589190184105228575509775437861194810114128293804518550015503478674215376973558551801959937646423, 7348551730526134269844474344843320874593220152077150721293689908105376303123526293549457485523388054871559487100009886469120877549640875229125679910062900, 3980652757335090376997966895588998245582192975449382011909532268728853465365643067981211212812543763607316362585146788052930930128811388536930969342059979, 6027435835414897879227982281610804883898257447430395373655482693982905460207165696577025993816548891414301115457107032212880895723138070720653764226458649, 4935176743833633453254610852208777179108847720614483842026980697614902097198030677572108382421721697955784940692357115100326157600867058374344306754345335, 11380188380193543686552603209635990889129830058847840211484047666443921358239983121578443798338622961931123079081312386043081771886474890372630867350934523, 302987216748498327772215483663698180358086916475422751109337904686429747813576273027596185544180584711869887380062832681724092251772710838738355782182450, 811143629811997853354681978704899746490333224184384674857937414780703218886854529258709525197480284388948037380964255401025910568649894324446856632636592, 1912197174748050506709090151289853815332962565872780585712134602155119195678387971652769864474405775662028797382605103443081542911360430369860062463563893, 7291021864361814150510118731044864385204363543462889467753348110602838791870962501076106462997795429050059428094480878740697465713025274178808092567542212, 10470454741786470619594017615965958273332950307267197723934552764686005671405407576286379932688897606971338908824726882615845921705580372546409941175331037, 10181553581483434681781949968008741740061264764289389453230798650897899608022705896680919782100794147183000150901376195723151791411050033951290283786019977, 4258448968850182298881050787339455844058983218447958438955469542872009797484665292406639737321421521390721898187715427947024660792416519473288140642795272, 665126950818270052200683167429361468415424104577516367369570410295667254789977695909839338561441230603199269238113935924286711971526139364836371465706219, 5778603245576121661625744968094217982871142011195728227336698796177623583983932093421170892589521281377735094971545437150524492567792401307382096969659571, 9041169568361270824631079916805143667485107440403819673118982324331196605243710736252243694585470054722017092703832685314107118663876738553603881090379765, 8431011838980342769799616288411243768347548689119233157208349141492002200386542305507576767212556262869263553150643023836392407323405139253427329269366753, 8553706268926206579355730973791660092353863784751509372422644440790878753983928717623545538807559356829947772453965617876985508934310354104621043687587875, 6085701268163349706176631571460435367494457139886003603182612764217346443544862940087286859921717077555924920693652181971614741028158787295175507903805498, 8258027474231127629757419236092115748878321896277358390666269357460217304432166604893188156062734768320200621455881016473474077406349529408491337579070619, 217331193100935107368229358299722097535960890408924136554062054994468178500442930497503537444463416350072629320109394984373121597844999496670174734623901, 2615530940468368976430415020232745908496491487732778845358342691984855337966644151086347954705207248347432846086811344429509626971772151674138828479034407, 9960118652490492442626264557722940366236550945756405929154467678797068007119691196073161215135625171292061966393931591117075379707418718493207613281734128, 11883479956336240751620508565956647791575906464658043904847102787653384413540737438954113122506827116919889512801006983398795266218225358709015970474796209, 6152285147387893134308305627413716697035724893956326980324894196703036047676192332607132054448632203410660151536148743152836146945863580679445515576633313, 3087204177300702725903801544645938527062384514542059207838072215532344688679150676602943592074143292505943525492596313110869017003113441178426953737136320, 3757237385014563017951360020497685657808716037369726973798008159647192565347911506203832144238975399303316833405799994094392890515318875781045298318308651, 4174290778215893394677957264252893474678237242610027055294712957192373957647857206677916027186240373718927301908828095938016364127818908516883960408679053, 3748803300372512770866385104654922154470904205965026771319291886728164245927197518590781953321238268806575463481225816414707349949847056384636893007457721, 8034791604871081754393742620809047036249538255482307958153762277184366357510690505406748023739482129037447179804389566282826743874110772660769989993214140, 3647010606069854412551850026099222166287473701386238939796403152511252931742239857496752497988938568540423402614995772990646648482450299155961694607003150, 7806003716386838238944347755133023427857127411524200971653891977428639559902033732325074590574245675288515664031976582135757036821962959301244591185185836, 562123165970750916018523521274665280554207579150705704505991893938951905226252420500731924279293805682202106917135997949779952378356926548090996464183261, 10017225347599062251185778825601433952376955965940785104804810153710575101527601556073680944735221687545673318069762612385520657594749285103779943556203859, 11034121495368102793824149104460238045159050590264281508159716286752391769866225931653206949515929308837443453281068270892449202454489663082251103597579414, 1393756984740491625980042801423925923652694124513215825983448770637319821986725266222696274322782094225350417979883496797845297892870351570641796736429365, 3894233430764171021978166251097684223603711526228678617083090942307219791681305224470393733859806270321706191768448575635613494955972821171942019155576022, 5038527951098793046808059643802686028797058725403977118364390586086699770072322326201266880837915838731709376700104758344376656110092506598359671395752201, 9060876869828818448898852928359252910511417178029126609685283138824053964178895354434001568085161220224819591618740459295638904077934235248948941835465621, 1213284553098562533791961352335340028855774866108118873722749495214290050781676187996449060540282711962596299780371703456279525985966066640468482695387037, 9458104547506301061680450860449196327062010922531182109678643885802054328886528832025671540545677869267828858508683156236410816570296275103437238768105346, 10040054309381342148323598117554716384177326501952268974305486266186254782754797649740498654297024089530806441993039549600316509292085634401892126157777725, 2276927462611754797775080537543333252522721301228205773464099348201834053373985987075600025798802656981615274790492592630699705223288330490059041063861371, 11556387618265616484447806363024761014562917993396940861921977454240032115257066203918497109784248023494996743861411413922697151976403744004551897333587419, 9889259553854405678741508034426455964451772337345174356626295292298205602394952451135449468310970347202594428138122580204423010430923553611754754581066813, 7868119367862772149704911491499473892301419246641480987785226518125812257513053330287476237691301677750429689882087996945744571488509040895507410804183873, 11508002714196611606395235648239725836815494703321432338230737422973329400113158960696048138066722457604799065695576108785835121800314850011501948179743038, 10619053976801844838774915437764267913028709258001605358060442557707903258319114013374183185245387748828857617374056519624892149856249176171314055188176610, 201114180079927977316442203939901331713590891511639359168566794984727753167419382266922071288806881033628450144449718352186865225718313149653818834069046, 2190019323352646788039891107369737594638195699052572482340522786006963164742529768845844542244804881489436879523607337606022137474264008443779753796524324, 8994078524243073711186983175744445990617668670221279088217344780392324816856868718135841406968011026331111428134944981275543409823808438028673340180600361, 6533284532224150900776455616895133851200922713727543406843945334153660021579927964092546898761699064888593901931845363003227384361960946837683468780536186, 2900049820355985276596651350970201641910754953548208005611546296295010850954727597768565027123529585734943900449339351229077414389982399805851238537614728, 1005880173354315818215910490344169033790331192510294503391908220666556408162907870924876819721045548763740285934029434904116009033147300587812755020644144, 4429054545144565886236734238945768223549483534284407724097387393750175064863874353898699526770177337528927941471007913087408339512025427531471222352188598, 1285938780473331065877152772696342220861565553509736020905508189616388274844286113355903326372890919435684927488271321733483666403913781504709399179873478, 4159150342515004345261144815031223818657482125521340153877247384204372764658422497390807502845508068305611676258953299381534589394265725368949773437475664, 6576053057257377078820906137528289451395389785096859241738114487306122040955968123160457777083015623663591073050698149441279744926252972821085393074005333, 1378738974519907914149249225442590530115602428508531939708952252356105515635440550944988163800986109078848963934554394890364246215667532562795230121599389, 7530997786399165063460850133858426260366809458237917996971974273555406375229986518119701973615401731228222820028200964035186619721317616016026502478833825, 11371420348305380659910667615045099750167009510608284140696036190712641050353322760033584623633845930207049409269889108127939128060387804390620146397391005, 1406722966782959654726752002298837227734989674210304975712947321382221136256184622554373120305519551329471835182546103526035414290130221817761536912957815, 5758051768032037692984394788957178321113409313718798728174793963781211431894591306550233406904077870173730087305011890560525061122641038861810843224356132, 8375592464786617292066912032437580000072737070264996613521303068301506481293691262141521386631735548118808483692010811823373696054502206285565746271896624, 9625907624488495507256482396243781284122158414224512296964826016170998792851176860574572431609386683318175698871706280650379052753758050216492793527676711, 6077121672943640395277987812076880734154021482921918507769764026301498404990781416398855464804098928307277904801175596028922879606596629086997501055486057, 10938317339216777969309005338771442572315779569919804097449082853678275737846462681571834649938887549054815344340466436822987440964989371612298886307178807, 10266683373756264194186447415036327152615834323531488817490014686098650065547689251785469369732777946066207328196236032745636606950149996263882005409859068, 8427162246188488278348961620437187641769838216136551139544284534863388602834144470655144389658677000026573199236022413391175268573166429748835445411482658, 5717464833792973913319562092059026311110221447664287634460947091552289507231429020487445388817891744834227397036749333830249281129481189357590616693269535, 6388818019678030249042408529039004378409245276686402664154657767440109416203769306619383018656924981215056511384850552069151122129846170533781262522748912, 8058907696340647071107754590699635637331185362322234472755551469964443477794313636568312465633167061469262463754899612550256454461142900371675688057900157, 2650747991231745389958958911304551569853139256346350929307683312550450872545634238374819072544315331311085466011529241531384249952089342273098825176365572, 1795582396480470137527176284050645710132884527117486543781042591101197373917145734791679886383698097545356710330294515054344795103981124797423720912065788, 3052494597227398062986766578785396078205343919129668957958403133104993465160270251274373731365131485657799744057254790666584712327793616306716481909813582, 10125274627175346533926610345531381215155487891981319401506773913530942967488666544216346832250066513931463806744742351603339791989023259173734707387511997, 4905680337396302183882293200926552057123452464915594706482473859546742047185066973667304120028692253252104621914547092876701216499304788257812361954677824, 6788406585087459374008868766038523502662818879678483645630850915173078456811145138541048171988301388863438344097400187657040868535924005858978037488288657, 7987535346230340897650689272410982431583013895248851443363614799158842046321593827278953603690586270590653576153599776704899221489125881490179734913546180, 8668917726517583777868824898842831799933140622366155997499295528164949892618224804058794268889856672657589162182942581708183617533722037397902258002530895, 9655881640658079998109185276195348247028848976437592393891872239361101495373466311759967129786284249009503363294866452781555176175074514406596570855032885, 2243254436239103264649148279923978439297113563084946410869285186376198427685827681488062426734892419878174177945847856801922284074524600494618385520306773, 1370395445224087129252981159080973354642721975377684037523867648255769044694663959614655088192001525836838035825117690852844390101675187401512396538329654, 4656356018264588713126970771096540938860534429248562594457229986461965010462394518948976087164472484086375527533066794826178852068228773967304732965776642, 399595104452867236939487452774442870382730185220898620972098982860940846257358797206676225999483077781771650287888749325035861259261575979039839692262492, 6713094317103593591035416401288016658374527895040216154450781797709219652499792405003768632192355326331160459215694094704931391013755418496926953624700285, 1355018836283025742708846544067619719808654650957172598457945625126225415187893386450296522915846040605946952638451856428941453174991662324580099164411759, 8507312388193815039448605936770163526583300978792064893979853487224838987061551285368575763268148426788906220831176609730056029700392843807931184213757186, 2390915763452094063824684068272365759171848406604147217738985384144180505204991956237689281338506240218745984753955055494680218520622041831641785650384604, 5078775779350968152334228179925283860790974436015640731121894535584508877508449803458104048591112435333313257450614663322502851401769525184404429846816662, 1425564122989501182786990586943993793473032764333069827246235450438848390559886137108308116686220076822910325740852447268122991165884941809370496785162762, 3241557185717009458583866491496790535555873425192682369967408484532454523143616622825602173631183439057048896614677331862355583135778598344467632239621265, 11153886486498005363601960922463467341760192139357482824612504299845068740009509797094949564531439906328941599335110459532334944225340180499338091922473414, 4750339554868896196047869851866222454424215998958859589162250220636186354219417775182461279765710413851720284554693629603182622333067705806099109845670979, 3931689678588961771487503092252686799044554895341999274823183685441609027829749616204909660105256179107533811726668939651921392965108014523612326438454763, 11187638131483583043295930937674327604068710567565996413543552914014991119808667664531916767958198065684486668485361079752275150252491497563209373369489026, 7951154730710536892216170200330921561976344676074745084927394513732709335427919379562575393123463516219422246176438982950570737516171571233794420196666886, 1672105185912794004124818038268311924305321636283766784591904708276129195324814049081791432685559117731983780119720703133146952521104542489075767958624517, 5961298351722930109958690694504209488357119642165137305859737050609557432218480991926525556188466406512020308464626017185419266848018117342271389200068990, 2614791092577719712081127427916398870473955060880008274836166534656201118982263931935400058828969825633552149733933209355913619475322640831081073991096019, 7585989640990063110599210948433357802190782090362288612653066977287873913659636348347931158157250612988653924395845263983389111801086659635847485205155792, 4431808088762149440258933713632651937723965113354466368892895978425300447231680836376644074059558059224711681073893610493216931561336057461872809335815419, 7803424065303659891769090326828845084396802995889011459387130902032712116540019926662218626165288561308869447406929573895286984344209221478683590810037836, 11333465632518722706044944069452368469429296564009722650087924377614457953420253199332209735022605809814036297664863446336960387614479076573269329031750987, 9015046896873406255435786931788379566338694649982989302643634589663708173842716795343443511577662905506449004999936754531825070165614729532129356052128575, 11605497784351360234525700004313542522479606465344927573861628615111353117631482629714381940820675064966051516229437449884465509791106407640656382300239363, 3618112506546716532317705417297714426926133719388251635042604657890418824749256430743547870156065078623067964196242241099881802766943775618184489388984614, 2961952780271618644341511265207741924062876582075139491069703688326317506273106501877576791814338926919371801113717337612487657355874282727562430403186215, 1959860827301876193534452473130565833580576931994622570402458534809572211163546248253809832512083364950948854715506995993724605349255618000388575898620819, 9522502213326349795872611375564340926065360170250620972307193996920225151270140085190219961878238320516211124175040938476084033356336641564459714925394556, 6822893241651652944802867129943790227179941374865599671130155956732332020891862363512840518812230889010452540282244203720602490116223523996809092557679690, 6857422579671283864309505737866570751014092920497487113429028085441724197811232340915656160313885768238889308579776669697849014732800696848033650297379889, 4018143097421566596818458699109838662675933060812340723092984957628021473520663072311941893877060261979047503976803401869798199151609532367574647600368003, 6194607058501590733164566924844005093710661715500276174295952934514177124661068706559499237499314609830082367219229089919247640185368549101514384767175538]
cipher = 1010137180395931262752398681857488526009620802401167859543237801022630704004744078316133982172587856565491470015404484864890095896964409269987597733836611756
攻略方針
problem.py を 見て「格子」のニオイがしたので後回しにしたのですが、よくよく読んでみると「Merkle–Hellman knapsack 暗号」っぽかったので、以前読ませていただいた Xornet さんの記事（https://project-euphoria.dev/blog/10-lll-for-crypto/ ）にあった、「NITAC miniCTF 3rd - knapsack」を解く際に使用したというスクリプトを利用することにしました。
攻略＆フラグ
前記スクリプトで、ct と pubkey の値を変えて SageMath に投げたらフラグをゲットできました。
ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}
2-6. p-8_RSA (Crypto, 387点, 想定難易度 = Hard)
It looks someone is encrypting it with RSA.
problem.py
from Crypto.Util.number import *
from random import getrandbits
from os import urandom
from flag import flag
def gen_primes(bits, e):
q = getStrongPrime(bits)
p = q
while True:
p = p-8 # p-8
phi = (p - 1) * (q - 1)
if isPrime(p) and GCD(phi, e) != 1:
break
return p, q
flag = flag.encode("utf-8") + urandom(64)
flag = bytes_to_long(flag)
e = 17
p, q = gen_primes(512, e)
n = p * q
print("n =", n)
print("e =", e)
print("c =", pow(flag, e, n))
output.txt
n = 169221770188000341507764005330769042705223611712308424479120192596136318818708135716157255550936563268500310852894489839470320516645317338473018150885997977008925839939560590924435380239519554475266121835753044660177349444503693993991253475530436734034224314165897550185719665717183285653938232013807360458249
e = 17
c = 100233131931360278332734341652304555814094487252151131735286074616555402795190797647001889669472290770925839013131356212574455274690422113278015571750653365512998669453161955302008599029919101244702933443124944274359143831492874463245444294673660944786888148517110942002726017336219552279179125115273728023902
攻略方針＆秘密鍵（p,q）のリーク
$p$ と $q$ は極めて近いので、Fermat 法で容易に計算できてしまいます（スクリプトは省略）。
p= 13008526826201356667891590694678121516071641430494347349438757349219893000439927852950504383765791466428599814640460028507882213264934492728368742844741541
q= 13008526826201356667891590694678121516071641430494347349438757349219893000439927852950504383765791466428599814640460028507882213264934492728368742844727189
しかし、$e$ は Totient の約数であるため、
$ed\equiv1\mod{(p-1)(q-1)}$
を満たす$d$はありません。
そこで、$\mod{p}$と$\mod{q}$で分けて考えて、最後に中国式剰余定理で $\mod{n}$ に戻すことを考えます。
$p-1$ と $e$ は互いに素なので通常の RSA 復号と同様 $ed \equiv 1 \mod{(p-1)}$ となる $d$ を使って $c^{d} \mod{p}$ を計算します。
$q-1$ は $e$ を割るので、$\mod{q}$ では $c$ の $e$ 乗根を計算しますが、複数出てくるので総当たりで中国式剰余定理にあてはめフラグに該当するものを見つけます。
ソルバ＆フラグ
solve.sage
from Crypto.Util.number import long_to_bytes, inverse
#######################################################################
# Params:
N = 169221770188000341507764005330769042705223611712308424479120192596136318818708135716157255550936563268500310852894489839470320516645317338473018150885997977008925839939560590924435380239519554475266121835753044660177349444503693993991253475530436734034224314165897550185719665717183285653938232013807360458249
e = 17
c = 100233131931360278332734341652304555814094487252151131735286074616555402795190797647001889669472290770925839013131356212574455274690422113278015571750653365512998669453161955302008599029919101244702933443124944274359143831492874463245444294673660944786888148517110942002726017336219552279179125115273728023902
#######################################################################
#by Fermat's method:
p = 13008526826201356667891590694678121516071641430494347349438757349219893000439927852950504383765791466428599814640460028507882213264934492728368742844741541
q = 13008526826201356667891590694678121516071641430494347349438757349219893000439927852950504383765791466428599814640460028507882213264934492728368742844727189
assert p*q == N
#but ... e mod q-1 == 0!
phi = p-1
dx = inverse(e, phi)
x =pow(c,dx,p)
assert(pow(x,17,p) == c % p)
F = GF(q)
R.<y> = PolynomialRing(F)
f = y^17 - c
ys = []
for i in range(len(f.factor())):
y = (-1 * f.factor()[i][0].constant_coefficient()) % q
assert(pow(y,17,q) == c % q)
ys.append(y)
mods = [p, q]
for y in ys:
vs = [int(x), int(y)]
pt = crt(vs, mods) % N
if(b"ctf4b{" in long_to_bytes(pt)[:-64]):
print(long_to_bytes(pt)[:-64].decode())
ctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}