BlueHens CTF 2021 Writeup - よっちんのブログ

この大会は2021/3/20 3:00(JST)～2021/3/22 3:00(JST)に開催されました。
今回もチームで参戦。結果は2347点で324チーム中23位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome to UDCTF (Misc)

Discordに入ると、#welcomeチャネルのメッセージにフラグがあった。

UDCTF{g00d-LuCk-3v3ry0n3}

Transforms (Misc)

$ nc challenges.ctfd.io 30008
you have solved 0/100

convert hexdigest to string: cbcf93f83286e075 @@@@@
> 

$ nc challenges.ctfd.io 30008
you have solved 0/100

convert bytearray to hexdigest: [97, 215, 52, 93, 185, 94, 149, 138] @@@@@
> 

$ nc challenges.ctfd.io 30008
you have solved 0/100

convert string to integer: ���:�� @@@@@
>

いくつか変換の問題が出るので、スクリプトにして答える。

import socket
import re
import binascii
from Crypto.Util.number import *

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('challenges.ctfd.io', 30008))

for i in range(100):
    data = recvuntil(s, '\n').rstrip()
    print data
    data = recvuntil(s, '> ')
    print data[:-1],

    pattern = '(convert .+)\: (.+) @@@@@'
    m = re.search(pattern, data, re.DOTALL)
    q_key = m.group(1)
    q_val = m.group(2)

    #### hexdigest -> ? ####
    if q_key == 'convert hexdigest to bytearray':
        ans = str([int(q_val[i:i+2], 16) for i in range(0, len(q_val), 2)])
    elif q_key == 'convert hexdigest to string':
        ans = q_val.decode('hex')
    elif q_key == 'convert hexdigest to integer':
        ans = str(int(q_val, 16))

    #### bytearray -> ? ####
    elif q_key == 'convert bytearray to hexdigest':
        q_val = eval(q_val)
        ans = ''.join([binascii.hexlify(chr(v)) for v in q_val])
    elif q_key == 'convert bytearray to string':
        q_val = eval(q_val)
        ans = ''.join([chr(v) for v in q_val])
    elif q_key == 'convert bytearray to integer':
        q_val = eval(q_val)
        ans = str(bytes_to_long(''.join([chr(v) for v in q_val])))

    #### string -> ? ####
    elif q_key == 'convert string to bytearray':
       ans = str([ord(v) for v in q_val])
    elif q_key == 'convert string to hexdigest':
        ans = binascii.hexlify(q_val)
    elif q_key == 'convert string to integer':
        ans = str(bytes_to_long(q_val))

    #### integer -> ? ####
    elif q_key == 'convert integer to hexdigest':
        ans = binascii.hexlify(long_to_bytes(q_val))
    elif q_key == 'convert integer to bytearray':
        b = long_to_bytes(int(q_val))
        ans = str([ord(v) for v in b])
    elif q_key == 'convert integer to string':
        q_val = int(q_val)
        ans = long_to_bytes(q_val)

    print ans
    s.sendall(ans + '\n')
    data = recvuntil(s, '\n').rstrip()
    print data

data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

　　　　　　　　：
you have solved 95/100

convert integer to hexdigest: 9956280526821745813 @@@@@
> 8a2bd06375596495
great

you have solved 96/100

convert integer to bytearray: 939509236931364368 @@@@@
> [13, 9, 206, 172, 90, 126, 6, 16]
great

you have solved 97/100

convert bytearray to hexdigest: [211, 219, 56, 79, 245, 3, 242, 82] @@@@@
> d3db384ff503f252
great

you have solved 98/100

convert bytearray to integer: [241, 150, 175, 119, 172, 154, 13, 205] @@@@@
> 17408294338178977229
great

you have solved 99/100

convert bytearray to integer: [91, 83, 120, 30, 110, 87, 208, 12] @@@@@
> 6580735552614027276
great

UDCTF{r0b075_1N_d15gu153}

UDCTF{r0b075_1N_d15gu153}

PHEnomenal (Crypto)

$ nc challenges.ctfd.io 30004
HEllo Pascal!

