# RSA perfect square phi

So I've been learning about RSA for quite a while (mainly by playing around in CTF competitions) and I came across an interesting problem.

The other day I was looking to create a challenge in which I needed $$\phi(n)$$ to be a perfect square, but under the condition that $$p \neq q$$.

For very small bitlengths (such as $$<= 20$$ bits) a naive approach such as the following will be enough to find such primes:

from Crypto.Util.number import *
from gmpy2 import iroot

p, q = getPrime(15), getPrime(15)

while p == q or not iroot((p - 1) * (q - 1), 2)[1]:
p, q = getPrime(15), getPrime(15)

print(p, q)


But if you're looking for 512 and 1024 bit numbers, this is like searching for a needle in a haystack.

And so, my question to you is, is there some efficient approach to do this?

I've looked all over Google, but nothing of this sort pops up :/

• Generate a perfect square torsion of small primes, randomly assign the primes to $p-1$ and $q-1$, check that $p$ and $q$ is prime with a fast primality test like Rabin Miller. Dec 6, 2023 at 17:30
• And, if you need a $pq$ that is hard to factor, you can use several not-very-small primes to create your square; it'll be more work (there might not be set that makes both $p$ and $q$ prime, and so you'll need to go through several sets), but it is still feasible. Dec 6, 2023 at 17:45
• @kelalaka: you should make your comment the answer Dec 6, 2023 at 17:46
• @kelalaka So essentially find small primes such that their product is a perfect square with 2*(desired_bitlength) bits and try to recover p and q such that p-1 and q-1 give us the same product? Wouldn't that need to check a lot of permutations when it comes to splitting the list of primes? Dec 6, 2023 at 17:49
• @poncho fgrieu's answer is better and I my answer will be half since the probability of hitting a prime is need.. Dec 6, 2023 at 22:39

We restrict to RSA modulus $$n=p\,q$$ with $$p$$ and $$q$$ distinct primes, thus $$\phi(n)=(p-1)(q-1)$$.

For any given $$(p,q)$$ such that $$\phi(n)$$ is a square, there exists $$(a,b,g)$$ with $$p=a^2g+1$$, $$q=b^2g+1$$. We have $$\sqrt{\phi(n)}=a\,b\,g$$, and $$a\ne b$$. Further that $$(a,b,g)$$ is unique if we add $$g=\gcd(p-1,q-1)$$, and then $$a$$ and $$b$$ are coprime, and $$g$$ is even.

Thus to generate the desired $$p$$ and $$q$$:

• pick random even $$g$$ of roughly $$1/4$$ the desired bit size of $$n$$.
• pick random $$a$$ of roughly $$1/8$$ the desired bit size of $$n$$, until $$p=a^2g+1$$ is prime.
• pick random $$b$$ of roughly $$1/8$$ the desired bit size of $$n$$, until $$\gcd(a,b)=1$$ (optional, see below), and $$q=b^2g+1$$ is prime, and $$b\ne a$$.

We can remove the requirement that $$\gcd(a,b)=1$$ in the generation of $$b$$, and for a fixed size of $$g$$ and $$a$$ that increases the number of $$n$$ that can be generated, which can be viewed as beneficial. However I fear this tends to increase the multiplicity of some primes in the factorization of $$\sqrt{\phi(n)}$$, which could be bad.

If it was not for the prescribed sizes, this procedure could generate any $$n$$ such that $$\phi(n)$$ is a square. I'm not sure about the size of $$g$$ that will make $$n$$ the hardest to factor.

An initial version of my answer, and the algorithm there, use $$2c$$ where there is now $$g$$. Also I restricted to $$a$$ and $$b$$ both odd, and incorrectly stated this is necessary when really it about halves the number of possible $$n$$.

Thank you so much @fgrieu for the detailed and understandable answer. I quickly implemented it in python for anyone else interested in this:

from Crypto.Util.number import *
from gmpy2 import iroot
from random import getrandbits

def generate(bitlength):
c_bitlength = bitlength // 4 # c is meant to be 1/4th of the modulus bitsize
a_bitlength = bitlength // 8 # a is meant to be 1/8th of the modulus bitsize

while True:
# Step 1: pick random c
c = getrandbits(c_bitlength)

while True:
# Step 2: pick random odd a until p is prime
a = getrandbits(a_bitlength)
p_candidate = 2 * a**2 * c + 1

if isPrime(p_candidate):
break

while True:
# Step 3: pick random odd b until q is prime and b != a
b = getrandbits(a_bitlength)

if b != a:
q_candidate = 2 * b**2 * c + 1

if isPrime(q_candidate):
phi_n = (p_candidate - 1) * (q_candidate - 1)

# Check if phi is a perfect square
if iroot(phi_n, 2)[1]:
return p_candidate, q_candidate

bitlength = 512
p, q = generate(bitlength)
print("p:", p)
print("q:", q)


Thanks again!

• Note that we are not a coding site and don't want code-only answers. We use the code to demonstrate the theory. Normally, this should be posted on GitHub and similar sites and commented on under the answer. Dec 7, 2023 at 9:33