如何生成作为Zn元素的随机数(部分盲签名程序) [英] How to Generate a Random Number, Which is an Element of Zn (Partially Blind Signature Program)

问题描述

我正在尝试从

I am trying to implement a partially blind signature scheme in Java from a paper. In equation (1), it requires two random elements r and u to be generated, which must be an element of Zn.

r，u∈Zn

这是在RSA方案中，模数 n = p.q .

This is in an RSA scheme where the modulus n = p.q.

我不确定如何实现-我是否只需要生成一个随机数，该随机数不能被 p 或 q 整除?我认为可以使用 BigInteger gcd 来完成此操作，但是我不确定这是正确的.

I am not entirely sure how this may be achieved - do I just need to generate a random number, which is not divisible by p nor q? I assume this could be done using BigInteger gcd, but I am not sure this is correct.

到目前为止，我生成的参数如下( e 是值为3的 BigInteger ):

So far, the parameters I have generated are as follows (with e being a BigInteger with a value of 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参数生成的一部分.

I do not believe the value of phi is relevant to this question, it is just part of my RSA parameter generation.

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

Ideally, there would be a library that can handle said generation of r, u for me, but I have been unsuccessful finding any.

推荐答案

设计一种简单而又快速的算法来生成 Zn 的随机元素相当容易:

It is fairly easy to devise an easy and fast algorithm to generate a random element of 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 的低值会更频繁地出现.

The problem with this code is that it is biased. BigInteger only allows us to generate random numbers based on the bit length. If we only generate r based on a bit less than that of n, some values of Zn cannot be reached. If we simply use all of the bits of n but take the mod (as shown in the code) the low values of r will appear more often.

解决该问题的方法是如此频繁地生成 r ，直到它出现在 n 的范围内:

The way to solve that is to generate r so often until it is appears within the bounds of 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 不会发生这种情况.

Keep in mind that this code might run very long if n is slightly higher than a power of 2. It is best to choose p and q in a certain way that this doesn't happen.

这篇关于如何生成作为Zn元素的随机数(部分盲签名程序)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！