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

Expand Messages
• Apr 4, 2002
--- 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