StarCTF2022复现--ez_RSA

2022-05-01
Tags: Crypto wp.
Categories: 题目复现.

学习！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

代码不长，很容易可以发现这个题的漏洞点在于p，q的选取上

对两段p，q的生成代码进行详细解读后，发现p,q的由前124位相同，125-924位相反（因为这一段q在p的基础上异或了(1<<900)-1,这个数字是900个1，在位运算中异或1就等于取反），最后300位是异或的一个300位的随机数

这种题很明显考察的是高位比特泄露，但不能用高位比特泄露的脚本一把梭，因为现在连p，q的高位都不知道。比赛的时候也是卡在这里，还是太菜了

赛后学习了一下wp，这道题要将分成三部分来解

高位

在看了wp后，前124位有两种解法

  1. 将n的前248位开方
1
2
3
4
5
import gmpy2
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
top_bits = int(gmpy2.iroot(n>>(2048-248),2)[0])
print(hex(top_bits))
# 0xf376c68d76f4ab9b4d247852ef07159

  1. 因为next_prime影响的是非常低位的数据，所以q约等于p异或(1<<900)-1再异或一个300位的随机数

    将p和q拆开，，，high指高124位，low指低900位

    设，显然。设随机数为，则有：

    所以：

    因此就是

    通过sagemath得出解

    1
    2
    3
    4
    5
    n=0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
    f=n//2**1800
    e=f-x-x^2
    e.solve(x)
    #[x == -20226195070633070235386534147535171930, x ==20226195070633070235386534147535171929]

    x为20226195070633070235386534147535171929

中位

因为异或随机数是在最后300位上，所以125-900位的p，q之和为一个定值，而这一段上p，q的每一位是相反的，因此可以将这一段设为极端情况——p全为1，q全为0。根据基本不等式，p、q的差值越大，积就越大，而最后300位还要继续将q增大。根据这几点可以爆破125-924位，当时，表示这个位置的数正确

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
top_bits = int(gmpy2.iroot(n>>(2048-248),2)[0])
# Put all 1 in p and 0 in q
p = top_bits<<900 | (2**900 - 1)
q = top_bits<<900
# Start from 125th bits (1024-125)
for i in range(899, 301, -1):
	cur = 1<<i
	# Swap p to 0 and q to 1
	# if less than n then is correct order
	# else no changes
	if (p^cur) * (q^cur) < n:
		p ^= cur
		q ^= cur
print(hex(p))
print(hex(q))
# 0xf376c68d76f4ab9b4d247852ef07159a09eeac920ac89148a8dee4f3c359a291b6bf03ab9258ca64783c416fcfeade13cf3c18a7677c29283c7fc6bfcdbba1d6fecbe9e243cc2e3ef0fe60035e1dbc727f3522bfab2bc28d5e29bfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
# 0xf376c68d76f4ab9b4d247852ef071595f611536df5376eb757211b0c3ca65d6e4940fc546da7359b87c3be90301521ec30c3e7589883d6d7c380394032445e290134161dbc33d1c10f019ffca1e2438d80cadd4054d43d72a1d64000000000000000000000000000000000000000000000000000000000000000000000000000

低位

现在已经算出来了泄露的高位，低位用高位比特泄露的脚本一把梭就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
p = 0xf376c68d76f4ab9b4d247852ef07159a09eeac920ac89148a8dee4f3c359a291b6bf03ab9258ca64783c416fcfeade13cf3c18a7677c29283c7fc6bfcdbba1d6fecbe9e243cc2e3ef0fe60035e1dbc727f3522bfab2bc28d5e29bfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
c = 0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
PR.<x> = PolynomialRing(Zmod(n))
f=x+p
roots=f.small_roots(X=2**430,beta=0.4)
p=int(p+roots[0])
assert n%p==0
q = n//p
phi = (p-1)*(q-1)
d = inverse(65537, phi)
print(long_to_bytes(pow(c,d,n)))
# b'*CTF{St.Diana_pls_take_me_with_you!}'

exp

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
from Crypto.Util.number import *
n=0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
c=0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
e=65537
#f=n//2**1800
#e=f-x-x^2
#e.solve(x)
p_high=20226195070633070235386534147535171929
q_high=p_high
p_mid=p_high<<900|(2**900-1)
q_mid=q_high<<900
for i in range(899,300,-1):
    cur=i<<i
    if (p_mid^cur)*(q_mid^cur)<n:
        p_mid^=cur
        q_mid^=cur
#p_mid = 0xf376c68d76f4ab9b4d247852ef07159a09eeac920ac89148a8dee4f3c359a291b6bf03ab9258ca64783c416fcfeade13cf3c18a7677c29283c7fc6bfcdbba1d6fecbe9e243cc2e3ef0fe60035e1dbc727f3522bfab2bc28d5e29bfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
#PR.<x> = PolynomialRing(Zmod(n))
#f=x+p_mid
#roots=f.small_roots(X=2**430,beta=0.4)
#p=int(p_mid+roots[0])
#print(p)
p=170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371527964357773254659131885022323526864655742577256932209187678896131068422973326545184343697783650940422950445390573562429093050687
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))