#强国杯babyrsa

题目：

1
2
3
4
p=141755878485521250585193526506481835647909733133264484491826506533095411036871187581787386511037412174342774745629361598256663156186634190655768748475210357241858257598757038958971434010720283092093970656262829235604751943313758736375629372244903654343619477366460118493729379823214225182978297539467629343751
q=105791326767350254361775085198789512601280034667878018736203482690296402930705105880941292311523491531268219920304105707946817881385239201060719345266176935014448981721004118085446297034921832910808404583724823060617037938408978927482413705465188767091927899538738934603096246585672422519596415454996951648933
e=33
c=1406397112339697711604857959634535602308393200925612487282395712494883971454736568217895405105641804234918132815025852520686132492440369381524536605289927570796848067004330389550235386191718059158797682686883851836520235452554108372524737561747360657926629011197101279036266730814165126504183746702642346930678406881723781517084042121908048000756941192812817934470545903542277748760076963885109519709405907055218814798421840231218418875714770702389870687977272565851870471136169739851824446107960081481505725577148169000576421732034715421196693795925511463683392371022845041003197960494696500662560942126741476511550

题解：

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

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    d = invert(e // 3, phi)
    m = pow(c, d, n)
    while 1:
        msg = iroot(m, 3)
        if msg[1]==True:
            print(long_to_bytes(msg[0]))
            break
        m += n

p=115527813793076185316851381449805634312168762458657191403286815066526250953188706928583056798579604342852966744015346317325822694054887219898915721915782637754329465514052854924553817535032759938725270570934210214428213523012934841467181935253769089655932739804044118941188314706468747928929674022797932677491
q=166400672883439986828248067692123363689048001045100362967157232932898845079847645677561248632693179197251519134531321011154377754163164855606639412545072704732134708868296084256496193743609181923015517115351345445824153230019197616579730076056575061573322756305055859636790371958064604509869192577321790513607
e=33
c=2115560894194923855739630759560263432863369647495989278797186061331927960652175182534536593259714647189428014744205682895048988970744494185844850545176656896750073471540369186693731841022954707114460986390619090986241777895532597176340296883545005058917849321578371609829147178589075514145416374661047508694566576157432639591003296975055455249269260800329069263661498941662392614602189878893057734163983485998267416879197126412977444307775211162627226211229437593330963712320994664878058875181731837287047039480049127389471576406574432640255100250675953098648028434804235316276464230311654580987077193891045891045379
decrypt(p, q, e, c)

国赛 LCG

题目代码

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 *

flag = getRandomNBitInteger(32)

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

    def next(self):
        self.seed = (self.a * self.seed * self.seed + self.b * self.seed + self.c) % self.n
        return self.seed 

    def output(self):
        print("b = {}\nn = {}".format(self.b, self.n))
        print("seed = {}".format(self.seed))
        print("s1 = {}".format(self.next()))
        print("s2 = {}".format(self.next()))

lcg = LCG()
lcg.output()
c1 = ((flag * lcg.a + lcg.c) % lcg.n) >> 16
c2 = ((c1 * lcg.a + lcg.c) % lcg.n) >> 16
print("c1 = {}".format(c1))
print("c2 = {}".format(c2))
print("flag = {}".format(flag))
'''
b = 3831416627
n = 2273386207
seed = 2403188683
s1 = 260742417
s2 = 447908860
c1 = 17275
c2 = 28951
'''

解题思路

看已知条件就知道要求出c和a

求a：联立方程，设a为x，因为x × seed^2^ + b × seed - s1 = -c 1

​ 又因为x*seed^2^ + b × seed -s2= - c 2

所以一式减去二式

利用corrppermith攻击

求出根，根就是a

再利用a和s1求出c ,设c为x；所以a × seed^2^ +b ×seed +c - s1 == 0

所以解出c

解题代码：

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
from sage.all import *
from Crypto.Util.number import long_to_bytes
from hashlib import md5
from binascii import hexlify

b = 3831416627
n = 2273386207
seed = 2403188683
s1 = 260742417
s2 = 447908860
c1 = 17275
c2 = 28951

N = Zmod(n)
x = polygen(N)
f = x * seed**2 + b * seed - s1 - (x*s1**2+b*s1-s2)
a = f.roots()[0][0]
print("a =",f.roots()[0][0])
x = a
assert (x * seed**2 + b * seed - s1 - (x*s1**2+b*s1-s2))%n == 0

x = polygen(N)
f = a * seed**2 + b*seed + x - s1
c = f.roots()[0][0]
print("c =", c)
x = c
assert (a * seed**2 + b*seed + x - s1)%n == 0

c0 = []
for i in range(2**16):
        if (( (c1*(2**16) + i) * a + c )%n) >> 16 == c2:
                c0.append((c1*2**16+i))


flag = []
for cc0 in c0:
        x = polygen(N)
        f = x * a + c - cc0
        flag.append(int(f.roots()[0][0]))

for fs in flag:
        for i in range(1000):
                if (fs+n*i)>=2**32:
                        break
                print("flag{%s}"%md5(str(fs+n*i).encode()).hexdigest())

[BJDCTF2020]伏羲六十四卦

这是什么，怎么看起来像是再算64卦！！！

密文:升随临损巽睽颐萃小过讼艮颐小过震蛊屯未济中孚艮困恒晋升损蛊萃蛊未济巽解艮贲未济观豫损蛊晋噬嗑晋旅解大畜困未济随蒙升解睽未济井困未济旅萃未济震蒙未济师涣归妹大有

嗯？为什么还有个b呢?
b=7

flag：请按照格式BJD{}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -- coding:UTF-8 --
from secret import flag

def encrpyt5():
    enc=''
    for i in flag:
        enc+=chr((a*(ord(i)-97)+b)%26+97)
    return(enc)

def encrypt4():
    temp=''
    offset=5
    for i in range(len(enc)):
        temp+=chr(ord(enc[i])-offset-i)
    return(temp)

解题思路：

先是看见题目给的提示64卦，在网上找到64卦和二进制的关系；

得到的密文再根据给出的加密脚本逆回去；

下面是解题代码：

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
s='升随临损巽睽颐萃小过讼艮颐小过震蛊屯未济中孚艮困恒晋升损蛊萃蛊未济巽解艮贲未济观豫损蛊晋噬嗑晋旅解大畜困未济随蒙升解睽未济井困未济旅萃未济震蒙未济师涣归妹大有'
dic={'坤': '000000', '剥': '000001', '比': '000010', '观': '000011', '豫': '000100', '晋': '000101', '萃': '000110', '否': '000111', '谦': '001000', '艮': '001001', '蹇': '001010', '渐': '001011', '小过': '001100', '旅': '001101', '咸': '001110', '遁': '001111', '师': '010000', '蒙': '010001', '坎': '010010', '涣': '010011', '解': '010100', '未济': '010101', '困': '010110', '讼': '010111', '升': '011000', '蛊': '011001', '井': '011010', '巽': '011011', '恒': '011100', '鼎': '011101', '大过': '011110', '姤': '011111', '复': '100000', '颐': '100001', '屯': '100010', '益': '100011', '震': '100100', '噬嗑': '100101', '随': '100110', '无妄': '100111', '明夷': '101000', '贲': '101001', '既济': '101010', '家人': '101011', '丰': '101100', '离': '101101', '革': '101110', '同人': '101111', '临': '110000', '损': '110001', '节': '110010', '中孚': '110011', '归妹': '110100', '睽': '110101', '兑': '110110', '履': '110111', '泰': '111000', '大畜': '111001', '需': '111010', '小畜': '111011', '大壮': '111100', '大有': '111101', '夬': '111110', '乾': '111111'}
li=[]
i=0
k=0
for i in range (len(s)):
    if k==1:               '''这里解释一下，如果是两个字符的，然后k=1，又因为下一次循坏的时候要加二所以就写这串代码让它                               再次循环一次,实现了加一；
                           '''
        k=0
        continue
    try:
        li.append(dic[s[i]])
    except:
        t=""
        t=t+s[i]+s[i+1]
        li.append(dic[t])
        k=1
print(li)
enc="".join(li)
print(enc)
c=""
for i in range(0,len(enc),8):
    c+=chr(eval("0b"+enc[i:i+8]))
print(c)
from base64 import*
cipher=b64decode(c).decode()
print(cipher)
def decrypt4(enc):
    temp=''
    offset=5
    for i in range(len(enc)):
        temp+=chr(ord(enc[i])+offset+i)
    return(temp)
def decrpyt5(flag):
    for a in range(1,200):
        enc=""
        for i in flag:
          for k in range(200):
            if (ord(i)-97-7+k*26)%a==0:
                enc+=chr((ord(i)-97-7+k*26)//a+97)
                break

        print(enc)



a=decrypt4(cipher)
decrpyt5(a)

#鹤城杯2021，babyrsa

题目：

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 getPrime, bytes_to_long
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)
已知条件：
p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
enc = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537

解题思路：

已知p的高位300位，q的低位256位，因为q % (2^265^) = hint1；q = k× 2^265^ +hint 1

qlow= hint1 =q mod 2^265^

qhigh=k × 2^265^

n = p (qlow + qhigh) =p × k × 2^265^ + p × q mod 2^265^*

两边同时取余2^265^

得到： plow= nlow × q^-1^ mod 2^265^

这样我们就得到了p的低位265位，有已知高位300位，所以未知位数459位，还差5位就可以用coppermith攻击，所以进行爆破

以下是解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
enc = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537
mod=pow(2,265)
p0=30417487794073877577997977068358253483488121930635899911316665665825597484019031
PR.<x>=PolynomialRing(Zmod(n))
for i in range(2**5):
    f = p_high * 2^724+p0+i * mod+x * 2^5 * mod
    f=f.monic()
    out_p=f.small_roots(2^454,0.4)
    if len(out_p) != 0:
        print(out_p[0])
        break
p=p_high * 2^724+p0+i * mod+out_p[0] * 2^5*mod
print(p)
q = n // p
fai_n = (p-1) * (q-1)
d = inverse_mod(e,fai_n)
m = pow(enc,d,n)
print(bytes.decode(long_to_bytes(m)))
flag{ef5e1582-8116-4f61-b458-f793dc03f2ff}

PolyRSA

题目：

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
#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def keygen(nbit = 64):
	while True:
		k = getRandomNBitInteger(nbit)
		p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
		q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
		if isPrime(p) and isPrime(q):
			return p, q

def encrypt(msg, n, e = 31337):
	m = bytes_to_long(msg)
	return pow(m, e, n)

p, q = keygen()
n = p * q
enc = encrypt(flag, n)
print(f'n = {n}')
print(f'enc = {enc}')
'''
n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
'''

解题只有一个思路就是求出k

下面是sagemath代码：

1
2
3
4
5
6
7
8
9
n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
PR.<k>=PolynomialRing(QQ)
p=k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q=k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
f=p*q-n
f=f.monic()
out_k=f.roots()
print(out_k[0])

然后是python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python3

from Crypto.Util.number import *
n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
k=9291098683758154336
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
e=31337
from gmpy2 import *
d=invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(enc,d,n)))
#CCTF{F4C70r!N9_tRIcK5_aR3_fUN_iN_RSA?!!!}

