RSA initialiser with primes generation

[ptoffy]

New API Proposal: RSA initialiser which generates p and q

Motivation:

After #247 lands we will have an API which allows us to create RSA keys directly from the raw elements, which is great. However I think an important step would be to also add an initialiser which generates RSA keys instead of just "parsing" them, meaning that it could leverage BoringSSL to create p and q itself without relying on the user to do so. The functionality is already inside of BoringSSL (https://boringssl.googlesource.com/boringssl/+/master/crypto/fipsmodule/bn/prime.c) so we could probably just bridge to that.

Importance:

Without such API users of the library could create a SwiftCrypto RSA key, though they would still have to generate the primes used in the key themselves. This means that users would have to add a dependency on an arbitrary precision library, then write prime generation algorithms (hard to get right, even harder to get performant) and just then can they use the new SwiftCrypto APIs. JWTKit is doing so at the moment and it works, though it's obviously not nearly as optimised as it could/would be if we were using BoringSSL directly. After #247 we can remove a ton of the serialisation code for RSA keys from JWTKit and if this API were to be added too we could remove a whole lot of unoptimised code (and even a dependency). This would then also be mostly inline with other keys like ECDSA etc.

I'd be open to making a PR myself but thought I'd open an issue first to test the waters

[Lukasa]

Don't you want this function?

https://github.com/apple/swift-crypto/blob/8dafe0fdce623f65178689f2d6dea7304f7fbe75/Sources/_CryptoExtras/RSA/RSA.swift#L207

[ptoffy]

No, I want to be able to generate an RSA key based on n, e and d, such as https://github.com/vapor/jwt-kit/blob/main/Sources/JWTKit/RSA/RSA%2BKeyCalculation.swift#L7

[Lukasa]

Ah, gotcha. @simonjbeaumont I'd be happy with us adding this API surface as well, if you're happy to do so.

[simonjbeaumont]

Sure. I can pick this up at some point.

[ptoffy]

