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: [EMAIL PROTECTED] -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] 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 ([EMAIL PROTECTED]). 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: [EMAIL PROTECTED] home: [EMAIL PROTECTED] _______________________________________________ Mono-list maillist - [EMAIL PROTECTED] http://lists.ximian.com/mailman/listinfo/mono-list _______________________________________________ Mono-list maillist - [EMAIL PROTECTED] http://lists.ximian.com/mailman/listinfo/mono-list
