Bug #52689 for Crypt-RSA: consider moving Crypt::RSA to Math::BigInt?

Fri Dec 11 18:25:21 2009 dkg [...] fifthhorseman.net - Ticket created

Subject:	consider moving Crypt::RSA to Math::BigInt?
Date:	Fri, 11 Dec 2009 18:24:51 -0500
To:	bug-Crypt-RSA [...] rt.cpan.org, Salvatore Bonaccorso <salvatore.bonaccorso [...] gmail.com>, Benjamin Trott <cpan [...] stupidfool.org>, Vipul Ved Prakash <mail [...] vipul.net>
From:	Daniel Kahn Gillmor <dkg [...] fifthhorseman.net>

Hi Vipul-- Would you consider patches (if i could provide them) that would make it so that Crypt::RSA used Math::BigInt instead of Math::Pari? Math::BigInt can use either GMP or Math::Pari as a backend, so a change like this could make Crypt::RSA a bit more versatile. My ultimate reason for this is that Math::Pari has proven very difficult to get into binary-distributed operating systems like debian because of upstream's preference for building from source everywhere. And i'd really like to see Crypt::RSA become available in debian. I'm Cc'ing Salvatore Bonaccorso here, who has indicated an intent to package Crypt::RSA for debian, if we can arrange to have the dependencies sorted out [0]. Also, i'm CC'ing Benjamin Trott (upstream of Crypt::OpenPGP, which relies on Crypt::RSA, has indicated a willingness to accept patches for Crypt::OpenPGP to move to Math::BigInt if i can get Crypt::RSA to do the same [1]. He also had some experience in porting Crypt::DSA to Math::BigInt several years ago. So what do you say? i'm willing to take a stab at the work, if a change like this is something you'd consider accepting. I suppose if you're dead set against it, forking is an option, but i'd much prefer to have your guidance and oversight on an undertaking like this. What do you think? is this doable? is it a good idea? is it madness? Are there a further dependency chains we'd need to follow (e.g. Crypt::Random, etc) to be able to use a Math::BigInt-based Crypt::RSA? Regards, --dkg [0] http://bugs.debian.org/532839 [1] https://rt.cpan.org/Public/Bug/Display.html?id=44174

Download signature.asc
application/pgp-signature 891b

Message body not shown because it is not plain text.

Sun Dec 05 19:27:19 2010 mutant.nz [...] gmail.com - Correspondence added

From:

mutant.nz [...] gmail.com

I've had a stab at this, and made some progress. However, there are possibly some performance issues I'd like to discuss. Vipul, if you're interested in this, can you please contact me? I've tried emailing you, but it bounced. Thanks, Sam.

Sun Dec 05 19:27:20 2010 The RT System itself - Status changed from 'new' to 'open'

Sun Dec 05 21:52:06 2010 dkg [...] fifthhorseman.net - Correspondence added

Subject:	Re: [rt.cpan.org #52689] consider moving Crypt::RSA to Math::BigInt?
Date:	Sun, 05 Dec 2010 21:51:45 -0500
To:	bug-Crypt-RSA [...] rt.cpan.org
From:	Daniel Kahn Gillmor <dkg [...] fifthhorseman.net>

On 12/05/2010 07:27 PM, Sam Crawley via RT wrote: Show quoted text

> <URL: https://rt.cpan.org/Ticket/Display.html?id=52689 > > > I've had a stab at this, and made some progress. However, there are > possibly some performance issues I'd like to discuss. Vipul, if you're > interested in this, can you please contact me? I've tried emailing you, > but it bounced.

Sam, i'd be interested in your progress, and in what the performance issues are that you're concerned about. If you'd care to share notes, i would be happy to look at it with you. I hope Vipul will weigh in soon too, of course. Regards, --dkg

Download signature.asc
application/pgp-signature 900b

Message body not shown because it is not plain text.

Mon Feb 14 17:46:00 2011 dkg [...] fifthhorseman.net - Correspondence added

Subject:	Re: [rt.cpan.org #52689] consider moving Crypt::RSA to Math::BigInt?
Date:	Mon, 14 Feb 2011 17:45:41 -0500
To:	mutant.nz [...] gmail.com, bug-Crypt-RSA [...] rt.cpan.org
From:	Daniel Kahn Gillmor <dkg [...] fifthhorseman.net>

What is the status of CPAN's RT #52689 (consider moving Crypt::RSA to Math::BigInt)? I'd really like to see this possibility happen. Sam, you say you have patches? Would you mind publishing them? if there are any performance issues to be sorted out, i'd like to be able to evaluate them. I would really like to see Crypt::RSA available without the Math::PARI dependency if possible. Regards, --dkg

Download signature.asc
application/pgp-signature 1k

Message body not shown because it is not plain text.

Mon Feb 14 18:02:45 2011 mutant.nz [...] gmail.com - Correspondence added

From:

mutant.nz [...] gmail.com

It's been a few months since I worked on this, so I can't quite remember all the details. I think there were a couple of issues. First, Crypt::RSA depends on other modules that also need Math::Pari, so it would be necessary to convert those as well (and they weren't completely trivial to convert). Secondly, Crypt::RSA (and dependencies) were using parts of the Math::Pari API that didn't necessarily have a corresponding call in Math::BigInt. This could be because those things aren't implemented by the other Math::BigInt backends. I think my attempted workaround to these problems was the cause of the performance issues (i.e. I was using APIs in the wrong way). I didn't really get anything to a stage where it could be released as a patch. It was really just a semi-functional prototype. I don't really have any more time to contribute at this point. However, I think it should be possible. It would need someone who really understands the code and Math::BigInt (and probably Math::Pari). I was really floundering around trying to guess how to make changes, but someone who knew what they were doing could probably do that easily, and code around any performance problems. It might require a fairly significant re-write though. Sorry I can't be of more help.

Mon Feb 14 23:42:01 2011 dkg [...] fifthhorseman.net - Correspondence added

Subject:	Re: [rt.cpan.org #52689] consider moving Crypt::RSA to Math::BigInt?
Date:	Mon, 14 Feb 2011 23:41:50 -0500
To:	bug-Crypt-RSA [...] rt.cpan.org, mutant.nz [...] gmail.com
From:	Daniel Kahn Gillmor <dkg [...] fifthhorseman.net>

On 02/14/2011 06:02 PM, Sam Crawley via RT wrote: Show quoted text

> <URL: https://rt.cpan.org/Ticket/Display.html?id=52689 > > > It's been a few months since I worked on this, so I can't quite remember > all the details. I think there were a couple of issues. First, > Crypt::RSA depends on other modules that also need Math::Pari,

Those seem to be Crypt::Primes and Crypt::Random, right? Show quoted text

> so it > would be necessary to convert those as well (and they weren't completely > trivial to convert). Secondly, Crypt::RSA (and dependencies) were using > parts of the Math::Pari API that didn't necessarily have a corresponding > call in Math::BigInt. This could be because those things aren't > implemented by the other Math::BigInt backends. > > I think my attempted workaround to these problems was the cause of the > performance issues (i.e. I was using APIs in the wrong way). I didn't > really get anything to a stage where it could be released as a patch. It > was really just a semi-functional prototype. I don't really have any > more time to contribute at this point. > > However, I think it should be possible. It would need someone who really > understands the code and Math::BigInt (and probably Math::Pari). I was > really floundering around trying to guess how to make changes, but > someone who knew what they were doing could probably do that easily, and > code around any performance problems. It might require a fairly > significant re-write though.

hm, ok. I'm unable to see either MX or A records for vipul.net, so i'm not sure how to contact Vipul, other than these tickets. Vipul, are you out there? --dkg

Download signature.asc
application/pgp-signature 1k

Message body not shown because it is not plain text.

Tue Feb 15 08:28:10 2011 CARNIL [...] cpan.org - Cc CARNIL added

Sat Jun 02 14:52:22 2012 kmx [...] cpan.org - Correspondence added

Hi,

just want to support this RT as Math::PARI does not work on 64-bit MS Windows and therefore there in no chance to have Crypt::RSA on MS Win/64bit.

--
kmx

Sat Jun 02 14:52:46 2012 kmx [...] cpan.org - Cc KMX added

Wed Dec 12 02:30:31 2012 DANAJ [...] cpan.org - Correspondence added

On Mon Feb 14 23:42:01 2011, dkg@fifthhorseman.net wrote: Show quoted text

> On 02/14/2011 06:02 PM, Sam Crawley via RT wrote:

> > <URL: https://rt.cpan.org/Ticket/Display.html?id=52689 > > > > > It's been a few months since I worked on this, so I can't quite remember > > all the details. I think there were a couple of issues. First, > > Crypt::RSA depends on other modules that also need Math::Pari,

> > Those seem to be Crypt::Primes and Crypt::Random, right?

Shameless plug, but Math::Prime::Util includes a random Maurer prime generator, which is most of Crypt::Primes. It requires only Math::BigInt (it's faster with Math::BigInt::GMP or Math::BigInt::Pari, but works fine without). I should adjust the interface to provide a little easier way to plug in RNGs while part of a library. It looks like Bytes::Random::Secure can provide all the functionality currently being provided by Crypt::Random. It's also much easier on system entropy use while still being secure (it uses Crypt::Random::Source for seeding, and Math::Random::ISAAC for the RNG). This still leaves all the Pari code in the module proper. It's certainly possible to do if this is still something wanted.

Wed Dec 12 03:42:41 2012 dkg [...] fifthhorseman.net - Correspondence added

CC:	CARNIL [...] cpan.org, kmx [...] cpan.org
Subject:	Re: [rt.cpan.org #52689] consider moving Crypt::RSA to Math::BigInt?
Date:	Wed, 12 Dec 2012 03:42:22 -0500
To:	bug-Crypt-RSA [...] rt.cpan.org
From:	Daniel Kahn Gillmor <dkg [...] fifthhorseman.net>

On 12/12/2012 02:30 AM, Dana Jacobsen via RT wrote: \> Shameless plug, but Math::Prime::Util includes a random Maurer prime Show quoted text

> generator, which is most of Crypt::Primes. It requires only > Math::BigInt (it's faster with Math::BigInt::GMP or Math::BigInt::Pari, > but works fine without). I should adjust the interface to provide a > little easier way to plug in RNGs while part of a library. > > It looks like Bytes::Random::Secure can provide all the functionality > currently being provided by Crypt::Random. It's also much easier on > system entropy use while still being secure (it uses > Crypt::Random::Source for seeding, and Math::Random::ISAAC for the RNG).

This all sounds reasonable to me. Show quoted text

> This still leaves all the Pari code in the module proper. It's > certainly possible to do if this is still something wanted.

yes, it's still wanted! I would be happy to see this happen :) I'm sorry i'm not able to spend much time on it myself right now. --dkg

Thu Dec 20 19:57:10 2012 DANAJ [...] cpan.org - Correspondence added

I have a module now that: 1. Passes the current test suite. 2. Has no references or requirements for Pari. Everything is done with Math::BigInt. 3. Replaces Crypt::Primes with Math::Prime::Util, and Crypt::Random with Bytes::Random::Secure. Hence no more Pari requirements at all. 4. Uses exactly the same interface. Anything that relied on numbers being Math::Pari objects would no longer work, but if it was nice and treated it as a number it should be fine. Math::BigInts are also a bit more portable. 5. If either GMP or Pari are available, it runs at about the same speed. 6. Switched to ExtUtils::MakeMaker. Uses Devel::CheckLib to check for GMP. If found, adds Math::BigInt::GMP and Math::Prime::Util::GMP to the prereq list. If GMP isn't found, it looks for Pari and adds Math::BigInt::Pari if so. If neither are found, it spits out a message explaining that things might be really slow, but will continue. 7. Fixes RTs: 4877, 52689, 61392, 63007, 64883, 76655. I may fix 45533 and 69376 as well but those will take a little more research. RTs 50356 and 59923 aren't clear, but the former may be an HP/UX+Pari issue. 8. Should still work back to 5.6.2, but this will take a little more digging. I want to add more tests and spend some time with Devel::Cover, but so far things look good. I also have some documentation changes I'd like to make. I'm thinking I'll try Ingy's Alt module, so: cpan Alt::Crypt::RSA::BigInt would get this version, all packaged as Crypt::RSA so it just plugs right in. Discussions about whether to replace the current Crypt::RSA can then proceed at leisure.

Thu Dec 20 20:48:38 2012 vipulved [...] gmail.com - Correspondence added

Subject:	Re: [rt.cpan.org #52689] consider moving Crypt::RSA to Math::BigInt?
Date:	Thu, 20 Dec 2012 17:48:24 -0800
To:	"bug-Crypt-RSA [...] rt.cpan.org" <bug-Crypt-RSA [...] rt.cpan.org>
From:	Vipul Ved Prakash <vipulved [...] gmail.com>

Awesome. How's relative performance? I am open to just replacing crypt::rsa if that sounds ok to you. Vipul Ved Prakash, via IPhone On Dec 20, 2012, at 4:57 PM, "Dana Jacobsen via RT" <bug-Crypt-RSA@rt.cpan.org> wrote: Show quoted text

> <URL: https://rt.cpan.org/Ticket/Display.html?id=52689 > > > I have a module now that: > > 1. Passes the current test suite. > > 2. Has no references or requirements for Pari. Everything is done > with Math::BigInt. > > 3. Replaces Crypt::Primes with Math::Prime::Util, and Crypt::Random > with Bytes::Random::Secure. Hence no more Pari requirements at all. > > 4. Uses exactly the same interface. Anything that relied on numbers > being Math::Pari objects would no longer work, but if it was nice and > treated it as a number it should be fine. Math::BigInts are also a bit > more portable. > > 5. If either GMP or Pari are available, it runs at about the same speed. > > 6. Switched to ExtUtils::MakeMaker. Uses Devel::CheckLib to check for > GMP. If found, adds Math::BigInt::GMP and Math::Prime::Util::GMP to the > prereq list. If GMP isn't found, it looks for Pari and adds > Math::BigInt::Pari if so. If neither are found, it spits out a message > explaining that things might be really slow, but will continue. > > 7. Fixes RTs: 4877, 52689, 61392, 63007, 64883, 76655. I may fix > 45533 and 69376 as well but those will take a little more research. RTs > 50356 and 59923 aren't clear, but the former may be an HP/UX+Pari issue. > > 8. Should still work back to 5.6.2, but this will take a little more > digging. > > I want to add more tests and spend some time with Devel::Cover, but so > far things look good. I also have some documentation changes I'd like > to make. > > > I'm thinking I'll try Ingy's Alt module, so: > > cpan Alt::Crypt::RSA::BigInt > > would get this version, all packaged as Crypt::RSA so it just plugs > right in. Discussions about whether to replace the current Crypt::RSA > can then proceed at leisure.

Fri Dec 21 05:40:19 2012 DANAJ [...] cpan.org - Correspondence added

On Thu Dec 20 20:48:38 2012, vipulved@gmail.com wrote: Show quoted text

> Awesome. How's relative performance? I am open to just replacing > crypt::rsa if that sounds ok to you.

Summary: With GMP, it's 2 to 5x faster. With Pari it's 1.5 - 3x slower. Without either it's 100x or more slower. I could make it dependent on GMP, which is still a lot more portable (and far more common in vendor installs) than Pari, but it's pretty handy to have something that works even without the big number libraries. I realize that it may just end up with a stream of "it's so slow!" complaints from people who didn't read the documentation. On my x86_64 computer, otherwise idle, t/15-benchmark.t using -3 for count: Crypt::RSA 1.99 (Pari) PKCS-sign: 770.19/s (n=2480) PKCS-sign-CRT: 1072.78/s (n=3390) PKCS-verify: 1556.92/s (n=4951) PKCS-verify-CRT: 3107.21/s (n=9912) PSS-sign: 635.65/s (n=2015) PSS-sign-CRT: 826.96/s (n=2638) PSS-verify: 1342.06/s (n=4308) PSS-verify-CRT: 3107.21/s (n=9912) Crypt::RSA BigInt, using Math::BigInt::GMP: PKCS-sign: 4912.69/s (n=15868) PKCS-sign-CRT: 3532.71/s (n=11340) PKCS-verify: 6198.44/s (n=19835) PKCS-verify-CRT: 7584.47/s (n=24422) PSS-sign: 2504.59/s (n=8190) PSS-sign-CRT: 2083.60/s (n=6605) PSS-verify: 2915.94/s (n=9331) PSS-verify-CRT: 7584.47/s (n=24422) With Math::BigInt::Pari: PKCS-sign: 324.92/s (n=1043) PKCS-sign-CRT: 367.41/s (n=1161) PKCS-verify: 1883.64/s (n=6103) PKCS-verify-CRT: 2247.66/s (n=7215) PSS-sign: 306.54/s (n=984) PSS-sign-CRT: 346.54/s (n=1102) PSS-verify: 1409.29/s (n=4552) PSS-verify-CRT: 2240.68/s (n=7215) With Math::BigInt::Calc: PKCS-sign: 4.58/s (n=14) PKCS-sign-CRT: 14.29/s (n=44) PKCS-verify: 164.35/s (n=521) PKCS-verify-CRT: 174.92/s (n=558) PSS-sign: 4.61/s (n=14) PSS-sign-CRT: 14.15/s (n=44) PSS-verify: 156.19/s (n=492) PSS-verify-CRT: 175.62/s (n=569) NYTProf indicates Calc and Pari are spending most of their time in bmodpow, basically in core_encrypt and core_decrypt. Interestingly, with Math::BigInt::GMP, most of the time was spent twiddling around in helper functions and making new objects. The bmodpow is far, far faster than the other two. I got a significant amount of speedup just by tweaking the code for some of those operations (e.g. i2osp and bitsize). It made no difference with Calc and with Pari only the verify operations sped up a tiny bit. Looking at NYTProf output, the GMP code could still be sped up (e.g. we're spending a non-trivial amount of time in octect_xor which could be quite a bit faster). Of course this is all dependent on the use case: signing 1M small messages, or 1 giant one. I'm a little surprised at the difference between Math::BigInt::GMP and Math::BigInt::Pari here. Usually I've seen GMP a little faster, but rarely by this much. Note that this is using the Math::BigInt objects in all cases, not Math::GMPz or Math::Pari objects. Using Math::GMPz would be a bit faster, and of course implementing things in C using gmp directly would be faster yet. I view all of this with some reserve, since I don't think all the functionality is tested by the current test suite, and there are interoperability concerns that the test suite may not cover. Also things like: - Does changing the mgf1 function to match RFC3447 cause issues? - Does changing the PKCS1v15 encode functions to match RFC3447 cause issues? Why does the SS/PKCSv15.pm encoded message not match the 2.1 specification? (same with RSAES).

Fri Dec 28 12:33:10 2012 DANAJ [...] cpan.org - Correspondence added

I've uploaded the first version to CPAN as Alt::Crypt::RSA::BigInt. Note that this uses Ingy's Alt namespace idea, so it is a direct replacement for Crypt::RSA (it installs as Crypt::RSA). To make sure this wasn't an x86_64-specific performance effect, I ran the same benchmark on an Itanium 2 and an HP PA-8600 machine with similar results. The new code using Math::BigInt::GMP runs t/15-benchmark.t 5 to 11 times faster than Crypt::RSA 1.99. I tried bumping the Pari code to 2.3.5, which made only a ~10% difference on the PA-8600 machine, still leaving it 4-9x slower than the new GMP code. These are just the sign and verify benchmarks in t/15-benchmark.t. I can run other benchmarks or tests if there are some better ones (e.g. oaep with long messages) I've tested it on various x86 Linux configurations, Cygwin, Win32 (Strawberry), and a few different non-x86 Linux systems. Thanks to super speedy CPAN testers, it looks like x86 FreeBSD works also. This still leaves a lot of ground to cover. It does *not* work on 5.6.2 because of some dependency issues. These could be probably be solved if this is something we really care about. What I have not done is a lot of testing of things such as whether we really are getting properly random keys and the like. For this version, I tried to leave most of the code and documentation as-is, just removing Pari and the two modeules that used it. I did make some changes for performance as mentioned above. One change that may be a bigger issue is changing the mgf1 function to match the spec (RT 45533). This module should fix RTs 4877, 45533, 52689, 61392, 63007, 64883, and 76655. I included the RT 69376 test in the xt/ directory that reproduces this issue, but decided to fix it later, as I think a proper fix will change the serialization, which would affect interoperability. I'm not thrilled with the length of the dependency chain, a lot of which comes from Crypt::Random::Source, which is used by Bytes::Random::Secure. There aren't many other good options that I see. Let me know if this looks like the right track, and how it works.

Fri Dec 28 13:26:08 2012 DANAJ [...] cpan.org - Correspondence added

I've fixed an issue in RSA/Primitives.pm that I found doing an OpenPGP test. I'll do more tests tonight and do an update.

Sun Dec 30 13:45:09 2012 DANAJ [...] cpan.org - Correspondence added

Version 0.03 on CPAN fixes RT 69376. I believe RT 59923's answer is: $pri->{Password} = 'my new secret'; though one has to be careful to do this while not hidden. Perhaps this is something a function would be better for. The only other RT's that I haven't verified are 4877 and 50356 which are failures on HP/UX machines. I no longer have access to HP/UX boxes, but they look like they were probably Math::Pari problems (segfault in test 11). It seems to work with Crypt::OpenPGP, Net::SSH::Perl, and Data::Encrypted with no changes needed to those. The latter not so useful given that anything new won't be in SSH1 format. We should probably add a PEM module using Convert::PEM or Convert::ASN1 plus some code.

Thu Feb 07 03:38:27 2013 davido [...] cpan.org - Correspondence added

On Fri Dec 28 09:33:10 2012, DANAJ wrote: Show quoted text

> I'm not thrilled with the length of the dependency chain, > a lot of which comes from Crypt::Random::Source, which is used by > Bytes::Random::Secure. There aren't many other good options > that I see.

Just a follow-up: Thanks to DANAJ's new Crypt::Random::Seed, Bytes::Random::Secure has been able to move away from its Crypt::Random::Source dependency, and consequently, has cut its dependency chain down to just a few non-core modules: Crypt::Random::Seed Crypt::Random::TESHA256 Test::Warn Test::Warn is the only module in that set that drags in a few non-Core modules, and in the next few days I intend to make it an optional dependency anyway. All versions of Bytes::Random::Secure from 0.20+ use Crypt::Random::Seed instead of Crypt::Random::Source.