Abstract. There has been a lot of recent work in the area of proving in zero-knowledge that an RSA modulus N is in the correct form. For example, protocols have been given that prove that N is the product of: two safe primes, two primes nearly equal in size, etc. Such proof systems are rather remarkable in what they achieve, but may be regarded as being heavyweight protocols due to the computational and messaging overhead they impose. In this paper an efficient zero-knowledge protocol is given that simultaneously proves that N is a Blum integer and that its factorization is recoverable. The proof system requires that the RSA primes p and q be such that p = = q = = 3 mod 4. The solution is therefore amenable for use with PKCS #1. A proof in the random oracle model is given that shows that our algorithm is secure under the integer factorization problem.