🎃
KnightCTF 2023 に参加しました
結果
チーム参加。125位/848チーム
解けた問題
Cryptography
- Xorathrust[345 solves]
- Factorie[505 solves]
- I Love Pi[221 solves]
- Jamal[142 solves]
- Encode Mania[186 solves]
- Toddler RSA[106 solves]
Basics
- KnightCTF Discord Server[665 solves]
Xorathrust [345 solves]
Read the script and solve the problem.
Demo Flag: KCTF{Fl4g_H3r3}
encrypt.py
def main():
flag_enc = ""
with open("flag.txt", "r") as infile:
flag = infile.read()
flag = list(flag)
for each in flag:
each = chr(ord(each) ^ 0x66)
flag_enc += each
with open("flag.enc", "w") as outfile:
outfile.write(flag_enc)
if __name__ == "__main__":
main()
-%2 S9R9RS9V
単純に 0x66 でまたXORすればよい
pt = ""
with open("flag.enc.txt", "r") as f:
enc = f.read()
enc = list(enc)
for each in enc:
each = chr(ord(each) ^ 0x66)
pt += each
print(pt)
KCTF{ju5t_4_b45ic_x0r}
Factorie [505 solves]
Have you ever heard of prime factors? The file challenge.txt contains a number that has two prime factors. Can you find them?
Demo Flag: KCTF{small-number_big-number}
n: 2174096211032823084932239036566496093206280423
SageMath に投げる
KCTF{39434538531451803895327_55131777675015246472249}
I Love Pi [221 solves]
Isaac Newton left me this piece of code and a message. Can you help me decode this...
Demo Flag : KCTF{FL4G_H3R3}
i_love.py
import base64
lengths = [--REDACTED--]
flag = "KCTF{*******************************}"
# len(lengths) = 10
# len(flag) = 39
s = 0
encoded_flag = ""
for l in lengths:
seg = flag[s:s+l]
for _ in range(len(seg)):
seg = base64.b64encode(seg.encode('ascii')).decode('ascii')
s+=l
encoded_flag += seg
print(encoded_flag)
encoded_flag.txt
VXpCT1ZRPT0=Rg==V2xod1UxcHNWa0pRVkRBOQ==MQ==VmpCb2QxVXhjSE5UYTFaV1ZrUkJPUT09Vm0wd2QyVkhVWGhUV0doaFUwVndVRlp0TVZOV01XeFZVbTVrVlUxV2NIbFdNalZyVmpKS1NHVkliRmRpVkVaSVZtMTRTMk15VGtWUmJIQk9VakF4TkZkWGRHRmtNRFZ5VFZWV2FHVnFRVGs9U0RNPQ==Vm1wQ1UxRXlTbkpOVldSVFYwZFNjVlJVU1RSUFVUMDk=VjFSS2QxWXhjSEpPVldSYVpXcEJPUT09VGtac09RPT0=
配列 base64 を復号する問題だということがわかる。
適当に == があるところまでで区切って復号化してみると、
length = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
ということがわかる。
VXpCT1ZRPT0=, 3, "KCT"
Rg==, 1, "F"
V2xod1UxcHNWa0pRVkRBOQ==, 4, "{4_P"
MQ==, 1, "1"
VmpCb2QxVXhjSE5UYTFaV1ZrUkJPUT09, 5, "_4_D4"
Vm0wd2QyVkhVWGhUV0doaFUwVndVRlp0TVZOV01XeFZVbTVrVlUxV2NIbFdNalZyVmpKS1NHVkliRmRpVkVaSVZtMTRTMk15VGtWUmJIQk9VakF4TkZkWGRHRmtNRFZ5VFZWV2FHVnFRVGs9, 9, "Y_K33P5_7"
U0RNPQ==, 2, "H3"
Vm1wQ1UxRXlTbkpOVldSVFYwZFNjVlJVU1RSUFVUMDk=, 6, "_H4CK3"
VjFSS2QxWXhjSEpPVldSYVpXcEJPUT09, 5, "r5_4W"
VGtac09RPT0=, 3, "4Y}"
KCTF{4_P1_4_D4Y_K33P5_7H3_H4CK3r5_4W4Y}
Jamal [142 solves]
My friend Jamal has encrypted the flag and sent me the files. He now wants me to decrypt it and find out. Can you do it for me, please?
Demo Flag: KCTF{f4k3_fl4g}
jamal-encrypt.py
from random import randint, seed
def is_prime(n):
if n == 2 or n == 3:
return True
if n % 2 == 0 or n < 2:
return False
for i in range(3, int(n**0.5)+1, 2):
if n % i == 0:
return False
return True
def get_prime(n):
while True:
p = randint(2**(n-1), 2**n)
if is_prime(p):
return p
def encrypt(ch, g, p, y, k):
pt_int = int.from_bytes(ch.encode(), "big")
c1 = pow(g, k, p)
c2 = (pt_int * pow(y, k, p)) % p
return c1, c2
def main():
flag = open("flag.txt", "r").read().strip()
x = randint(2, 9999999)
p = get_prime(43)
g = get_prime(43)
while g == p:
g = get_prime(43)
if g > p:
g, p = p, g
y = pow(g, x, p)
with open("flag.enc", "w") as out:
for ch in list(flag):
# encrypt
k = randint(2, 9999)
c1, c2 = encrypt(ch, g, p, y, k)
out.write(f"{c1},{c2}\n")
with open("key.pub", "w") as out:
out.write(f"p: {p}\n")
if __name__ == "__main__":
seed(0)
main()
jamal-flag.enc.txt
2542674357061,3229421908786
1047095110514,2703124715302
2241080680361,339282920484
2877082899121,213437588357
2962454333590,1146622182354
8667422468,2914668005810
3283797690288,5668747940970
92336276716,2578935770315
280618016374,4820189175032
1209866491592,146344916624
2253881281576,2448560213475
1161992879414,1674301627359
4818900557459,4874289912091
1794902833332,3885572444087
3082175285512,235300300457
1157352410430,3391910550439
1975682514838,4412581570619
940190944451,4668208507929
4892987552563,3969703431560
861276404486,4681646838677
5308919438905,740205209430
4882067017820,5684832423565
832490479211,3882413987731
2768698738377,2559643212287
4799150729489,2715004149410
2400910224808,2411154824523
871309115691,312836731476
32734373338,5274112237786
2427518930772,3618374377486
3075900055786,2047586052701
5395051057487,427396164824
663270611761,2916443609523
p: 5690411473163
シードが固定されているので、平文の各文字を brute-force すればよい。
seed(0)
x = randint(2, 9999999)
p = get_prime(43)
g = get_prime(43)
if g > p:
g, p = p, g
y = pow(g, x, p)
flg = []
for i in range (32):
k = randint(2, 9999)
c1 = cs[i][0]
c2 = cs[i][1]
for num in range (128):
g1, g2 = encrypt(chr(num), g, p, y, k)
if c1 == g1 and c2 == g2:
flg.append(chr(num))
print(''.join(c for c in flg))
KCTF{h4v3_y0u_h34rd_0f_3l64m4l?}
Encode Mania [186 solves]
Encoding random stuffs is so cool! I just want to encode it over and over and over again ...
Demo Flag: KCTF{fl4g_h3r3}
encode_mania.py
import base64
from random import randint
flag = "kctf{************}"
def encrypt(s, option):
if option == 0:
ret = base64.b64encode(s)
elif option == 1:
ret = base64.b32encode(s)
elif option == 2:
ret = base64.b16encode(s)
else:
ret = base64.b85encode(s)
return ret
encrypted_flag = flag.encode('utf-8')
for _ in range(12):
option = randint(0, 3)
encrypted_flag = encrypt(encrypted_flag, option)
with open("encode_mania.txt", 'w') as f:
f.write(encrypted_flag.decode())
encode_mania.txt
GUZDGMRUIQ3TENJYGMYTOMBUHA2TSMZRGM4TGOBVIE2DKNRUGZATIQRXIEZTSNRRGUZDGMRUIU3DMNRWGQ3TKMRUHA2TSNZZG4ZTERRVHE3EENRUGZATKOBTGM3TQNRZGUZDGMRUIUZTMNCCGMYTMOBUHA2TSMZRGM4TGOBVIE2DKNRUGZATIQRTGEZTSNRRGUZDGMRUIU3DONCEGQ3DOMBUHA2TSNZZG42DMNRVG42TKNRUGZATIQRXIEZTSNSBGUZDGMRUIQ3TENJQGMYTOMBUHA2TSMZRGM4TGOBVHEZTANRUGZATMNJWHE3TINJZGUZDGMRUIU3DMNRWGQ3TKNRUHA2TSNZZG4ZTERRVIE2DKNRUGZATKOBTGM3TQNSCGUZDGMRUIUZTMNCCGMYTOMBUHA2TSMZRGM4TGOBVIE2DKNRUGZATIQRXIEZTSNJZGUZDGMRUIU3DMNRWGQ3TKMRUHA2TSMZRGM4TGOBVHE2TKNRUGZATIQRXIEZTSNRRGUZDGMRUIQ3TENJYGMYTMQZUHA2TSNZZG42DMNRVG42TKNRUGZATIQRTGEZTSNRZGUZDGMRUIQ3TENJQGMZDKNRUHA2TSMZRGM4TGOBVHEZTANRUGZATKOBTGM3TQNSBGUZDGMRUIU3DMNRWGQ3DOMBUHA2TSNZZG42DMNRVHE2TKNRUGZATIQRTGEZTSNRRGUZDGMRUIU3DMNRWGQ3TKMRUHA2TSNZZG4ZTERRVG43EENRUGZATKOBTGM3TQNSDGUZDGMRUIU3DMNRWGQ3DMQZUHA2TSMZRGM4TGOBVHE2TKNRUGZATKOBTGM3TQNRYGUZDGMRUIU3DMNRWGQ3TMNBUHA2TSNZZG42DMNRVHEZTANRUGZATIQRXIEZTSNSBGUZDGMRUIQ3TENJYGMZDIRJUHA2TSNZZG4ZTERRVHEZTANRUGZATIQRXIEZTSNRRGUZDGMRUIU3DMNRWGQ3TIRJUHA2TSMZTGZDDOMRVG42DKNRUGZATKOBTGM3TQNSDGUZDGMRUIQ3TENJQGMZDKMRUHA2TSMZRGM4TGOBVG43EENRUGZATKOBTGM3TQNSDGUZDGMRUIQ3TENJQGMZDIRJUHA2TSNZZG4ZTERRVG42DKNRUGZATMNJWHE3TINKBGUZDGMRUIQ3TENJQGMYTOMBUHA2TSNZZG4ZTERRVIE2DKNRUGZATIQRTGEZTSNSBGUZDGMRUIU3DMNRWGQ3TKMRUHA2TSNZZG42DMNRVHEZTANRUGZATIQRXIEZTSNSCGUZDGMRUIU3DMNRWGQ3TINRUHA2TSMZTGZDDOMRVG42DKNRUGZATIQRXIEZTSNRYGUZDGMRUIU3DMNRWGQ3DMOBUHA2TSNZZG42DMNRVG43EENRUGZATKOBTGM3TQNSCGUZDGMRUIQ3TENJQGMYTOMBUHA2TSMZRGM4TGOBVIE2DKNRUGZATIQRXIEZTSNRZGUZDGMRUIU3DMNRWGQ3DOMBUHA2TSMZRGM4TGOBVHE2TKNRUGZATKOBTGM3TQNRZGUZDGMRUIQ3TENJQGMZDKMRUHA2TSNZZG4ZTERRVHEZTANRUGZATIQRTGEZTSNKBGUZDGMRUIQ3TENJQGMZDIRJUHA2TSNZZG4ZTERRVG43EENRUGZATKOBTGM3TQNSBGUZDGMRUIU3DMNRWGQ3TINRUHA2TSMZRGM4TGOBVHEZTANRUGZATIQRXIEZTSNSCGUZDGMRUIQ3TENJQGMZDIRJUHA2TSNZZG42DMNRVHEZTANRUGZATIQRXIEZTSNRZGUZDGMRUIU3DMNRWGQ3TKNRUHA2TSMZRGM4TGOBVIE2DKNRUGZATKOBTGM3TQNRYGUZDGMRUIQ3TENJQGMYTOMBUHA2TSNZZG42DMNRVG42TKNRUGZATIQRXIEZTSNSBGUZDGMRUIQ3TENJYGMYTMQZUHA2TSMZRGM4TGOBVIE2DKNRUGZATKOBTGM3TQNKBGUZDGMRUIU3DMNRWGQ3TIQJUHA2TSMZRGM4TGOBVG43EENRUGZATKOBTGM3TQNSCGUZDGMRUIQ3TENJYGMYTOMBUHA2TSMZRGM4TGOBVIE2DKNRUGZATIQRXIEZTSNRYGUZDGMRUIU3DMNRWGQ3TKNRUHA2TSNZZG4ZTERRVIE3EENRUGZATKOBTGM3TQNRYGUZDGMRUIQ3TENJQGMYTOMBUHA2TSMZRGM4TGOBVHE3EENRUGZATIQRXIEZTSNSEGUZDGMRUIU3DONCEGQ3DOMBUHA2TSNZZG4ZTERRVHE2TKNRUGZATIQRXIEZTSNSBGUZDGMRUIQ3TENJQGMYTOMBUHA2TSMZRGM4TGOBVHEZTANRUGZATKOBTGM3TQNRYGUZDGMRUIU3DMNRWGQ3TIRJUHA2TSNZZG4ZTERRVIE2DKNRUGZATIQRXIEZTSNSBGUZDGMRUIQ3TENJYGMZDINRUHA2TSMZRGM4TGOBVIE2TKNRUGZATIQRXIEZTSNRRGUZDGMRUIQ3TENJYGMZDIQJUHA2TSNZZG42DMNRVG43EENRUGZATIQRXIEZTSNSCGUZDGMRUIQ3TENJQGMZDKQJUHA2TSMZTGZDDOMRVHE2TKNRUGZATIQRXIEZTSNSEGUZDGMRUIQ3TENJQGMZDIRJUHA2TSMZRGM4TGOBVG42TKNRUGZATIQRTGEZTSNSBGUZDGMRUIQ3TENJQGMYTMQZUHA2TSMZRGM4TGOBVHEZTANRUGZATIQRTGEZTSNRRGUZDGMRUIU3DMNRWGQ3TKMRUHA2TSNZZG4ZTERRVG43EENRUGZATKOBTGM3TQNSCGUZDGMRUIQ3TENJQGMZDIQJUHA2TSMZRGM4TGOBVG43EENRUGZATKOBTGM3TQNRYGUZDGMRUIU3DMNRWGQ3DMQZUHA2TSNZZG42DMNRVHEZTANRUGZATKOBTGM3TQNRRGUZDGMRUIU3DMNRWGQ3TKNRUHA2TSNZZG4ZTERRVHEZTANRUGZATIQRXIEZTSNRRGUZDGMRUIU3DMNRWGQ3TKNRUHA2TSMZRGM4TGOBVHE2TKNRUGZATKOBTGM3TQNSEGUZDGMRUIQ3TENJYGMZDINRUHA2TSNZZG42DMNRVG42TKNRUGZATIQRXIEZTSNRZGUZDGMRUIU3DMNRWGQ3TKMRUHA2TSNZZG42DMNRVG43EENRUGZATIQRTGEZTSNRZGUZDGMRUIQ3TENJYGMYTOMBUHA2TSNZZG4ZTERRVG43EENRUGZATIQRTGEZTSNKBGUZDGMRUIQ3TENJQGMZDIRJUHA2TSNZZG42DMNRVG43EENRUGZATKOBTGM3TQNSDGUZDGMRUIU3DMNRWGQ3TIRJUHA2TSMZTGZDDOMRVG43EENRUGZATMNJWHE3TINKBGUZDGMRUIQ3TENJYGMZDINRUHA2TSNZZG42DMNRVG43EENRUGZATKOBTGM3TQNSCGUZDGMRUIQ3TENJQGMZDINRUHA2TSMZRGM4TGOBVIE2DKNRUGZATIQRTGEZTSNRZGUZDGMRUIUZTMNCCGMYTMQZUHA2TSNZZG4ZTERRVG43EENRUGZATKOBTGM3TQNSFGUZDGMRUIQ3TENJYGMZDIRJUHA2TSNZZG42DMNRVHEZTANRUGZATKOBTGM3TQNSBGUZDGMRUIQ3TENJQGMZDIRJUHA2TSNZZG4ZTERRVG42DKNRUGZATKOBTGM3TQNSBGUZDGMRUIQ3TENJQGMYTMQZUHA2TSMZRGM4TGOBVHE3EENRUGZATIQRXIEZTSNSEGUZDGMRUIQ3TENJYGMYTMQZUHA2TSMZRGM4TGOBVHE3EENRUGZATKOBTGM3TQNSDGUZDGMRUIQ3TENJYGMYTOMBUHA2TSNZZG42DMNRVHE3EENRUGZATIQRTGEZTSNRRGUZDGMRUIQ3TENJQGMYTOMBUHA2TSNZZG42DMNRVG42TKNRUGZATIQRTGEZTSNKBGUZDGMRUIQ3TENJYGMZDIQJUHA2TSNZZG4ZTERRVIE2DKNRUGZATMNJWHE3TINJZGUZDGMRUIUZTMNCCGMYTMQZUHA2TSMZTGZDDOMRVG42TKNRUGZATMNJWHE3TINJZGUZDGMRUIQ3TENJYGMYTOMBUHA2TSMZRGM4TGOBVIE2DKNRUGZATIQRXIEZTSNRRGUZDGMRUIU3DMNRWGQ3TKMRUHA2TSNZZG4ZTERRVHE3EENRUGZATKOBTGM3TQNRRGUZDGMRUIU3DMNRWGQ3TINRUHA2TSMZRGM4TGOBVG42DKNRUGZATIQRXIEZTSNSEGUZDGMRUIU3DONCEGQ3DOMBUHA2TSNZZG4ZTERRVG42TKNRUGZATIQRXIEZTSNSBGUZDGMRUIQ3TENJQGMYTMOBUHA2TSMZRGM4TGOBVHEZTANRUGZATIQRXIEZTSNKBGUZDGMRUIU3DMNRWGQ3TIQJUHA2TSNZZG4ZTERRVIE3EENRUGZATIQRTGEZTSNKBGUZDGMRUIUZTMNCCGMYTMOBUHA2TSNZZG4ZTERRVHE3EENRUGZATMNJWHE3TINRRGUZDGMRUIU3DMNRWGQ3DMQZUHA2TSNZZG42DMNRVG42TKNRUGZATMNJWHE3TINRYGUZDGMRUIQ3TENJQGMZDKNRUHA2TSMZRGM4TGOBVHEZTANRUGZATMNJWIE3TQNRYGUZDGMRUIUZTMNJQGQ3TINRUHA2TSMZTGZDDGOBVHE2TKNRUGZATMNJWIE3TQNRYGUZDGMRUIUZTMNJQGQ3TINRUHA2TSMZTGZDDGOBVHE2TCM2EGNCA====
その方式でしか使えない文字があったら、その方式であると推測し、復号化した
import base64
enc = ""
with open('encode_mania.txt', 'r') as f:
enc = f.read()
chars16 = "0123456789ABCDEF"
chars32 = "GHIJKLMNOPQRSTUVWXYZ"
chars64 = "abcdefghijklmnopqrstuvwxyz+/"
chars85 = "!#$%&()*-;<>?@^_`{|}~"
while enc[0:4] != "KCTF":
mode = -1
if mode == -1:
for c85 in chars85:
if c85 in enc:
mode = 85
if mode == -1:
for c64 in chars64:
if c64 in enc:
mode = 64
break
if mode == -1:
for c32 in chars32:
if c32 in enc:
mode = 32
break
if mode == -1:
for c16 in chars16:
if c16 in enc:
mode = 16
break
if mode == -1:
print("ERR")
print(enc)
exit(-1)
if mode == 16:
enc = base64.b16decode(enc)
if mode == 32:
enc = base64.b32decode(enc)
if mode == 64:
enc = base64.b64decode(enc)
if mode == 85:
enc = base64.b85decode(enc)
enc = enc.decode()
print(enc)
KCTF{dfs_0r_b4u7e_f04c3}
Toddler RSA [106 solves]
You may have heard of baby RSA. But did you know that toddler RSA is a thing as well?
Demo Flag : KCTF{fl4g_h3r3}
toddler_rsa.py
from Crypto.Util.number import getPrime, bytes_to_long
import random
flag1 = b"kctf{*****"
flag2 = b"******}"
p, q = getPrime(512), getPrime(512)
n = p * q
e = 0x10001
phi = (p - 1) * (q - 1)
m = bytes_to_long(flag1)
ct = pow(m, e, n)
primes = [p, q]
for _ in range(98):
primes.append(getPrime(512))
random.shuffle(primes)
primes2 = []
while True:
if len(primes2) == 16:
break
p = getPrime(128)
if p not in primes2:
primes2.append(p)
while True:
n2 = 1
for p in primes2:
r = random.randint(0, 1)
if r:
n2 *= p
if n2.bit_length() > 1024:
break
m2 = bytes_to_long(flag2)
ct2 = pow(m2, e, n2)
with open("infos.txt", 'w') as f:
f.write('{}\n'.format(ct))
f.write('{}\n'.format(ct2))
for p in primes:
f.write(str(p) + " ")
f.write("\n")
for p in primes2:
f.write(str(p) + " ")
infos.txt
66583536270887021807490397743997271455125755581160018003919916008658356150175910713440835182971996187562565226675351042460434353931585831584272555696179274126321107345396847166333122985792520485127336843400145192855625694720207592205790961842916053059876605678603849267317164063089140203608170094060063975862
2279780221943295570270982236035582893977993979407790219223966836692545701998684597925266035868375779180218333832926459880229000054158919717743575043736900857245622481911503420167128462730860113002412674566899699371968214333231947746623067855028026843801255651389667577056503904971101594424541057381520257614453843471818576395516786682190919979161
13222824171934158795160017601111983741654223888476625973950275883862159298970076592660290659087375028487839263506230550950954738263237932702764355101517599 8978218440360436772235286311777411873413406027349849093024924257750929134670580864086577595401547891869173780064243105867543502813494481721960549178734933 8798068787464414221197551296572936834120506461129636585457070924885719707767419223056437741312655425088750417646336045043935576206958190908227376649816311 8030010099167454614960222504466241738018348712555301693805378086778095226716475768328494310610463069062410668569126285398897237915737813051218561486949661 9055251760177547872940166101580078387797598200872674009939438706220395803028074529456868014854874943327211163891726007597467757106686723097692393955690209 6859436135120487087497059388407753889091359939418063353544340593288960333716530348130557020877661334085430098869425207812303618587906929317989878364445927 10131543868910545016763564342668644797467734878362450948600041668707417091596010549904617745787056134914271620187430566778590406046294200547007645850481303 13396508311817357141752215255099252623364698033324141891630501088864849832595658646432103953284005969465311565311391979907391999640050074419458123219155603 10181940734649931795215490119971369608085374553973301280505166110215912741573683069591890941461759051435534340056831272416988448284912031024385416313627321 10769230225612119942280183290912162659882855090406190026504946362498094977666994810977191766033026702436373553913732137087675964305415476940219266331973103 10908631376982577198348577535384506308458873896093144493231727775302012357896230599591384219644682356992105824827628783353708435819356317918959386749340197 7102379140576069248026402682339395072753597161688628753274478933837665833536300729759624302466228624341656091638243469719724214419688712644348878754757037 10949461199314836301834498543126560585570642899449488409087122398927583969218891833872718651229376951341433061778465528435114884346065299222366479993449951 10559564211173215089561264958779505532305941247903270999283946919937637816301113213822420107539956901586019938513291699519846407793454852170203459400200139 10223965523215245840191227602818642461799895605508849872372428654892656126821926771081301891595050880004699492889635264372826668119732937919376334747530129 12829760826192971804891430057324307849634625513427615416868251386898381409061614483004403717963615884607907349526676633253437239862141473635541890294406331 7480624952139945226451437643423056944796341567791603048875315903370612237627966857505554400193442794491398878249143536897726712581485101669610197039105509 13041934632941219819663484633330472023273824291155449756695667846163397976993940853066528351600487550349381414827114219182247371876386898443016228706946389 10834707415664850634588569895780637283117301572801660308229147836719165701734623005630233654476703456618450948697188479408144160665108878803767339115644937 12850957660778813867517092468057670784071135976888659699304219711834693884621042741610118817149665919677640186214700156966109007057491106519637448695323023 12213004842507218949562154060595703268230012299641089756341896615626500964965571616702052514719503826053297191335873716984638525413693290756311002244928623 9419795468869517189901222130110773149856772842870234040099254749191896253545472100243260050810416689509708167041799218049337175234855195215351401899803233 11850997857955634476272118261304026070236489573648662915426159834328884168950078690919521609442880584969648441497162993737910024055284526115058850808771013 10752949857060647800211981945412727046650056356183460892623799579880450418434209324126809150950855404602213891028876556866552201427156007941182141981631923 11399197204528028815495253590734090777792410754085803191702637775710831879914720356388295046841681410720861267645528894715042695085325106604882588747535409 7739431165157974762444305202848126820062552554202816458867313874728099446022140795644884923071652212963418578968815965453906566455843064010028976991102511 12659769827416495991287113023455948111916736557897804403016765586616139273414769140708116465013563633226026242205396029989144972153979570651073582484187471 10627169742126947025392790590768637878822500912152629159448868026758809220995616742451806649752572242226317874223405517553186350803502769792229124542540151 9819828692684493192109694966971332967713969316577344536109810317172351401177617132078857304310485971330167438072779519003135012100194417221835352640711939 10170621648199566387106673435995854302458965391711961985283156594810662298127358955297408070217209651423206809954647508884327797763114435134379200648117159 12510381023597689931294236321249351188573058628279654090487677524747022706408010951311536974558054126082567415586945990716730844935248806427044669231743087 12691210825671364073325819080348576532897609699634307598299963642621471264127436122154558493761791743708872018050764508307176362046363581265259593264730711 13127065464336852897918109649831899469923094488558714286993531392049497536371040810674489740658698079069379337063393077187650855931746983624224434316556609 13377766327780695496159703407238202370319810840966475834954445596728370101513802816884127495128339853436952176363247457373704659373211485689121456939715897 7675060709347277862945832106701479880602491791564115797530525791530922893515354352710484364395636587477723777246265966244546742142457001572836753489493593 13229709315981991165045324656770922715819387836303405943042966649562029831380516463919096815928427910736256818500084176413900651833501150345644706156685131 8044365590712803459868754351937519259709415440350862051507478162120539458347285196520100025100373613531471860634315081347920108093743522719586344655840173 8437931680795192794350711947565368917073861510303712436869017367175394820235389864362034860939345384464775951060228832244052544291496291437902659850917571 10847975313299814506337224370879768462790437892447319446608635316857788443488070523834358733697657760746761372874070988493984324918131083767511469360949423 8117954006552790061372037567074823470633849559545453196333086631521637108349256841124850975471297012784040931781137777720173712233277608364807395474467681 8663500869108450931160521683715880126467951267958015979405859345805386047272533400891876987608249030577383546262600862455589385703971361086228951413468257 13129979194288403777157252264366659597526500743554535449557347414903207272588686417836868019000088347345210107106494809951077555465789873050027232041619137 8076678662951245929345327121519906664054500362724848436996383918495993405666024027837419167298446412976497444301570831468074401133209128355940200200493577 9791645850536669463780287487722761494907814550981282228311591346707747747131298075893279528152112616563778905315958953654427628683023531611055686203493691 9999267150738435699813231980756582356275562946795614946595110177047897822091704379882122999861431869209414495532532940064500381902535819722628971037460267 12717331722363842801301082906055085560884618586155337066146410795287479173999965901426494585559510136248922475060081843321096648856689244647554006001118181 12079688891415731036582414617951521310878737917972229714081485308788815758332852964831084740931434686063552308158704644347896298475032074267700295161187259 9599903824216097722302136116255349523765332420360955347843894710491720771683469017762880232916700832242164218162150134474004513723399259260426520636021837 7029133526868145182267327718011639648974982164550791512970874607486125543002630753849397266853504003988537140267096111925424465643638368036209699940897153 6759038700892593173761798119065852474769920286018351882064884500112702851789145768149877554584936010960308795528134077285946532138828843346856342577158583 10573685672240299048455887969210791429035686600702842607618106362978118832896619160140412085431431426615373587011400989534795498173457737760447750423647207 11849330907472765905121742114127309725615372314202829341782183380338753349196288579092418919555071630669779852441960880800494576829993234058800944110732247 12969954677918029060365858390229751851314108311801485466152903273679860440529787680906978465929995486347591777637113698393392851327489329042683310697069957 12745798267180228979422025830664998690681040967309971012501119955804991396070856902060612210995121768622278320217294150262577945761480693984438202136693427 8981912330163990725974451584039364509477210630663326084916332302940319018581836294788829318422804561579143105510591586932537114894794998769552212578444163 9253740586564887343293570758104913550491085825250839778845285810248464713011574245335382304480203725329090209875443068797654632817956440395143065038269181 9978711656634651333145837157201996382647241705748548649468526251060723047492501980541116602778931268147529734926225829860304071380239343523805079725437631 11489585486737867847513661203528160276421675944841680379855871281267583627720452786764176053958716932545928403926884737982834155534643244277479494209836217 9933344267566807143116374512401327710612445363820907935163043143958940993146355278292365722490560052874063588309170509983211791863217062422715836901746783 7157036311031108919986039929068887434643004838489691968685163540586382198709453211990364944705396033648372730426192675925804276042720219436123362626184379 11322284375546218230895961159449801111807506757726471747732951934776886582747161435605244470827276114850232546836111868455753235778861823190430545486930373 9914914980638104609052127547822729669315668672815710063508306095021825481338835595363970444250851917572080410416359620159351042080757051606108373797407041 7404433155166780767517541803225840492195071377507822852068412968151864474974448611758117496093302886324505388330281157727052683078758125722278640523734709 10721558819375823115198610693110206445350343724938188737047744035208742979530009718161710813312666029473974830883559452398588367746520346098028868477685099 12087559364698799083646309369449674361847312477443433452900954690666788587660445296183795795296092886363913103796815490192247779594875883071941781454979923 12798337704796296789978712383765863276008400272930300285578831261286179969372050232382075319465578905413739443133562812372208010517548883050316861684122957 8085474185715380619504462470378449289148649888306724902551702023843293586970459786787832004104365925114585351503144285909433277979106902219247126016093373 11721075075276040988157268296761738639079449334046076008222868950789353354030000142993229865461319461172991919925500847511116440694480095785544054487745487 10848586093141019899518528636110172938777130467258630816793913320856664102203955148333762081349273445811084674475491695276176918242033986192041946474497487 8263383319567875182631053036582463505030763508154235744907245406788504450448715945850867458463359584440335478349143817868737562078954062136614184837789441 6795184129653891934423217687442657639405833761610049601919669643858090869344025190951126892921122808008493540127457127109487026379764399131749737025761051 11828920755782128489978865763699492624690162481058971670314657411296867370019036319747760575904266606182254068162322242272204952775673525818430800363004399 9605569629088201414734322120165901050254991381458843401700824588025593641596420841429995984719211953820284974350858845538108700301558557636311584178418393 12866267497543386664496631341122803127357526277740362670834618767550190081542164243211776119679135741098503541006258002743804016012898164119229064960404107 12725411135088154579525779901094480576915173805688490410911371420713784360685772520182988733022219879186020020990591675863889948261362017058975786247089187 8707879348339333769571880114160712569033433680204758637182266589895067471646582484508509695935624459025882823460830600386361844306781070176699196807449799 7222328250919075499708620748618060948460187251943132886728282217891096052040107817148422916751560672075713219439047049534230458352381529112965429477395237 7358532221514650425334644537383354095686597256020816383129333715177723829493933657192969120419438117944079555161929969972811712739153836745271837277150533 12963822484683306518968653458187125904726138900528875261222387626003111632525064742650330000074083968638997866418406004946078983064331431634278053295656181 9721745538799098170907621992769344656836760623094737239410622413281125924392096420878112473559948050736406614502945603971291608836728423123847439947324779 9683955386692846487377531447569658799780691031019077556449413914596848587784463885961725390766202879071221651180998238357686457479722086210694963487341803 11571100613227846965249904329897452743318917767794273926304972985631866295751883979308269962891001188270328187403611102182325437514503445062659337203997723 9290861835085821906065369471784316828401397205126974629304237348542833890081785143462808909575590613605440512594444110153377630357258980806558350046037843 7447117534948401053340723916390599281587451888951874732630755254978123893526873601210526342886062765762558424841762129944902695365289329018253265408857057 7641787798831316885636241989069074570518493018455455940676868425704234735991927991347480298523331967307500529075474030481161502641362840796467855622636329 10709202873078015076562185747269936428270340425727963656217531822719197816589155171888457197401842321058597557174072909034278820643400305116941458348433287 8051691596444037812929283423270289534914081955906881518455063970606386194965934256747442075211224926920680300606039491600944156845781165410597448063129579 10214732900656536373817557108035716379103345518834646085012976320961996965470856898815575928080297147955465452805440831445630727423729378210257365275132619 10537433132461818669809088883167413095200463651843350060180161273935780561663190106638994781596717928647182587933401499499744048938660291970862563549777413 11890435781663452233713348946211482017023013412747171685759682235851525288089682360063310827787132454951841663578704117336825818779465557776250196090853359 8312989354720509888206514989976876350992168686566734655737578944758900712960449723278487136422750096448378492734195178178271268593520640988291966214076853 7768208519530152260791582271373263380363628347772179494525444088180265946056952211715665312379204636071100756599541714826775212918796144263676951221407059 10711809872399203859533525539021743176286530328561971556985671149198495456451206007108894902278090627770724088426360072744462976225935725256518700404533327 12534622082142707492292767543128862991703619096994237741907228431329953552424080461031630677964388289726617101525219341820388433688906145290518424994258041 10174333855725959002126370677386361414150295518834171679957502792719895564803304624772585821993612497540534475214174228134585929716775518647700807137866783 10564505713738317131546547012532599630476211458930116166462176258766533340180692715985087807312776167131499181641223676237623469021104581308865527115648147 11498904232393138660400711721765848008129283525980208050214998582653056213381552208474251099998131654372512724884475451668320152705126045412888397974423903 11758681064186232229551633887690033254210889776480909631135385889162941040171837055662047562366106267078578844038464523206798769429131100849412257790596241 7528551626700645090534899703476762388567550424954231349139101909154295194665485698781783315742009792344681056055737076325656215231188268498606944841931767 13220609650849874808339816379600869355806891056203120834879430225390869618889521016019966144078055939224007474284814389723158980197221950437296717999733563
308089921556184669678067116453554498083 269146033926397645805375455649073618511 233752348549763691930734307740517186901 198900085063562438325290932756032828991 325056627648586804000260397839751402681 199207323217993149137530299063863021101 223010468650623848513929934188605947191 187248241561061590190699990690176830001 244860073201395394574265869514524044319 247762662262277180796128790164032314883 224934578245666728615293083378672676597 314092235613143539528686079670166783589 336298198087347741578643304009007407279 331992409524106686129786965591136175513 224759198911453561220620014369783797077 242327619287649969401337972817534706189
前半部と後半部の暗号文を復号化する問題となっている。前半部は与えられた素数の集合から
from Crypto.Util.number import *
ct = 66583536270887021807490397743997271455125755581160018003919916008658356150175910713440835182971996187562565226675351042460434353931585831584272555696179274126321107345396847166333122985792520485127336843400145192855625694720207592205790961842916053059876605678603849267317164063089140203608170094060063975862
e = 65537
primes = []
with open("primes.txt", "r") as f:
primes = list(map(int, f.read().split()))
for i in range(len(primes)):
for j in range(len(primes)):
if i >= j:
continue
p = primes[i]
q = primes[j]
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(ct, d, n)
m = long_to_bytes(m)
if m.count(b'KCTF'):
print(m)
from Crypto.Util.number import *
ct = 2279780221943295570270982236035582893977993979407790219223966836692545701998684597925266035868375779180218333832926459880229000054158919717743575043736900857245622481911503420167128462730860113002412674566899699371968214333231947746623067855028026843801255651389667577056503904971101594424541057381520257614453843471818576395516786682190919979161
e = 65537
primes = []
with open("primes2.txt", "r") as f:
primes = list(map(int, f.read().split()))
for bit in range(2 ** 16):
if bit == 0:
continue
n = 1
phi = 1
for i in range(16):
if (bit & (1 << i)) == 0:
continue
n *= primes[i]
phi *= (primes[i] - 1)
if n.bit_length() > 1024:
continue
d = pow(e, -1, phi)
m = pow(ct, d, n)
m = long_to_bytes(m)
try:
print(m.decode('UTF-8'))
except:
pass
KCTF{rsa_and_only_rsa_ftw}
Discussion