
Computational Science Scientific Computing  Bioinformatics, Computational Chemistry, Computational Neuroscience, Computational Physics, Numerical Algorithms, Symbolic Mathematics, Cognitive Science 
 LinkBack  Thread Tools  Display Modes 
July 26th, 2008, 06: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. 
My Computer Forum is free to register and we welcome everyone! 
July 26th, 2008, 07: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?

July 27th, 2008, 02:50 AM  #3  
Joined: Jul 2008 Posts: 7  Re: Practical RSA ecncryption speeds Quote:
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  
July 29th, 2008, 08: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?

July 30th, 2008, 07: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. 
July 30th, 2008, 12: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 builtin 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. 
July 30th, 2008, 01: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 
July 31st, 2008, 05:19 AM  #8 
Joined: Dec 2007 Posts: 232  Re: Practical RSA ecncryption speeds
Did you drop the exponent roughly 100/3 ? 33fold, or roughly 2^(100/3) ? 11,000,000,000fold? 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/3fold 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) 
July 31st, 2008, 05: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? 
July 31st, 2008, 05: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:
Okay...to the laboratory! (emphasis on the 2nd syllable, naturally)  
July 31st, 2008, 06:33 AM  #11  
Joined: Dec 2007 Posts: 138  Re: Practical RSA ecncryption speeds Quote:
 
July 31st, 2008, 07:09 AM  #12  
Joined: Jul 2008 Posts: 7  Re: Practical RSA ecncryption speeds Quote:
Quote:
 
July 31st, 2008, 07:18 AM  #13  
Joined: Dec 2007 Posts: 232  Re: Practical RSA ecncryption speeds Quote:
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.  
July 31st, 2008, 07:24 AM  #14  
Joined: Dec 2007 Posts: 232  Re: Practical RSA ecncryption speeds Quote:
 
July 31st, 2008, 07: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? 