CTF-RSA基本破解姿势

CTF
, ,

0x01 信息提取

提取信息：

1
openssl rsa -pubin -text -modulus -in pubkey.pem

or：

1
2
3
4
5
6
7
8
9
10
11
12
13
import base64
from Crypto.PublicKey import RSA
from libnum import n2s,s2n
from gmpy2 import invert

pub = RSA.importKey(open('pubkey1.pem').read())
n= long(pub.n)
e= long(pub.e)
ce= base64.b64decode(open('flag1.enc','rb').read())
c=0
for x in ce:
    c= c << 8
    c=c + ord(x)

0x02 N的分解

0x01 在线分解

n不是特别大时：

1
2
3
n=0xc4606b153b9d06d934c9ff86a3be5610266387d82d11f3b4e354b1d95fc7e577
e=0x10001(65537)
c=0xa87fc50517b50db03a038c93c2a2c2c36de67660920da8720b787fedc3e19dd9

尝试在线网站分解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
2
3
4
5
6
7
8
9
10
11
12
13
from gmpy2 import invert

n=
e=
c=#int("".decode("base64").encode("hex"),16)
p=
q=
def rsa(n, p, q, e, c):
    d = invert(e, (p - 1) * (q - 1))
    m = pow(c, d, n)
    print hex(m)[3:].decode("hex")

rsa(n, p, q, e, c)

0x03 特殊情况下的RSA破解

0x01 RSA Wiener Attack

当e很大时：

1
2
3
n=0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1
e=0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46f
c=0x2add7528efe278a70a43f97fc5af83bbaab1238364735d998de005d7feb1a8ab931c7410f0f785db455857b8154a68de318bfffd2099c5b06d6a5e859b3812752e0c28dd626dfa1c26e1dbf8bc43686de75863da5f9df96331d81302cb6269e9d71661b03910726db6add3b8b2f7629cc981800f88376ae5541b0e6b072a72bd22505cde978b5a8433c7279407083d585cc6e0d74bff7e1a62b1e895fccc0144145528f3c32433a1a66cb85fb16749ac1e9ff176bedf8fbf2157a616bcd8e457e7ac571df1c8e07b31c8eaa47f01dee15367389ea0d0e40fc58f2a2658d220922b046eb1fb78e99ccb4c166c9cf5750a91b17b21ef8d80a131466ed98e5c4d4a

尝试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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from hashlib import sha256
from gmpy2 import invert, iroot
from libnum import xgcd, invmod

def commonN(n, e1, c1, e2, c2):
    s1, s2, _ = xgcd(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = invmod(c1, n)
    if s2 < 0:
        s2 = -s2
        c2 = invmod(c2, n)
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    return m

n = 
c1 = 
c2 = 
e1 =
e2 = 
print commonN(n,e1,c1,e2,c2)

0x03 广播攻击

一个e，多组n,c
尝试采用广播攻击：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from gmpy2 import invert, iroot
from libnum import xgcd, invmod

def broadcast(n1, n2 ,n3, c1, c2, c3):
    n = [n1, n2, n3]
    C = [c1, c2, c3]
    N = 1
    for i in n:
        N *= i

    Ni = []
    for i in n:
        Ni.append(N / i)

    T = []
    for i in xrange(3):
        T.append(long(invert(Ni[i], n[i])))

    X = 0
    for i in xrange(3):
        X += C[i] * Ni[i] * T[i]

    m3 = X % N
    m = iroot(m3, 3)
    return m[0]

n1=
c1=
n2=
c2=
n3=
c3=
print  broadcast(n1, n2 ,n3, c1, c2, c3)

0x04 N的公约数分解

多组N，尝试公约数分解N：

1
2
3
4
5
6
7
8
from libnum import gcd

n1=
n2=

print "p -> {}".format(gcd(n1, n2))
print "q1 -> {}".format(n1 / gcd(n1, n2))
print "q2 -> {}".format(n2 / gcd(n1, n2))

0x05 低加密指数攻击

只有一组且e比较小
低加密指数攻击:
例：

1
2
3
n=0x7003581fa1b15b80dbe8da5dec35972e7fa42cd1b7ae50a8fc20719ee641d6080980125d18039e95e435d2a60a4d5b0aaa42d5c13b0265da4930a874ddadcd9ab0b02efcb4463a33361a84df0c02dfbd05c0fdc01e52821c683bd265e556412a3f55e49517778079cb1c1c1c22ef8a6e0bccd5e78888ff46167a471f6bff25664a34311c5cb8d6c1b1e7ac2ab0e6676d594734e8f7013b33806868c151316d0cf762a50066c596244fd70b4cb021369aae432e174da502a806e7a8ab13dad1f1b83ac73c0e9e39648630923cbd5726225f17cc0d15afadb7d2c2952b6e092ffc53dcff2914bfddedd043bbdf9c6f6b6b5a6269c5bd423294b9deac4f268eaadb
e=0x3
c=0xb2ab05c888ab53d16f8f7cd39706a15e51618866d03e603d67a270fa83b16072a35b5206da11423e4cd9975b4c03c9ee0d78a300df1b25f7b69708b19da1a5a570c824b2272b163de25b6c2f358337e44ba73741af708ad0b8d1d7fa41e24344ded8c6139644d84dc810b38450454af3e375f68298029b7ce7859f189cdae6cfaf166e58a22fe5a751414440bc6bce5ba580fd210c4d37b97d8f5052a69d31b275c53b7d61c87d8fc06dc713e1c1ce05d7d0aec710eba2c1de6151c84d7bc3131424344b90e3f8947322ef1a57dd3a459424dd31f65ff96f5b8130dfd33111c59f3fc3a754e6f98a836b4fc6d21aa74e676f556aaa5a703eabe097140ec9d98
1
2
3
4
5
6
7
8
9
10
11
12
13
from gmpy2 import iroot

n=
e=
c=

i = 0
while True:
    if iroot(c + i * n, 3)[1] == True:
        print "Success!"
        print iroot(c + i * n, 3)
        break
    i += 1

0x06 明文高位已知

已知n，c，e和明文的高位
可以参考：

1
2
https://github.com/mimoo/RSA-and-LLL-attacks
http://inaz2.hatenablog.com/entry/2016/01/20/022936

例：

1
2
3
4
5
n=0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d
e=0x3
c=0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e2b34e5b175af25d5b3bd71db88b3b31e48a177a469116d957592c
b=0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
m=b+x (x:64bit)

sagemath下解密：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = 0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d
e = 3

m = randrange(n)
c = pow(m, e, n)

beta = 1
epsilon = beta^2/7

nbits = n.nbits()
kbits = floor(nbits*(beta^2/e-epsilon))
#mbar = m & (2^nbits-2^kbits)
mbar = 0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
c = 0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e2b34e5b175af25d5b3bd71db88b3b31e48a177a469116d957592c
print "upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)

PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c

print m
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n
print mbar + x0
print x0