[HDCTF 2023]Normal_Rsa（e,phi不互素）

本文主要是介绍[HDCTF 2023]Normal_Rsa（e,phi不互素），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

from Crypto.Util.number import *
m=bytes_to_long(b'xxxxxx')
p=getPrime(256)
q=getPrime(256)
e=74
n=p*q
c=pow(m,e,n)
print("p=",p)
print("q=",q)
print("c=",c)
#p= 86053582917386343422567174764040471033234388106968488834872953625339458483149
#q= 72031998384560188060716696553519973198388628004850270102102972862328770104493
#c= 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123

首先我们利用网站对n进行分解得到P，Q，然后计算出phi后发现e,phi不互素

但e,phi的最大公约数t很小，为2，故我们直接利用e//t，与phi计算得到d。

EXP：

from gmpy2 import gmpy2
from Cryptodome.Util.number import long_to_bytesp= 86053582917386343422567174764040471033234388106968488834872953625339458483149
q= 72031998384560188060716696553519973198388628004850270102102972862328770104493
c= 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123
e=74
n=p*q
phi=(p-1)*(q-1)
t = gmpy2.gcd(e, phi)
print(t)
d = gmpy2.invert(e//t, phi)
flag = gmpy2.powmod(c, d, n)
print(long_to_bytes(flag))
msg = gmpy2.iroot(flag, t)
if msg[1]:print(long_to_bytes(msg[0]))

这篇关于[HDCTF 2023]Normal_Rsa（e,phi不互素）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---