rsa

一、固定数的幂开方

question:

c = pow(m, 256, p)
print(p)

payload:

from sympy.ntheory.residue_ntheory import nthroot_mod
m = nthroot_mod(c,256,p,all_roots=True)

二、P,Q很近，已知c,d， n未知(拓展欧几里得算法爆破pq)

from gmpy2 import *
from sympy import *
from Crypto.Util.number import *
d = 
c = 
e=0x10001
src=d*e-1
i=2**15
while True:
    if(src%i==0):
        if((src//i)>=2**2046 and (src//i)<=2**2048):
            phi=src//i
            q_1=iroot(phi,2)[0]
            q=nextprime(q_1)
            if(phi%(q-1)==0):
                p_1=phi//(q-1)
                p=p_1+1
                if(isprime(p)):
                    print(p,q)
                    break
    i+=1
    if((src//i)<2**2046):
        print 0
        break
n=p*q
m=pow(c,d,n)
flag=long_to_bytes(m)
print flag

三、模中共因数,m相同(需要拆分合并)

question:

#已知e1,e2,p,q1,q2
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))

payload:

def exCRT_getequation(a,n):
    a1=a[0]
    n1=n[0]
    le= len(a)
    for i in range(1,le):
        a2 = a[i]
        n2=n[i]
        if not merge(a1,n1,a2,n2):
            return -1
        a1 = a3
        n1 = n3
    return (a1,n1)

phi1=(p-1)*(q1-1)
phi2=(p-1)*(q2-1)
xx1=gmpy2.gcd(e1,phi1)
xx2=gmpy2.gcd(e2,phi2)
d1=gmpy2.invert(e1//xx1,phi1)
d2=gmpy2.invert(e2//xx2,phi2)
nn=[]
aa=[]
nn.append(q1)
nn.append(q2)
a1=gmpy2.powmod(c1,d1,p*q1)%q1
a2=gmpy2.powmod(c2,d2,p*q2)%q2
aa.append(a1)
aa.append(a2)
last=exCRT_getequation(aa,nn)#最终方程组 aa=n^14%q1*q2
new_e=14/2
new_phi=(q1-1)*(q2-1)
new_d=gmpy2.invert(new_e,new_phi)
m_2=gmpy2.powmod(last[0],new_d,last[1])#特解m_2
flag=gmpy2.iroot(m_2,2)[0]
import binascii
print(binascii.unhexlify(hex(flag)[2:]))

四、小指数爆破

question:

ee1 = 42
ee2 = 3
ce1 = 
ce2 = 
tmp = 
n  = 
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)

payload:

def doit(ee,n,ce):
    k=0
    while True:
        x=ce+k*n
        if gmpy2.iroot(x,ee)[1]:
            return gmpy2.iroot(x,ee)[0]
        k=k+1
e1=doit(ee1,n,ce1)
e2=doit(ee2,n,ce2)-tmp
print(e1)
print(e2)
##小指数爆破
##其中,ee为指数,n为模数,ce为余数

五、给lcm[(p-1),(q-1)]最小公倍数

question:

p = getPrime(1024)
q = getPrime(1024)
n = p * q
gift = lcm(p - 1 , q - 1)#求最小公倍数
e = 54722
flag = b'NPUCTF{******************}'
m = int.from_bytes(flag , 'big')
c = powmod(m , e , n)
print('n: ' , n)
print('gift: ' , gift)
print('c: ' , c)

answer:

#查看bit长度
print(len(bin(n)))
print(len(bin(gift)))
#尝试分解gift
#比较二者长度差k  
#估算phi=gift*2**k
#e分解至与phi互质
#求d
#求m

payload:

from Crypto.Util.number import *
import gmpy2

e = 54722
# e = 2*27361
n = 
gift = 
c =
# gift = 8 * 11 * 97 * 9601 * 26057167557433418766727399341516665922795024485718296827775927226598694152064298989740080209950805089159979564300359652085874056289167084685303669920341402021998569251561854184586912056788515477034039863935829715784489123437315798902409373317578932823488000322365526936227790036245092665207472438169954702748857842187299166976320465787901470261800372425345547560303561842376571751928531743505412746346436473024093575122041981043859827477404447458211341273671273506575488189374812217939984540494633634622813448773520886788206836310702581026986331011987344147901504555559723572981774237352245997308787165273589

print(len(bin(gift)[2:]))
print(len(bin(n)[2:]))

# gift * gcd = (p-1) * (q-1)
# gift % gcd = 0
for gcd_val in range(4, 8):
    phi = gift * gcd_val
    try:
        d = gmpy2.invert(e // 2, phi)
        m_2 = pow(c, int(d), n)
        flag = long_to_bytes(gmpy2.isqrt(m_2))
        print(flag)
    except ZeroDivisionError:
        continue
#NPUCTF{diff1cult_rsa_1s_e@sy}

六、共模攻击(n相同)

1. 给出e1,e2(新生成e1,e2)

question:

p, q = getPrime(256), getPrime(256)
n = p * q
e1, e2 = getPrime(32), getPrime(32)
c1, c2 = pow(c, e1, n), pow(c, e2, n)
print(n)
print(e1, c1)
print(e2, c2)

payload:

# py2 sameNAttack.py
import primefac

def same_n_attack(n,e1,e2,c1,c2):
    def egcd(a,b):
        x, lastX = 0, 1
        y, lastY = 1, 0
        while (b != 0):
          q = a // b
          a, b = b, a % b
          x, lastX = lastX - q * x, x
          y, lastY = lastY - q * y, y
        return (lastX, lastY)
    s = egcd(e1,e2)
    s1 = s[0]
    s2 = s[1]
    if s1 < 0:
        s1 = -s1
        c1 = primefac.modinv(c1, n)
        if c1 < 0:
           c1 += n
    elif s2 < 0:
        s2 = -s2
        c2 = primefac.modinv(c2, n)
        if c2 < 0:
            c2 += n
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    return m

2. e1,e2即p,q

question:

m = bytes_to_long(flag)

p, q = getPrime(512), getPrime(512)
n = p * q
e1, e2 = p, q
c1, c2 = pow(m, e1, n), pow(m, e2, n)

print(n)
print(c1)
print(c2)

payload:

#sage
n=128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
c1=96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
c2=9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585m
PR.<m> = PolynomialRing(Zmod(n))
f = m^2-(c1+c2)*m+c1*c2
x0 = f.small_roots(X=2^400)
print(x0)

七、中国剩余定理通解版

question:

n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L]
f=lambda m,e,n,c:pow(m,e,n)==c
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)

payload:

def  merge(a1,n1,a2,n2):
    d = math.gcd(n1,n2)
    c = a2-a1
    if c%d!=0:
        return 0
    c = (c%n2+n2)%n2
    c = c//d
    n1 = n1//d
    n2 = n2//d
    c *= gmpy2.invert(n1,n2)
    c %= n2
    c *= n1*d
    c += a1
    global n3
    global a3
    n3 = n1*n2*d
    a3 = (c%n3+n3)%n3
    return 1
def exCRT(a,n):
    a1=a[0]
    n1=n[0]
    le= len(a)
    for i in range(1,le):
        a2 = a[i]
        n2=n[i]
        if not merge(a1,n1,a2,n2):
            return -1
        a1 = a3
        n1 = n3
    global mod
    mod=n1
    return (a1%n1+n1)%n1

p_4=exCRT(c,n)
p=gmpy2.iroot(p_4,4)[0]

八、解方程

使用方法

from z3 import *

s = Solver()

flag1 = Int('flag1')
flag2 = Int('flag2')

s.add(flag1 + flag2 == 2732509502629189160482346120094198557857912754)
s.add(pow(flag1,3)+pow(flag2,3) ==5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554)

if s.check() == sat:
    print s.model()

print hex(1590956290598033029862556611630426044507841845)[2:-1].decode('hex')+hex(1141553212031156130619789508463772513350070909)[2:-1].decode('hex')

九、e为phi因子，无法直接计算d

payload:

import gmpy2

def n2s(x):
    try:
        try:
            flag = hex(x)[2:].decode("hex")
        except:
            flag = hex(x)[2:-1].decode("hex")
    except:
        flag=''
    return flag

def onemod(p,r):
    t=p-2
    while pow(t,(p-1)/r,p)==1: t-=1
    return pow(t,(p-1)/r,p)

def solution(p,root): 
    g=onemod(p,0x1337)
    may=[]
    for i in range(0x1337):
        if i%100 == 0:
            print i
        may.append(root*pow(g,i,p)%p)
    return may

c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059

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

c_p = pow(c,(1+3307*(p-1)/e)/e,p)
print "find one"
C1=solution(p,c_p)
print "find all"
c_q = pow(c,(1+(2649*(q-1)/e))/e,q)
print "find another"
C2=solution(q,c_q)
print "find all"
a= gmpy2.invert(p,q)
b = gmpy2.invert(q,p)
#x = (b*q*c_p+a*p*c_q)%n
flag=0
for i in C1:
    for j in C2:
        flag+=1
        if flag%1000000 == 0:
            print flag
        x = (b*q*i+a*p*j)%n
        if "{" in n2s(x):
            print n2s(x)

十、模不互素

question:

p1 = get_a_prime(128)
p2 = get_a_prime(128)
p3 = get_a_prime(128)
n1 = p1*p2
n2 = p1*p3
e = 0x1001
c1 = encrypt(msg1, e, n1)
c2 = encrypt(msg2, e, n2)
print(c1)
print(c2)

payload:

#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes,isPrime
n1 = 2499586809914462821807624371088011200618603528498132509598946284572455726453497171635086810524607288333625665025664872216634366700044105279185519761587818169021167370991396691510275499486673922916370294043072503635630922980240462022218565365191228535222150496387990987123639567257124081274667568443678527637259644488779394704508217357758791670308548246801142468699716221789070607334747835552167450340441488756779323653879402176647890584656379628685893686585469918686253137796663587854943386347039389769790329948165162483370187914412810153613198247569427480466488647563900948387020677830797976534568626241686906738179
n2 = 7741603029707932330739678982394275613217057249691533148704382574439895657047911501600910571360188397109729289277796711334388156202412769743785164713243932001078475541271281825859671767783178037363138683152051263779907568124470598237502689045677891605285193637790880045372303913424654655825837641694318544209980415256180296972066060073206323473960669679401950151966003026531573962072358852304635671658878866030003484715256388556599713638695448516673643703041094737763957937855870992247472296348887788212823714735080211059688680618314050267995177478035769912691185787944037050674163079867101586607780761245261558200843
n3 = 9895571060693703887018268413746107679094703478067972087862851570192520012058188062485476484700707994684397704099884436398099581319015589480235346899990863625919087077906193223937343450727301243043576326163300258770936289423785376338765758863453745278516208013244068358484113062931878984339475569902332075509121153749576470546863477142562563573654198332099438611713385318497180237117792417826080724886477023904678472464557511959911739272258202310963925049222305927992349171516332320267610895787011879250778522843808895509894741144901052000573058315131265960606119769594234837973757057319170067823816025499647517874841
c1 = 0x1240198b148089290e375b999569f0d53c32d356b2e95f5acee070f016b3bef243d0b5e46d9ad7aa7dfe2f21bda920d0ac7ce7b1e48f22b2de410c6f391ce7c4347c65ffc9704ecb3068005e9f35cbbb7b27e0f7a18f4f42ae572d77aaa3ee189418d6a07bab7d93beaa365c98349d8599eb68d21313795f380f05f5b3dfdc6272635ede1f83d308c0fdb2baf444b9ee138132d0d532c3c7e60efb25b9bf9cb62dba9833aa3706344229bd6045f0877661a073b6deef2763452d0ad7ab3404ba494b93fd6dfdf4c28e4fe83a72884a99ddf15ca030ace978f2da87b79b4f504f1d15b5b96c654f6cd5179b72ed5f84d3a16a8f0d5bf6774e7fd98d27bf3c9839
c2 = 0x129d5d4ab3f9e8017d4e6761702467bbeb1b884b6c4f8ff397d078a8c41186a3d52977fa2307d5b6a0ad01fedfc3ba7b70f776ba3790a43444fb954e5afd64b1a3abeb6507cf70a5eb44678a886adf81cb4848a35afb4db7cd7818f566c7e6e2911f5ababdbdd2d4ff9825827e58d48d5466e021a64599b3e867840c07e29582961f81643df07f678a61a9f9027ebd34094e272dfbdc4619fa0ac60f0189af785df77e7ec784e086cf692a7bf7113a7fb8446a65efa8b431c6f72c14bcfa49c9b491fb1d87f2570059e0f13166a85bb555b40549f45f04bc5dbd09d8b858a5382be6497d88197ffb86381085756365bd757ec3cdfa8a77ba1728ec2de596c5ab

p1 = gmpy2.gcd(n1,n2)
p2 = n1//p1
p3 = n2//p1

assert isPrime(p1)          //检查这三个数是否为素数
assert isPrime(p2)
assert isPrime(p3)

e = 0x1001
phi1 = (p1-1) * (p2-1)
phi2 = (p1-1) * (p3-1)

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

m1 = gmpy2.powmod(c1,d1,n1)
m2 = gmpy2.powmod(c2,d2,n2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

十一、wiener attack攻击（e很大）

from Crypto.Util.number import *
from Crypto.Cipher import DES
from gmpy2 import *
class ContinuedFraction():
    def __init__(self , numerator, denumerator):
        self.numberlist = []    #number in continued fraction
        self.fractionlist = []  #the near fraction list
        self.GenerateNumberList(numerator , denumerator)
        self.GenerateFractionList()

    def GenerateNumberList(self,numerator,denumerator):

        while numerator != 1:
            quotient = numerator//denumerator
            remainder = numerator % denumerator
            self.numberlist.append(quotient)
            numerator = denumerator
            denumerator = remainder

    def GenerateFractionList(self):
        self.fractionlist.append([self.numberlist[0] ,1 ])
        for i in range(1,len(self.numberlist)):
            numerator = self.numberlist[i]
            denumerator = 1
            for j in range(i):
                temp = numerator
                numerator = denumerator + numerator * self.numberlist[i-j-1]
                denumerator = temp
            self.fractionlist.append([numerator,denumerator])

def Solve(a , b , c):
    '''solve ax^2+bx+c=0 , return x1 , x2'''
    delta = b**2 - 4 * a * c
    if delta < 0:
        return 0
    if is_square(delta):
        sqr_delta = isqrt(delta)
        temp1 = -b + sqr_delta
        temp2 = -b - sqr_delta
        if temp1 % (2*a) != 0 or temp2 % (2*a) != 0:
            return 0
        else:
            return [temp1//(2*a) , temp2//(2*a)]
    else:
        return 0
def WienersAttack(e , N):
    a = ContinuedFraction(e , N)
    for i in a.fractionlist:
        k = i[0]
        d = i[1]
        if k == 0:
            continue
        fai_N = (d * e - 1) // k
        b = fai_N - N - 1
        temp = Solve(1 , b , N)
        if isinstance(temp ,list):
            print(d)
            p ,q = temp
            return d , p , q

n = 
e = 
c = 
d ,p ,q= WienersAttack(e, n)
phi = (p - 1)*(q - 1)
m=pow(c,d,n)
print(m)

十二、Extending Wiener Attack(e有2个)

题目

#已知e1,e2,c,N,E 求P，Q
P = getPrime(1024)
Q = getPrime(1024)
N = P * Q
E = 65537
lcm = gmpy2.lcm(P-1, Q-1)
e1 = gmpy2.invert(getPrime(730), lcm)
e2 = gmpy2.invert(getPrime(730), lcm)
m = bytes_to_long(flag)
c = pow(m, E, N)

payload

from sage.all import *
from Crypto.Util.number import long_to_bytes
import gmpy2
# Different parameters for each team
N = 
e2 = 
e1 = 
c = 
E =
alpha2 = 730/2048
#730:d's bits  2048:n's bits
M1 = int(gmpy2.mpz(N)**0.5)
M2 = int( gmpy2.mpz(N)**(1+alpha2) )
D = diagonal_matrix(ZZ, [N, M1, M2, 1])
B = Matrix(ZZ, [ [1, -N,   0,  N**2],
                 [0, e1, -e1, -e1*N],
                 [0,  0,  e2, -e2*N],
                 [0,  0,   0, e1*e2] ]) * D
L = B.LLL()
v = Matrix(ZZ, L[0])
x = v * B**(-1)
phi = (x[0,1]/x[0,0]*e1).floor()

PR = PolynomialRing(ZZ, 'x')
x = PR.gen()
f = x**2 - (N-phi+1)*x + N
p = f.roots()[0][0]
print(p)
q = int(N) // int(p)
d = inverse_mod( E, (p-1)*(q-1) )
m = power_mod(c, d, N)
print(b'flag: ' + long_to_bytes(m))

十三、Extending Wiener Attack(e有3个)

from sage.all import *
from Crypto.Util.number import *
n=
e=
c=
e1=
e2=
e3=
b=0.4
A=[
[1,-n,0,n^2,0,0,0,-n^3],
[0,1,-1,-n,-1,0,n,n^2],
[0,0,1,-n,0,n,0,n^2],
[0,0,0,1,0,-1,-1,-n],
[0,0,0,0,1,-n,-n,n^2],
[0,0,0,0,0,1,0,-n],
[0,0,0,0,0,0,1,-n],
[0,0,0,0,0,0,0,1]]
Q=[n^1.5,n,n^(1.5+b),n^0.5,n^(1.5+b),n^(1+b),n^(1+b),1]
P=[1,e1,e2,e1*e2,e3,e1*e3,e2*e3,e1*e2*e3]
A,P,Q=matrix(ZZ,A),diagonal_matrix(ZZ,P),diagonal_matrix(ZZ,Q)
A=P*A*Q
w=vector(ZZ,A.LLL()[0])
v=w*A^(-1)
phi1,phi2=int(e1*v[1]//v[0]),int(e2*v[2]//v[0])
phi=int(phi1)
print(hex(phi1))
d,d0=inverse(e,phi),inverse(e2,phi)
print(long_to_bytes(pow(c,d,n)))

十四、Extending Wiener Attack(e有4个)

from sage.all import *
from Crypto.Util.number import *
n=
e=
c=
e1=
e2=
e3=
e4=
b=0.4
A=[
[1,-n,0,n^2,0,0,0,-n^3,0,0,0,0,0,0,0,n^4],
[0,1,-1,-n,-1,0,n,n^2,-1,0,n,0,n,0,-n^2,-n^3],
[0,0,1,-n,0,n,0,n^2,0,n,0,0,0,-n^2,0,-n^3],
[0,0,0,1,0,-1,-1,-n,0,-1,-1,0,0,n,n,n^2],
[0,0,0,0,1,-n,-n,n^2,0,0,0,-n^2,0,0,0,-n^3],
[0,0,0,0,0,1,0,-n,0,0,0,n,-1,0,n,n^2],
[0,0,0,0,0,0,1,-n,0,0,0,n,0,n,0,n^2],
[0,0,0,0,0,0,0,1,0,0,0,-1,0,-1,-1,-n],
[0,0,0,0,0,0,0,0,1,-n,-n,n^2,-n,n^2,n^2,-n^3],
[0,0,0,0,0,0,0,0,0,1,0,-n,0,-n,0,n^2],
[0,0,0,0,0,0,0,0,0,0,1,-n,0,0,-n,n^2],
[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,-n],
[0,0,0,0,0,0,0,0,0,0,0,0,1,-n,-n,n^2],
[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,-n],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,-n],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]]
Q=[n^2,n^1.5,n^(2+b),n,n^(2+b),n^(1.5+b),n^(1.5+b),n^0.5,n^(2+b),n^(1.5+b),n^(1.5+b),n^(1+b),n^(1.5+b),n^(1+b),n^(1+b),1]
P=[1,e1,e2,e1*e2,e3,e1*e3,e2*e3,e1*e2*e3,e4,e1*e4,e2*e4,e1*e2*e4,e3*e4,e1*e3*e4,e2*e3*e4,e1*e2*e3*e4]
A,P,Q=matrix(ZZ,A),diagonal_matrix(ZZ,P),diagonal_matrix(ZZ,Q)
A=P*A*Q
w=vector(ZZ,A.LLL()[0])
v=w*A^(-1)
phi=int(e1*v[1]//v[0])
print(hex(phi))
d=inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

十五、n=p^k*q

p = getPrime(512)
q = getPrime(512)
n = p**4*q

e = 0x10001
phi = gmpy2.lcm(p - 1, q - 1)
d = gmpy2.invert(e, phi)
dp = d % (p - 1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print "dp = " + str(dp)
print "c = " + str(c)

m=pow(c,dp,p)