#!/usr/bin/perl -s
##
## ElGamal Digital Signatures and Key Generation. 
##
## Copyright (c) 1998, Vipul Ved Prakash.  All rights reserved.
## This code is free software; you can redistribute it and/or modify
## it under the same terms as Perl itself.
##
## $Id: ElGamal.pm,v 0.21 1999/02/20 08:16:30 root Exp root $

package Crypt::ElGamal; 

use Math::Pari qw( PARI Mod nextprime pari2pv gcd floor );
use Math::TrulyRandom; 
use Crypt::Random; 
use Digest::MD5;
use vars qw( $VERSION ); 

( $VERSION ) = '$Revision: 0.21 $' =~ /(\d+\.\d+)/; 
my $SIG      = "Crypt::ElGamal $VERSION"; 
my $BLOCK    = 79; 
my $ENTROPY  = 2;

sub keygen { 

    ## Replace this code to use provable Maurer primes. 

    my ( $key, $size, $v ) = @_; 

    my $g = makerandom ( $size - 4, $v );
    my $x = makerandom ( $size - 4, $v );
    my $p = prime ( $size, $v );
    my $y = Mod ( $g, $p ) ** $x; 

    $key->{ public  }->{ y } = MOD2intpv ( $y ); 
    $key->{ public  }->{ g } = pari2pv $g; 
    $key->{ public  }->{ p } = pari2pv $p; 
    $key->{ private }->{ x } = pari2pv $x; 
    $key->{ size }  = $size; 

}

sub sign { 

    my ( $key, $M ) = @_; 

    my $p = PARI ( $key->{ public  }->{ p } ); 
    my $g = PARI ( $key->{ public  }->{ g } ); 
    my $y = PARI ( $key->{ public  }->{ y } ); 
    my $x = PARI ( $key->{ private }->{ x } ); 

    return 0 if $M > $p; 

    my $p1 = $p - 1;
    my $k  = relprime ( $p1, $key->{ size } - 4);

    my $a = Mod ( $g, $p ) ** $k; 
       $a = MOD2int ( $a );

    my $t = Mod ( $M, $p1 ) - PARI ( $x * $a );
    my $i = Mod ( $k, $p1 ) ** (-1); 

    my $b = MOD2intpv ( $t * $i );
       $a = pari2pv   ( $a );

    return [ $a, $b ];

}

sub verify {

    my ( $key, $a, $b, $M ) = @_;
    my $p = PARI ( $key->{ public  }->{ p } ); 
    my $g = PARI ( $key->{ public  }->{ g } ); 
    my $y = PARI ( $key->{ public  }->{ y } ); 

    ##  check:
    ##  a should not be be divisible by a large prime divisor 
    ##  of p-1.  this should be considered in sign() as well.

    my $q = Mod ( $y, $p ) ** $a;
    my $s = Mod ( $a, $p ) ** $b;

    my $p1 = $q * $s; 
    my $p2 = Mod ( $g, $p ) ** $M; 

    return 1 if ( "$p1" eq "$p2"); 
    return 0;

}    

sub signtext { 

    my ( $key, $text ) = @_; 

    my $md5 = new  Digest::MD5;
    $md5->add ( $text ); 
    my $hex = $md5->hexdigest ();
    my $sign = sign ( $key, Math::Pari::_hex_cvt ( "0x$hex" )  );

    if ( $sign )  {
        my $sig = $SIG . " Signature " . $key->{ id }. ' ' . 
                  $sign->[0]. ', '. $sign->[1]; 
        my @x = $sig =~ /(.{$BLOCK})/g; push @x, $' . ".\n";
        return join "\n", @x; 
    }

    return 0;

}

sub verifytext { 

    my ( $key, $text, $signature ) = @_; 
    $signature =~ /(^$SIG.*?)\./gs; 
    $signature = $1;
    $signature =~ s/\n//gs;

    my ( $scheme, $version, $object, $keyid, $a, $b ) = split /\s|,\s/, $signature; 
    my $md5 = new  Digest::MD5;
    $md5->add ( $text ); 
    my $hex = $md5->hexdigest ();
    return verify ( $key, $a, $b, Math::Pari::_hex_cvt ( "0x$hex" ) );

}


sub makerandom { 

	my ( $size, $verbose ) = @_; 
	return Crypt::Random::makerandom ( $size, 0 );

}
    
sub prime { return nextprime ( makerandom ( @_ ) ) }

sub MOD2intpv { 
    
    my $m = pari2pv ( shift );
    $m =~ /Mod\((\d+)/;
    return $1 if $1;
    return 0;

}

sub MOD2int { 
    
    my $m = pari2pv ( shift );
    $m =~ /Mod\((\d+)/;
    $m = $1;
    return PARI "$m";

}

sub bitsize { 

    my $nstr = shift;
    return 0 if $nstr eq "0";
    return 0 if $nstr =~ /^0x0+$/;

    if ( $nstr =~ /^0x/ ) { 
        $n = Math::Pari::_hex_cvt ( $nstr );
    } else { 
        $n = PARI ( $nstr )
    }

    my $bits = 1; my $t = PARI (2);

    while ( $n = floor ( $n / $t ) ) { $bits++ };
    return $bits;

}

'True Value';