Hackover CTF 2015: radorium

,

https://github.com/ctfs/write-ups-2015/tree/master/hackover-ctf-2015/crypto/radorium

sshの公開鍵がたくさん与えられるので、秘密鍵を作る問題。 gcdを取ってみれば互いに素でない組が見つかる。 実際のssh鯖が落ちているので見つけただけで終わりにするが、秘密鍵を作ってちゃんとloginする部分はちょっと面倒そう。

#!/usr/bin/env python3
import base64
import math

keys = []
with open('message.txt') as fh:
    for line in fh:
        line = line.strip()
        if line.startswith('ssh-rsa ') and line.endswith([email protected]'):
            _, s, user = line.split()
            s = base64.b64decode(s)
            s = s[ s.index(b'ssh-rsa') + len('ssh-rda') : ]
            l = int.from_bytes(s[: 4], 'big')
            e = int.from_bytes(s[4 : 4+l], 'big')
            r = int.from_bytes(s[4+l : 4+l+4], 'big')
            m = int.from_bytes(s[4+l+4 : 4+l+4+r], 'big')
            assert e == 0x10001
            keys += [(l, e, r, m, user)]

for _, _, _, m1, user1 in keys:
    for _, _, _, m2, user2 in keys:
        if m1 < m2 and math.gcd(m1, m2) != 1:
            p = math.gcd(m1, m2)
            q1 = m1 // p
            q2 = m2 // p
            print('(p, q) = ({}, {}) for {}'.format(p, q1, user1))
            print('(p, q) = ({}, {}) for {}'.format(p, q2, user2))
$ ./a.py
(p, q) = (18009693508862469906115874440480265166561160295809859489336654048468359768525445177013883145324327097708045894275326410026731952547197584476160121816734131387014991005323013576751539102770837863492732969595516022077729616402557178595603621724844579271807129661352610464230511219308181198560241172473750519797, 51298003120871478983717117589858640626012977851245661263743991742024877574155860752821559553850408906692866529175965537240767998090190354414685747176726550819198701295936366053352395872509931879219991915928631502854553809431626717096659346689628408458954999365146321328348448677926179496427051542622086999323) for [email protected]
(p, q) = (18009693508862469906115874440480265166561160295809859489336654048468359768525445177013883145324327097708045894275326410026731952547197584476160121816734131387014991005323013576751539102770837863492732969595516022077729616402557178595603621724844579271807129661352610464230511219308181198560241172473750519797, 132192685775643347814581273449525980264082315545799841587539287116234234152628556942423799518041047832527692576347497396799659399167007353913261542406554403831800950893096971682716431356190244713302442824846652168348164392026951494909983630968696331495194096154001647753792031798459925887513938654848471220327) for [email protected]
./a.py  12.42s user 0.02s system 99% cpu 12.443 total