3
$\begingroup$

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 :/

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – kelalaka
    Dec 6, 2023 at 17:30
  • $\begingroup$ 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. $\endgroup$
    – poncho
    Dec 6, 2023 at 17:45
  • 1
    $\begingroup$ @kelalaka: you should make your comment the answer $\endgroup$
    – poncho
    Dec 6, 2023 at 17:46
  • $\begingroup$ @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? $\endgroup$
    – Anonymous
    Dec 6, 2023 at 17:49
  • $\begingroup$ @poncho fgrieu's answer is better and I my answer will be half since the probability of hitting a prime is need.. $\endgroup$
    – kelalaka
    Dec 6, 2023 at 22:39

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – kelalaka
    Dec 7, 2023 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.