Re: RSA moduli sizes

On Apr 5, 12:53�am, "Joseph Ashwood" <ashw...@xxxxxxx> wrote:
<1.41...@xxxxxxxxx> wrote in message

news:bae59f14-fd65-4fc2-8f10-db06c729134c@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Not that I want to rock the boat in this heated discussion but, is it
not the case that by demanding that the most significant bit of an N-
bit RSA modulus be 1 we are effectively turning it into an (N-1)-bit
modulus?

Since the entire modulus is public there is no uncertainty. The difficulty
is in determining the factors of the modulus. Since the best known factoring
algorithms have their running time dominated by the magnitude of the number
being factored, verifying that the top bit is set forces the complexity as
high as possible.

More gibberish. It is NEVER the case that one verifies that the
top bit is set. The top bit is ALWAYS set and does not need to be
verified!!!!! The sentence about "forcing the complexity as high
as possible" is also nonsense. One does not "force the complexity"
in any way. The run-time complexity depends only on the SIZE
of the modulus. A 1024-bit integer is larger than a 1023-bit integer.
But BOTH have the most significant bit lit.

If you want more security, just choose a larger modulus.

Doesn't what I say get through???



This of course has to be balanced against the need for
random selection of primes,

What? This is total nonsense. Your discussion about "balancing
the need for random primes" is meaningless drivel. One selects
two primes, uniformly at random, from a specified interval. The
interval is chosen so that their product has the required size.
PERIOD.

Please explain how you think that requiring a 1024-bit (or 1023-bit
etc)
modulus somehow restricts the 'random' selection of primes.

IT DOESN'T. It merely determines the interval in which one looks
for the primes.


but this is a much softer requirement, a
1024-bit modulus requires less than 2^80 work to factor, so a 1024-bit
modulus with 80-bits of entropy in the selection is sufficient to force the
factoring algorithm.


Please define what you mean by "force the factoring algorithm"???

This is not a mathematical statement.

We have the blind leading the blind.
.

Relevant Pages

  • Re: Number Theoretic transform : dimensions
    ... multiplications modulus p are used instead of complex ... That's usually not really a reduction in complexity. ... do p modulus such that it's still simpler than complex ... power-of-two transform lengths up to 2^20, and fits snugly into a 32-bit ...
    (comp.dsp)
  • Re: RSA moduli sizes
    ... bit RSA modulus be 1 we are effectively turning it into an -bit ... verifying that the top bit is set forces the complexity as ... you are not verifying that the top bit is lit. ...
    (sci.crypt)
  • Re: RSA moduli sizes
    ... bit RSA modulus be 1 we are effectively turning it into an -bit ... verifying that the top bit is set forces the complexity as ... But BOTH have the most significant bit lit. ... But the rejection criterion you give  is non-linear ...
    (sci.crypt)
  • Re: RSA moduli sizes
    ... bit RSA modulus be 1 we are effectively turning it into an -bit ... Since the best known factoring ... verifying that the top bit is set forces the complexity as ...
    (sci.crypt)
  • Re: RSA moduli sizes
    ... bit RSA modulus be 1 we are effectively turning it into an -bit ... verifying that the top bit is set forces the complexity as ... The if statement is "verifying that the top bit is set". ... you are not verifying that the top bit is lit. ...
    (sci.crypt)