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.
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.
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
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 > >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
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.
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
participants (5)
-
catalyst-remailer＠netcom.com -
jamesd＠netcom.com -
NetSurfer -
Perry E. Metzger -
Roger Bryner