CTFshow-ROARCTF-Reverse

​ 根据题目所给算法，通过递归爆破获得p，q破解密文。

​ 题目：

from Crypto.Util.number import *
from gmpy2 import *
from secret import *

assert(flag.decode().startswith('flag{')) and (flag.decode().endswith('}'))
def reverse(x):
	y = 0
	while x != 0:
		y = y*2 + x%2
		x = x // 2
	return y


while True:
	p = getStrongPrime(512)
	q = reverse(p)
	if is_prime(q):
		break

n = p*q
e = 65537
m = bytes_to_long(flag)
enc = powmod(m,e,n)
#n = 158985980192501034004997692253209315116841431063210516613522548452327355222295231366801286879768949611058043390843949610463241574886852164907094966008463721486557469253652940169060186477803255769516068561042756903927308078335838348784208212701919950712557406983012026654876481867000537670622886437968839524889
#enc = 103728452309804750381455306214814700768557462686461157761076359181984554990431665209165298725569861567865645228742739676539208228770740802323555281253638825837621845841771677911598039696705908004858472132222470347720085501572979109563593281375095145984000628623881592799662103680478967594601571867412886606745

​ 实际上reverse（）的作用就是将传入参数的二进制表示倒序排列形成一个新的数，因此题目中的p和q是512位长度且01序列顺序相反的2进制数；所以我们可以通过遍历p（512位）的01序列（因为顺序相反，其实也在遍历q），并与n的二进制表示得到每一位进行比对，来获得p、q的值。

​ exp：

from Crypto.Util.number import *
import gmpy2
n = 158985980192501034004997692253209315116841431063210516613522548452327355222295231366801286879768949611058043390843949610463241574886852164907094966008463721486557469253652940169060186477803255769516068561042756903927308078335838348784208212701919950712557406983012026654876481867000537670622886437968839524889
c = 103728452309804750381455306214814700768557462686461157761076359181984554990431665209165298725569861567865645228742739676539208228770740802323555281253638825837621845841771677911598039696705908004858472132222470347720085501572979109563593281375095145984000628623881592799662103680478967594601571867412886606745
e = 65537
def Brute_force(a, b, k):
    if k == 256:
        if a * b == n:#跳出递归的条件
            print(a, b)
        return 0

    for i in range(2):
        for j in range(2):

            a1 = a + i * (2 ** (511 - k)) + j * (2 ** k)
            b1 = b + j * (2 ** (511 - k)) + i * (2 ** k)
            #限制条件一，加快爆破速度
            if a1 * b1 > n:
                continue
            #限制条件二，加快爆破速度
            if (a1 + 2 ** (511 - k)) * ((b1 + 2 ** (511 - k))) < n:
                continue
            #这个条件限制n从低位到高位的每一位和爆破出来的每一位相等，是不可缺少的限制条件
            if (a1 * b1) % (2 ** (k + 1)) != n % (2 ** (k + 1)):
                continue

            Brute_force(a1, b1, k + 1)

    return 0

Brute_force(0, 0, 0)
p = 11954360020159164180709939019047385560179850436770100207193049651260543609501871575909448998378290922795824941066935928157032997160163537467165365731882943
q = 13299413764048930133302138749466137829470129709829516069778014310838093114516400589047888072065037035007023741009041669893387899867083575829855377403280423
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
flag = long_to_bytes(pow(c,d,n))
print(flag)

flag{b92d9b6c-e75d-4cbb-bc39-bf39a2f57c3f}