ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

InCTF2017 Write-up

InCTFにHarekazeとして参加しました.
最終的に2701p獲得し, 全体で5位でした(全体156チーム).
うち僕は3問解いて450p取得しました. Write-upです.


[Crypto 100] Multi Layer RSA
RSA1問目です.

p = getPrime(512)
q = getPrime(512)
n = p*q
phin = (p-1)*(q-1)

encryption_keys = [34961, 3617491, 68962801, 293200159531, 1191694878666066510321450623792489136756229172407332230462797663298426983932272792657383336660801913848162204216417540955677965706955404313949733712340714861638106185597684745174398501025724130404133569866642454996521744281284226124355987843894614599718553178595963014434904833]

for i in encryption_keys:
    assert GCD(i,phin) == 1

for i in encryption_keys:
    flag = pow(flag, i, n)

flag = hex(flag)[2:].replace("L","")

n = 135568509670260054049994954417860747085442883428459182441559553532993752593294067458983143521109377661295622146963670193783017382697726454953197805014428888491744355387957923382241961401063461549210355871385000347645387907568135032087942016502668629010859519249039662555733548461551175133582871220209515648241

c = 0x5d695edb47b81a303d162611f7d407579160ef8818929031e1e13ca20cb7094eddbb0658d95980e1753182c5d5c529fb45062891bb5da573c618e35df0103233ded582a53ed807846b19ea82be427f2bbc63e5c7eb685d8a22b2b7539cf45d4ad93bbf5b892b66288b568b6bbff6bb263d809475e6f0aa3cfd01539d8364c243

複数のeを使ってフラグを5回暗号化しています.
暗号化の式を立てます.

[e1, e2, e3, e4, e5] と それに対する暗号文を [c1, c2, c3, c4, c5] とすると

c1 = m ^ e1 mod n
c2 = c1 ^ e2 mod n
c3 = c2 ^ e3 mod n
c4 = c3 ^ e4 mod n
c5 = c4 ^ e5 mod n

これを一つの式にまとめると
c5 = m ^ e mod n; e = e1 * e2 * e3 * e4 * e5

eがnに対してかなり大きくなるためWiener's Attackが使えます.

[Crypto 150] RSA 1s fun
RSA2問目です.

e1 = 9
e2 = 123

def prime_gen():
    while True:
        p = getPrime(1024)
        q = getPrime(1024)
        n = p*q
        phin = (p-1)*(q-1)
        if GCD(e1, phin) == 1 and GCD(e2, phin) == 1:
            return (p, q, n)
p, q, n = prime_gen()

print "p: ", p
print "q: ", q
print "n: ", n

flag = bytes_to_long(open("flag.txt").read().strip())
assert flag < n
assert flag**9 > n

c1 = pow(flag, e1, n)
c2 = pow(flag, e2, n)

c1=2866791410300982209581160682590202727064178543076468723716078826950532969157774101954514922479283214185175373229881780072369520438740798302436630031675039672300318769368767955792505592752805860745234692545366181568007521937632340018956679380260500802782833711686141651664082139115158618826168145286856348145354753632046650620308808972739953286345861292290201731165641142066561682325108497439840996007817718867058397591772543642180750091195001088272756689038764789254056479422278248719908521586989566666627884968909640431124163896764204393560913490590077031435330210539197147863375903077038431543732467897239841303254

c2=4885380046320959173192546343078276684691332256383912605057298042587886299857925359111993638346079742855901548480637616739859552612594516195353274413384196031117800323365020227270534113077873495873427630043665909900269079429369278616380093363461750865151600963795982366459803668193824090785941635118091474660341873110737939523053889456794499981099067016285308979086542807431649241746997853017895403122499239437959257317791355670927392439947971693686626563871460473615495733407552262810140872942644864039949040024604157449691762976155356244948844966532675041107842219829093528089233085580060616519775692376829287486898

n = 20333254691880587307936337314043639948842015851766398721090407302956251747329178671065731363354242526918246592697537469440013326971933436283835869953205389270794974354649936678036319060756577261022556782132429409780897209149764199287410299784057084352324514504271696413494646839995519846723688986124055120364880326007695589111754397828528457250142219463380016968678118831245509936377859985508548247011183090952083546525956426331360929466685835043639197893823027068509935334942858316357902671524385521979877692725137825489358188564620960020623845798362737725511832599703350407211941298094845205725160096135130216181313

2つのeと同一のnを使って暗号文を2つ出力しています.
今回1つめのeが9(eが小さい)なのでc1の9乗根を取ればフラグが得られる可能性もありますが, assert flag**9 > n によって防がれています.

CommonModulesAttackが使えますが, 解法としてはCodeblueのCommonModules2と同じです.

e1*s + e2*t = GCD(e1, e2) となる (s, t) の組み合わせを探します.
今回の場合 GCD(9, 123) = 3 なので, 得られる平文は m3 です.
3乗根を取ってあげましょう.

First Solverでした.

[Crypto 200] Crafted RSA
RSA3問目です.

seed = 0

def genPrime(sz):
    global seed
    while True:
        if seed == 0:
            pr = getPrime(sz)
            while size(pr) < 1024:
                pr *= getRandomNBitInteger(16)
            i = 2
            while i<1000 and size(pr)==1024:
                if isPrime(pr+i) and size(pr+i) == 1024:
                    seed = pr+i
                    return pr+i
                i += 1
        else:
            pr = seed + random.randint(2**100,2**300)
            if isPrime(pr) and size(pr) == 1024:
                seed = pr
                return pr

p = genPrime(num_size)
q = genPrime(num_size)
e = 2**16 + 1

n=16597712262800095098226130512282927179497011173406539443409876664765634654792363184411825406484837021057998483611151825837103388795480529002121502546121948928066281359031028270878297218661409934035886546020930964028780335737680348596910306513206117504108058925329858396067856573163592825383960058578681644875980180546847557812966223271765120162910255137784213094212309609759257353674875979882725784871783757837297703281196379092511265281287845023919390729682379344606965288462358145824117145872183931465422694130609005144944508184194344888497580577863328136806345023037939204996365581479722451260520977982655414777159

c = 0x6444941f812bd69f57dd94579532e52230e0cb6c3990e6bed0f19950e30126afe92baf35db0ee64cc8d59443b2bff99574142bdab354400ea19ef309b37b946d18e4d003ab63c159cebd7f954867f7a82e1d44082d8d63e1fea874f3793ab56c28b2d66eb054edd3520bf60f70806d8c49e8f80200dd33943376042ee324d425c612b7ab7a52bd86b42e6f485ce19b83db156a6ea42ba8d90ca348f444887f230672bd90d673a36250476a5c3e1413fc09862007f4fee942dcf1ec45ae7fd04ab829bde3f3d3e1ee562a2c7ecfd98b345f87cfe1f6cff67c81c7d23c659cd29660376f4b64fa592dd17695124818e95ce8b09f4f24d9d9f05cf929237eac3dff


素数の生成に自前の関数を使用しています.
1回目の呼び出し(p)の時は seed == 0 で2回目の呼び出し(q)に seed != 0 となっています.
ちゃんと解析はしていませんが, p と q はもしかするとnの平方数付近(pとqの差が小さい)なのではないかと思いフェルマー法で素因数分解しました.



150, 200, 100の順で解きました(100問題で勘違いしていたので時間かかった).
GiantXORも解きたかったです.