前置き

SECCON Beginners CTF 2021 運営の方々、参加者の皆さんお疲れさまでした。楽しかったです！
crypto の6問についてwrite-upを載せます。

simple_RSA
Logical_SEESAW
GFM
Imaginary
Field_trip
p-8RSA

simple_RSA と Imaginary は、チームメイトが解いてくれました。

simple_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

公開鍵のnが2046ビットより大きいのに対し、暗号鍵eは3、flagも375ビットとどちらも小さめです。これは、暗号文cの3乗根を計算するだけでフラグが得られます。

solver.py

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot

c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613
m,b = iroot(c,3)
print(long_to_bytes(m))
# ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}

Logical_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進数に変換されて、同じビット長のkeyが用意されます。
乱数nを生成して0.5より大きければ、フラグとkeyの1ビットずつについてAND演算が行われる、というものです。そして、ひとつのkeyを使って16通りの暗号文を生成しています。暗号化に乱数を用いているので、各暗号文は異なっています。

AND演算の出力が1であるときにはフラグとkeyの両方が1である必要があるため、暗号文に偏りが生じます。この性質を利用すると解けました。

solver.py

from Crypto.Util.number import long_to_bytes
cipher = ['11000010111010000100110001000000010001001011010000000110000100000100011010111110000010100110000001101110100110100100100010000110001001101000101010000010101000100000001010100010010010001011110001101010110100000010000010111110000010100010100011010010100010001001111001101010011000000101100', '11000110110010000100110001000000010001001111010010000110110000000110011010101110011010100110000010100110101100000100000000001110001001001000101000001010101001100000001010101010010110001001110001101010110100000110011010010110011000000100100011010000110010001001011001101010011000001101100', '11000010110010000100110001101000010001001111001000000110000100000110011000111110010010100110000000101110101101100000000010010110001001101000101010000010101000100000001000101110000010001001111001101010110100000010011010010110011000100000100011010010100010001001111001101010011000001101100', '11000110110010001100110000101000110001000111000000000110000000000110011010101110011000100110000010100110101101100100100010000100101001001000101010000010101000100000001010100110010010001001110001101010110000000110000010110110000000000000100011010010110010001011011001101010001000000111101', '11000110100010001100110000000000010001000111001010000110110100000110011010111110001010100110100011101110101110100010000000110100001001101000101010000010101001101000001000101000010010001001111001101010110000000010000010111110000000000010000011010010100010001001011001101010011000001111101', '11000010110010001100110001001000010001000011000000100110000000000110011010101110000010100110100011100110101110100010000000101100101001101000101010000010101001101000001010100010000010001011111001101010110100000110001010010110001010100100000011010010110010001011111001101010011000000101100', '11000110110010000100110001101000110001001011010000100110110000000110011000101110010000100110100001100110100110000000100010000110101001001000101010000010101001100000001000101110010010001011111001101010110000000010001010110110001010100110000011010000110010001011111001101010011000000101100', '11000010110010000100110000100000010001000111011000100110100000000110011000111110000010100110000001101110101111100100000010111110001001001000101000001010101001101000001000101010000110001011110001101010110000000110001010011110000010100010100011010010110010000011011001101010001000000111100', '11000010101010000100110001001000010001000011000000100110010000000100011000111110011000100110000001100110100101000010000000011100101001101000101000001010101001101000001010101110010110001001110001101010110000000010010010110110011000000010100011010000100010001011111001101010001000000101100', '11000010101010001100110000100000010001001111001010000110000000000100011010101110011000100110000011100110100111100110100000000110001001001000101010000010101000100000001000101100010010001011110001101010110000000110011010010110011010000000000011010010100010001011011001101010011000001101101', '11000010101010001100110001000000010001001011010010000110010100000100011000111110011000100110000010100110100111000100000000000100101001101000101010001010101000100000001000100000000110001001111001101010110000000110011010010110000010000100100011010000110010000011011001101010001000001101100', '11000110101010001100110001000000110001001111001010000110110000000110011010101110011000100110100001100110101111000100100010011110101001001000101010001010101000101000001000101100000110001011111001101010110100000010011010011110001000000100100011010010100010000001011001101010011000001111100', '11000110100010001100110001000000010001001011011010100110000000000100011000101110001000100110100001101110101101000110100010001100101001001000101010000010101000100000001010101100000010001001111001101010110100000110011010010110010000100110100011010010110010001001111001101010011000001101101', '11000110101010000100110000000000010001001111001010100110100100000100011010111110001000100110100001101110101100000000100000111110001001101000101000001010101001101000001010100110010010001011110001101010110100000110000010010110001010000010100011010010110010001001011001101010001000000101100', '11000010101010000100110000000000110001001011011010100110110000000110011000101110010010100110100000100110101111000010000000100100001001001000101000001010101001100000001000100000000010001011110001101010110000000010011010011110001010000000000011010010100010001001011001101010001000000101101', '11000110101010001100110001000000110001001111011000000110010100000100011000101110001010100110000001101110101110000100100000101110101001101000101000000010101000100000001010101010000010001011110001101010110000000010000010010110001000100100100011010000100010000001011001101010001000001111101']

