Loading ...
Sorry, an error occurred while loading the content.

6250Re: [PrimeNumbers] Re: new kind of numbers?

Expand Messages
  • Phil Carmody
    Apr 4, 2002
    • 0 Attachment
      --- hislat <hislat@...> wrote:
      > --- In primenumbers@y..., Phil Carmody <thefatphil@y...> wrote:
      > > --- Hislat Nasanov <hislat@y...> wrote:
      > > > Is it new kind of numbers(modulo)?
      > > >
      > > > Our researches show, that in RSA cryptosystems it is
      > > > impossible to use as the modulo product of such prime
      > > > numbers P1, P2, for which ((P1*P2)-1) will be multiple
      > > > to (P1-1) + (P2-1).
      > >
      > > What do you mean by 'it is impossible to use'.
      >
      > What I means? Please visit to our site
      > http://hasanov.ilm.uz/prime6e.htm You can find answer for your
      > question. >

      I think I see what your attack is now.
      The property you've found is a real one. However, as I said before,
      it doesn't make RSA _impossible_, simply _weaker_.
      However, it appears that the main property that makes them weak is
      smoothness.

      in 91, 13-1 is 3-smooth, 7 is 3-smooth.
      in 481, 13-1 is 3-smooth, 37-1 is 3-smooth.
      in 18721, 18721 != 97*151, so your page needs correcting, but anyway,
      97-1 is 3-smooth, 193-1 is 3-smooth.

      Basically you've found numbers that can be split using P-1 factoring
      using exponent P1.P2-1. This exponent is less likely to split most
      numbers than a traditionally chosen exponent (product of small prime
      powers). You've used this new attack to crack something that can be
      cracked using P-1 with exponent 2^5.3^2. i.e. there's already a
      simpler attack against these numbers.

      But it's /already/ recommended that primes do not have smooth P-1 or
      P+1, which would make the product easily factorable.

      Can you find an example which wouldn't be immediately thrown out by
      looking at the factors of P1+/-1 and P2+/-1?

      Can you find any examples amongst the 'safe' primes?

      Don't get me wrong, you've found a very interesting property (I must
      have spent half an hour bouncing equations and relations around
      before writing this, it was quite fun trying to get to the root of
      it), it's just that it seems to be contained inside a more general
      property that is already defended against.

      Phil


      __________________________________________________
      Do You Yahoo!?
      Yahoo! Tax Center - online filing with TurboTax
      http://taxes.yahoo.com/
    • Show all 10 messages in this topic