[CRYPTOCTF] DoRSA

题目：


from Crypto.Util.number import *
from math import gcd
from flag import FLAG
#获取e, n_1, n_2
def keygen(nbit, dbit):
    assert 2*dbit < nbit
    while True:
        u, v = getRandomNBitInteger(dbit), getRandomNBitInteger(nbit // 2 - dbit)
        p = u * v + 1
        if isPrime(p):
            while True:
                x, y = getRandomNBitInteger(dbit), getRandomNBitInteger(nbit // 2 - dbit)
                q = u * y + 1
                r = x * y + 1
                if isPrime(q) and isPrime(r):
                    while True:
                        e = getRandomNBitInteger(dbit)
                        if gcd(e, u * v * x * y) == 1:
                            phi = (p - 1) * (r - 1)
                            d = inverse(e, phi)
                            k = (e * d - 1) // phi
                            s = k * v + 1
                            if isPrime(s):
                                n_1, n_2 = p * r, q * s
                                return (e, n_1, n_2)

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

nbit, dbit = 1024, 256

e, n_1, n_2 = keygen(nbit, dbit)#获取e,n1,n2

FLAG = int(FLAG.encode("utf-8").hex(), 16)

c_1 = encrypt(FLAG, (e, n_1))
c_2 = encrypt(FLAG, (e, n_2))

print('e =', e)
print('n_1 =', n_1)
print('n_2 =', n_2)

print('enc_1 =', c_1)
print('enc_2 =', c_2)

'''
e = 93546309251892226642049894791252717018125687269405277037147228107955818581561
n_1 = 36029694445217181240393229507657783589129565545215936055029374536597763899498239088343814109348783168014524786101104703066635008905663623795923908443470553241615761261684865762093341375627893251064284854550683090289244326428531870185742069661263695374185944997371146406463061296320874619629222702687248540071
n_2 = 29134539279166202870481433991757912690660276008269248696385264141132377632327390980628416297352239920763325399042209616477793917805265376055304289306413455729727703925501462290572634062308443398552450358737592917313872419229567573520052505381346160569747085965505651160232449527272950276802013654376796886259
enc_1 = 4813040476692112428960203236505134262932847510883271236506625270058300562795805807782456070685691385308836073520689109428865518252680199235110968732898751775587988437458034082901889466177544997152415874520654011643506344411457385571604433702808353149867689652828145581610443408094349456455069225005453663702
enc_2 = 2343495138227787186038297737188675404905958193034177306901338927852369293111504476511643406288086128052687530514221084370875813121224208277081997620232397406702129186720714924945365815390097094777447898550641598266559194167236350546060073098778187884380074317656022294673766005856076112637129916520217379601
'''

题解：

加密：p=u∗v+1q=u∗y+1r=x∗y+1s=k∗v+1加密：\\ p=u*v+1\qquad q=u*y+1\\ r=x*y+1\qquad s=k*v+1\\

n1=p∗rn2=q∗sphi1=uvxyphi2=uykvc1=flage(modn1)c2=flage(modn2)n1=p*r\\ n2=q*s\\ phi1=uvxy\qquad phi2=uykv\\ c1=flag^e(mod\quad n1)\\ c2=flag^e(mod\quad n2)\\

相较于u∗v、x∗y、u∗y、k∗v来说太小，所以n1n2≈xk对n1n2展开，xk是他的渐进分数，求出x,k\\相较于u*v、x*y、u*y、k*v来说太小，所以\frac{n1}{n2}\approx \frac{x}{k}\\对\frac{n1}{n2}展开，\frac{x}{k}是他的渐进分数，求出x,k\\

又因为k=(e∗d−1)//phiphi=uvxy{k∗phi+1≡0(mode)(1)phi≡0(modx)(2)又因为 k = (e * d - 1) // phi \qquad phi=uvxy\\ \begin{cases} k*phi+1\equiv 0(mod\quad e) \qquad \qquad(1)\\ phi\equiv 0(mod\quad x)\qquad \qquad \qquad \quad(2)\\ \end{cases}\\

对（1）变形两边同乘k−1(k在模e下乘法逆元)，得到phi≡k−1(mode)利用中国剩余定理求模ex下的phi由于phi是在ex下的很小，真实的phi与n差不多大，扩大在模ex下的phi,对phi进行爆破求出phi，进而求出d，简单rsa求出flag对（1）变形两边同乘k^{-1}(k在模e下乘法逆元)，得到phi\equiv k^{-1}(mod\quad e)\\ 利用中国剩余定理求模ex下的phi\\由于phi是在ex下的很小，真实的phi与n差不多大，扩大在模ex下的phi, \\对phi进行爆破求出phi，进而求出d，简单rsa求出flag

wp:

import gmpy2
from gmpy2 import mpz
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long, isPrime, getPrime, GCD
from sympy import Integer, continued_fraction
from tqdm import tqdm
from pwn import *

def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0#分子
    denominator = 1#分母
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator
def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf
def Crt(a1,a2,m1,m2):
    M=m1*m2
    M1=m2
    M2=m1
    M11=gmpy2.invert(mpz(M1),mpz(m1))
    M22=gmpy2.invert(mpz(M2),mpz(m2))
    return (a1*M1*M11%M+a2*M2*M22%M)%M

e = 93546309251892226642049894791252717018125687269405277037147228107955818581561
n_1 = 36029694445217181240393229507657783589129565545215936055029374536597763899498239088343814109348783168014524786101104703066635008905663623795923908443470553241615761261684865762093341375627893251064284854550683090289244326428531870185742069661263695374185944997371146406463061296320874619629222702687248540071
n_2 = 29134539279166202870481433991757912690660276008269248696385264141132377632327390980628416297352239920763325399042209616477793917805265376055304289306413455729727703925501462290572634062308443398552450358737592917313872419229567573520052505381346160569747085965505651160232449527272950276802013654376796886259
enc_1 = 4813040476692112428960203236505134262932847510883271236506625270058300562795805807782456070685691385308836073520689109428865518252680199235110968732898751775587988437458034082901889466177544997152415874520654011643506344411457385571604433702808353149867689652828145581610443408094349456455069225005453663702
enc_2 = 2343495138227787186038297737188675404905958193034177306901338927852369293111504476511643406288086128052687530514221084370875813121224208277081997620232397406702129186720714924945365815390097094777447898550641598266559194167236350546060073098778187884380074317656022294673766005856076112637129916520217379601

c = continued_fraction(Integer(n_2) / Integer(n_1))#分数列表
c=getGradualFra(c)

for i in range(1, 150):
    k = c[i][1]#numerator(i)
    x = c[i][0]

    if GCD(e, k) != 1:
        continue
    res = gmpy2.invert(mpz(e-k), mpz(e))
    cc = Crt(res, 0, e, x)
    md = e * x // GCD(e, x)
   # break
    #print(cc[1])
    st = cc + (n_1 // md) * md - 100 * md

    #print(st)
    for j in range(200):
        if GCD(e, st) != 1:
            st += md
            continue
        d_1 = gmpy2.invert(mpz(e), mpz(st))
        #print(d_1)
        flag = pow(enc_1, d_1, n_1)
       # print(flag)
        flag = long_to_bytes(flag)
        if b"CCTF" in flag:
            print(flag)
        st += md
##CCTF{__Lattice-Based_atT4cK_on_RSA_V4R1aN75!!!}

[NUSTCTF 2022] ezRSA

题目

from Crypto.Util.number import getPrime, bytes_to_long
from sympy import nextprime
from secret import flag

p1 = getPrime(2048)
q1 = getPrime(600)
p2 = nextprime(p1 + getPrime(600))
q2 = getPrime(600)

e = 0x10001

N1 = p1 * p1 * q1
N2 = p2 * p2 * q2

print("N1 =", N1)
print("N2 =", N2)

flag1 = bytes_to_long(flag[:len(flag) // 2])
flag2 = bytes_to_long(flag[len(flag) // 2:])

cipher1 = pow(flag1, e, N1)
cipher2 = pow(flag2, e, N2)

print("cipher1 =", cipher1)
print("cipher2 =", cipher2)

# N1 = 3289746385054724131365721020639496300945479666755005407239362220435929471663971559131973068094267242759747682915202602265269024546168034070348080432976135403371083936361236868186476392365554734516698695915807318328547349333450125215426536032220967810893464208090339137598724593917266763998037725309967496052803477931961681761135080900299333158097292389350335121611775110493009954911832572636099153354952171029044016319029661601727739828271424563980850243898202779669776639104067478441675153857040164775196713586656673764171877161326751846236980454659960530174960321852298270258312146241360929350418220172331956030775384681767932014061291168620965347842124549316096247113770711834360498936747471888481237404034471246978342020816271785925362208839937490625070051801028223342083281773366267363149243726101075926327550718757413133631119649782144511080448476370411156544146278468602957599519708203511203435394861053372096309444985117323976240925612725880016576029876493825989064619463226166401883310383733295274652092903872304933657343307118616812213637906513530016004460475073291823916649597185291734261926576108675712303422832460766980003743958182130150811173621769221262799069912858162405156365709344847558244669016188305691537672753134766406649385330682157984720023661279153645005631349488537261911860571171672813544726579872640486753312665928030263533489558821140031095492111373847722540582741061909831250761476687
# N2 = 2292263744571677490370198515319050673022350367021940229132415885393214523108231545410288799524823682686607005535541881885794949322622162858593875970155712564868530006799557973311000615581843236548539733075504282834631939435260232339940338468890310925405870533590386398071667718507612723307978025099102004513584485422609923041107028535400446355591432930994813185411831860201820145983435091523773691560011687528125877698679841462745728326159525372061320952493949821495222248383893254880735838359120880431072244214361010867779059178282739912365087421904643477215607290679708352033106358356290644004853543174075195107627794359272018100648168661860452919746052205404895413998960327066611970768862624073581670828267510841602161728589913841163473811894218339948715205301321356774629578043062238684103507006315521103670400509643518854842374093509082331379305822049420033746124157212615698602544129110388591266923967512746018551734391176602223771675279723873630468099034521371667295520830509224068753383327420799595674898227670628881521095495898465890256628288779785408613688721508315026743250146090703141554141208186588758560579281631449476819201739513661261100456398775274335050320480934180632543242116316388750179657345282978014879818574111951053767465935985181195234991374892341383106554664200986728169474150302232887629401491764905429656980077385228539526682528035467486946883267941678859904770170914569949948781798383
# cipher1 = 758346536265430423952822486066685295768780904671958564513706915003627653309986327906604310025557676880130150973194443591153899441660221125085406078577489990064034099758898680250346992154199616929381594288918352701155172644054184374384778201304104144436102359709180739955762513436889301607686277088230852661148556440251553059814853050711377102806879036793210874472411397851504602916797481132018776755416068149801594219844674499351889997208649442043923826505239289470153001663639688739092310857881616013610569511757767780350165048282465256454770748877584119349207769812826840607665168961680724232789109312681055375411182858820698025923104994832566402422884359019460479145829812817446509615552819113705033128233093081687704471007797878802184788802106948491309583791881593217988561342681568377126606055476508381741342859362339824940846336741346126512500348868154174463810299929429409815515908136711497765026252563374327541491024303290989175383501994515761077240391195396083766760326143468930305986070405962303571534654392917816088220966950447926277802817335097304148972911332832248113849846752219065263639980629213197260594242031101803801865240157341309018859709063723920616432168289755151080828619642932516426139982777613526680161145782566883722320235485389839997229666979487071672091138823743231576011381309205283462045931376953038071401274899229258796970036565931730655471667545203734032609058125128632555918726761
# cipher2 = 2281163375114595112593683220870779643793045914138930809669934728297504812745368657964524831965320392164027435706363680996214578180045485041532876049868691323690200562004954003143194397255512951717400899604307009993030792644670830602941543918898535970779253703220162651022293286208338299826844988619345629892007235258389532666376623514170628541968337364745860334903754371727427376399211310359996960626733244649671665175464666807399652951289553389561033148215888827057495743582318390507639029065358587166019110069479019692411629179363742708597061223484237748437654542910240974030049076975739481960903748359283570086571360417832776823264202688497555419017227144724790205424467059280453940666789219388347170532415234759731375390229140544207931837445265744016932142504371200121886182154284965893665022781184321216382767703694597553489507371271887593799060901908513758134472760311502510753557029741715193386673389466599068008750012915225818076301655694045130332321314233483042503950958442501013310465239137942770667655164906193219286435485452257047415797293472629254376873962168035382262951696816840667369861437088409243033239980128747965838367176274122593955221422537124546203553941387134587884149412499272660959871746858550851448840531698152805786123875121854564754397297726121984646669253047201515221545545683432754661774694401343486893270795112334494874407955432598253951220055000392855162417030953645428808146502304

题解：

N1N2=p1∗p1∗q1p2∗p2∗q2≈q1q2q1q2是N1N2的连续分数，对N1N2进行wiener攻击，求解出q1,q2由于N1=p1∗p1∗q1，现在q1已知，求出p1,同理求出p2对明文前半部分加密  cipher1=pow(flag1,e,N1))简单RSA，已知c,e,n,p,q,求出flag1,同理求出flag2flag1+flag2就是flag啦\frac{N1}{N2}=\frac{p1*p1*q1}{p2*p2*q2}\approx \frac{q1}{q2}\\ \frac{q1}{q2}是\frac{N1}{N2}的连续分数，对\frac{N1}{N2}进行wiener攻击，求解出q1,q2\\由于N1=p1*p1*q1，现在q1已知，求出p1,同理求出p2\\对明文前半部分加密\ \ cipher1 = pow(flag1, e, N1))\\简单RSA，已知c,e,n,p,q,求出flag1,同理求出flag2\\flag1+flag2就是flag啦

wp

import gmpy2
import libnum
from Crypto.Util.number import long_to_bytes

N1 = 3289746385054724131365721020639496300945479666755005407239362220435929471663971559131973068094267242759747682915202602265269024546168034070348080432976135403371083936361236868186476392365554734516698695915807318328547349333450125215426536032220967810893464208090339137598724593917266763998037725309967496052803477931961681761135080900299333158097292389350335121611775110493009954911832572636099153354952171029044016319029661601727739828271424563980850243898202779669776639104067478441675153857040164775196713586656673764171877161326751846236980454659960530174960321852298270258312146241360929350418220172331956030775384681767932014061291168620965347842124549316096247113770711834360498936747471888481237404034471246978342020816271785925362208839937490625070051801028223342083281773366267363149243726101075926327550718757413133631119649782144511080448476370411156544146278468602957599519708203511203435394861053372096309444985117323976240925612725880016576029876493825989064619463226166401883310383733295274652092903872304933657343307118616812213637906513530016004460475073291823916649597185291734261926576108675712303422832460766980003743958182130150811173621769221262799069912858162405156365709344847558244669016188305691537672753134766406649385330682157984720023661279153645005631349488537261911860571171672813544726579872640486753312665928030263533489558821140031095492111373847722540582741061909831250761476687
N2 = 2292263744571677490370198515319050673022350367021940229132415885393214523108231545410288799524823682686607005535541881885794949322622162858593875970155712564868530006799557973311000615581843236548539733075504282834631939435260232339940338468890310925405870533590386398071667718507612723307978025099102004513584485422609923041107028535400446355591432930994813185411831860201820145983435091523773691560011687528125877698679841462745728326159525372061320952493949821495222248383893254880735838359120880431072244214361010867779059178282739912365087421904643477215607290679708352033106358356290644004853543174075195107627794359272018100648168661860452919746052205404895413998960327066611970768862624073581670828267510841602161728589913841163473811894218339948715205301321356774629578043062238684103507006315521103670400509643518854842374093509082331379305822049420033746124157212615698602544129110388591266923967512746018551734391176602223771675279723873630468099034521371667295520830509224068753383327420799595674898227670628881521095495898465890256628288779785408613688721508315026743250146090703141554141208186588758560579281631449476819201739513661261100456398775274335050320480934180632543242116316388750179657345282978014879818574111951053767465935985181195234991374892341383106554664200986728169474150302232887629401491764905429656980077385228539526682528035467486946883267941678859904770170914569949948781798383
c1 = 758346536265430423952822486066685295768780904671958564513706915003627653309986327906604310025557676880130150973194443591153899441660221125085406078577489990064034099758898680250346992154199616929381594288918352701155172644054184374384778201304104144436102359709180739955762513436889301607686277088230852661148556440251553059814853050711377102806879036793210874472411397851504602916797481132018776755416068149801594219844674499351889997208649442043923826505239289470153001663639688739092310857881616013610569511757767780350165048282465256454770748877584119349207769812826840607665168961680724232789109312681055375411182858820698025923104994832566402422884359019460479145829812817446509615552819113705033128233093081687704471007797878802184788802106948491309583791881593217988561342681568377126606055476508381741342859362339824940846336741346126512500348868154174463810299929429409815515908136711497765026252563374327541491024303290989175383501994515761077240391195396083766760326143468930305986070405962303571534654392917816088220966950447926277802817335097304148972911332832248113849846752219065263639980629213197260594242031101803801865240157341309018859709063723920616432168289755151080828619642932516426139982777613526680161145782566883722320235485389839997229666979487071672091138823743231576011381309205283462045931376953038071401274899229258796970036565931730655471667545203734032609058125128632555918726761
c2 = 2281163375114595112593683220870779643793045914138930809669934728297504812745368657964524831965320392164027435706363680996214578180045485041532876049868691323690200562004954003143194397255512951717400899604307009993030792644670830602941543918898535970779253703220162651022293286208338299826844988619345629892007235258389532666376623514170628541968337364745860334903754371727427376399211310359996960626733244649671665175464666807399652951289553389561033148215888827057495743582318390507639029065358587166019110069479019692411629179363742708597061223484237748437654542910240974030049076975739481960903748359283570086571360417832776823264202688497555419017227144724790205424467059280453940666789219388347170532415234759731375390229140544207931837445265744016932142504371200121886182154284965893665022781184321216382767703694597553489507371271887593799060901908513758134472760311502510753557029741715193386673389466599068008750012915225818076301655694045130332321314233483042503950958442501013310465239137942770667655164906193219286435485452257047415797293472629254376873962168035382262951696816840667369861437088409243033239980128747965838367176274122593955221422537124546203553941387134587884149412499272660959871746858550851448840531698152805786123875121854564754397297726121984646669253047201515221545545683432754661774694401343486893270795112334494874407955432598253951220055000392855162417030953645428808146502304
e = 0x10001

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    #辗转相除法
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf
def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0#分子
    denominator = 1#分母
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator

def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf

def wienerAttack(n1, n2):
    cf = continuedFra(n1, n2)#获得连分数列表
    for (p2, p1) in getGradualFra(cf):#所有渐进分数
        if p1 == 0:
            continue
        if n1 % p1 == 0 and p1 != 1:
            return p1, p2

q1,q2=wienerAttack(N1, N2)
p1,f1=gmpy2.iroot(N1 // q1, 2)
p2,f2=gmpy2.iroot(N2 // q2, 2)
#print(p1,f1)
#print(p2,f2)

if f1==1 and f2==1:
    phi1=p1*(p1-1)*(q1-1)
    phi2=p2*(p2-1)*(q2-1)
    d1=gmpy2.invert(e,phi1)
    d2=gmpy2.invert(e,phi2)
    tflag1=long_to_bytes(pow(c1, d1, N1))
    tflag2=long_to_bytes(pow(c2, d2, N2))
    print(tflag2)
    print(tflag1)
    flag=b''
    flag=tflag1+tflag2
    print(flag)
else:
    print("wrong")

#b'flag{6575266e9fc6411275185799ec9477ee}'

[强网杯 2022]factor

题目

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

def gen1():##attack 3
	r = 2
	while True:
		p2 = getPrime(1792)
		p1 = getPrime(1792)

		q1 = getPrime(512)
		q2 = getPrime(512)

		if (abs(p1-p2) < (p1//(2*r*q1*q2))):
			n1, n2 = (p1**r)*q1, (p2**r)*q2
			break

	phi1 = (p1**(r-1))*(p1-1)*(q1-1)
	phi2 = (p2**(r-1))*(p2-1)*(q2-1)
	while True:
		e1 = randint(5, (p1-1)*(q1-1))
		e2 = randint(5, (p2-1)*(q2-1))
		if gcd(e1, e2) == 1 and gcd(phi1, e1) == 1 and gcd(phi2, e2) == 1:
			break
	return n11, n12, e11, e12


def gen2():##attack 2
	r = 7
	while True:
		p = getPrime(512)
		q =	getPrime(512)
		N = (p**r)*q
		if len(bin(N)) == 4096:
			break

	idx = (r*(r-1)) / ((r+1)*(r+1))
	delta = int(pow(mpz(N), idx))##将 N 的值提高到指数 idx 次方，然后将结果转换为一个整数并存储在变量 delta 中。mpz()起保护作用
	phi = (p**(r-1))*(p-1)*(q-1)

	while True:
		d1 = getPrime(int(2048*idx)//2)
		d2 = getPrime(int(2048*idx)//2)
		if abs(d1-d2) < delta:
			m1 = invert(d1, phi)
			m2 = invert(d2, phi)
			break

	e2 = 0x10001
	return n2, e2, m1, m2

def gen3():#attack1
	r = 7
	while True:
		p = getPrime(512)
		q =	getPrime(512)
		N = (p**r)*q
		phi = (p**(r-1))*(p-1)*(q-1)

		if len(bin(N))-2 == 4096:
			break

	idx = (r*(r-1)) / ((r+1)*(r+1))
	delta = int(pow(mpz(N), idx))

	while True:
		b = getRandomNBitInteger(int(2048*idx)//2)
		a = getRandomNBitInteger(int(2048*idx)//2)
		if a*b < delta:
			e = invert(a, phi)*b
			return n3, e3, b


n11, n12, e11, e12 = gen1()
print(f"n11={n11}\nn12={n12}\ne11={e11}\ne12={e12}\n")
n2, e2, m1, m2 = gen2()#连分数攻击，求解m1,m2
print(f"n2={n2}\ne2={e2}\n")
n3, e3, b = gen3()
print(f"n3={n3}\ne3={e3}\n")

m3 = bytes_to_long(flag)
c11 = powmod(m1, e11, n11)
c12 = powmod(m2, e12, n12)
c2 = powmod(b, e2, n2)
c3 = powmod(m3, e3, n3)
print(f"c11={c11}\nc12={c12}\nc2={c2}\nc3={c3}\n")
'''
n11=801049932940568005269978912396585741498810389425615966036828877784238116634177290247194019425111606811005728521368879065336038221361037062407029836155148874719789714345603547779284558101833801155509762818376470874215789574939002212274399950433269775325144015468620263028557804618774240232988157961712628677901130814703917513004114547234375629747176834581166306552311075522669403347828095831520693563291249869832390698646691647204371133362254846234990175138047928703289833460734235302093916147489509206061923877623300596194317059884824322527532662470348274079800781120104946546063500763852622187404608639542858285661288293918912184354236687975919510300221932074135531028314170475917110204254042336116619335841213418990605590620842511615815443114612333881430920769002933370887494558640833005339906706603497809846863863967391543647049224309556936909768179259581851520214669904560467640473144481633920438487615788689262961741053146610554997224861331949716721056553499531186695425439163222802917813140266513735841447717418846360096652592844940362932171019143434080184728093326143821165097895058935372215708948088248596585127475770021962501262915274497478428868130455122612016408381607561200802267038869516896665387576895570245272035575637
n12=635401970340205725139325006504978344512744926958688031423448003992072769931808217486709574151492230879374574313457662436423263437792389711379687512056391117410807565492548718691166183372633151644917135272259770997096195518489056319350258673723095417922153182423913759272893696867426193704479752772511081457729513843682588951499551132432923147997238597538055902932123792252593514225328196541483451747314048080824405530742533473914329294346486691684904100406972073037050089861816604505650042953778360621934380815999541183067585498606053857125775979915077329566722531830089714823979965934190338538564188253271016367299890015449611141166780048763403252309160517164569110740561584100839212138661881615351382946813818078899882595313362934594951895560189003438775450675343590147821186953526262224973333962454561275321925151619178204499342339749637758100126893330994252902926509705617882239610380420830791088907378397226817514095468815228186716220057075095711894070032344613244803934541318573847029365563159918970404057137270884587905766828750387753130065274147902379993224780149663600462492281891320702134153853359393588902750423972068679293373333869389393970353760507436913233657422185531482023237384247535554666481760197851108297145147371
e11=1898839980562048754607069073527844852132536432440793106124181406514770178066775988232362054809850074774981836898118651469424148725970708199461113088705044905633592578936333918328544505910996746428679299419879472444790941363558025887620570856598548320246426354974395765243741646121743413447132297230365355148066914830856904433750379114692122900723772114991199979638987571559860550883470977246459523068862898859694461427148626628283198896659337135438506574799585378178678790308410266713256003479022699264568844505977513537013529212961573269494683740987283682608189406719573301573662696753903050991812884192192569737274321828986847640839813424701894578472933385727757445011291134961124822612239865
e12=1262647419018930022617189608995712260095623047273893811529510754596636390255564988827821761126917976430978175522450277907063247981106405519094560616378241247111698915199999363948015703788616554657275147338766805289909261129165025156078136718573006479030827585347458143645738353716189131209398056741864848486818076440355778886993462012533397208330925057305502653219173629466948635110352752162442552541812665607516753186595817376029707777599029040724727499952161261179707271814405907165207904499722122779096230563548011491932378429654764486855147873135769116637484240454596231092684424572258119768093562747249251518965380465994055049411715353547147466711949391814550591591830515262296556050946881

n2=209798341155088334158217087474227805455138848036904381404809759100627849272231840321985747935471287990313456209656625928356468120896887536235496490078123448217785939608443507649096688546074968476040552137270080120417769906047001451239544719039212180059396791491281787790213953488743488306241516010351179070869410418232801398578982244984544906579574766534671056023774009163991804748763929626213884208260660722705479782932001102089367261720194650874553305179520889083170973755913964440175393646890791491057655226024046525748177999422035469428780228224800114202385209306803288475439775037067014297973202621118959024226798935588827359265962780792266516120013602384766460619793738405476219362508944225007365127768741191310079985425349292613888185378948854602285379329682053663283534930182589905986063348509703027498270111412063194971956202729807710253369312175636837558252924035002153389909587349043986253518050303628071319876207392440085675892353421232158925122721273720564784886530611286461575045181073744696415657043278123662980166364494583141297996445429477446442693717498789391918530672770193730629928408766563592081857706608049076318165712479742423149330311238462044666384622153280310696667586565906758451118241914402257039981388209
e2=65537

n3=539779851369541956878655738599584730199799866957191805784596190682932284216781781433367450841202917758999300635019369629627621029957135109806205877317954671312041249493462048283611940752235036153024920172209763260723728345918562258401803973624430150143563078517485996070862532682695228590709019451174548520135142052216785774589096706631010293690859363524584240662502290912412366366114571976050857239915691266377257797199583543940504695517331512813468837128344612227973709974625418257243011036826241599265375741977853552204640800449679679351666009764297016524814036295707311913711955324055690490892097177271718850857268982130811714517356073266905474635370690445031512184247179039751734276906533177939993769044135143389748416635981226449566039039202521305851567296884751935162651063209779647359922622084851547605090230221057349511482738300221222563908357379545905837110168948295030747460300104202323692732549831403834387939156877086852393515817984772384147449841124275061609701453997579569931391166586163299940486204581696722731952467570857217406030804590055255431828403195798003509083922294733709507134156466158642941338493323430671502043066148246348074878064089651235355282144209668143249348243220714471988019011613749340243917652821
e3=8179300978753084587812861894047395225516049110376948812109811319430275614612773726672345893359691900281432484382670047044697374818043512731533402576374645405477207239801498428774783768163880078495448747421425078521981578408638790336528372019271073712013371141939808017049399434858687299480461753638164719404612128939787055797762174745092074547412183349192156638711750872083313795551439465507724807626674514935170104573715458782366469587138508845980490673890245713729782917089910271980557159592807350504157192913530007199510144004848020221181558472160543018733124225266127379373751910439604459368078652499029070936707349862139053913745186413782066470461478961703013591655136140060879250067379283913798867648758171004535775565306842444545755351202796833177560656564652632975685912935281581268141803696686952259539945588609591385807620108279333498170028167338690235117003515264281843953984997958878272347778561933726792473981855755454522886321669676790813189668084373153897754540290867346751033567500922477317530445967753955221454744946208555394588111484610700789566547507402309549957740815535069057837915204852490930168843605732632328017129154852857227895362549146737618906180651623216848500491438142456250653458053922622240299736136335179639180898730269690699965799644757774472147210271111150769048976871249731156387939260749192370361488285775377622944817570292095201906142567403539151179209316853493906909989301225903409448461436855145

c11=18979511327426975645936984732782737165217332092805655747550406443960209507493506811471688957217003792679188427155591583024966608843371190136274378868083075515877811693937328204553788450031542610082653080302874606750443090466407543829279067099563572849101374714795279414177737277837595409805721290786607138569322435729584574023597293220443351227559400618351504654781318871214405850541820427562291662456382362148698864044961814456827646881685994720468255382299912036854657082505810206237294593538092338544641919051145900715456411365065867357857347860000894624247098719102875782712030938806816332901861114078070638796157513248160442185781635520426230183818695937457557248160135402734489627723104008584934936245208116232179751448263136309595931691285743580695792601141363221346329077184688857290503770641398917586422369221744736905117499140140651493031622040723274355292502182795605723573863581253354922291984335841915632076694172921289489383700174864888664946302588049384130628381766560976143458735712162489811693014419190718601945154153130272620025118408017441490090252674737105557818759190934585829634273698371996797545908125156282869589331913665938038870431655063063535672001112420959158339261862052308986374193671007982914711432579
c12=336587005671304527566745948355290412636261748969581976214239578621816863343117433524033533838636941679300497270909696775021031004312477997130741361709262822736904340641138652359632950455651920464042448022467664596484055174270895170499076347333381222768518599018520948098943626229061996126260154604038101543546588917619576702866444998578555907070990331574722135141778182631559802154493815687284077524469331290249057291163803290619701104007028836609832847351748020354798788508790258935718399783002069490123663345156902440501507117289747695510266461539019431610123351176227443612317037899257774045751487135646052309277098939919088029284437221840182769808850184827681307611389353392683707516141736067793897378911235819049432542758429901945202632117089595899280390575706266239252841152490534353760118231918190110043319877744119083811214707593122757409240645257409097436061825613686773916466122693168971062418046703969144004779270391320645495586024342668002497155358623795942692477164489475917351003149045087283510728981096449890130735055015075557614253867698702479920619299919816768972581273507837309179450374634916567083251630203067065663910073926990517108921490442919372774170201239734064819301693527366233007925670043499415100789027665
c2=18352572608055902550350386950073774530453857897248738030380007830701135570310622004368605208336922266513238134127496822199799761713782366178177809597137102612444147565578155260524747439899150012223027218489946124086276814899675563837669559795153349686434242738207425653079514376089070980797596457151965772460109519623572502109592612394316680202287712465721767341302234806130244551387296133051760893033194962691942040228545508895009195291106297581470066545991352668826197346830561010198417527057944507902143965634058848276017283478933675052993657822322866778994956205033704582047618324071045349072526540250707463112668579342537349567247810715604220690215313641329522674080146047291570752430231923566302463491877377617044768978997438596643458475128936850994934029476030136643053997549253792076260765459166618369864942681056864815996253315631930002738854235841120321870075261782250357506436825550088826469396508045912258303652912217151127280959435741419961721418428605515096160344688795655562889755165362006775317188009008288782691705879510655892181975003485714604340542378477388225736316682379616676770234557939471098919647053799313777248678455620231721202780830980063824003076308811540534492317719811588898727134190545533822501681653
c3=113097822337683973761068913398570777162211043704088253732500045618770280334319497174908657828372816818344430304314992760410247741225285170975119344962728883084314382093407445567724674775086423808679124143380073906159023182353116556175251427048715466914368972746661938211846262612414049036821553068430149530397389927209475908905748728402722287875974303298260579839357610962198145974153609818939841880084892796820949226354126424023144300953584658958900737493704530725894948802258740332090822797815745616247879170037794873059391625680745994045522420168248552864215035136318711240256011217929372430302003068882829637056296413462078222453765071094277727760527662423010417144554652783429899139309180017349156600053882338180319473460877576898373222480215735280046214925463242092830060830764299787309912687294672319845054775281463150375545716818434962456139485501224661520991156961587158843064393883274763714930309353593180897123378717852182761518709151878662808890356934477932099818218743384674756674800089177733447066489275506387382342429495897972218764782517198727316942685748481956118012927027254979181519862451112593068440686462293151078537886822555211870303467014484443432209106264020502334805536091587252238173816637270028678636848763

'''

题解

该题主要是对论文论文：https://eprint.iacr.org/2015/399.pdf的实现。

gen1()

联想截图_20230505225140

image-20230505225430944

∣N2∗N1−q2∗q1∣满足定理2条件，abs(p1−p2)<(p1//(2∗r∗q1∗q2))满足定理5。因此，我们只要对N2N1使用连分数展开,可得q1,q2n1=p1r∗q1n2=p2r∗q2r=2由于p1与p2相差较小可得n1n2=p1∗p1∗q1p2∗p2∗q2≈q1q2又因为{c11=powmod(m1,e11,n11)c12=powmod(m2,e12,n12)可解出m1m2|N2*N1−q2*q1|满足定理2条件，\\abs(p1-p2) < (p1//(2*r*q1*q2))满足定理5。\\因此，我们只要对\frac{N2}{N1}使用连分数展开,可得q1,q2\\ n1=p1^r*q1\qquad n2=p2^r*q2\quad r=2\\由于p1与p2相差较小可得\\ \frac{n1}{n2}=\frac{p1*p1*q1}{p2*p2*q2}\approx \frac{q1}{q2}\\又因为\begin{cases} c11 = powmod(m1, e11, n11)\\ c12 = powmod(m2, e12, n12) \end{cases}\\可解出m1 m2

对于gen2()

image-20230505232819303

由题目

idx = (r*(r-1)) / ((r+1)*(r+1)) delta = int(pow(mpz(N), idx)) abs(d1-d2) < delta:满足定理4，将d1-d2设为x 求解出d1-d2

{m1∗d1≡(modphi)(1)m2∗d2≡(modphi)(2)\begin{cases} m1*d1\equiv(mod\quad phi)\qquad (1)\\ m2*d2\equiv (mod\quad phi)\qquad (2)\\ \end{cases} \\

(1)∗m2得:m1∗m2∗d1≡(modphi)(3)(2)∗m2得:m1∗m2∗d2≡(modphi)(4)(3)−(4)得：m1∗m2∗(d1−d2)≡m2−m1(modphi)(1)*m2得: m1*m2*d1\equiv(mod\quad phi)\qquad(3)\\ (2)*m2得: m1*m2*d2\equiv(mod\quad phi)\qquad(4)\\ (3)-(4)得： m1*m2*(d1-d2)\equiv m2-m1(mod\quad phi)\\

构造f(x)求出的d1−d2,对f(x)变形f(x)=phi∗(m2∗k2+m1∗k1)=pr−1∗(p−1)∗(q−1)∗(m2∗k2+m1∗k1)可以发现f(x)与n有公约数pr−1,可以得出p,q,解出b构造f(x)求出的d1-d2,对f(x)变形 \\f(x)=phi*(m2*k2+m1*k1)\qquad \qquad \qquad \\=p^{r-1}*(p-1)*(q-1)*(m2*k2+m1*k1)\\可以发现f(x)与n有公约数p^{r-1},可以得出p,q,解出b

对于gen3():

image-20230505234835055

题目中idx = (r*(r-1)) / ((r+1)*(r+1))
	delta = int(pow(mpz(N), idx))

	while True:
		b = getRandomNBitInteger(int(2048*idx)//2)
		a = getRandomNBitInteger(int(2048*idx)//2)
		if a*b < delta:
			e = invert(a, phi)*b
			return n3, e3, b

满足定理3，可以分解n3，解出m3

对于e=invert(a,phi)∗b，两边同乘以a的逆元x即得到e∗x≡b(modphi)对于e = invert(a, phi)*b，两边同乘以a的逆元x\\即得到e*x\equiv b(mod\quad phi)

构造f(x)=e∗x−b求出x，f(x)与n有最大公约数pr−1构造f(x)=e*x-b求出x，f(x)与n有最大公约数p^{r-1}

求出p,q,得到flag

wp

from Crypto.Util.number import *
import gmpy2


n11=801049932940568005269978912396585741498810389425615966036828877784238116634177290247194019425111606811005728521368879065336038221361037062407029836155148874719789714345603547779284558101833801155509762818376470874215789574939002212274399950433269775325144015468620263028557804618774240232988157961712628677901130814703917513004114547234375629747176834581166306552311075522669403347828095831520693563291249869832390698646691647204371133362254846234990175138047928703289833460734235302093916147489509206061923877623300596194317059884824322527532662470348274079800781120104946546063500763852622187404608639542858285661288293918912184354236687975919510300221932074135531028314170475917110204254042336116619335841213418990605590620842511615815443114612333881430920769002933370887494558640833005339906706603497809846863863967391543647049224309556936909768179259581851520214669904560467640473144481633920438487615788689262961741053146610554997224861331949716721056553499531186695425439163222802917813140266513735841447717418846360096652592844940362932171019143434080184728093326143821165097895058935372215708948088248596585127475770021962501262915274497478428868130455122612016408381607561200802267038869516896665387576895570245272035575637
n12=635401970340205725139325006504978344512744926958688031423448003992072769931808217486709574151492230879374574313457662436423263437792389711379687512056391117410807565492548718691166183372633151644917135272259770997096195518489056319350258673723095417922153182423913759272893696867426193704479752772511081457729513843682588951499551132432923147997238597538055902932123792252593514225328196541483451747314048080824405530742533473914329294346486691684904100406972073037050089861816604505650042953778360621934380815999541183067585498606053857125775979915077329566722531830089714823979965934190338538564188253271016367299890015449611141166780048763403252309160517164569110740561584100839212138661881615351382946813818078899882595313362934594951895560189003438775450675343590147821186953526262224973333962454561275321925151619178204499342339749637758100126893330994252902926509705617882239610380420830791088907378397226817514095468815228186716220057075095711894070032344613244803934541318573847029365563159918970404057137270884587905766828750387753130065274147902379993224780149663600462492281891320702134153853359393588902750423972068679293373333869389393970353760507436913233657422185531482023237384247535554666481760197851108297145147371
e11=1898839980562048754607069073527844852132536432440793106124181406514770178066775988232362054809850074774981836898118651469424148725970708199461113088705044905633592578936333918328544505910996746428679299419879472444790941363558025887620570856598548320246426354974395765243741646121743413447132297230365355148066914830856904433750379114692122900723772114991199979638987571559860550883470977246459523068862898859694461427148626628283198896659337135438506574799585378178678790308410266713256003479022699264568844505977513537013529212961573269494683740987283682608189406719573301573662696753903050991812884192192569737274321828986847640839813424701894578472933385727757445011291134961124822612239865
e12=1262647419018930022617189608995712260095623047273893811529510754596636390255564988827821761126917976430978175522450277907063247981106405519094560616378241247111698915199999363948015703788616554657275147338766805289909261129165025156078136718573006479030827585347458143645738353716189131209398056741864848486818076440355778886993462012533397208330925057305502653219173629466948635110352752162442552541812665607516753186595817376029707777599029040724727499952161261179707271814405907165207904499722122779096230563548011491932378429654764486855147873135769116637484240454596231092684424572258119768093562747249251518965380465994055049411715353547147466711949391814550591591830515262296556050946881
n2=209798341155088334158217087474227805455138848036904381404809759100627849272231840321985747935471287990313456209656625928356468120896887536235496490078123448217785939608443507649096688546074968476040552137270080120417769906047001451239544719039212180059396791491281787790213953488743488306241516010351179070869410418232801398578982244984544906579574766534671056023774009163991804748763929626213884208260660722705479782932001102089367261720194650874553305179520889083170973755913964440175393646890791491057655226024046525748177999422035469428780228224800114202385209306803288475439775037067014297973202621118959024226798935588827359265962780792266516120013602384766460619793738405476219362508944225007365127768741191310079985425349292613888185378948854602285379329682053663283534930182589905986063348509703027498270111412063194971956202729807710253369312175636837558252924035002153389909587349043986253518050303628071319876207392440085675892353421232158925122721273720564784886530611286461575045181073744696415657043278123662980166364494583141297996445429477446442693717498789391918530672770193730629928408766563592081857706608049076318165712479742423149330311238462044666384622153280310696667586565906758451118241914402257039981388209
e2=65537
n3=539779851369541956878655738599584730199799866957191805784596190682932284216781781433367450841202917758999300635019369629627621029957135109806205877317954671312041249493462048283611940752235036153024920172209763260723728345918562258401803973624430150143563078517485996070862532682695228590709019451174548520135142052216785774589096706631010293690859363524584240662502290912412366366114571976050857239915691266377257797199583543940504695517331512813468837128344612227973709974625418257243011036826241599265375741977853552204640800449679679351666009764297016524814036295707311913711955324055690490892097177271718850857268982130811714517356073266905474635370690445031512184247179039751734276906533177939993769044135143389748416635981226449566039039202521305851567296884751935162651063209779647359922622084851547605090230221057349511482738300221222563908357379545905837110168948295030747460300104202323692732549831403834387939156877086852393515817984772384147449841124275061609701453997579569931391166586163299940486204581696722731952467570857217406030804590055255431828403195798003509083922294733709507134156466158642941338493323430671502043066148246348074878064089651235355282144209668143249348243220714471988019011613749340243917652821
e3=8179300978753084587812861894047395225516049110376948812109811319430275614612773726672345893359691900281432484382670047044697374818043512731533402576374645405477207239801498428774783768163880078495448747421425078521981578408638790336528372019271073712013371141939808017049399434858687299480461753638164719404612128939787055797762174745092074547412183349192156638711750872083313795551439465507724807626674514935170104573715458782366469587138508845980490673890245713729782917089910271980557159592807350504157192913530007199510144004848020221181558472160543018733124225266127379373751910439604459368078652499029070936707349862139053913745186413782066470461478961703013591655136140060879250067379283913798867648758171004535775565306842444545755351202796833177560656564652632975685912935281581268141803696686952259539945588609591385807620108279333498170028167338690235117003515264281843953984997958878272347778561933726792473981855755454522886321669676790813189668084373153897754540290867346751033567500922477317530445967753955221454744946208555394588111484610700789566547507402309549957740815535069057837915204852490930168843605732632328017129154852857227895362549146737618906180651623216848500491438142456250653458053922622240299736136335179639180898730269690699965799644757774472147210271111150769048976871249731156387939260749192370361488285775377622944817570292095201906142567403539151179209316853493906909989301225903409448461436855145
c11=18979511327426975645936984732782737165217332092805655747550406443960209507493506811471688957217003792679188427155591583024966608843371190136274378868083075515877811693937328204553788450031542610082653080302874606750443090466407543829279067099563572849101374714795279414177737277837595409805721290786607138569322435729584574023597293220443351227559400618351504654781318871214405850541820427562291662456382362148698864044961814456827646881685994720468255382299912036854657082505810206237294593538092338544641919051145900715456411365065867357857347860000894624247098719102875782712030938806816332901861114078070638796157513248160442185781635520426230183818695937457557248160135402734489627723104008584934936245208116232179751448263136309595931691285743580695792601141363221346329077184688857290503770641398917586422369221744736905117499140140651493031622040723274355292502182795605723573863581253354922291984335841915632076694172921289489383700174864888664946302588049384130628381766560976143458735712162489811693014419190718601945154153130272620025118408017441490090252674737105557818759190934585829634273698371996797545908125156282869589331913665938038870431655063063535672001112420959158339261862052308986374193671007982914711432579
c12=336587005671304527566745948355290412636261748969581976214239578621816863343117433524033533838636941679300497270909696775021031004312477997130741361709262822736904340641138652359632950455651920464042448022467664596484055174270895170499076347333381222768518599018520948098943626229061996126260154604038101543546588917619576702866444998578555907070990331574722135141778182631559802154493815687284077524469331290249057291163803290619701104007028836609832847351748020354798788508790258935718399783002069490123663345156902440501507117289747695510266461539019431610123351176227443612317037899257774045751487135646052309277098939919088029284437221840182769808850184827681307611389353392683707516141736067793897378911235819049432542758429901945202632117089595899280390575706266239252841152490534353760118231918190110043319877744119083811214707593122757409240645257409097436061825613686773916466122693168971062418046703969144004779270391320645495586024342668002497155358623795942692477164489475917351003149045087283510728981096449890130735055015075557614253867698702479920619299919816768972581273507837309179450374634916567083251630203067065663910073926990517108921490442919372774170201239734064819301693527366233007925670043499415100789027665
c2=18352572608055902550350386950073774530453857897248738030380007830701135570310622004368605208336922266513238134127496822199799761713782366178177809597137102612444147565578155260524747439899150012223027218489946124086276814899675563837669559795153349686434242738207425653079514376089070980797596457151965772460109519623572502109592612394316680202287712465721767341302234806130244551387296133051760893033194962691942040228545508895009195291106297581470066545991352668826197346830561010198417527057944507902143965634058848276017283478933675052993657822322866778994956205033704582047618324071045349072526540250707463112668579342537349567247810715604220690215313641329522674080146047291570752430231923566302463491877377617044768978997438596643458475128936850994934029476030136643053997549253792076260765459166618369864942681056864815996253315631930002738854235841120321870075261782250357506436825550088826469396508045912258303652912217151127280959435741419961721418428605515096160344688795655562889755165362006775317188009008288782691705879510655892181975003485714604340542378477388225736316682379616676770234557939471098919647053799313777248678455620231721202780830980063824003076308811540534492317719811588898727134190545533822501681653
c3=113097822337683973761068913398570777162211043704088253732500045618770280334319497174908657828372816818344430304314992760410247741225285170975119344962728883084314382093407445567724674775086423808679124143380073906159023182353116556175251427048715466914368972746661938211846262612414049036821553068430149530397389927209475908905748728402722287875974303298260579839357610962198145974153609818939841880084892796820949226354126424023144300953584658958900737493704530725894948802258740332090822797815745616247879170037794873059391625680745994045522420168248552864215035136318711240256011217929372430302003068882829637056296413462078222453765071094277727760527662423010417144554652783429899139309180017349156600053882338180319473460877576898373222480215735280046214925463242092830060830764299787309912687294672319845054775281463150375545716818434962456139485501224661520991156961587158843064393883274763714930309353593180897123378717852182761518709151878662808890356934477932099818218743384674756674800089177733447066489275506387382342429495897972218764782517198727316942685748481956118012927027254979181519862451112593068440686462293151078537886822555211870303467014484443432209106264020502334805536091587252238173816637270028678636848763

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    #辗转相除法
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf
def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0#分子
    denominator = 1#分母
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)
def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf)):
        gf.append(gradualFra(cf[:i]))
    return gf

#attack 
def solveGen12 ():
    cf=continuedFra(n11,n12)
    #print(cf)
    gf=getGradualFra(cf)
    #print(gf)
    r=2
    f=0
    for j,i in gf[1:]:
        if i != 1 and j != 1:
            if n11%i==0 and n12%j==0:
                print(1)
                f=1
                p1 = gmpy2.iroot(n11 // i, r)[0]
                # print(p1)
                p2 = gmpy2.iroot(n12 // j, r)[0]
                # print(p2)
                phi1 = p1 * (p1 - 1) * (i - 1)
                phi2 = p2 * (p2 - 1) * (j - 1)
                d1 = gmpy2.invert(e11, phi1)
                d2 = gmpy2.invert(e12, phi2)
                mm1 = pow(c11, d1, n11)
                mm2 = pow(c12, d2, n12)
                return mm1, mm2
m1,m2=solveGen1()
print(f"m1={m1}")
print(f"m2={m2}")

m1=167033559384298522723574512241709447697750495062051373339874928117760768631565225663704494711294488556402223152830158600944819657473430506318731286655519728589208977191031849602792050411662024383502548579402516538753112670329781366297260905517214408459895097308286783418547254449419676568096534767340832822470233461516097690657337287889405321592527860524201824371955082411119548743528220794151774190322092515459637969925138496615421690273925560390321721643556915400569894100488394008220811596560968566833296068500476868375996187754631888256419438775013308064639754700359028260289266420692324376220460340153811660590804281527733243177527178698523018103373311259548716062006020121615186595491453534952848570829485638553678760994354019044715078062414748269425818079274218450448217803229617020494546843594180682307375768323235309661628678546003718924902228908888185484412626429441196588985691713767554591991735686919964937441820738008046218954331990752603146125777571183543616375946363623251491371247594696767767918341279655251868517380267258878990871525012299220182939441091806206624720194246691865367941280852353547267930167542329486261552854451001546455904682702366584763940463481732752992487773878685793275652314513014646439770319249
m2=69076592619651589706691933313826601279528159013379300261609967352748175972662567592943146333144902972780621576811778115958019397062270814057821407036352529372113467206560849267275602453288227390740346959857322649956992529510338912182696854496200041245775322561359546062736323363354733510660780489558215103581313753430117471361013972291126160134685745917715386613876414886325025010348396410346222272648657374977901786530969589123771261040601627906959627351426881111464943086191212001374558078570830214670111422731410682212770683631011038163623234630601007231955235905528750031898751733232446644402069580930596404887288935724879795199659228145390574503341087565153744389617539607111733080406125228559950446336384154674927952991964565965760896308198785777527690939982523416579778957846249005801121682470447753074839399698315364445972142571727376297422736232659133510385808957304351692629177239808890209690661982628408419571131470406142532800330250274534615063537773403062635865734585850821677880659194795963303700015814615804751909674946908768425855361277478190640780518117596780808975720826484146074528564147729911624750510271539697935538038871993380673492022099183863825435237650082706168588306816635866830411481021066926833372846305

'''#attack 
#sage
P.<x>= Zmod(n2)[]
f = m1*m2*x -(m2-m1)
x0 = f.monic().small_roots(X=2 ^ 672, beta=0.5)[0]
x0 = int(x0) 
#x0=d1-d2
#x0=3549384841973213309621072870106254602253656209014197632823411827739864720839737811030401306800875843661955913236834617545674409639259372934721570288281471569069146201536309734296340629562207991295283896

'''
def solveGen3():
    r2 = 7
    x0=3549384841973213309621072870106254602253656209014197632823411827739864720839737811030401306800875843661955913236834617545674409639259372934721570288281471569069146201536309734296340629562207991295283896
    xx= m1*m2*x0 -(m2-m1)
    tp2=gmpy2.gcd(xx,n2)
    p2=gmpy2.iroot(tp2,r2-1)[0]
    q2=n2//(tp2*p2)
    phi2=p2**6*(p2-1)*(q2-1)
    d2=gmpy2.invert(e2,phi2)
    b=pow(c2,d2,n2)
    return b



b=solveGen2()
print(f"b={b}")
b=17623328397444755087284107444487160871617682792372566887446834913712379373851213638071138745775127796589871734472781755930251379295485892067473329763997583502625804363418069062645997342172778252731889437

#flag
#sage
#PR.<x> = PolynomialRing(Zmod(n3))
#f = e3 * x -int(b)
#x0 = f.monic().small_roots(X=2 ^ 672, beta=0.5)[0]
x=16731588253866128571163910758846497670928988943944436618514118121761227689113110943465936457030051710610254169629932203082368465978112219532158626669990117160986135699541953274434781877420432743573801621
tp3=gmpy2.gcd(e3*x-b,n3)
r3=7
p3 = gmpy2.iroot(tp3, r3 - 1)[0]
q3 = n3 // (p3**r3)
phi3 = p3 ** (r3-1) * (p3 - 1) * (q3 - 1)
d3 = gmpy2.invert(e3, phi3)
m= pow(c3, d3, n3)
print(long_to_bytes(int(m)))

#qwb{8633ce6d-fece-4cf1-8f0f-f27e5bf6d678}