flag = ""
len_flag = len(cipher[0])

for k in range(len_flag):
    t = 0
    for i in range(16):
        t += int(cipher[i][k])
    if t >= 1:
        flag += "1"
    else:
        flag += "0"
#     print(t,end=' ')

print(long_to_bytes(int(flag,2)))
# ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}

GFM

問題

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]

この問題では、有限体の要素を持つ行列が扱われています。
コードはSageMathのものですね。

enc = key * M * key という行列が与えられているので、
M = key^(-1) * enc * key^(-1) を「有限体上で」計算するとMが得られます。ここで、key^(-1)は行列keyの逆行列を表しています。SageMathなら、有限体や逆行列の計算が楽にできます。

solver.sage

p = 331941721759386740446055265418196301559
SIZE = 8
MS = MatrixSpace(GF(p), SIZE) # 有限体GF(p)上で、8×8の行列を扱います、という宣言

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]]
key = MS(key)
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]]
enc = MS(enc)

M = key^(-1) * enc * key^(-1) # 両側から逆行列列を掛ける

flag = ""
for i in range(SIZE):
    for j in range(SIZE):
        if M[i,j] < 0xff:
            flag += chr(M[i,j])
        else:
            break
print(flag)
# ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}

Imaginary

問題

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()

netcatを使ってサーバに接続する問題です。
サーバではpythonの辞書型で複素数が作成・保存されます。また、saveしたデータはAES-ECBで暗号化してExportする機能と、暗号文をImportする機能が備わっています。

コードを読むと、辞書型の変数numbersに「1337i」というキーがあるとフラグが得られるようです。しかし、サーバの機能では、「a + bi」という形のキーしか作れません。しかし、AESのECBモードでは16バイトごとに暗号化が実施されることを利用して、「1337i」というキーを持つデータを作成できます。

一例ですが、平文で考えると、
{"1234567 + 0i": [1234567, 0], "0 + 0i": [0, 0]}　の前半32バイト目以前と、
{"12345 + 0i": [12345, 0], "0 + 1337i": [0, 1337]}　の33バイト目以降がつながった、
{"1234567 + 0i": [1234567, 0], "1337i": [0, 1337]}　という平文を得よう、という試みです。

サーバに接続してやってみます。
１回目、{"1234567 + 0i": [1234567, 0], "0 + 0i": [0, 0]} の暗号文を作ります。

user$ nc imaginary.quals.beginners.seccon.jp 1337
Welcome to Secret IMAGINARY NUMBER Store!
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 1234567
Imaginary part> 0
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 0
Imaginary part> 0
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 2
--------------------------------------------------
1234567 + 0i: (1234567, 0)
0 + 0i: (0, 0)
--------------------------------------------------
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 4
{"1234567 + 0i": [1234567, 0], "0 + 0i": [0, 0]}
Exported:
f427c0cb77b86e5f84614d6ef8d50db7700a22e238f8065ff34578d4cad62cc6aefae56d528b5b6c1ca7dd8b9cbe47a78db4341b6d2b363abdc9d13de3042f42

2回目、{"12345 + 0i": [12345, 0], "0 + 1337i": [0, 1337]}の暗号文を作ります。

