RSA暗号解読問題を解く(後編)[CTF for Beginners 2018]"RSA is Power"
経緯
これの続き。
ちょっとだけ巻き戻しで、まず問題に与えられている数字は以下
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(([モジュラとする数],[公開鍵にする数],[秘密鍵にする数]))