Dest0g3 520迎新赛

很遗憾，由于暑假需要参与数模，暑假每日一练可能很难实现，但仍会陆续复现一些之前的题目。时间跨度上可能会长一些。

babyRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import bytes_to_long, getPrime
from gmpy2 import next_prime
p = getPrime(1024)
q = next_prime(p)
n = p*q
flag = open('flag.txt', 'rb').read()
m = bytes_to_long(flag)
e = 65537
c = pow(m, e, n)
print(n)
print(c)
'''
27272410937497615429184017335437367466288981498585803398561456300019447702001403165885200936510173980380489828828523983388730026101865884520679872671569532101708469344562155718974222196684544003071765625134489632331414011555536130289106822732544904502428727133498239161324625698270381715640332111381465813621908465311076678337695819124178638737015840941223342176563458181918865641701282965455705790456658431641632470787689389714643528968037519265144919465402561959014798324908010947632834281698638848683632113623788303921939908168450492197671761167009855312820364427648296494571794298105543758141065915257674305081267
14181751948841206148995320731138166924841307246014981115736748934451763670304308496261846056687977917728671991049712129745906089287169170294259856601300717330153987080212591008738712344004443623518040786009771108879196701679833782022875324499201475522241396314392429412747392203809125245393462952461525539673218721341853515099201642769577031724762640317081252046606564108211626446676911167979492329012381654087618979631924439276786566078856385835786995011067720124277812004808431347148593882791476391944410064371926611180496847010107167486521927340045188960373155894717498700488982910217850877130989318706580155251854
'''

$p,q$ 近似，对 $n$ 开根号取前后素数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2

n = 27272410937497615429184017335437367466288981498585803398561456300019447702001403165885200936510173980380489828828523983388730026101865884520679872671569532101708469344562155718974222196684544003071765625134489632331414011555536130289106822732544904502428727133498239161324625698270381715640332111381465813621908465311076678337695819124178638737015840941223342176563458181918865641701282965455705790456658431641632470787689389714643528968037519265144919465402561959014798324908010947632834281698638848683632113623788303921939908168450492197671761167009855312820364427648296494571794298105543758141065915257674305081267
c = 14181751948841206148995320731138166924841307246014981115736748934451763670304308496261846056687977917728671991049712129745906089287169170294259856601300717330153987080212591008738712344004443623518040786009771108879196701679833782022875324499201475522241396314392429412747392203809125245393462952461525539673218721341853515099201642769577031724762640317081252046606564108211626446676911167979492329012381654087618979631924439276786566078856385835786995011067720124277812004808431347148593882791476391944410064371926611180496847010107167486521927340045188960373155894717498700488982910217850877130989318706580155251854

tmp = gmpy2.iroot(n,2)[0]
p = gmpy2.next_prime(tmp)
q = n//p
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
#Dest0g3{96411aad-032c-20a8-bc43-b473f6f08536}

babyAES

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Cipher import AES
import os
iv = os.urandom(16)
key = os.urandom(16)
my_aes = AES.new(key, AES.MODE_CBC, iv)
flag = open('flag.txt', 'rb').read()
flag += (16 - len(flag) % 16) * b'\x00'
c = my_aes.encrypt(flag)
print(c)
print(iv)
print(key)

'''
b'C4:\x86Q$\xb0\xd1\x1b\xa9L\x00\xad\xa3\xff\x96 hJ\x1b~\x1c\xd1y\x87A\xfe0\xe2\xfb\xc7\xb7\x7f^\xc8\x9aP\xdaX\xc6\xdf\x17l=K\x95\xd07'
b'\xd1\xdf\x8f)\x08w\xde\xf9yX%\xca[\xcb\x18\x80'
b'\xa4\xa6M\xab{\xf6\x97\x94>hK\x9bBe]F'
'''

简单的AES加解密。

1
2
3
4
5
6
7
8
9
from Crypto.Cipher import AES

c = b'C4:\x86Q$\xb0\xd1\x1b\xa9L\x00\xad\xa3\xff\x96 hJ\x1b~\x1c\xd1y\x87A\xfe0\xe2\xfb\xc7\xb7\x7f^\xc8\x9aP\xdaX\xc6\xdf\x17l=K\x95\xd07'
iv = b'\xd1\xdf\x8f)\x08w\xde\xf9yX%\xca[\xcb\x18\x80'
key = b'\xa4\xa6M\xab{\xf6\x97\x94>hK\x9bBe]F'
my_aes = AES.new(key, AES.MODE_CBC, iv)
flag = my_aes.decrypt(c)
print(flag)
#b'Dest0g3{d0e5fa76-e50f-76f6-9cf1-b6c2d576b6f4}\x00\x00\x00'

ezDLP

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *

flag = open('flag.txt', 'rb').read()
x = bytes_to_long(flag)
g = 19
p = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
h = pow(g, x, p)
print(h)
'''
199533304296625406955683944856330940256037859126142372412254741689676902594083385071807594584589647225039650850524873289407540031812171301348304158895770989218721006018956756841251888659321582420167478909768740235321161096806581684857660007735707550914742749524818990843357217489433410647994417860374972468061110200554531819987204852047401539211300639165417994955609002932104372266583569468915607415521035920169948704261625320990186754910551780290421057403512785617970138903967874651050299914974180360347163879160470918945383706463326470519550909277678697788304151342226439850677611170439191913555562326538607106089620201074331099713506536192957054173076913374098400489398228161089007898192779738439912595619813699711049380213926849110877231503068464392648816891183318112570732792516076618174144968844351282497993164926346337121313644001762196098432060141494704659769545012678386821212213326455045335220435963683095439867976162
'''

离散对数问题。用sage或python的sympy库求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#sage
g = 19
p = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
h = 199533304296625406955683944856330940256037859126142372412254741689676902594083385071807594584589647225039650850524873289407540031812171301348304158895770989218721006018956756841251888659321582420167478909768740235321161096806581684857660007735707550914742749524818990843357217489433410647994417860374972468061110200554531819987204852047401539211300639165417994955609002932104372266583569468915607415521035920169948704261625320990186754910551780290421057403512785617970138903967874651050299914974180360347163879160470918945383706463326470519550909277678697788304151342226439850677611170439191913555562326538607106089620201074331099713506536192957054173076913374098400489398228161089007898192779738439912595619813699711049380213926849110877231503068464392648816891183318112570732792516076618174144968844351282497993164926346337121313644001762196098432060141494704659769545012678386821212213326455045335220435963683095439867976162
m = discrete_log(mod(h,p),mod(g,p))
print(m)
----------------------------------------------------------------------------------
#python
from Crypto.Util.number import *
from sympy import discrete_log

g = 19
p = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
h = 199533304296625406955683944856330940256037859126142372412254741689676902594083385071807594584589647225039650850524873289407540031812171301348304158895770989218721006018956756841251888659321582420167478909768740235321161096806581684857660007735707550914742749524818990843357217489433410647994417860374972468061110200554531819987204852047401539211300639165417994955609002932104372266583569468915607415521035920169948704261625320990186754910551780290421057403512785617970138903967874651050299914974180360347163879160470918945383706463326470519550909277678697788304151342226439850677611170439191913555562326538607106089620201074331099713506536192957054173076913374098400489398228161089007898192779738439912595619813699711049380213926849110877231503068464392648816891183318112570732792516076618174144968844351282497993164926346337121313644001762196098432060141494704659769545012678386821212213326455045335220435963683095439867976162

m = discrete_log(p,h,g)
print(long_to_bytes(m))
#b'Dest0g3{07ed2a6f-182f-a05d-c81e-1318af820a78}'

ezStream

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
from Crypto.Util.number import *

f = open('flag.txt', 'r')
flag = f.read()
f.close()
assert flag[:8] == "Dest0g3{"


