#!/usr/bin/perl

# ($x, $p, $g, $y) = &el_gamal_keygen( $p_or_bits, $g )
#
# Compute a new El Gamal key pair by choosing $x at random
# and computing a corresponding $y.  $p_or_bits may be provided:
# if it is a small number (less than 10000), it specifies the number
# of bits to use for $p; if it is a larger value, it will be used
# as $p directly.  If it is not provided, 512 will be used for the
# number of bits of length for generating $p.  If $g is not provided,
# a random value less than $p is generated.
    use SSLeay;
    my ( $p, $g ) = @_;

    unless ( $p > 10000 ) {
        $p = SSLeay::BN::generate_prime( $p || 512, 0 );
    }
    unless ( $g ) {
        $g = SSLeay::BN::rand( $p->num_bits - 1 );
    }
    my $x = SSLeay::BN::rand( $p->num_bits - 1 );
    my $y = $g->mod_exp( $x, $p );

    return ( $x, $p, $g, $y );
}

# ($a, $b ) = &el_gamal_encrypt( $message, $p, $g, $y )
#
# Encrypt $message using public key ( $p, $g, $y ).
sub el_gamal_encrypt {
    use SSLeay;
    my ( $msg, $p, $g, $y ) = @_;

    my $k;
    do { $k = SSLeay::BN::rand( $p->num_bits - 1 );
    } until $k->gcd( $p - 1 ) == 1;

    my $a = $g->mod_exp( $k, $p );
    my $b = $y->mod_exp( $k, $p );
    $b = $b->mod_mul( $msg, $p );

    return ( $a, $b );
}

# $message = &el_gamal_decrypt( $a, $b, $p, $x ).
#
# Decrypt $a and $b message pair using private key ( $p, $x ).
sub el_gamal_decrypt {
    use SSLeay;
    my ( $a, $b, $p, $x ) = @_;

    my $message = $b->mod_mul(
        $a->mod_exp( $x, $p )->mod_inverse( $p ),
        $p );

    return $message;
}

# ($a, $b ) = &el_gamal_sign( $message, $p, $g, $x )
#
# Sign $message using private key ( $p, $g, $x ).
sub el_gamal_sign {
    use SSLeay;
    my ( $msg, $p, $g, $x ) = @_;

    my $k;
    do { $k = SSLeay::BN::rand( $p->num_bits - 1 );
    } until $k->gcd( $p - 1 ) == 1;

    my $a = $g->mod_exp( $k, $p );
    my $b = $p - 1 + $msg - $x->mod_mul( $a, $p-1 );
    $b = $b->mod_mul( $k->mod_inverse( $p-1 ), $p-1 );

    return ( $a, $b );
}

# $valid = &el_gamal_valid( $message, $a, $b, $p, $g, $y )
#
# Validate that $message matches $a and $b using public key ( $p, $g, $y )
sub el_gamal_valid {
    use SSLeay;
    my ( $msg, $a, $b, $p, $g, $y ) = @_;

    my $lhs = $a->mod_exp( $b, $p );
    $lhs = $y->mod_exp( $a, $p )->mod_mul( $lhs, $p );
    my $rhs = $g->mod_exp( $msg, $p );

    return $lhs == $rhs;
}