Re: [Newbie] Prime factorization question

From: Mxsmanic (mxsmanic_at_hotmail.com)
Date: 10/10/03 

Date: Fri, 10 Oct 2003 05:14:33 +0200

Gregory G Rose writes:

> I think you have a problem understanding large
> numbers. Yes, there is a chance of it happening.
> But probably not in this universe.

Should I interpret this to mean that the decision to develop the modulus
as the product of two equal-sized primes is made simply to reduce the
possibility of a failure of the cipher and/or factorization of the
modulus, and not because a modulus with exactly two prime factors is
essential in some way to the proper function of the cipher?

If so, then I presume that a modulus that has more than two factors
(i.e., that is the product of something other than exactly two primes)
would still work for RSA, but with a far greater likelihood of failure,
and with far greater susceptibility to cracking through factorization.
And conversely, it would also mean that even with ideal prime factors,
RSA is not completely sound, because it can still fail if one of the
factors of the modulus is also a factor of the message being encrypted.

Is this all correct? 

-- 
Transpose hotmail and mxsmanic in my e-mail address to reach me directly.

Relevant Pages

  • A question about modular exponentiation
    ... One can also compute the private exponent in a slightly different way: ... generating primes to produce RSA keys ... with modulus length of 512, ...
    (sci.crypt)
  • Re: Factoring a number whose Euler phi is known?
    ... RSA works for any number of factors in the modulus, ... > When the modulus n is a product of 2 primes p and q, ... > and well known algorithm: ...
    (sci.crypt)
  • Re: special DH prime
    ... represent the modulus as a polynomial with *much smaller* coefficients ... Primes with low Hamming weight are, on average, easier than general ... algorithms will react on special form moduli, ... than modular integers (otherwise I would have gone for elliptic curves) ...
    (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)
  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... the product is indeed, say, 512 bits, for a 512-bit modulus. ... an N bits long product of two primes doesn't really contain N ... slightly more than 502.5 bits of entropy, so a 1024 bits long RSA ... the sieve of Eratosthenes or the sieve of Atkin. ...
    (sci.crypt)