My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Computational Science

Computational Science Scientific Computing - Bioinformatics, Computational Chemistry, Computational Neuroscience, Computational Physics, Numerical Algorithms, Symbolic Mathematics, Cognitive Science


Reply
 
LinkBack Thread Tools Display Modes
July 26th, 2008, 07:46 AM   #1
 
Joined: Jul 2008
Posts: 7
Practical RSA ecncryption speeds

Well, I finally got a working RSA implementation running and now I'm wondering about speed. Does anyone know how quickly a competitive RSA program might encrypt say, 50kB in? Is there even such thing as a 'competitive' RSA program anymore? I realize mine should be slower than these, or I should be getting money somehow. I'll just put it all on the line and say that mine took a staggering 10 seconds to encrypt that 50kB file.

I'm pretty sure that's slow, just not sure how slow.
yttrium88 is offline  
 

My Computer Forum is free to register and we welcome everyone!

July 26th, 2008, 08:55 PM   #2
 
Joined: Dec 2007
Posts: 232
Re: Practical RSA ecncryption speeds

Yes, that's slow. How much of that is initialization? Does a 500 kB file take 1000 seconds, 100 seconds, or more like 20?
CRGreathouse is offline  
July 27th, 2008, 03:50 AM   #3
 
Joined: Jul 2008
Posts: 7
Re: Practical RSA ecncryption speeds

Quote:
Originally Posted by CRGreathouse
Yes, that's slow. How much of that is initialization? Does a 500 kB file take 1000 seconds, 100 seconds, or more like 20?
Alas, not much of it is initialization. On a 500kB test file it took over 100s. Something like 120 or so. I am using a modulus for the operation that is between 256 bytes and 258 bytes. By commenting lines out I have been able to determine that the vast majority of the program's time is spent in the modular exponentiation function from the GMP library. I tested the modular exponentiation with similarly sized inputs and it took 63 seconds to do only 1000 such operations. That's no fun. Is my modulus too big? I've noticed that some people pick their first exponent to be small, but of course they take what they can get when they compute it's multiplicative inverse mod (p-1)(q-1). Maybe this is a better strategy.

EDIT: I finally got the very cool gprof (gnu profiler) working under ubuntu:
Code:
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  Ts/call  Ts/call  name    
 65.14     60.09    60.09                             __gmpn_addmul_1
 29.30     87.11    27.03                             __gmpn_sqr_basecase
  1.60     88.59     1.48                             __gmpn_add_n
  1.41     89.89     1.30                             __gmpn_mul_basecase
  1.15     90.95     1.06                             redc
  0.74     91.63     0.68                             __gmpn_sub_n
  0.23     91.84     0.21                             __gmpn_kara_sqr_n
  0.21     92.03     0.20                             __gmpn_addmul_1c
  0.07     92.09     0.06                             __gmpz_powm
  0.04     92.14     0.04                             __gmpn_kara_mul_n
  0.03     92.17     0.03                             __gmpn_sqr_n
  0.02     92.19     0.02                             __gmpz_import
  0.01     92.19     0.01                             __gmpn_mul_n
  0.01     92.20     0.01                             __gmpn_rshift
  0.01     92.22     0.01                             __gmpn_sb_divrem_mn
  0.01     92.22     0.01                             __gmpn_tdiv_qr
  0.01     92.23     0.01                             vfprintf
  0.01     92.24     0.01                             __gmpn_add_nc
  0.00     92.24     0.00     2002     0.00     0.00  zero
  0.00     92.24     0.00     2001     0.00     0.00  rsa
  0.00     92.24     0.00        1     0.00     0.00  cname
  0.00     92.24     0.00        1     0.00     0.00  file_len
  0.00     92.24     0.00        1     0.00     0.00  fnrsa
  0.00     92.24     0.00        1     0.00     0.00  kfile_key
  0.00     92.24     0.00        1     0.00     0.00  main
This was with a 500kB file. I think it's pretty clear that most of the time is being spent in the GMP library. I may try the Pari lib again.
yttrium88 is offline  
July 29th, 2008, 09:11 PM   #4
 
Joined: Dec 2007
Posts: 232
Re: Practical RSA ecncryption speeds

GMP's supposed to be rather fast except for tiny numbers. What size are you working with?
CRGreathouse is offline  
July 30th, 2008, 08:58 AM   #5
 
Joined: Jul 2008
Posts: 7
Re: Practical RSA ecncryption speeds

