0

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

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

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.

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);

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

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

lb-99
  • 33
  • 5
  • Define your terminology within the question. Your question should be self-contained, people shouldn't have to go to an external link to find out what you're asking. – pjs Feb 16 '21 at 20:58
  • @pjs I have added some more info, I think this should help. – lb-99 Feb 16 '21 at 22:15
  • I suspect you want something like the [Chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Encryption). It's been decades since I've looked at this stuff, so I'm throwing you a pointer rather than an answer. – pjs Feb 16 '21 at 22:45

1 Answers1

2

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);
}

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.

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;
}

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.

Artjom B.
  • 61,146
  • 24
  • 125
  • 222