Implement techniques from 2020/1507 eprint?

[tarcieri]

Interesting paper which contains techniques for improving both key generation and inversion-free RSA-CRT:

https://eprint.iacr.org/2020/1507

[randombit]

Section 8 "Some of these techniques may be covered by US and/or international patents."

☢️

[tarcieri]

@randombit aah, unfortunate

[tarcieri]

I'll go ahead and close this issue then. We can potentially revisit it if the IPR situation clears up somehow (e.g. perpetual royalty-free license or thereabouts granted by the relevant patent holders)

[tarcieri]

@randombit do you have any specific recommendations for non-patented optimizations we can do instead? I see you have a semi-related post: https://randombit.net/bitbashing/posts/modular_inversion_using_crt.html

I'm also trying to consolidate our big integer code and associated algorithm implementations into the crypto-bigint crate (I mostly work on our ECC implementations) and am tracking some of the algorithms we should potentially implement here: https://github.com/RustCrypto/utils/issues/453

[randombit]

TBH I'm not totally familiar with what this crate (and the num-bigint fork) are doing so it's hard to say anything concrete. My general impression is that the best approach for RSA is the "Smooth RSA-CRT" of https://eprint.iacr.org/2007/039. IIRC this is what BoringSSL uses.