Add RSA PKCS#1 1.5 signing

[briansmith]

There's a bunch of code to do the low-level RSA operation in GFp_rsa_private_transform in crypto/rsa/rsa_impl.c that should be used.

We need a new implementation of PKCS#1 1.5 padding (in Rust, unless there's a reason it can't be done in Rust for some reason).

We can (should, unless we're going to somehow implement blinding in Rust) use the blinding code in crypto/rsa/blinding.c. But, we need to write new Rust code that manages the pool of BN_BLINDINGs in some kind of thread-safe way. I guess this largely depends on the threading model chosen for the signing API.

NIST publishes test vectors for this, and testing using those test vectors are the minimum acceptable testing. Note that NIST's test vectors are in a format that's not really usable by ring's testing framework. The comments in src/rsa_pkcs1_verify_tests.txt explain what I did to reformat NIST's RSA PKCS#1 1.5 verification test vectors for ring; a similar thing needs to be done for the signing test vectors.

This is complicated by the fact that there's no code for deserializing RSA private keys or for serializing RSA private keys. Adding the deserialization/serialization is probably a big task on its own so it might be worth splitting into a separate bug.

See also #205 for any general requirements on signing APIs.

[briansmith]

I am not going to have time to implement this, so I'm hoping somebody will volunteer to do it. It is not hard, but it isn't going to be as easy as #206 was. I recommend looking at #206 and the conversation in 211 to get a sense of how this would go down.

[briansmith]

OK, I will break this down:

• Only full RSA keys (the ones with n, e, p, q, and all the rest of the CRT parameters) are supported. RSA keys that only have d and n are not supported.
• The formatting of the signature buffer prior to the actual RSA private key computation is the inverse of the parsing code in ring::rsa::signature_impl::VerificationAlgorithmImpl::verify. It is described at https://tools.ietf.org/html/rfc3447#section-9.2.
• The function to do the actual RSA private key computation is GFp_rsa_private_transform. Notice that it requires the full set of RSA parameters.
• Parsing RSA private keys should be done using the der submodule. In particular, der::Nested and der::positive_integer will be very useful. It would actually be very similar to parse_public_key in ring::rsa, but with more parameters to parse. The syntax is RSAPrivateKey and is described at https://tools.ietf.org/html/rfc3447#appendix-A.1.2.
• Blinding is required because the RSA code isn't 100% constant time (even though it claims to be). See BN_BLINDING, BN_BLINDING_new, BN_BLINDING_free. It looks like GFp_rsa_private_transform does all the work other than creating the BN_BLINDINGs.
• NIST has test vectors here: http://csrc.nist.gov/groups/STM/cavp/digital-signatures.html#rsa2vs. They need to be converted into the format that ring expects. See the notes at the top of https://github.com/briansmith/ring/blob/master/src/rsa_pkcs1_verify_tests.txt.

[briansmith]

This all landed! Awesome work!

In the last set of changes, I tweaked the example to match the ring style (qualifying Input as untrusted::Input, avoiding unwrap(), etc.). I also added some tests to complete(-ish) the test coverage.

Thanks a ton for doing this!

[briansmith]

I should add: #225 contains a laundry list of follow-up tasks for improving the RSA internals.