CTF-RSA基本破解姿势
0x01 信息提取
提取信息:
1 | openssl rsa -pubin -text -modulus -in pubkey.pem |
or:
1 | import base64 |
0x02 N的分解
0x01 在线分解
n不是特别大时:
1 | n=0xc4606b153b9d06d934c9ff86a3be5610266387d82d11f3b4e354b1d95fc7e577 |
尝试在线网站分解n:
1 | http://factordb.com/ |
0x02 yafu分解
当p,q相差过大或过小:
尝试使用yafu:
1 | yafu-x64.exe "factor(@)" -batchfile ./file_n |
file_n中保存了n
注意./file_n结尾需要换行,否则会报错
0x03 msieve153分解
当n不是太大时,也可以尝试msieve153分解:
1 | msieve153.exe [N] -v |
解密
分解后解密脚本:
1 | from gmpy2 import invert |
0x03 特殊情况下的RSA破解
0x01 RSA Wiener Attack
当e很大时:
1 | n=0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1 |
尝试wiener attack求出d
(具体wiener attack使用方法见github(对于一些分解,直接修改RSAwienerHacker.py即可)):
1 | https://github.com/pablocelayes/rsa-wiener-attack |
1 | m=pow(c,d,n) |
0x02 共模攻击
一个n,多组c,e
尝试采用共模攻击:
1 | from hashlib import sha256 |
0x03 广播攻击
一个e,多组n,c
尝试采用广播攻击:
1 | from gmpy2 import invert, iroot |
0x04 N的公约数分解
多组N,尝试公约数分解N:
1 | from libnum import gcd |
0x05 低加密指数攻击
只有一组且e比较小
低加密指数攻击:
例:
1 | n=0x7003581fa1b15b80dbe8da5dec35972e7fa42cd1b7ae50a8fc20719ee641d6080980125d18039e95e435d2a60a4d5b0aaa42d5c13b0265da4930a874ddadcd9ab0b02efcb4463a33361a84df0c02dfbd05c0fdc01e52821c683bd265e556412a3f55e49517778079cb1c1c1c22ef8a6e0bccd5e78888ff46167a471f6bff25664a34311c5cb8d6c1b1e7ac2ab0e6676d594734e8f7013b33806868c151316d0cf762a50066c596244fd70b4cb021369aae432e174da502a806e7a8ab13dad1f1b83ac73c0e9e39648630923cbd5726225f17cc0d15afadb7d2c2952b6e092ffc53dcff2914bfddedd043bbdf9c6f6b6b5a6269c5bd423294b9deac4f268eaadb |
1 | from gmpy2 import iroot |
0x06 明文高位已知
已知n,c,e和明文的高位
可以参考:
1 | https://github.com/mimoo/RSA-and-LLL-attacks |
例:
1 | n=0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d |
sagemath下解密:
1 | n = 0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d |