[Mono-list] Poor RSACryptoServiceProvider performance

[Ben Maurer]

To expand on what Sebastien has said:

Key pair generation is _really_ slow. Basically, it involves 1) finding
2 primes each with a len of 1/2 the keylength (so that they multiply out
to the key length). Currently, on the version that is in CVS, this
involves doing the Rabin-Miller test on the number 80 times on each
candidate prime (in practice however, most numbers fail the first
round). Each round of this test requires a modPow operation, which in
turn requires ~O(n) bignum multiplies, in turn requiring O(n^2)
multiplies. It also requires Barrett Reduction for each multiply. The
entire process is very long.

Also, one reason it is slow is that if it is running on the Mono jit,
then every time an array is accessed a bounds check must be done. Each
time a multiply is done > O(2 n^2) items must be accessed in the array.
That means that many function calls -- that hurts! This facto is the
main reason why the real CSP will always one-up us--it never has to do
bounds checking.

As Sebastien said, I am going to do a ground up rewrite of the
BigInteger class. Right now, my major problem with it is that there is a
predefined maximum number (maxLength). This prevents us from
implementing 16kbit keys. However, in making this change I am also going
to make many other speed improvements (for example, right now doing a
BigNum square is O(n^2), but it can be made O(n^2/2 - n)). Thus far, I
have +,-,*,/ implemented as well as modPow. All I have to do really is
to implement some of the number theory stuff (prime testing, gcd,
modInv). At that point, I would do a big optimizing run through of the
program (I am writing lots of NUnit tests, so this should be easy). It
would then be ready to integrate into the CVS tree.

If you would be willing to help out with the BigInteger development, I
would be glad to have you ( or anyone for that matter :) on board. There
are many jobs to be done, most of which require no more mathematical
ability than the average algebra student (and at most times, only the
knowledge of say a 4th grader [in math, not programming :)] ).

In terms of profilers, I would highly recommend DevPartner, although
make sure you turn on the "only collect to method granularity"
(especially on stuff like BigInteger, because otherwise it spends all
its time in inner loops). Also, it makes VS.net much less stable, so
beware, save early, save often.

Also, if you are willing, could you possibly release the code for the
crypto part of your project as a benchmark? That could help me and
Sebastien and anyone who works with to have a real-life application to
compare speed against.

Sincerely,
Ben Maurer
Webmaster
The Ratner School
Web:	theratnerschool.org
E-mail:	webmaster@theratnerschool.org


-----Original Message-----
From: mono-list-admin@lists.ximian.com
[mailto:mono-list-admin@lists.ximian.com] On Behalf Of Sebastien Pouliot
Sent: Wednesday, February 19, 2003 11:07 PM
To: Elan Feingold
Cc: mono-list
Subject: Re: [Mono-list] Poor RSACryptoServiceProvider performance

> - The performance of the RSACryptoServiceProvider seems abysmal. Just
> starting up and reading a key using FromXmlString is really really
slow,
> like orders of magnitude slower than under XP/.NET.

Reading a keypair shouldn't be so slow. However generating keypairs is
VERY
slow.

There's a design bug in MS.NET crypto. Each time you create an RSA
object
(without naming a container in CspParameters) a new keypair is generated
(which is really BAD when you do crypto in a server application). For
compatibility reason this behaviour is also present in Mono but is
delayed
until you actually use the keypair (so it should not affect code that
import
a keypair before using it) __unless__ you provide a keysize in the
constructor [*].

* I'll probably change this behaviour as it's not really required.

> Any ideas why this might be?

Sure :-)

Mono has a 100% C# implementation for all it's cryptography (well except
RNG). MS use the default CSP (unmanaged) to provide much of it's crypto.

This means that:
- unmanaged code is (most of the time) faster than managed code - even
more
when we're talking about heavily optimized unamanaged code (like MS
CSP);
- the performance of the compiler and the JIT are much more important
for
Mono than MS (which means that the crypto performance will get better -
even
without any further optimization ;-).

But there are many advantage in having a managed implementation.

> Is there a profiler for Mono ?

Yes , however I've never used it (someone else may help you with this).
However I did use the "Community Edition of DevPartner Profiler" (with
VS.NET) which is excellent.

If you're interested in optimizing the math part (where the RSA
implementation needs help) send an email to Ben Mauer
(webmaster@theratnerschool.org). He is doing optimizations on the
BigInteger
class (well last time we talked it looked more like a total rewrite). So
asymmetric performance should improve but will never match the
performance
of hand-tuned implementation (like MS).

You can find more information @ http://www.go-mono.com/crypto.html.

Sebastien Pouliot
Security Architect, Motus Technologies, http://www.motus.com/
work: spouliot@motus.com
home: spouliot@videotron.ca


_______________________________________________
Mono-list maillist  -  Mono-list@lists.ximian.com
http://lists.ximian.com/mailman/listinfo/mono-list