P11.共享素数-N不互素

两个n里使用有相同的素数p或q 在CTF中，同样一个e（一般为65537）和m， 有两个或多个n和c时，那么n之间可能是共享素数

出题脚本

随机生成flag

import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

题目

import libnum

#生成随机素数
p1=libnum.generate_prime(1024)
p2=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
m="flag{c9d48baa792e91ce65d175bb586f8c24}"
#字符串转数字
m=libnum.s2n(m)
print(q)
n1=p1*q
n2=p2*q
#求逆元
c1=pow(m,e,n1)
c2=pow(m,e,n2)

print ("e=",e)
print("n1=",n1)
print("n2=",n2)
print ("c1=",c1)
print ("c2=",c2)

解题脚本

import libnum
import gmpy2


e= 65537
n1= 
n2= 
c1= 
c2=

#求最大公约数
q=gmpy2.gcd(n1,n2)
p1=n1//q

phi_n=(q-1)*(p1-1)
#求逆元d
d1=libnum.invmod(e,phi_n)
m=pow(c1,d1,n1)
print(m)
#数字转字节，转字符串
print(libnum.n2s(int(m)).decode())

模不互素,另类脚本 sage

e= 65537
n1= 21093893530165595850339636291340886775560459889174993298599564679470961520127537242137351793326916956073009495303622153882623912792088101281148271957920985536369095953335024370158909102755939425266322061024660469804331164229029302486833732919273709880115072578649082360889893770131535569945349586879686172801621707802368786052168013925892590355941771860436819249314675001571361991296570354259045254453585842424561844676250437625123809885279029491512960326206418322762119343167800501997630708987739950144724219375568233516957162796160222178022591375724806703162674485897117438453945303273004012532132059011075717387753
n2= 14824267720565830614198366423536599666692078969408403530258418602151322644585576708517191288357418574410537646212589360867055238409644225020114747038342097744542022643037865665129552322573216047070677736725417436626920538199776045223182025555032687422098410274010072272948921387942284889428172227747124840681230287572405913777684484640035353309074356839921615363768839468380890923086904115913017609689750326299359077846457821010369130002914875100460359637094049091716624328545343429605828899486733904861746381542564902018804771429533804771098266001841458433664015729735822285137823715376774756745985491673136930276941
c1= 15493359169301410074294742205843127951680374731395022149514872755993630629089162028408320207198994693027373636212060578272511287443597043280252256375148624563670499072871754643384189774533934405727733699679220914275088403183879336594241788249627810478123376166068327204499510069769671107400170031827409347799781818216854334998468909013183811525688284142974464445136216626020389073625379426889005557474784633107067037562364550927860932957239328403322326674852543731738932181913222422086087135017041465305467628933404091450876573447149054228726054585012570036091080257371923849834757954329673617514640675309941718326627
c2= 1129639783725801764965293730716077563236066858849848417513754106728304324550964149779456929545632835403665303400567929779454798061338838786581070336886869145357696864488611518771125027534268787109010503430313447389460984683822032899389007646158783785728285343713347931494062199917243631366285764058939519090743602216977513724902021454418835574712871092514940757735723709297452463014431720040155161772629328937153713384012521957796438994675887733312827926502709695530933411909694455038223632075992122461473772324457706144526855909934434396846023332605403533525981854297958006877942800622448532300316434156727548355876

p=GCD(n1,n2) 
q1=n1//p 
q2=n2//p 
e=0x10001 
a=crt([c1,c2],[n1,n2]) 
d=inverse_mod(e,(p-1)*(q1-1)*(q2-1)) 
m=pow(int(a),d,p*q1*q2) 
print(m)
nb=int(m).bit_length()//8+1 
print(int(m).to_bytes(nb,'big'))