0
$\begingroup$

I'm learning math of RSA. I'm interesting about realisation of computing private expoinent in source code.

Where can I read a well made implemenation? (I prefer Python or Go implementation) I tried to read OpenSSL code, but couldn't find where private exponent computes

PS I have some sense, that this code is in bignum module, but I can't find.

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to crypto-SE, but notice our position on homework, and programming problems. Hints: If all you want is an expression yeilding the value of a valid $d$ given valid $p,q,e$, that fits in 21 characters in python 3.8 and higher using pow. The exercise is less easy with earlier Python, or if you can't use pow, or if you want the lowest possible positive $d$, especially if you can't use libraries. $\endgroup$
    – fgrieu
    Commented Jul 8 at 18:07
  • $\begingroup$ @fgrieu No it's not my homework Main idea in question, read well made implementation of computing private exponent(d) I tried to find it in OpenSSL source code, but couldn't $\endgroup$
    – Andrew
    Commented Jul 8 at 18:17
  • 1
    $\begingroup$ One place in OpenSSL where it computes $d$ is there. Another is there. But this is far from what I'd recommend to learn the math of RSA. What about that? $\endgroup$
    – fgrieu
    Commented Jul 8 at 19:58

1 Answer 1

2
$\begingroup$

There are lots of things that C and C++ are good for, but readability is - in my opinion - not one of them. C has a simple syntax but requires a lot of code to be able to execute a task (e.g. regarding memory and resource management, error handling, ...) and C++ has a very complex language model and many distinct libraries to do basic things like big integer arithmetic.

In this case you could e.g. look at the Java implementation of the Bouncy Castle RSA key pair generator here. It is very readable code and it even contains comments (which is somewhat of a rarity for Bouncy Castle to be honest).

Some complexity is hidden by the BigInteger class, but since Java has been open-sourced as well, it should not be hard to look up the functionality. Note that many of the BigInteger OPS may actually be replaced with CPU-native instructions (intrinsics) when they are run on a decent desktop or server grade virtual machine. Then again, that does make the code more easy to understand.

Java is fully big endian, which makes understanding integer ops a bit easier, at least for humans rather than machines. The RSA specifications are big endian as well. Not as clean as Python maybe, but it's still pretty intuitive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.