java - 查找与模数互质的数

Question

我一直在研究 RSA 加密系统，使用小素数编写一个非常简单，因为没有太多的可能性，而且性能也不是真正的问题。

RSA 的工作原理如下:

• 首先，您生成一个 n 值，它是随机选取的 2 个素数的乘积:

  n = p * q
  

  • 然后您需要您的公钥，称为e。它可以是任何与 φ(n) 互质的数:

    mcd(φ(n), e) = 1

  • 根据欧拉函数，φ(n) = (p-1)(q-1)

  • 您仍然需要您的私钥，称为 d，它是 e 模 **φ(n) 的倒数。

  • 所以 d * e = 1 (mod φ(n))

  • n 和 e 是您的公开值，而 d 是您的私钥。没有人应该知道 p 或 q，因为有了这些值就可以得到 φ(n)，并用它来计算 d.
• 要加密消息，我们使用 M = m^e (mod n)，其中 m 是原始消息，而 M是加密的。因此，每个人都可以使用您的公共(public)值(value)观向您发送一条您可以阅读的加密消息。
• 要解密消息，您可以使用 d，因为它是 e 的倒数，所以 M^d = (m^e)^d = m (mod n)。可以解密消息，但只能使用 d。

知道这一点，要加密一条消息，我们只需要获得两个随机素数，计算n, e, d, 并制定我们的加密和解密方法。

---

这在理论上似乎很容易，现在让我们把它变成 java 代码:

我先随机选择两个素数，数字越大加密越强。所以我会选择 p = 1644623 和 q = 1644751。根据this page , 它们是素数。

BigInteger p = new BigInteger("1644623");
BigInteger q = new BigInteger("1644751");

然后，在我的 init 方法中，我初始化了 n, e 和 d:

BigInteger p = new BigInteger("1644623");
BigInteger q = new BigInteger("1644751");

BigInteger n;
BigInteger e;
BigInteger d;

void init() {
    n = p.multiply(q);

    BigInteger pn = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

    e = n.subtract(pn);
    while (!mcd(pn, e).equals(BigInteger.ONE)) {
        e = e.add(BigInteger.ONE);
        System.out.println(e);
    }

    d = e.modPow(new BigInteger("-1"), pn);
}

我使用 BigInteger 而不是 long，因为使用的值非常大。

理论上，一切正常。实际上，pn = 2704992034500，所以检查是否 mcd(pn, e) = 1，如果不加 1 到 e 并重试不是一个选择。该程序运行了 30 分钟，平均每秒处理 150.000 个数字。 e = 548151505 仍未找到 mcd(pn, e) = 1。

---

有没有办法在合理的时间内找到e？

---

Answer 1

根据定义，任何质数都将与模数互质，因此您无需搜索一个，只需选择一个质数即可。由于加密 key 是公开的，因此大多数 RSA 实现使用的东西可以很容易地计算模幂:3 和 65537 = 2 ** 16 + 1 都是质数，并且都常用于加密 key 。