素数分解

[柏鹭杯 2021]试试大数据分解?

题目附件

题目给出了四个附件，分别是flag.enc1、flag.enc2、flag.enc3、flag.enc4和public.pem

解题思路

我们先读取先public.pem看下有没有进一步的发现。

from Crypto import Random
from Crypto.PublicKey import RSA
with open("public.pem") as f:
    key=RSA.import_key(f.read())
    n=key.n
    e=key.e
print(n)
print(e)


#980710843783426929436352108445477207723530613536846588304753445659989738992892689598648497

#99991

我们尝试分解n

p=948539437740472240970258995719507356652939947
q=1033916782753483187367063564275935620987269651

同时e=99991

这样我们就可以进行解密。

exp.py

from Crypto import Random
from Crypto.PublicKey import RSA
from gmpy2 import *
from Crypto.Util.number import *
import bas64
with open("public.pem") as f:
    key=RSA.import_key(f.read())
    n=key.n
    e=key.e

p=948539437740472240970258995719507356652939947
q=1033916782753483187367063564275935620987269651

phi=(p-1)*(q-1)

d=invert(e,phi)
with open('flag.enc1','rb') as f:
    c=f.read()
    c=bytes_to_long(base64.b64decode(c))
    m=pow(c,d,n)
    print(long_to_bytes(m))

with open('flag.enc2','rb') as f:
    c=f.read()
    c=bytes_to_long(base64.b64decode(c))
    m=pow(c,d,n)
    print(long_to_bytes(m))

with open('flag.enc3','rb') as f:
    c=f.read()
    c=bytes_to_long(base64.b64decode(c))
    m=pow(c,d,n)
    print(long_to_bytes(m))


with open('flag.enc4','rb') as f:
    c=f.read()
    c=bytes_to_long(base64.b64decode(c))
    m=pow(c,d,n)
    print(long_to_bytes(m))

[黑盾杯 2020]Factor

题目附件

这题附件解压完全是乱码，也不知道是环境坏了，还是有什么别的考点。。。。

最后在别的师傅的wp里找到了原题。

n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208
gcd(m, n) = 1

解题思路

这里的n也是可以被分解，但是这个n被分解成了三个素数

exp.py

import gmpy2
import binascii

n = 3454083680130687060405946528826790951695785465926614724373
p = 11761833764528579549
q = 17100682436035561357
r = 17172929050033177661
e=3
c = 1347530713288996422676156069761604101177635382955634367208
phi=(p-1)*(q-1)*(r-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(binascii.unhexlify(hex(m)[2:]))

#直接这样求解发现逆元不存在，但是考虑flag比较小，我们把和e存在公约数的素数消去掉，不影响最终的结果
import gmpy2
import binascii

n = 3454083680130687060405946528826790951695785465926614724373
p = 11761833764528579549
q = 17100682436035561357
r = 17172929050033177661
e=3
c = 1347530713288996422676156069761604101177635382955634367208
# print(gmpy2.gcd(q-1,e)) 3 下边消去q的影响
phi=(p-1)*(r-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n//q)
print(binascii.unhexlify(hex(m)[2:]))

#CMISCCTF{3_RSA}

共享素数

[羊城杯 2021]Bigrsa

task.py

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

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n1)
c = pow(c, e, n2)

print("c = %d" % c)

# output
# c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

解题思路

我们可以发现n1,n2存在公约数，进而可以分解这两个大整数，之后对整个加密流程逆向，先用(d2,n2)对c解密，再用(d1,n1)对解密后的结果继续解密，就能还原m

exp.py

from gmpy2 import *
import binascii

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

p=gcd(n1,n2)
q1=n1//p
q2=n2//p

e=65537

phi1=(p-1)*(q1-1)
phi2=(p-1)*(q2-1)

d1=invert(e,phi1)
d2=invert(e,phi2)

m=pow(c,d2,n2)
m=pow(m,d1,n1)

print(binascii.unhexlify(hex(m)[2:]))

[闽盾杯 2021]decode

task.py

n1:
15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591
n2:
28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749
n3:
18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839
e1:
65537
e2:
27751
e3:
65537
c1:
5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206
c2:
21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741
c3:
13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486

解题思路

随便测试一下发现（n1,n2）,（n2,n3）公约数不为零，那么借助公约数可以分解这三个大整数。

exp.py

from gmpy2 import *
import binascii

n1=15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591
n2=28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749
n3=18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839
e1=65537
e2=27751
e3=65537
c1=5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206
c2=21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741
c3=13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486

p1=gcd(n1,n2)
q1=n1//p1

p2=gcd(n1,n2)
q2=n2//p2

p3=gcd(n2,n3)
q3=n3//p3

phi1=(p1-1)*(q1-1)
phi2=(p2-1)*(q2-1)
phi3=(p3-1)*(q3-1)

d1=invert(e1,phi1)
d2=invert(e2,phi2)
d3=invert(e3,phi3)

m1=pow(c1,d1,n1)
m2=pow(c2,d2,n2)
m3=pow(c3,d3,n3)

print(binascii.unhexlify(hex(m1)[2:]))
print(binascii.unhexlify(hex(m2)[2:]))
print(binascii.unhexlify(hex(m3)[2:]))

#b"hahaha, you've got the flag didn't you !the front part is :flag{G00d_w4"
#b"hahaha, you've got the flag didn't you !the middle part is :y_tO_cR"
#b"hahaha, you've got the flag didn't you !the last part is :4ck_RS4}"

广播攻击

[鹤城杯 2021]Crazy_Rsa_Tech

task.py

from Crypto.Util.number import *
from Crypto.Util.Padding import *

FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p*q
    e = 9
    while(GCD((p-1)*(q-1),e)!=1):
        p, q = getPrime(512), getPrime(512)
        n = p*q
    d = inverse(e,(p-1)*(q-1))
    return n,e,d

n_list=list()
c_list=list()
for i in range(9):
    N,e,d=init_key()
    n_list.append(N)
    c=pow(FLAG,e,N)
    c_list.append(pow(FLAG,e,N))
    assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)


