Join Log in
Score:1
J. Doe avatar Crypto

Which impact on security (factorization) has a common prime factor among prime factors? $N=P\cdot Q$ with $P=2\cdot F\cdot p+1$, $Q=2\cdot F\cdot q+1$

at flag
J. Doe

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.

82
0 + 0
Score:1
MostlyResults avatar Crypto
fr flag
MostlyResults

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.

0 + 0
J. Doe avatar
at flag
J. Doe
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.
0
Reply
J. Doe avatar
at flag
J. Doe
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?
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.