20211228, 21:28  #1 
"Sam"
Nov 2016
5·67 Posts 
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 P1). 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 P1 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 nontrivial factor of a number by Pollard's P1 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 nontrivial factor? Here is an example of a 1024 bit semiprime which is the product of 2 512bit primes. For one of these 512bit primes p, the largest prime factor of p1 is less than 30000: 138159721549767274960487678291531343292183195677718885\ 477432762458585326645295477987290750804285864167904260\ 285769058502741794972739960985744325167453541900181842\ 967770698333727012237182322587981542647540960470710720\ 950595066112386963608030879176464946106762911612669456\ 515659310517169085965398026696831449061 Here is another example, except for one of the 512bit primes p, for the largest prime factor q of p1, the largest prime factor of q1 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 20211228 at 22:23 Reason: Horizontal scrolling is boring. Broke up those long boring numbers. 
20211229, 00:29  #2  
Sep 2002
Database er0rr
2^{2}×1,063 Posts 
Quote:
Code:
X=Mod(2,n);g=1;c=1;while(g==1,c++;X=X^c;g=gcd(X1,n));lift(g) 10421011604833387067190296909158836101110548573269326251685665964444162442023015134978170656789154169582637066936991754729125200455639857196601236554945537 

20220204, 08:52  #3 
Sep 2019
2×5 Posts 
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 512bit 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.) 
20220204, 16:54  #4 
Sep 2009
940_{16} Posts 
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). 
20220204, 17:28  #5  
Sep 2019
10_{10} Posts 
Quote:
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 30000^{2} = 900000000 times  which is totally doable by a determined attacker, but I don't want to wait that long for a toy problem :) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Strong Law of Small Numbers?  Christenson  Information & Answers  36  20110216 04:29 
Strong Pseudoprime Distribution  flouran  Math  3  20090601 05:04 
A new Strong Law of Small Numbers example  cheesehead  Math  7  20090206 20:49 
Strong Pseudoprime Question  amcfarlane  Math  35  20060902 23:02 
What is the significance of prime numbers?  Unregistered  Math  10  20050822 16:41 