Can you hold on to this for me? 9401696427901823179425938612277559249331574262532464295046824245382364018745231738575982969553544987594404297605813475997925866335673494370550221471865620616488976938340522230965539774358455753772834025830308454646634578935062692257126419871099402646207953512716237839934967790084562794412205441615393142365189792829617628664746618204819731840933188287806838329752042038570194539813884197233892382767553374417069324242153780932983354405599555489739657095780569087453259418346102459939811318079615339586952810931131125330412546579493324346375440985341938785968313623135218985485391173371270978828038621740048422775173004731329694426966984097954107178345438735093859366884282690067805991478699428642315377555162702730247252415862225131631318438295595806992588913614612153113002364979049305962923576002304196001857094325571356769235128539829930014624443643845336236462505426407769026892053035561446403728481656413411560702779701630030500914960829835116198915654551134955125553532514334893016350861535169974509858170988825850467528098220479301044348487028684723703783995627594861929042441215921405542452886210123808860298958064055339098929791702367327488226117417530515533234034764388398871573802186727761836167535559351958402698411401087653102996338249901467968019498793973030703040624693859687135581781124470332810414636748564334299791035414378769633542008284482034650798292476947381842136089712406697363760382139263151426933551067409948792414935630080509767405826876541117004371718271940941997756163716687690595887755355537742631234238027698122137428597944442394644937563401825433354599706202655070368078707310633917124527614676616112777449176016983714316779490514965104296294716488133723902673282647606908899471693138508468510887689967901713523209128682835007726958177822251628480238693326583471855136776412486367859346446560585832704077345121216646

I want to keep it somewhere safe. It's an encryption of my lucky number 61 !

Oh, I think you may need N^2 as well: 11524758657623999982442658301236796480466459977520300597557767528123954032057862449679708951179328168372176050989981442876023409285804582602964508661899216132642272355130795098923056785895175377095862957831524247471228639125488315700367645226595931645231369986758606729300686193373144247294329400597194500032362693063296602021233169957029367930879220364642471772623413217464725693670469627165119041661071660491278696527533731691772920121347155156311849597253498482506850159221549910350587148027534199681620229730720462951207562976847473097670840167610505869476369016727546246598162381358835578402733011530049522459378101342195007732259463382272290990335363266494048034530071459593426176748991344795820073413617789924902597715156974863072095225673279635178302788041064929206697981189697539836011746648332117502460578304035905452491608471299210310715546650614793213722779906137412446237796073255369431031282227236288730574992060167990277597164697649278738357574815560023826092588842108786838111748972310851424670910093027251750380185001876929453214876811498252925138854297116864500047933812972400236445779857499147169385946219223424743590703646161257211891341931725866510263914588320124190478553090668581904952215993379975007331084742439024510348158356619949608739017786634860907110262635879680412787178706149856661968839258727912616366392978478557392339002918613194059148943308757990769198090688279963475792270735876629539220760212988594934694776932004909113593048293991812807361945230529704506674434774936353585928562307413577354173181452785736766106622419787881107623221517121569905885828790269252032914115523389584809493934039073449660229698441093587938825063040071240240184405450811925449698902077190488801007615688258319805371436103808116812081023523007303957555489015611827516684607641295132231862670645295583845862874057967705603054442480921089

Uh oh, I need some help! Can you give me the encryption of 49105?

タイトルと合わせて考えると、Paillier暗号のようだ。

c = (pow(g, m) * pow(r, n)) % N^2

m = 61の場合
c = 94016964279....

上記の場合49105は61の倍数になっている。何回かアクセスしてみたが、数値は変わるが必ず倍数になっている。Pailler暗号の加法的準同型性を利用する。
平文aとbの暗号化C(a), C(b)について、以下のようになる。

C(a + b) = C(a) * C(b)

このことから49105の暗号を算出できる。

import socket

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('challenges.ctfd.io', 30004))

for _ in range(2):
    data = recvuntil(s, '\n').rstrip()
    print data

data = recvuntil(s, '\n').rstrip()
print data
c1 = int(data.split(' ')[-1])

data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data
m1 = int(data.split(' ')[-2])

data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data
N2 = int(data.split(' ')[-1])

data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '? ')
m2 = int(data.split(' ')[-2][:-1])

assert m2 % m1 == 0

