编码 RSA 算法 Java

Question

因此，我正在尝试从头开始创建 RSA 算法。

到目前为止，我已经成功地创建了 select 两个素数的能力（在我当前的示例中，我有 11 和 13。然后，我通过执行 p x q 来计算 N。得到 143。

然后，我继续使用我的 public BigInteger findZ() 方法计算 ϕ，即 (p-1)(q-1)。

使用这个新计算的 ϕ，我想找到一个数字，或者更确切地说，创建一个遵循 1<(e)<ϕ 或简单 gcd(e,ϕ) = 1 的 e 变量因此，我最初设置 temp等于我的常数 ONE（等于一）+ 1 以满足范围。然而，在连续调试尝试之后，循环永远找不到 GCD 等于 1 的值，我创建了一个常量来表示，因为我需要使用 BigInteger。这有什么原因吗？

这是我的代码。

import java.math.BigInteger;

public class RSA 
{
//Intialize the variables.

private BigInteger p;
private BigInteger q;
private BigInteger n;
private BigInteger z;

final private BigInteger ONE = BigInteger.valueOf(1);


public BigInteger getP()
{
    return p;
}

public BigInteger getQ()
{
    return q;
}

//Computes N, which is just p*q.
public BigInteger findN()
{

    n = p.multiply(q);


    return p.multiply(q);
}


public BigInteger findZ()
{
    long pMinusOne = p.intValue() - 1;
    long qMinusOne = q.intValue() - 1;


    z = BigInteger.valueOf(pMinusOne * qMinusOne);

    return z;
}


public BigInteger getE()
{
     int temp = ONE.intValue() + 1;

     BigInteger GCD = BigInteger.valueOf(temp);

     while (GCD.gcd(z).compareTo(ONE) != 0)
     {
         temp++;
     }



    e = BigInteger.valueOf(temp);

    return e;
}

}

非常感谢任何帮助。

谢谢！

Answer 1

既然你寻求帮助，我会回答你的问题并提供其他提示。

如何获得e

一个技巧是在检查是否相等时使用 equals() 而不是 compareTo()。有时这可以减少完成的工作量，也更容易阅读。

你的代码中最大的错误是 temp 用于设置 GCD 的原始值，但 没有 link temp 到 GCD。他们保持断开连接。如果您稍后更改 temp，GCD 将不会知道并且不会更改。您需要直接在 GCD 中加一。下面是一些示例代码：

BigInteger e = BigInteger.valueOf(3);
while (! phi.gcd(e).equals(BigInteger.ONE)) {
    e = e.add(BigInteger.ONE);
}

查看BigInteger的方法

通过使用您最喜欢的搜索引擎并搜索 BigInteger 8 API，了解您可以轻松地使用 BigInteger 做什么。 8 代表您正在使用的 Java 版本，所以它可能会改变。 API 用于方法列表。

在搜索结果的前面，您应该找到 this API page。 BigInteger有很多好用又方便的方法，不妨看看。它甚至有一个构造函数，可以为您提供任意大小的 BigInteger，它很可能是素数，这对于为新的随机 RSA 密钥生成素数非常有用。

使用BigInteger的内置常量

不要重新创建以下常量（显示在上面的 API 页面中）：

• BigInteger.ZERO
• BigInteger.ONE
• BigInteger.TEN

切勿将 BigInteger 转换为 long，除非您确定它适合

您正在将 BigInteger 转换为 long，这是个坏主意，因为有很多 BigInteger 不适合 [=31] =], 给你不正确的结果。为了正确性（比速度更重要），直接用BigIntegers.

做算术运算

当你得到 long 时，你也经常使用 intValue()。使用 longValueExact()。就此而言，在获得 int.

时使用 intValueExact()

因此，要计算 ϕ:

BigInteger pMinusOne = p.subtract(BigInteger.ONE);
BigInteger qMinusOne = q.subtract(BigInteger.ONE);

BigInteger phi = pMinusOne.multiply(qMinusOne);

现在您知道它会给出正确的结果，即使对于更大的 BigIntegers。读起来也不难，有利于以后维护代码。

存储什么

您还应该只存储 n 和 e（以及 d 但前提是私钥）Never 存储 p、q 或 ϕ 使用 RSA，因为它们可以让您轻松地从 public 密钥中找出私钥。

一般情况下，不要在getZZZ方法中计算

你应该弄清楚 n 和 e（和 d 但前提是它是私钥）在构造函数方法中，并仅将那些存储在实例变量中。然后，您可以使用 getN() 和 getE() 方法来获取预先计算的实例变量。例如（你不必使用这段代码，它只是提供一个想法）：

public class RSA {
    private final BigInteger n;
    private final BigInteger e;
    private final BigInteger d;

    public RSA(final BigInteger p, final BigInteger q) {
        this.n = p.multiply(q);

        // Calculate phi
        final BigInteger pMinusOne = p.subtract(BigInteger.ONE);
        final BigInteger qMinusOne = q.subtract(BigInteger.ONE);
        final BigInteger phi = pMinusOne.multiply(qMinusOne);

        // Calculate e
        BigInteger e = BigInteger.valueOf(3L);
        while (! phi.gcd(e).equals(BigInteger.ONE)) {
            e = e.add(BigInteger.ONE);
        }
        this.e = e;

        // Calculate d
        this.d = e.modInverse(phi);
    }

    public BigInteger getN() {
        return n;
    }

    public BigInteger getE() {
        return e;
    }

    public BigInteger getD() {
        return d;
    }
}