RSA Key Size & QP

A wild card here is the recent work in quantum computing,  done
at AT&T and reported in a recent post by Pal Vitanyi.
With a specialized quantum computer (not clear yet whether one could
economically built it, but it's theoretically possible) one
can factor in polynomial time (computational class "QP", or
something like that).  If cycles on such a computer would be,
say, 1,000 times more expensive than on your PC, then
cracking the key would be 1,000*O(keysize^c) more expensive than 
generating it, not 1,000*O(c^keysize).  Having a keysize of, say,
8 kbits instead of 1 kbit in this circumstance is not at all overkill; 
it makes a practical economic difference.   Of course if your 
info is _very_ valuable and the polynomial is of small degree, 
even a large key size won't help much.

If such a device was built, we'd want to switch to a cryptosystem 
whose inverse is not in QP; but some of our current communications
would be compromised.  If a QP machine is with even small probability
feasible within the next few decades (or whatever your timeline 
of concern is), it makes sense to use larger key sizes.

catalyst-remailer@netcom.com writes
> 
> A wild card here is the recent work in quantum computing,  done
> at AT&T and reported in a recent post by Pal Vitanyi.
> With a specialized quantum computer (not clear yet whether one could
> economically built it, but it's theoretically possible) one
> can factor in polynomial time (computational class "QP", or
> something like that).  If cycles on such a computer would be,
> say, 1,000 times more expensive than on your PC,

The limit will not be cost per cycle, but the problem of maintaining
quantum coherence over a large area for a long time.

My guess would be that some time in the next thirty odd years
we will see quantum computers that can maintain quantum coherence
over a few hundred bits of memory for a few hundred CPU cycles.

This will make possible many useful and interesting tasks that
classical computers cannot do, but I doubt that cracking thousand
bit keys will be one of those tasks.

If cracking big keys using quantum computers does become feasible
in the near future, we will have several years of advance warning,
during which we will switch to some alternative, less convenient
cryptography system.



-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our    |
property, because of the kind of animals that we |         James A. Donald
are.  True law derives from this right, not from |
the arbitrary power of the omnipotent state.     |         jamesd@netcom.com

On Wed, 22 Jun 1994 catalyst-remailer@netcom.com wrote:
> something like that).  If cycles on such a computer would be,
> say, 1,000 times more expensive than on your PC, then
> cracking the key would be 1,000*O(keysize^c) more expensive than 
> generating it, not 1,000*O(c^keysize).  Having a keysize of, say,
> 8 kbits instead of 1 kbit in this circumstance is not at all overkill; 
I would say this can be extended and made a general rule.  You should 
always take some reasonable ammount of time(say 5 min) to encrypt your 
most sensitive messages, even if you have a 12 crays and a connection 
machene.  The algorithim can be viewed as giving you an economic 
advantage, and worying over spending $.01 vs $.0001 is not just stingy, 
it is dangerous.

Roger.

In the folder RSA sends out in response to inquirys they have a nice
explanation of brute-force factor-cracking estimated computation time
on several platforms at several key sizes.  I'll see if I can dig it
up (I know it's *somewhere* on my desk here...)



-NetSurfer

#include standard.disclaimer

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
==  =    = |James D. Wilson        |V.PGP 2.4:   512/E12FCD 1994/03/17 >
 "  "    " |P. O. Box 15432        |     finger for full PGP key        >
 "  " /\ " |Honolulu, HI  96830    |====================================>
\"  "/  \" |Serendipitous Solutions|    Also NetSurfer@sersol.com      >
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Roger Bryner says:
> I would say this can be extended and made a general rule.  You should 
> always take some reasonable ammount of time(say 5 min) to encrypt your 
> most sensitive messages, even if you have a 12 crays and a connection 
> machene.

First of all, you behave as though time is not a factor. If it takes
five minutes to start every phone conversation you have, well, you've
just given people a big incentive not to use any encryption at all.

Second of all, all this rubble bouncing is insane. The NSA or whomever
isn't stupid. They will not attack you where you are strong -- they
will attack you where you are weak. Do YOU do all your typing in a
faraday cage? No? Then why the hell bother?

Lastly, you behave as though cost is not a factor. Well, you don't
live in the real world, then. Cost is ALWAYS a factor. 

Perry

Hello, 
Are there archives for this mailing list?

Roger.

Is there any company that sells pre-made true unpredictable random number 
sources?  Please forwared information if you know where I could buy one.

Roger.