Extract numbers from a key

[Peter Lebbing]

On 14/08/11 13:41, Hubert Kario wrote:
> From what I learned, RSA cracking is basically an exaustive search. 
> If your "prime" is composite, it is at most half as long as a real prime would 
> be.
> 
> So, instead of a ~1024 bit prime you have a ~512 bit prime, which are tryvial 
> to crack.

Yes [1], but it depends on your search space (and the route through it). You are
trying to find two 1024 bits long primes, not shorter ones.

The most naïve method would be:

pick a 1024-bit random number a
pick a 1024-bit random number b
n = a*b? yes -> done!
  no -> again

Now, there is no reason why you would find 'a' quicker if a were composite. It's
still just one of those 1024-bit long random numbers. This naïve method doesn't
use the fact that a and b are prime at all.

If, however, you *know* 'a' is composite, you can speed up, yes. But you do not
know.

By the way, if 'a' is composite, there is nothing which says that it has ~512
bit prime factors. The degenerate case is a 1023-bit prime times two :).

> Mind that I learned RSA 5 years ago during 2 hours of a 20 hours course on 
> cryptography, so it may be even easier to crack encryption using composite 
> numbers.

Or harder :).

I have also learned a piece of the underlying mathematics, but it is long enough
ago that I happily postulate that I'm pretty sure that given n and e, d can only
be one value. And then I grab the Handbook of Applied Cryptography and learn
that you can use both phi and lambda to determine it, and lambda might give a
smaller d. Which obviously means d is not unique. And that I'm wrong.

Peter.

[1] Actually, a 1024-bit RSA key is considered secure, and that consists of two
512-bit primes. Now, a 512-bit RSA key, yes, those are crackable, but not
512-bit primes. But it's the thought that counts, not the actual numbers, so
this is just a footnote.

-- 
I use the GNU Privacy Guard (GnuPG) in combination with Enigmail.
You can send me encrypted mail if you want some privacy.
My key is available at http://wwwhome.cs.utwente.nl/~lebbing/pubkey.txt