SECCON Beginners CTF 2018 Crypto Writeup(+2) Crypto道場②[4/100]

どうも。duckです。
happy!解くのは明日にさせてください。
昨日上げようとしてたやつ先にあげちゃいます。

1.[Warmup] Veni, vidi, vici
fileが３つあったらしい。

#part1
Gur svefg cneg bs gur synt vf: pgs4o{a0zber

#part2
Lzw kwugfv hsjl gx lzw xdsy ak: _uDskk!usd_u

#part3
{ʎɥdɐɹɓ0ʇdʎᴚ :sı ɓɐlɟ ǝɥʇ ɟo ʇɹɐd pɹıɥʇ ǝɥ⊥

part1,2はceaser暗号なので昔作ったpythonファイルにぶち込むとすぐ答えが出た。
(そのうちgitにあげる予定)

part3は自力で反転した。

flag:ctf4b{n0more_cLass!cal_cRypt0graphy}

2.RSA is Power

次のファイルが渡されたらしい。

RSA暗号ですね。

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

Nの桁数を数えてみたら77桁だった。bit数に換算すると
$77*\log_{10}2 \approx 256$
256bitとNが非常に小さいので素因数分解攻撃が有効である。

from Crypto.Util.number import long_to_bytes

def gcd(a,b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

#ax+by=gcd(a,b)の解[x,y]
def extend_gcd(a,b):
    k_list=[]
    while b != gcd(a,b):
        r = a % b
        k_list.append((a - r) // b)
        a = b
        b = r
    k_list.reverse()
    y = 1
    x = 0
    for k in k_list:
        temp_y = y
        y = x - k * temp_y
        x = temp_y
    return [x,y]

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

p=299681192390656691733849646142066664329
q=324144336644773773047359441106332937713
phi=(p - 1)*(q - 1)

d = int(extend_gcd(phi,E)[1]) % phi
print(long_to_bytes(pow(C,d,N)))