# Finding two primes that satisfy the conditions

I want to implement partially blind signature, and I looked at Zheng Gong's scheme. (Title: Efficient Partially Blind Signature Scheme with Provable Security)

In the scheme, there is a initialization phase. Signer S selects two large prime numbers p and q (length of p = 1024, q = 160), which satisfied q|p-1. Then chosses a generator g (element of Zp), and g^q = 1 mod p.

I wonder how can I find "quickly" the two primes that satisfy the condition (q|p-1) and the generator g that satisfy g^q = 1 (mod p).

Thank you

• DSA has the same / similar requirements, which will help you finding standards / implementations for this – SEJPM Nov 14 '16 at 12:07
• For example take a look at Diffie-Hellman. It uses safe-primes $kq+1$ so $q|(p-1)$ then choose a generator that satisfies $1 \equiv g^{q} \pmod{p}$ – kub0x Nov 14 '16 at 12:50
• BTW: the paper is 10 years old, and these security parameters are now considered insufficient. I would recommend p=2048 and q=256. – poncho Nov 14 '16 at 15:44
• FIPS 186-4 A.1 and A.2 (PDF) has the specifications you need / want using the sizes poncho recommended. – SEJPM Nov 14 '16 at 23:15