0
$\begingroup$

I am trying to implement the RSA algorithm using the C language, for learning purpose.

I was wondering how much time should we expect it to take for encrypting a message of size 1024/2048/4096bits on an average consumer computer, assuming a reasonably efficient implementation ?

For now, I am trying to generate pseudo-random numbers using the Miller-Rabin primality test, but even for 320-bits wide numbers it seems to become unfeasible in a reasonable amount of time. For sure my implementation is not efficient, but I would like to know how much more efficient I could make it.

Thanks !

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Are you talking about creating an RSA key pair, or encrypting the message once the key has been created? We don't create RSA keys very often, so it doesn't have to be super fast. $\endgroup$
    – Eugene Styer
    Commented Feb 4 at 19:42
  • $\begingroup$ @EugeneStyer creating the key, that's right. Generating the (pseudo)prime numbers is already a struggle. On my side this is absolutely not reasonable, it could take several hours for long keys so I have an issue for sure, but I don't know what would be reasonable for this algorithm $\endgroup$
    – wbs2422
    Commented Feb 4 at 20:02
  • 1
    $\begingroup$ If you have a speed problem and it's not due to using slow big integer arithmetic, see the algorithms of choice in FIPS 186-5 appendix A.1. $\endgroup$
    – fgrieu ♦
    Commented Feb 5 at 13:13
  • 1
    $\begingroup$ As you can see from the answers, your implementation is far slower than needed. If I were to guess what the problem is (based on the fact that computing $g^{(n-1)/2^\lambda} \bmod n$ for 160 bit $n$ is just barely feasible) is perhaps you are skipping the intermediate $\bmod n$ operation. You shouldn't compute $g^{(n-1)/2^\lambda}$ and then apply a modulus; you should also apply the modulus after every multiplication operation. That'll keep the intermediate values small (less than $n$), which translates to a significant improvement in speed. $\endgroup$
    – poncho
    Commented Feb 5 at 13:15
  • $\begingroup$ @poncho Actually for modular exponentiation I am already appliying the modulus at each multiplication operation; but perhaps it is my modulus function itself that is failing. I mean, not failing in term of result (for several tested inputs, the result was the same than the one given by Python) but in term of efficiency $\endgroup$
    – wbs2422
    Commented Feb 6 at 14:19

2 Answers 2

Reset to default
2
$\begingroup$

This table from a 2006 paper suggest times of 310ms/2924ms/24332ms for 1024/2048/4096-bit RSA key generation on commodity hardware.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you, this is what I was looking for $\endgroup$
    – wbs2422
    Commented Feb 4 at 22:47
  • 2
    $\begingroup$ Of course, that would be commodity hardware as of 2006. Current hardware would be significantly faster... $\endgroup$
    – poncho
    Commented Feb 5 at 2:51
1
$\begingroup$

OpenSSL's speed command is the base helper to compare your implementation on your platform. You don't need an old article or arbitrary internet library.

Run

openssl speed rsa

on your system get results then compare. I get the below on my system.

Doing 512 bits private rsa's for 10s: 365354 512 bits private RSA's in 9.99s
Doing 512 bits public rsa's for 10s: 6632923 512 bits public RSA's in 10.00s
Doing 1024 bits private rsa's for 10s: 145277 1024 bits private RSA's in 10.00s
Doing 1024 bits public rsa's for 10s: 2467123 1024 bits public RSA's in 10.00s
Doing 2048 bits private rsa's for 10s: 21029 2048 bits private RSA's in 10.00s
Doing 2048 bits public rsa's for 10s: 748543 2048 bits public RSA's in 10.00s
Doing 3072 bits private rsa's for 10s: 6886 3072 bits private RSA's in 10.00s
Doing 3072 bits public rsa's for 10s: 349552 3072 bits public RSA's in 9.99s
Doing 4096 bits private rsa's for 10s: 3038 4096 bits private RSA's in 10.00s
Doing 4096 bits public rsa's for 10s: 201612 4096 bits public RSA's in 10.00s
Doing 7680 bits private rsa's for 10s: 343 7680 bits private RSA's in 10.01s
Doing 7680 bits public rsa's for 10s: 58627 7680 bits public RSA's in 10.00s
Doing 15360 bits private rsa's for 10s: 65 15360 bits private RSA's in 10.12s
Doing 15360 bits public rsa's for 10s: 14943 15360 bits public RSA's in 10.00s

Later, it turns into a better table as;

                  sign    verify    sign/s verify/s
rsa  512 bits 0.000027s 0.000002s  36572.0 663292.3
rsa 1024 bits 0.000069s 0.000004s  14527.7 246712.3
rsa 2048 bits 0.000476s 0.000013s   2102.9  74854.3
rsa 3072 bits 0.001452s 0.000029s    688.6  34990.2
rsa 4096 bits 0.003292s 0.000050s    303.8  20161.2
rsa 7680 bits 0.029184s 0.000171s     34.3   5862.7
rsa 15360 bits 0.155692s 0.000669s      6.4   1494.3

Note that, OpenSSL uses BIGNUM as its arbitrary precision library, you may use GNU GMP or it's ports for other languages like gmpy2 in python.

Improve this answer
$\endgroup$
9
  • $\begingroup$ This answers the Q as in title and beginning, on speed of RSA, understood as not including generation. I don't know that OpenSSL's speed command times RSA key generation, as in the end of the question and the OP's comments. $\endgroup$
    – fgrieu ♦
    Commented Feb 5 at 13:08
  • $\begingroup$ @fgrieu Prime generation is probabilistic and I don't know OpenSLL has it (looked more and couldn't find). With time command one can get it, however, these are what I get 0.235s, 0,096s, 0,066s, 0,087s $\endgroup$
    – kelalaka
    Commented Feb 5 at 13:31
  • $\begingroup$ With the algorithms in OpenSSL, the distribution of duration of RSA key generation (for a given size) kinda follows a (shifted) geometric distribution, making it a bit hard to characterize precisely. And that's when we discount the time to gather entropy. $\endgroup$
    – fgrieu ♦
    Commented Feb 5 at 13:43
  • $\begingroup$ @kelakala interesting, I wasn't aware of that tool (neither of openssl at all). For sure there is a really shift between the result of my program and the result displayed by this tool. $\endgroup$
    – wbs2422
    Commented Feb 6 at 14:13
  • 1
    $\begingroup$ This and How can I prevent side-channel attacks against authentication? and our Bear's bearssl.org/constanttime.html $\endgroup$
    – kelalaka
    Commented Feb 6 at 15:30

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.