彩笔
2022-12-08

2022_重庆市赛WP_...

n和Q求最大公约数拿到q，P直接开立方拿到p，n整除p和q拿到r

或者求解q时可以

1
2
3
# Eq = Euler(Q) = Euler(q**2) 求q-> sqrt(Euler(q**2)) + 1 = q
# EQQ = gmpy2.iroot(Eq, 2)[0] # 求平方根
# q = EQQ + 1

Euler对于任意 互质 的整数a和b有性质f(a b) = f(a) ⋅ f(b)

题面

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

p=getPrime(512)
q=getPrime(512)
r=getPrime(512)
n=p*q*r
e=65537
m=bytes_to_long(flag)

def Euler(x):
    res=0
    for i in range(1,x):
        if gmpy2.gcd(i,x)==1:
            res+=1
    return res

P=p**3
Q=q**2
c=pow(m,e,n)

print(P)
print(Euler(Q))
print(c)
print(n)

#P = 1686761823519516525084824311416810253107853832929411677237594989001281261421956188747941222367576127569696216513071075733130132251383529469095077597202999362675041210639065389821237728348981344440193122126487447235175127680730304754656661704596111547454161716607787386914764780833658069534913186485846587027674567133467341836048413431174183101579802349498153899249182793495245916757355079598668221097821452488627067390724198617676379698358212167618567704428433303
#Eq = 54800501457630149544580145188029519076092032026436445384163914536965196942938808746487258773679836358732387355329080483568564046906919385574994390974732491368590525875801103056613954297623835159311237599961507385582029709732950222118171961946571285930711702624160354541459438994349318149872111029043942485620
#c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493
#n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051

$gcd$ 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
e = 65537
r = 12142261002625479270959358223863571062295429117378994112396394259314721874267081158944354513358164889564741712782226613341612447412750073385958464420872713
c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493
n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051
# p = gmpy2.iroot(P, 3)[0] # 开3次方根
p = 11903771663059518341912645066042582267678745214691121272332269847512624178064427789028954264701292914161793272471217879550653909080475237446747964043276487
# q = gmpy2.gcd(n,Eq)
q = 7402736079155473279000574596031490410671021795687853893698348179857428763438305848933328416647633118223876785823588566614584124350907811192587130096357221
phi = (q - 1) * (p - 1) * (r - 1)
# phi = (q - 1) * (p - 1)
# n = q * p
d = pow(e, -1, phi) # 求逆元 d = e**-1 mod phi
m = pow(c, d, n)
print(long_to_bytes(m))

拿到q p r (n的三个因子) 后也可以只用q p (不用r) 构造出新的phi, d和n来解密(数学底力不足，有的题不能这样操作，原因暂时未知，挖坑先)

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
q = 7402736079155473279000574596031490410671021795687853893698348179857428763438305848933328416647633118223876785823588566614584124350907811192587130096357221
p = 11903771663059518341912645066042582267678745214691121272332269847512624178064427789028954264701292914161793272471217879550653909080475237446747964043276487
e = 65537
r = 12142261002625479270959358223863571062295429117378994112396394259314721874267081158944354513358164889564741712782226613341612447412750073385958464420872713
c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493
n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051
# phi = (q - 1) * (p - 1) * (r - 1)
phi = (q - 1) * (p - 1)
n = q * p
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

$sqrt(Eq)$

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
#by sangge’s code
from Crypto.Util.number import *
import gmpy2
import binascii
import hashlib


def Euler(x):
    res = 0
    for i in range(1, x):
        if gmpy2.gcd(i, x) == 1:
            res += 1
            return res

# 16进制转字符串
def hex_to_str1(s):
    s = binascii.unhexlify(s) # ASCII 码转换函数
    # unhexlify()传入的参数也可以是b'xxxx'(xxxx要符合16进制特征)
    return s.decode('utf-8')  # s的类型是bytes类型，用encode()方法转化为str类型(去除b'')

P = 1686761823519516525084824311416810253107853832929411677237594989001281261421956188747941222367576127569696216513071075733130132251383529469095077597202999362675041210639065389821237728348981344440193122126487447235175127680730304754656661704596111547454161716607787386914764780833658069534913186485846587027674567133467341836048413431174183101579802349498153899249182793495245916757355079598668221097821452488627067390724198617676379698358212167618567704428433303
EQ = 54800501457630149544580145188029519076092032026436445384163914536965196942938808746487258773679836358732387355329080483568564046906919385574994390974732491368590525875801103056613954297623835159311237599961507385582029709732950222118171961946571285930711702624160354541459438994349318149872111029043942485620
c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493
n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051
e = 65537
p = gmpy2.iroot(P, 3)[0]
# Euler对于任意 互质 的整数a和b有性质f ( a b ) = f ( a ) ⋅ f ( b )
Eq = gmpy2.iroot(EQ, 2)[0] # 求平方根
q = Eq + 1
r = n//p//q # 求整数除法
phi_n = (p - 1) * (q - 1) * (r - 1) # 求欧拉函数
d = gmpy2.invert(e, phi_n) # 求逆元
m = pow(c, d, n) # 求模幂
# print(m)
flag = hex_to_str1(hex(m)[2:]) # 不会附带 b'' 与下方转换类似(# 转化为16进制 后去掉前面的0x 后转化为str类型)
# flag = long_to_bytes(m) # 会附带 b'' 可以像上面一样再转一次str
print(flag[5:-1]) # 去掉前后的flag{} ,下面继续进行题意要求的md5加密
hash = hashlib.md5() # md5加密
hash.update(flag[5:-1].encode('utf-8')) # encode()方法将str类型转化为bytes类型
print("flag{" + hash.hexdigest() + "}") # hexdigest()方法将bytes类型转化为str类型

![q的推导.png]]

彩笔

彩笔

熟练拼写:XCPC,Crypto