输出数据有点多 这里不放了

解题思路

观察加密的过程，这里一共进行了9次循环，我们可以得到。

这样我们可以借助crt求解出再开根还原m

exp.sage

from gmpy2 import *
import binascii

n_list=...
c_list=...


m=crt(c_list,n_list)
m=iroot(m,9)[0]
print(binascii.unhexlify(hex(m)[2:]))


#flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16

连分数攻击

[湖湘杯 2021]signin

task.sage

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

m1 = bytes_to_long(flag[:len(flag) // 2])
m2 = bytes_to_long(flag[len(flag) // 2:])

def gen(pbits, qbits):
    p1, q1 = getPrime(pbits), getPrime(qbits)
    n1 = p1**4*q1
    q2 = getPrime(qbits)
    bound = p1 // (8*q1*q2) + 1
    p2 = random.randrange(p1, p1 + bound)
    while not isPrime(p2):
        p2 = random.randrange(p1, p1 + bound)
    n2 = p2**4*q2
    return (n1, n2), (p1, q1), (p2, q2)

e = 0x10001
pbits = int(360)
qbits = int(128)
pk, sk1, sk2 = gen(pbits, qbits)
c1 = pow(m1, e, pk[0])
c2 = pow(m2, e, pk[1])
print(f'pk = {pk}')
print(f'c1, c2 = {c1, c2}')

"""
pk = (1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989)
c1, c2 = (361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394)
"""

思路分析

注意到这里的n1,n2的生成方式是经典的，这里我们可以用尝试用连分数分解n1,n2

exp.sage

from Crypto.Util import number
import gmpy2

n1=1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233
c1=361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438
e1=65537

n2=1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989
c2=33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394
e2=65537


def continuedFra(x, y):
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y
    return cF


def Simplify(ctnf):
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)


def getit(c):
    cf = []
    for i in range(1, len(c)):
        cf.append(Simplify(c[:i]))
    return cf


def attack(e, n):
    cf = continuedFra(e, n)
    for (p2, p1) in getit(cf):
        if p1 == 0:
            continue
        if n1 % p1 == 0 and p1 != 1:
            return p1, p2
    print('not find!')


q1, q2 = attack(n1, n2)
p1 = gmpy2.iroot(n1//q1, 2)[0]
p2 = gmpy2.iroot(n2//q2, 2)[0]
phi1 = p1**3*(p1-1)*(q1-1)
phi2 = p2**3*(p2-1)*(q2-1)
d1 = gmpy2.invert(e1, phi1)
d2 = gmpy2.invert(e2, phi2)
m1 = number.long_to_bytes(gmpy2.powmod(c1, d1, n1))
m2 = number.long_to_bytes(gmpy2.powmod(c2, d2, n2))
print(m1+m2)

#b'flag{8ef333ac-21a7-11ec-80f1-00155d83f114}'

[广东强网杯 2021 个人组]EzRSA

task.py

#coding=utf-8
from Crypto.Util.number import *
from random import randint
from math import gcd
from flag import FLAG
assert len(FLAG)==47
def get_pub_key(bit_n, bit_lucky):
    assert 2*bit_lucky < bit_n
    while True:
        ran_num1, ran_num2 = randint(pow(2,bit_lucky-1),pow(2,bit_lucky)), randint(pow(2,bit_n // 2 - bit_lucky-1),pow(2,bit_n // 2 - bit_lucky))
        g = ran_num1 * ran_num2 + 1
        if isPrime(g):
            while True:
                ran_num3, ran_num4 = randint(pow(2,bit_lucky-1),pow(2,bit_lucky)), randint(pow(2,bit_n // 2 - bit_lucky-1),pow(2,bit_n // 2 - bit_lucky))
                j = ran_num1 * ran_num4 + 1
                t = ran_num3 * ran_num4 + 1
                if isPrime(j) and isPrime(t):
                    while True:
                        e = randint(pow(2,bit_lucky-1),pow(2,bit_lucky))
                        if gcd(e, ran_num1 * ran_num2 * ran_num3 * ran_num4) == 1:
                            phi = (g - 1) * (t - 1)
                            d = inverse(e, phi)
                            k = (e * d - 1) // phi
                            o = k * ran_num2 + 1
                            if isPrime(o):
                                n1, n2 = g * t, j * o
                                return (e, n1, n2)

def encrypt(msg, e,n):
    return pow(msg, e, n)

bit_n, bit_lucky = 1024, 256

e, n1, n2 = get_pub_key(bit_n, bit_lucky)

FLAG = bytes_to_long(FLAG.encode())

c1 = encrypt(FLAG, e, n1)
c2 = encrypt(FLAG, e, n2)

print('e =', e)
print('n1 =', n1)
print('n2 =', n2)

print('c1 =', c1)
print('c2 =', c2)

解题思路

参考文章

国际赛题目WP

分析源代码有

然后我们有（文章里有详细证明）

然后我们对进行连分数展开，进而获得的展开。

同时，我们已知

这样我们可以通过CRT求解欧拉函数，进而完成解密。

exp.py

借鉴了Xenny的脚本。

from Crypto.Util.number import *
from sage.all_cmdline import *
from xenny.ctf.crypto.modern.asymmetric.rsa import wiener
e = 77493305850606946966866586869701562747566137421194857276849326558383863716599
n1 = 38214712801044280452242029022307023900010505700133304226967361821658293768459754887223522190673421124166486124464596635967747405359806642464884601455285823454970604600165907209542618963333642882524596571019916658676095313436156240684679902251615046617153094607425987125749225956361360222801251450373042579071
n2 = 11918534754165556595562303500191427316052163288557481525821438608864207524482981704928088272082867228651327063972728644192877335261376841505970220897803876176646736511250339814035116162036800063521023303060582016775080988747746487028664050144843952770605999675734459531886474293242344088869877433555271258269
enc1 = 15808757304442558489652709164051631267713593320560967145595438513675108079906680505924179038743563463272753097766933667737349956243897214853643343110837736923623483907392474855188388096345292952323482631367759757699216716624973244377786699291503949070419765404840454938181818882998235566160193218211345167102
enc2 = 6376686158682997059741103218078544724010800198504747162290763103690338182777916072489234933936183210135919268370502287963945937266836059808775864844630371956704383598114953698187649635431791980376016420776898290168916806683089572655387949425292390749405301644222442142567586889975355029412203353803624681004

cf = wiener.ContinuedFraction(n2, n1) #连分数展开
cnt = 0
for k, r3 in cf.fractionlist:
    print(cnt)
    cnt += 1
    if gcd(k, e) != 1:
        continue
    
    r = inverse_mod(-k, e)
    phi = crt([r, 0], [e, r3])
    md = e*r3 // gcd(e, r3)
    st = phi + (n1//md) * md #e,r3不一定互素
    
    for i in range(-100, 100):
        if gcd(e, st+i*md) != 1:
            continue
        d = inverse_mod(e, st + i*md)
        m = long_to_bytes(power_mod(enc1, d, n1))
        if b'flag' in m:
            print(m)

AMM算法

[NCTF 2019]easyRSA

task.py

from flag import flag

e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q

assert(flag.startswith('NCTF'))
m = int.from_bytes(flag.encode(), 'big')
assert(m.bit_length() > 1337)

c = pow(m, e, n)
print(c)
# 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

解题思路

AMM裸题，直接上板子。

exp.py

# -*- coding:utf8 -*-
from gmpy2 import *
from Crypto.Util.number import *
import random
import math

def onemod(e, q):
    p = random.randint(1, q-1)
    while(powmod(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = powmod(p, r**(t-1)*s, q)
    b = powmod(o, r*a-1, q)
    c = powmod(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = powmod(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (powmod(o, alp, q)*h)
    return result

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp


def calc(mp, mq, e, p, q):
    i = 1
    j = 1
    t1 = invert(q, p)
    t2 = invert(p, q)
    for mp1 in mp:
        for mq1 in mq:
            j += 1
            if j % 1000000 == 0:
                print(j)
            ans = (mp1*t1*q+mq1*t2*p) % (p*q)
            if check(ans):
                return
    return


def check(m):
    try:
        a = long_to_bytes(m).decode('utf-8')
        if 'NCTF' in a:
            print(a)
            return True
        else:
            return False
    except:
        return False


def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = powmod(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li


if __name__ == '__main__':
    c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
    p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
    q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
    e = 0x1337
    cp = c % p
    cq = c % q

    mp = AMM_rth(cp, e, p)
    mq = AMM_rth(cq, e, q)

    rt1 = ALL_ROOT2(e, p)
    rt2 = ALL_ROOT2(e, q)

    amp = ALL_Solution(mp, p, rt1, cp, e)
    amq = ALL_Solution(mq, q, rt2, cq, e)

    calc(amp, amq, e, p, q)
#NCTF{T4k31ng_Ox1337_r00t_1s_n0t_th4t_34sy}

[NISACTF 2022]rrssaa2

task.py

e = 1801
p = 49610229352589717245227429186510630298995334563536199979797365135356894947505595171590737127611751124743823204969291853243936699113293137172961540731655194113111189561603261168928406442577570919901769348742992633428864861175880441682752947688509869668929473479230018031647980097396415380123118521799468844841
q = 21081926656979729045764441706195868361643779935106260715219328461497406780587336009385210898093496090213306812904410650499587043699660339207567766840318127296396962037273317168795761421233687815992929975284592353117739413561939283754964442896468496199833988666060155459156116345763999855126020972915904618043
c = 601596145172542477058917394071994325109856881057412872218601643742101914635753765731910337249806643258952637146341530783703613931109366648847232809553067941206928974141651198815184695746636818122414926015513095322872645068410957200062317958684872682628646759817233433643987003499153702624673493727886566639667597997520471371146056861227114668317633291934130573158877960548655006208725827943739971068608175370661619328559766977175575896437656636083179668805135271793023165492681941002853661303072959879197775224449456951125268328000206540965011249895216257583247180682482954741912101069920760903900864428405997751199
n = p * q

解题思路

AMM裸题，直接上板子。

exp.py

# -*- coding:utf8 -*-
from gmpy2 import *
from Crypto.Util.number import *
import random
import math

def onemod(e, q):
    p = random.randint(1, q-1)
    while(powmod(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = powmod(p, r**(t-1)*s, q)
    b = powmod(o, r*a-1, q)
    c = powmod(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = powmod(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (powmod(o, alp, q)*h)
    return result

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp


def calc(mp, mq, e, p, q):
    i = 1
    j = 1
    t1 = invert(q, p)
    t2 = invert(p, q)
    for mp1 in mp:
        for mq1 in mq:
            j += 1
            if j % 1000000 == 0:
                print(j)
            ans = (mp1*t1*q+mq1*t2*p) % (p*q)
            if check(ans):
                return
    return


def check(m):
    try:
        a = long_to_bytes(m).decode('utf-8')
        if 'NCTF' in a:
            print(a)
            return True
        else:
            return False
    except:
        return False


def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = powmod(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li


if __name__ == '__main__':
    e = 1801
    p = 49610229352589717245227429186510630298995334563536199979797365135356894947505595171590737127611751124743823204969291853243936699113293137172961540731655194113111189561603261168928406442577570919901769348742992633428864861175880441682752947688509869668929473479230018031647980097396415380123118521799468844841
    q = 21081926656979729045764441706195868361643779935106260715219328461497406780587336009385210898093496090213306812904410650499587043699660339207567766840318127296396962037273317168795761421233687815992929975284592353117739413561939283754964442896468496199833988666060155459156116345763999855126020972915904618043
    c = 601596145172542477058917394071994325109856881057412872218601643742101914635753765731910337249806643258952637146341530783703613931109366648847232809553067941206928974141651198815184695746636818122414926015513095322872645068410957200062317958684872682628646759817233433643987003499153702624673493727886566639667597997520471371146056861227114668317633291934130573158877960548655006208725827943739971068608175370661619328559766977175575896437656636083179668805135271793023165492681941002853661303072959879197775224449456951125268328000206540965011249895216257583247180682482954741912101069920760903900864428405997751199
    n = p * q
    cp = c % p
    cq = c % q

    mp = AMM_rth(cp, e, p)
    mq = AMM_rth(cq, e, q)

    rt1 = ALL_ROOT2(e, p)
    rt2 = ALL_ROOT2(e, q)

    amp = ALL_Solution(mp, p, rt1, cp, e)
    amq = ALL_Solution(mq, q, rt2, cq, e)

    calc(amp, amq, e, p, q)
#

算术推导

[长安杯 2021]checkin

task.py

from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(16)
n = p*q
m = bytes_to_long(flag)
for i in range(1,p-q):
    m = m*i%n
e = 1049
print(pow(2,e,n))
print(pow(m,e,n))
#4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
#3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270

解题思路

首先，这个题目没有给出我们n的值，我们观察这个c0=pow(2,e,n)。

我们可以知道kn=2^e-c0，这时候分解kn然后对kn进行分解，根据已知p,q的范围可以分解n。

分解n之后，我们可以解密求得m1。

我们进而观察m1的生成过程

这里我们需要根据威尔逊定理求解m

我们需要消去，这里的思路是，我们把从p-q到p的阶层定义为x。

那么

这时候我们求个逆元消去-1

exp.py

from gmpy2 import *
import binascii

p=170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231
q=34211
n = p*q
phi=(p-1)*(q-1)
e = 1049
c = 3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
d=invert(e,phi)
m=pow(c,d,n)

x=1
for i in range(p-q,p):
    x=x*i%p

m1=(m*x*invert(-1,p))%p

print(binascii.unhexlify(hex(m1)[2:]))
#flag{7h3_73rr1b13_7h1ng_15_7h47_7h3_p457_c4n'7_b3_70rn_0u7_by_175_r0075}

[GKCTF 2021]RRRRsa

task.py

from Crypto.Util.number import *
from gmpy2 import gcd

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

解题思路

很有意思的一道构造题目

两边同时模上得到

构造一下得到

这样我们求解得到，之后分解，求解RSA

对于

两边同时模上得到

这里构造可以分两步进行，首先配平的指数，再配平系数，最终得到

这样我们求解，之后分解，求解RSA

exp.py

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

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

q = gcd(pow(2021,202020)*hint1 - powmod(2020*(hint2 - 212121), 202020, n1), n1)
p = n1 // q
d = invert(0x10001, (p-1)*(q-1))
pp = powmod(c1, d, n1)

q = gcd(powmod(pow(2021,202020)*hint3, 212121, n2) - powmod(pow(2020,212121)*hint4, 202020, n2), n2)
p = n2 // q
d = invert(0x10001, (p-1)*(q-1))
qq = powmod(c2, d, n2)

d = invert(0x10001, (pp-1)*(qq-1))
print(long_to_bytes(powmod(c, d, pp*qq)))

#GKCTF{f64310b5-d5e6-45cb-ae69-c86600cdf8d8}

[黑盾杯 2020]Change

task.py

from flag import FLAG
from Crypto.Util.number import *
import gmpy2
import random

while True:
    p = int(gmpy2.next_prime(random.randint(10**399, 10**400-1)))
    q = int(str(p)[200:]+str(p)[:200])
    if gmpy2.is_prime(q):
        break

m = bytes_to_long(FLAG)
n = p*q
e = 65537
c = pow(m,e,n)

with open("enc","wb") as f:
    f.write(str(c))
    f.write("\n")
    f.write(str(n))
    
    
c=182812482972168423884795132699225934365072979206288632257180603530046820174392675977209758378734399146216742345585898385168866887000708558119959898992294085847474548306743585711154035585848291290988967352517174312220756638881837930962458861193652684492265539096477345065113556380573776423787885892688197584678128636231428194711357642971544417113415626331810909274966752557628893585198569815939514862013512237657828262360291726912615575646318630641527418369988268899879152029186728850816178597399494254385226049249357897840618728804680238123954207656671747782543031545429711152272581734051959578453680011676521727918037340906791388178004979453256050227967701258768070039292546964652071924183467364467145178290753361477912582242961929982420950384199259355122986865808523351306098081481072454093823090
n=438980397031315392229453908048509540832246041631432878509579665664182747463100230160823865621798053164989325086085003940181731721089701380743698761443812523024144817205902380903062054138730658451286904347536210833160924917347633148983052015550354913154312162901555870494273903714349869746793861874257201085777893961715468950661641778512110325457371446203379767458862059193946434683324578530163650541637261158037041205642428802942295011562277084687025213626698849526240663754073508102229066475773893638716845176469070938803298515155140240970836387785401085919369741520890271902332951669953411373633688944162470994856654604872287103746922041844065053274059990595496159866206551119361036237431289830985174384522423364811997241255005514248198447925396378192915553898993758660041223393168707380580012437

解题思路

参考文章

exp.py

个人感觉大佬这个代码变量有点乱，这里进一步解释一下。

from sympy.solvers import solve
from sympy.abc import h,l
from gmpy2 import *
from Crypto.Util.number import *

c = 182812482972168423884795132699225934365072979206288632257180603530046820174392675977209758378734399146216742345585898385168866887000708558119959898992294085847474548306743585711154035585848291290988967352517174312220756638881837930962458861193652684492265539096477345065113556380573776423787885892688197584678128636231428194711357642971544417113415626331810909274966752557628893585198569815939514862013512237657828262360291726912615575646318630641527418369988268899879152029186728850816178597399494254385226049249357897840618728804680238123954207656671747782543031545429711152272581734051959578453680011676521727918037340906791388178004979453256050227967701258768070039292546964652071924183467364467145178290753361477912582242961929982420950384199259355122986865808523351306098081481072454093823090
n = 438980397031315392229453908048509540832246041631432878509579665664182747463100230160823865621798053164989325086085003940181731721089701380743698761443812523024144817205902380903062054138730658451286904347536210833160924917347633148983052015550354913154312162901555870494273903714349869746793861874257201085777893961715468950661641778512110325457371446203379767458862059193946434683324578530163650541637261158037041205642428802942295011562277084687025213626698849526240663754073508102229066475773893638716845176469070938803298515155140240970836387785401085919369741520890271902332951669953411373633688944162470994856654604872287103746922041844065053274059990595496159866206551119361036237431289830985174384522423364811997241255005514248198447925396378192915553898993758660041223393168707380580012437
e = 0x10001

pqh = n // pow(10, 600) #这里是(ph*pl)h
pql = n % pow(10, 200) #这里是(ph*pl)l
pq = pqh*pow(10, 200) + pql ## pq指的其实就是ph*pl

n -= pow(10, 400)*pq + pq #这里先把n变形了一下

tmp = pow(10, 200)

s = solve([h*l-pq, tmp*h*h + tmp*l*l - n], [h, l])
for i in s:
    h,l = int(i[0]), int(i[1])
    p = h*tmp + l
    q = l*tmp + h
    if p > 0 and q > 0 and is_prime(p) and is_prime(q):
        break

d = invert(e, (p-1)*(q-1))

print(long_to_bytes(powmod(c, d, p*q)))

[MTCTF 2021]hamburgerRSA

task.py

from Crypto.Util.number import *

flag = open('flag.txt').read()
nbit = 64

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    PP = int(str(p) + str(p) + str(q) + str(q))
    QQ = int(str(q) + str(q) + str(p) + str(p))
    if isPrime(PP) and isPrime(QQ):
        break

n = PP * QQ
m = bytes_to_long(flag.encode())
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)

n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096

解题思路

参考文章

exp.py

N=177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193

low=str(N)[-19:]
high=str(N)[:19]

for i in ['']+[str(i) for i in range(10)]:
    n=int(high+i+low)
    f=factor(n)
    if len(f)==2:
        print(f)
from Crypto.Util.number import*
PP=978854293858047442997885429385804744291810985831791386711718109858317913867117
QQ=181098583179138671171810985831791386711797885429385804744299788542938580474429
phi=(PP-1)*(QQ-1)
n=PP*QQ
c=47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096
d=inverse(65537,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

后边几个题越来越费劲了。。。。

[第五空间 2021]signin

task.py

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

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x10001
x = (p ^ q) & ((1 << 400) - 1)

m = bytes_to_long(flag)

c = pow(m,e,n)

print("c = " + str(c))
print("e = " + str(e))
print("n = " + str(n))
print("x = " + str(x))

'''
c = 86415476382906786465939442398992406348852252355326334785583474583480585659663836032856765037225261433532613020730103955916772373674295180495452293421279237222544308971840820110279355118064931506637793547489441433938707518241461449059717326341918746156620038847745542794560335988858156929013492541794032580255
e = 65537
n = 166337085427556441543394334802135957169988266794453522153008810336368247289697353242192853337017363111987395194428553050681210209730724596529629525357502302165396675392000087988956194589350195512264427901330860811469484473725396354231555692283910488095918243519370430703255279433498479943391876108577325840381
x = 2509898544460604898497702985357222191225421344430742181152035006910161802193623236888758239071502008180363546424715261788
'''

解题思路

exp.py

from sage.all_cmdline import *
from Crypto.Util.number import *

c = 86415476382906786465939442398992406348852252355326334785583474583480585659663836032856765037225261433532613020730103955916772373674295180495452293421279237222544308971840820110279355118064931506637793547489441433938707518241461449059717326341918746156620038847745542794560335988858156929013492541794032580255
e = 65537
n = 166337085427556441543394334802135957169988266794453522153008810336368247289697353242192853337017363111987395194428553050681210209730724596529629525357502302165396675392000087988956194589350195512264427901330860811469484473725396354231555692283910488095918243519370430703255279433498479943391876108577325840381
x = 2509898544460604898497702985357222191225421344430742181152035006910161802193623236888758239071502008180363546424715261788

plist = [0]
qlist = [0]

'''
    0^0 = 0
    0^1 = 1
    1^0 = 1
    1^1 = 0
'''

mask = 0
for i in range(400):
    tmpp, tmpq = [],[]
    for p,q in [(0,0),(0,1),(1,0),(1,1)]:
        if p^q == ((x>>mask)&1):
            for j in range(len(plist)):
                if ((p<<mask) + plist[j]) * ((q<<mask) + qlist[j]) % (2<<mask) == n % (2<<mask):
                    tmpp.append((p<<mask) + plist[j])
                    tmpq.append((q<<mask) + qlist[j])
    plist,qlist = tmpp, tmpq
    mask += 1

for pbar in plist:
    PR = PolynomialRing(Zmod(n), 'x')
    x = PR('x')
    ZmodN = Zmod(n)
    f = x*ZmodN(2**400) + pbar
    f = f.monic()
    r = f.small_roots(X=2**112, beta=0.4)
    if r:
        p = int(pbar+r[0]* 2**400)
        if n%p == 0:
            break

q = n // p
d = inverse_mod(e, (p-1)*(q-1))
print(long_to_bytes(power_mod(c, d, n)))

CopperSmith

[CISCN 2021初赛]rsa

task.py

from flag import text,flag
import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime

assert md5.new(text).hexdigest() == flag[6:-1]

msg1 = text[:xx]
msg2 = text[xx:yy]
msg3 = text[yy:]

msg1 = bytes_to_long(msg1)
msg2 = bytes_to_long(msg2)
msg3 = bytes_to_long(msg3)

p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)

p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)

p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200

19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
(3, 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009L)
54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
(17, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)
(65537, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)
59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
(65537, 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147L)
7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902

解题思路

不禁感慨一下，几年前的国赛，考察的题目还是那么直白。

这里把flag分成了三段，第一段是一个低加密指数，第二段是个共模攻击，第三段是p高位泄露，我们逐段求解就可以。

exp.py

第一段

from gmpy2 import *
import binascii
c=19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
e=3
n=123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
k=0
while True:
    res=iroot(k*n+c,e)
    if(res[1]==True):
        print(binascii.unhexlify(hex(res[0])[2:]))
        break
    k+=1
    
#b' \nO wild West Wind, thou breath of Autum'

感觉可以直接求第三段。。。。

第二段

import gmpy2
import binascii

n=gmpy2.mpz(111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977)

c1=gmpy2.mpz(54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610)

c2=gmpy2.mpz(91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950)

e1=17

e2=65537

s=gmpy2.gcdext(e1,e2)

m1=pow(c1,s[1],n)

m2=pow(c2,s[2],n)

m=(m1*m2)%n

print(binascii.unhexlify(hex(m)[2:]))

#b"n's being,\nThou, from whose unseen presence the leaves dead\nAre driven, like ghosts from an enchanter fleeing,\nYellow, a"

第三段

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

n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
c = 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646

p = p<<200

PR.<x> = PolynomialRing(Zmod(n))

f = p+x
res = f.small_roots(X=2^200, beta=0.4)

p = int(res[0]) + p
q = n // p
print(q)
d = inverse_mod(65537, (p-1)*(q-1))
m = power_mod(c, d, n)
print(long_to_bytes(m))
#b'nd black, and pale, and hectic red,\nPestilence-stricken multitudes: O thou,\nWho chariotest to their dark wintry bed\n'

贴一个好用的脚本

n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p4 = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
e = 65537
pbits = 512
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
    p = p4+int(roots[0])
    print("n: "+str(n))
    print("p: "+str(p))
    print("q: "+str(n//p))

[鹏城杯 2022]easy_rsa

task.py

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'}

解题思路

第一段是个e,phi不互素，第二段是p部分泄露

解释一下第三段，这里c和n的公约数就是p，这样就能封禁n然后求解RSA

exp.py

第一段

import gmpy2
import binascii

p=0xbb602e402b68a5cfcc5cfcc63cc82e362e98cb7043817e3421599a4bb8755777c362813742852dad4fec7ec33f1faec04926f0c253f56ab4c4dde6d71627fbc9ef42425b70e5ecd55314e744aa66653103b7d1ba86d1e0e21920a0bfe7d598bd09c3c377a3268928b953005450857c6cfea5bfdd7c16305baed0f0a31ad688bd
q=0xbb8d1ea24a3462ae6ec28e79f96a95770d726144afc95ffffa19c7c3a3786a6acc3309820ba7b1a28a4f111082e69e558b27405613e115139b38e799c723ab7fdd7be14b330b118ae60e3b44483a4c94a556e810ab94bbb102286d0100d7c20e7494e20e0c1030e016603bd2a06c1f6e92998ab68e2d420faf47f3ee687fb6d1
e=0x292
c=0x27455f081e4858790c6503580dad3302ae359c9fb46dc601eee98f05142128404e95377324720adbbdebf428549008bcd1b670f6749592a171b30316ab707004b9999f3b80de32843afdfd30505b1f4166a03cee9fc48902b74b6e850cfd268e6917c5d84e64f7e7cd0e4a30bfe5903fb5d821d27fdc817d9c4536a8e7aea55af266abcae857a8ffff2f741901baba1b44091a137c69c471c123ab0b80e250e055959c468e6e37c005105ecd7c8b48c659024e5e251df3eeff5da7b3d561cd98150da3575a16bee5f2524d2795fd4879487018345c1e96efc085ed45fb5f02c027aee5bca3aad0eb3e23376c0cd18b02fb05a1ff8fb1af0a3ce4bb671599894e
phi=(p-1)*(q-1)
d=gmpy2.invert(e//2,phi)
m=pow(c,d,p*q)
m=gmpy2.iroot(m,2)
print(binascii.unhexlify(hex(m[0])[2:]))

#PCL{16745c3b

第二段

n = 0x841a5a012c104e600eca17b451d5fd37c063ad347707a2e88f36a07e9ad4687302790466e99f35b11580cbe8b0a212e6709686c464a6393c5895b1f97885f23ea12d2069eb6dc3cb4199fb8c6e80a4a94561c6c3499c3c02d9dc9cf216c0f44dc91701a6d9ec89981f261a139500420a51014492f1da588a26e761439dd5739b32540ca6dc1ec3b035043bc535304a06ccb489f72fcd1aa856e1cffe195039176937f9a16bd19030d1e00095f1fd977cf4f23e47b55650ca4712d1eb089d92df032e5180d05311c938a44decc6070cd01af4c6144cdab2526e5cb919a1828bec6a4f3332bf1fa4f1c9d3516fbb158fd4fbcf8b0e67eff944efa97f5b24f9aa65
p4 = 0xa9cb9e2eb43f17ad6734356db18ad744600d0c19449fc62b25db7291f24c480217d60a7f87252d890b97a38cc6943740ac344233446eea4084c1ba7ea5b7cf2399d42650b2a3f0302bab81295abfd7cacf248de62d3c63482c5ea8ab6b25cdbebc83eae855c1d07a8cf0408c2b721e43c4ac53262bf9aaf7a
e = 65537
pbits = 1024
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
    p = p4+int(roots[0])
    print("n: "+str(n))
    print("p: "+str(p))
    print("q: "+str(n//p))
    
n: 16676450704117406984592025063850900053789376003399190311720188158488886691280209555175830133393912861925677252847063707907536810656295135435030437243734401026617255634459734936796594942776689510859440558194110373664718925429745882204691083430639740384638701716026693412425164473472213091425769296148093070149231932577216369178892250824397978684233626964889041865056363294707998482306347934376164838745527260555009869036640749099896227929806275810818204261768115257353261726117067560402676352095817968864707164594118005516052080082446065707283304316695188972531988085450543617829295860842249432419321698844088907442789
p: 119234372387564173916926418564504307771905987823894721284221707768770334474240277144999791051191061404002537779694672314673997030282474914206610847346023297970473719280866108677835517943804329212840618914863288766846702119011361533150365876285203805100986025166317939702179911918098037294325448226481818486521
q: 139862779248852876780236838155351435339041528333485708458669785004897778564234874018135441729896017420539905517964705602836874055417791439544162777504181482765029478481701166935117795286988835104239238153206137155845327225155932803904032184502243017645538314995056944419185855910939481260886933456330514972109
import gmpy2
import binascii

n=16676450704117406984592025063850900053789376003399190311720188158488886691280209555175830133393912861925677252847063707907536810656295135435030437243734401026617255634459734936796594942776689510859440558194110373664718925429745882204691083430639740384638701716026693412425164473472213091425769296148093070149231932577216369178892250824397978684233626964889041865056363294707998482306347934376164838745527260555009869036640749099896227929806275810818204261768115257353261726117067560402676352095817968864707164594118005516052080082446065707283304316695188972531988085450543617829295860842249432419321698844088907442789
p=119234372387564173916926418564504307771905987823894721284221707768770334474240277144999791051191061404002537779694672314673997030282474914206610847346023297970473719280866108677835517943804329212840618914863288766846702119011361533150365876285203805100986025166317939702179911918098037294325448226481818486521
q=139862779248852876780236838155351435339041528333485708458669785004897778564234874018135441729896017420539905517964705602836874055417791439544162777504181482765029478481701166935117795286988835104239238153206137155845327225155932803904032184502243017645538314995056944419185855910939481260886933456330514972109
phi=(p-1)*(q-1)
e=65537
c=0x3a80caebcee814e74a9d3d81b08b1130bed6edde2c0161799e1116ab837424fbc1a234b9765edfc47a9d634e1868105d4458c9b9a0d399b870adbaa2337ac62940ade08daa8a7492cdedf854d4d3a05705db3651211a1ec623a10bd60596e891ccc7b9364fbf2e306404aa2392f5598694dec0b8f7efc66e94e3f8a6f372d833941a2235ebf2fc77c163abcac274836380045b63cc9904d9b13c0935040eda6462b99dd01e8230fdfe2871124306e7bca5b356d16796351db37ec4e574137c926a4e07a2bfe76b9cbbfa4b5b010d678804df3e2f23b4ec42b8c8433fa4811bf1dc231855bea4225683529fad54a9b539fe824931b4fdafab67034e57338217f
d=gmpy2.invert(e,phi)
m=pow(c,d,p*q)
print(binascii.unhexlify(hex(m)[2:]))

#b'0c134c83b74f'

第三段

import gmpy2
import binascii

n=0xc2b17c86a8950f6dafe0a633890e4271cfb20c5ffda2d6b3d035afa655ed05ec16c67b18832ed887f2cea83056af079cc75c2ce43c90cce3ed02c2e07d256f240344f1734adeee6dc2b3b4bbf6dcfc68518d0a74e3e66f1865db95ef4204457e6471903c2321ac97f3b8e3d8d935896e9fc9145a30a3e24e7c320490a9944c1e94d301c8388445532699e6189f4aa6a86f67f1d9b8fb0de4225e005bd27594cd33e36622b2cd8eb2781f0c24d33267d9f29309158942b681aab81f39d1b4a73bd17431b46a89a0e4c2c58b1e24e850355c63b72392600d3fff7a16f6ef80ea515709da3ef1d28782882b0dd2f76bf609590db31979c5d1fd03f75d9d8f1c5069
c=0x1bd2a47a5d275ba6356e1e2bd10d6c870693be540e9318c746e807a7672f3a75cc63841170126d7dba52d7f6f9cf0f8dce9705fc1785cc670b2658b05d4b24d8918f95594844bfa920c8ffe73160c2c313b3fdbc4541ec19828165e34afa7d05271cc6fd59d08138b88c11677e6ac3b39cff525dcb19694b0388d895f53805a5e5bd8cfb947080e4855aaf83ebd85a397526f7d76d26031386900cb44a2e4bd121412bcee7a6c1e9af411e234f130e68a428596265d3ec647e50f65cb81393f4bd38389a2b9010fd715582506b9054dc235aced50757462b77a5606f116853af0c1ea3c7cf0d304f885d86081f8bac8b67b0625122f75448c5b6eb8f1cc8a0df
p=gmpy2.gcd(c,n)
q=n//p
phi=(p-1)*(q-1)
e=65537
d=gmpy2.invert(e,phi)
M=pow(c,d,p*q)
m=M//(2022*1011*p)
print(binascii.unhexlify(hex(m)[2:]))

#b'977260aae9b5}'

未完待续。。。。