Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

ElGamal public key encryption can loop forever for too larges values of 'p' #30

Open
gozer opened this issue Nov 17, 2015 · 7 comments · May be fixed by #31
Open

ElGamal public key encryption can loop forever for too larges values of 'p' #30

gozer opened this issue Nov 17, 2015 · 7 comments · May be fixed by #31

Comments

@gozer
Copy link

gozer commented Nov 17, 2015

if $p is very large (and it's not a Math::BigInt), $p-1 can overflow and return "inf", causing the loop below to just loop forever looking for relative primeness against infinity.

sub gen_k {
    my($p) = @_;
    [...]
    my $p_minus1 = $p - 1;
    [...]
    $k = Math::BigInt->new($k);
    while (1) {
        last if Math::BigInt::bgcd($k, $p_minus1) == 1;
        $k++;
    }
gozer added a commit to gozer/Crypt-OpenPGP that referenced this issue Nov 17, 2015
@gozer
ElGamal: key's p can be a large integer, use Bigint
0f5a675 
Fixes btrott#30
@gozer gozer linked a pull request Nov 17, 2015 that will close this issue
Open
@sergeyromanov
Copy link
Collaborator

Hi, thank you for the report and the patch!

Would you be so kind to provide a short test to accompany them (say, under t/52-gh30.t)?

@gozer
Copy link
Author

gozer commented Nov 25, 2015

Yes, certainly! Will do

@gozer
Copy link
Author

gozer commented Nov 25, 2015

I just need to find the offending GPG key that triggered this and create a test case

@dylanwh
Copy link

dylanwh commented Sep 20, 2016

we're running into this again in production as we moved to a newer version of Crypt::OpenPGP. Can you please accept the pull request and get the fixed version up to CPAN? I'm asking one of the people with an offending key if they'd like have their pubkey pushed as a test example.

@dylanwh
Copy link

dylanwh commented Sep 20, 2016

Here's code that will trigger the bug.

test-case.txt

@dylanwh dylanwh mentioned this issue Sep 20, 2016
Closed
@barnsls
Copy link

barnsls commented Dec 17, 2017

I have just encountered this problem with version 1.12 from CPAN. I applied the fix locally & it works fine. Can we push the fix to CPAN so that other people don't run into the same problem?

timlegge pushed a commit to timlegge/Crypt-OpenPGP that referenced this issue Sep 30, 2024
@gozer @timlegge
ElGamal: key's p can be a large integer, use Bigint
4221098 
Fixes btrott#30
@timlegge
Copy link

timlegge commented Oct 3, 2024

@gozer Issue can be closed as 1.15 has been released with the fix. I don't have admin here so I cannot close this issue

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

ElGamal: key's p can be a large integer, use Bigint gozer/Crypt-OpenPGP
5 participants
@dylanwh @gozer @timlegge @sergeyromanov @barnsls