RSA sign time out

[klone]

Hello!

First of all thanks for phpseclib, its a very good lib.

I have been signing data with RSA on my local machine which uses PHP 5.3.5 and it works fine. But now I moved me sources to a online server
using PHP 5.2.10 and I'm getting time out problems when signing data.

Here is PHP code along with the error message,

Code: Select all

$rsa = new Crypt_RSA();
if(!$rsa->loadKey($private_key_contents)){
   exit("Nope, bad key");
}

$rsa->sign("hello"); //this line times out

//and the error message
Fatal error: Maximum execution time of 30 seconds exceeded in biginteger.php on line 1165


So it's seems to me that the biginteger class is using a lot of time, does any one know how I can fix this?

Thanks in advance

[TerraFrost]

Can you generate an RSA private key of the same size and send it to me?

Also, can you post your line 1165? The file's been renamed from BigInteger.php to biginteger.php and I kinda wonder if other things have maybe changed too. Here's what I see as line 1165:

Code: Select all

                $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;

(in the _regularMultiply function)

Thanks!

[TerraFrost]

The above post having been made, operations involving the private key are gonna take more time than operations involving the public key.

Usually, the public exponent is fixed at 65537, for speed. The private exponent, on the other hand, is huge. A standard RSA private key will contain the two prime numbers that were used to generate the modulo, among other things, and those can be used to speed the calculation up, but even with that, it's still a lot slower than operations with the public exponent.

Like on my own system, when MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_INTERNAL, operations on a 2048 bit RSA private key take ~5.5 seconds. For a 4096 bit key it takes 39 seconds on average.

When MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP (requires the gmp extension be installed), 4096 bit keys take ~0.08 seconds, on average, and with MATH_BIGINTEGER_MODE_BCMATH (requires the bcmath extension be installed), they take 29 seconds on average.

[klone]

Hello TerraFrost!

Sorry for the late response, but I just had to wait to be accepted into this forum first, so I forgot to check.

I generated a new private key, and yes I forgot to mention that in the previous example I used a 1024-bit private key.

-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQCK47eJ2SzdA4fRDmfBKo6ooZPDrgMPCUVD/bA7+zQPyPhh388iGds0MMIhf16f
9Do8Wc0qsEldexql8iaBOu6evmVOX7VUPnVKn9c0g9kJOVE/MVCOjrO/ax/FN5xGsVPn09/i8e+q
o5NenUkdCVKwwt0fwjtrOD4SsgQfMEPI/QIDAQABAoGAGBACQyNpYqQjMmy6vIxtOVl/AnqiJIeA
ZNptn0Ky/x4cLEbMedW9dMISzB9nSzKSqVSMl14B4+x5TjFRCvglEYE1urVXCOB0OYcVXcuN70Do
jrK5Nf8Z56Ivqa236w60I4WwfeKeJwWOrxv+hfexBqCWBJiIeN4r/zQ3aiaZu4kCQQClNkgqOR3G
F6TgYUzXcz1lDzHMRPg/6mOY1Bb38ThfkUdvTNF0qTslIIY1rDREYb3cJbcIq92R7YAxdBdmS631
AkEA1zZuwv5dKRKbaLE45M9L0v/qP9y/SOvINlnSCGpefJ3xl7/Wrf3tljsMya0tcQRmPdmosD9a
AN1yRcrLqZKB6QJBAI3990wCxuooDBakyawqaUvgIUaUyF/2jR8euZbjhTXt4N1xwltnz2N7bp3W
oR1cfBcnewZC4C25WAIo6quKw7kCQQCEFD8D4xIPrAC+zs0o9+QEGdWM3hBzU2krmhJh4c4dUt27
kRvS6p2Obq0ZdPQHgXiyCswRZr/4+e8w0BYP+v9JAkBXB5Fj3aO4aLeDGdp7DaI/0vG+u4IQ4FQ9
IOySzSL4zoaj26PaPfvAUrJhQh0jkbt5Ta8bc6vQiD6PnNOkWof0
-----END RSA PRIVATE KEY-----

The line you mention is the one timing out, I only changed the biginteger file name and nothing else, since I find capital letters somehow offensive , I also downloaded the trunk version and tried it out too, but with the same outcome.

I did some tests and increased the time out on the server to 60 seconds and it signed that message in 40 sec. I also noticed that the server did not have any math lib installed so it was running MATH_BIGINTEGER_MODE_INTERNAL. I was forced to switch to openssl since I think 40 sec is a lot of waiting time for signing a 5 char message with a 1024-bit key.

(But I guess that's the nature of php, if there are no optimizations left to do in big integer class.)

Thanks

[TerraFrost]

What kind of computer do you have? I tried that query on a 1.73GHz quad core Intel i7 and it took a little less than a second. Not the 40 seconds it's taking for you.

I'm also curious... how long does the following take for you?:

Code: Select all

$start = microtime(true);
for ($i = 0; $i < 10000000; $i++);
$elapsed = microtime(true) - $start;
echo "took $elapsed seconds";

On my computer it takes about 0.75 seconds.