Skip Menu |
 

This queue is for tickets about the Crypt-RSA CPAN distribution.

Report information
The Basics
Id: 52689
Status: open
Priority: 0/
Queue: Crypt-RSA

People
Owner: Nobody in particular
Requestors: dkg [...] fifthhorseman.net
Cc: CARNIL [...] cpan.org
kmx [...] cpan.org
AdminCc:

Bug Information
Severity: (no value)
Broken in: (no value)
Fixed in: (no value)



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>
Download (untitled) / with headers
text/plain 1.5k
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.

From: mutant.nz [...] gmail.com
Download (untitled) / with headers
text/plain 240b
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.
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>
Download (untitled) / with headers
text/plain 597b
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.

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>
Download (untitled) / with headers
text/plain 407b
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.

From: mutant.nz [...] gmail.com
Download (untitled) / with headers
text/plain 1.2k
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.
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>
Download (untitled) / with headers
text/plain 1.5k
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.

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
Download (untitled) / with headers
text/plain 1.1k
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.
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>
Download (untitled) / with headers
text/plain 974b
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
Download (untitled) / with headers
text/plain 1.5k
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.
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>
Download (untitled) / with headers
text/plain 1.9k
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.
Download (untitled) / with headers
text/plain 3.5k
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).
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.
Download (untitled) / with headers
text/plain 123b
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.
Download (untitled) / with headers
text/plain 721b
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.
Download (untitled) / with headers
text/plain 808b
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.


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.