I keep the product of my two primes between 256 and 258 bytes. So just over 600 decimal digits. I think that is a good size. Maybe I should just do some more test runs of GMP outside of my program. In other news: I went back into my long forgotten Ubuntu install and after updating to 8.04 (endearingly codenamed HHHardy HHHeron) got my program to compile there. It was maybe 2% faster. Not much. I would be interested to see what you can do with the GMP or Pari libraries, sir. Especially if they work faster than 10^4 milliseconds.

EDIT: That product of primes is, of course, the base for the modular exponentiation. Both operands in the exponentiation are around that same size too.
yttrium88 is offline  
July 30th, 2008, 01:34 PM   #6
 
Joined: Dec 2007
Posts: 232
Re: Practical RSA ecncryption speeds

Okay, so I've never implemented RSA before, so be gentle.

I wrote a quick script in Pari to test this sort of thing out. I choose these initial values:

p=makeR()
q=makeR()
nn=p*q
e = 65537
msg=vector(1600,i,random(1<<256))

where makeR chooses a prime from 2^127 to 2^128. Note that 1600 blocks of 256 bits each is 50 kB.

Then, for each block in msg, I do the following calculation:
Mod(msg[i],nn)^e

where Mod(a, b)^e calculates a^e mod b (a built-in Pari function).

Pari took 31ms. For 500 kB, it took 375ms.


Now I may be doing this wrong, and certainly this isn't a good implementation (I don't even check that e is a valid choice!), but it does give some kind of reference.
CRGreathouse is offline  
July 30th, 2008, 02:48 PM   #7
 
Joined: Jul 2008
Posts: 7
Re: Practical RSA ecncryption speeds

After changing my exponents so that one of them is MUCH lower than the other, I was able to drop the 500kB file down to about 3 seconds from over 100, which I think is now acceptable, especially given that RSA isn't even supposed to be that fast. Of course, the other direction (with the other exponent) still takes just as long.

Thanks for the help,

Nathan
yttrium88 is offline  
July 31st, 2008, 06:19 AM   #8
 
Joined: Dec 2007
Posts: 232
Re: Practical RSA ecncryption speeds

Did you drop the exponent roughly 100/3 ? 33-fold, or roughly 2^(100/3) ? 11,000,000,000-fold? Because with fast exponentiation methods, the time to calculate a^b mod n should vary as log n log b, whereas multiplying in a loop takes b log n time. That is, to get 100/3-fold gains in time, with a fast exponentiation method, you'd need to reduce the exponent by a factor of roughly 11 billion (instead of roughly 33 with slow exponentiation).

Slow: 3^12 = 3*3*3*3*3*3*3*3*3*3*3*3 (11 multiplications)
Fast: 3^12 = ((3^2 * 3)^2)^2 (1 multiply + 3 squarings ? 4 multiplications)

Slow: 3^1000 = 3*3*...*3 (999 multiplications)
Fast: ((((((((3^2 * 3)^2 * 3)^2 * 3)^2 * 3)^2)^2 * 3)^2)^2)^2 (5 multiply + 9 squarings ? 14 multiplications)
CRGreathouse is offline  
July 31st, 2008, 06:27 AM   #9
 
Joined: Dec 2007
Posts: 232
Re: Practical RSA ecncryption speeds

There are faster laddering methods than the simple addition chain method I posted. An easy one is precomputing x^3 and going 4 at a time instead of 2:

a^(4n+4) = ((a^(4n))^2)^2
a^(4n+5) = ((a^(4n) * a)^2)^2
a^(4n+6) = ((a^(4n))^2 * a)^2
a^(4n+7) = ((a^(4n) * a^3)^2)^2, where a^3 is precomputed


And I have to ask... why are you named after a gamma source?
CRGreathouse is offline  
July 31st, 2008, 06:55 AM   #10
 
Joined: Jul 2008
Posts: 7
Re: Practical RSA ecncryption speeds

Hmm. I went from an exponent on the order of 256 bytes=2048 bits to a 49 bit exponent. Clearly we are looking at something much closer to 33 than to 11 billion. So if you are correct, and I assume you are, this is using slow exponentiation OR I have a lot of overhead. I really don't think I have that much overhead. But how can GMP be using slow exponentiation? I will do some more tests with my two keys and different file sizes. For the record, here are the bit lengths of my numbers:

Mod base N is 2060 bits long.
Exponent E is 49 bits long.
Exponent D is 2058 bits long.

