RSA CRT parameters?

[public]

AKA dp, dq and qinv.

Should we extend the RSA private key API to include these? Probably both in __init__ as well as getters.

Some probably extremely suspect fors and againsts...

For:

• PKCS Initial commit. Migrates over basic project files, and the OpenSSL bindings #1 uses them.
• Without them as part of the key object we need to compute them whenever we send keys to any of our current backends. Slow. (How slow?) Smells a bit like doing actual crypto ourselves.
• Serialised key formats all(?) include them. (Probably all based on PKCS Initial commit. Migrates over basic project files, and the OpenSSL bindings #1.)

Against:

• Adds 3 more things to __init__.
• How do we validate them?
• Maybe not every RSA implementation actually uses CRT?
• Not strictly required, (but then we only need p, q, and e anyway.)

[Ivoz]

If they're only generated when an RSA private key is instantiated, I don't think it's very slow; certainly not slower than generation of p and q themselves.

code to generate them is just (assuming an implementation of mod_mul_inv)

    phi = (p - 1) * (q - 1)
    # d = pow(e, phi - 1, phi)
    d = mod_mul_inv(e, phi)
    dp = d % (p - 1)
    dq = d % (q - 1)
    # qinv = pow(q, p - 2, p)
    qinv = mod_mul_inv(q, p)

def mod_mul_inv(e, m):
    """ Modular Multiplicative Inverse.
        return the value x such that (x*e) mod m == 1 """
    x1, y1, x2, y2 = 1, 0, 0, 1
    a, b = e, m
    while b > 0:
        q, r = divmod(a, b)
        xn, yn = x1 - q * x2, y1 - q * y2
        a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn
    return x1 % m

[public]

Caching them on the private key object ourselves is indeed an option too. We need some benchmarks :)

[reaperhulk]

Per discussion in IRC I support adding these values as required parameters to the constructor. We can loosen this restriction in the future if we decide computing these values in Python is permissible/desirable.