CTF中RSA套路

以前一直用的是http://bobao.360.cn/learning/detail/3058.html这里的,可是发现这里面好久没更新了,想了想还是自己在整理一下吧。

具体RSA加解密算法就不介绍了,先看数据提取吧。

需要注意的是,代码中很多地方用到了gmpy2库,安装方法参考https://www.cnblogs.com/pcat/p/5746821.html

数据提取

一般来说,RSA基本围绕着c,m,e,d,p,q,n这几个参数展开,但是题目一般不会直接给参数,需要我们自己手工提取。

  • pem文件:针对这类文件可以直接使用openssl提取,大概使用过的方式有:

    1
    2
    openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc
    openssl rsa -pubin -text -modulus -in warmup -in public.pem
  • pcap文件:针对这类文件可以使用wireshake follow一下。这种问题一般都是写了一个交互式crypto系统,可能产生多轮交互

  • ppc模式:这种模式是上述pcap文件的交互版,会给一个端口进行一些crypto的交互,参数会在交互中给出。

模数分解

已知e,p,q求d

1
d = gmpy2.invert(e, (p-1)*(q-1))


已知e,d,n求p,q

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
34
35
36
37
import random
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def getpq(n,e,d):
p = 1
q = 1
while p==1 and q==1:
k = d * e - 1
g = random.randint ( 0 , n )
while p==1 and q==1 and k % 2 == 0:
k /= 2
y = pow(g,k,n)
if y!=1 and gcd(y-1,n)>1:
p = gcd(y-1,n)
q = n/p
return p,q
def main():
n = 0xa66791dc6988168de7ab77419bb7fb0c001c62710270075142942e19a8d8c51d053b3e3782a1de5dc5af4ebe99468170114a1dfe67cdc9a9af55d655620bbab
e = 0x10001
d = 0x123c5b61ba36edb1d3679904199a89ea80c09b9122e1400c09adcf7784676d01d23356a7d44d6bd8bd50e94bfc723fa87d8862b75177691c11d757692df8881
p,q = getpq(n,e,d)
print "p: "+hex(p)
print "q: "+hex(q)
if __name__ == '__main__':
main()


在线分解n

http://factordb.com
通过在此类网站上查询n,如果可以分解或者之前分解成功过,那么可以直接得到p和q

yafu分解n


直接打开程序,然后输入factor($n),$n为模数,此方法比上面的在线要好用很多

公约数分解n

识别此类题目,通常会发现题目给了多个n,均不相同,并且都是2048bit,4096bit级别,无法正面硬杠,并且明文都没什么联系,e也一般取65537。可以直接gcd(n1,n2)求出一个因数。如下:

1
2
n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743

可以直接用公约数分解n,求得p,q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
print "p: "+str(gcd(n1,n2))
print "q1: "+str(n1/gcd(n1,n2))
print "q2: "+str(n2/gcd(n1,n2))


低加密指数攻击

e=3时的小明文攻击

当e=3时,如果明文过小,导致明文的三次方仍然小于n,那么通过直接对密文三次开方,即可得到明文。如果明文的三次方虽然比n大,但是大不了多少,则可以爆破。如下代码:

1
2
3
4
5
6
i=0
while 1:
if(gmpy2.root(c+i*N, 3)[1]==1):
print gmpy2.root(c+i*N, 3)
break
i=i+1


低加密指数广播攻击

如果选取的加密指数较低,并且使用了相同的加密指数给一个接受者的群发送相同的信息,那么可以进行广播攻击得到明文。
这个识别起来比较简单,一般来说都是给了三组加密的参数和明密文,其中题目很明确地能告诉你这三组的明文都是一样的,并且e都取了一个较小的数字。


低解密指数攻击

识别:e看起来特别大就行了
github上有开源的攻击代码https://github.com/pablocelayes/rsa-wiener-attack
这里注意一个细节问题,如果在运行脚本的时候报错,请在脚本前加上:

1
2
import sys
sys.setrecursionlimit(10000000)

题目:

1
2
3
4
5
6
7
8
9
10
11
12
Bob is extremely paranoid, so he decided that just one RSA encryption is not enough. Before sending his message to Alice, he forced her to create 5 public keys so he could encrypt his message 5 times! Show him that he still is not secure.
Here are the 5 public keys that Bob used, each in the format of (N, e):
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 11)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 41)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 67623079903)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 5161910578063)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 175238643578591220695210061216092361657427152135258210375005373467710731238260448371371798471959129039441888531548193154205671)
Here is his encrypted message:
7117565509436551004326380884878672285722722211683863300406979545670706419248965442464045826652880670654603049188012705474321735863639519103720255725251120

根据题意,用一样的n不同的e来加密5次,其实效果和用5个e的乘积加密一次是一样的。其实如果5个e的乘积来加密的话,e很大的话就可以用低解密指数攻击来了。

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
34
35
36
37
38
39
40
import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator
def hack_RSA(e,n):
'''
Finds d knowing (e,n)
applying the Wiener continued fraction attack
'''
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)
for (k,d) in convergents:
#check if d is actually the key
if k!=0 and (e*d-1)%k == 0:
phi = (e*d-1)//k
s = n - phi + 1
# check if the equation x^2 - s*x + n = 0
# has integer roots
discr = s*s - 4*n
if(discr>=0):
t = Arithmetic.is_perfect_square(discr)
if t!=-1 and (s+t)%2==0:
print("Hacked!")
return d
(n1,e1)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 11)
(n2,e2)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 41)
(n3,e3)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 67623079903)
(n4,e4)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 5161910578063)
(n5,e5)=(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 175238643578591220695210061216092361657427152135258210375005373467710731238260448371371798471959129039441888531548193154205671)
c=7117565509436551004326380884878672285722722211683863300406979545670706419248965442464045826652880670654603049188012705474321735863639519103720255725251120
e=e1*e2*e3*e4*e5%n1
d=hack_RSA(e,n1)
m=pow(c,d,n1)
print '{:x}'.format(m).decode('hex')

运行的时候如果报import包不存在,那是因为没有把https://github.com/pablocelayes/rsa-wiener-attack里面所有的py文件放在同一目录下。


共模攻击

识别:若干次加密,e不同,n相同,m相同。就可以在不分解n和求d的前提下,解出明文m。
已知e1,e2,n,c1,c2

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
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1<0:
s1 = - s1
c1 = modinv(c1, n)
elif s2<0:
s2 = - s2
c2 = modinv(c2, n)
m=(pow(c1,s1,n)*pow(c2,s2,n)) % n
print '{:x}'.format(m).decode('hex')


已知dp,dq求解

其实这种方法很简单,但是由于我当时做的时候查了好久dp,dq是什么,所以还是记录下来扫个坑吧。
这种参数是为了让解密的时候更快速产生的,其中:

1
2
dp=d%(p-1)
dq=d%(q-1)

解密全部代码如下:

1
2
3
4
5
InvQ=gmpy2.invert(q,p)
mp=pow(c,dp,p)
mq=pow(c,dq,q)
m=(((mp-mq)*InvQ)%p)*q+mq
print '{:x}'.format(m).decode('hex')


隐藏小私有指数δ的RSA后门密钥生成算法

以下题目来自于hctf2016
http://0x48.pw/2016/11/28/0x28/
https://github.com/Hcamael/ctf-library/tree/master/RSA1
https://github.com/Hcamael/ctf-library/blob/master/RSA1/rsa1_payload.py
算法原理如下:

攻击方法也很简单

解题关键是在下图


根据rsa-wiener-attack我们可以知道,在rsa算法中,如果密钥d特别小,则我们可以根据e,n直接求出d,所以上图满足条件。

而当我们求出了那两个东西(原谅我打不出来…),则和已知e,d,n求p,q的情况一样了,当p,q已知的时候就可以解出d了

