It appears to be the logarithm of the time taken to break into the cryptosystem without prior knowledge of the key. For example, it takes O(exp(N^(1/3))) time to break RSA with the General Number Field Sieve. O> --> O/ Sincerely, Adam P. Goucher

----- Original Message ----- From: Eugene Salamin Sent: 08/18/13 05:23 PM To: math-fun Subject: Re: [math-fun] cryptosystem speed comparison (theory)

Warren, what do you mean by "security level" ?

  --  Gene

...

________________________________ From: Warren D Smith <warren.wds@gmail.com> To: math-fun@mailman.xmission.com Sent: Saturday, August 17, 2013 9:08 PM Subject: [math-fun] cryptosystem speed comparison (theory)

...

What about RSA (as a simple cryptosystem)?

--Too slow or insecure. Say you are encrypting N-bit message using N-bit key. Then the following time and security formulas hold approximately for N large (ignoring constant factors and sometimes log factors).  "Fast" denotes fast FFT-based arithmetic. "Security" is kind of a guess, not proven at least until we know P unequal NP.

SYSTEM....TIME.....SECURITY slowRSA........N^3............N^(1/3) fastRSA........N^2*logN.....N^(1/3) slowECC.......N^3.............N^(1/2) fastECC........N^2*logN.....N^(1/2) Feistel...........N^2*logN......N

I said for my question I did not care about speed so much... but you've got to be in the right ballpark on speed.  I'll forgive a factor 10 or even 100 speed loss -- but squaring or cubing the runtime to reach same security level, that seems too much.

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun