mersenneforum.org Significance of 'strong primes'?
 Register FAQ Search Today's Posts Mark Forums Read

 2021-12-28, 21:28 #1 carpetpool     "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 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.
2021-12-29, 00:29   #2
paulunderwood

Sep 2002
Database er0rr

22×1,063 Posts

Quote:
 Originally Posted by carpetpool 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.

 2022-02-04, 08:52 #3 jdcs   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 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.)
 2022-02-04, 16:54 #4 chris2be8     Sep 2009 94016 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).
2022-02-04, 17:28   #5
jdcs

Sep 2019

1010 Posts

Quote:
 Originally Posted by chris2be8 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 :)

 Similar Threads Thread Thread Starter Forum Replies Last Post Christenson Information & Answers 36 2011-02-16 04:29 flouran Math 3 2009-06-01 05:04 cheesehead Math 7 2009-02-06 20:49 amcfarlane Math 35 2006-09-02 23:02 Unregistered Math 10 2005-08-22 16:41

All times are UTC. The time now is 18:29.

Sun Aug 14 18:29:48 UTC 2022 up 38 days, 13:17, 2 users, load averages: 0.96, 0.98, 0.95