补充另一种方法解出k

利用sympy模块联立方程可以解出

下面是解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
from Crypto.Util.number import *
from sympy.abc import a
from sympy import solve
n  = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532

p = a**6 + 7*a**4 - 40*a**3 + 12*a**2 - 114*a + 31377
q = a**5 - 8*a**4 + 19*a**3 - 313*a**2 - 14*a + 14011
eq=p*q

k=solve([eq-n],[a])
print(k)
a=9291098683758154336
p = a**6 + 7*a**4 - 40*a**3 + 12*a**2 - 114*a + 31377
q = a**5 - 8*a**4 + 19*a**3 - 313*a**2 - 14*a + 14011


phi=(p-1)*(q-1)
d=gmpy2.invert(31337,phi)
m=pow(enc,d,n)
print(long_to_bytes(int(m)))

#[UTCTF2020]hill

##希尔算法

利用矩阵的原理去加密

算法原理：

一个n*n矩阵(加密矩阵) A
一个英文字符串s
记 a=0,b=1,c=2…z=25

  1. 先将s转成数字表示形式.

  2. 分组,比如s得到的序列为 x1,x2,x3,x4,x5,x6 n=2,那么要分成每列两个元素的矩阵即:
    x1 x3 x5
    x2 x4 x6
    加密过程: 记上述的矩阵为M,得到的密文矩阵为C,则转化过程为:
    (AM)%26=C(注意是M左乘一个A)
    解密过程:
    M=(A^-1^ C)%26
    一般做题过程中n不会太高.

    以下是题目：

    wznqca{d4uqop0fk_q1nwofDbzg_eu}

    猜测前面六位为utflag；假设n=2

    则加密矩阵为2*2矩阵；求明文我们必须知道加密矩阵，加密矩阵的逆矩阵乘上密文即可求出明文：

    求出2*2加密矩阵

    上代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    s='wznqcaduqopfkqnwofDbzgeu'
    flag_pre='utflag'
    def getit(a1,b1,c1,a2,b2,c2,a3,b3,c3):
        for i in range(26):
            for j in range(26):
                if (a1 * i + b1 * j) % 26 == c1 and (a2 * i + b2 * j) % 26 == c2 and (a3 * i+b3*j) % 26 == c3:
                    return (i,j)
    x1=getit(22,25,20,13,16,5,2,0,0)              ##要自己尝试写在本子上，举例更加好证明；
    x2=getit(22,25,19,13,16,11,2,0,6)
    import string
    flag=''
    for i in range(0, len(s),2):
        flag+=string.ascii_letters[(x1[0]*string.ascii_letters.index(s[i])+x1[1]*string.ascii_letters.index(s[i+1]))%26]
        flag+=string.ascii_letters[(x2[0]*string.ascii_letters.index(s[i])+x2[1]*string.ascii_letters.index(s[i+1]))%26]
    print(flag)

巅峰极客

point power

题目内容：

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

assert len(flag)==42
p=getPrime(600)
a=bytes_to_long(flag)
b=randrange(2,p-1)
E=EllipticCurve(GF(p),[a,b])
G=E.random_element()

x1,y1,_=G
G=2*G
x2,y2,_=G

print(f"p = {p}")
print(f"b = {b}")
print(f"x1 = {x1}")
print(f"x2 = {x2}")
'''
p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
'''

根据椭圆曲线的公式和定义：

题解

因为：根据公式和定义 y1^2^ = x1^3^ +ax1 + b

​ x2 = k^2^ - 2x1

​ y2 = k (x1-x2) - y1

所以联立方程：

4× k^2^ × y1 ^2^ = (3x1^2^ +a)^2^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
PR.<a> = Zmod(p)[]
kk = x2+2*x1
yy1 = x1^3+a*x1+b
yy2 = x2^3+a*x2+b
f = 4*kk*yy1-(3*x1*x1+a)^2
res = f.roots()
for i in res:
 if b'flag' in long_to_bytes(int(i[0])):
 print(long_to_bytes(int(i[0])))
# b'flag{fa76cfb1-0052-4416-914d-91517bcebd52}'

[2022鹏城杯] easy_rsa

题目描述:

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

m1 = flag[0:12]
m2 = flag[12:24]
m3 = flag[24:]