Quote:
Originally Posted by CRGreathouse
And I have to ask... why are you named after a gamma source?
:lol: Very good sir, very good. Back in the day when I got my first email account I was young and foolish and thought that yttrium sounded pretty cool and thought a gamma emitter was pretty cool. Ever since then I have been uncreative enough to use the same ridiculous name everywhere I go. To be fair, I have thought about changing it several times. Maybe now that I have finally been called out on that I will have to change it. I haven't really posted a whole lot on this forum, so I could at least scrap it here.

Okay...to the laboratory! (emphasis on the 2nd syllable, naturally)
yttrium88 is offline  
July 31st, 2008, 07:33 AM   #11
 
Joined: Dec 2007
Posts: 138
Re: Practical RSA ecncryption speeds

Quote:
Originally Posted by yttrium88

Okay...to the laboratory! (emphasis on the 2nd syllable, naturally)
To get the yttrium to do something sci-fi to destroy the world, I assume?
cknapp is offline  
July 31st, 2008, 08:09 AM   #12
 
Joined: Jul 2008
Posts: 7
Re: Practical RSA ecncryption speeds

Quote:
Originally Posted by cknapp
Quote:
Originally Posted by yttrium88

Okay...to the laboratory! (emphasis on the 2nd syllable, naturally)
To get the yttrium to do something sci-fi to destroy the world, I assume?
Well, almost that awesome. I actually just did time trials on the program:
Quote:
Exp: E D D/E
size(kB) time(ms) time ratio
10 168 2692 16.0
20 237 5499 23.2
50 430 12687 29.5
100 765 25546 33.4
200 1455 50562 34.8
500 3543 127374 36.0
1000 7234 256296 35.4
2000 14256 517610 36.3
Just to refresh: Mod base N is 2060 bits, D is 2058 and E is 49.
yttrium88 is offline  
July 31st, 2008, 08:18 AM   #13
 
Joined: Dec 2007
Posts: 232
Re: Practical RSA ecncryption speeds

Quote:
Originally Posted by yttrium88
Hmm. I went from an exponent on the order of 256 bytes=2048 bits to a 49 bit exponent. Clearly we are looking at something much closer to 33 than to 11 billion. So if you are correct, and I assume you are, this is using slow exponentiation OR I have a lot of overhead. I really don't think I have that much overhead. But how can GMP be using slow exponentiation? I will do some more tests with my two keys and different file sizes. For the record, here are the bit lengths of my numbers:

Mod base N is 2060 bits long.
Exponent E is 49 bits long.
Exponent D is 2058 bits long.
No, that sounds about right for fast exponentiation -- the bit lengths are off by a factor of about 40, so the numbers are off by a factor of about 2^40. But the performance is still bad. A 50 kB sample with a 256-byte exponent took Pari 6.6 seconds, and a 500 kB sample took 64.9 seconds.

Maybe this isn't a fair comparison, though. Is your computer slow? For the 500 kB sample (so overhead is less of an issue), mine was doing 360 million operations per kilobyte. How does GMP compare? At that size of number and exponent, GMP should be quite a lot better than Pari.
CRGreathouse is offline  
July 31st, 2008, 08:24 AM   #14
 
Joined: Dec 2007
Posts: 232
Re: Practical RSA ecncryption speeds

Quote:
Originally Posted by yttrium88
:lol: Very good sir, very good. Back in the day when I got my first email account I was young and foolish and thought that yttrium sounded pretty cool and thought a gamma emitter was pretty cool. Ever since then I have been uncreative enough to use the same ridiculous name everywhere I go.
Just thought I'd mention it since I'm in radiation safety -- though I've never worked with/around Y-88. Americium, tritium, technetium yes; yttrium, no. (And 'of course' all the old standbys: C-14, S-35, P-32, P-33, I-129.)
CRGreathouse is offline  
July 31st, 2008, 08:38 AM   #15
 
Joined: Jul 2008
Posts: 13
Re: Practical RSA ecncryption speeds

Note: This is the user formerly known as yttrium88. I will be using this here and probably back on mymath from now on.

Yeah, our hardware could be significantly different. I'm running this on a 1.6GHz Intel Centrino Duo with 1GB memory though that can hardly be an issue. Were you running on something faster?
NClement is offline  
Reply

  My Computer Forum > Computer Science Forum > Computational Science

Tags
ecncryption, practical, rsa, speeds



Thread Tools
Display Modes






Copyright © 2017 My Computer Forum Forum. All rights reserved.