Veiled XOR#

The challenge gives p^reversed(q) as a hint for a rsa challenge.

1
from Crypto.Util.number import getPrime, bytes_to_long
2
n = (p := getPrime(1024)) * (q := getPrime(1024))
3
print(f"n : {n}\nc : {pow(bytes_to_long(flag), 65537, n)}\nVeil XOR: {p ^ int(bin(q)[2:][::-1], 2)}")
4
# n : ...
5
# c : ...
6
# Veil XOR: ...

What we know#

We already knew that a similar challenge that is p^q can be solved by this forum: <-link-to-forum->
But what about p^reversed(q)?
Luckily, we found a solved writeup that is exactly this challenge. Big thanks to KevinLiu.

Solution Script#

note that we can increase NBITS
@ creds to: KevinLiu

1
n = 2565099383...
2
e = 65537
3
ct = 787441922...
4
# p xor (reverse q)
5
xor = 2684507369...
6
NBITS = 1024
7

8
# q = highQ || lowQ and p = highP || lowP, where all high/low have idx bits
9
def find(idx, lowP, highP, lowQ, highQ):
10

11
    if idx == NBITS:
12
        assert highP * highQ == n
13
        print("FOUND!")
14
        print(highP)
15
        print(highQ)
16
        exit()
17

18

19
    highX = (xor >> (NBITS - 1 -idx)) & 1
20
    lowX = (xor >> idx) & 1
21

22
    possibleLow = []
23
    possibleHigh = []
24

25
    # find possible (highP, lowQ) pairs from the MSB of the XOR
26
    if highX == 1:
27
        possibleHigh.append(((highP << 1) | 1, lowQ))
28
        possibleHigh.append((highP << 1, lowQ + (1 << idx)))
29
    else:
30
        possibleHigh.append((highP << 1, lowQ))
31
        possibleHigh.append(((highP << 1) | 1, lowQ + (1 << idx)))
32

33
    # find possible (lowP, highQ) pairs from the LSB of the XOR
34
    if lowX == 1:
35
        possibleLow.append((lowP, (highQ << 1) | 1))
36
        possibleLow.append((lowP + (1 << idx), highQ << 1))
37
    else:
38
        possibleLow.append((lowP, highQ << 1))
39
        possibleLow.append((lowP + (1 << idx), (highQ << 1) | 1))
40

41

42
    for highP, lowQ in possibleHigh:
43
        for lowP, highQ in possibleLow:
44
            # prune lower bits
45
            if lowP * lowQ % (1 << (idx + 1)) != n % (1 << (idx + 1)):
46
                continue
47

48
            pad = NBITS-1-idx
49

50
            # check upper bit bounds
51
            if (highP << pad) * (highQ << pad) > n:
52
                continue
53

54
            if ((highP << pad) + (1 << pad) - 1) * ((highQ << pad) + (1 << pad) - 1) < n:
55
                continue
56

57
            find(idx+1, lowP, highP, lowQ, highQ)
58

59
import sys
60
sys.setrecursionlimit(NBITS + 50) # set higher limit
61
find(0, 0, 0, 0, 0)

To decrypt flag with p and q:#

1
from Crypto.Util.number import inverse, long_to_bytes
2
p =
3
q =
4
n =
5
c =
6
phi = (p-1)*(q-1)
7
d = inverse(0x10001, (p-1)*(q-1))
8
flag = long_to_bytes(pow(c, d, n)).decode()
9
print(flag)