def encrypt1(m):
    while 1:
        e = random.randint(100, 1000)
        p = getPrime(1024)
        q = getPrime(1024)
        phi_n = (p - 1) * (q - 1)
        t = gmpy2.gcd(e, phi_n)
        if gmpy2.invert(e // t, phi_n) and t != 1:
            break
    n = p * q
    c = pow(m, e, n)
    print({'c': format(c, 'x'), 'p': format(p, 'x'), 'q': format(q, 'x'), 'e': format(e, 'x')})


def encrypt2(m):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 65537
    c = gmpy2.powmod(m, e, n)
    print({'c': format(c, 'x'), 'p': format((p >> 60) << 60, 'x'), 'e': format(e, 'x'), 'n': format(n, 'x')})


def encrypt3(m):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 65537
    M = 2022 * m * 1011 * p
    c = pow(M, e, n)
    print({'c': format(c, 'x'), 'n': format(n, 'x'),'e':format(e, 'x')})


if __name__ == '__main__':
    encrypt1(bytes_to_long(m1))
    encrypt2(bytes_to_long(m2))
    encrypt3(bytes_to_long(m3))

# {'c': '27455f081e4858790c6503580dad3302ae359c9fb46dc601eee98f05142128404e95377324720adbbdebf428549008bcd1b670f6749592a171b30316ab707004b9999f3b80de32843afdfd30505b1f4166a03cee9fc48902b74b6e850cfd268e6917c5d84e64f7e7cd0e4a30bfe5903fb5d821d27fdc817d9c4536a8e7aea55af266abcae857a8ffff2f741901baba1b44091a137c69c471c123ab0b80e250e055959c468e6e37c005105ecd7c8b48c659024e5e251df3eeff5da7b3d561cd98150da3575a16bee5f2524d2795fd4879487018345c1e96efc085ed45fb5f02c027aee5bca3aad0eb3e23376c0cd18b02fb05a1ff8fb1af0a3ce4bb671599894e', 'p': 'bb602e402b68a5cfcc5cfcc63cc82e362e98cb7043817e3421599a4bb8755777c362813742852dad4fec7ec33f1faec04926f0c253f56ab4c4dde6d71627fbc9ef42425b70e5ecd55314e744aa66653103b7d1ba86d1e0e21920a0bfe7d598bd09c3c377a3268928b953005450857c6cfea5bfdd7c16305baed0f0a31ad688bd', 'q': 'bb8d1ea24a3462ae6ec28e79f96a95770d726144afc95ffffa19c7c3a3786a6acc3309820ba7b1a28a4f111082e69e558b27405613e115139b38e799c723ab7fdd7be14b330b118ae60e3b44483a4c94a556e810ab94bbb102286d0100d7c20e7494e20e0c1030e016603bd2a06c1f6e92998ab68e2d420faf47f3ee687fb6d1', 'e': '292'}
# {'c': '3a80caebcee814e74a9d3d81b08b1130bed6edde2c0161799e1116ab837424fbc1a234b9765edfc47a9d634e1868105d4458c9b9a0d399b870adbaa2337ac62940ade08daa8a7492cdedf854d4d3a05705db3651211a1ec623a10bd60596e891ccc7b9364fbf2e306404aa2392f5598694dec0b8f7efc66e94e3f8a6f372d833941a2235ebf2fc77c163abcac274836380045b63cc9904d9b13c0935040eda6462b99dd01e8230fdfe2871124306e7bca5b356d16796351db37ec4e574137c926a4e07a2bfe76b9cbbfa4b5b010d678804df3e2f23b4ec42b8c8433fa4811bf1dc231855bea4225683529fad54a9b539fe824931b4fdafab67034e57338217f', 'p': 'a9cb9e2eb43f17ad6734356db18ad744600d0c19449fc62b25db7291f24c480217d60a7f87252d890b97a38cc6943740ac344233446eea4084c1ba7ea5b7cf2399d42650b2a3f0302bab81295abfd7cacf248de62d3c63482c5ea8ab6b25cdbebc83eae855c1d07a8cf0408c2b721e43c4ac53262bf9aaf7a000000000000000', 'e': '10001', 'n': '841a5a012c104e600eca17b451d5fd37c063ad347707a2e88f36a07e9ad4687302790466e99f35b11580cbe8b0a212e6709686c464a6393c5895b1f97885f23ea12d2069eb6dc3cb4199fb8c6e80a4a94561c6c3499c3c02d9dc9cf216c0f44dc91701a6d9ec89981f261a139500420a51014492f1da588a26e761439dd5739b32540ca6dc1ec3b035043bc535304a06ccb489f72fcd1aa856e1cffe195039176937f9a16bd19030d1e00095f1fd977cf4f23e47b55650ca4712d1eb089d92df032e5180d05311c938a44decc6070cd01af4c6144cdab2526e5cb919a1828bec6a4f3332bf1fa4f1c9d3516fbb158fd4fbcf8b0e67eff944efa97f5b24f9aa65'}
# {'c': '1bd2a47a5d275ba6356e1e2bd10d6c870693be540e9318c746e807a7672f3a75cc63841170126d7dba52d7f6f9cf0f8dce9705fc1785cc670b2658b05d4b24d8918f95594844bfa920c8ffe73160c2c313b3fdbc4541ec19828165e34afa7d05271cc6fd59d08138b88c11677e6ac3b39cff525dcb19694b0388d895f53805a5e5bd8cfb947080e4855aaf83ebd85a397526f7d76d26031386900cb44a2e4bd121412bcee7a6c1e9af411e234f130e68a428596265d3ec647e50f65cb81393f4bd38389a2b9010fd715582506b9054dc235aced50757462b77a5606f116853af0c1ea3c7cf0d304f885d86081f8bac8b67b0625122f75448c5b6eb8f1cc8a0df', 'n': 'c2b17c86a8950f6dafe0a633890e4271cfb20c5ffda2d6b3d035afa655ed05ec16c67b18832ed887f2cea83056af079cc75c2ce43c90cce3ed02c2e07d256f240344f1734adeee6dc2b3b4bbf6dcfc68518d0a74e3e66f1865db95ef4204457e6471903c2321ac97f3b8e3d8d935896e9fc9145a30a3e24e7c320490a9944c1e94d301c8388445532699e6189f4aa6a86f67f1d9b8fb0de4225e005bd27594cd33e36622b2cd8eb2781f0c24d33267d9f29309158942b681aab81f39d1b4a73bd17431b46a89a0e4c2c58b1e24e850355c63b72392600d3fff7a16f6ef80ea515709da3ef1d28782882b0dd2f76bf609590db31979c5d1fd03f75d9d8f1c5069', 'e': '10001'}

第一个涉及模不互素的问题；

第二个涉及coppermith已知p的高位攻击；

第三个就是求公约数的问题啦；

所以解题代码如下：

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
from gmpy2 import *
from Crypto.Util.number import *
c1=0x27455f081e4858790c6503580dad3302ae359c9fb46dc601eee98f05142128404e95377324720adbbdebf428549008bcd1b670f6749592a171b30316ab707004b9999f3b80de32843afdfd30505b1f4166a03cee9fc48902b74b6e850cfd268e6917c5d84e64f7e7cd0e4a30bfe5903fb5d821d27fdc817d9c4536a8e7aea55af266abcae857a8ffff2f741901baba1b44091a137c69c471c123ab0b80e250e055959c468e6e37c005105ecd7c8b48c659024e5e251df3eeff5da7b3d561cd98150da3575a16bee5f2524d2795fd4879487018345c1e96efc085ed45fb5f02c027aee5bca3aad0eb3e23376c0cd18b02fb05a1ff8fb1af0a3ce4bb671599894e
p1=0xbb602e402b68a5cfcc5cfcc63cc82e362e98cb7043817e3421599a4bb8755777c362813742852dad4fec7ec33f1faec04926f0c253f56ab4c4dde6d71627fbc9ef42425b70e5ecd55314e744aa66653103b7d1ba86d1e0e21920a0bfe7d598bd09c3c377a3268928b953005450857c6cfea5bfdd7c16305baed0f0a31ad688bd
q1=0xbb8d1ea24a3462ae6ec28e79f96a95770d726144afc95ffffa19c7c3a3786a6acc3309820ba7b1a28a4f111082e69e558b27405613e115139b38e799c723ab7fdd7be14b330b118ae60e3b44483a4c94a556e810ab94bbb102286d0100d7c20e7494e20e0c1030e016603bd2a06c1f6e92998ab68e2d420faf47f3ee687fb6d1
e=0x292
n=p1*q1
x=gcd(e,(q1-1)*(p1-1))
print(x)
d=invert(e//x,(q1-1)*(p1-1))
print(iroot(pow(c1,d,n),2))
m1=24840159987970087265973252962
c2=0x3a80caebcee814e74a9d3d81b08b1130bed6edde2c0161799e1116ab837424fbc1a234b9765edfc47a9d634e1868105d4458c9b9a0d399b870adbaa2337ac62940ade08daa8a7492cdedf854d4d3a05705db3651211a1ec623a10bd60596e891ccc7b9364fbf2e306404aa2392f5598694dec0b8f7efc66e94e3f8a6f372d833941a2235ebf2fc77c163abcac274836380045b63cc9904d9b13c0935040eda6462b99dd01e8230fdfe2871124306e7bca5b356d16796351db37ec4e574137c926a4e07a2bfe76b9cbbfa4b5b010d678804df3e2f23b4ec42b8c8433fa4811bf1dc231855bea4225683529fad54a9b539fe824931b4fdafab67034e57338217f
p2=119234372387564173916926418564504307771905987823894721284221707768770334474240277144999791051191061404002537779694672314673997030282474914206610847346023297970473719280866108677835517943804329212840618914863288766846702119011361533150365876285203805100986025166317939702179911918098037294325448226481818486521
e2=0x10001
n2=0x841a5a012c104e600eca17b451d5fd37c063ad347707a2e88f36a07e9ad4687302790466e99f35b11580cbe8b0a212e6709686c464a6393c5895b1f97885f23ea12d2069eb6dc3cb4199fb8c6e80a4a94561c6c3499c3c02d9dc9cf216c0f44dc91701a6d9ec89981f261a139500420a51014492f1da588a26e761439dd5739b32540ca6dc1ec3b035043bc535304a06ccb489f72fcd1aa856e1cffe195039176937f9a16bd19030d1e00095f1fd977cf4f23e47b55650ca4712d1eb089d92df032e5180d05311c938a44decc6070cd01af4c6144cdab2526e5cb919a1828bec6a4f3332bf1fa4f1c9d3516fbb158fd4fbcf8b0e67eff944efa97f5b24f9aa65
q2=n2//p2
d2=invert(e2,(p2-1)*(q2-1))
print(pow(c2,d2,n2))
m2=14975196468082942664896885862
print(int("c2b17c86a8950f6dafe0a633890e4271cfb20c5ffda2d6b3d035afa655ed05ec16c67b18832ed887f2cea83056af079cc75c2ce43c90cce3ed02c2e07d256f240344f1734adeee6dc2b3b4bbf6dcfc68518d0a74e3e66f1865db95ef4204457e6471903c2321ac97f3b8e3d8d935896e9fc9145a30a3e24e7c320490a9944c1e94d301c8388445532699e6189f4aa6a86f67f1d9b8fb0de4225e005bd27594cd33e36622b2cd8eb2781f0c24d33267d9f29309158942b681aab81f39d1b4a73bd17431b46a89a0e4c2c58b1e24e850355c63b72392600d3fff7a16f6ef80ea515709da3ef1d28782882b0dd2f76bf609590db31979c5d1fd03f75d9d8f1c5069",16))
c=0x1bd2a47a5d275ba6356e1e2bd10d6c870693be540e9318c746e807a7672f3a75cc63841170126d7dba52d7f6f9cf0f8dce9705fc1785cc670b2658b05d4b24d8918f95594844bfa920c8ffe73160c2c313b3fdbc4541ec19828165e34afa7d05271cc6fd59d08138b88c11677e6ac3b39cff525dcb19694b0388d895f53805a5e5bd8cfb947080e4855aaf83ebd85a397526f7d76d26031386900cb44a2e4bd121412bcee7a6c1e9af411e234f130e68a428596265d3ec647e50f65cb81393f4bd38389a2b9010fd715582506b9054dc235aced50757462b77a5606f116853af0c1ea3c7cf0d304f885d86081f8bac8b67b0625122f75448c5b6eb8f1cc8a0df
n=0xc2b17c86a8950f6dafe0a633890e4271cfb20c5ffda2d6b3d035afa655ed05ec16c67b18832ed887f2cea83056af079cc75c2ce43c90cce3ed02c2e07d256f240344f1734adeee6dc2b3b4bbf6dcfc68518d0a74e3e66f1865db95ef4204457e6471903c2321ac97f3b8e3d8d935896e9fc9145a30a3e24e7c320490a9944c1e94d301c8388445532699e6189f4aa6a86f67f1d9b8fb0de4225e005bd27594cd33e36622b2cd8eb2781f0c24d33267d9f29309158942b681aab81f39d1b4a73bd17431b46a89a0e4c2c58b1e24e850355c63b72392600d3fff7a16f6ef80ea515709da3ef1d28782882b0dd2f76bf609590db31979c5d1fd03f75d9d8f1c5069
e=0x10001
p=gcd(c,n)
q=n//p
d=invert(e,(p-1)*(q-1))
M=pow(c,d,n)
m=M//2022//1011//p
print(m)
m3=4533093666891254524352997242237
print((long_to_bytes(m1))+(long_to_bytes(m2))+(long_to_bytes(m3)))
#PCL{16745c3b0c134c83b74f977260aae9b5}

AES&RSA

题目：

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
#!/usr/bin/python
#coding:utf-8

import gmpy2
import random
from flag import flag
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from Crypto.Cipher import AES
from os import urandom

def getkey():
    p = getPrime(2048)
    k = random.randint(3, 10)
    r = random.randint(k, 2048)
    while True:
        e = random.randint(3, p**k*(p-1))
        if gmpy2.gcd(e, p**r*(p-1)) == 1:
        	break
    pubkey = (long(e), long(p**k))
    return pubkey

def c1pto(m, pubkey):
    e, n = pubkey
    print(hex(e))
    assert m < n - 1
    c = pow(m, e, n)
    print(hex(c))
    return n

def c2pto(p):
    key = urandom(16)
    iv = urandom(16)
    cipher = AES.new(key,AES.MODE_CBC,iv)
    m = iv + long_to_bytes(p)
    print(cipher.encrypt(m).encode("base64"))
    return key


m=bytes_to_long(urandom(64)+flag)
pubkey = getkey()
n = c1pto(m, pubkey)
key=c2pto(n)
print(bytes_to_long(key))


'''output
0x5b0cd450a7bfb679dc9caa8aa6fc131708fca2a34375d049ac035fb019463d9c3fa11adb0eb51dea1ae85223df59f887a12ab376cbcb272681c3872c57f4da27396052242b608e3ea4ff53061e63bbfdff652ce25f4ce73315fd1a73a5d5e7307402c7a3c6c1a80c63297b441125c38e23729da6473e5dc332e4e7201df25ff6c8b9918b262e56a31bebe13e093e6f4dba47a771961358cedf6d740732425cb708a633d538dcdc12ef7b49ce76aa270f50dd7cc1b879f1d7b19c6ac3b891fe4e20fb7645b7567237775881de7d30ba754d495ffe8ee751d1cfee1c661a2dbf13a53ff1bcf8085b39f6508fbf37137ebad659665fe5fcc67eef02970a44ac675e28103bd10f2045983d5adaa909b18b70a909b08b76c21b2798830276068d0ebd27303985bb5f3e681219a50bc761b7630587743768cf61922804d195e265aaaabb4740a2c5d7e8ff4e1c19cfb534d345f537e95e948591557f3136da617657e24d1904be373f5e7d63af330b837bcc662cbcd801eb436dbbeb714469d227e9f17e118db39eeb42e45455e6daf4d8fe0e19c4457b596c20e1ef8d235b230018a58e1c66c52c7317094aa5797f50a3b5ebe2be2abd1a04d907fbb68919956d7b0939ac0195a3f3bd3eb6f08eef67a895807768250172ec6bb2b35c9962de03df847170472b73981c04f2aef03721554c818ec9eb7f625d1a3fcdcf756adc4b6fd61950724ac2164a94df70f4aa1cc36c51dd2c3b6545c6c2233544254f6a24e6a170918fd0c533734ef859fed3c5d6f1f9acf8d3b77804c98fa5f1429763ebe860a77380a1e94626b46d88e5263855a0a0d226eb7ca64824c9a06acda851e650e6b035c04e27de61cd49ff49ac3ea3407440f9e76ce47c02301c1bc9c28befe0cd1f5b999961b055ffb39e2f451302aaedc5d779da03830bda1ed3ba9be4f23b2381096f3dc60c84a91ba0aa44242cc6aa361e2ecac867a2d1ef6868199ecb3004aa62bd56683c3476a9bd3f0316905e4f83ef5a907d9796231b9f506c82c09c739513a0db04467a071dcc34cb11bbba8cd3f1870174e04160ae74c2160a61a7c472e8edc51e969a2f0fb47cee59b67d401ecb13b06f72dcfb24f5850b8921b8bad14f7c6bd123c13b3a2ea1761fc425066ba107d61e96d2fa9b3ed88befec93578495ef4c7a1eb95d76679d1f5261f0202e1de881c5c5b1fb44f471a75a305d86df1123cd83c8bc9449c73cf34dbd247111c873bc1fc7948863bb59f2ac3d7129c2e7c3e0ef94afb38a01b3e42f83f42a5cc8e14cbe53c0c8d76768cdc98bef921aaca60204519b516d4c9de7cf581eec8a53faa2e2d96722d0ef2c23d5567ba48104890534cd84432565236cb3402504e0feb6c25426c52d2b2b42f10a007cdd38b540cf64a96ee784deb2b595deb4a9497f9a25ab06eab443010b66e7decc162dcbd7de12737d72a46ec0b8151e1ed42716af2c7602692d7c0ea757bc056c89d2640773a4c3c1a2297c87c13676e414003ff3af0d1abb87ba618e24a4dfe05c0b4443bda53d26c7e30f0dec498d9091074fe3444e81b9a4d8d7acc8b1e38f6afc63540a4e8880fd73bd34bc3563cc0a98bd35ce7455d5cf8a114bc2fe2fb9a58e725cc121e4e242fc0a9a8e38615bda67fd9f158e718154eb51d0ec3d941426933e36fba1db0d7b59d52be90aa796895e6a49fed0a7887b8d7c71a9aa023a8dc73391e3d1bfc746cde9f964d99625900624a8eb300f2d7d2f8703f470776088f27aaa72e7607dcd78cf63754cec00db23bb36beb48cffb20a06df884f101a9L
0x26c6b16ed40253ff31bdcd502d63230a9655f29599cfb41a29f10e700589e6a13a8c78f483e0aa8b9353fa258a1437ba15e8d2c8bb2b090a6887740b31d71550745611fabd087904f150b4d928d155a7fcdd1a64c7349ce984dfd08c4c795e93b409f53c1458e6de777dc5993198f4c0648381116fe5cbafa57499d9ce685c625df4797afc344e8fe4a0fc36cf82ba1423c8a4ad7a33bc4cbab25e2df729085f96d3d9d542d981fa46cac8a37ceb70b9f808213845c06b72be7e2d1224e4dc02817bd474c690e43f6d8f1916a20f2e078bfaa604343d695e6f5f88d9f11c43a886ff97d9bd26b0126af40bed8e03a43bf8c912b5b0dd2f9f2e7e99db066759f573cd59a40a554bebdd3e7e0adbc38fcb91adeb72f9dcd30558b082471a02fd9131a61cf29b1f4e38a5d689d8dcd0b8dc29075e3a33b2d6a25bee6ff9e20d269cc088a2b155be76a1531ce30b25edf928990b5143fc5ae2737d8d4070d0517f5137c458d7afed8f51e2c2973dd143235c9deaffe9ce8fbcd767a93573399dafd5ef61408c77302c993354a080684cdbfb7c1eeb6e6be907db790038c7ce62517815d16fe366bd26178f2f05b9e56450814f4ba7ab6cab54c5f78316b0451057785c03a77c20814eb405cd20e5bff5247a12500dd16173125ffdef4fb6317ab942d0d7e0e584a8fd97a8ba8d87fd38127d6d059902a2d48dafd10938ea5d108f3eb986aabf9e212151b0e540bb5fd25888143633be9982395d4d3bef5278be37328e0239569eb511698ef7f9e7e12aa204cb4c069ffcdeecb65f42ba37f7bfd47c4ba8df384a88adf3486b58cc1620185ac81dfb10f591fc82f3ae046341ebd1e8288f10500d6677e91b89729dfd299b74be13a9183725aacb0023f4fb01efda61390b0312d90ff6a9a319433681ad1811efe038fcdeb6dc1c3f594c4f8011aacfee74ea9638fccb3d669435a1208578c934277caa3ec74f9efbb33e024909b121e7b4e48ec94b762fa9dcab8a1c11b86bb9db164c7655504d304661e04e95b0b356f5968334596fb11df95bbdcb3a6618f431c864658827662f760fc86b2136221bd50472dc19c4f177eb5edf7978760dc15150cfda0a3ea649cb672b8f37229298c6edcc630e3ac9a5f43f58a93ba8def335472f7ebdedd7715a27c4ea622344a949bec59af030455ed61911d53388022bd502e800b769ef499f94f02c96f486b40ce68dbdc42e5690ac2992bedf7f0ba384504c32cb00a25d4e125483003152e81ebe9c12d928627d7f14fc3fbdf5141addc477d5ae4f32e64dcb58a6e2cf955ad7ae54e1665b3199bd0fae36b9ec56c09ac00efc9d27e69a93f4e08652edc3340fa2c518d388ee4a005b9c83956b9139b98380f6925a1a4c3e64ff8d96f2827d0d8a25cc72a2c03a28e33871284b46e10c85f2ad75969b1d84e9d88bb4e05dL
GuGfliJiRkNsUbbmB+g/q4U3z6YahJ6G1Q9bg6ZT/ilJnkNMICmQYMFuhlNBuVZHfJJIFwwFJ5FK
G+z9zSXalJq6quN6d3CSYSMHvYk04Orpn76Y2VQX5qQk72uCssd4x5KNIOmX0CvzJmjTWjLvL1U5
twQupfkuDr/axqyHFss3pJkj9o0IRZmtz87bi5WojeUjOaayQ0RNenJJzhJ+zFJwdUCpUhwotHxL
OPsUXYSoY7AKPwj53Dlsy0deNBKFN89BolC4pTwHWvn0M/8eu9kIze+5sQuKrk0VI5ASNzA6PRp1
owpgsxNuy18k6/y01+mVheQkFrH2IrFNgqe3+Gu/PXEDPi3G2nAIi/4Xf9QI0DNH+hkoN40zWaX3
OkEVQeLQ9o/KuggeoajYwDusFyQxOQZYFr5I+v8uBApcQz29bKIRiZX78r9YN3IaSsL0JgLPQPYa
NPNiZMm5pqmv/zV0poZikYGYJsAwfjLJ/CYQ/iLBhkhKZoE9VxYEae7Wga1jwpJb3h/lA3mbvQof
MTR6ivnSZHzUu3elxMFTgTi5adB4PsBdke0YRXlWP8/AoggBAN5OMw8n2LCASIhp7q/1iljNUuw/
40mBCt75jszo1eBBDAbP7/DjXL5hUHFgen6xjedcySq/H0ibyNGasyePs3e+igr78fHyvXyIYYPa
EtM4RjC3j3TXheRYRo9lObJgHUHSY0PgAgrqc1rECexNa+QCvzzapemNAEE9OT8YLOEkB6zzpSrZ
6k/NR9KffGnqplQlWAfXdDrf3SsOmWVJ3G6DvmpTCukQgVYn+DCv5LdSSUZo2hjxBHPv8C5zpZia
sPLDr+2CwUvccettO3wwrWQ1bPfRBZ7OSghvipbYI7awjt45tyxT5TopN7e3kud1s4bdm7da/KQD
DQ3pxylH7Kc2b8wWfptW2t9wEoqdjNezr24E+/c6kNIo9TmZ8mPigNBz/d7Sd5TzxhstmXoXscAv
FLpc7B/RhD5qwXWlYZwisemsTL6GVgBpaWI0zp4pk4DaQcT7FM17qddeHCiF5YD9g6TZBkYXnvke
5hW1JERYny3GjTNum8P3p9L3NHWpfAK2S90ChRwDb3nDy81B6b6K+YMNsJmmMjJhE/GbP6jMFE/2
cLIAsAT+Ssk/zNEJKXKe3gN4pQzBcDJksDxrlYJoYQE/rz1Ni7EpKiuuEUtODcGSCcRagh6t6cJV
yDh76DgxgjAvjATjPS6bdJ5PQWocTtjoMUvkMjbeEoWMuoe5cgsHl3HoYsLyxWwk1zn4BVSdjumi
D0o8juKUTFsFjN8yyNQyAA4KNRrhrIBdK8VTcsJC5JFjJnJiX1P6yrUWZPnH4YB3wIZwA5EkXjlg
tNrZghyWTMNoMs4GH6A=

301960965517874528560207857875230191048
'''

解题思路：

爆破iv 求得n 再将n进行yafu分解得到四个相同的p，因为n=p^k^ 所以k=4

解题代码：

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
from base64 import *
from gmpy2 import *
from os import urandom
from Crypto.Cipher import AES
from Crypto.Util.number import *

key=301960965517874528560207857875230191048
key=long_to_bytes(key)
m='GuGfliJiRkNsUbbmB+g/q4U3z6YahJ6G1Q9bg6ZT/ilJnkNMICmQYMFuhlNBuVZHfJJIFwwFJ5FKG+z9zSXalJq6quN6d3CSYSMHvYk04Orpn76Y2VQX5qQk72uCssd4x5KNIOmX0CvzJmjTWjLvL1U5twQupfkuDr/axqyHFss3pJkj9o0IRZmtz87bi5WojeUjOaayQ0RNenJJzhJ+zFJwdUCpUhwotHxLOPsUXYSoY7AKPwj53Dlsy0deNBKFN89BolC4pTwHWvn0M/8eu9kIze+5sQuKrk0VI5ASNzA6PRp1owpgsxNuy18k6/y01+mVheQkFrH2IrFNgqe3+Gu/PXEDPi3G2nAIi/4Xf9QI0DNH+hkoN40zWaX3OkEVQeLQ9o/KuggeoajYwDusFyQxOQZYFr5I+v8uBApcQz29bKIRiZX78r9YN3IaSsL0JgLPQPYaNPNiZMm5pqmv/zV0poZikYGYJsAwfjLJ/CYQ/iLBhkhKZoE9VxYEae7Wga1jwpJb3h/lA3mbvQofMTR6ivnSZHzUu3elxMFTgTi5adB4PsBdke0YRXlWP8/AoggBAN5OMw8n2LCASIhp7q/1iljNUuw/40mBCt75jszo1eBBDAbP7/DjXL5hUHFgen6xjedcySq/H0ibyNGasyePs3e+igr78fHyvXyIYYPaEtM4RjC3j3TXheRYRo9lObJgHUHSY0PgAgrqc1rECexNa+QCvzzapemNAEE9OT8YLOEkB6zzpSrZ6k/NR9KffGnqplQlWAfXdDrf3SsOmWVJ3G6DvmpTCukQgVYn+DCv5LdSSUZo2hjxBHPv8C5zpZiasPLDr+2CwUvccettO3wwrWQ1bPfRBZ7OSghvipbYI7awjt45tyxT5TopN7e3kud1s4bdm7da/KQDDQ3pxylH7Kc2b8wWfptW2t9wEoqdjNezr24E+/c6kNIo9TmZ8mPigNBz/d7Sd5TzxhstmXoXscAvFLpc7B/RhD5qwXWlYZwisemsTL6GVgBpaWI0zp4pk4DaQcT7FM17qddeHCiF5YD9g6TZBkYXnvke5hW1JERYny3GjTNum8P3p9L3NHWpfAK2S90ChRwDb3nDy81B6b6K+YMNsJmmMjJhE/GbP6jMFE/2cLIAsAT+Ssk/zNEJKXKe3gN4pQzBcDJksDxrlYJoYQE/rz1Ni7EpKiuuEUtODcGSCcRagh6t6cJVyDh76DgxgjAvjATjPS6bdJ5PQWocTtjoMUvkMjbeEoWMuoe5cgsHl3HoYsLyxWwk1zn4BVSdjumiD0o8juKUTFsFjN8yyNQyAA4KNRrhrIBdK8VTcsJC5JFjJnJiX1P6yrUWZPnH4YB3wIZwA5EkXjlgtNrZghyWTMNoMs4GH6A='
m=b64decode(m)
while 1:
    iv = urandom(16)
    cipher = AES.new(key,AES.MODE_CBC,iv)
    s=cipher.decrypt(m)
    if iv in s:
        n=bytes_to_long(s.replace(iv,b''))
        print(n)
        break
e=0x5b0cd450a7bfb679dc9caa8aa6fc131708fca2a34375d049ac035fb019463d9c3fa11adb0eb51dea1ae85223df59f887a12ab376cbcb272681c3872c57f4da27396052242b608e3ea4ff53061e63bbfdff652ce25f4ce73315fd1a73a5d5e7307402c7a3c6c1a80c63297b441125c38e23729da6473e5dc332e4e7201df25ff6c8b9918b262e56a31bebe13e093e6f4dba47a771961358cedf6d740732425cb708a633d538dcdc12ef7b49ce76aa270f50dd7cc1b879f1d7b19c6ac3b891fe4e20fb7645b7567237775881de7d30ba754d495ffe8ee751d1cfee1c661a2dbf13a53ff1bcf8085b39f6508fbf37137ebad659665fe5fcc67eef02970a44ac675e28103bd10f2045983d5adaa909b18b70a909b08b76c21b2798830276068d0ebd27303985bb5f3e681219a50bc761b7630587743768cf61922804d195e265aaaabb4740a2c5d7e8ff4e1c19cfb534d345f537e95e948591557f3136da617657e24d1904be373f5e7d63af330b837bcc662cbcd801eb436dbbeb714469d227e9f17e118db39eeb42e45455e6daf4d8fe0e19c4457b596c20e1ef8d235b230018a58e1c66c52c7317094aa5797f50a3b5ebe2be2abd1a04d907fbb68919956d7b0939ac0195a3f3bd3eb6f08eef67a895807768250172ec6bb2b35c9962de03df847170472b73981c04f2aef03721554c818ec9eb7f625d1a3fcdcf756adc4b6fd61950724ac2164a94df70f4aa1cc36c51dd2c3b6545c6c2233544254f6a24e6a170918fd0c533734ef859fed3c5d6f1f9acf8d3b77804c98fa5f1429763ebe860a77380a1e94626b46d88e5263855a0a0d226eb7ca64824c9a06acda851e650e6b035c04e27de61cd49ff49ac3ea3407440f9e76ce47c02301c1bc9c28befe0cd1f5b999961b055ffb39e2f451302aaedc5d779da03830bda1ed3ba9be4f23b2381096f3dc60c84a91ba0aa44242cc6aa361e2ecac867a2d1ef6868199ecb3004aa62bd56683c3476a9bd3f0316905e4f83ef5a907d9796231b9f506c82c09c739513a0db04467a071dcc34cb11bbba8cd3f1870174e04160ae74c2160a61a7c472e8edc51e969a2f0fb47cee59b67d401ecb13b06f72dcfb24f5850b8921b8bad14f7c6bd123c13b3a2ea1761fc425066ba107d61e96d2fa9b3ed88befec93578495ef4c7a1eb95d76679d1f5261f0202e1de881c5c5b1fb44f471a75a305d86df1123cd83c8bc9449c73cf34dbd247111c873bc1fc7948863bb59f2ac3d7129c2e7c3e0ef94afb38a01b3e42f83f42a5cc8e14cbe53c0c8d76768cdc98bef921aaca60204519b516d4c9de7cf581eec8a53faa2e2d96722d0ef2c23d5567ba48104890534cd84432565236cb3402504e0feb6c25426c52d2b2b42f10a007cdd38b540cf64a96ee784deb2b595deb4a9497f9a25ab06eab443010b66e7decc162dcbd7de12737d72a46ec0b8151e1ed42716af2c7602692d7c0ea757bc056c89d2640773a4c3c1a2297c87c13676e414003ff3af0d1abb87ba618e24a4dfe05c0b4443bda53d26c7e30f0dec498d9091074fe3444e81b9a4d8d7acc8b1e38f6afc63540a4e8880fd73bd34bc3563cc0a98bd35ce7455d5cf8a114bc2fe2fb9a58e725cc121e4e242fc0a9a8e38615bda67fd9f158e718154eb51d0ec3d941426933e36fba1db0d7b59d52be90aa796895e6a49fed0a7887b8d7c71a9aa023a8dc73391e3d1bfc746cde9f964d99625900624a8eb300f2d7d2f8703f470776088f27aaa72e7607dcd78cf63754cec00db23bb36beb48cffb20a06df884f101a9
c=0x26c6b16ed40253ff31bdcd502d63230a9655f29599cfb41a29f10e700589e6a13a8c78f483e0aa8b9353fa258a1437ba15e8d2c8bb2b090a6887740b31d71550745611fabd087904f150b4d928d155a7fcdd1a64c7349ce984dfd08c4c795e93b409f53c1458e6de777dc5993198f4c0648381116fe5cbafa57499d9ce685c625df4797afc344e8fe4a0fc36cf82ba1423c8a4ad7a33bc4cbab25e2df729085f96d3d9d542d981fa46cac8a37ceb70b9f808213845c06b72be7e2d1224e4dc02817bd474c690e43f6d8f1916a20f2e078bfaa604343d695e6f5f88d9f11c43a886ff97d9bd26b0126af40bed8e03a43bf8c912b5b0dd2f9f2e7e99db066759f573cd59a40a554bebdd3e7e0adbc38fcb91adeb72f9dcd30558b082471a02fd9131a61cf29b1f4e38a5d689d8dcd0b8dc29075e3a33b2d6a25bee6ff9e20d269cc088a2b155be76a1531ce30b25edf928990b5143fc5ae2737d8d4070d0517f5137c458d7afed8f51e2c2973dd143235c9deaffe9ce8fbcd767a93573399dafd5ef61408c77302c993354a080684cdbfb7c1eeb6e6be907db790038c7ce62517815d16fe366bd26178f2f05b9e56450814f4ba7ab6cab54c5f78316b0451057785c03a77c20814eb405cd20e5bff5247a12500dd16173125ffdef4fb6317ab942d0d7e0e584a8fd97a8ba8d87fd38127d6d059902a2d48dafd10938ea5d108f3eb986aabf9e212151b0e540bb5fd25888143633be9982395d4d3bef5278be37328e0239569eb511698ef7f9e7e12aa204cb4c069ffcdeecb65f42ba37f7bfd47c4ba8df384a88adf3486b58cc1620185ac81dfb10f591fc82f3ae046341ebd1e8288f10500d6677e91b89729dfd299b74be13a9183725aacb0023f4fb01efda61390b0312d90ff6a9a319433681ad1811efe038fcdeb6dc1c3f594c4f8011aacfee74ea9638fccb3d669435a1208578c934277caa3ec74f9efbb33e024909b121e7b4e48ec94b762fa9dcab8a1c11b86bb9db164c7655504d304661e04e95b0b356f5968334596fb11df95bbdcb3a6618f431c864658827662f760fc86b2136221bd50472dc19c4f177eb5edf7978760dc15150cfda0a3ea649cb672b8f37229298c6edcc630e3ac9a5f43f58a93ba8def335472f7ebdedd7715a27c4ea622344a949bec59af030455ed61911d53388022bd502e800b769ef499f94f02c96f486b40ce68dbdc42e5690ac2992bedf7f0ba384504c32cb00a25d4e125483003152e81ebe9c12d928627d7f14fc3fbdf5141addc477d5ae4f32e64dcb58a6e2cf955ad7ae54e1665b3199bd0fae36b9ec56c09ac00efc9d27e69a93f4e08652edc3340fa2c518d388ee4a005b9c83956b9139b98380f6925a1a4c3e64ff8d96f2827d0d8a25cc72a2c03a28e33871284b46e10c85f2ad75969b1d84e9d88bb4e05d
#n解出来用yafu分解 命令yafu-x64 "factor(@)" -batchfile p.txt 将要分解的数放进去，记得换行

p=20935418603755826153357961486749000137883878122092541278485245382546346099923598569473814209357669395236788185259189925906627960621490996925200115559569329810746744675867738485473466021581185385430988547168263735484625716958718825113577345085361945421237478366338611831738408648424304228723729310335432168121087334054958276987167490905779911687736536416815227240962562460212183301435420718431023950641725670461044591993133883921646824589614644103106984493917214402278641218422432546374433956301830629567708335305598359150744372547912472684947785245810663217040977994966632748245272393755319650187559761562868158211001
n=192099659971585644585994265356151893462377034960456794411988891865292985043855003153008582523342780428794810302819600257505211543181857907106415116235678327109890992104863370288179222517757670217778339429390238355802091081769000348240713104001227465195009290503347809694648095737603288589286587488951249122808668565718081375241590144993161651582987613212486939491481151331461062699460189663231086086438368188327851901136662178362187582946879512941211019554239356512237609083714797677920647956302526035540976096625395045576074618882913271336136197136983455626303177930159461486947144900160609689255459511724884379858318269727855760842754096692298627624434916921714588784746851193083162412064551556945404206854303755771760752959780690233660596074620616291920828653736584021095005924141651891036415545086668712524203621422434855332350634434410255685899978575653707114060202874964589333127633649581915659487394392054766924938473585908627256425677898409670003835577877230695953230779772624257018952499735317822119685099669750110189929339815489604592011705747522509443099530871227359100112168474188213599742539558713508525377201675194485642343270883438486906530571528359024979260422106335247512597006126883635090340753475080689838573417741101697005667509804117477078714343224837766971175288554228364175312803060405952234277289653353821049167680289322424370730116331485806992442330752262754657170209301796826520903516939270541484630918051998431104746567068050303837266511857593664457675203874622377426656951134697321668662464768461125119491757074002358277630438779981831394788463952738787381176350532134825112678994090733193226361777537532269515922485937976349665991399772388721397960468392351155664481353730638831836994949983037350384382753327305729403941493686341892251753278811372338966651828844911034352886809190060883995056847456555950315611326987545276629529435068813158170690823902054787362572088738335891773343913632258874832438998334332913261810760087047758552754566575308536675397251987093487164542963055804002441751864022715424662848335470359948420027756835213050500577294799638589135949755879898985814242501638839907383377834819866500082619067419468232672548637154121177897443704368253245514204975147693342503301921844252239673318375741456151277008424086433210309669337358030499431697081307189511178107489812792122478536534259554160073644974772253911579253927334216606449192146737795612311912838169178570116934403812068138348378295739329366212651044519758844001
d=invert(e,(p-1))
print(long_to_bytes(pow(c,d,p)))

[GKCTF 2021]RRRRsa

题目如下：

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

# flag = b'xxxxxxxxxxxxx'
# p = getPrime(512)
# q = getPrime(512)
# m = bytes_to_long(flag)
# n = p*q
# e = 65537
# c = pow(m,e,n)
# print('c={}'.format(c))
#
# p1 = getPrime(512)
# q1 = getPrime(512)
# n1 = p1*q1
# e1 = 65537
# assert gcd(e1,(p1-1)*(q1-1)) == 1
# c1 = pow(p,e1,n1)
# print('n1={}'.format(n1))
# print('c1={}'.format(c1))
# hint1 = pow(2020 * p1 + q1, 202020, n1)
# hint2 = pow(2021 * p1 + 212121, q1, n1)
# print('hint1={}'.format(hint1))
# print('hint2={}'.format(hint2))
#
# p2 = getPrime(512)
# q2 = getPrime(512)
# n2 = p2*q2
# e2 = 65537
# assert gcd(e1,(p2-1)*(q2-1)) == 1
# c2 = pow(q,e2,n2)
# hint3 = pow(2020 * p2 + 2021 * q2, 202020, n2)
# hint4 = pow(2021 * p2 + 2020 * q2, 212121, n2)
# print('n2={}'.format(n2))
# print('c2={}'.format(c2))
# print('hint3={}'.format(hint3))
# print('hint4={}'.format(hint4))

c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513

题解：运用了二项式定理和费马定理：

###二项式定理：

image-20221224172817112

###费马定理:

(对于任意的a)都有 a^p^ = a mod p

下面是题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513

q1=gcd(pow(hint2-212121,202020,n1)*pow(2020,202020,n1)-pow(2021,202020,n1)*hint1,n1)
p1=n1//q1
d1=invert(65537,(p1-1)*(q1-1))
p=pow(c1,d1,n1)

q2=gcd(pow(hint4*pow(2020,212121,n2),202020,n2)-pow(hint3*pow(2021,202020,n2),212121,n2),n2)
p2=n2//q2
d2=invert(65537,(q2-1)*(p2-1))
q=pow(c2,d2,n2)

d=invert(65537,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,p*q)))