c2 = pow(c1, m2 // m1, N2)  % N2
print data + str(c2)
s.sendall(str(c2) + '\n')

data = recvuntil(s, '\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

HEllo Pascal!

Can you hold on to this for me? 2856202253840126425607479940562414686504060276541544326077121841542971533651022158043463327671150037558862024897338868586689732353681779160368549315968342584841433855961811846725781989836304258950434432266659558881778012148366451140654051231787441009277320957853301913739979638335779344175939775015834163308908721757246260402066112375842551184345806029863429190659219854909567681301498851297476125188051701821059659829732928801957682954371875538625918534485887999113707789888651538807091140474653513737813631265591446381867297953367553732961397606553380788544640659266658468517080998402206744148331276475802684842389911306112367919101523214094361615757663980901281815833116716947971931573402937123686893538743246375034672576129603388657474488037226100391947658622281816195053698705583018301362675846412877237993060313322952293980843345053313359910040061735611869045029888974582487463713682138586739453798331127079824651009112125807698208883266591963976240223590817727248131339687143997651296366349926901450441515361432017463527903621952997893100895442341279639999638454033573179650363865987216042069376664679311600505353327182644673409066528072850790401539816585484599499660357052452567023693377115052337587157358210464872250514254601436849364735401207910022922960810435125931005829786682985667607275359012000772663491351577065201856160449119190579237415143171524796483165896608527301636615039457469489517590014367878764318064588418785460652567271381245063066985199235402203195483700803965212406799754694045293566057103034364395552206059278842864855985283190690503259918635716629735110608317294569457756091972029874802539135474078296554443265107941565309036524417676158373489328931112418671531345263997755565468492401227124143997203628251727713060260268820074043161232487210073265595614430500535011732593339026309181727275165329889953628040240114403

I want to keep it somewhere safe. It's an encryption of my lucky number 39 !

Oh, I think you may need N^2 as well: 9462443801404504174539993065515652478061032522288659760464062752045490903620143876820156413591103069000866494184722675104687633244484653513266138373423732461376250375945555879146920913895666632034205043574773727395899188343148229094638900893938227922985993102317695063859116480622688867405786428632431883415654523756514758495829626766788964757085348300511123904285859925967527288204732558160933085095987551545933913422033536350322762118527232624509690981264658965867169282331307028150124243992546072534148836887631184117053448015649640730687537088097590425131324433423625561003715685221817364561449734050214711351737617134501381461915460970690187048253995619498114159738502051963307165283899998273208493437676544979234847265462331069187147234308910769003352240892224941749958600945061074033067457060402165043750002270287110079523561553178471215339681869957788106500666389826015762921025104773613534580002970992429077474029580863032489958295743510689141597015134660457072404473120409763524617177785943610323199636219471269421292956289984725052078127150980198556207789707504162310532999113155598635057605794704133247062673594724037142620826968566626519114747433758034075969843527428627997717556067129640981731844105558435905851041701153499022067345816462073005280240921091873198043608803184739656567040861946403476345080529101459625330913943722133997981914796097958520433622865246661498512272934465893714295273860819337851339979419050618688232927204732618796276752148741202731941165938650035796483979506790958693491061115423884746894510607344696002672026900736162407913311216535908545933892552437236846030560174275086193301423414548590790705311401669752793422443854632039954293291091336729055022470248724894640872954908548735427700795322820803213742928774293915059246343431403542602500211258802321632876660940567192890048090636428727782678833507279049

Uh oh, I need some help! Can you give me the encryption of 21294? 9109398162485919474689826547424353875793679926603336599817986914336873127152774782738370079124609227332954517148390421616587718752860268037847126668821937574811992316476547767043015279747784041562189644043518023699083715255673796263579953520365230157608854062521755520978637475953592385938315359624717155912735694609013113366553903755954284276064721507296067832332400732415660037175896480040135931434827478462093090964041334349567243612082779736203480693670851323724561683561531447716854680501511833034907724311619491119234434445215611861598580113994237572784742284518394418528163390803203913503654851246946653287244700394141886783617111109854047688482202462147328914348538012173610510180289349495931090729667509857676802878994668659862898945201528389738936885664548870706553980546868443625604110233469408971645321980409260401127065229894252179636018820091593227406524899363724630838250703945686813381325633045662591202887645041450849745286148761192322436595146250349689211955716277741238356187356701678851866685322407654539188381257459999011520401595434054058138204649049703944387574370803456120219878525578395868287415735996451845116868415830937390451817969118210072534235233109418751516242409332736403842508559011430547480173812954191728534743296100772294257187214667554992110385390900317759554476388800677347058938156728427172209111812689681692153867723876468995214127647264566197750779163265930459111954164553029938370336146049496615119365367140818448740760489373263048716202363258616157435276691389131987300663402312802313536277977471265190764359445535286681125195709203294476354341694372749331083132047249313010736124156654849789487962202957496835966202918900965742313791157846691807988669843470739293668732937003449775799935310223779695668889980889108977224037595349940393532575118881021004232243177975833405260728876185217965392222536195269

UDCTF{P41ll13R_one_oh_one}

UDCTF{P41ll13R_one_oh_one}

OTP1 (Crypto)

2つのテキスト文がflagをキーにXOR暗号されている。テキスト文はアルファベット大文字のみで構成されている。
flagの先頭 "UDCTF{" で条件を満たす箇所を調べる。

[+] 000 THUSCA WEMUST
[+] 025 PRESSI NDNOTS
[+] 050 OSTEXT USMYDE
[+] 075 NCONST HEPLAY
[+] 100 SEVERY TUNEDO
[+] 125 RUMPET DPEOPL
[+] 150 STONIS RWHATT
[+] 175 RSTHER UNDRED
[+] 200 ESOCOM EJOICE
[+] 225 THEWOR EYREJO
[+] 250 ERFALL PEOPLE
[+] 275 AUSETH GAINOR
[+] 300 ONOFTH NAGREE
[+] 325 ATSUCH EORMER
[+] 350 LANDST EVERKN
[+] 375 MBWITH BOUTIT
[+] 400 AXIMOF SLAINA
[+] 425 EXCLUD ORDNEE
[+] 450 EVERRE OKEEPI
[+] 475 BLEMUS ECANEN
[+] 500 REGRET SIDETH
[+] 525 FROMTH SUFFER
[+] 550 FORWAR HEREIS
[+] 575 SJUSTB PEECHM
[+] flag length: 6
[*] flag: UDCTF{

この結果からflagは25バイトと推測して良さそうだ。
あとはこの結果から文となるようキーを推測していく。

from Crypto.Util.strxor import strxor
from string import uppercase

def is_uppercase(s):
    for c in s:
        if not c.isupper():
            return False
    return True

ct = '010c1607053a24763f2c76242b1521630b7936371e2d30292d051606071532387d2d2d74393c0d357e1169343c1b373c23301a1717111e2f25723a22772c2b0b3679187f212006222623341b070c1a152f367d382c732e300d267511733033122c3a21280601151114223372352a6424360b3c751c652626102e20292907110e04032f317c3e377820301c3c67107e31370d223a223c06100c1a0f283f7e292d642c310b3c751c783c3719223732320717171c0329327a2230753931163a771e643137192a35283e10170c170936277f293775213c0b3c7510603c3c162c3a293b010c060309293b772e3664392d1a267516633b3d1831312729101605150a373670352a6424360f26751c792637133a36233e141110111233326a282c73222b0c217c0b643d3710333d28341a0a0c121233327a3e2c6723291620641375223d0d2f303235141010010533237b252d773e311e3f750f7c34311a2220273119050d10152f257a27266425201826751e64223d0d2f3022281806141d1233367e2d397520201120790b792633112c382230141c0a19093d3a7a22266425240b23781a7e2c3d0a2b353038101c0018133f3277382b7524280f3b630c79373e1a343c272910120606143e3a72252d63252a0831661a623c3f0f313b243c170806191328237129377828310d216417673021172c212a3907010406032f38663e2e793e311e3f750c713b36132635343313160c191233327e2e366423200931621c71272006373c2330130b11030729337a22377f392d1a32650b652737082a202e28060e1607123925762d3778242b183d631164393b092a3a21@@02010e01152f3a7629376228331a26631a63373d1327383f3c1b000d1b122822752a2662392d1a39641076273b182b20233300170e0d023e36613b267d38360b38751e623b2610223732291d0113180722386638347520300c207c1666303f163032292f01110d110234207d38317f393c1a207e1064343a0a2d3034381114061b1637327a2237782c311d35640b7c3039112623203207130b15122f3f7635257f382217207f0d673d2b112c202735000a0706033f3875382b75242b1c3b7e0c7931370d2220232f100e0c1d053e2560252d642520093d730b7f272b082b2d3235101d11110c343e7029277e223117357c19713d27112726233905010c040a3e20763e266425201d31640b7527341031202e3812050a1a09293b7c3f307e223117357c1971313d05263a2b381b050406033e237c382b793e2d102162107e213a1a2035332e100b111903293e673f227e292b10367f1b693c3c0c2b3b3429101206060d3532642d2d69392d163a771b792626162d37323c170b16000f2f35663837782828102162117527211025202e380608021d083a3a7a22277e28201b2772107f3e211e3035352a1a16071a033e33602d347828310c207f11753c3416373d35291a0f06111632236029277728281627761062212711262729331007021a033533663e2664252006377f12753320102e3b3329060d07111233326a2d31752c261c3d741a7e21211d36203232061105120329317c3e2c7e283610237e1971203e0b30352e291d0111110f28237b293064242b183b761379333719223d342e050106170e36366a242a742824193b65137830330d37'

ct1 = ct.split('@@')[0].decode('hex')
ct2 = ct.split('@@')[1].decode('hex')
assert len(ct1) > len(ct2)

flag = 'UDCTF{'

#### guess (add the conditions) ####
pt2_131 = 'E'
flag += strxor(pt2_131, ct2[131])
pt1_232 = 'D'
flag += strxor(pt1_232, ct1[232])
pt1_108 = 'Y'
flag += strxor(pt1_108, ct1[108])
pt1_359 = 'E'
flag += strxor(pt1_359, ct1[359])
pt1_210 = 'E'
flag += strxor(pt1_210, ct1[210])
pt2_586 = 'E'
flag += strxor(pt2_586, ct2[586])
pt2_087 = 'UST'
flag += strxor(pt2_087, ct2[87:90])
pt1_015 = 'ST'
flag += strxor(pt1_015, ct1[15:17])
pt2_267 = 'ER'
flag += strxor(pt2_267, ct2[267:269])
pt1_444 = 'LE'
flag += strxor(pt1_444, ct1[444:446])
pt2_296 = 'EN'
flag += strxor(pt2_296, ct2[296:298])
pt2_098 = 'OR'
flag += strxor(pt2_098, ct2[98:100])
###################################

for i in range(len(ct2) - len(flag)):
    try_pt1 = strxor(ct1[i:i+len(flag)], flag)
    if not is_uppercase(try_pt1):
        continue
    try_pt2 = strxor(ct2[i:i+len(flag)], flag)
    if not is_uppercase(try_pt2):
        continue
    print '[+] %03d' % i, try_pt1, try_pt2

print '[+] flag length:', len(flag)
print '[*] flag:', flag

最終的なコードで実行した結果は以下の通り。

[+] 000 THUSCASESOFINJUSTICEANDOP WEMUSTMEETREVERSESBOLDLYA
[+] 025 PRESSIONANDTYRANNYANDTHEM NDNOTSUFFERTHEMTOFRIGHTEN
[+] 050 OSTEXTRAVAGANTBIGOTRYAREI USMYDEARWEMUSTLEARNTOACTT
[+] 075 NCONSTANTOCCURRENCEAMONGU HEPLAYOUTWEMUSTLIVEMISFOR
[+] 100 SEVERYDAYITISTHECUSTOMTOT TUNEDOWNTROTYETNOTAHUNDRE
[+] 125 RUMPETFORTHMUCHWONDERANDA DPEOPLEINTHATBATTLEKNEWFO
[+] 150 STONISHMENTATTHECHIEFACTO RWHATTHEYFOUGHTORWHYNOTAH
[+] 175 RSTHEREINSETTINGATDEFIANC UNDREDOFTHEINCONSIDERATER
[+] 200 ESOCOMPLETELYTHEOPINIONOF EJOICERSINTHEVICTORYWHYTH
[+] 225 THEWORLDBUTTHEREISNOGREAT EYREJOICEDNOTHALFAHUNDRED
[+] 250 ERFALLACYITISPRECISELYBEC PEOPLEWERETHEBETTERFORTHE
[+] 275 AUSETHEYDOCONSULTTHEOPINI GAINORLOSSNOTHALFADOZENME
[+] 300 ONOFTHEIROWNLITTLEWORLDTH NAGREETOTHISHOURONTHECAUS
[+] 325 ATSUCHTHINGSTAKEPLACEATAL EORMERITSANDNOBODYINSHORT
[+] 350 LANDSTRIKETHEGREATWORLDDU EVERKNEWANYTHINGDISTINCTA
[+] 375 MBWITHAMAZEMENTITISANOLDM BOUTITBUTTHEMOURNERSOFTHE
[+] 400 AXIMOFMINETHATWHENYOUHAVE SLAINAMINDNEEDSBOOKSASASW
[+] 425 EXCLUDEDTHEIMPOSSIBLEWHAT ORDNEEDSAWHETSTONEIFITIST
[+] 450 EVERREMAINSHOWEVERIMPROBA OKEEPITSEDGEMISFORTUNESON
[+] 475 BLEMUSTBETHETRUTHWESHOULD ECANENDURETHEYCOMEFROMOUT
[+] 500 REGRETOURMISTAKESANDLEARN SIDETHEYAREACCIDENTSBUTTO
[+] 525 FROMTHEMBUTNEVERCARRYTHEM SUFFERFORONESOWNFAULTSAHT
[+] 550 FORWARDINTOTHEFUTUREWITHU HEREISTHESTINGOFLIFEFAIRS
[+] flag length: 25
[*] flag: UDCTF{w3lc0me_t0_0ur_ctf}

UDCTF{w3lc0me_t0_0ur_ctf}

hot_diggity_dog (Crypto)

eが大きいので、Wiener attackで復号する。

from fractions import Fraction

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    gcd, a, b = egcd(e, phi)
    d = a
    pt = pow(c, d, n)
    return hex(pt)[2:-1].decode('hex')

def continued_fractions(n,e):
    cf = [0]
    while e != 0:
        cf.append(int(n/e))
        N = n
        n = e
        e = N%e
    return cf

def calcKD(cf):
    kd = list()
    for i in range(1,len(cf)+1):
        tmp = Fraction(0)
        for j in cf[1:i][::-1]:
            tmp = 1/(tmp+j)
        kd.append((tmp.numerator,tmp.denominator))
    return kd

def int_sqrt(n):
    def f(prev):
        while True:
            m = (prev + n/prev)/2
            if m >= prev:
                return prev
            prev = m
    return f(n)

def calcPQ(a,b):
    if a*a < 4*b or a < 0:
        return None
    c = int_sqrt(a*a-4*b)
    p = (a + c) /2
    q = (a - c) /2
    if p + q == a and p * q == b:
        return (p,q)
    else:
        return None

def wiener(n,e):
    kd = calcKD(continued_fractions(n,e))
    for (k,d) in kd:
        if k == 0:
            continue
        if (e*d-1) % k != 0:
            continue
        phin = (e*d-1) / k
        if phin >= n:
            continue
        ans = calcPQ(n-phin+1,n)
        if ans is None:
            continue
        return (ans[0],ans[1])

ct = 1445158457387990092729868574235690883328476381078437687117878228610678310947334902928151958126564073831321511131120493936116572980844392339059695082676944986711787958020467838355715919844010417357214590554232283621365683356875746321589009098953624328174730340745378234041481603493747258963262531884670382042229428718330510592290008758111173719368374299854731022071324105897071753892331177288853041690780740815531486651595502580196838941532727366305459058746061588746640490687182589242546152875181973797724210940606061367176901019489599206915050389787568489542789560060345579688651817178939492459114225606406771235955

e = 5330937005006880093598805190457883063630518250745326049791291310524191688770900677498253541876968725608988780011516913878357798140003135027183366863417959569121844853154112633643536091957118974799216641940813816076761892236211162375350644432689995305078796388972317016831896068476526526240493710949951454131783438007369494808004238449351949310021365138218085659500266511659278324660907726047634205954578349090143258122339575130486086737348129446819710953982137783348510587816619070115876002869074901265649919320219852616110355922199696052682562769419854041433691634833396620026960716117376716599744619445906636482175

N = 23556978386989862035227152665942267051448371189104346192996652142451495705784925966782823083699578017218099068429270687003013513402446285863364337355914497014903287391640470691911301379324025739991132998846569160231096469746500676982968388236346330604875221880999292763567973167457083433522181668657217912177241888729758963460176309486324449898397985561906686499104935496010357883868875083629704557203354175080409863639147851384555705571167351576323781959338290250693193849433909988970284946272004099242515681352168706645027456876652910731084445006361925449302087580591425037548670961363916624298931229939048540585477

p, q = wiener(N, e)

flag = decrypt(p, q, e, ct)
print flag

UDCTF{5t1ck_t0_65537}

OTP2 (Crypto)

2つのテキスト文が[ランダム文字列]+[flag]+[ランダム文字列]をキーにXOR暗号されている。テキスト文はアルファベット大文字のみで構成されている。OTP1との違いはキーの長さが128バイトと決まっていて、途中の一部でのみフラグが鍵になっていること。
flagの先頭 "UDCTF{" で条件を満たす箇所を調べる。

[+] 005 INGONE THINGS

この結果からflagは0～127のインデックスで5からフラグが鍵になっているとわかる。あとはこの結果から文となるようキーを推測していく。

from Crypto.Util.strxor import strxor
from string import uppercase

def is_uppercase(s):
    for c in s:
        if not c.isupper():
            return False
    return True

ct = 'de1aaff3510601061a092e2a7b307e3e23100f643a1e27203a763c22763a1a35783a38a73de82037856d0e68a62d5fd23cc78e88c4c88ef8a307cd96d8d26d461ab0d4fa35c675befe312308972f1f1e7d0b9f536f5ba7c1ea43f5eebfb7a3ac756e4efd9053fd0b42df31c56cc175cd5c26afbfbc116a31b5d80c7c869a1617df12acef59061d0c01092924642b643929171966370b3b3b27742633763c192f652429b137e8202f9f781d6bbc3b4ec82bc78a95c0d490e2be1dc48ed4d9765b0db0cafa30dc63adf6272412942f1906640b9a4c7c52b4d0e45ae5e7b2b0b8ab767d5bfe9c52f5005fd020c063db75c45d35bda6ac0f6621b9cc1e789b9a100cd91aa0e8411d051511023423762d65212210167f26173a3a35702129633a1624622338a42bf5242e95630868bf2856d52eda8689c9cf99e8a41bce97d4d966521ba1cbeb31d464b5eb3738168c34131962058153665bbec1e346efe3a7b1b0ab76654af49c45fe175ed132dd6cc166ca5c35aca6ab0a6e38b1d20776899d1502c21caaed561c170e1b1233286137702c3e0c1075301a3f3d37652b34763b17277b313cbf37ef3b2891641363a73b42dc37ca9980d7df8ee2a21dc294c8d361461aa5d9fc3cd470ade8352b158e261d046416885e6f43b3cbf95bfbffaeb1a4a5727d5bee9152e80559da36c660d775cd5a3fada8bb0c7720a7c8057e9c9b180fde0fbbe65d1c0a041b083e22753079302016167f20093a2626662b34602016257f2038b337f4262f97680d72a22852ce31db8689c9c797e8a21ac596d4d1674701adddf627c168a9fc302f0797371e14790d8e566a54@@ce1eb6ea5701050b01083f3f76206130220f14753b11273c33672c26633c13237c3938a03ef53b2c9e6a0873a33f4edd30da888dd1c991fab80ac595c9d66a4606a4cafa30da66b8f32723088028181e6300884d6a4eb0d6ee45ede6a5a1a5b07e654af49c41f20744d137d07ada78d15b34b3bbbc096d3db4d80f73879a1102db1da3ec4d1b001111022b287c347d303a1a0a752617363637673a22652e1034633f38b039f3273484671374b83458cf37ce8383c4c28cf7b51dc69fd3d665410da5ccf020dd69bff32d3f148c2902056f078c4a785fbad6e64af0e6b2b7b6ad736551fe9653e20d5ecd2dc67fc664d35623a1a7bc14633aaec9037486891d0ac40fabea5b0105011b132f246726642139171d7d3d0a213a37613d28713c1723643b3cbe36ee213a9a671166a03f5fd232c38e90c2ce82e3a41bce88d8c46c5c1fb4d9ec33da6fa8fd2d380f8f2b1002660f8c4c675ba0c3e346ece6b5a9b8b77f6e4cef984ee81758db27cc61db64d35622abbab1026e32b6d504689a9d1e0cd81faee54d120c06020329347e2b633b24110d74310a21313370262667290c31762430b633f32729936a187ead3545cf26df8790d6c086fbb501df92d8d674561aa1dffa39d46ea8f42c3e0a8a2c1319780b985d675fb4caef4be3e1a1a1a5ad786951f88054fa0a43ce2ac061d36dcc5534a7b0bd066326a3d50a699b80160dc41eacf75d010c0a1a01282572346130231d0d64251a313b30663e32793f1a2a743830b22ce83c2f9e781d75ae3458cf2fc09f90c9c791e7a500df98cfd2634700a9d6f83dc66eb8f72b3c0f8d20'

ct1 = ct.split('@@')[0].decode('hex')
ct2 = ct.split('@@')[1].decode('hex')
assert len(ct1) > len(ct2)

flag = 'UDCTF{'

#### guess (add the conditions) ####
pt2_011 = 'RED'
flag += strxor(pt2_011, ct2[11:14])
pt1_526 = 'HE'
flag += strxor(pt1_526, ct1[526:528])
pt2_016 = 'OPLE'
flag += strxor(pt2_016, ct2[16:20])
pt1_148 = 'E'
flag += strxor(pt1_148, ct1[148])
pt1_021 = 'AT'
flag += strxor(pt1_021, ct1[21:23])
pt2_023 = 'HAT'
flag += strxor(pt2_023, ct2[23:26])
pt2_154 = 'TER'
flag += strxor(pt2_154, ct2[154:157])
pt2_029 = 'TLE'
flag += strxor(pt2_029, ct2[29:32])
pt1_288 = 'UTE'
flag += strxor(pt1_288, ct1[288:291])

####################################

for i in range(128 - len(flag)):
    found = True
    for j in range(i, len(ct2), 128):
        try_pt1 = strxor(ct1[j:j+len(flag)], flag)
        if not is_uppercase(try_pt1):
            found = False
            break
        try_pt2 = strxor(ct2[j:j+len(flag)], flag)
        if not is_uppercase(try_pt2):
            found = False
            break
    if found:
        print '[+] %03d' % i, try_pt1, try_pt2

print '**********************************************************************'

for i in range(5, len(ct2), 128):
    try_pt1 = strxor(ct1[i:i+len(flag)], flag)
    try_pt2 = strxor(ct2[i:i+len(flag)], flag)
    print '[+] %03d' % i, try_pt1, try_pt2

print '[+] flag length:', len(flag)
print '[*] flag:', flag

最終的なコードで実行した結果は以下の通り。

[+] 005 INGONEOFTHEMINORVIRTUESWHICHWE THINGSHAPPENBUTWEBOBUPUNWELCOM
**********************************************************************
[+] 005 SEENOUGHTOKNOWTHATTHEREARESOME TAHUNDREDPEOPLEINTHATBATTLEKNE
[+] 133 SYOUORIWOULDHAVETHOUGHTATFIRST NDREDPEOPLEWERETHEBETTERFORTHE
[+] 261 HAVEDONEITTOONOTHINGCONTRIBUTE TABOUTITBUTTHEMOURNERSOFTHESLA
[+] 389 ISMOTHERSAYSSHEBELIEVESASHALFA GHEVERYMORNINUDCUREACHAPASWASM
[+] 517 INGONEOFTHEMINORVIRTUESWHICHWE THINGSHAPPENBUTWEBOBUPUNWELCOM
[+] flag length: 30
[*] flag: UDCTF{m3d1um_X0r_str3ng7h_f7w}

UDCTF{m3d1um_X0r_str3ng7h_f7w}