[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.
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
Well then, what about the only mathematically provable secure cryptosystem, the one-time key. Warren, every time someone has suggested a cryptosystem, you have complained. Help us to better target our suggestions by explaining your application. -- 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
participants (2)
-
Eugene Salamin -
Warren D Smith