复现StarCTF2022的一道Crypto题-ezRSA
潜心 2022-7-21 CryptoRSA已知p高位攻击StarCTF2022
# ezRSA
from Crypto.Util.number import getStrongPrime
from gmpy import next_prime
from random import getrandbits
from flag import flag
p=getStrongPrime(1024)
q=next_prime(p^((1<<900)-1)^getrandbits(300))
n=p*q
e=65537
m=int(flag.encode('hex'),16)
assert m<n
c=pow(m,e,n)
print(hex(n))
#0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
print(hex(c))
#0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 官方Writeup
starctf2022/crypto-ezRSA at main · sixstars/starctf2022 (github.com) (opens new window)
sqrt(n) for high bits. Use xor relationship to get middle bits. Partial p to get the rest.
对N开方得到p的高位，异或关系得到p中间几位，coppersmith得到p的低位。
from Crypto.Util.number import *
n=0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
c=0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
p = (1<<900)-(1<<300)
q = 1<<300-1
PR.<x> = PolynomialRing(Zmod(n))
pm=int(sqrt(n))>>900
p = (1<<900)-1
q = 1<<300-1
p+=pm*(1<<900)
q+=pm*(1<<900)
#in the rest place, '1' either belong to p or q
for i in range(898, 301, -1):
cur = 1<<i
if (p^^cur) * (q^^cur) < n:
p ^^= cur
q ^^= cur
f=x+p
roots=f.small_roots(X=2**450,beta=0.4)
p=p+roots[0]
q=n//int(p)
fn=(p-1)*(q-1)
d=inverse(65537,fn)
print(hex(int(pow(c,d,n)))[2:-1].decode('hex'))
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 解题
在题目中， q=next_prime(p^((1<<900)-1)^getrandbits(300)) ，由于
对于中间部分，先看看下面这个小例子
p = '101011'
q = '010100'
print(int(p, 2)*int(q, 2)) # 860
# p和q赋值如下
p = '111111'
q = '000001'
# 第一位异或后
p = '011111'
q = '100001'
print(int(p, 2)*int(q, 2)) # 1023
'''
大于原先值，那么该位不用改，即
p = '111111'
q = '000001'
'''
# 第二位异或后
p = '101111'
q = '010001'
print(int(p, 2)*int(q, 2)) # 799
'''
小于原先值，那么该位要改，进行异或，即
p = '101111'
q = '010001'
'''
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
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
据此便能求出
import gmpy2
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
# 对n开方得到p的高位
pm = int(gmpy2.iroot(n, 2)[0]) >> 900 << 900
# 异或关系得到p中间几位
p = pm + (1<<900)-1
q = pm + (1<<(300-1))
for i in range(899, 300, -1):
cur = 1<<i
if (p^cur) * (q^cur) < n:
p ^= cur
q ^= cur
print(p)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371587272537229893805114908933760610743465439666764039511881880973034080383988769147716853426501095208507041971091550177578964746239
1
使用sage进行已知p高位攻击，求出p
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
p0 = 170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371587272537229893805114908933760610743465439666764039511881880973034080383988769147716853426501095208507041971091550177578964746239# 已知的p的高位
PR.<x> = PolynomialRing(Zmod(n))
f = p0 + x
x0 = f.small_roots(X=2^450, beta=0.4)[0]
print(x0 + p0)
1
2
3
4
5
6
2
3
4
5
6
170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371527964357773254659131885022323526864655742577256932209187678896131068422973326545184343697783650940422950445390573562429093050687
1
接下来便能求出
import gmpy2
import libnum
e = 65537
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
c = 0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
p = 170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371527964357773254659131885022323526864655742577256932209187678896131068422973326545184343697783650940422950445390573562429093050687
q = n//p
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, n)
print(libnum.n2s(int(m)))
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
*CTF{St.Diana_pls_take_me_with_you!}
1