Document PyCrypto's hilarious/sad slowmath vs fastmath BS

[bitprophet]

Background

While investigating some slow connection times for my employer, I narrowed our particular slowdown to public key authentication, and then specifically to the creation of the RSA algorithm object based on the key in question (a 2048-bit RSA key).

Searching around for why this operation would be slow led me to #270 (comment) which mentions the hitherto unknown to me 'slowmath' concept in PyCrypto.

More digging found this: https://github.com/dlitz/pycrypto/blob/7acba5f3a6ff10f1424c309d0d34d2b713233019/lib/Crypto/Util/number.py#L39-L53

tl;dr you need libgmp-dev, gmp-devel or similar installed to trigger building/using of this _fastmath.so module; otherwise, you get a significantly slower Python implementation of the same logic.

In my local testing, a key that takes on average 2.5-3.5s to generate its RSA object with slowmath, takes only 0.5-0.9s with fastmath. Presumably all sorts of other operations (like regular transit encryption, vs authentication signing) are faster in this setup as well - I am still testing.

To do

• Add install documentation noting that if you install libgmp-dev etc, you may see significantly faster operations.
• Doublecheck exactly what appears faster so I can quantify that a little better meh
• Sanity check whether the average distro-distributed/built paramiko/pycrypto seems to be enabling fastmath or not, so we can quantify whether this mostly impacts from-source users or not. (I'd guess 'yes'.)

[bitprophet]

• Debian 8's python-crypto depends on libgmp10 and does appear to distribute a _fastmath.so enabled PyCypto.
• CentOS 6's PyCrypto is 2.0 and seems too old to exhibit the impl test I was looking at
• CentOS 7's is 2.6.1 (same as I was testing), also relies on libgmp, is also using fastmath

[bitprophet]

Committed to the 1.15, 1.16 and 1.17 branches, should appear in those doc subsites momentarily. Does not impact 2.0 and above because yay cryptography.io.