Hack The Vote 2016 | BabyHands (crypto 300pt)

solver.py

# filename: solver.sage

#f = open("intercepted", "r")
#
#f.readline()
#
#for line in f:
#    d, n, c = map(int, line.strip()[1:-1].split(":"))
#    print d, n, c
#
#f.close()

e = 64193765095472280945778947695026260940793161700792092928929371930940586875921621250436677664062645637750266086941620369817913432656342447118119648040487568561166129534408858429501807430550886328164336961068507005046531729954378900389289038547121166749974617776234380115780563231906876010653549490718147637109
n = 162375468556255342840184380017752307049575955143811124651668179546999144455415632265862602514386409412258772643790637233144774447636694664087397175482938958661142022166864007317692608104513835959387316735889741416403005613839667775733147723497537341613995375357897642024075069112712472560335406551536669543677
c = 161368580245997137625438248139098888389801359838792140099794084052829279383422322670122662786704858201672541232233171127388341066584896672407182421832728901923771676356720611937864219195771372253188974650818854505110963737925290199983571032857746780899310446337006151661497839040062867489758146326490061720009

# Wiener's Attack
c_fracs = continued_fraction(e / n).convergents()

test_plain = 100
test_cipher = pow(100, e, n)

for i in xrange(len(c_fracs)):
    if pow(test_cipher, c_fracs[i].denom(), n) == test_plain:
        d = c_fracs[i].denom()
        break

plain = pow(c, d, n)

print hex(int(plain))[2:-1].decode("hex")

# flag{G3t_1t?_1t_h4s_4_sm4ll_d}

RSAのd, n, cのペアが渡され、eの値を求める必要がある。dが大きいとeが相対的に小さくなることを利用して逆Wiener's Attackを行うとeが求まる。Sageを使うと容易に連分数の計算ができる。