user$ nc imaginary.quals.beginners.seccon.jp 1337
Welcome to Secret IMAGINARY NUMBER Store!
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 12345
Imaginary part> 0
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 0
Imaginary part> 1337
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 2
--------------------------------------------------
12345 + 0i: (12345, 0)
0 + 1337i: (0, 1337)
--------------------------------------------------
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 4
{"12345 + 0i": [12345, 0], "0 + 1337i": [0, 1337]}
Exported:
0c94f7bccc57cd9a7a9ffd281cb73b79d584dcf52bfddd298f9cd7b35825dc54634842688c2ca7eaa5a9f91a03cb0b3af36e1309837f85a8ef0b81de1e9a6bb2

ふたつの暗号文を組み合わせて、「1337i」をキーに含む暗号文を作ります。

# {"1234567 + 0i": [1234567, 0], "0 + 0i": [0, 0]} のExport
enc0 = 0xf427c0cb77b86e5f84614d6ef8d50db7700a22e238f8065ff34578d4cad62cc6aefae56d528b5b6c1ca7dd8b9cbe47a78db4341b6d2b363abdc9d13de3042f42

# {"12345 + 0i": [12345, 0], "0 + 1337i": [0, 1337]} のExport
enc1 = 0x0c94f7bccc57cd9a7a9ffd281cb73b79d584dcf52bfddd298f9cd7b35825dc54634842688c2ca7eaa5a9f91a03cb0b3af36e1309837f85a8ef0b81de1e9a6bb2

enc0 = long_to_bytes(enc0)
enc1 = long_to_bytes(enc1)
data = enc0[:32] + enc1[32:]
print(format(bytes_to_long(data),'x'))
# f427c0cb77b86e5f84614d6ef8d50db7700a22e238f8065ff34578d4cad62cc6634842688c2ca7eaa5a9f91a03cb0b3af36e1309837f85a8ef0b81de1e9a6bb2
# これをImportする

1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 3
Exported String> f427c0cb77b86e5f84614d6ef8d50db7700a22e238f8065ff34578d4cad62cc6634842688c2ca7eaa5a9f91a03cb0b3af36e1309837f85a8ef0b81de1e9a6bb2
Imported.
--------------------------------------------------
1234567 + 0i: (1234567, 0)
1337i: (0, 1337)
--------------------------------------------------
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 5
Congratulations!
The flag is ctf4b{yeah_you_are_a_member_of_imaginary_number_club}

おまけ

ローカルで確認。

check.py

import os
import json
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import bytes_to_long

key = os.urandom(16)
cipher = AES.new(key, AES.MODE_ECB)

m0 = {"1234567 + 0i": [1234567, 0], "0 + 0i": [0, 0]}
m1 = {"12345 + 0i": [12345, 0], "0 + 1337i": [0, 1337]}

dump = pad(json.dumps(m0).encode(), AES.block_size)
enc0 = cipher.encrypt(dump)

dump = pad(json.dumps(m1).encode(), AES.block_size)
enc1 = cipher.encrypt(dump)

print("enc0 :",hex(bytes_to_long(enc0)),len(enc0))
print("enc1 :",hex(bytes_to_long(enc1)),len(enc1))

c = enc0[:32] + enc1[32:]
print("c :",hex(bytes_to_long(c)))

m_ = cipher.decrypt(c)
pt = unpad(m_,AES.block_size)
pt = json.loads(pt.decode())
print(pt) # {'1234567 + 0i': [1234567, 0], '1337i': [0, 1337]}
if '1337i' in pt: 
    print("OK")

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.py

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

ナップサック暗号のようです。
PlaidCTF CTF 2015のLazy が似た（というか同じ？）問題です。
PlaidCTFの問題の解説（Kimiyukiさんの記事やkatagaitaiのスライド）が参考になります。攻撃の名前はCLOS法というらしいです。LLLアルゴリズムを利用するのですが、SageMathだと簡単に（中身を知らなくても）実行できます。LLLの用途などについては、xornetさんが資料にまとめてくださっています。

あと、CryptoHackにも似た問題があったと思います。
ソルバーはKimiyukiさんの記事を参考にしています。（ほとんどそのまんま）

