Mawa Town

Mawaという人が作る小さな町でMawaTownです。技術と音楽が好き。

RSA暗号解読問題を解く(後編)[CTF for Beginners 2018]"RSA is Power"

f:id:k_mawa:20180619141331p:plain

経緯

これの続き。

k-mawa.hateblo.jp

ちょっとだけ巻き戻しで、まず問題に与えられている数字は以下

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

前回、素因数分解パッケージのmsieveの計算パワーで、素因数のペアが、299681192390656691733849646142066664329と324144336644773773047359441106332937713になるということころまでわかりました。

さてその続き。

pycryptoを使う

インストールが必要

$ pip install pycrypto

これでよし。

さて計算。まずわかっている数を書く。

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316
p = 299681192390656691733849646142066664329
q = 324144336644773773047359441106332937713

公開鍵から秘密鍵をつくる

#pycryptoをインポート
from Crypto.PublicKey import RSA
from Crypto import Random
from Crypto.Util.number import * #inverse()を使う
import Crypto.PublicKey.RSA as RSA

>>> inverse(E,(p-1)*(q-1))
88509020092584531671107468782943602124921999287671161687233461555074737950465

d = inverse(E,(p-1)*(q-1))

>>> d
88509020092584531671107468782943602124921999287671161687233461555074737950465

#秘密鍵
  • pycryptoのinverse()について
inverse()
秘密鍵 = inverse([公開鍵にする数], [(p - 1) * (q - 1)])

inverseが何をしているかはこれを。 https://asecuritysite.com/encryption/inve?val1=17&val2=3120

秘密鍵で暗号化された文章を復号

rsa_key = RSA.construct((p*q, E, d))
#もちろんrsa_key = RSA.construct((N, E, d))でもOK

>>> rsa_key
<_RSAobj @0x10f7b06a0 n(256),e,d,p,q,u,private>

>>> rsa_key.decrypt(C)
175721217420599820463601725034319415104774797848891230924248444157707646333

int = rsa_key.decrypt(C)

>>> long_to_bytes(int)
b'ctf4b{5imple_rs4_1s_3asy_f0r_u}'

解けた!!

  • pycryptoのRSA.construct()について
RSA.construct
RSA = RSA.construct(([モジュラとする数],[公開鍵にする数],[秘密鍵にする数]))

参考記事

SECCON Beginners CTF 2018 Write-up

zeosutt.hatenablog.com