Ok I've taken a look into this out of curiosity and implemented it using RSA_new_private_key_no_crt(n, e, d), this basically creates a key without the CRT and therefore without prime factors. The problem with this approach is that this key cannot be serialised into DER or PEM and therefore fails when being used in Swift. As mentioned before, BoringSSL does have the ability to generate random primes, though it does not include an algorithm to find p and q primes which make up the RSA modulus. What I'm asking is how we can go forward with this, whether to implement something like we currently have in JWTKit (https://github.com/vapor/jwt-kit/blob/main/Sources/JWTKit/RSA/PrimeGenerator.swift#L6) which allows to find p and q and would allow using the usual RSA initialiser, or if this is too much to have in CryptoExtras and it should just be kept for the users to implement if needed

[simonjbeaumont]

BoringSSL does have the ability to generate random primes, though it does not include an algorithm to find p and q primes which make up the RSA modulus.

This is my recollection when implementing #247 too. Adding new API that bridges BoringSSL is fine—and, with RSA, we've now done this even when there's no Security.framework equivalent—but reimplementing the internals of BoringSSL is another matter.

WDYT @Lukasa?

@ptoffy forgive my ignorance, is it common for private keys in JWK format to not have the primes? My cursory read of the RFC0 and a few other resources suggested they'd come like this:

{
  "kty" : "RSA",
  "kid" : "cc34c0a0-bd5a-4a3c-a50d-a2a7db7643df",
  "use" : "sig",
  "n"   : "pjdss8ZaDfEH6K6U7GeW2nxDqR4IP049fk1fK0lndimbMMVBdPv_hSpm8T8EtBDxrUdi1OHZfMhUixGaut-3nQ4GG9nM249oxhCtxqqNvEXrmQRGqczyLxuh-fKn9Fg--hS9UpazHpfVAFnB5aCfXoNhPuI8oByyFKMKaOVgHNqP5NBEqabiLftZD3W_lsFCPGuzr4Vp0YS7zS2hDYScC2oOMu4rGU1LcMZf39p3153Cq7bS2Xh6Y-vw5pwzFYZdjQxDn8x8BG3fJ6j8TGLXQsbKH1218_HcUJRvMwdpbUQG5nvA2GXVqLqdwp054Lzk9_B_f1lVrmOKuHjTNHq48w",
  "e"   : "AQAB",
  "d"   : "ksDmucdMJXkFGZxiomNHnroOZxe8AmDLDGO1vhs-POa5PZM7mtUPonxwjVmthmpbZzla-kg55OFfO7YcXhg-Hm2OWTKwm73_rLh3JavaHjvBqsVKuorX3V3RYkSro6HyYIzFJ1Ek7sLxbjDRcDOj4ievSX0oN9l-JZhaDYlPlci5uJsoqro_YrE0PRRWVhtGynd-_aWgQv1YzkfZuMD-hJtDi1Im2humOWxA4eZrFs9eG-whXcOvaSwO4sSGbS99ecQZHM2TcdXeAs1PvjVgQ_dKnZlGN3lTWoWfQP55Z7Tgt8Nf1q4ZAKd-NlMe-7iqCFfsnFwXjSiaOa2CRGZn-Q",
  "p"   : "4A5nU4ahEww7B65yuzmGeCUUi8ikWzv1C81pSyUKvKzu8CX41hp9J6oRaLGesKImYiuVQK47FhZ--wwfpRwHvSxtNU9qXb8ewo-BvadyO1eVrIk4tNV543QlSe7pQAoJGkxCia5rfznAE3InKF4JvIlchyqs0RQ8wx7lULqwnn0",
  "q"   : "ven83GM6SfrmO-TBHbjTk6JhP_3CMsIvmSdo4KrbQNvp4vHO3w1_0zJ3URkmkYGhz2tgPlfd7v1l2I6QkIh4Bumdj6FyFZEBpxjE4MpfdNVcNINvVj87cLyTRmIcaGxmfylY7QErP8GFA-k4UoH_eQmGKGK44TRzYj5hZYGWIC8",
  "dp"  : "lmmU_AG5SGxBhJqb8wxfNXDPJjf__i92BgJT2Vp4pskBbr5PGoyV0HbfUQVMnw977RONEurkR6O6gxZUeCclGt4kQlGZ-m0_XSWx13v9t9DIbheAtgVJ2mQyVDvK4m7aRYlEceFh0PsX8vYDS5o1txgPwb3oXkPTtrmbAGMUBpE",
  "dq"  : "mxRTU3QDyR2EnCv0Nl0TCF90oliJGAHR9HJmBe__EjuCBbwHfcT8OG3hWOv8vpzokQPRl5cQt3NckzX3fs6xlJN4Ai2Hh2zduKFVQ2p-AF2p6Yfahscjtq-GY9cB85NxLy2IXCC0PF--Sq9LOrTE9QV988SJy_yUrAjcZ5MmECk",
  "qi"  : "ldHXIrEmMZVaNwGzDF9WG8sHj2mOZmQpw9yrjLK9hAsmsNr5LTyqWAqJIYZSwPTYWhY4nu2O0EY9G9uYiqewXfCKw_UngrJt8Xwfq1Zruz0YY869zPN4GiE9-9rzdZB33RBw8kIOquY3MK74FMwCihYx_LiU2YTHkaoJ3ncvtvg"
}

[ptoffy]

So the key will most often look like that (ideally, they should for performance reasons as I think that when the primes etc are not present, the key is supposed to be used without CRT, which just makes it slower and apparently not PKCS serialisable, as BoringSSL states), however it's still a valid key even without CRT components, which means we can't just remove the "without primes" initialiser. I do however agree it's less common for keys to not come with primes so the most sensible thing here might be to go with the init(n, e, d, p, q) as default and fall back to init(n, e, d) we already implemented on the off chance we are in such a case

[simonjbeaumont]

When I experimented with creating a key with RSA_new_private_key_no_crt(n, e, d), ISTR BoringSSL gave a clear error code when trying to serialize it. With that in mind, we could (hypothetically*) provide an initializer in _CryptoExtras that used this BoringSSL API and update our APIs that serialize the key to throw a very clear error as to why that isn't possible, in the case where it doesn't have enough information.

*: I don't think this is a great idea though, just putting it out there for completeness.

[Lukasa]

For what it's worth, I'm open to us porting the JWTKit implementation into CryptoExtras. We should make the API that uses it extremely hard to reach (not just a regular init, a factory function with an underscored name), but if you must do it it's probably better than we do it than that anyone else does.

[ptoffy]

Cool! I'll try making a PR