用非常大的模块($n$)和非常小的$e$攻击RSA (7)

Question

作为一个练习，我被授予了一个RSA来攻击。我有模块(n)、公共指数(e)和单个密文(c)。

对于这种特殊情况，n非常大(大约5000位数)，但是公共指数很小(e=7)。

我知道，作为m \ll n，这不会导致模块操作(m^7\bmod n = m^7)的使用。我试着逆转它做c^{1/7}=m^{7\cdot1/7}=m，但这是行不通的。可能是那个m^7 \bmod n \neq m^7。在这种情况下我能做什么？

我遗漏了什么/误解了什么？

编辑

有人给了我一个提示：“大n对小e毫无用处”。我猜想它更多的是与指数有关，而不是n。

Answer 1

我发现了问题:我的实现是不正确的。在发生m^e \mod n = m^e的情况下，确实存在一个漏洞。下面是一个用于正确计算它的Python实现(出于隐私原因，n和c的值被修改)。

from decimal import *

n = {redacted}
c = {redacted}
e = 7

# https://docs.python.org/3/library/decimal.html
c = Decimal(c)
e = Decimal(e)

getcontext().prec = 500 # Set a big enough precision
root = pow(c, 1/e) # Calculate c^(1/e) = m^(e * 1/e) = m
print(root)

# Decode with no padding
m = hex(int(root))[2:-1] # Number to hex
m = ''.join(chr(int(m[i:i+2], 16)) for i in range(0, len(m), 2)) # Hex to Ascii
print(m)