Re: RSA moduli sizes

On Apr 7, 6:55 am, pubkeybreaker <pubkeybrea...@xxxxxxx> wrote:
On Apr 6, 10:37 pm, Tim Smith <reply_in_gr...@xxxxxxxxxxxxxxxx> wrote:





In article
 pubkeybreaker <pubkeybrea...@xxxxxxx> wrote:
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.

Mr. Ashwood is talking about when generating the modulus.  A common way
to generate a 2n bit modulus is to do something like this:

   genm:
      p = RandomPrimeUpTo(2^n)
      q = RandomPrimeUpTo(2^n)
      m = p q
      if m is not a 2n bit number
         goto genm

The if statement is "verifying that the top bit is set".

This better not be a common way.  It violates cryptographic
standards. And it fails to ensure that p and q both have the
correct length.  And, if you knew anything about statistics
you would realize that you are generating a sample by rejection.
But the rejection criterion you give (mn has 2n bits)  is non-linear
and ensures that p,q are no longer iid. Your criterion rejects
by sampling the JOINT distribution.  Do you even know what that is???

And once again, you are not verifying that the top bit is lit.
It is always lit.  You are verifying that the product has the
desired length.  They are DIFFERENT.

Instead, do what I told you to do several posts back.
Generate p,q uniformly at random from an interval such that
their product is GUARANTEED to have 2n bits.  This is trivial.

And people wonder why I lose patience.

May I suggest that you people stop presenting your own 'pet'
ideas and go out and STUDY this subject????  Read some books.
Read IEEE 1363 and FIPS-140 and X9-80 and X9-31, etc. etc.
Stop prattling!  Leave design of algorithms (such as the
erroneous one given above) to people who have studied how to
do it.- Hide quoted text -



No pithy comebacks about how rude I am being??????
.

Relevant Pages

  • 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: 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 ... The if statement is "verifying that the top bit is set". ... 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 ... The sentence about "forcing the complexity as high ... two primes, uniformly at random, from a specified interval. ...
    (sci.crypt)
Quantcast