RSA encode/decode speed


#1

Hi again,

Just a quick question, it appears that the Juce RSA implementation is much slower at encoding then decoding - ie when RSAKey::applyToValue() is using a private key rather than a public one.

For a 1024bit keypair en/decoding approx 300 bytes the times are:
encoding (private key) - 13 seconds!
decoding (public key) - 37 ms

Is this expected? Stepping through the code it appears it should be doing pretty much the same for an encode as a decode??!!

Cheers -


#2

Well creating the key pair is slow, but you only have to do that once.

Like it says in applyToValue(), that function does both encoding and decoding.


#3

Yeah, that’s what I can’t understand, I’m not creating a keypair, just using RSAKey::applyToValue(), for example the following code:

[code]#define PUB_KEY “3,cb9d0d4be2f8b92d6a2852dc04c231ff353cdf23e5b583a3304514b1a030de0e1cdef254f36a2fccbc4fe1233feb196e900d1b6214260b424bbf24faca52bf2eeb1bf998f19eadaa7709f7d1e87c3be37acd4a397ddda09228877fa20302fd892cc6c960573ab7a870dfafa0be5674c5e2a08e796349aa0b14f291bb909b0eef”
#define PRIV_KEY “87be08dd41fb261e46c58c92add6cbff78d33f6d43ce57c2202e0dcbc02094096894a18df79c1fddd2dfeb6cd5476649b55e124162c4078187d4c351dc372a1e1691079d9e0b00c0692139889ac519b15df9c45fe9982ffdf45dea7ea8320de32bd9ebfe48e86a248401dcc6b8911d91b3dabc647d1e5181ced922d355390afb,cb9d0d4be2f8b92d6a2852dc04c231ff353cdf23e5b583a3304514b1a030de0e1cdef254f36a2fccbc4fe1233feb196e900d1b6214260b424bbf24faca52bf2eeb1bf998f19eadaa7709f7d1e87c3be37acd4a397ddda09228877fa20302fd892cc6c960573ab7a870dfafa0be5674c5e2a08e796349aa0b14f291bb909b0eef”

String s("the quick brown dog jumped over the lazy fox yes it did...");
RSAKey privateKey(PRIV_KEY);
RSAKey publicKey(PUB_KEY);
MemoryBlock mb ((const char*) s, s.length());
BitArray val;
val.loadFromMemoryBlock (mb);

//time encryption with private key
Time start=Time::getCurrentTime();
privateKey.applyToValue (val);
printf("encrypt took %s\n", (const char*)((Time::getCurrentTime()-start).getDescription()));

//time decryption with public key
start=Time::getCurrentTime();
publicKey.applyToValue (val);
printf("decrypt took %s\n", (const char*)((Time::getCurrentTime()-start).getDescription()));

mb = val.toMemoryBlock();
printf(mb.toString());[/code]

outputs the following:

encrypt took 4 secs decrypt took 8 ms the quick brown dog jumped over the lazy fox yes it did...

and takes just over 4 seconds to run… am I doing anything obviously silly??! Thanks -


#4

RSA speed is mostly about the time it takes to raise a number to a power. This is roughly proportional to the log of the power…
so for example, to compute x^3, you have to do two multiplies. To compute x^256, you need to do 8 multiplies.

RSA encoding can (mostly) pick one of the powers, almost always for the public key, and almost always for efficiency. So x^3 is a popular choice. So is 65537, which is also efficient to compute.
However, the PRIVATE exponent is always long, and for a 2048 bit key, will tend to have an exponent with close to 2048 bits.
It’s roughly 2000 times slower to raise a number to a power with 2000 digits than it is to raise it to a power with 1 digit.

So, your public speed of 37ms is computing x^3 (notice the 3 in the private key). The private decode, with 1000 bit exponent really is about 1000 times more work, so your 37ms and 13 sec timings are in the right ballpark.

Annoying? Yep, but that’s part of the cost of RSA. The public part is fast only because it’s CHOSEN to be specifically efficient. It’s not a JUCE problem in general.

The slowness of RSA is one reason people often use RSA to encrypt a large random key to a fast symmetric cypher, and then encrypt the actual message with the symmetric cypher.


#5

Ah ok, thanks for the explanation -

:slight_smile:


#6