A couple of nits

[sfluhrer]

I'm reviewing the code for use in my company, and while I found no major problems at all (congratulations), I did find a few minor points, and I thought I might as well bring them to your attention (and if you decide to ignore them, that's fine).

• RSA private key consistency check (rsa.py, line 590 and following): you check whether d is relatively prime to n; while this is extremely probable to be the case, it's not actually a problem (either from a correctness or a security standpoint) if that's not the case. On the other hand, you don't check dp or dq (and you should; if those are wrong, the private operations don't work)

• RSA generate (rsa.py, line 394 and following); the comments say that "The algorithm closely follows NIST FIPS 186-4"; well, it is kinda similar, however it's not the NIST algorithm (it doesn't generate both primes from a single seed), and so is not the NIST approved algorithm.

• Shamir Secret Sharing code; the check-in comments state that this is constant time; actually, the inversion code is not. You could fix this by either changing the inversion to compute x (2128 - 2), or by blinding it (like you did in the ECDSA inversion code)

[Bl4omArchie]

While I was reading the code I saw in the generate function for RSA that the public exponent e could be anything above 3. Did a big e could lead to issue ? Except for performance issue