From: ec1828@somewhere.edu   
      
   Richard Kettlewell  writes:   
      
   > Ethan Carter  writes:   
   >> 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   
   >   
   > Noting again for reference that conventional notation here is n=pq.   
      
   Noted.  (I wanted to keep most of the choices of the OP.)   
      
   >>> 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.)   
   >   
   > I covered this in another post. For a given RSA key there’s only one k   
   > and it’s straightforward to write down an expression for it, just not   
   > practical to compute the value of that expression. I don’t know why   
   > Sylvia thought there might be more than one, or for that matter why k=0   
   > would work since it’s obviously not possible for any RSA key.   
   >   
   >>> 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.   
      
   What was I thinking?  I somehow thought 2^8 = 16.   
      
   >> 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.   
   >   
   > p-1 and q-1 are always divisible by 2, as small a factor as you can   
   > possibly get.   
      
   You're right.  I'm totally mistaken.  Scratch it all.  Thanks!   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)