#dp高位泄露

∵e $\times$ d == 1 (mod (p-1)*(q-1))

∴ e×d=k1(p−1)(q−1)+1,k1∈Z

∵dp=d(modp−1)

∴e×[k2(p−1)+dp]=k1(p−1)(q−1)+1,k1、k2∈Z

∴e×dp=(p−1)[k1(q−1)−ek2]+1

令k3=k1(q−1)−ek2，即e×dp=k3(p−1)+1

∴e×dp≡1(modp−1)

∵dp<p−1

∴k3<e

∵e×dp=k3(p−1)+1=k3×p−k3+1

∴e×dp+k3−1≡0(modp)

例题

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

p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = bytes_to_long(flag)

e = getPrime(128)
c = pow(m, e, n)
Phi = (p - 1) * (q - 1)

d = inverse(e,Phi)
dp = d % (p - 1)
secret_bit = dp.nbits()
chall_bit = secret_bit // 10
dp_high = dp >> (secret_bit //4 - chall_bit)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
print(f"{dp_high = }")

n = 9626914648175807268839143676227095101980031070047647327045582280748694832216645112357529307944805440114412025869877414925765509609949371295125175984152355326423825913374665443245233712196365817534604282292930878932535542824662249475565126660861897374850035460910330354370702344758838468565703425837126965670261413234060341822240842303253772814320580075327044602083527665829967879201244632766438777732622471383090330433132675934776788448154390615884791376197275832246225394346036867574477571331077665534270202128676467131896817397009441732798179988097476549452316090454248154250557222275509657583603369166147046224167
e = 261033845461512919347224526819426965993
c = 8167072875653908300438534241945111978973377034004369729154075917327506787788294641265723479936235733352952340094125694128083517849993080549059971933916349692515383524310897091844797640158242392286178833532090645120013397781259946259897809389572007177779345464727367090798190829584050410581922434447977979455846430899041335833529254283223307060899575576984818796299073185136561133516441028922375927995959717704831141580300822294712823384439560144989777737557584997102713261649578080236551187991584888132891423792799039597796489304179392680823403263989219951067097395478445898353752093075695145723204835775616547644040
dp_high = 1833446753326863013514016952467031467611205859176333578141304173443670822178061540565686499910445598690074115131572091819797766974985107130799022745293901239282222406491407466248300317047718537990282593656719800970412646141269406221391171573486187631003443884607
print(dp_high.bit_length())
print(e.bit_length())

解题代码：

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

n = 9626914648175807268839143676227095101980031070047647327045582280748694832216645112357529307944805440114412025869877414925765509609949371295125175984152355326423825913374665443245233712196365817534604282292930878932535542824662249475565126660861897374850035460910330354370702344758838468565703425837126965670261413234060341822240842303253772814320580075327044602083527665829967879201244632766438777732622471383090330433132675934776788448154390615884791376197275832246225394346036867574477571331077665534270202128676467131896817397009441732798179988097476549452316090454248154250557222275509657583603369166147046224167
e = 261033845461512919347224526819426965993
c = 8167072875653908300438534241945111978973377034004369729154075917327506787788294641265723479936235733352952340094125694128083517849993080549059971933916349692515383524310897091844797640158242392286178833532090645120013397781259946259897809389572007177779345464727367090798190829584050410581922434447977979455846430899041335833529254283223307060899575576984818796299073185136561133516441028922375927995959717704831141580300822294712823384439560144989777737557584997102713261649578080236551187991584888132891423792799039597796489304179392680823403263989219951067097395478445898353752093075695145723204835775616547644040
dp_high = 1833446753326863013514016952467031467611205859176333578141304173443670822178061540565686499910445598690074115131572091819797766974985107130799022745293901239282222406491407466248300317047718537990282593656719800970412646141269406221391171573486187631003443884607
xx=dp_high.bit_length()
secret=dp_high
xx=xx//17*3
'''
z=[]
F.<x> = PolynomialRing(Zmod(n))
for i in range(10):
    f = (secret << (xx+i))*e+ x
    x0= f.small_roots(X=2 ** (xx+128+i), beta=0.44)
    z+=x0
print(z)
'''
z=[2496101125860707554682684372938133658387043188879132480090222251307117091908623947631, 4992202251721415109365368745876267316774086377758264960180444502614234183817247895262, 9984404503442830218730737491752534633548172755516529920360889005228468367634495790524, 19968809006885660437461474983505069267096345511033059840721778010456936735268991581048, 39937618013771320874922949967010138534192691022066119681443556020913873470537983162096, 79875236027542641749845899934020277068385382044132239362887112041827746941075966324192, 159750472055085283499691799868040554136770764088264478725774224083655493882151932648384, 319500944110170566999383599736081108273541528176528957451548448167310987764303865296768, 639001888220341133998767199472162216547083056353057914903096896334621975528607730593536, 1278003776440682267997534398944324433094166112706115829806193792669243951057215461187072]
p=gmpy2.gcd(n,z[1]+(secret<<(xx+1))*e)
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

杭赛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
from random import randint
from libnum import gcd, s2n

from secret import flag

plain = flag[6:-1]
assert flag == 'hgame{' + plain + '}'
v = bin(s2n(plain))[2:]
l = len(v)
a = [2 << i for i in range(l)]
m = randint(sum(a), 2 << l + 1)
w = randint(0, m)
assert gcd(w, m) == 1
b = [w * i % m for i in a]

c = 0
for i in range(l):
    c += b[i] * int(v[i])

print(f'm = {m}')
print(f'b0 = {b[0]}')
print(f'c = {c}')
from gmpy2 import *
m = 1528637222531038332958694965114330415773896571891017629493424
b0 = 69356606533325456520968776034730214585110536932989313137926
c = 93602062133487361151420753057739397161734651609786598765462162

参考代码 (感谢 RUAN XINGZHI)

解题代码：

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
m = 1528637222531038332958694965114330415773896571891017629493424
b0 = 69356606533325456520968776034730214585110536932989313137926
c = 93602062133487361151420753057739397161734651609786598765462162
w=798996914532181894739831870574530315179503554412003471315675

# for k in range(0,1000):
#     w=(k*m+b0)//2
#     if(w*2%m==b0) and gcd(w,m)==1 and w<m:
#         print(w,k)
#     continue
# 
# 
# for l in range(180,300):
#     a=[2<< i for i in range(l)]
#     if (sum(a)<m<(2<<l+1)):
#         print(l)
l=198
a=[2<< i for i in range(l)]
print(a)

def dec(A,B,r, S):
    S = S * gmpy2.invert(A, B) % B
    print(f"S' = {S}")

    ans = []

    for t in r[::-1]:
        if S >= t:
            ans.append(1)
            S -= t
            print(f'find {t}, S <- {S}')
        else:
            ans.append(0)

    return ans[::-1]


m = 1528637222531038332958694965114330415773896571891017629493424
b0 = 69356606533325456520968776034730214585110536932989313137926
c = 93602062133487361151420753057739397161734651609786598765462162
w=798996914532181894739831870574530315179503554412003471315675
l=198
a=[2<< i for i in range(l)]
print(dec(w,m,a,c))
x=[1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
flag=""
for i in x:
    flag+=str(i)
print(flag)
from libnum import *
flag="110001011101000010011101110011010111110011010001101110010111110011001101100001011100110111100101011111011000100110000100111001010111110110100101110011011011100011011101011111011010010111010000111111"
print(int(flag,2))
print(n2s(310426075381425495216582488381732379757682003677291488048191))

rsa

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
# from secret import flag
from sympy import nextprime
from math import *
from gmpy2 import*
flag=b''
r = getRandomNBitInteger(64)
p = r**5 + r**4 - r**3 + r**2 - r + 2023
q = r**5 - r**4 + r**3 - r**2 + r + 2023
p =nextprime(p)
q =nextprime(q)
n = p*q
def enc(flag, n):
    m = bytes_to_long(flag)
    return pow(m, 65537, n)
c = enc(flag, n)
print(n)
print(c)
#n=
11824699584547388001880993009585262615559521133074853372912781885870658357656825890203055052542350108160772914440279592619943330080926206705955780256356624153251252693475833017685304050970071
#c=
9670726607020944351671204940747927021122961984798144090103241740809652984246397187861619784919850158332729124051811115335648904417579853822542292490318033224916195688565647063342943307830109

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c=9670726607020944351671204940747927021122961984798144090103241740809652984246397187861619784919850158332729124051811115335648904417579853822542292490318033224916195688565647063342943307830109
r_r=iroot(n,10)[0]
r=10169017895217972920
for i in range(1000):
    r=r+i
    p=r**5 + r**4 - r**3 + r**2 - r + 2023
    q=r**5 - r**4 + r**3 - r**2 + r + 2023
    P=nextprime(p)
    Q=nextprime(q)
    if(P*Q-n)==0:
        print(P)
        print(Q)
e=65537
p=108741434534161760819145712447425136902637648261753373877849516624154160412557307600529791486217
q=108741434534161760797758900927445824700076964173732251026857646765719423492132169786665492535263
print(p*q)
d=invert(e,(p-1)*(q-1))
m=powmod(c,d,n)
print(m)
print(long_to_bytes(m))