基于隐藏素数因子的RSA-HPβ算法(高比特位已知分解)

以下题目来自于hctf2016
https://github.com/Hcamael/ctf-library/tree/master/RSA2
payload:

1
2
https://github.com/Hcamael/ctf-library/blob/master/RSA2/rsa2_payload.py
https://github.com/Hcamael/ctf-library/blob/master/RSA2/rsa2_payload.sage

该后门算法依赖于Coppersmith partial information attack算法, sage实现该算法,sage安装详细看我的另一篇关于sage的安装。

Coppersmith partial information attack算法可以理解成,当我们已知素数p或者q的前一定位数,可以根据这个算法还原完整的p,q。
算法实现代码:https://github.com/Gao-Chuan/RSA-and-LLL-attacks

例题如下:

仔细观察算法,n是靠t,u,r来拼接成,而u是根据p的前5k/16位进行des转置得到的,所以当我们已知n的前提下,相当于我们已知p的前5k/16位。这就是我们利用的点。如下图:

利用代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
p4 = 0xf3a5f928e11c5901f9f4289e513f046748efb99d4f8e706e207a943e1d2c9df43feab38e20c2106d87167e5501ac41adfc4912732457103a4359e5b433da78f39ad6f206b8f170192aa0841feb501ce1
n = 0x7e7007c7c85788b9b77cda64c9b3f5d2a795fe1b1f8d3f120288a30a168c3ea932c7574700ff0f596c5ad04a703756aedc66b9b9e44911d55f0a72a1cc1a569cee02a84499cdb091b8471a8e6cc0ebca583dfd6fb8d5fecf32ff67d2ddeaaaaf9c71a10009b4218fc57743675f283d22734ac7ade2ca240772d11b5783755378f7c30988f41d4a9d62561ea6e5f2f21d3d44e8689e781d3f61356123929457d17b07a1d04741bf970afb590cd820dd12cf88f68b0e896388f433fd2adf3354353c9c56abb0cfea223387e6d0b2df10e450c621ac153e47369f888fdc0b39c842a5ddc6a11339862ccdb4be97a81445205fb8f8bde9daaad5d0dc2ea5bd3b8c43
//p的位数
pbits = 1024
//p未知的位数
kbits = pbits - p4.nbits()
print p4.nbits()
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
//f是原始的p
f = x + p4
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
print "x: %s" %hex(int(x0))
p = p4+x0
print "p: ", hex(int(p))
assert n % p == 0
q = n/int(p)
print "q: ", hex(int(q))



第二届强网杯_nextrsa_Coppersmith

题目描述是,加密指数e=3,同时已知明文的高位,参数如下:

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

其中不知道的就是64比特的x,不过根据以下代码就可以算出x:

1
2
3
4
5
6
7
8
9
10
e = 0x3
b = b=0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
n = 0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d
c=0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e2b34e5b175af25d5b3bd71db88b3b31e48a177a469116d957592c
kbits=64
PR.<x> = PolynomialRing(Zmod(n))
f = (x + b)^e-c
x0 = f.small_roots(X=2^kbits, beta=1)[0]
print "x: %s" %hex(int(x0))

强网杯_nextrsa_nextprime

参数如下:

