Zn元素如何生成随机数（部分盲签名程序）

Question

我正在尝试通过 paper 在 Java 中实施部分盲签名方案。式(1)中，需要生成两个随机元素r和u，必须是Zn.

中的一个元素

r, u ∈ Zn

这是一个 RSA 方案，其中模数 n = p.q。

我不完全确定这是如何实现的 - 我是否只需要生成一个随机数，它不能被 p 或 q 整除？我假设这可以使用 BigInteger gcd 来完成，但我不确定这是正确的。

到目前为止，我生成的参数如下（e是一个BigInteger，值为3）：

        do {
            p = BigInteger.probablePrime(bitlength, rnd);
            q = BigInteger.probablePrime(bitlength, rnd);

            n = p.multiply(q);
            phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
        } while (phi.gcd(e).compareTo(BigInteger.ONE) > 0);

        d = e.modInverse(phi);

我不认为 phi 的值与这个问题相关，它只是我生成 RSA 参数的一部分。

理想情况下，会有一个库可以为我处理上述生成的 r, u，但我一直没有找到任何库。

Answer 1

设计一个简单快速的算法来生成 Zn:

的随机元素是相当容易的

public BigInteger getBiasedRandomModN(BigInteger n) {
    BigInteger r = new BigInteger(n.bitLength(), new SecureRandom());
    return r.mod(n);
}

这段代码的问题是它有偏见。 BigInteger只允许我们根据位长生成随机数。如果我们只根据n的小一点生成r，Zn的某些值是达不到的。如果我们简单地使用 n 的所有位，但采用 mod（如代码所示），r 的低值将更频繁地出现。

解决这个问题的方法是经常生成 r，直到它出现在 n 的范围内：

public BigInteger getRandomModN(BigInteger n) {
    SecureRandom rnd = new SecureRandom();
    BigInteger r;
    do {
        r = new BigInteger(n.bitLength(), rnd);
    } while (r.compareTo(n) >= 0);
    return r;
}

请记住，如果 n 略高于 2 的幂，此代码可能运行很长。最好选择 p 和 q在某种程度上，这不会发生。

Zn元素如何生成随机数（部分盲签名程序）

How to Generate a Random Number, Which is an Element of Zn (Partially Blind Signature Program)

java

random

encryption

rsa

digital-signature