3

I'm writing a web server in Common Lisp. Now it works OK but slow. According to the profiling the bottleneck is expt-mod function which is used to do key exchange by RSA.

Here is the detail. I got c from the client(browser). c is a 2048 bits integer. I got n and d from the RSA private key file. n and d are also 2048 bits integers. Then calculate (expt-mod c d n) to get the pre-master-key of TLS connection. The profiling shows as below:

(EXPT-MOD C D N) took 542,184 microseconds (0.542184 seconds) to run.
9,941 microseconds (0.009941 seconds, 1.83%) of which was spent in GC.
During that period, and with 4 available CPU cores
1,057,317 microseconds (1.057317 seconds) were spent in user mode
7,123 microseconds (0.007123 seconds) were spent in system mode
3,309,856 bytes of memory allocated.
10 minor page faults, 0 major page faults, 0 swaps.

I think it's super slow since OpenSSL just take 0.002 seconds to process a TLS handshake. I've tried my own version of expt-mod, cl-utilities:expt-mod and ironclad:expt-mod but no luck. The profiling result shows pretty much the same.

So where did I make mistakes? Thanks.

Wise Simpson
  • 305
  • 3
  • 9
  • You need to know how and why it's being called - too many times perhaps? I use [*stackshots*](http://stackoverflow.com/a/378024/23771). – Mike Dunlavey Jun 09 '14 at 07:49
  • You failed to create a high performance RSA engine, what else do you want us to say? – Maarten Bodewes Jun 09 '14 at 10:45
  • hi @owlstead, I didn't create a RSA engine. I tried to use one from package cl-utilities and ironclad. I also tried to use the one from CLIKI [http://www.cliki.net/expt-mod](http://www.cliki.net/expt-mod). Are you saying the performance is low because of the code? – Wise Simpson Jun 09 '14 at 13:17
  • @MikeDunlavey, the function expt-mod function isn't being called too many times. It's just been called once and took 0.5 seconds. I wonder if it's normal? – Wise Simpson Jun 09 '14 at 13:20
  • 1
    Modular exponentiation (with a large exponent as used in an RSA private exponent) is the most time expensive component of RSA, and it is only beaten in slowness by RSA key pair generation of all the algorithms I know. Now 0.5 seconds is still *very* slow if you compare it with an optimized, native implementation, but I would expect such values for systems where the big number library is not optimized. If you want something faster, use something based on EC, but note that not all clients will have EC support. – Maarten Bodewes Jun 09 '14 at 13:53
  • `openssl rsa speed` : Doing 2048 bit private rsa's for 10s: 887 2048 bit private RSA's in 9.89s on my old laptop. So it is about a factor 500 slower than it can be. Note that `openssl` has a very fast implementation. – Maarten Bodewes Jun 09 '14 at 13:59
  • Yes. That's why I feel the expt-mod function in Common Lisp is weird slow. So I wonder if I didn't something wrong, like didn't compile it right? or it must be this slow just because using Common Lisp? Thanks for your reply @owlstead – Wise Simpson Jun 09 '14 at 14:05
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/55324/discussion-between-owlstead-and-wise-simpson). – Maarten Bodewes Jun 09 '14 at 14:07
  • Which implementation? What optimization settings? – Samuel Edwin Ward Dec 31 '14 at 22:02
  • 1
    @SamuelEdwinWard The problem happened when I was using Clozure CL with default settings. Then I switched to SBCL and it is significant fast at expt-mod. – Wise Simpson Jan 01 '15 at 01:59
  • @WiseSimpson why are you inventing the wheel? There are few webservers in Common Lisp already. Just take Woo or Hunchentoot. – Alexander Artemenko Sep 08 '16 at 10:51
  • @AlexanderArtemenko Because I want a web server: (a) Support HTTP/2. (b) No OpenSSL dependency. Neither Woo nor Hunchentoot does that. – Wise Simpson Sep 09 '16 at 08:08

1 Answers1

0

I'm not sure if it's the answer but I did solve this problem by switching from Closure CL to SBCL.

Wise Simpson
  • 305
  • 3
  • 9