2022祥云杯crypto部分

2022-10-30 祥云杯赛后复盘（crypto)

伤心，没做出来几道题

密码方向题目
链接：https://pan.baidu.com/s/1fUYYk6mrL0Vq1MH07lVvFA
提取码：v4lk

参考wp

little little fermat

题目

from Crypto.Util.number import *
from random import *
from libnum import *
import gmpy2

from secret import x

flag = b'?????????'
m = bytes_to_long(flag)
def obfuscate(p, k):
    nbit = 512
    while True:
        l1 = [randrange(-1, 1) for _ in '_' * k]
        l2 = [randrange(100, nbit) for _ in '_' * k]
        l3 = [randrange(10, nbit//4) for _ in '_' * k]
        l4 = [randrange(2, 6) for _ in '_' * k]
        A = sum([l1[_] * 2 ** ((l2[_]+l3[_])//l4[_]) for _ in range(0, k)])
        print(A)
        q = p + A
        if isPrime(q) * A != 0:
            return q

p = getPrime(512)
q = obfuscate(p, 5)
e = 65537
n = p*q
print(f'n = {n}')

assert 114514 ** x % p == 1
m = m ^ (x**2)
c = pow(m, e, n)
print(f'c = {c}')

# n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
# c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
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

签到难度，yafu分解n，已知一个数的x次方mod p = 1，根据费马小定理x=p-1

n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
e = 65537

p = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734648016476153593841839977704512156756634066593725142934001
q = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734646483980612727952939084061619889139517526028673988305393

phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
m1 = m ^ ((p-1)**2)
m2 = m ^ ((q-1)**2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

tracing

from secret import p, q, flag
from Crypto.Util.number import bytes_to_long

def gcd(a, b):
    s = 0
    while b != 0:
        print(a, b)
        if isOdd(a):
            if isOdd(b):
                a = a - b
                a = rshift1(a)
                if a < b:
                    a, b = b, a
            else:
                b = rshift1(b)
                if a < b:
                    a, b = b, a
        else:
            if isOdd(b):
                a = rshift1(a)
                if a < b:
                    a, b = b, a
            else:
                a = rshift1(a)
                b = rshift1(b)
                s += 1
    if s:
        return lshift(a, s)
    return a

def isOdd(a):
    return a & 1 == 1

def rshift1(a):
    return a >> 1

def lshift(a, s):
    return a << s


n = p * q
e = 65537
phi = (p - 1) * (q - 1)
assert gcd(phi, e) == 1
c = pow(bytes_to_long(flag), e, n)
print(c)
print(n)
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
41
42
43
44
45
46
47

我的思路是从文件从上往下读，依次知道phi的末位，

当遇到a=a-b时将减去的数存起来在最后统一加上

当遇到a,b=b,a时说明剩下的a已经比b小了，也就是小于65537了，而且时刚刚比b小，就可以大胆说剩下的数在1<<15和1<<16之间，因为后面ab一直换来换去算起来太麻烦所以选择爆破最后一部分

def myadd(a,b):
    a = int('0b'+a, 2)
    b = int('0b'+b, 2)
    s = a+b
    return str(bin(s))[2:]

def mysub(a,b):
    a = int('0b'+a, 2)
    b = int('0b'+b, 2)
    s = a-b
    return str(bin(s))[2:]

c = 64885875317556090558238994066256805052213864161514435285748891561779867972960805879348109302233463726130814478875296026610171472811894585459078460333131491392347346367422276701128380739598873156279173639691126814411752657279838804780550186863637510445720206103962994087507407296814662270605713097055799853102
e = 65537
n = 113793513490894881175568252406666081108916791207947545198428641792768110581083359318482355485724476407204679171578376741972958506284872470096498674038813765700336353715590069074081309886710425934960057225969468061891326946398492194812594219890553185043390915509200930203655022420444027841986189782168065174301
f = open('trace.out', 'r').read().split('\n')

a = ''
b = '10000000000000001'
jia = 0
s = 0

for i in f:
    if i == 'task.py(19):                 a = rshift1(a)':
        a = '0' + a
    elif i == 'task.py(10):                 a = rshift1(a)':
        a = '1' + a
        jia += int('0b'+mysub(b[:-1]+a, a), 2)
    elif i == 'task.py(14):                 b = rshift1(b)':
        b = '0' + b
    elif i == 'task.py(23):                 a = rshift1(a)':
        a = '0' + a
        b = '0' + b
        s += 1
    elif i == 'task.py(28):     return a':
        break
    if i == 'task.py(12):                     a, b = b, a' or i == 'task.py(16):                     a, b = b, a' or i == 'task.py(21):                     a, b = b, a':
        print('a =', str(a), 'b =', b, jia)
        break


from Crypto.Util.number import *

s = 32769
from sympy import nextprime
while s < 65537:
    s = nextprime(s)
    print(s)
    phi = int(bin(s) + str(a), 2) + jia
    try:
        d = inverse(e,phi)
        m = long_to_bytes(pow(c, d, n))
        print(m)
        if b'flag{' in m or b'ctf{' in m :
            break
    except:
        continue

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

比赛结束后发现其他师傅大都用的另一种方法：逆着来

from Crypto.Util.number import *
c = 64885875317556090558238994066256805052213864161514435285748891561779867972960805879348109302233463726130814478875296026610171472811894585459078460333131491392347346367422276701128380739598873156279173639691126814411752657279838804780550186863637510445720206103962994087507407296814662270605713097055799853102
n = 113793513490894881175568252406666081108916791207947545198428641792768110581083359318482355485724476407204679171578376741972958506284872470096498674038813765700336353715590069074081309886710425934960057225969468061891326946398492194812594219890553185043390915509200930203655022420444027841986189782168065174301
f = open('trace.out', 'r')
data = f.read().split('task.py(6):     while b != 0:\n')[1:][::-1]
t1 = 'task.py(11):'
t12 = 'task.py(12):'
t2 = 'task.py(14):'
t22 = 'task.py(16):'
t3 = 'task.py(19):'
t32 = 'task.py(21):'
def lshift1(a):
    return a << 1

def f1(a, b, data):
    if t12 in data:
        a, b = b, a
    a = lshift1(a)
    a = a + b
    return a, b

def f2(a, b, data):
    if t22 in data:
        a, b = b, a
    b = lshift1(b)
    return a, b

def f3(a, b, data):
    if t32 in data:
        a, b = b, a
    a = lshift1(a)
    return a, b
a, b = 1, 0
for data0 in data:
    if t1 in data0:
        a, b = f1(a, b, data0)
    elif t2 in data0:
        a, b = f2(a, b, data0)
    elif t3 in data0:
        a, b = f3(a, b, data0)
phi = a
d = inverse(65537, phi)
print(long_to_bytes(pow(c, d, n)))
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
41
42
43

fill

题目

from Crypto.Util.number import *
from random import *
from gmpy2 import gcd
from numpy import dot

nbits = 32
msg = getRandomNBitInteger(nbits)
flag = b'flag{sha256(msg)}'
tmp_m = bin(msg)[2:]
f_list = []
for i in range(len(tmp_m)):
    f_list.append(int(tmp_m[i]))

r_list =[randint(20, 50)]
for i in range(nbits - 1):
    r_list.append(randint(2 * r_list[-1], 3 * r_list[-1]))

while True:
    A = randint(2 * r_list[-1] + 1, 3 * r_list[-1])
    B = randint(2 * r_list[-1] + 1, 3 * r_list[-1])
    if gcd(A, B) == 1:
        break

M = [A * x % B for x in r_list]

S = dot(f_list, M)
print(S)

seed = getRandomNBitInteger(30)
s = [0] * nbits
s[0] = seed
m = getRandomNBitInteger(20)
c = getPrime(24)
n = 991125622
for i in range(1, nbits):
    s[i] = (s[i-1]*m+c)%n
print(s[0], s[1], s[2])
for t in range(nbits):
    M[t] = M[t] + s[t]
print(M)


'''
492226042629702
562734112 859151551 741682801
M = [19621141192340, 39617541681643, 3004946591889, 6231471734951, 3703341368174, 48859912097514, 4386411556216, 11028070476391, 18637548953150, 29985057892414, 20689980879644, 20060557946852, 46908191806199, 8849137870273, 28637782510640, 35930273563752, 20695924342882, 36660291028583, 10923264012354, 29810154308143, 4444597606142, 31802472725414, 23368528779283, 15179021971456, 34642073901253, 44824809996134, 31243873675161, 27159321498211, 2220647072602, 20255746235462, 24667528459211, 46916059974372]
'''
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
41
42
43
44
45
46
47

dot()返回的是两个数组的点积(dot product)

已知

s[1] = (s[0] * m + c) % n
s[2] = (s[1] * m + c) % n
1
2

已知s[0],s[1],s[2],n可以求出来m、n

m = (s1-s2) * inverse(s0-s1,n) % n
c = (s1 - s0 * m)% n
# m = 55365664
# c = 8712091
1
2
3
4

然后就可以算出了s

s = [0]*32
s[0] = s0
for i in range(1, nbits):
    s[i] = (s[i-1]*m+c)%n
1
2
3
4

也就可以求出来原来的M

for t in range(nbits):
    M[t] = M[t] - s[t]
1
2

然后就是已知dot(f_list,M)=S
已知S、M求f_list
没做出来，，，

大佬如是说：

s[i] = (s[i-1]*m+c)%n
很容易想到LCG（n,c互素）
LCG 解得m,c （后面发现m位数>20 很奇怪）
然后求得M
S是M与f_list的点乘
f_list 是0,1数组
背包求解f_list

from functools import reduce

from gmpy2 import *
def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)

def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * invert(states[1] - states[0], modulus) % modulus # 注意这里求逆元
    return crack_unknown_increment(states, modulus, multiplier)
def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

state=[562734112,859151551,741682801]
print(crack_unknown_multiplier(state,991125622))
n=991125622
s=[0]*32
s[0]=state[0]
n=991125622
m=55365664
c=8712091
for i in range(1, 32):
    s[i] = (s[i-1]*m+c)%n
#print(s)
M = [19621141192340, 39617541681643, 3004946591889, 6231471734951, 3703341368174, 48859912097514, 4386411556216, 11028070476391, 18637548953150, 29985057892414, 20689980879644, 20060557946852, 46908191806199, 8849137870273, 28637782510640, 35930273563752, 20695924342882, 36660291028583, 10923264012354, 29810154308143, 4444597606142, 31802472725414, 23368528779283, 15179021971456, 34642073901253, 44824809996134, 31243873675161, 27159321498211, 2220647072602, 20255746235462, 24667528459211, 46916059974372]
for t in range(32):
    M[t] = M[t] - s[t]

pk1 = M
ct1 = 492226042629702
nbit = len(pk1)
A = Matrix(ZZ, nbit + 1, nbit + 1)
for i in range(nbit):
    A[i, i] = 1
for i in range(nbit):
    A[i, nbit] = pk1[i]
A[nbit, nbit] = -int(ct1)
res = A.LLL()
s='0b'
a=(1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0)
for i in a:
    s+=str(i)
from hashlib import *
print(sha256(str(int(s,2)).encode()).hexdigest())
#flag{8f504aee71626212f275117326722b6c0ccc94f4039ed31fbcfde08e026352c4}
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
41
42
43
44
45
46
47
48

也就是大佬这里对于

dot(f_list,M)=S 已知S、M求f_list

这个问题用的是背包体制求解的

先建立矩阵A
A = ( E M 0 − S ) A = \left(

\right ) A=(E0​M−S​)
然后对A进行格基约化，取a为A[-1][:-1]
即为所求

babyDLP

题目：

import socketserver
from time import sleep
from secret import flag
import signal
import random

from Crypto.Util.number import *
import random

def pow_d(g, e, n):
    t, r = 0, 1
    for _ in bin(e)[2:]:
        if r == 4: t += 1
        r = pow(r, 2, n)
        if _ == '1': r = r * g % n
    return t, r

def ts(m, p):
    m = m % p
    return pow(m, (p - 1) // 2, p) == 1
class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self):
        return self._recvall()




    def handle(self):
        border = b"|"
        self.send(border*72)
        self.send(border+b"Solve a DLP challenge in some special way to get the flag", border)

        p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
        s = random.randint(2, (p - 1) // 2)

        while True:
            self.send(b"| Options: \n|\t[T]ry the magic machine \n|\t[Q]uit")
            ans = self.recv().lower()

            if ans == b't':
                self.send(border+b"please send your desired integer: ")
                g = self.recv()
                try:
                    g = int(g)
                except:
                    self.send(border+b"The given input is not integer!")
                    break
                sleep(0.3)
                if ts(g, p):
                    t, r = pow_d(g, s, p)
                    if r == 4:
                        self.send(border+b'Great! you got the flag:'+flag)
                    else:
                        self.send(border+b"t, r = "+f"{t, r}".encode())
                else:
                    self.send(border+"The given base is NOT valid!!!")
            elif ans == b'q':
                self.send(border+"Quitting ...")
                break
            else:
                self.send(border+"Bye bye ...")
                break


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

DLP是指离散对数问题
先nc进环境看看

 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|Solve a DLP challenge in some special way to get the flag
| Options: 
|       [T]ry the magic machine 
|       [Q]uit
T
|please send your desired integer: 
123
|t, r = (0, 1875432736570840149858700690249292995544028281200006722168796364690668925789431292161967745729404863104865558569034566838999165575136079036010072654407517177991565368072030928708922020928904177177172742147181127295601168905201262946028677746048096900276465943635512932185526527864608537277933745104820219530)
| Options: 
|       [T]ry the magic machine 
|       [Q]uit
T
|please send your desired integer: 
12
|t, r = (0, 170659490678360108985814123019431028070497021039543984050717078095401807166227689097346127991525759918978935124320716364167828670786537284881828082090352756706146909103644810497828426563323758069828229126035787702632746227084199915342561552143788761406913754258966545653232504030530263120674069688788605107025)
| Options: 
|       [T]ry the magic machine 
|       [Q]uit
T
|please send your desired integer: 
1236420579048500
|t, r = (0, 162410778155615355406232501107278472199227017427793782589189472357149811456929838686871435127917872064531346051148076979062863408710729218532971787603224087299087656775978247345459016952894254548116774887911499911822018218462789750386753703522977730488293789066594963263654071151488831482386308719611819285542)
| Options: 
|       [T]ry the magic machine 
|       [Q]uit
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

也就是选择T，输入一个数会自动生成一对(t,r)，当生成的r刚好是4是则输出flag

所以重点在于

def pow_d(g, e, n):
    t, r = 0, 1
    for _ in bin(e)[2:]:
        if r == 4: t += 1
        r = pow(r, 2, n)
        if _ == '1': r = r * g % n
    return t, r

def ts(m, p):
    m = m % p
    return pow(m, (p - 1) // 2, p) == 1
1
2
3
4
5
6
7
8
9
10
11

和

p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
s = random.randint(2, (p - 1) // 2)
1
2

然后
额
看大佬的代码吧

from pwn import *
from sage.all import *
from Crypto.Util.number import *

class Gao:
    def __init__(self):
        # self.conn = process(['python3', 'another.py'])
        self.conn = remote("39.106.13.71",34092)
        self.p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
        self.s_high = 1
        self.Zp = Zmod(self.p)

    def gao_check(self):
        self.conn.sendline(b'T')
        ans = self.Zp(4).nth_root(self.s_high)
        print('Guessing: {}'.format(ans))
        self.conn.sendline(str(ans).encode())
        self.conn.recvuntil(b'integer: \n')
        a = self.conn.recvline()
        if ('Great!' in a):
            print(a)
            print(ZZ(ans).nbits())
            return True
        else:
            return False

    def gao_one(self):
        self.conn.sendline(b'T')
        ans = self.Zp(2).nth_root(self.s_high)
        self.conn.sendline(str(ans).encode())
        self.conn.recvuntil(b'integer: \n')
        a = self.conn.recvline()
        if (b'Great!' in a):
            print(a)
            print(ZZ(ans).nbits())
            return True
        else:
            a = a[9:-2]
        t, r = eval(a)
        self.s_high <<= 1
        if (t == 0):
            self.s_high |= 1
        self.t = 1 - t
        print('{:b}'.format(self.s_high))
        return False

    def gao(self):
        while (True):
            if (self.gao_one()):
                break
            if (self.t == 1):
                if (self.gao_check()):
                    break

    def gao_2(self):
        for i in range(1023):
            if (self.gao_one()):
                break
        else:
            for i in range(20):
                self.gao_check()
                self.s_high >>= 1


if __name__ == '__main__':
    g = Gao()
    g.gao_2()
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

大致就是，没看懂

但是还有一道类似的题有春哥的解释

common_rsa

题目

from Crypto.Util.number import getPrime, isPrime, bytes_to_long, inverse
from math import lcm
from secret import flag

def gen(g):
    bits = 512 - g.bit_length()
    while True:
        a = getPrime(bits)
        p = 2 * a * g + 1
        if isPrime(p):
            return p

flag = bytes_to_long(flag)
g = getPrime(320)
p = gen(g)
q = gen(g)
n = p * q
d = getPrime(135)
phi = lcm(p - 1, q - 1)
e = inverse(d, phi)
c = pow(flag, e, n)
print("n = {}".format(n))
print("e = {}".format(e))
print("c = {}".format(c))
'''
n = 253784908428481171520644795825628119823506176672683456544539675613895749357067944465796492899363087465652749951069021248729871498716450122759675266109104893465718371075137027806815473672093804600537277140261127375373193053173163711234309619016940818893190549811778822641165586070952778825226669497115448984409
e = 31406775715899560162787869974700016947595840438708247549520794775013609818293759112173738791912355029131497095419469938722402909767606953171285102663874040755958087885460234337741136082351825063419747360169129165
c = 97724073843199563126299138557100062208119309614175354104566795999878855851589393774478499956448658027850289531621583268783154684298592331328032682316868391120285515076911892737051842116394165423670275422243894220422196193336551382986699759756232962573336291032572968060586136317901595414796229127047082707519
'''
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

没解出来

据说，这是一道经典的common prime rsa($p=2ga,q=2gb,ed=1+k\ast lcm(p-1,q-1)$)

相关论文

大佬的代码：

#Sage

# the following attack is due to Ellen Jochemsz and Alexander May
# see https://www.iacr.org/archive/asiacrypt2006/42840270/42840270.pdf

gamma = 320/1024
delta = 135/1024
m = 2
tau = (1 / 2 + gamma - 4 * delta) / (2 * delta)
t = ZZ(floor(tau * m))

X = ZZ(floor(n ^ delta))
Y = ZZ(floor(n ^ (delta + 1 / 2 - gamma)))
Z = ZZ(floor(n ^ (delta + 1 / 2 - gamma)))
W = ZZ(floor(n ^ (2 + 2 * delta - 2 * gamma)))
R = W * X ^ (2 * (m - 1) + t) * (Y * Z) ^ (m - 1)

# assert X ^ (7 + 9 * tau + 3 * tau ^ 2) * (Y * Z) ^ (5 + 9 * tau / 2) < W ^ (3 + 3 * tau)

P = PolynomialRing(ZZ, 'x,y,z')
x,y,z = P.gens()

# we know that ed = k(2gab) + 1 = k(p - 1)b + 1 = ka(q - 1) + 1
# we can multiply the last two expressions to get a semi-symmetric equation for
# (ed)^2, of which we want to find its roots
f = e^2 * x^2 + e * x * (y + z - 2) - (n - 1) * y * z - (y + z - 1)
assert f.constant_coefficient() == 1

M = set()
S = set()
# generate monomials
# S contains monomials of f^{m - 1} with x-shifts
# M contains monomials of f^{m} with x-shifts \setminus S
for i3 in range(0, m):
    for i2 in range(0, m):
        for i1 in range(0, 2 * (m - 1) - (i2 + i3) + t + 1):
            S.add(x ^ i1 * y ^ i2 * z ^ i3)
for i3 in range(0, m + 1):
    for i2 in range(0, m + 1):
        for i1 in range(0, 2 * m - (i2 + i3) + t + 1):
            M.add(x ^ i1 * y ^ i2 * z ^ i3)
M_S = M - S
M_S = sorted(M_S)
S   = sorted(S)
M   = sorted(M)

# use a dict to map each shift polynomial with its lowest order monomial to
# make diagonalizing the basis matrix easier
g   = {}

# generate shift polynomials
# the shift polynomials are generated with a polynomial derived from f (mod R)
# namely ff = a0^{-1} * f (mod R) such that the constant term of ff is 1
# i am fairly certain any polynomial with constant term 1 and the correct roots
# can be used here, although i have only tested it with ff and f
ff = f.change_ring(Zmod(R)).change_ring(ZZ)
for mono in S:
    i1, i2, i3 = mono.degree(x), mono.degree(y), mono.degree(z)
    fn = mono * ff(x, y, z) * X ^ (2 * (m - 1) + t - i1) * Y ^ (m - 1 - i2) * Z ^ (m - 1 - i3)
    fn = expand(fn(x * X, y * Y, z * Z))
    g[mono] = fn
for mono in M_S:
    fn = R * mono
    fn = expand(fn(x * X, y * Y, z * Z))
    g[mono] = fn

npolys = len(g)
nmonos = len(M)
print("polynomials: {}".format(npolys))
print("monomials:   {}".format(nmonos))
assert npolys == nmonos

B = Matrix(ZZ, npolys, nmonos)
C = Matrix(ZZ, npolys, nmonos)

for row, mono in enumerate(M):
    i1, i2, i3 = mono.degree(x), mono.degree(y), mono.degree(z)
    for c, mono_ in g[mono]:
        col = M.index(mono_)
        C[row, col] = 1
        B[row, col] = c

    # assert that diagonal elements are what they should be
    idx = M.index(mono)
    if mono in S:
        assert B[idx, idx] == X ^ (2 * (m - 1) + t) * (Y * Z) ^ (m - 1)
    elif mono in M_S:
        assert B[idx, idx] == R * X ^ i1 * Y ^ i2 * Z ^ i3
    else:
        raise Exception("what")

print(C.str())

# assert triangular form
for col in range(nmonos):
    for row in range(col + 1, npolys):
    # for row in xrange(col):
        assert B[row, col] == 0
    assert B[col, col] != 0

print("LLL...")
BB = B.LLL(algorithm='fpLLL:proved', fp='rr')
CC = Matrix(ZZ, npolys, nmonos)
for row in range(npolys):
    for col in range(nmonos):
        if BB[row, col] != 0:
            CC[row, col] = 1
print(CC.str())

# helper to construct a polynomial from coefficients
def topoly(r):
    RR = PolynomialRing(QQ, 'x,y,z')
    pol = 0
    for col in range(nmonos):
        pol += r[col] * M[col]
    pol = RR(pol(x / X, y / Y, z / Z))
    for c, _ in pol:
        assert c.is_integer()
    return P(pol)

# pull out h1, h2
hv = [expand(topoly(r)) for r in BB]
h1, h2 = hv[0:2]

# at some point we need to polynomial engines to something that can solve for
# roots, the default univariate engine works
s, = PolynomialRing(ZZ, 's').gens()

# these should be algebraically independent
assert h1.gcd(f).degree() == 0
assert h2.gcd(f).degree() == 0
assert h1.gcd(h2).degree() == 0

# take care that resultants are computed with f and not ff, which is a
# polynomial mod R
# these resultants eliminate z
h1x = h1.resultant(f, z)
h2x = h2.resultant(f, z)
hh  = h1.resultant(h2, z)

# this eliminates y
hy = h1x.resultant(h2x, y)

# now we can solve for roots via back substitution
d = []
for r, m in hy(x=s).roots():
    if r == 0:
        continue
    d.append(r)
assert len(d) == 1
d = d[0]

ka = []
for r, m in hh(x=d, y=s).roots():
    if r == 0:
        continue
    ka.append(r)
# f(x, y, z) = f(x, z, y) so we should have two solutions here
assert len(ka) == 2
ka = ka[0]

kb = []
for r, m in f(x=d, y=ka, z=s).roots():
    if r == 0:
        continue
    kb.append(r)
assert len(kb) == 1
kb = kb[0]

print("found d  = {}".format(d))
print("found ka = {}".format(ka))
print("found kb = {}".format(kb))

k = gcd(ka, kb)
a = ka // k
b = kb // k
g = (e * d - 1) // (2 * k * a * b)
p = 2 * g * a + 1
q = 2 * g * b + 1

from Crypto.Util.number import *
n = 253784908428481171520644795825628119823506176672683456544539675613895749357067944465796492899363087465652749951069021248729871498716450122759675266109104893465718371075137027806815473672093804600537277140261127375373193053173163711234309619016940818893190549811778822641165586070952778825226669497115448984409
e = 31406775715899560162787869974700016947595840438708247549520794775013609818293759112173738791912355029131497095419469938722402909767606953171285102663874040755958087885460234337741136082351825063419747360169129165
c = 97724073843199563126299138557100062208119309614175354104566795999878855851589393774478499956448658027850289531621583268783154684298592331328032682316868391120285515076911892737051842116394165423670275422243894220422196193336551382986699759756232962573336291032572968060586136317901595414796229127047082707519

print(long_to_bytes(int(pow(c,d,n))))
# b'flag{9aecf8d8-6966-4ffa-96b0-2e744d28baf2}'
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

leak rsa

题目

n = 73380160475470842653695210816683702314062827937540324056880543809752271506601290265975543542548117392788987830919581511428492717214125296973338501980504384307279414528799452106399062576988406269897425829853390463840834798274139351938197666753546672052277640048588091137812362810008344723302886421059831149393
e = 3116872133
c = 69574121902821459446683688068339366486115223765903849266663001038736496551168104587683366853482649748413400537793260948337629422998336301256862519087984048032673577462034223842650399943613576577927825123830629917138007035313624847266208032195071033675853881447717750353382112841885318776240405314057286867952
hint1 = {120: '0', 401: '0', 58: '1', 420: '0', 192: '1', 164: '0', 100: '0', 425: '1', 227: '0', 497: '0', 284: '0', 110: '1', 257: '0', 31: '1', 68: '0', 2: '1', 206: '0', 174: '1', 326: '0', 320: '0', 498: '1', 50: '1', 7: '0', 128: '1', 54: '1', 15: '1', 222: '0', 166: '1', 496: '1', 151: '1', 317: '0', 449: '1', 181: '1', 288: '1', 311: '1', 80: '1', 69: '1', 410: '1', 127: '1', 308: '1', 39: '0', 435: '0', 258: '0', 235: '1', 94: '1', 93: '1', 412: '0', 427: '0', 352: '1', 123: '0', 25: '0', 316: '1', 3: '0', 88: '1', 390: '0', 72: '1', 450: '1', 397: '0', 309: '1', 487: '1', 207: '0', 234: '0', 144: '1', 229: '1', 48: '1', 506: '0', 253: '1', 86: '0', 384: '0', 428: '0', 359: '1', 104: '0', 339: '0', 142: '0', 452: '1', 480: '0', 224: '1', 310: '1', 98: '1', 508: '0', 133: '0', 90: '1', 170: '0', 146: '0', 101: '1', 416: '1', 460: '1', 387: '0', 67: '0', 285: '0', 213: '1', 162: '1', 14: '0', 485: '1', 413: '1', 312: '1', 458: '0', 75: '0', 242: '1', 177: '1', 30: '1', 501: '0', 434: '1', 456: '0', 264: '0', 407: '0', 135: '1', 84: '0', 476: '0', 471: '1', 430: '1', 191: '0', 176: '0', 29: '1', 156: '0', 26: '0', 322: '1', 388: '1', 364: '1', 321: '1', 351: '0', 230: '1', 345: '0', 432: '1', 36: '0', 296: '1', 79: '0', 23: '0', 290: '1', 117: '0', 507: '1', 421: '0', 274: '0', 6: '1', 327: '1', 204: '1', 383: '0', 305: '1', 113: '0', 334: '0', 85: '1', 511: '1', 464: '1', 491: '0', 370: '0', 92: '0', 495: '0', 279: '1', 346: '1', 16: '1', 44: '1', 24: '0', 466: '1', 87: '0', 243: '0', 461: '0', 379: '0', 256: '0', 473: '1', 17: '0', 276: '1', 147: '1', 187: '0', 112: '1', 218: '1', 78: '1', 411: '1', 343: '0', 10: '1', 271: '1', 378: '0', 492: '0', 269: '1', 291: '0', 289: '0', 132: '1', 9: '1', 408: '0', 398: '1', 468: '1', 124: '1', 236: '0', 377: '1', 83: '0'}
hint2 = {125: '0', 86: '1', 8: '0', 498: '1', 311: '0', 93: '0', 385: '0', 315: '1', 300: '1', 454: '0', 152: '0', 205: '0', 400: '1', 348: '1', 18: '1', 154: '0', 51: '1', 435: '0', 25: '1', 430: '0', 72: '1', 136: '0', 294: '0', 466: '0', 388: '0', 428: '0', 440: '1', 250: '1', 506: '0', 48: '0', 270: '1', 318: '0', 107: '0', 327: '1', 474: '0', 325: '0', 281: '0', 392: '0', 473: '1', 13: '1', 90: '0', 278: '0', 425: '0', 109: '1', 423: '1', 412: '1', 190: '1', 171: '0', 475: '1', 441: '1', 336: '0', 371: '0', 323: '0', 22: '1', 469: '0', 451: '0', 438: '0', 203: '1', 121: '0', 52: '1', 494: '1', 399: '0', 314: '0', 24: '1', 183: '0', 492: '1', 246: '1', 108: '1', 379: '0', 460: '1', 56: '0', 372: '1', 313: '1', 44: '0', 237: '1', 12: '0', 6: '0', 204: '1', 80: '1', 339: '1', 296: '0', 483: '0', 402: '0', 67: '0', 338: '1', 116: '0', 406: '1', 218: '0', 115: '0', 301: '0', 490: '1', 502: '0', 343: '1', 46: '1', 321: '0', 231: '1', 88: '0', 404: '1', 426: '0', 344: '0', 123: '1', 463: '0', 45: '1', 461: '1', 1: '0', 229: '0', 28: '1', 274: '1', 134: '1', 104: '1', 21: '0', 256: '0', 471: '1', 157: '0', 217: '1', 158: '0', 307: '1', 26: '0', 255: '0', 386: '1', 373: '0', 114: '1', 360: '0', 148: '1', 383: '1', 63: '0', 19: '1', 472: '0', 201: '1', 262: '1', 47: '0', 221: '0', 310: '0', 352: '1', 224: '1', 185: '0', 214: '1', 285: '1', 410: '0', 455: '0', 445: '0', 464: '0', 284: '1', 503: '1', 298: '1', 449: '0', 477: '0', 376: '0', 16: '0', 133: '0', 177: '1', 210: '0', 364: '1', 163: '1', 213: '1', 295: '1', 111: '1', 458: '0', 146: '0', 244: '0', 261: '1', 508: '1', 106: '0', 112: '1', 120: '0', 156: '1', 303: '0', 259: '1', 35: '0', 444: '0', 215: '1', 304: '0', 140: '0', 351: '0', 443: '0'}
hint3 = {891: '0', 74: '0', 129: '0', 477: '0', 880: '1', 57: '0', 473: '0', 289: '1', 361: '1', 1012: '0', 529: '0', 294: '1', 174: '1', 500: '0', 257: '1', 392: '1', 405: '1', 11: '0', 763: '1', 637: '1', 564: '0', 941: '1', 923: '1', 1014: '1', 670: '1', 558: '0', 304: '1', 444: '1', 716: '0', 208: '0', 130: '1', 634: '1', 661: '0', 862: '0', 412: '1', 796: '1', 761: '1', 113: '1', 752: '0', 818: '0', 797: '1', 390: '1', 337: '0', 133: '1', 367: '1', 470: '1', 345: '1', 170: '1', 312: '0', 624: '1', 53: '1', 75: '1', 281: '1', 522: '1', 100: '0', 554: '1', 583: '1', 16: '1', 836: '0', 715: '1', 450: '0', 484: '0', 876: '0', 165: '0', 842: '0', 62: '0', 442: '1', 927: '0', 586: '1', 399: '1', 227: '0', 886: '1', 663: '0', 947: '0', 906: '1', 377: '0', 246: '1', 365: '0', 177: '1', 59: '1', 63: '0', 936: '1', 144: '0', 416: '1', 228: '1', 366: '0', 117: '0', 78: '0', 717: '1', 14: '0', 800: '1', 47: '0', 80: '0', 34: '0', 662: '1', 970: '0', 986: '1', 287: '1', 597: '0', 783: '0', 805: '1', 112: '1', 671: '1', 540: '1', 153: '1', 577: '1', 543: '0', 414: '0', 123: '1', 626: '1', 452: '1', 810: '1', 30: '0', 905: '0', 602: '1', 537: '1', 374: '0', 408: '1', 434: '0', 137: '1', 532: '0', 397: '0', 333: '1', 258: '1', 359: '1', 134: '1', 322: '1', 653: '0', 1018: '0', 639: '1', 40: '1', 826: '1', 489: '0', 5: '0', 858: '0', 44: '1', 516: '0', 149: '0', 945: '0', 106: '1', 694: '0', 221: '0', 207: '0', 186: '1', 316: '0', 449: '1', 297: '1', 276: '0', 103: '0', 437: '0', 802: '0', 108: '1', 921: '1', 427: '0', 728: '1', 879: '0', 953: '0', 51: '1', 459: '0', 37: '0', 559: '0', 610: '1', 341: '0', 299: '0', 952: '0', 201: '0', 327: '0', 741: '1', 253: '1', 310: '1', 946: '1', 696: '0', 398: '1', 266: '1', 829: '0', 908: '0', 469: '0', 873: '1', 658: '0', 798: '1', 54: '0', 621: '0', 238: '0', 654: '1', 205: '0', 925: '0', 391: '1', 480: '0', 4: '0', 598: '0', 677: '0', 142: '1', 606: '0', 118: '0', 164: '0', 973: '1', 347: '0', 159: '1', 307: '1', 83: '1', 668: '1', 675: '0', 924: '1', 191: '1', 890: '0', 352: '1', 965: '1', 692: '1', 782: '1', 817: '1', 889: '1', 515: '1', 433: '0', 356: '0', 845: '1', 104: '0', 18: '0', 979: '0', 426: '0', 785: '1', 546: '0', 52: '0', 55: '0', 824: '1', 704: '1', 510: '1', 710: '0', 1022: '0', 647: '0', 465: '1', 245: '0', 850: '1', 657: '0', 1007: '0', 807: '1', 158: '1', 328: '0', 292: '1', 355: '1', 596: '0', 275: '1', 371: '0', 1004: '0', 594: '0', 384: '1', 446: '1', 7: '0', 994: '1', 616: '1', 317: '0', 305: '0', 151: '1', 400: '0', 900: '1', 203: '0', 563: '1', 745: '1', 536: '1', 726: '0', 751: '1', 402: '1', 116: '0', 781: '1', 988: '0', 768: '1', 688: '1', 954: '1', 976: '1', 868: '1', 723: '1', 131: '1', 794: '0', 513: '0', 914: '1', 641: '1', 319: '0', 629: '1', 620: '1', 711: '0', 601: '0', 531: '0', 393: '0', 168: '0', 132: '0', 17: '0', 950: '0', 488: '0', 679: '0', 568: '0', 43: '1', 545: '1', 217: '0', 680: '1', 501: '1', 1008: '0', 514: '0', 746: '0', 187: '0', 436: '1', 336: '1', 139: '1', 338: '0', 695: '1', 300: '0', 584: '1', 152: '0', 828: '1', 251: '0', 691: '1', 296: '1', 128: '0', 394: '1', 655: '1', 544: '1', 58: '0', 313: '1', 565: '1', 685: '1', 720: '0', 178: '1', 667: '0', 403: '1', 697: '1', 138: '1', 659: '0', 960: '0', 454: '0', 271: '0', 33: '0', 295: '0', 600: '0', 579: '1', 68: '1', 211: '1', 82: '1', 114: '1', 209: '0', 226: '0', 753: '0', 874: '0', 903: '1', 358: '0', 141: '0', 236: '1'}
1
2
3
4
5
6

from Crypto.Util.number import getPrime, inverse, bytes_to_long
from secret import flag
from random import randint
from math import floor

def hint(p, length, upper):
    gift = {}
    pstr = bin(p)[2:].zfill(upper + 1)
    for i in range(length):
        idx = randint(1, upper)
        if idx not in gift:
            gift[idx] = pstr[idx]
    return gift

p = getPrime(512)
q = getPrime(512)
n = p * q
e = getPrime(32)
d = inverse(e, (p - 1) * (q - 1))
c = pow(bytes_to_long(flag), e, n)
hint1 = hint(p, floor(0.42 * p.bit_length()), 511)
hint2 = hint(q, floor(0.42 * q.bit_length()), 511)
hint3 = hint(d, floor(0.42 * d.bit_length()), 1023)
print("n =", n)
print("e =", e)
print("c =", c)
print("hint1 =", hint1)
print("hint2 =", hint2)
print("hint3 =", hint3)
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

再次感受到了世界的参差

照例copy一下大佬的代码吧

import logging
import os
import sys
from itertools import product
from Crypto.Util.number import *
from gmpy2 import powmod
import tqdm
from sage.all import Zmod

path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
if sys.path[1] != path:
    sys.path.insert(1, path)

from shared import bits_to_int_le
from shared import int_to_bits_le
from shared.partial_integer import PartialInteger


# Section 3.
def _tau(x):
    i = 0
    while x % 2 == 0:
        x //= 2
        i += 1

    return i


# Section 2.
def _find_k(N, e, d_bits):
    best_match_count = 0
    best_k = None
    best_d__bits = None
    # Enumerate every possible k value.
    for k in range(1, e):
        d_ = (k * (N + 1) + 1) // e
        d__bits = int_to_bits_le(d_, len(d_bits))
        match_count = 0
        # Only check the most significant half.
        for i in range(len(d_bits) // 2 + 2, len(d_bits)):
            if d_bits[i] == d__bits[i]:
                match_count += 1

        # Update the best match for d.
        if match_count > best_match_count:
            best_match_count = match_count
            best_k = k
            best_d__bits = d__bits

    return best_k, best_d__bits


# Section 2.
def _correct_msb(d_bits, d__bits):
    # Correcting the most significant half of d.
    for i in range(len(d_bits) // 2 + 2, len(d_bits)):
        d_bits[i] = d__bits[i]


# Section 3.
def _correct_lsb(e, d_bits, exp):
    # Correcting the least significant bits of d.
    # Also works for dp and dq, just with a different exponent.
    inv = powmod(e, -1, 2 ** exp)
    for i in range(exp):
        d_bits[i] = (inv >> i) & 1


# Branch and prune for the case with p and q bits known.
def _branch_and_prune_pq(N, p, q, p_, q_, i):
    if i == len(p) or i == len(q):
        yield p_, q_
    else:
        c1 = ((N - p_ * q_) >> i) & 1
        p_prev = p[i]
        q_prev = q[i]
        p_possible = [0, 1] if p_prev is None else [p_prev]
        q_possible = [0, 1] if q_prev is None else [q_prev]
        for p_bit, q_bit in product(p_possible, q_possible):
            # Addition modulo 2 is just xor.
            if p_bit ^ q_bit == c1:
                p[i] = p_bit
                q[i] = q_bit
                yield from _branch_and_prune_pq(N, p, q, p_ | (p_bit << i), q_ | (q_bit << i), i + 1)

        p[i] = p_prev
        q[i] = q_prev


# Branch and prune for the case with p, q, and d bits known.
def _branch_and_prune_pqd(N, e, k, tk, p, q, d, p_, q_, i):
    if i == len(p) or i == len(q):
        yield p_, q_
    else:
        d_ = bits_to_int_le(d, i)
        c1 = ((N - p_ * q_) >> i) & 1
        c2 = ((k * (N + 1) + 1 - k * (p_ + q_) - e * d_) >> (i + tk)) & 1
        p_prev = p[i]
        q_prev = q[i]
        d_prev = 0 if i + tk >= len(d) else d[i + tk]
        p_possible = [0, 1] if p_prev is None else [p_prev]
        q_possible = [0, 1] if q_prev is None else [q_prev]
        d_possible = [0, 1] if d_prev is None else [d_prev]
        for p_bit, q_bit, d_bit in product(p_possible, q_possible, d_possible):
            # Addition modulo 2 is just xor.
            if p_bit ^ q_bit == c1 and d_bit ^ p_bit ^ q_bit == c2:
                p[i] = p_bit
                q[i] = q_bit
                if i + tk < len(d):
                    d[i + tk] = d_bit
                yield from _branch_and_prune_pqd(N, e, k, tk, p, q, d, p_ | (p_bit << i), q_ | (q_bit << i), i + 1)

        p[i] = p_prev
        q[i] = q_prev
        if i + tk < len(d):
            d[i + tk] = d_prev


# Branch and prune for the case with p, q, d, dp, and dq bits known.
def _branch_and_prune_pqddpdq(N, e, k, tk, kp, tkp, kq, tkq, p, q, d, dp, dq, p_, q_, i):
    if i == len(p) or i == len(q):
        yield p_, q_
    else:
        d_ = bits_to_int_le(d, i)
        dp_ = bits_to_int_le(dp, i)
        dq_ = bits_to_int_le(dq, i)
        c1 = ((N - p_ * q_) >> i) & 1
        c2 = ((k * (N + 1) + 1 - k * (p_ + q_) - e * d_) >> (i + tk)) & 1
        c3 = ((kp * (p_ - 1) + 1 - e * dp_) >> (i + tkp)) & 1
        c4 = ((kq * (q_ - 1) + 1 - e * dq_) >> (i + tkq)) & 1
        p_prev = p[i]
        q_prev = q[i]
        d_prev = 0 if i + tk >= len(d) else d[i + tk]
        dp_prev = 0 if i + tkp >= len(dp) else dp[i + tkp]
        dq_prev = 0 if i + tkq >= len(dq) else dq[i + tkq]
        p_possible = [0, 1] if p_prev is None else [p_prev]
        q_possible = [0, 1] if q_prev is None else [q_prev]
        d_possible = [0, 1] if d_prev is None else [d_prev]
        dp_possible = [0, 1] if dp_prev is None else [dp_prev]
        dq_possible = [0, 1] if dq_prev is None else [dq_prev]
        for p_bit, q_bit, d_bit, dp_bit, dq_bit in product(p_possible, q_possible, d_possible, dp_possible,
                                                           dq_possible):
            # Addition modulo 2 is just xor.
            if p_bit ^ q_bit == c1 and d_bit ^ p_bit ^ q_bit == c2 and dp_bit ^ p_bit == c3 and dq_bit ^ q_bit == c4:
                p[i] = p_bit
                q[i] = q_bit
                if i + tk < len(d):
                    d[i + tk] = d_bit
                if i + tkp < len(dp):
                    dp[i + tkp] = dp_bit
                if i + tkq < len(dq):
                    dq[i + tkq] = dq_bit
                yield from _branch_and_prune_pqddpdq(N, e, k, tk, kp, tkp, kq, tkq, p, q, d, dp, dq, p_ | (p_bit << i),
                                                     q_ | (q_bit << i), i + 1)

        p[i] = p_prev
        q[i] = q_prev
        if i + tk < len(d):
            d[i + tk] = d_prev
        if i + tkp < len(dp):
            dp[i + tkp] = dp_prev
        if i + tkq < len(dq):
            dq[i + tkq] = dq_prev


def factorize_pq(N, p, q):
    """
    Factorizes n when some bits of p and q are known.
    If at least 57% of the bits are known, this attack should be polynomial time, however, smaller percentages might still work.
    More information: Heninger N., Shacham H., "Reconstructing RSA Private Keys from Random Key Bits"
    :param N: the modulus
    :param p: partial p (PartialInteger)
    :param q: partial q (PartialInteger)
    :return: a tuple containing the prime factors
    """
    assert p.bit_length == q.bit_length, "p and q should be of equal bit length."
    # p_bits = p
    p_bits = p.to_bits_le()
    for i, b in enumerate(p_bits):
        p_bits[i] = None if b == '?' else int(b, 2)
    # q_bits = q
    q_bits = q.to_bits_le()
    for i, b in enumerate(q_bits):
        q_bits[i] = None if b == '?' else int(b, 2)

    # p and q are prime, odd.
    p_bits[0] = 1
    q_bits[0] = 1

    # logging.info("Starting branch and prune algorithm...")
    print("Starting branch and prune algorithm...")
    for p, q in _branch_and_prune_pq(N, p_bits, q_bits, p_bits[0], q_bits[0], 1):
        if p * q == N:
            return int(p), int(q)


def factorize_pqd(N, e, p, q, d):
    """
    Factorizes n when some bits of p, q, and d are known.
    If at least 42% of the bits are known, this attack should be polynomial time, however, smaller percentages might still work.
    More information: Heninger N., Shacham H., "Reconstructing RSA Private Keys from Random Key Bits"
    :param N: the modulus
    :param e: the public exponent
    :param p: partial p (PartialInteger)
    :param q: partial q (PartialInteger)
    :param d: partial d (PartialInteger)
    :return: a tuple containing the prime factors
    """
    assert p.bit_length == q.bit_length, "p and q should be of equal bit length."
    # p_bits = p
    p_bits = p.to_bits_le()
    for i, b in enumerate(p_bits):
        p_bits[i] = None if b == '?' else int(b, 2)
    # q_bits = q
    q_bits = q.to_bits_le()
    for i, b in enumerate(q_bits):
        q_bits[i] = None if b == '?' else int(b, 2)

    # p and q are prime, odd.
    p_bits[0] = 1
    q_bits[0] = 1
    d_bits = d.to_bits_le()
    for i, b in enumerate(d_bits):
        d_bits[i] = None if b == '?' else int(b, 2)

    # Because e is small, k can be found by brute force.
    # logging.info("Brute forcing k...")
    print("Brute forcing k...")
    k, d__bits = _find_k(N, e, d_bits)
    # logging.info(f"Found k = {k}")
    print(f"Found k = {k}")

    _correct_msb(d_bits, d__bits)

    tk = _tau(k)
    _correct_lsb(e, d_bits, 2 + tk)

    # logging.info("Starting branch and prune algorithm...")
    print("Starting branch and prune algorithm...")
    for p, q in _branch_and_prune_pqd(N, e, k, tk, p_bits, q_bits, d_bits, p_bits[0], q_bits[0], 1):
        if p * q == N:
            return int(p), int(q)


def factorize_pqddpdq(N, e, p, q, d, dp, dq):
    """
    Factorizes n when some bits of p, q, d, dp, and dq are known.
    If at least 27% of the bits are known, this attack should be polynomial time, however, smaller percentages might still work.
    More information: Heninger N., Shacham H., "Reconstructing RSA Private Keys from Random Key Bits"
    :param N: the modulus
    :param e: the public exponent
    :param p: partial p (PartialInteger)
    :param q: partial q (PartialInteger)
    :param d: partial d (PartialInteger)
    :param dp: partial dp (PartialInteger)
    :param dq: partial dq (PartialInteger)
    :return: a tuple containing the prime factors
    """
    assert p.bit_length == q.bit_length, "p and q should be of equal bit length."
    # p_bits = p
    p_bits = p.to_bits_le()
    for i, b in enumerate(p_bits):
        p_bits[i] = None if b == '?' else int(b, 2)
    q_bits = q
    q_bits = q.to_bits_le()
    for i, b in enumerate(q_bits):
        q_bits[i] = None if b == '?' else int(b, 2)

    # p and q are prime, odd.
    p_bits[0] = 1
    q_bits[0] = 1

    d_bits = d.to_bits_le()
    for i, b in enumerate(d_bits):
        d_bits[i] = None if b == '?' else int(b, 2)

    # Because e is small, k can be found by brute force.
    logging.info("Brute forcing k...")
    k, d__bits = _find_k(N, e, d_bits)
    logging.info(f"Found k = {k}")

    _correct_msb(d_bits, d__bits)

    tk = _tau(k)
    _correct_lsb(e, d_bits, 2 + tk)

    x = Zmod(e)["x"].gen()
    f = x ** 2 - x * (k * (N - 1) + 1) - k
    logging.info("Computing kp and kq...")

    for kp in f.roots(multiplicities=False):
        kp = int(kp)
        kq = (-pow(kp, -1, e) * k) % e
        logging.info(f"Trying kp = {kp} and kq = {kq}...")

        # Make a copy for every try of kp and kq so we are sure these bits are not modified.
        # We don't need to make a copy of p, q, and d bits in this loop because those bits only get modified in the branch and prune.
        # The branch and prune algorithm always resets the bits after recursion.
        dp_bits = dp.to_bits_le()
        for i, b in enumerate(dp_bits):
            dp_bits[i] = None if b == '?' else int(b, 2)

        dq_bits = dq.to_bits_le()
        for i, b in enumerate(dq_bits):
            dq_bits[i] = None if b == '?' else int(b, 2)

        tkp = _tau(kp)
        _correct_lsb(e, dp_bits, 1 + tkp)
        tkq = _tau(kq)
        _correct_lsb(e, dq_bits, 1 + tkq)

        logging.info("Starting branch and prune algorithm...")
        for p, q in _branch_and_prune_pqddpdq(N, e, k, tk, kp, tkp, kq, tkq, p_bits, q_bits, d_bits, dp_bits, dq_bits,
                                              p_bits[0], q_bits[0], 1):
            if p * q == N:
                return int(p), int(q)


n = 73380160475470842653695210816683702314062827937540324056880543809752271506601290265975543542548117392788987830919581511428492717214125296973338501980504384307279414528799452106399062576988406269897425829853390463840834798274139351938197666753546672052277640048588091137812362810008344723302886421059831149393
e = 3116872133
c = 69574121902821459446683688068339366486115223765903849266663001038736496551168104587683366853482649748413400537793260948337629422998336301256862519087984048032673577462034223842650399943613576577927825123830629917138007035313624847266208032195071033675853881447717750353382112841885318776240405314057286867952
hint1 = {120: '0', 401: '0', 58: '1', 420: '0', 192: '1', 164: '0', 100: '0', 425: '1', 227: '0', 497: '0', 284: '0',
         110: '1', 257: '0', 31: '1', 68: '0', 2: '1', 206: '0', 174: '1', 326: '0', 320: '0', 498: '1', 50: '1',
         7: '0', 128: '1', 54: '1', 15: '1', 222: '0', 166: '1', 496: '1', 151: '1', 317: '0', 449: '1', 181: '1',
         288: '1', 311: '1', 80: '1', 69: '1', 410: '1', 127: '1', 308: '1', 39: '0', 435: '0', 258: '0', 235: '1',
         94: '1', 93: '1', 412: '0', 427: '0', 352: '1', 123: '0', 25: '0', 316: '1', 3: '0', 88: '1', 390: '0',
         72: '1', 450: '1', 397: '0', 309: '1', 487: '1', 207: '0', 234: '0', 144: '1', 229: '1', 48: '1', 506: '0',
         253: '1', 86: '0', 384: '0', 428: '0', 359: '1', 104: '0', 339: '0', 142: '0', 452: '1', 480: '0', 224: '1',
         310: '1', 98: '1', 508: '0', 133: '0', 90: '1', 170: '0', 146: '0', 101: '1', 416: '1', 460: '1', 387: '0',
         67: '0', 285: '0', 213: '1', 162: '1', 14: '0', 485: '1', 413: '1', 312: '1', 458: '0', 75: '0', 242: '1',
         177: '1', 30: '1', 501: '0', 434: '1', 456: '0', 264: '0', 407: '0', 135: '1', 84: '0', 476: '0', 471: '1',
         430: '1', 191: '0', 176: '0', 29: '1', 156: '0', 26: '0', 322: '1', 388: '1', 364: '1', 321: '1', 351: '0',
         230: '1', 345: '0', 432: '1', 36: '0', 296: '1', 79: '0', 23: '0', 290: '1', 117: '0', 507: '1', 421: '0',
         274: '0', 6: '1', 327: '1', 204: '1', 383: '0', 305: '1', 113: '0', 334: '0', 85: '1', 511: '1', 464: '1',
         491: '0', 370: '0', 92: '0', 495: '0', 279: '1', 346: '1', 16: '1', 44: '1', 24: '0', 466: '1', 87: '0',
         243: '0', 461: '0', 379: '0', 256: '0', 473: '1', 17: '0', 276: '1', 147: '1', 187: '0', 112: '1', 218: '1',
         78: '1', 411: '1', 343: '0', 10: '1', 271: '1', 378: '0', 492: '0', 269: '1', 291: '0', 289: '0', 132: '1',
         9: '1', 408: '0', 398: '1', 468: '1', 124: '1', 236: '0', 377: '1', 83: '0'}
hint2 = {125: '0', 86: '1', 8: '0', 498: '1', 311: '0', 93: '0', 385: '0', 315: '1', 300: '1', 454: '0', 152: '0',
         205: '0', 400: '1', 348: '1', 18: '1', 154: '0', 51: '1', 435: '0', 25: '1', 430: '0', 72: '1', 136: '0',
         294: '0', 466: '0', 388: '0', 428: '0', 440: '1', 250: '1', 506: '0', 48: '0', 270: '1', 318: '0', 107: '0',
         327: '1', 474: '0', 325: '0', 281: '0', 392: '0', 473: '1', 13: '1', 90: '0', 278: '0', 425: '0', 109: '1',
         423: '1', 412: '1', 190: '1', 171: '0', 475: '1', 441: '1', 336: '0', 371: '0', 323: '0', 22: '1', 469: '0',
         451: '0', 438: '0', 203: '1', 121: '0', 52: '1', 494: '1', 399: '0', 314: '0', 24: '1', 183: '0', 492: '1',
         246: '1', 108: '1', 379: '0', 460: '1', 56: '0', 372: '1', 313: '1', 44: '0', 237: '1', 12: '0', 6: '0',
         204: '1', 80: '1', 339: '1', 296: '0', 483: '0', 402: '0', 67: '0', 338: '1', 116: '0', 406: '1', 218: '0',
         115: '0', 301: '0', 490: '1', 502: '0', 343: '1', 46: '1', 321: '0', 231: '1', 88: '0', 404: '1', 426: '0',
         344: '0', 123: '1', 463: '0', 45: '1', 461: '1', 1: '0', 229: '0', 28: '1', 274: '1', 134: '1', 104: '1',
         21: '0', 256: '0', 471: '1', 157: '0', 217: '1', 158: '0', 307: '1', 26: '0', 255: '0', 386: '1', 373: '0',
         114: '1', 360: '0', 148: '1', 383: '1', 63: '0', 19: '1', 472: '0', 201: '1', 262: '1', 47: '0', 221: '0',
         310: '0', 352: '1', 224: '1', 185: '0', 214: '1', 285: '1', 410: '0', 455: '0', 445: '0', 464: '0', 284: '1',
         503: '1', 298: '1', 449: '0', 477: '0', 376: '0', 16: '0', 133: '0', 177: '1', 210: '0', 364: '1', 163: '1',
         213: '1', 295: '1', 111: '1', 458: '0', 146: '0', 244: '0', 261: '1', 508: '1', 106: '0', 112: '1', 120: '0',
         156: '1', 303: '0', 259: '1', 35: '0', 444: '0', 215: '1', 304: '0', 140: '0', 351: '0', 443: '0'}
hint3 = {891: '0', 74: '0', 129: '0', 477: '0', 880: '1', 57: '0', 473: '0', 289: '1', 361: '1', 1012: '0', 529: '0',
         294: '1', 174: '1', 500: '0', 257: '1', 392: '1', 405: '1', 11: '0', 763: '1', 637: '1', 564: '0', 941: '1',
         923: '1', 1014: '1', 670: '1', 558: '0', 304: '1', 444: '1', 716: '0', 208: '0', 130: '1', 634: '1', 661: '0',
         862: '0', 412: '1', 796: '1', 761: '1', 113: '1', 752: '0', 818: '0', 797: '1', 390: '1', 337: '0', 133: '1',
         367: '1', 470: '1', 345: '1', 170: '1', 312: '0', 624: '1', 53: '1', 75: '1', 281: '1', 522: '1', 100: '0',
         554: '1', 583: '1', 16: '1', 836: '0', 715: '1', 450: '0', 484: '0', 876: '0', 165: '0', 842: '0', 62: '0',
         442: '1', 927: '0', 586: '1', 399: '1', 227: '0', 886: '1', 663: '0', 947: '0', 906: '1', 377: '0', 246: '1',
         365: '0', 177: '1', 59: '1', 63: '0', 936: '1', 144: '0', 416: '1', 228: '1', 366: '0', 117: '0', 78: '0',
         717: '1', 14: '0', 800: '1', 47: '0', 80: '0', 34: '0', 662: '1', 970: '0', 986: '1', 287: '1', 597: '0',
         783: '0', 805: '1', 112: '1', 671: '1', 540: '1', 153: '1', 577: '1', 543: '0', 414: '0', 123: '1', 626: '1',
         452: '1', 810: '1', 30: '0', 905: '0', 602: '1', 537: '1', 374: '0', 408: '1', 434: '0', 137: '1', 532: '0',
         397: '0', 333: '1', 258: '1', 359: '1', 134: '1', 322: '1', 653: '0', 1018: '0', 639: '1', 40: '1', 826: '1',
         489: '0', 5: '0', 858: '0', 44: '1', 516: '0', 149: '0', 945: '0', 106: '1', 694: '0', 221: '0', 207: '0',
         186: '1', 316: '0', 449: '1', 297: '1', 276: '0', 103: '0', 437: '0', 802: '0', 108: '1', 921: '1', 427: '0',
         728: '1', 879: '0', 953: '0', 51: '1', 459: '0', 37: '0', 559: '0', 610: '1', 341: '0', 299: '0', 952: '0',
         201: '0', 327: '0', 741: '1', 253: '1', 310: '1', 946: '1', 696: '0', 398: '1', 266: '1', 829: '0', 908: '0',
         469: '0', 873: '1', 658: '0', 798: '1', 54: '0', 621: '0', 238: '0', 654: '1', 205: '0', 925: '0', 391: '1',
         480: '0', 4: '0', 598: '0', 677: '0', 142: '1', 606: '0', 118: '0', 164: '0', 973: '1', 347: '0', 159: '1',
         307: '1', 83: '1', 668: '1', 675: '0', 924: '1', 191: '1', 890: '0', 352: '1', 965: '1', 692: '1', 782: '1',
         817: '1', 889: '1', 515: '1', 433: '0', 356: '0', 845: '1', 104: '0', 18: '0', 979: '0', 426: '0', 785: '1',
         546: '0', 52: '0', 55: '0', 824: '1', 704: '1', 510: '1', 710: '0', 1022: '0', 647: '0', 465: '1', 245: '0',
         850: '1', 657: '0', 1007: '0', 807: '1', 158: '1', 328: '0', 292: '1', 355: '1', 596: '0', 275: '1', 371: '0',
         1004: '0', 594: '0', 384: '1', 446: '1', 7: '0', 994: '1', 616: '1', 317: '0', 305: '0', 151: '1', 400: '0',
         900: '1', 203: '0', 563: '1', 745: '1', 536: '1', 726: '0', 751: '1', 402: '1', 116: '0', 781: '1', 988: '0',
         768: '1', 688: '1', 954: '1', 976: '1', 868: '1', 723: '1', 131: '1', 794: '0', 513: '0', 914: '1', 641: '1',
         319: '0', 629: '1', 620: '1', 711: '0', 601: '0', 531: '0', 393: '0', 168: '0', 132: '0', 17: '0', 950: '0',
         488: '0', 679: '0', 568: '0', 43: '1', 545: '1', 217: '0', 680: '1', 501: '1', 1008: '0', 514: '0', 746: '0',
         187: '0', 436: '1', 336: '1', 139: '1', 338: '0', 695: '1', 300: '0', 584: '1', 152: '0', 828: '1', 251: '0',
         691: '1', 296: '1', 128: '0', 394: '1', 655: '1', 544: '1', 58: '0', 313: '1', 565: '1', 685: '1', 720: '0',
         178: '1', 667: '0', 403: '1', 697: '1', 138: '1', 659: '0', 960: '0', 454: '0', 271: '0', 33: '0', 295: '0',
         600: '0', 579: '1', 68: '1', 211: '1', 82: '1', 114: '1', 209: '0', 226: '0', 753: '0', 874: '0', 903: '1',
         358: '0', 141: '0', 236: '1'}
p = list('?' * 512)
q = list('?' * 512)
d = list('?' * 1024)
print(len(hint1), len(hint2), len(hint3))
for i in hint1:
    p[i] = hint1[i]
for i in hint2:
    q[i] = hint2[i]
for i in hint3:
    d[i] = hint3[i]
p_bits = ''.join(p)
q_bits = ''.join(q)
d_bits = ''.join(d)
p_bits = PartialInteger.from_bits_be(p_bits)
q_bits = PartialInteger.from_bits_be(q_bits)
d_bits = PartialInteger.from_bits_be(d_bits)
# k = 1972411342
p = 9133917064511781922031258437152327261693143304454013549549758156666324513465089691034313787446294509129449327989019056217376060978961891599469362333006483
q = 8033810681353399639534641829067934203193783188961178150445992214367649502764412203925061359540792375365156063944961787518643928146665931290500178482197771
# p, q = factorize_pqd(n, e, p_bits, q_bits, d_bits)
print(p, q)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)))
# b'flag{022db473-bd93-4c64-8e6f-a8f45205f364}'
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412