How long would it take?

Could the NSA reverse PGP encryption on a message that was iencrypted with
a 1264bit key? Do you think they could do this in a matter of hours? Why, or
why not? How long would it take? What do you know that corroborates this?

This is a genereic question, which I hope aeveryone who knows about  this
will attempt to answer. If this is not the right subject for the LIST, send
replies via EMAIL to

wesley@ctrvax.vanderbilt.edu

Thanks

re: a question about the security of RSA

This question is better asked in sci.crypt, since it involves
technicalities of number theory that are not in the purview of this
list.

Eric

There are a number of ways to attack a PGP (or PEM) encrypted
document.  The first, and most likely easiest, is to try to get
someone's private key.  Other attacks include attacks on IDEA (128-bit
keys) or RSA.

Its unclear what any of these attacks require, at this point.
Breaking IDEA would take a brute force attack (2^128 keys) unless
something better comes up.  Breaking RSA requires factoring the
modulus, unless something easier comes up.

I would expect that the time to factor a 1200bit modulus would be on
the order of a million years or more, even given technology upgreades
of the near-future.

I've seen a number-of-addition-bits to amount-of-extra-time-to-factor
ratio, but I don't remember what it is.  (order of magnitude per 10
decimal digits, maybe????)

Comments, suggestions, corrections, all welcome.

-derek

Derek Atkins says:
> Breaking IDEA would take a brute force attack (2^128 keys) unless
> something better comes up.

Its generally unwise to make the assumption that the only possible
attack on your conventional scheme is a brute force attack. Certainly
the attacks used on many previous generations of cryptosystems were
never brute force -- and certainly every generation of naive
cryptographer has said "well, using brute force it would take N years
to break my cypher". A simple vingenere cypher with a 12 letter key
would seem to be very strong indeed (stronger than DES), and yet we
know you can break one in a few moments because there are better
attacks than brute force.

We have suprisingly little in the way of general theory on what would
or would not make a conventional cryptosystem strong.  Certainly
differential cryptanalysis will not be the last thing people come up
with. Until we know everything the NSA knows, I will be hesitant to
say "unless something better comes up" and more comfortable saying
"until something better comes up."

Perry