ctf4b 2018 write up

RSA is Power

問題文として下記が与えられる

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

N　=　p * q を求める

https://factordb.com/
にNを入れてあげる

p = 299681192390656691733849646142066664329
q = 324144336644773773047359441106332937713

p,q長いから16進数に変換

p = 0xe1747f8b4fe5236cec869cd855de2389
q = 0xf3dbedad3eeac8f64d1c6b4fde21edf1

dを求める

from Crypto.Util.number import inverse

p = 0xe1747f8b4fe5236cec869cd855de2389
q = 0xf3dbedad3eeac8f64d1c6b4fde21edf1
e = 0x10001 #eも一応16進数に変換しておく
n = p * q
d = inverse(e, (p-1)*(q-1))
print(d)

こうなる

q = 0xe1747f8b4fe5236cec869cd855de2389
p = 0xf3dbedad3eeac8f64d1c6b4fde21edf1
n = p * q
e = 0x10001
c = 0xab09082bd950ae6f62502c9bfeb948d48a45d00afae58a064864d00c53faaab4
d = 0xc3ae54812ff39e5dc840ace1e2026032b2534e89f14d21db76d812b3046ccf01

値が長いから16進数に変換した.

復号

よっちんのブログ
をもとにコードを組んでいく

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

plaintext = decrypt(p, q, e, c)
print(plaintext) # ctf4b{5imple_rs4_1s_3asy_f0r_u}

参考

• よっちんのブログ

最後に

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

plaintext = decrypt(p, q, e, c)
print(plaintext)

はpython2だから3では実行できない.
私はpaizaに投げた.