How to use RSA?

Question

I trying to use RSA to encrypt my data in Python.

I created two small (private and public) keys

e : 14918179 N : 15372757 D : 7495819 N : 15372757

I tried to encrypt a small value (10) with those keys, and it worked. But the problem is that it takes a long time to do. For example, I compared it to openssl by using a big key and long string and it worked under a second. And I know there is a third library for using RSA (not a big fan of them). I am trying to use this method to encrypt my data that is going to be sent to the server and it should do it under a second How can I do it?

do not use RSA to encrypt data (that is not only slow it is also bad for security reasons [unless you also use optimal padding...]); use RSA to encrypt a session key and encrypt the data symmetrically (i.e. with AES-GCM) using that session key. — hiro protagonist
– hiro protagonist, Commented May 6, 2019 at 6:49
While I am surely an advocate of doing things from scratch to understand the principles, I do not advice you to reinvent the wheel. Use a library if you want to encrypt data, or even better use already existing security protocols ( HTTPS, SSL, TLS) and use a library to access them. — bracco23
– bracco23, Commented May 6, 2019 at 7:05
Without seeing your code, we can't really tell why it's slow. But as a random guess, are you using the 3-argument form of pow()? If not, you should be. Also note that a simple Python script using Python's generic integer math will never be as fast as a C library specifically optimized for RSA. But with that change (and reasonable algorithms) it should at least get close to the same ballpark. — Ilmari Karonen
– Ilmari Karonen, Commented May 6, 2019 at 7:06

mksteve · Accepted Answer · 2019-05-06 08:41:12Z

I think in general your questions on performance are answered here. wikipedia : modular exponentiation

The article describes

Direct exponentiation
Memory efficient exponentiation
Binary exponentiation

Direct Exponentiation

raise to the power e and take the modulo. This is straight forward, but the size of the number pre modulo is extermely large.

Memory efficient exponentiation

Replacing the power operation with a multiply e times, allows the accumulated result to always be within the modulo range. This limits the size of the bignum and speeds up the operation.

Binary exponentiation

If you convert the power to a binary number

if e = 13 => 1101 pow(n, 13) = pow( n, 8) * pow(n,4) * pow(n, 1) So for an m bit exponent, then only about m operations need to be done.

Combining the memory efficient and binary exponentiation solves most of the performance.

Python offers an implementation of these improvements using the 3 argument power function e.g.

>>> import timeit >>> t = timeit.Timer( 'print(pow( 10,14918179, 15372757))' ) >>> t.timeit(1) 10140931 0.06365180000000237 >>> u = timeit.Timer( 'print(pow( 10,14918179) % 15372757)' ) >>> u.timeit(1) 10140931 15.021656000000007

The 3 parameter of pow takes .06s whilst the 2 parameter version of pow takes 15 seconds.

Collectives™ on Stack Overflow

How to use RSA?

1 Answer 1

Direct Exponentiation

Memory efficient exponentiation

Binary exponentiation

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Direct Exponentiation

Memory efficient exponentiation

Binary exponentiation

Comments

Related