The implementation uses the method described in p24 of this CL paper when generating the issuer public key, which involves sampling a random quadratic residue S and from that computing random powers to generate additional residues. However, as stipulated in the paper, this method only works if S is a generator of the group of invertible quadratic residues mod n. This can be checked by verifying that it has order equal to the product of the Sophie-Germain primes p' and q' used to construct the safe RSA modulus n, but this check is not done in the implementation.
Since p' and q' are coprime and are primes, every invertible quadratic residue has order 1, p', q' or p'*q'. It therefore suffices to check that S is not 1, that S^p' is not 1 mod n, and S^q' is not 1 mod n.
Added this check in a separate PR from my other one but both need to be integrated - hope it makes sense!
doowt
commented
1 year ago
The implementation uses the method described in p24 of this CL paper when generating the issuer public key, which involves sampling a random quadratic residue S and from that computing random powers to generate additional residues. However, as stipulated in the paper, this method only works if S is a generator of the group of invertible quadratic residues mod n. This can be checked by verifying that it has order equal to the product of the Sophie-Germain primes p' and q' used to construct the safe RSA modulus n, but this check is not done in the implementation.
Since p' and q' are coprime and are primes, every invertible quadratic residue has order 1, p', q' or p'*q'. It therefore suffices to check that S is not 1, that S^p' is not 1 mod n, and S^q' is not 1 mod n.
Added this check in a separate PR from my other one but both need to be integrated - hope it makes sense!