题目描述

解题步骤

下载附件，得到：

1
2
在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d作为flga提交

  • p = 473398607161
  • q = 4511491
  • e = 17

要求：

  • 计算私钥 d，使得：d ≡ e⁻¹ mod φ(n)
  • 其中 φ(n) = (p-1)*(q-1)
  • 最终以 flag{d} 形式提交
    主要步骤：
  1. 计算欧拉函数：φ(n) = (p-1)*(q-1)
  2. 计算 d = e⁻¹ mod φ(n)，即 d 是 e 在模 φ(n) 下的模逆元
  3. 输出 d

SageMath 是非常适合数论和 RSA 计算的工具，支持大整数和模逆元直接计算。

1
2
3
4
5
6
7
8
9
10
11
# RSA 参数
p = 473398607161
q = 4511491
e = 17

# 计算 phi(n) = (p-1)*(q-1)
phi = (p - 1) * (q - 1)

# 计算 d = e^(-1) mod phi
d = inverse_mod(e, phi)