mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-12-28, 21:28   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5·67 Posts
Post Significance of 'strong primes'?

This is more of a theoretical question, but what is the importance of a 'strong prime', specifically, the second property illustrated on the Wikipedia page here:

p - 1 has a large prime factor (same for p+1). That is, p = q*k + 1 for some large prime q.

The reason for this is obvious to avoid factorization by Pollard's method (P+1 and or P-1).

What about the requirement for q = q2*k + 1 for some large prime q2 ? Why would that make any difference in attempting to discover 'p' as a factor?

For illustrative purposes, consider the prime p = 1202945084652377667350713.

We have

p - 1 = 2^3 * 3 * 43 * 1165644461872458979991

and

p + 1 = 2 * 601472542326188833675357

So p would not be (easily) discoverable by P-1 or P+1.

However, consider the prime q = 1165644461872458979991

q - 1 = 2 * 5 * 19 * 103 * 157 * 163^2 * 193 * 257 * 479 * 601

So q can be easily be discovered as a non-trivial factor of a number by Pollard's P-1 method.
So p is not a strong prime in the sense that it violates the second property (defined on the wiki page), since q is not a strong prime.

Would using p (or a prime of much larger size with properties similar to p), be cryptographically secure? Are there any vulnerabilities, or shortcuts to discovering p as a non-trivial factor?

Here is an example of a 1024 bit semiprime which is the product of 2 512-bit primes. For one of these 512-bit primes p, the largest prime factor of p-1 is less than 30000:

138159721549767274960487678291531343292183195677718885\
477432762458585326645295477987290750804285864167904260\
285769058502741794972739960985744325167453541900181842\
967770698333727012237182322587981542647540960470710720\
950595066112386963608030879176464946106762911612669456\
515659310517169085965398026696831449061

Here is another example, except for one of the 512-bit primes p, for the largest prime factor q of p-1, the largest prime factor of q-1 is less than 30000:

107384331139997712292608044829884581457955639278607711\
542022364914787793128010346462083629887762158126103633\
105530625713562415510943460073331183604568004438276690\
127457251631795244146466192372003408772110440282620183\
010777290233855191117458953532085526276946274628241292\
319115256099937324502350174777436244819


Obviously, you could easily factor the first number. If there is really any importance as to why q should also be strong, then the second number should also be easily factorable.

Last fiddled with by retina on 2021-12-28 at 22:23 Reason: Horizontal scrolling is boring. Broke up those long boring numbers.
carpetpool is offline   Reply With Quote
Old 2021-12-29, 00:29   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×1,063 Posts
Default

Quote:
Originally Posted by carpetpool View Post
Here is an example of a 1024 bit semiprime which is the product of 2 512-bit primes. For one of these 512-bit primes p, the largest prime factor of p-1 is less than 30000:

138159721549767274960487678291531343292183195677718885\
477432762458585326645295477987290750804285864167904260\
285769058502741794972739960985744325167453541900181842\
967770698333727012237182322587981542647540960470710720\
950595066112386963608030879176464946106762911612669456\
515659310517169085965398026696831449061
Code:
X=Mod(2,n);g=1;c=1;while(g==1,c++;X=X^c;g=gcd(X-1,n));lift(g)                                             
10421011604833387067190296909158836101110548573269326251685665964444162442023015134978170656789154169582637066936991754729125200455639857196601236554945537
Simple to factor.
paulunderwood is offline   Reply With Quote
Old 2022-02-04, 08:52   #3
jdcs
 
Sep 2019

1010 Posts
Default

I think the recommendation to use a large q2 is to prevent certain "cycling attacks."

If you had generated your RSA modulus as the product of 2 primes, and BOTH of those primes had small q2, then it may be possible to recover the plaintext message from the ciphertext message c by repeatedly taking c, encrypting it, taking the result, encrypting that again, etc., until you get the plaintext.

The number of times you need to repeatedly encrypt until you get the plaintext is a multiple of the q2 of the 2 primes, so you want the q2 to be big.

(In practice, if you just pick random 512-bit primes, the q2 will most likely be so large that the attacker will never be able to repeat the encryption enough times to recover the plaintext.)
jdcs is offline   Reply With Quote
Old 2022-02-04, 16:54   #4
chris2be8
 
chris2be8's Avatar
 
Sep 2009

26·37 Posts
Default

Thanks for that. So I assume there's no practical way to factor numbers by checking for small q2 (unless they are deliberately built to have an unusually small q2).

Although note 512 bit primes would be for RSA1024, which can probably be broken by the NSA, the FSB and the Chinese government if they really want to break it. The current recomendation is RSA2048 (ie 1024 bit primes).
chris2be8 is offline   Reply With Quote
Old 2022-02-04, 17:28   #5
jdcs
 
Sep 2019

A16 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
Thanks for that. So I assume there's no practical way to factor numbers by checking for small q2 (unless they are deliberately built to have an unusually small q2).
Heh, the way you would "check for small q2" is to just try a cycle attack for as long as you're willing to wait, and see if it works.

But now I'm kinda curious if the cycle attack I have in mind would actually work. If @carpetpool could generate a new RSA modulus where the q2 for BOTH primes are small, I guess I could try implementing it. But please pick something even smaller than 30000 for the upper bound of q2. If I understand the cycle attack correctly, if the q2 bound is 30000 for both primes, then I'll have to repeat the encryption at least 300002 = 900000000 times -- which is totally doable by a determined attacker, but I don't want to wait that long for a toy problem :)
jdcs is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Strong Law of Small Numbers? Christenson Information & Answers 36 2011-02-16 04:29
Strong Pseudoprime Distribution flouran Math 3 2009-06-01 05:04
A new Strong Law of Small Numbers example cheesehead Math 7 2009-02-06 20:49
Strong Pseudoprime Question amcfarlane Math 35 2006-09-02 23:02
What is the significance of prime numbers? Unregistered Math 10 2005-08-22 16:41

All times are UTC. The time now is 16:25.


Sat Aug 13 16:25:25 UTC 2022 up 37 days, 11:12, 2 users, load averages: 2.19, 1.50, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