RSA key generation

I wasn't satisfied with the performance of RSA key pair generation at all since Sagittarius supported cryptographic operations. So I've done a lot of performance tuning such as bytevector->integer, integer->bytevector procedures. These changes, however, did not make that much difference even it's been improved 100 times faster than previous implementation.

Why? Actually I knew why. The prime number generation was really slow. It reads random number each time and checks if the number is prime or not with Millar Rabin test. In this prime number generation procedure, bytevector->integer is used so I thought if I improve the performance it would be changed dramatically. I've bet on the wrong horse, unfortunately.

Then I let it be for long time (I guess 3 month or so?) and I've got an idea today. The random number generation creates fresh bytevector each time, what if I modified it to read destructively. So I have introduced read-random-bytes! procedure and modified random-prime to use it. Now it's benchmark time. I used following code which generates 1024 bits RSA key pair.

(import (crypto) (math) (time))
(generate-key-pair RSA :prng (pseudo-random RC4))

To make sure the key generation procedure uses the same random generator, I specified :PRNG keyword. The result is below;

% sash test2.scm

;;  (generate-key-pair RSA :prng (pseudo-random RC4))
;;  1.7565269470214844 real    1.826000 user    0.047000 sys

% ./build/sash.exe -Llib -Lsitelib -Dbuild -L./ext/crypto -Lext/time test2.scm

;;  (generate-key-pair RSA :prng (pseudo-random RC4))
;;  0.769230 real    0.749000 user    0.031000 sys

Yes! It's improved as twice fast as before. The problem is, however, this change, more specificaly read-random-bytes!, introduced imcompatiblity of 0.3.5. Well, the change only affects custom pseudo random generator and I guess it's used by only me. So just wrote note on the document.