solver.sage

from Crypto.Util.number import long_to_bytes
from output import *
public_key = pub_key
encrypted = cipher

n = len(public_key)
density = n / float(log(max(public_key),2))
assert(density < 0.94) # CLOS method

I = matrix.identity(n)
I2 = 2*I

bottom_row = matrix(ZZ,1,n,[-1] * n)

M = 100
right_column = matrix(ZZ,n,1,[i * M for i in public_key])

B = matrix(ZZ, n + 1, n + 1)
B.set_block(0, 0, I2)
B.set_block(n, 0, bottom_row)
B.set_block(0, n, right_column)
B.set_block(n, n, matrix(ZZ,1,1,-M * encrypted))

B_LLL = B.LLL()

for row in B_LLL:
    if all(x in [1,-1] for x in row[0:n]) and row[n] == 0:
        row0 = row

m = ''
for i in range(n):
    if row0[i] == 1:
        m += '1'
    elif row0[i] == -1:
        m += '0'
        
print(long_to_bytes(int(m,2)))
# ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}

p-8RSA

問題

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

RSA暗号の問題です。
ひとつめのポイントは、素数p、qの作り方です。この問題では、はじめにqを作り、pはqから8ずつ引いていく、という作業を行っています。
この作り方だと、pとqの値が近くなり、フェルマー法という方法でn(=p*q)の因数分解ができてしまいます。（参考）

ふたつめのポイントは、暗号鍵e とphi(=(p-1)(q-1)) が互いに素ではない、という点ですね。互いに素ではないということは、最大公約数が1ではないということです。ここが互いに素であれば普通に復号鍵が算出できるのですが、今回はそうはいきません。

解法は考えてもわからなかったのでググりました。
私が参考にしたのはこちらです。原理をいまひとつわかってないですが、記事のとおりに実装したら解けました。暗号鍵とphiが互いに素でない場合、復号結果が一意に定まらないのですが、e個（今回は17）通りに絞れるということのようです。

CTF終了後にツイッターでみかけたのですが、だこつさんの記事のほうが丁寧に解説されています。

solver.py

import gmpy2
from Crypto.Util.number import long_to_bytes

# output.txt
n = 169221770188000341507764005330769042705223611712308424479120192596136318818708135716157255550936563268500310852894489839470320516645317338473018150885997977008925839939560590924435380239519554475266121835753044660177349444503693993991253475530436734034224314165897550185719665717183285653938232013807360458249
e = 17
c = 100233131931360278332734341652304555814094487252151131735286074616555402795190797647001889669472290770925839013131356212574455274690422113278015571750653365512998669453161955302008599029919101244702933443124944274359143831492874463245444294673660944786888148517110942002726017336219552279179125115273728023902

def fermat_factors(n): # https://tex2e.github.io/blog/crypto/fermat-factorization-method
    assert n % 2 != 0
    x = gmpy2.isqrt(n)
    y2 = x**2 - n
    while not gmpy2.is_square(y2):
        x += 1
        y2 = x**2 - n
    factor1 = x + gmpy2.isqrt(y2) # a = x + y
    factor2 = x - gmpy2.isqrt(y2) # b = x - y
    return int(factor1), int(factor2)

p,q = fermat_factors(n)
p,q = q,p # アサーションが出たら、pとqを入れ替えてみる

# https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e
assert((p - 1)%e == 0)
assert((q - 1)%e != 0)
assert((p - 1)%(e**2) != 0)

lamb = (p-1)*(q-1) / gcd(p-1,q-1)
k = 2
L = pow(k,lamb/e,n)
d = pow(e,-1,lamb/e)

for i in range(e):
    m = (pow(c,d,n) * pow(L,i,n)) % n
    m = long_to_bytes(m)
    if m[:3] == b'ctf':
        print(m)
# ctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}

あとがき

大変勉強になりました。
よく理解しないまま解いていることが多いので、今後はもう少し掘り下げていきたいなと思います。あと、ほかの人が解いているのをみててCrypto以外のジャンルも楽しそうだと思ったのでちょいちょいやっていきたい。

記事にわからないところ、おかしいところあったらご指摘ください。
おしまい！