1
$\begingroup$

Which impact on security (factorization) has a common prime factor among the prime factors $P$,$Q$ of a number $N$ $$N=P\cdot Q$$ $$P=2\cdot F\cdot p+1$$ $$Q=2\cdot F\cdot q+1$$ with $F,q,p$ different primes and $F$ the biggest prime factor of $P$ and $Q$ with $$F\gg p,q$$


A potential adversary who want to factorize $N$ does know about the internal structure but does not know $F,p,q,P,Q$


For example $N$ is a $1024$-bit number with $P,Q \approx$ $512$-bit each.
$F \approx 461$-bit and $p,q \approx 50$-bit each.
Would security significantly change for larger $N,F$ but constant size $p,q$?
Or how would security change for larger/smaller $p,q$ but constant size of $N$?

--

Edit Update: It turned out a common factor is not necessary. I did some more detailed question.

$\endgroup$

1 Answer 1

1
$\begingroup$

There is a large weakness in 1024 bit products created according to the method described if you reuse F.

If N1 and N2 are both created with the same F, F can be calculated immediately:

G = gcd(N1-1,N2-1) = 2Fk.  

Factor G to get F, which is easy to spot because it is length 461 bits.

Additionally, security can be significantly weakened if the difficulty of factoring N-1 is significantly easier than factoring N.

N-1 is a composite which can be significantly easier to factor than a 1024 bit product of two 512 bit primes.

Based on the definitions and limitations of F, p and q in the question: N = (2Fp+1)(2Fq+1)

Expanding N = 4*F^2pq+2Fp+2Fq+1

Rearranging N = 2F(2Fpq+p+q)+1

N-1 = 2F(2Fpq+p+q)

After factoring N-1 you have F, an approx. 461 bit prime.

Let u be (N-1)/2F = (2Fpq+p+q)

u = (2Fpq+p+q)

Then calculate s = mod(u,2F) = p+q,

q = s-p

Substitute s-p for q and s for p+q

u = (2Fp(s-p)+s)
u = 2Fps-2Fp^2+s

This results in a quadratic in p

-2Fp^2+2Fsp+s-u = 0

p = (Fs - sqrt(F(Fs^2 + 2s - 2u)))/(2F)

q = s-p

The two approx 512 bit primes can now be calculated.

N = (2Fp+1)(2Fq+1)

Note that factoring N-1 may still take a significant amount of time requiring GNFS or CADO-NFS, but still significantly easier to factor than a 1024 bit product of two 512 bit primes.

$\endgroup$
2
  • $\begingroup$ is factoring '$N-1 = 2F(2Fpq+p+q)$' that easy? It's still an 922-bit number. How much easier is it compared to a regular used 922-bit number? Current record of a hard number is 829-bit. If it is easy. Does it significantly depend at the size of $F$? We could scale it as big as we want as long $p,q$ have a constant size. $\endgroup$
    – J. Doe
    Mar 25, 2022 at 14:46
  • $\begingroup$ ah ok, '$(2Fpq+p+q)$' may be factorized easily. How about we take care about this and set it to a small number times a $500$-bit prime? Would it be still easy? $\endgroup$
    – J. Doe
    Mar 25, 2022 at 14:56

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.