Laymans explanation of RSA encryption

[Fusion_power]

http://arstechnica.com/security/2013...-cryptography/

[jasonp]

Actually the post is more about elliptic curve crypto than RSA...

[R.D. Silverman]

Originally Posted by jasonp

Actually the post is more about elliptic curve crypto than RSA...

It also makes some grossly wrong assertions. e.g.

"These factoring algorithms get more efficient as the size of the numbers being factored gets larger. The gap between the difficulty of factoring large numbers and multiplying large numbers is shrinking as the number (i.e. the key's bit length) gets larger. As the resources available to decrypt numbers increase, the size of the keys needs to grow even faster. "


This is totally wrong. The gap between multiplying large numbers
and factoring large numbers is GROWING as the numbers get larger.
Multiplying N by N takes time M(N) := O(log N loglog N logloglog N) via
convolution methods. This is polynomial in log N. Factoring takes
(via GNFS) L(N, 1/3). This is sub-exponential.

lim N-->oo L(N,1/3)/M(N) --> oo.

The assertion is so grossly and trivially wrong that it makes me wonder if the
author knows what the f*ck he is doing.

[ewmayer]

Originally Posted by R.D. Silverman

It also makes some grossly wrong assertions. e.g.

"These factoring algorithms get more efficient as the size of the numbers being factored gets larger. The gap between the difficulty of factoring large numbers and multiplying large numbers is shrinking as the number (i.e. the key's bit length) gets larger. As the resources available to decrypt numbers increase, the size of the keys needs to grow even faster. "

Perhaps the author has access to a quantum computer? :)

I mention this because speaking of "gross inaccuracies", PBS Nova last week aired a segment on interesting science going on as one moves down the temperature scale - very close to 0Kthey discussed Bose-Einstein condensates and quantum computers, which will revolutionize tasks such as "factorization and ... weather prediction." I was rather taken aback to hear such abject nonsense coming from writers for that show.