class LCG:
    def __init__(self):
        self.a = getRandomNBitInteger(32)
        self.b = getRandomNBitInteger(32)
        self.m = getPrime(32)
        self.seed = getRandomNBitInteger(32)

    def next(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed >> 16

    def output(self):
        print("a = {}\nb = {}\nm = {}".format(self.a, self.b, self.m))
        print("state1 = {}".format(self.next()))
        print("state2 = {}".format(self.next()))


lcg = LCG()
lcg.output()
c = b''.join([long_to_bytes(ord(flag[i]) ^ (lcg.next() % 10)) for i in range(len(flag))])
print(bytes_to_long(c))
'''
a = 3939333498
b = 3662432446
m = 2271373817
state1 = 17362  
state2 = 20624
600017039001091357643174067454938198067935635401496485588306838343558125283178792619821966678282131419050878
'''

$$
\begin{cases}
seed1 = (a * seed + b)% m,\ state1 = seed1>>16
\\seed2 = (a * seed1 + b)% m,\ state2 = seed2>>16
\end{cases}
$$

这让我想到了二元copper，不过貌似没求出正解。

$seed1,seed2$ 缺失位数小，可以进行爆破。

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
from Crypto.Util.number import *
import gmpy2
from tqdm import tqdm

class LCG:
    def __init__(self,a,b,m,seed):
        self.a = a
        self.b = b
        self.m = m
        self.seed = seed

    def next(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed >> 16

a = 3939333498#32bit
b = 3662432446#32bit
m = 2271373817
state1 = 17362
state2 = 20624
c = 600017039001091357643174067454938198067935635401496485588306838343558125283178792619821966678282131419050878
c = long_to_bytes(c)

end = 2**16
for i in tqdm(range(end)):
    seed1 = (state1 << 16) + i#打括号！！！
    seed2 = (a*seed1+b)%m
    if seed2 >> 16 == state2:
        print(seed2)
        lcg1 = LCG(a, b, m, seed2)
        flag = b''.join([long_to_bytes(c[i] ^ (lcg1.next() % 10)) for i in range(len(c))])
        if b'Dest0g3{' in flag:
            print(flag)
            break
'''
1351677183
b'Dest0g3{f21c7180-c35e-f912-e4bc-bfd235759a25}'
'''

Mr.Doctor

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
from Crypto.Util.number import *
from hashlib import sha256
import string

table = string.ascii_letters + string.digits
flag = open('flag.txt', 'rb').read()[8:-1]
seed = getRandomNBitInteger(40)


class SHA256:
    def __init__(self):
        self.proof = []
        self.sha = 0
        self.sha_flag = []

    def encryption(self):
        for i in range(len(flag) // 4):
            self.proof.append(flag[4 * i:4 + 4 * i])#四个一组
            self.sha = sha256(self.proof[i]).hexdigest().encode()#sha256加密 64bytes
            self.sha_flag.append(bytes_to_long(self.sha))
        return self.sha_flag


class RHODES_ELITE:
    def __init__(self):
        self.Doctor = getPrime(64)
        self.Amiya = getRandomNBitInteger(40)
        self.Rosmontis = getRandomNBitInteger(40)
        self.Blaze = getRandomNBitInteger(40)
        self.seed = seed

    def next(self):
        self.seed = (self.Amiya * self.seed * self.seed + self.Rosmontis * self.seed + self.Blaze) % self.Doctor
        return self.seed >> 12

    def output(self):
        print("Amiya = ", self.Amiya)
        print("Rosmontis = ", self.Rosmontis)
        print("Blaze = ", self.Blaze)
        print("Doctor = ", self.Doctor)


sha = SHA256()
sha_flag = sha.encryption()
elite = RHODES_ELITE()
elite.output()
print("Ash = ", elite.next())
print("SliverAsh = ", elite.next())
W = b''.join([long_to_bytes(sha_flag[i] % (seed ** 3) ^ (elite.next() % 100)) for i in range(len(sha_flag))])
print(bytes_to_long(W))

'''
Amiya =  956366446278
Rosmontis =  1061992537343
Blaze =  636205571590
Doctor =  18068433704538283397
Ash =  1097363493609113
SliverAsh =  2051431344160327
1920358673646340365826516899186299898354902389402251443712585240681673718967552394250439615271108958695077816395789102908554482423707690040360881719002797624203057223577713119411615697309430781610828105111854807558984242631896605944487456402584672441464316236703857236007195673926937583757881853655505218912262929700452404084
'''

跟上一题相差不大，同样可以进行二元copper或爆破求出 $seed1,seed2$ ，不过还要求出 $seed$。

二元copper如下：

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
#sage
import itertools

Amiya = 956366446278
Rosmontis = 1061992537343
Blaze = 636205571590
Doctor = 18068433704538283397
Ash = 1097363493609113
SliverAsh = 2051431344160327

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

R.<x1,x2> = PolynomialRing(Zmod(Doctor))
f = Amiya*(Ash*2^12+x2)^2 + Rosmontis*(Ash*2^12+x2) + Blaze - (SliverAsh*2^12+x1)
result = small_roots(f,[2^12, 2^12],m =4,d=4)
#[(1695, 3324)]，验证了一下，是对的
low_Ash, low_Sli = result[0][1],result[0][0]
#print(low_Ash)
#print(low_Sli)

seed1 = (Ash<<12)+low_Ash
seed2 = (SliverAsh<<12)+low_Sli

R.<x> = PolynomialRing(Zmod(Doctor))
f = Amiya*x^2 + Rosmontis*x + Blaze - seed1
x0 = f.monic().roots()
print(x0)
#[(12358488364449364025, 1), (626844643882, 1)]

根据 $seed$ 的范围筛选出 $seed$ 。

还有个麻烦就是不清楚加密的时候有多少组。但可以根据 $seed$ 来判断。$seed$ 40bit，三次方就120bit，故long_to_bytes之后就是15bytes一组，而 $W$ 转字节后正好是135bytes，故分为9组。

剩下的就是爆破了。

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
from Crypto.Util.number import *
from hashlib import sha256
import string
from tqdm import tqdm

table = '0123456789abcdef-'

def SHA256_decrypt(state,seed,data):
    for a in table:
        for b in table:
            for c in table:
                for d in table:
                    b_string = (a+b+c+d).encode()
                    sha = sha256(b_string).hexdigest().encode()
                    sha_flag = bytes_to_long(sha)
                    if long_to_bytes((sha_flag % (seed ** 3)) ^ (state % 100)) == data:
                        print(b_string)
                        return b_string

class RHODES_ELITE:
    def __init__(self,Doctor,Amiya,Rosmontis,Blaze,seed):
        self.Doctor = Doctor
        self.Amiya = Amiya
        self.Rosmontis = Rosmontis
        self.Blaze = Blaze
        self.seed = seed

    def next(self):
        self.seed = (self.Amiya * self.seed * self.seed + self.Rosmontis * self.seed + self.Blaze) % self.Doctor
        return self.seed >> 12

Amiya = 956366446278
Rosmontis = 1061992537343
Blaze = 636205571590
Doctor = 18068433704538283397
Ash = 1097363493609113
SliverAsh = 2051431344160327
W = 1920358673646340365826516899186299898354902389402251443712585240681673718967552394250439615271108958695077816395789102908554482423707690040360881719002797624203057223577713119411615697309430781610828105111854807558984242631896605944487456402584672441464316236703857236007195673926937583757881853655505218912262929700452404084
W = long_to_bytes(W)
print(len(W))
W = [W[i:i+15] for i in range(0,135,15)]

low_Ash = 3324
low_Sli = 1695
seed = 626844643882
seed1 = (Ash<<12)+low_Ash
seed2 = (SliverAsh<<12)+low_Sli

elite = RHODES_ELITE(Doctor,Amiya,Rosmontis,Blaze,seed2)

flag = b''
for each in tqdm(W):
     state = elite.next()
     flag += SHA256_decrypt(state,seed,each)

print(flag)
#b'd2a4d1af-8a80-8794-99ac-635f89494cac'

Bag

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
import gmpy2
from Crypto.Util.number import *
from secret import flag

message = bytes_to_long(flag[8:-1])
Baglenth=286
Bag=[2, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472, 6442450944, 12884901888, 25769803776, 51539607552, 103079215104, 206158430208, 412316860416, 824633720832, 1649267441664, 3298534883328, 6597069766656, 13194139533312, 26388279066624, 52776558133248, 105553116266496, 211106232532992, 422212465065984, 844424930131968, 1688849860263936, 3377699720527872, 6755399441055744, 13510798882111488, 27021597764222976, 54043195528445952, 108086391056891904, 216172782113783808, 432345564227567616, 864691128455135232, 1729382256910270464, 3458764513820540928, 6917529027641081856, 13835058055282163712, 27670116110564327424, 55340232221128654848, 110680464442257309696, 221360928884514619392, 442721857769029238784, 885443715538058477568, 1770887431076116955136, 3541774862152233910272, 7083549724304467820544, 14167099448608935641088, 28334198897217871282176, 56668397794435742564352, 113336795588871485128704, 226673591177742970257408, 453347182355485940514816, 906694364710971881029632, 1813388729421943762059264, 3626777458843887524118528, 7253554917687775048237056, 14507109835375550096474112, 29014219670751100192948224, 58028439341502200385896448, 116056878683004400771792896, 232113757366008801543585792, 464227514732017603087171584, 928455029464035206174343168, 1856910058928070412348686336, 3713820117856140824697372672, 7427640235712281649394745344, 14855280471424563298789490688, 29710560942849126597578981376, 59421121885698253195157962752, 118842243771396506390315925504, 237684487542793012780631851008, 475368975085586025561263702016, 950737950171172051122527404032, 1901475900342344102245054808064, 3802951800684688204490109616128, 7605903601369376408980219232256, 15211807202738752817960438464512, 30423614405477505635920876929024, 60847228810955011271841753858048, 121694457621910022543683507716096, 243388915243820045087367015432192, 486777830487640090174734030864384, 973555660975280180349468061728768, 1947111321950560360698936123457536, 3894222643901120721397872246915072, 7788445287802241442795744493830144, 15576890575604482885591488987660288, 31153781151208965771182977975320576, 62307562302417931542365955950641152, 124615124604835863084731911901282304, 249230249209671726169463823802564608, 498460498419343452338927647605129216, 996920996838686904677855295210258432, 1993841993677373809355710590420516864, 3987683987354747618711421180841033728, 7975367974709495237422842361682067456, 15950735949418990474845684723364134912, 31901471898837980949691369446728269824, 63802943797675961899382738893456539648, 127605887595351923798765477786913079296, 255211775190703847597530955573826158592, 510423550381407695195061911147652317184, 1020847100762815390390123822295304634368, 2041694201525630780780247644590609268736, 4083388403051261561560495289181218537472, 8166776806102523123120990578362437074944, 16333553612205046246241981156724874149888, 32667107224410092492483962313449748299776, 65334214448820184984967924626899496599552, 130668428897640369969935849253798993199104, 261336857795280739939871698507597986398208, 522673715590561479879743397015195972796416, 1045347431181122959759486794030391945592832, 2090694862362245919518973588060783891185664, 4181389724724491839037947176121567782371328, 8362779449448983678075894352243135564742656, 16725558898897967356151788704486271129485312, 33451117797795934712303577408972542258970624, 66902235595591869424607154817945084517941248, 133804471191183738849214309635890169035882496, 267608942382367477698428619271780338071764992, 535217884764734955396857238543560676143529984, 1070435769529469910793714477087121352287059968, 2140871539058939821587428954174242704574119936, 4281743078117879643174857908348485409148239872, 8563486156235759286349715816696970818296479744, 17126972312471518572699431633393941636592959488, 34253944624943037145398863266787883273185918976, 68507889249886074290797726533575766546371837952, 137015778499772148581595453067151533092743675904, 274031556999544297163190906134303066185487351808, 548063113999088594326381812268606132370974703616, 1096126227998177188652763624537212264741949407232, 2192252455996354377305527249074424529483898814464, 4384504911992708754611054498148849058967797628928, 8769009823985417509222108996297698117935595257856, 17538019647970835018444217992595396235871190515712, 35076039295941670036888435985190792471742381031424, 70152078591883340073776871970381584943484762062848, 140304157183766680147553743940763169886969524125696, 280608314367533360295107487881526339773939048251392, 561216628735066720590214975763052679547878096502784, 1122433257470133441180429951526105359095756193005568, 2244866514940266882360859903052210718191512386011136, 4489733029880533764721719806104421436383024772022272, 8979466059761067529443439612208842872766049544044544, 17958932119522135058886879224417685745532099088089088, 35917864239044270117773758448835371491064198176178176, 71835728478088540235547516897670742982128396352356352, 143671456956177080471095033795341485964256792704712704, 287342913912354160942190067590682971928513585409425408, 574685827824708321884380135181365943857027170818850816, 1149371655649416643768760270362731887714054341637701632, 2298743311298833287537520540725463775428108683275403264, 4597486622597666575075041081450927550856217366550806528, 9194973245195333150150082162901855101712434733101613056, 18389946490390666300300164325803710203424869466203226112, 36779892980781332600600328651607420406849738932406452224, 73559785961562665201200657303214840813699477864812904448, 147119571923125330402401314606429681627398955729625808896, 294239143846250660804802629212859363254797911459251617792, 588478287692501321609605258425718726509595822918503235584, 1176956575385002643219210516851437453019191645837006471168, 2353913150770005286438421033702874906038383291674012942336, 4707826301540010572876842067405749812076766583348025884672, 9415652603080021145753684134811499624153533166696051769344, 18831305206160042291507368269622999248307066333392103538688, 37662610412320084583014736539245998496614132666784207077376, 75325220824640169166029473078491996993228265333568414154752, 150650441649280338332058946156983993986456530667136828309504, 301300883298560676664117892313967987972913061334273656619008, 602601766597121353328235784627935975945826122668547313238016, 1205203533194242706656471569255871951891652245337094626476032, 2410407066388485413312943138511743903783304490674189252952064, 4820814132776970826625886277023487807566608981348378505904128, 9641628265553941653251772554046975615133217962696757011808256, 19283256531107883306503545108093951230266435925393514023616512, 38566513062215766613007090216187902460532871850787028047233024, 77133026124431533226014180432375804921065743701574056094466048, 154266052248863066452028360864751609842131487403148112188932096, 308532104497726132904056721729503219684262974806296224377864192, 617064208995452265808113443459006439368525949612592448755728384, 1234128417990904531616226886918012878737051899225184897511456768, 2468256835981809063232453773836025757474103798450369795022913536, 4936513671963618126464907547672051514948207596900739590045827072, 9873027343927236252929815095344103029896415193801479180091654144, 19746054687854472505859630190688206059792830387602958360183308288, 39492109375708945011719260381376412119585660775205916720366616576, 78984218751417890023438520762752824239171321550411833440733233152, 157968437502835780046877041525505648478342643100823666881466466304, 315936875005671560093754083051011296956685286201647333762932932608, 631873750011343120187508166102022593913370572403294667525865865216, 1263747500022686240375016332204045187826741144806589335051731730432, 2527495000045372480750032664408090375653482289613178670103463460864, 5054990000090744961500065328816180751306964579226357340206926921728, 10109980000181489923000130657632361502613929158452714680413853843456, 20219960000362979846000261315264723005227858316905429360827707686912, 40439920000725959692000522630529446010455716633810858721655415373824, 80879840001451919384001045261058892020911433267621717443310830747648, 161759680002903838768002090522117784041822866535243434886621661495296, 323519360005807677536004181044235568083645733070486869773243322990592, 647038720011615355072008362088471136167291466140973739546486645981184, 1294077440023230710144016724176942272334582932281947479092973291962368, 2588154880046461420288033448353884544669165864563894958185946583924736, 5176309760092922840576066896707769089338331729127789916371893167849472, 10352619520185845681152133793415538178676663458255579832743786335698944, 20705239040371691362304267586831076357353326916511159665487572671397888, 41410478080743382724608535173662152714706653833022319330975145342795776, 82820956161486765449217070347324305429413307666044638661950290685591552, 165641912322973530898434140694648610858826615332089277323900581371183104, 331283824645947061796868281389297221717653230664178554647801162742366208, 662567649291894123593736562778594443435306461328357109295602325484732416, 1325135298583788247187473125557188886870612922656714218591204650969464832, 2650270597167576494374946251114377773741225845313428437182409301938929664, 5300541194335152988749892502228755547482451690626856874364818603877859328, 10601082388670305977499785004457511094964903381253713748729637207755718656, 21202164777340611954999570008915022189929806762507427497459274415511437312, 42404329554681223909999140017830044379859613525014854994918548831022874624, 84808659109362447819998280035660088759719227050029709989837097662045749248, 169617318218724895639996560071320177519438454100059419979674195324091498496, 339234636437449791279993120142640355038876908200118839959348390648182996992, 678469272874899582559986240285280710077753816400237679918696781296365993984, 1356938545749799165119972480570561420155507632800475359837393562592731987968, 2713877091499598330239944961141122840311015265600950719674787125185463975936, 5427754182999196660479889922282245680622030531201901439349574250370927951872, 10855508365998393320959779844564491361244061062403802878699148500741855903744, 21711016731996786641919559689128982722488122124807605757398297001483711807488, 43422033463993573283839119378257965444976244249615211514796594002967423614976, 86844066927987146567678238756515930889952488499230423029593188005934847229952, 173688133855974293135356477513031861779904976998460846059186376011869694459904, 347376267711948586270712955026063723559809953996921692118372752023739388919808, 694752535423897172541425910052127447119619907993843384236745504047478777839616, 1389505070847794345082851820104254894239239815987686768473491008094957555679232, 2779010141695588690165703640208509788478479631975373536946982016189915111358464, 5558020283391177380331407280417019576956959263950747073893964032379830222716928, 11116040566782354760662814560834039153913918527901494147787928064759660445433856, 22232081133564709521325629121668078307827837055802988295575856129519320890867712, 44464162267129419042651258243336156615655674111605976591151712259038641781735424, 88928324534258838085302516486672313231311348223211953182303424518077283563470848, 177856649068517676170605032973344626462622696446423906364606849036154567126941696, 355713298137035352341210065946689252925245392892847812729213698072309134253883392, 711426596274070704682420131893378505850490785785695625458427396144618268507766784, 1422853192548141409364840263786757011700981571571391250916854792289236537015533568, 2845706385096282818729680527573514023401963143142782501833709584578473074031067136, 5691412770192565637459361055147028046803926286285565003667419169156946148062134272, 11382825540385131274918722110294056093607852572571130007334838338313892296124268544, 22765651080770262549837444220588112187215705145142260014669676676627784592248537088, 45531302161540525099674888441176224374431410290284520029339353353255569184497074176, 91062604323081050199349776882352448748862820580569040058678706706511138368994148352, 182125208646162100398699553764704897497725641161138080117357413413022276737988296704, 364250417292324200797399107529409794995451282322276160234714826826044553475976593408, 728500834584648401594798215058819589990902564644552320469429653652089106951953186816, 1457001669169296803189596430117639179981805129289104640938859307304178213903906373632, 2914003338338593606379192860235278359963610258578209281877718614608356427807812747264, 5828006676677187212758385720470556719927220517156418563755437229216712855615625494528, 11656013353354374425516771440941113439854441034312837127510874458433425711231250989056, 23312026706708748851033542881882226879708882068625674255021748916866851422462501978112, 46624053413417497702067085763764453759417764137251348510043497833733702844925003956224, 93248106826834995404134171527528907518835528274502697020086995667467405689850007912448, 186496213653669990808268343055057815037671056549005394040173991334934811379700015824896]
Bag=Bag[::-1]
m=372992427307339981616536686110115630075342113098010788080347982669869622759400031649792
w=274062421102700155372289583695782343443

assert gmpy2.gcd(m,w)==1
h=0
j=0
if m.bit_length()%2==0:
    h=m.bit_length()
    j=int(h//2)
else:
    h=m.bit_length()
    j=int(h//2+1)
def pad(m,lenth):
    while len(m)<lenth:
        m='0'+m
    return m

def keygen():
    pk=[]
    sk=[]
    sk.append(m)
    sk.append(int(gmpy2.invert(w,m)))
    D=[]
    binD=[]
    for i in range(Baglenth):
        di=(w*Bag[i])%m
        D.append(di)
        bindi=bin(di)[2:]
        bindi=pad(bindi,h)
        binD.append(bindi)
    U=[]
    V=[]
    for i in range(Baglenth):
        tempu=int(str(binD[i][:j]),2)
        U.append(tempu)
        tempv=int(str(binD[i][j:]),2)
        V.append(tempv)
    e=gmpy2.next_prime(sum(V))+2
    f=gmpy2.next_prime(sum(U))
    assert gmpy2.gcd(e,f)==1
    sk.append(int(e))
    sk.append(int(f))
    for i in range(Baglenth):
        ai=e*U[i]+f*V[i]
        pk.append(int(ai))
    return pk,sk

Pk,Sk=keygen()
print(Pk)
print(Sk)

def Encrypt(plain,pk):
    mbin=bin(plain)[2:]
    c=0
    mbin=pad(mbin,Baglenth)
    for i in range(Baglenth):
        c=c+int(mbin[i])*pk[i]
    return c

c=Encrypt(message,Pk)
print(c)

# [13427720507293490146512325883268574617159432219330328705146993381673927145360640901644288, 20141580760940235219768488824902861925739148328995493057720490072510890718040961352466432, 10070790380470117609884244412451430962869574164497746528860245036255445359020480676233216, 5035395190235058804942122206225715481434787082248873264430122518127722679510240338116608, 15945418102411019548983386986381432357876825760454765337362054640737788485115761070702592, 7972709051205509774491693493190716178938412880227382668681027320368894242557880535351296, 3986354525602754887245846746595358089469206440113691334340513660184447121278940267675648, 1993177262801377443622923373297679044734603220056845667170256830092223560639470133837824, 14424309138694178868323787569917414139526733829358751538732121796720038925680375968563200, 20639875076640579580674219668227281686922799134009704474513054280033946608200828885925888, 10319937538320289790337109834113640843461399567004852237256527140016973304100414442962944, 5159968769160144895168554917056820421730699783502426118628263570008486652050207221481472, 16007704891873562594096603341796984828024782111081541764461125166678170471385744512385024, 21431572953230271443560627554167067031171823274871099587377555965013012381053513157836800, 24143506983908625868292639660352108132745343856765878498835771364180433335887397480562688, 25499473999247803080658645713444628683532104147713267954564879063764143813304339641925632, 26177457506917391686841648739990888958925484293186962682429432913555999052012810722607104, 13088728753458695843420824369995444479462742146593481341214716456777999526006405361303552, 6544364376729347921710412184997722239731371073296740670607358228388999763003202680651776, 16699902695658164107367531975767435737025117755978699040450672495868427026862242241970176, 8349951347829082053683765987883717868512558877989349520225336247934213513431121120985088, 4174975673914541026841882993941858934256279438994674760112668123967106756715560560492544, 2087487836957270513420941496970929467128139719497337380056334061983553378357780280246272, 1043743918478635256710470748485464733564069859748668690028167030991776689178890140123136, 521871959239317628355235374242732366782034929874334345014083515495888344589445070061568, 260935979619658814177617687121366183391017464937167172507041757747944172294722535030784, 13558188497103319553601134726829257708854940951798912291400514260547899231508002169159680, 20206814755845149923312893246683203471586902695229784850847250511947876761114641986224128, 23531127885216065108168772506610176352952883566945221130570618637647865525917961894756352, 25193284449901522700596712136573662793635874002802939270432302700497859908319621849022464, 12596642224950761350298356068286831396817937001401469635216151350248929954159810924511232, 6298321112475380675149178034143415698408968500700734817608075675124464977079905462255616, 16576881063531180484086914900340282466363916469680696113951031219236159633900593632772096, 21716161039059080388555783333438715850341390454170676762122508991292006962310937718030336, 10858080519529540194277891666719357925170695227085338381061254495646003481155468859015168, 5429040259764770097138945833359678962585347613542669190530627247823001740577734429507584, 2714520129882385048569472916679839481292673806771334595265313623911500870288867214753792, 1357260064941192524284736458339919740646336903385667297632656811955750435144433607376896, 678630032470596262142368229169959870323168451692833648816328405977875217572216803688448, 13767035523528788277583509997853554552321016445176745529555157584662864754146749303488512, 6883517761764394138791754998926777276160508222588372764777578792331432377073374651744256, 16869479388175687215908203382731963255239686330624515087535782777839643333897328227516416, 8434739694087843607954101691365981627619843165312257543767891388919821666948664113758208, 4217369847043921803977050845682990813809921582656128771883945694459910833474332056879104, 2108684923521960901988525422841495406904960791328064385941972847229955416737166028439552, 1054342461760980450994262711420747703452480395664032192970986423614977708368583014219776, 527171230880490225497131355710373851726240197832016096485493211807488854184291507109888, 13691306122733735259260891561123761543022552318246336753389739987577671572452786655199232, 20273373568660357776142771663830455388670708378453497081841863375462762931587034229243904, 10136686784330178888071385831915227694335354189226748540920931687731381465793517114621952, 18496063899458579590548018799226188464327109313943702975607459225539617878257399458955264, 9248031949729289795274009399613094232163554656971851487803729612769808939128699729477632, 4624015974864644897637004699806547116081777328485925743901864806384904469564349864738816, 2312007987432322448818502349903273558040888664242962871950932403192452234782174932369408, 14583724501009651370921577058220211396179876551451810141122459583270153262751728367828992, 7291862250504825685460788529110105698089938275725905070561229791635076631375864183914496, 3645931125252412842730394264555052849044969137862952535280614895817538315687932091957248, 15250686069919696567877523015546101041681916788261804972787300829582696303204606947622912, 7625343034959848283938761507773050520840958394130902486393650414791348151602303473811456, 17240392024773414288481706637155099877579911416395779948343818589069601221161792638550016, 22047916519680197290753179201846124555949387927528218679318902676208727755941537220919296, 24451678767133588791888915484191636895134126183094438044806444719778291023331409512103936, 25653559890860284542456783625364393064726495310877547727550215741563072657026345657696256, 26254500452723632417740717695950771149522679874769102568922101252455463473873813730492416, 26554970733655306355382684731243960191920772156714879989608044007901658882297547766890496, 26705205874121143324203668248890554713119818297687768699951015385624756586509414785089536, 26780323444354061808614160007713851973719341368174213055122501074486305438615348294189056, 13390161722177030904307080003856925986859670684087106527561250537243152719307674147094528, 20122801368382005598665865885197037610589267561373881968927618650295503505014477975191552, 23489121191484492945845258825867093422454066000017269689610802706821678897867879889240064, 11744560595742246472922629412933546711227033000008634844805401353410839448933939944620032, 5872280297871123236461314706466773355613516500004317422402700676705419724466969972310016, 16363860656229051764742983236501961294966190469332487416348343720026637007594125887799296, 8181930328114525882371491618250980647483095234666243708174171860013318503797062943899648, 17518685671350753087698071692394064940900979836663450559234079311680586397259172373594112, 8759342835675376543849035846197032470450489918331725279617039655840293198629586186797056, 17807391925131178418436843806367090852384677178496191344955513209594073744675433995042816, 8903695962565589209218421903183545426192338589248095672477756604797036872337716997521408, 17879568488576284751121536834860347330255601513954376541385871684072445581529499400404992, 8939784244288142375560768417430173665127800756977188270692935842036222790764749700202496, 17897612629437561334292710091983661449723332597818922840493461302692038540743015751745536, 8948806314718780667146355045991830724861666298909461420246730651346019270371507875872768, 4474403157359390333573177522995915362430833149454730710123365325673009635185753937936384, 15664922085973185313298914644766532298374848794057694060208676044510431962953517870612480, 21260181550280082803161783205651840766346856616359175735251331403929143126837399836950528, 24057811282433531548093217486094495000332860527509916572772659083638498708779340820119552, 25456626148510255920558934626315822117325862483085286991533322923493176499750311311704064, 26156033581548618106791793196426485675822363460872972200913654843420515395235796557496320, 26505737298067799199908222481481817455070613949766814805603820803384184842978539180392448, 13252868649033899599954111240740908727535306974883407402801910401692092421489269590196224, 6626434324516949799977055620370454363767653487441703701400955200846046210744634795098112, 3313217162258474899988527810185227181883826743720851850700477600423023105372317397549056, 15084329088422727596506589788361188208101345591190754630497232181885438698046799600418816, 7542164544211363798253294894180594104050672795595377315248616090942719349023399800209408, 3771082272105681899126647447090297052025336397797688657624308045471359674511699900104704, 15313261643346331096075649606813723143172100418229173033959147404409606982616490851696640, 21084351328966655694550150686675436188745482428444915222126567083878730636668886327492608, 10542175664483327847275075343337718094372741214222457611063283541939365318334443163746304, 5271087832241663923637537671668859047186370607111228805531641770969682659167221581873152, 16063264423414322108331094719103004140752617522885943107912814267158768474944251692580864, 21459352719000651200677873242820076687535740980773300259103400515253311382832766747934720, 10729676359500325600338936621410038343767870490386650129551700257626655691416383373967360, 5364838179750162800169468310705019171883935245193325064775850128813327845708191686983680, 16110139597168571546597060038621084203101399841926991237534918446080591068214736745136128, 8055069798584285773298530019310542101550699920963495618767459223040295534107368372568064, 4027534899292142886649265009655271050775349960481747809383729611520147767053684186284032, 2013767449646071443324632504827635525387674980240873904691864805760073883526842093142016, 1006883724823035721662316252413817762693837490120436952345932402880036941763421046571008, 503441862411517860831158126206908881346918745060218476172966201440018470881710523285504, 251720931205758930415579063103454440673459372530109238086483100720009235440855261642752, 125860465602879465207789531551727220336729686265054619043241550360004617720427630821376, 13490650740094929879116220649044438227327797062462856014668614156853929454220854717054976, 6745325370047464939558110324522219113663898531231428007334307078426964727110427358527488, 16800383192317222616291381045529684173991381484946042708814146920887409508915854580908032, 21827912103452101454658016406033416704155122961803350059554066842117631899818568192098304, 24341676559019540873841334086285282969236993700232003734924026802732743095269924997693440, 12170838279509770436920667043142641484618496850116001867462013401366371547634962498846720, 19513139647048375364972659404839895359468680644388329638878000082357112919178122151067648, 9756569823524187682486329702419947679734340322194164819439000041178556459589061075533824, 4878284911762093841243164851209973839867170161097082409719500020589278229794530537766912, 2439142455881046920621582425604986919933585080548541204859750010294639114897265268883456, 14647291735234013606823117096071068077126224759604599307576868386821246702809273536086016, 20751366374910496949923884431304108655722544599132628358935427575084550496765277669687296, 23803403694748738621474268098920628945020704518896642884614707169216202393743279736487936, 11901701847374369310737134049460314472510352259448321442307353584608101196871639868243968, 5950850923687184655368567024730157236255176129724160721153676792304050598435819934121984, 16403145969137082474196609395633653235287020284192409065723831777825952444578550868705280, 21629293491862031383610630581085401234802942361426533238008909270586903367649916335996928, 10814646745931015691805315290542700617401471180713266619004454635293451683824958167998464, 5407323372965507845902657645271350308700735590356633309502227317646725841912479083999232, 2703661686482753922951328822635675154350367795178316654751113658823362920956239541999616, 1351830843241376961475664411317837577175183897589158327375556829411681460478119770999808, 675915421620688480737832205658918788587591948794579163687778414705840730239059885499904, 337957710810344240368916102829459394293795974397289581843889207352920365119529942749952, 168978855405172120184458051414729697146897987198644790921944603676460182559764971374976, 84489427702586060092229025707364848573448993599322395460972301838230091279882485687488, 42244713851293030046114512853682424286724496799661197730486150919115045639941242843744, 21122356925646515023057256426841212143362248399830598865243075459557522819970621421872, 10561178462823257511528628213420606071681124199915299432621537729778761409985310710936, 5280589231411628755764314106710303035840562099957649716310768864889380704992655355468, 2640294615705814377882157053355151517920281049978824858155384432444690352496327677734, 1320147307852907188941078526677575758960140524989412429077692216222345176248163838867, 11376929106527795892898839465621865505177413571970563898745322852504166513570004716585524, 5688464553263897946449419732810932752588706785985281949372661426252083256785002358292762, 2844232276631948973224709866405466376294353392992640974686330713126041628392501179146381, 12798385171189843925916723859561259905445110198204389679873949362959076155178131224239281, 17775461618468791402262730856139156670020488600810264032467758687875593418570946246785731, 20263999842108265140435734354428105052308177802113201208764663350333852050267353758058956, 10131999921054132570217867177214052526154088901056600604382331675166926025133676879029478, 5065999960527066285108933588607026263077044450528300302191165837583463012566838439514739, 13909269013137402581858835720662039848836455726972219343626366925187786847265299854423460, 6954634506568701290929417860331019924418227863486109671813183462593893423632649927211730, 3477317253284350645464708930165509962209113931743054835906591731296946711816324963605865, 13114927659516044762036723391441281698402490467579596610484079872044528696890043116469023, 17933732862631891820322730622079167566499178735497867497772823942418319689426902192900602, 8966866431315945910161365311039583783249589367748933748886411971209159844713451096450301, 15859702248531842394385051581878318608922728185582536066973989992000635263338606182891241, 19306120157139790636496894717297686021759297594499337226017779002396372972651183726111711, 21029329111443764757552816285007369728177582298957737805539673507594241827307472497721946, 10514664555721882378776408142503684864088791149478868902769836753797120913653736248860973, 16633601310734810628692572997610369149342329076447503643915702383294615797808748759096577, 19693069688241274753650655425163711291969098039931821014488635198043363239886255014214379, 21222803876994506816129696638940382363282482521673979699775101605417736960925008141773280, 10611401938497253408064848319470191181641241260836989849887550802708868480462504070886640, 5305700969248626704032424159735095590820620630418494924943775401354434240231252035443320, 2652850484624313352016212079867547795410310315209247462471887700677217120115626017721660, 1326425242312156676008106039933773897705155157604623731235943850338608560057813008860830, 663212621156078338004053019966886948852577578802311865617971925169304280028906504430415, 11707875343451908608306395436341970191724222291109225125339769968980707480996333886881298, 5853937671725954304153197718170985095862111145554612562669884984490353740498166943440649, 14303237868736846591380967785444019265228989074485375473865726498641232211230964106386415, 18527887967242292734994852819080536349912428038950756929463647255716671446597362687859298, 9263943983621146367497426409540268174956214019475378464731823627858335723298681343929649, 16008241024684442623053082131128660804776040511445758424896695820325223202631221306630915, 19380389545216090750830909991922857119685953757430948404979131916558666942297491287981548, 9690194772608045375415454995961428559842976878715474202489565958279333471148745643990774, 4845097386304022687707727497980714279921488439357737101244782979139666735574372821995387, 13798817726025880783158232675348883857258677721386937743153175495965888708769067045663784, 6899408863012940391579116337674441928629338860693468871576587747982944354384533522831892, 3449704431506470195789558168837220964314669430346734435788293873991472177192266761415946, 1724852215753235097894779084418610482157334715173367217894146936995736088596133380707973, 12238695140750486988251758468567831958376600859294752801477857474893923385279947325020077, 17495616603249112933430248160642442696486233931355445593269712743843017033621854297176129, 20124077334498425906019493006679748065541050467385791989165640378317563857792807783254155, 21438307700123082392314115429698400750068458735400965187113604195554837269878284526293168, 10719153850061541196157057714849200375034229367700482593556802097777418634939142263146584, 5359576925030770598078528857424600187517114683850241296778401048888709317469571131573292, 2679788462515385299039264428712300093758557341925120648389200524444354658734785565786646, 1339894231257692649519632214356150046879278670962560324194600262222177329367392782893323, 12046216148502715764064185033536601740737572837189349354628084137507144005665577026112752, 6023108074251357882032092516768300870368786418594674677314042068753572002832788513056376, 3011554037125678941016046258384150435184393209297337338657021034376786001416394256528188, 1505777018562839470508023129192075217592196604648668669328510517188393000708197128264094, 752888509281419735254011564596037608796098302324334334664255258594196500354098564132047, 11752713287514579306931374708656545521695982652870236359862911635693153591158929916732114, 5876356643757289653465687354328272760847991326435118179931455817846576795579464958366057, 14314447354752514266037212603522663097721929164925628282496511915319343738771613113849119, 18533492710250126572322975228119858266158898084170883333779039964055727210367687191590650, 9266746355125063286161487614059929133079449042085441666889519982027863605183843595795325, 16009642210436401082385112733388491283837658022750790025975543997409987143573802432563753, 19381090138092069980496925293052772359216762513083464205518556005101048912768781850947967, 21066814101919904429552831572884912896906314758249801295290062008946579797366271560140074, 10533407050959952214776415786442456448453157379124900647645031004473289898683135780070037, 16642972558353845546692576819579754941524512191270519516353299508632700290323448524701109, 19697755312050792212650657336148404188060189597343328950707433760712405486143604897016645, 21225146688899265545629697594432728811328028300379733667884500886752258084053683083174413, 21988842377323502212119217723574891122961947651897936026473034449772184383008722176253297, 22370690221535620545363977788145972278778907327657037205767301231282147532486241722792739, 22561614143641679711986357820431512856687387165536587795414434622037129107225001496062460, 11280807071820839855993178910215756428343693582768293897707217311018564553612500748031230, 5640403535910419927996589455107878214171846791384146948853608655509282276806250374015615, 14196470800829079403302663653912465824383856897400142666957588334150696479385005821673898, 7098235400414539701651331826956232912191928448700071333478794167075348239692502910836949, 14925386733081139290130034839836643173393897726058104859270181089933729460828132090084565, 18838962399414439084369386346276848303994882364737121622165874551362920071395946679708373, 20795750232581088981489062099496950869295374684076630003613721282077515376679853974520277, 21774144149164413930048899976107002151945620843746384194337644647434813029321807621926229, 22263341107456076404328818914412027793270743923581261289699606330113461855642784445629205, 22507939586601907641468778383564540613933305463498699837380587171452786268803272857480693, 22630238826174823260038758118140797024264586233457419111221077592122448475383517063406437, 22691388445961281069323747985428925229430226618436778748141322802457279578673639166369309, 22721963255854509973966242919072989332013046810926458566601445407624695130318700217850745, 22737250660801124426287490385895021383304456907171298475831506710208402906141230743591463, 22744894363274431652448114119306037408950161955293718430446537361500256794052496006461822, 11372447181637215826224057059653018704475080977646859215223268680750128397026248003230911, 17062492623692477352416397456185036069535473990531498800142418346771119539495004636281546, 8531246311846238676208198728092518034767736995265749400071209173385559769747502318140773, 15641892188796988777408468290404785734681801999340943892566388593088835225855631793736477, 19197215127272363828008603071560919584638834501378541138813978302940472953909696531534329, 20974876596510051353308670462138986509617350752397339761937773157866291817936728900433255, 21863707331128895115958704157428019972106608877906739073499670585329201249950245084882718, 10931853665564447557979352078714009986053304438953369536749835292664600624975122542441359, 16842195865656093218294044965715531710324585721184753960905701652728355653469441905886770, 8421097932828046609147022482857765855162292860592376980452850826364177826734720952943385, 15586817999287892743877880167787409644879079932004257682757209419578144254349241111137783, 19169678032517815811243309010252231539737473467710198033909388716185127468156501190234982, 9584839016258907905621654505126115769868736733855099016954694358092563734078250595117491, 16168688541003323392115196178921584602232301868635618701008131185442337208021005932224836, 8084344270501661696057598089460792301116150934317809350504065592721168604010502966112418, 4042172135250830848028799044730396150558075467158904675252032796360584302005251483056209, 13397355100499284863318768448723724792576971235287521530156800404576347491984506376194195, 18074946583123511870963753150720389113586419119351829957609184208684229086974133822763188, 9037473291561755935481876575360194556793209559675914978804592104342114543487066911381594, 4518736645780877967740938287680097278396604779837957489402296052171057271743533455690797, 13635637355764308423174838070198575356496235891627047937231932032481583976853647362511489, 18194087710756023650891787961457814395546051447521593161146750022636847329408704315921835, 20473312888251881264750262907087433915070959225468865773104159017714479005686232792627008, 10236656444125940632375131453543716957535479612734432886552079508857239502843116396313504, 5118328222062970316187565726771858478767739806367216443276039754428619751421558198156752, 2559164111031485158093782863385929239383869903183608221638019877214309875710779099078376, 1279582055515742579046891431692964619691934951591804110819009938607154937855389549539188, 639791027757871289523445715846482309845967475795902055409504969303577468927694774769594, 319895513878935644761722857923241154922983737897951027704752484651788734463847387384797, 11536216789813337261685230355320147294759425370657044706383160248721949708213804328358489, 17144377427780538070146984104018600364677646187036591545722364130757030195088782798845335, 19948457746764138474377860978367826899636756595226364965391966071774570438526272034088758, 9974228873382069237188930489183913449818378297613182482695983035887285219263136017044379, 16363383469564904057898834170950483442207122650514660433878775524339697950613448643188280, 8181691734782452028949417085475241721103561325257330216939387762169848975306724321594140, 4090845867391226014474708542737620860551780662628665108469693881084924487653362160797070, 2045422933695613007237354271368810430275890331314332554234846940542462243826681080398535, 12398980499721675942923046062042931932435878667365235469648207476667286462895221174865358, 6199490249860837971461523031021465966217939333682617734824103738333643231447610587432679, 14476014157804288425035130441869259700406903168549378059942835875562876956705685928382430, 7238007078902144212517565220934629850203451584274689029971417937781438478352842964191215, 14995272572324941545563151536825841642399659293845413707516492975286774580158302116761698, 7497636286162470772781575768412920821199829646922706853758246487643387290079151058380849, 15125087175955104825695156810564987127897848325169422619409907250217748986021456163856515, 18938812620851421852151947331641020281246857664292780502235737631504929833992608716594348, 9469406310425710926075973665820510140623428832146390251117868815752464916996304358297174, 4734703155212855463037986832910255070311714416073195125558934407876232458498152179148587, 13743620610480297170823362342813654252453790709744666755310251210334171570230956724240384, 6871810305240148585411681171406827126226895354872333377655125605167085785115478362120192, 3435905152620074292705840585703413563113447677436166688827562802583542892557739181060096, 1717952576310037146352920292851706781556723838718083344413781401291771446278869590530048, 858976288155018573176460146425853390778361919359041672206890700645885723139434795265024, 429488144077509286588230073212926695389180959679520836103445350322942861569717397632512, 214744072038754643294115036606463347694590479839760418051722675161471430784858698816256, 107372036019377321647057518303231673847295239919880209025861337580735715392429349408128, 53686018009688660823528759151615836923647619959940104512930668790367857696214674704064, 26843009004844330411764379575807918461823809979970052256465334395183928848107337352032, 13421504502422165205882189787903959230911904989985026128232667197591964424053668676016, 6710752251211082602941094893951979615455952494992513064116333598795982212026834338008, 3355376125605541301470547446975989807727976247496256532058166799397991106013417169004, 1677688062802770650735273723487994903863988123748128266029083399698995553006708584502, 838844031401385325367636861743997451931994061874064133014541699849497776503354292251]
# [372992427307339981616536686110115630075342113098010788080347982669869622759400031649792, 284117116837182934114178639859989682847967251175497623662086047895218803240335140835099, 1605652832106941558090105598761930941083559723, 1020259092832776008725259110973662538898604019]
# 1475864207352419823225329328555476398971654057144688193866218781853021651529290611526242518

之前没学习过背包密码。现在长长见识。

参考：密码学学习笔记 之 knapsack | Van1sh的小屋 (jayxv.github.io)

因为 $Pk$ 是无序的，所以构建矩阵如下：

进行LLL格基规约。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#sage
Pk = [13427720507293490146512325883268574617159432219330328705146993381673927145360640901644288, 20141580760940235219768488824902861925739148328995493057720490072510890718040961352466432, 10070790380470117609884244412451430962869574164497746528860245036255445359020480676233216, 5035395190235058804942122206225715481434787082248873264430122518127722679510240338116608, 15945418102411019548983386986381432357876825760454765337362054640737788485115761070702592, 7972709051205509774491693493190716178938412880227382668681027320368894242557880535351296, 3986354525602754887245846746595358089469206440113691334340513660184447121278940267675648, 1993177262801377443622923373297679044734603220056845667170256830092223560639470133837824, 14424309138694178868323787569917414139526733829358751538732121796720038925680375968563200, 20639875076640579580674219668227281686922799134009704474513054280033946608200828885925888, 10319937538320289790337109834113640843461399567004852237256527140016973304100414442962944, 5159968769160144895168554917056820421730699783502426118628263570008486652050207221481472, 16007704891873562594096603341796984828024782111081541764461125166678170471385744512385024, 21431572953230271443560627554167067031171823274871099587377555965013012381053513157836800, 24143506983908625868292639660352108132745343856765878498835771364180433335887397480562688, 25499473999247803080658645713444628683532104147713267954564879063764143813304339641925632, 26177457506917391686841648739990888958925484293186962682429432913555999052012810722607104, 13088728753458695843420824369995444479462742146593481341214716456777999526006405361303552, 6544364376729347921710412184997722239731371073296740670607358228388999763003202680651776, 16699902695658164107367531975767435737025117755978699040450672495868427026862242241970176, 8349951347829082053683765987883717868512558877989349520225336247934213513431121120985088, 4174975673914541026841882993941858934256279438994674760112668123967106756715560560492544, 2087487836957270513420941496970929467128139719497337380056334061983553378357780280246272, 1043743918478635256710470748485464733564069859748668690028167030991776689178890140123136, 521871959239317628355235374242732366782034929874334345014083515495888344589445070061568, 260935979619658814177617687121366183391017464937167172507041757747944172294722535030784, 13558188497103319553601134726829257708854940951798912291400514260547899231508002169159680, 20206814755845149923312893246683203471586902695229784850847250511947876761114641986224128, 23531127885216065108168772506610176352952883566945221130570618637647865525917961894756352, 25193284449901522700596712136573662793635874002802939270432302700497859908319621849022464, 12596642224950761350298356068286831396817937001401469635216151350248929954159810924511232, 6298321112475380675149178034143415698408968500700734817608075675124464977079905462255616, 16576881063531180484086914900340282466363916469680696113951031219236159633900593632772096, 21716161039059080388555783333438715850341390454170676762122508991292006962310937718030336, 10858080519529540194277891666719357925170695227085338381061254495646003481155468859015168, 5429040259764770097138945833359678962585347613542669190530627247823001740577734429507584, 2714520129882385048569472916679839481292673806771334595265313623911500870288867214753792, 1357260064941192524284736458339919740646336903385667297632656811955750435144433607376896, 678630032470596262142368229169959870323168451692833648816328405977875217572216803688448, 13767035523528788277583509997853554552321016445176745529555157584662864754146749303488512, 6883517761764394138791754998926777276160508222588372764777578792331432377073374651744256, 16869479388175687215908203382731963255239686330624515087535782777839643333897328227516416, 8434739694087843607954101691365981627619843165312257543767891388919821666948664113758208, 4217369847043921803977050845682990813809921582656128771883945694459910833474332056879104, 2108684923521960901988525422841495406904960791328064385941972847229955416737166028439552, 1054342461760980450994262711420747703452480395664032192970986423614977708368583014219776, 527171230880490225497131355710373851726240197832016096485493211807488854184291507109888, 13691306122733735259260891561123761543022552318246336753389739987577671572452786655199232, 20273373568660357776142771663830455388670708378453497081841863375462762931587034229243904, 10136686784330178888071385831915227694335354189226748540920931687731381465793517114621952, 18496063899458579590548018799226188464327109313943702975607459225539617878257399458955264, 9248031949729289795274009399613094232163554656971851487803729612769808939128699729477632, 4624015974864644897637004699806547116081777328485925743901864806384904469564349864738816, 2312007987432322448818502349903273558040888664242962871950932403192452234782174932369408, 14583724501009651370921577058220211396179876551451810141122459583270153262751728367828992, 7291862250504825685460788529110105698089938275725905070561229791635076631375864183914496, 3645931125252412842730394264555052849044969137862952535280614895817538315687932091957248, 15250686069919696567877523015546101041681916788261804972787300829582696303204606947622912, 7625343034959848283938761507773050520840958394130902486393650414791348151602303473811456, 17240392024773414288481706637155099877579911416395779948343818589069601221161792638550016, 22047916519680197290753179201846124555949387927528218679318902676208727755941537220919296, 24451678767133588791888915484191636895134126183094438044806444719778291023331409512103936, 25653559890860284542456783625364393064726495310877547727550215741563072657026345657696256, 26254500452723632417740717695950771149522679874769102568922101252455463473873813730492416, 26554970733655306355382684731243960191920772156714879989608044007901658882297547766890496, 26705205874121143324203668248890554713119818297687768699951015385624756586509414785089536, 26780323444354061808614160007713851973719341368174213055122501074486305438615348294189056, 13390161722177030904307080003856925986859670684087106527561250537243152719307674147094528, 20122801368382005598665865885197037610589267561373881968927618650295503505014477975191552, 23489121191484492945845258825867093422454066000017269689610802706821678897867879889240064, 11744560595742246472922629412933546711227033000008634844805401353410839448933939944620032, 5872280297871123236461314706466773355613516500004317422402700676705419724466969972310016, 16363860656229051764742983236501961294966190469332487416348343720026637007594125887799296, 8181930328114525882371491618250980647483095234666243708174171860013318503797062943899648, 17518685671350753087698071692394064940900979836663450559234079311680586397259172373594112, 8759342835675376543849035846197032470450489918331725279617039655840293198629586186797056, 17807391925131178418436843806367090852384677178496191344955513209594073744675433995042816, 8903695962565589209218421903183545426192338589248095672477756604797036872337716997521408, 17879568488576284751121536834860347330255601513954376541385871684072445581529499400404992, 8939784244288142375560768417430173665127800756977188270692935842036222790764749700202496, 17897612629437561334292710091983661449723332597818922840493461302692038540743015751745536, 8948806314718780667146355045991830724861666298909461420246730651346019270371507875872768, 4474403157359390333573177522995915362430833149454730710123365325673009635185753937936384, 15664922085973185313298914644766532298374848794057694060208676044510431962953517870612480, 21260181550280082803161783205651840766346856616359175735251331403929143126837399836950528, 24057811282433531548093217486094495000332860527509916572772659083638498708779340820119552, 25456626148510255920558934626315822117325862483085286991533322923493176499750311311704064, 26156033581548618106791793196426485675822363460872972200913654843420515395235796557496320, 26505737298067799199908222481481817455070613949766814805603820803384184842978539180392448, 13252868649033899599954111240740908727535306974883407402801910401692092421489269590196224, 6626434324516949799977055620370454363767653487441703701400955200846046210744634795098112, 3313217162258474899988527810185227181883826743720851850700477600423023105372317397549056, 15084329088422727596506589788361188208101345591190754630497232181885438698046799600418816, 7542164544211363798253294894180594104050672795595377315248616090942719349023399800209408, 3771082272105681899126647447090297052025336397797688657624308045471359674511699900104704, 15313261643346331096075649606813723143172100418229173033959147404409606982616490851696640, 21084351328966655694550150686675436188745482428444915222126567083878730636668886327492608, 10542175664483327847275075343337718094372741214222457611063283541939365318334443163746304, 5271087832241663923637537671668859047186370607111228805531641770969682659167221581873152, 16063264423414322108331094719103004140752617522885943107912814267158768474944251692580864, 21459352719000651200677873242820076687535740980773300259103400515253311382832766747934720, 10729676359500325600338936621410038343767870490386650129551700257626655691416383373967360, 5364838179750162800169468310705019171883935245193325064775850128813327845708191686983680, 16110139597168571546597060038621084203101399841926991237534918446080591068214736745136128, 8055069798584285773298530019310542101550699920963495618767459223040295534107368372568064, 4027534899292142886649265009655271050775349960481747809383729611520147767053684186284032, 2013767449646071443324632504827635525387674980240873904691864805760073883526842093142016, 1006883724823035721662316252413817762693837490120436952345932402880036941763421046571008, 503441862411517860831158126206908881346918745060218476172966201440018470881710523285504, 251720931205758930415579063103454440673459372530109238086483100720009235440855261642752, 125860465602879465207789531551727220336729686265054619043241550360004617720427630821376, 13490650740094929879116220649044438227327797062462856014668614156853929454220854717054976, 6745325370047464939558110324522219113663898531231428007334307078426964727110427358527488, 16800383192317222616291381045529684173991381484946042708814146920887409508915854580908032, 21827912103452101454658016406033416704155122961803350059554066842117631899818568192098304, 24341676559019540873841334086285282969236993700232003734924026802732743095269924997693440, 12170838279509770436920667043142641484618496850116001867462013401366371547634962498846720, 19513139647048375364972659404839895359468680644388329638878000082357112919178122151067648, 9756569823524187682486329702419947679734340322194164819439000041178556459589061075533824, 4878284911762093841243164851209973839867170161097082409719500020589278229794530537766912, 2439142455881046920621582425604986919933585080548541204859750010294639114897265268883456, 14647291735234013606823117096071068077126224759604599307576868386821246702809273536086016, 20751366374910496949923884431304108655722544599132628358935427575084550496765277669687296, 23803403694748738621474268098920628945020704518896642884614707169216202393743279736487936, 11901701847374369310737134049460314472510352259448321442307353584608101196871639868243968, 5950850923687184655368567024730157236255176129724160721153676792304050598435819934121984, 16403145969137082474196609395633653235287020284192409065723831777825952444578550868705280, 21629293491862031383610630581085401234802942361426533238008909270586903367649916335996928, 10814646745931015691805315290542700617401471180713266619004454635293451683824958167998464, 5407323372965507845902657645271350308700735590356633309502227317646725841912479083999232, 2703661686482753922951328822635675154350367795178316654751113658823362920956239541999616, 1351830843241376961475664411317837577175183897589158327375556829411681460478119770999808, 675915421620688480737832205658918788587591948794579163687778414705840730239059885499904, 337957710810344240368916102829459394293795974397289581843889207352920365119529942749952, 168978855405172120184458051414729697146897987198644790921944603676460182559764971374976, 84489427702586060092229025707364848573448993599322395460972301838230091279882485687488, 42244713851293030046114512853682424286724496799661197730486150919115045639941242843744, 21122356925646515023057256426841212143362248399830598865243075459557522819970621421872, 10561178462823257511528628213420606071681124199915299432621537729778761409985310710936, 5280589231411628755764314106710303035840562099957649716310768864889380704992655355468, 2640294615705814377882157053355151517920281049978824858155384432444690352496327677734, 1320147307852907188941078526677575758960140524989412429077692216222345176248163838867, 11376929106527795892898839465621865505177413571970563898745322852504166513570004716585524, 5688464553263897946449419732810932752588706785985281949372661426252083256785002358292762, 2844232276631948973224709866405466376294353392992640974686330713126041628392501179146381, 12798385171189843925916723859561259905445110198204389679873949362959076155178131224239281, 17775461618468791402262730856139156670020488600810264032467758687875593418570946246785731, 20263999842108265140435734354428105052308177802113201208764663350333852050267353758058956, 10131999921054132570217867177214052526154088901056600604382331675166926025133676879029478, 5065999960527066285108933588607026263077044450528300302191165837583463012566838439514739, 13909269013137402581858835720662039848836455726972219343626366925187786847265299854423460, 6954634506568701290929417860331019924418227863486109671813183462593893423632649927211730, 3477317253284350645464708930165509962209113931743054835906591731296946711816324963605865, 13114927659516044762036723391441281698402490467579596610484079872044528696890043116469023, 17933732862631891820322730622079167566499178735497867497772823942418319689426902192900602, 8966866431315945910161365311039583783249589367748933748886411971209159844713451096450301, 15859702248531842394385051581878318608922728185582536066973989992000635263338606182891241, 19306120157139790636496894717297686021759297594499337226017779002396372972651183726111711, 21029329111443764757552816285007369728177582298957737805539673507594241827307472497721946, 10514664555721882378776408142503684864088791149478868902769836753797120913653736248860973, 16633601310734810628692572997610369149342329076447503643915702383294615797808748759096577, 19693069688241274753650655425163711291969098039931821014488635198043363239886255014214379, 21222803876994506816129696638940382363282482521673979699775101605417736960925008141773280, 10611401938497253408064848319470191181641241260836989849887550802708868480462504070886640, 5305700969248626704032424159735095590820620630418494924943775401354434240231252035443320, 2652850484624313352016212079867547795410310315209247462471887700677217120115626017721660, 1326425242312156676008106039933773897705155157604623731235943850338608560057813008860830, 663212621156078338004053019966886948852577578802311865617971925169304280028906504430415, 11707875343451908608306395436341970191724222291109225125339769968980707480996333886881298, 5853937671725954304153197718170985095862111145554612562669884984490353740498166943440649, 14303237868736846591380967785444019265228989074485375473865726498641232211230964106386415, 18527887967242292734994852819080536349912428038950756929463647255716671446597362687859298, 9263943983621146367497426409540268174956214019475378464731823627858335723298681343929649, 16008241024684442623053082131128660804776040511445758424896695820325223202631221306630915, 19380389545216090750830909991922857119685953757430948404979131916558666942297491287981548, 9690194772608045375415454995961428559842976878715474202489565958279333471148745643990774, 4845097386304022687707727497980714279921488439357737101244782979139666735574372821995387, 13798817726025880783158232675348883857258677721386937743153175495965888708769067045663784, 6899408863012940391579116337674441928629338860693468871576587747982944354384533522831892, 3449704431506470195789558168837220964314669430346734435788293873991472177192266761415946, 1724852215753235097894779084418610482157334715173367217894146936995736088596133380707973, 12238695140750486988251758468567831958376600859294752801477857474893923385279947325020077, 17495616603249112933430248160642442696486233931355445593269712743843017033621854297176129, 20124077334498425906019493006679748065541050467385791989165640378317563857792807783254155, 21438307700123082392314115429698400750068458735400965187113604195554837269878284526293168, 10719153850061541196157057714849200375034229367700482593556802097777418634939142263146584, 5359576925030770598078528857424600187517114683850241296778401048888709317469571131573292, 2679788462515385299039264428712300093758557341925120648389200524444354658734785565786646, 1339894231257692649519632214356150046879278670962560324194600262222177329367392782893323, 12046216148502715764064185033536601740737572837189349354628084137507144005665577026112752, 6023108074251357882032092516768300870368786418594674677314042068753572002832788513056376, 3011554037125678941016046258384150435184393209297337338657021034376786001416394256528188, 1505777018562839470508023129192075217592196604648668669328510517188393000708197128264094, 752888509281419735254011564596037608796098302324334334664255258594196500354098564132047, 11752713287514579306931374708656545521695982652870236359862911635693153591158929916732114, 5876356643757289653465687354328272760847991326435118179931455817846576795579464958366057, 14314447354752514266037212603522663097721929164925628282496511915319343738771613113849119, 18533492710250126572322975228119858266158898084170883333779039964055727210367687191590650, 9266746355125063286161487614059929133079449042085441666889519982027863605183843595795325, 16009642210436401082385112733388491283837658022750790025975543997409987143573802432563753, 19381090138092069980496925293052772359216762513083464205518556005101048912768781850947967, 21066814101919904429552831572884912896906314758249801295290062008946579797366271560140074, 10533407050959952214776415786442456448453157379124900647645031004473289898683135780070037, 16642972558353845546692576819579754941524512191270519516353299508632700290323448524701109, 19697755312050792212650657336148404188060189597343328950707433760712405486143604897016645, 21225146688899265545629697594432728811328028300379733667884500886752258084053683083174413, 21988842377323502212119217723574891122961947651897936026473034449772184383008722176253297, 22370690221535620545363977788145972278778907327657037205767301231282147532486241722792739, 22561614143641679711986357820431512856687387165536587795414434622037129107225001496062460, 11280807071820839855993178910215756428343693582768293897707217311018564553612500748031230, 5640403535910419927996589455107878214171846791384146948853608655509282276806250374015615, 14196470800829079403302663653912465824383856897400142666957588334150696479385005821673898, 7098235400414539701651331826956232912191928448700071333478794167075348239692502910836949, 14925386733081139290130034839836643173393897726058104859270181089933729460828132090084565, 18838962399414439084369386346276848303994882364737121622165874551362920071395946679708373, 20795750232581088981489062099496950869295374684076630003613721282077515376679853974520277, 21774144149164413930048899976107002151945620843746384194337644647434813029321807621926229, 22263341107456076404328818914412027793270743923581261289699606330113461855642784445629205, 22507939586601907641468778383564540613933305463498699837380587171452786268803272857480693, 22630238826174823260038758118140797024264586233457419111221077592122448475383517063406437, 22691388445961281069323747985428925229430226618436778748141322802457279578673639166369309, 22721963255854509973966242919072989332013046810926458566601445407624695130318700217850745, 22737250660801124426287490385895021383304456907171298475831506710208402906141230743591463, 22744894363274431652448114119306037408950161955293718430446537361500256794052496006461822, 11372447181637215826224057059653018704475080977646859215223268680750128397026248003230911, 17062492623692477352416397456185036069535473990531498800142418346771119539495004636281546, 8531246311846238676208198728092518034767736995265749400071209173385559769747502318140773, 15641892188796988777408468290404785734681801999340943892566388593088835225855631793736477, 19197215127272363828008603071560919584638834501378541138813978302940472953909696531534329, 20974876596510051353308670462138986509617350752397339761937773157866291817936728900433255, 21863707331128895115958704157428019972106608877906739073499670585329201249950245084882718, 10931853665564447557979352078714009986053304438953369536749835292664600624975122542441359, 16842195865656093218294044965715531710324585721184753960905701652728355653469441905886770, 8421097932828046609147022482857765855162292860592376980452850826364177826734720952943385, 15586817999287892743877880167787409644879079932004257682757209419578144254349241111137783, 19169678032517815811243309010252231539737473467710198033909388716185127468156501190234982, 9584839016258907905621654505126115769868736733855099016954694358092563734078250595117491, 16168688541003323392115196178921584602232301868635618701008131185442337208021005932224836, 8084344270501661696057598089460792301116150934317809350504065592721168604010502966112418, 4042172135250830848028799044730396150558075467158904675252032796360584302005251483056209, 13397355100499284863318768448723724792576971235287521530156800404576347491984506376194195, 18074946583123511870963753150720389113586419119351829957609184208684229086974133822763188, 9037473291561755935481876575360194556793209559675914978804592104342114543487066911381594, 4518736645780877967740938287680097278396604779837957489402296052171057271743533455690797, 13635637355764308423174838070198575356496235891627047937231932032481583976853647362511489, 18194087710756023650891787961457814395546051447521593161146750022636847329408704315921835, 20473312888251881264750262907087433915070959225468865773104159017714479005686232792627008, 10236656444125940632375131453543716957535479612734432886552079508857239502843116396313504, 5118328222062970316187565726771858478767739806367216443276039754428619751421558198156752, 2559164111031485158093782863385929239383869903183608221638019877214309875710779099078376, 1279582055515742579046891431692964619691934951591804110819009938607154937855389549539188, 639791027757871289523445715846482309845967475795902055409504969303577468927694774769594, 319895513878935644761722857923241154922983737897951027704752484651788734463847387384797, 11536216789813337261685230355320147294759425370657044706383160248721949708213804328358489, 17144377427780538070146984104018600364677646187036591545722364130757030195088782798845335, 19948457746764138474377860978367826899636756595226364965391966071774570438526272034088758, 9974228873382069237188930489183913449818378297613182482695983035887285219263136017044379, 16363383469564904057898834170950483442207122650514660433878775524339697950613448643188280, 8181691734782452028949417085475241721103561325257330216939387762169848975306724321594140, 4090845867391226014474708542737620860551780662628665108469693881084924487653362160797070, 2045422933695613007237354271368810430275890331314332554234846940542462243826681080398535, 12398980499721675942923046062042931932435878667365235469648207476667286462895221174865358, 6199490249860837971461523031021465966217939333682617734824103738333643231447610587432679, 14476014157804288425035130441869259700406903168549378059942835875562876956705685928382430, 7238007078902144212517565220934629850203451584274689029971417937781438478352842964191215, 14995272572324941545563151536825841642399659293845413707516492975286774580158302116761698, 7497636286162470772781575768412920821199829646922706853758246487643387290079151058380849, 15125087175955104825695156810564987127897848325169422619409907250217748986021456163856515, 18938812620851421852151947331641020281246857664292780502235737631504929833992608716594348, 9469406310425710926075973665820510140623428832146390251117868815752464916996304358297174, 4734703155212855463037986832910255070311714416073195125558934407876232458498152179148587, 13743620610480297170823362342813654252453790709744666755310251210334171570230956724240384, 6871810305240148585411681171406827126226895354872333377655125605167085785115478362120192, 3435905152620074292705840585703413563113447677436166688827562802583542892557739181060096, 1717952576310037146352920292851706781556723838718083344413781401291771446278869590530048, 858976288155018573176460146425853390778361919359041672206890700645885723139434795265024, 429488144077509286588230073212926695389180959679520836103445350322942861569717397632512, 214744072038754643294115036606463347694590479839760418051722675161471430784858698816256, 107372036019377321647057518303231673847295239919880209025861337580735715392429349408128, 53686018009688660823528759151615836923647619959940104512930668790367857696214674704064, 26843009004844330411764379575807918461823809979970052256465334395183928848107337352032, 13421504502422165205882189787903959230911904989985026128232667197591964424053668676016, 6710752251211082602941094893951979615455952494992513064116333598795982212026834338008, 3355376125605541301470547446975989807727976247496256532058166799397991106013417169004, 1677688062802770650735273723487994903863988123748128266029083399698995553006708584502, 838844031401385325367636861743997451931994061874064133014541699849497776503354292251]
c = 1475864207352419823225329328555476398971654057144688193866218781853021651529290611526242518

n = len(Pk)

M = []
for i in range(n):
    L = [0]*(n+1)
    L[i] = 2
    L[n] = Pk[i]
    M.append(L)
M.append([1]*n+[c])
M = matrix(M)
L = M.LLL()
print(L)
'''
print(L[-16].list())
print(L[-8].list())
print(L[-6].list())
print(L[-5].list())
'''

很遗憾，并没有完全满足的向量。将向量中的不符合地做一些微小改变，尽量拟合flag。

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
from Crypto.Util.number import *

L = [
    [-1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, -1, -3, 1, -1, -1, 3, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 0]
    ,[1, 1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, -1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, -1, -1, 1, 1, -1, 1, 1, 1, 3, -1, 1, 1, -3, 1, -1, 1, -1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, -1, -1, 1, -1, -1, -1, 1, 1, -1, 1, -1, -1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -3, -1, -1, -1, 1, -1, 0]
    ,[-1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, -1, -3, 1, -1, -1, 3, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, 1, -1, -3, 1, -1, 1, 0]
    ,[-1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, -1, -3, 1, -1, -1, 3, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, 1, -1, -1, -3, -1, 1, 0]
]

for each in L:
    m = ''
    for i in range(len(each)-1):
        if each[i] == -1:
            m += '0'
        elif each[i] == 1:
            m += '1'
        elif each[i] == -3:
            m += '0'
        elif each[i] == 3:
            m += '1'
    print(m)
    print(long_to_bytes(int(m,2)))
#5090ea29-8cb6-4ad8-ab43-1e6f65cc8eeb
#5090ea29-8cb6-4ad7=ab43-1e6f65cc8eeb（-1，+1代表的值互换）
#5090ea29-8cb6-4ad75ab43-1e6f65cc8ee\x82

出来的结果有些误差。

FourThousandRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from random import *

from secret import p, q, flag

d = (p - 1) * (randint(1 << 895, 1 << 905)) + getPrime(66)
assert GCD(d, (p - 1) * (q - 1)) == 1

e = inverse(d, (p - 1) * (q - 1))
n = p * q
m = bytes_to_long(flag)
c = pow(m, e, n)
lnK = [n, e, d, p, q]
for i in range(5):
    lnK[i] = lnK[i].bit_length()

print(n)
print(e)
print(c)
print(lnK)
# 2008245202726111195525139787077766845460301971221282725789653525445717877831247040311792229284045975453691272797897794805042646233029706866078707630143984010874126231698685294168749255436126975986003969530103617426741064270423218259588978877370113177828293456561413806780703064713982940589926704665536293631846419385505665983693074491341550629844185026851229010312732921558017787072574777346960912025366025572718687418119633550194015169661191937337614795319500510125026882103589501497847356092372022899906904311120130529291320419495706452187192436497658895872460456299020678691633147066767550340869239242665444676015223859488181778716351439391614896237952082547346751012334359281894362102507693710804521999826603241204878074796474371682930675553715217908515291214108531394832662173298837242969662633805422396059510882443282508140025449969731242643820520540750378151812795959963934842270926945543049483993393288111252859368438315000543965899671606298852910335484127077917071912504701937501178567564695543045503695648983193718396823789188986832546133398012148358369105865469590306905583050200981598525031197740358763416786658682107838491293027639364508979821571709310278056633617824675033779928720051885352835157353803
# 807032534004084758580375189157328561548795804530942985115124520531221373527096275904469284031734054835824102563821158171589235747667599272991298059693818077176669425056991292994334793629184405818520272993874070884698385334019049156576500287497429412919772544592662544872484546264801483551861046175807498926198088282017428499839509688184982602419754320550459089738363252159087637831975525246450729834548975894498204691170246637710357850579558483403451912974355124654280116319260254145067344177881377307629659609044861901831073680528402705499960011480684401009582453074445582770870258919978732068123428866624493163278443134701482587357134070124133221075748585768453464832312107505344577054027293922365686198638830956703448628155371973969488855140627118939048137913508744817167302068674632091539914140795622964012240768679911315743790231690924423221631592930482614786389990208367405878537840797769431729477448292378308254306426728498718084148271069061132613717597098762769671154028101328451549784614737777731600209296493017630537336889457808923914655393955515432343410385118818484779667586279513209712795980030600707800342547828383384392042988707358771882529896527356417371670949948690120768388723079299981807646726911
# 1479098843223597304786742970274134598770261170942980086038287429905405158086547268458308645377797729404756116803215570224420375863682276378830919895619659050799395956146572726236750711207231799570925819982063426093862796144319017426916290208631746748701116840125309109359766050752569570197143931328071928910272144487415408708111493159410784983656461473802920988821467611079772020575539261046542193167444757825649926376069763390388540651778066220417921640963803183015067230139701713552782995724061821817700770220827885999306389960050273479873187643335537248639494631153812809968161473247467770291102906672062014528600784321726886085505174266116545186131025910553430133389924415555728463048311407897414482070647200465503078473266937663980748718243201906335338839452018573040634977122916044674440902206770428978968958675742011856119772241474589012913197944864164658153691848011206012988704668234612237127302621256390964532600110123457039129898476045860122356186227473879930882612843980001579020344087043771505157047280424063737637399280369256220373591698317585713187436849457927758798371213053969011609925655180333896843921881279342761083499824073913636798612382743862755759722932438784880987705776287623448376091072071
# [4038, 4036, 3503, 2599, 1439]

论文题：https://link.springer.com/content/pdf/10.1007%2F3-540-45708-9_16.pdf

构造如下矩阵：

其中$f_p(x,y) = ex - y$。矩阵中的每一行为$g_{m,i,j}(x,y)$。

至于$n,m$的选取似乎没有很准确的说明。（可能是我没有读透）

我不理解的地方有以下几点：

  1. $x,y$的系数为什么是解。
  2. 得出的解按照论文应该是$(x_0,y_0)=(dp,k+1)$，但为什么$k$最后是+1而不是-1。

如果有清楚的师傅希望能解答我的疑惑！感谢！

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
#sage
N=2008245202726111195525139787077766845460301971221282725789653525445717877831247040311792229284045975453691272797897794805042646233029706866078707630143984010874126231698685294168749255436126975986003969530103617426741064270423218259588978877370113177828293456561413806780703064713982940589926704665536293631846419385505665983693074491341550629844185026851229010312732921558017787072574777346960912025366025572718687418119633550194015169661191937337614795319500510125026882103589501497847356092372022899906904311120130529291320419495706452187192436497658895872460456299020678691633147066767550340869239242665444676015223859488181778716351439391614896237952082547346751012334359281894362102507693710804521999826603241204878074796474371682930675553715217908515291214108531394832662173298837242969662633805422396059510882443282508140025449969731242643820520540750378151812795959963934842270926945543049483993393288111252859368438315000543965899671606298852910335484127077917071912504701937501178567564695543045503695648983193718396823789188986832546133398012148358369105865469590306905583050200981598525031197740358763416786658682107838491293027639364508979821571709310278056633617824675033779928720051885352835157353803
e=807032534004084758580375189157328561548795804530942985115124520531221373527096275904469284031734054835824102563821158171589235747667599272991298059693818077176669425056991292994334793629184405818520272993874070884698385334019049156576500287497429412919772544592662544872484546264801483551861046175807498926198088282017428499839509688184982602419754320550459089738363252159087637831975525246450729834548975894498204691170246637710357850579558483403451912974355124654280116319260254145067344177881377307629659609044861901831073680528402705499960011480684401009582453074445582770870258919978732068123428866624493163278443134701482587357134070124133221075748585768453464832312107505344577054027293922365686198638830956703448628155371973969488855140627118939048137913508744817167302068674632091539914140795622964012240768679911315743790231690924423221631592930482614786389990208367405878537840797769431729477448292378308254306426728498718084148271069061132613717597098762769671154028101328451549784614737777731600209296493017630537336889457808923914655393955515432343410385118818484779667586279513209712795980030600707800342547828383384392042988707358771882529896527356417371670949948690120768388723079299981807646726911

n=12
beta = 0.36
delta = 0.02

X = int(N ** delta*(n+1)/2)
Y = int(N ** (delta + beta)*(n+1)/2)

def C(a,b):
    ret=1
    for i in range(b):
        ret*=(a-i)
        ret/=(b-i)
    return ret
def get_Matrix(n,m):
    MM=[[0 for __ in range(n)] for _ in range(n)]
    for j in range(n): 
        pN=max(0,m-j)
        for i in range(j+1):
            MM[j][i]=pow(N,pN)*pow(X,n-i-1)*pow(Y,i)*pow(e,j-i)*C(j,i)*pow(-1,i)
    MM=Matrix(ZZ,MM)
    return MM

M=get_Matrix(n,n//2+1)
L=M.LLL()[0]

x,y = var('x'),var('y')
f=0
for i in range(n):
    f+=x**(n-i-1) * y**i * (L[i] // pow(X,n-i-1) // pow(Y,i))#将x,y参数化

print(f.factor())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import gmpy2

n = 2008245202726111195525139787077766845460301971221282725789653525445717877831247040311792229284045975453691272797897794805042646233029706866078707630143984010874126231698685294168749255436126975986003969530103617426741064270423218259588978877370113177828293456561413806780703064713982940589926704665536293631846419385505665983693074491341550629844185026851229010312732921558017787072574777346960912025366025572718687418119633550194015169661191937337614795319500510125026882103589501497847356092372022899906904311120130529291320419495706452187192436497658895872460456299020678691633147066767550340869239242665444676015223859488181778716351439391614896237952082547346751012334359281894362102507693710804521999826603241204878074796474371682930675553715217908515291214108531394832662173298837242969662633805422396059510882443282508140025449969731242643820520540750378151812795959963934842270926945543049483993393288111252859368438315000543965899671606298852910335484127077917071912504701937501178567564695543045503695648983193718396823789188986832546133398012148358369105865469590306905583050200981598525031197740358763416786658682107838491293027639364508979821571709310278056633617824675033779928720051885352835157353803
e = 807032534004084758580375189157328561548795804530942985115124520531221373527096275904469284031734054835824102563821158171589235747667599272991298059693818077176669425056991292994334793629184405818520272993874070884698385334019049156576500287497429412919772544592662544872484546264801483551861046175807498926198088282017428499839509688184982602419754320550459089738363252159087637831975525246450729834548975894498204691170246637710357850579558483403451912974355124654280116319260254145067344177881377307629659609044861901831073680528402705499960011480684401009582453074445582770870258919978732068123428866624493163278443134701482587357134070124133221075748585768453464832312107505344577054027293922365686198638830956703448628155371973969488855140627118939048137913508744817167302068674632091539914140795622964012240768679911315743790231690924423221631592930482614786389990208367405878537840797769431729477448292378308254306426728498718084148271069061132613717597098762769671154028101328451549784614737777731600209296493017630537336889457808923914655393955515432343410385118818484779667586279513209712795980030600707800342547828383384392042988707358771882529896527356417371670949948690120768388723079299981807646726911
c = 1479098843223597304786742970274134598770261170942980086038287429905405158086547268458308645377797729404756116803215570224420375863682276378830919895619659050799395956146572726236750711207231799570925819982063426093862796144319017426916290208631746748701116840125309109359766050752569570197143931328071928910272144487415408708111493159410784983656461473802920988821467611079772020575539261046542193167444757825649926376069763390388540651778066220417921640963803183015067230139701713552782995724061821817700770220827885999306389960050273479873187643335537248639494631153812809968161473247467770291102906672062014528600784321726886085505174266116545186131025910553430133389924415555728463048311407897414482070647200465503078473266937663980748718243201906335338839452018573040634977122916044674440902206770428978968958675742011856119772241474589012913197944864164658153691848011206012988704668234612237127302621256390964532600110123457039129898476045860122356186227473879930882612843980001579020344087043771505157047280424063737637399280369256220373591698317585713187436849457927758798371213053969011609925655180333896843921881279342761083499824073913636798612382743862755759722932438784880987705776287623448376091072071
lnK = [4038, 4036, 3503, 2599, 1439]

dp = 53884891560160528919
k = 302884665515803766011906438013192003712099358870001780564269089035021793994528619923490222376829646206262773174752214834261410191185822844479036873079049649442148949148666170143829689538107319496991988733386708820659360609308128307216254687970393854057754055298044301139034587343570198869912515404392889596455648319972063467359880205558544007697140900913860985852897308920005250016284550898672612541129402073944532028683909649120706671728845700276654410
k += 1

p = (e * dp - 1 ) // k + 1
q = n // p
print(p.bit_length())
print(q.bit_length())
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
#b'Dest0g3{1087fb88-a2da-4d21-d81a-40c6e1f105fa}'
Crypto
#RSA #AES #背包密码
Dest0g3 520迎新赛
http://example.com/2022/07/10/CTF/Dest0g3 520迎新赛/
作者
gla2xy
发布于
2022年7月10日
许可协议