Suitable Language for RSA implementation

Question

I want to implement an RSA cryptosystem algorithm for a university project and I' m trying to decide which programming language to use. I am very familiar with C so it would be a convenient choice. However, the algorithm will have to deal with very large numbers (it will include a Primality subroutine), and I have heard that using Python will result in a better implementation. Is that right?

Thank you in advance.

Answer 1

Of course you could use any language to implement RSA, even Assembler. The question is probably not about a "better" implementation, but maybe about what's easier to grasp when looking at the resulting code a couple of weeks later.

Let's recap what you would need for a RSA implementation:

• Large integer support
• modular exponentiation
• modular inverse
• primality testing for key generation

The more support the language of your choice has for these, the cleaner and easier to understand will be the result. Lower-level languages like C(++) won't have native support for large integers, but a library like gmp will provide you with everything that's necessary. Java has the BigInteger class for that.

But still, the result will probably not be as easy to understand as an implementation in a language that has built-in big integer support, such as Python, Ruby or Haskell for example. The resulting code will pretty much look like the textbook description of the algorithms that are used. On the downside, they tend to be slower than for example the highly optimized gmp code.

But since performance is probably not what you are after at this point, I would recommend to use a higher-level language. You don't have to deal with low-level maintenance and can concentrate on the task at hand, pick the one you like best or have experience in. If you want to draw from your familiarity with C, no problem, use a aribitrary-precision library such as gmp and you're good to go, too.

For the missing parts that are probably not built into the language by default, you can use the following as references:

• modular exponentiation is built-in in Python (pow with 3 arguments), for other languages you may try the "square-and-multiply" method
• the modular inverse can be retrieved from the Extended Euclidean Algorithm. gmp and the Python port gmpy2 will have these algorithms built in.
• for primality testing I'd recommend to use Miller-Rabin which is also not too hard to implement, but you could also find implementations for example in PyCrypto

Although you probably know this already, for the sake of completeness just let me warn you that this, what is called "textbook RSA" implementation, will not be secure to use in production - a lot of things have not been addressed yet. There's RSA blinding to prevent side-channel attacks, for RSA to be secure as an encryption scheme you will also need to implement some form of padding, it's crucial to use a cryptographically secure random generator for your keys etc. etc.

Answer 2

Using a scripting language or any more high level language than C (e.g. C# or Java) will most likely be easier since you don't have to deal with memory management and other tasks not really related to your project.

Answer 3

I don't know if Python will result in a "better" implementation, since better is rather subjective here. You can find numerical libraries for both that will allow you to deal with large numbers easily. Python has the advantage (imo) of having the numpy library which is very easy to read and use and is generally more human readable which often leads to easier debugging.