RSA Real World Implementation

[Michael Wojcik]

Haven't seen a response to this one yet, so I thought I'd provide what I could.

> From: openssl-users <openssl-users-bounces at openssl.org> On Behalf Of
> Dingsi Bumsi
> Sent: Tuesday, 4 April, 2023 17:41
> 
> As a student of computer science with focus on security I would like to see
> how RSA is implemented in the real world. I was warned not to write my own
> implementation of RSA encryption due to the high risk of bugs und
> vulnerability issues, which would be dealt with much better in a battle proven
> lib like openssl. So I would like to see how it is done properly. :-)

OpenSSL would not be my choice for this. Whatever the virtues of OpenSSL, the code is not written for readability. In fact I wouldn't advise anyone to study a "real world" RSA implementation in C at all; while C is the language I use the most (and the only one for which I've memorized a non-trivial portion of the standard), its low expressiveness, required scaffolding, and aspects of common C culture (such as short, meaningless identifiers) make it a difficult to learn concepts from.

You might look at, say, Go's RSA implementation (https://pkg.go.dev/crypto/rsa, source at https://cs.opensource.google/go/go/+/master:src/crypto/rsa/), for example; even if you don't know Go, it's probably faster to learn Go and then learn from Go's implementation. And much of Go's cryptography was, I believe, written by Filippo Valsorda, who's both a good cryptographer and good at explaining cryptography; his blog is worth reading.

> I did already find the source code on github under
> https://github.com/openssl/openssl/tree/master/crypto/rsa
> 
> Tbh I find it yet quite overwhelming and cumbersome to work through all
> those rather cryptic (pun intendet) looking lines of source code and figure out
> what they do.

Yes, that's what I would expect. Correct cryptographic code is difficult to begin with; C is difficult; and OpenSSL is not particularly readable C.

> Is there further documentation available about how the source code files work
> together, e.g. which part of the library/file plays which role?

There might be some material along those lines in the OpenSSL docs and wiki; that should be your starting place, if you're determined to understand the OpenSSL source code.

(After that, and looking at the source, my approach would be to debug through some operations.)

>  From the manpages I assume that several libraries must be used in order to
> en-/decrypt a message, so I guess documentation on how to use the openssl
> library in C source code might help too.

Prior to 3.0, only one OpenSSL library was, in the simple case, used for RSA: libcrypto. With older versions of OpenSSL you might also have an engine involved, which is technically a separate (dynamically-loaded) library. In OpenSSL 3.0, we have providers, which complicate the picture. (This is another good reason not to try to use OpenSSL as your example, by the way; the provider architecture complicates the implementation in ways irrelevant to the actual cryptography.) But libcrypto is still where the most basic implementation lives, I believe (without actually checking the source).

A number of functions are involved, but functions and libraries are different things. 

> Where does the actual magic happen, meaning, where are the prime numbers
> generated and where are the messages en-/decrypted?

Aside from "crypto/rsa/*.c" I couldn't give you a definitive answer without spending time looking at the source, and possibly not without debugging through some RSA operations just to be sure.

> And one other question: Is there a reimplementation in Rust planned already?

That seems rather unlikely to me. I certainly don't recall hearing anyone talk about reimplementing OpenSSL in Rust. I don't know offhand the status of cryptography and TLS packages for Rust, but I'd think what Rust needs is its own crypto implementation, just as Go and other languages have; and if you want crypto and TLS written in Rust, that's what you'd use.

-- 
Michael Wojcik