1
2
3
4
# n=0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5518fa1d0c159621e1f832b474182593db2352ef05101bf367865ad26efe14fce977e9e48d3310a18b67991958d1a01bd0f3276a669866f4deaef2a68bfaefd35fe2ba5023a22c32ae8b2979c26923ee3f855363f18d8d58bb1bc3b7f585c9d9f6618c727f0f7b9e6f32af2864a77402803011874ed2c65545ced72b183f5c55d4d1
# e=0x10001
# nextprime(p)*nextprime(q)=0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5a58ee70a59ac06b64dbe04b876ff69436b78cf03371f2062707897bf4e580870e42b5e62709b69f6d4939ac5641ea0f29de44aaee8f2fcd0f66aaa720b584f7c801e52ce7cd41db45ceb99ebd7b51bef8d0cd2deb5c50b59f168276c9c98d46a1c37bd3d6ef81f2c6e89028680a172e00d92dd8b392135112dd16efab57d00b26b9
# c=0x1c3588ac81ec3d1b439cfd2d5e6e8a5a95c8f95aaeff1b0ba49276ade80435323f307a17006ae2ffb4ca321e54387d9b33ed7ccda3117f7bc8d247ffd2ccdd67b7e2aad3d908d0a5187a73d13d532c1cf41758e2743bd4359bf72a99bbf0d716bb171cf636bd56acee9551cbb8af25f32583facbd25aed232659d24580c5a30a080e2860790a65422f7c442559c3042d37fdd7e8c1dd604252a2cbff8c74e5a0b6a0dfb9dcfed9eed515705ab9214dcf2dabce7b354040940613d065918079b3197da948b6d1d7daccc417069f7102fd2525e879fe69b6d5fb39e1dd6c0a9a9087dcc809294d7774efb42829f6124dff4af44f308977d1f91422c63073176026

方法一:

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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
__Auther__ = 'M4x'
from gmpy2 import is_prime as prime
from gmpy2 import iroot
n = 15260473398916071686287752340249158279343013077145667794514717692352941873466690686288442204714585854869226872705293008837554012949598044297596015507031315006195230644722581744643756573982729344499452200116366327869178694692162014446578711956663348262932703160394101606708475725742890049311933691849747707673216322758418530420118502556719323543077771821163439824876751874675862075401986796272014746925015772045578403357300038192830197985871077621213669817380577176611560467051848951044963527185916781094981810804641387975398361694935093473717039550361644252381923994841138817152748279477868854093033234031994635408593
nn = 15260473398916071686287752340249158279343013077145667794514717692352941873466690686288442204714585854869226872705293008837554012949598044297596015507031315006195230644722581744643756573982729344499452200116366327869178694692162014446578711956663348262932703160394101606708475725742890049311933691849747707914818082716474881224336472709074679047145667796106895298086129057288449508218237679974321952279429832707229303594474494519945899481320231091983665654947081839784375373657345023890332691371443571370016623789041883821610353473726465037590414008198228956920913181526550775524028059426312173493877228564452496582329
# print nn > n
t = nn - n
f1 = lambda x, y: pow(x * y - t, 2) - 4 * n * x * y
f2 = lambda x, y, s: (t - x * y - s) / (2 * x)
for x in xrange(1, 3000):
for y in xrange(1, 3000):
print x, y
if f1(x, y) >= 0:
s, b = iroot(f1(x, y), 2)
if b:
if prime(f2(x, y, int(s))):
print "Success"
print f2(x, y, int(s))
exit()

就是

1
2
3
4
5
6
7
pq = n
(p + x)(q + y) = n'
-> xy + py + qx = t(t = n' - n)
-> xq^2^ + (xy - t)q + ny = 0
则该方程有素数接即可,可爆破x,y

方法二:
因为n = p * q,nn = p1 * q1
因为n和nn很相近,所以nnn讲道理用yafu很快就能跑出来
可以得到`t1 = p
q1,t2 = q*p1 `
然后gcd一下就可以了

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 数据提取
  2. 2. 模数分解
  • 已知e,p,q求d
  • 已知e,d,n求p,q
  • 在线分解n
  • yafu分解n
  • 公约数分解n
    1. 1. 低加密指数攻击
  • e=3时的小明文攻击
  • 低加密指数广播攻击
    1. 1. 低解密指数攻击
    2. 2. 共模攻击
    3. 3. 已知dp,dq求解
    4. 4. 隐藏小私有指数δ的RSA后门密钥生成算法
    5. 5. 基于隐藏素数因子的RSA-HPβ算法(高比特位已知分解)
    6. 6. 第二届强网杯_nextrsa_Coppersmith
    7. 7. 强网杯_nextrsa_nextprime
  • ,