Re: How easy is it to break 128bit RSA

From: Simon Hunt (nospam_at_never.com)
Date: 11/20/03 

Date: Thu, 20 Nov 2003 16:43:03 -0000

Actually your math is mostly wrong. RSA is an asymmetric algorithm meaning
there are NOT 2^128 possible keys in a 128bit RSA key, there are about as
many as there are factors of the primes. Off the top of my head I think
128bit RSA is about 2^16 unique keys, a few seconds of processor time
perhaps.

Simon.

the following link may help understand..
http://www.sandelman.ottawa.on.ca/ipsec/2000/12/msg00045.html

"Brad Murray" <bjm-nntp@vsca.ca> wrote in message
news:BK8ub.72305$jy.70940@clgrps13...
> Amol <deshmua@ececs.uc.edu> wrote:
> A> I wanted to know what would be the estimated time required to break
> A> 128 bit RSA on a desktop PC. Also what should be the key size if it is
> A> required that the encryption not be broken within a couple of months
> A> using the fastest computer on which the craking program is run?
>
> It depends. It depends on how the cipher is being used (most modes
> leak information, reducing the total secrecy substantially). If you
> are asking "how long to brute force a 128 bit key" the answer is "a
> hella long time". Do the math yourself: you have 2^128 items to
> iterate through. Assume you can do 1 iteration every 2^-20 seconds
> (nice and fast). That's 2^108 seconds to exhaustively search. You're
> probably in danger by halfway through, so call it 2^107 seconds.
> That's 5,145,207,915,690,428,823,933,853 years. If your mode leaks
> data at rates comparable to CTR or CBC, then you cut that down much
> more (2^128 goes down to 2^64 after leakage, then 2^44 for
> computation, half that for a 50% or so hit to 2^43 and that's only
> 278,922 years.
>
> Of course, if RSA has some known defect that further leaks
> information, then factor that into your calculation. Once done,
> change your keys rather more frequently than the result you get.
>
> Your mileage may vary.
>
> --
> Brad Murray * "When cryptography is outlawed, bayl bhgynjf jvyy
> VSCA Founder * unir cevinpl." -- Kevin McCurley

Relevant Pages

  • Re: A question about modular exponentiation
    ... > One can also compute the private exponent in a slightly different way: ... > I ran tests on this, generating primes to produce RSA keys ... Therefore, d is inverse of e both for mod lambda, and for phi. ...
    (sci.crypt)
  • Re: RSA key size and safety
    ... assymmetric (RSA) will be safe for the next 50 years. ... LEAST 768-bit RSA keys. ... so any time estimates were likely based ... your public keys your system is fairly dead in the water. ...
    (sci.crypt)
  • Re: How easy is it to break 128bit RSA
    ... SH> Actually your math is mostly wrong. ... RSA is an asymmetric algorithm meaning ... SH> there are NOT 2^128 possible keys in a 128bit RSA key, ...
    (comp.security.misc)
  • Re: SSH keys: RSA vs DSA
    ... >> Ssh protocol version 2 can use RSA as well as DSA keys. ... > DSA is an old and fairly weak encryption, ...
    (comp.os.linux.security)
  • Re: CryptoAPI Hard Coding Keys, Help
    ... You can use RSA, DH/DSA or ECDSA - but you should first check what Windows ... // key container name. ... printf(" Create a default container and generate keys \n"); ... "Generating Keys \n"); ...
    (microsoft.public.platformsdk.security)