P17.e和phi_n不互素

P18.e和phi_n不互素

出题脚本

import gmpy2
import libnum
import random
import uuid
flag="flag{"+str(uuid.uuid4())+"}"
m=libnum.s2n(flag)

while 1:
    e = random.randint(100,1000)
    p=libnum.generate_prime(1024)
    q=libnum.generate_prime(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("p=",p)
print("q=",q)
print("e=",e)
print("c=",c)

解题脚本

import gmpy2
from Crypto.Util.number import *
#当e约去公约数后与phi互素
def decrypt(p,q,e,c):
    n=p*q
    phi=(p-1)*(q-1)
    t=gmpy2.gcd(e,phi)
    d=gmpy2.invert(e//t,phi)
    m=pow(c,d,n)
    msg=gmpy2.iroot(m,t)
    if msg[1]:
        print(long_to_bytes(msg[0]))
p=149728544112555599590936673615696271318636529352637830106348687941183054498250042553549708433208468004536400117026086238076264785396396599290721801532887662723160698502186620809003309343021490868380464762486274154096814166441270611631342173101926176645742035350917214925625954628200341278782929951624259583527
q=149728544112555599590936673615696271318636529352637830106348687941183054498250042553549708433208468004536400117026086238076264785396396599290721801532887662723160698502186620809003309343021490868380464762486274154096814166441270611631342173101926176645742035350917214925625954628200341278782929951624259582993
e=180
c=17971123746814947059314270113966290245749007752378241906733564181493060407114219968936077930494933520528427074831694818994710527963410153282657079091353179846750982127804195747725871635911272654572811618799762595633801414107052800867035212498914627567940429340162711284873714117628807667324064684965941290688518710890089086623981356782977499005308798890348799101436318386502089586589964942282091818134339082321114129830959264557408611168516265190076744300272908807347811446203373025446057616713876047942653095947804696077860211107853183353180163392501353685418796451123620066941329424857070023018877454625734091037559


decrypt(p,q,e,c)