From: ec1828@somewhere.edu   
      
   Sylvia Else  writes:   
      
   > Sometimes in an idle moment, I find myself wondering about possible   
   > ways to attack RSA. Spoiler alert, I haven't found one.   
   >   
   > But in passing, I found myself thinking about this:   
   >   
   > For the uninitiated, RSA is based on the fact that if p and q are   
   > large primes, then the product p*q is a large number that is   
   > computationally infeasible to factorise - which is to say, no one's   
   > found a way, though quantum computers offer a possibility.   
   >   
   > Let m be p * q, and n be (p-1)(q-1). Then RSA further depends on the   
   > fact that for any integer a, co-prime with m, a^n modulo m is 1. Since   
   > 2 will be co-prime with m, that means that 2^n modulo m is also 1. We   
   > can write that equivalently as   
   >   
   > 	2^n - 1 = k * m   
   >   
   > where k is an unknown integer. Actually, there are an infinity of   
   > possible k, but we're interested in the lowest (ignoring the trivial   
   > case of k = 0).   
      
   I suggest you should not use the word ``unknown'' here because the   
   equation is true for all integers k, as you observe on the following   
   sentence.  The equation is saying that 2^n - 1 is a multiple of m.   
   Mathematical lingo is such that ``an unknown integer'' means a /fixed/   
   number k (that we don't which it is), but your k here is not fixed.   
   (You can say ``an arbitrary integer'' instead.)   
      
   > If we knew k, then that would give us n, or a factor of n (n is never   
   > prime, it is at least divisible by 4).   
      
   Something isn't quite right here.  We trivially know the smallest   
   positive k that satisfy the equation---that's k = 1.  For example, take   
   p = 3, q = 5 so that m = 15 and n = 8.  Then the equation   
      
     2^8 - 1 = k * 15   
      
   is trivially satisfied by taking k = 1, which is the smallest /positive/   
   integer you're looking for.   
      
   So I did not really understand the rest of your post.  You seemed to be   
   looking for a factor of n.  You're then looking for a factor of   
      
     p - 1 or q - 1.   
      
   If these numbers would have /small/ factors, you could find them by   
   trial division, say.  That would indeed be a weakness.  RSA is not safe   
   if we pick p, q such that p - 1 or q - 1 have small factors.  (A keyword   
   here would be ``Pollard's p - 1 method''.)  However, Ronald Rivest and   
   Robert Silverman have argued that by just selecting large random primes,   
   we're unlikely to run into trouble.  (In other words, we don't need   
   ``strong primes'', meaning the security gain is negligible.)   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)