security - RSA密码系统

Question

嗨，我正在尝试建立一个 RSA 加密系统，我拥有除 d 选定素数之外的所有值:p=1889、q=2003、n =3783667、phi=3779776、e= 61

我找不到d，有人能帮我解决吗？

设置 RSA 加密系统

• 选择两个不同的大质数p和q，并且n = pq和Φ(n) = (p − 1)(q − 1) 计算。

• 选择一个整数e，使得gcd(Φ(n), e) = 1和乘法逆元d = e^(计算ZΦ(n)中的−1)，即

  ed = 1 (mod Φ(n))。

• 数字p、q和Φ(n)随后被丢弃。

• (e, n) 对作为公共(public)加密 key 发布
• 数字d是 secret 解密 key 。

Answer 1

Here's算法，一步一步，包括找到d。
文章中的 m 是您的 Φ(n)。
现在，您尝试找到 d = (1 + nm)/e，遍历 n 的值，直到 e 的整数解为找到了。

编辑: Here您会找到整个算法的更详细说明。