<?php

/* stupid PHP DSA implementation, Copyright © 2007 Kyle McFarland */

/* TODO: 
    * write JSON-related functionality, could be harder than expected
        because serializing gmp objects as an int requires either something
        supporting serializing/deserializing them, or some extensibility
        support in the json lib
*/

error_reporting(E_ALL);

$N_hashalgos = array(
    160 => "sha1",
    256 => "sha256",
);

$bytesInLimb = 4;

function gmp_to_bytearray($value) {
    $ret = array();
    while (gmp_cmp($value, 0) > 0) {
        $ret[] = gmp_intval(gmp_and($value, gmp_init("FF", 16)));
        $value = gmp_div($value, gmp_pow("2", "8"));
    };
    return array_reverse($ret);
}

function gmp_to_bin($value) {
    $ba = gmp_to_bytearray($value);
    return call_user_func_array("pack", array_merge(array("C*"), $ba));
}

function bin_to_gmp($value) {
    return gmp_init(bin2hex($value), 16);
}

function gmp_size($value) {
    $size = 0;
    $lastfound = 0;
    while ($lastfound != -1) {
        $size = $lastfound+1;
        $lastfound = gmp_scan1($value, $lastfound+1);
    }
    return $size;
}

class Default_Progress {
    public $current = null;

    function start($var) {
        $this->current = $var;
    }

    function disp($c) {}

    function done($c="+") {
        if ($c) {
            $this->disp($c);
        }
        $this->current = null;
    }
}

class OpenSSL_Progress extends Default_Progress {
    function start($var) {
        parent::start($var);
        echo "Generating $var: ";
    }

    function disp($c) {
        parent::disp($c);
        echo $c;
        flush();
    }

    function done($c="+") {
        parent::done($c);
        echo "\n";
        flush();
    }
}

class OpenSSL2_Progress extends OpenSSL_Progress {
    public $count = 0;

    function disp($c) {
        $this->count += 1;
        if (($this->count > 10) && ($c == ".") && ($this->count % 10)) {
            return;
        }
        parent::disp($c);
    }

    function done($c="+") {
        parent::done($c);
        $this->count = 0;
    }
}

class Number_Progress extends OpenSSL2_Progress {
    public $first = TRUE;

    function _format($count) {
        if ($count > 1) {
            return "$count attempts... ";
        } else {
            return "$count attempt... ";
        }
    }

    function disp($c) {
        if ($c == ".") {
            if (!$this->first) {
                echo str_repeat("\x08", strlen($this->_format($this->count)));
            }
            $this->count += 1;
            echo $this->_format($this->count);
            flush();
            $this->first = FALSE;
        } else if ($c == "+") {
            echo "done";
        }
    }

    function done($c="+") {
        parent::done($c);
        $this->first = TRUE;
    }
}

class Ajax_Progress extends Default_Progress {
    function start($var) {
        parent::start($var);
        echo json_encode(array("event" => "start", "value" => $var))."\n";
        flush();
    }

    function disp($c) {
        parent::disp($c);
        echo json_encode(array("event" => "progress", "value" => $c))."\n"; //"<progress>$c</progress>\n";
        flush();
    }

    function done($c="+") {
        $var = $this->current;
        parent::done($c);
        echo json_encode(array("event" => "done", "value" => $var))."\n"; //"<done>$var</done>\n";
        flush();
    }
}
    

class Signature {
    public $text = null;
    public $sig = null;

    function __construct($text, $sig) {
        $this->text = $text;
        $this->sig = $sig;
    }

    function verify($key, $hash=TRUE) {
        return $key->verify($this, $hash);
    }

    function to_json() {
        $ret = array(
            "text" => $this->text,
            "sig" => array_map("gmp_strval", $this->sig),
        );
        return json_encode($ret);
    }
}

class DSA {
    public $N = 160;
    public $L = 1024;
    public $p = null;
    public $q = null;
    public $g = null;
    public $gindex = 1;
    public $y = null;
    public $x = null;
    public $domain_parameter_seed = null;
    public $counter = 0;
    public $progress_class = "Default_Progress";

    function to_json() {
        $ret = array(
            "L" => $this->L,
            "N" => $this->N,
            "p" => gmp_strval($this->p),
            "q" => gmp_strval($this->q),
            "g" => gmp_strval($this->g),
            // gindex
            "y" => gmp_strval($this->y),
            // x
            // domain_parameter_seed
            // counter
        );
        if ($this->gindex) {
            $ret["gindex"] = $this->gindex;
        }
        if ($this->x) {
            $ret["x"] = gmp_strval($this->x);
        }
        if ($this->domain_parameter_seed) {
            $ret["domain_parameter_seed"] = gmp_strval($this->domain_parameter_seed);
        }
        if ($this->counter) {
            $ret["counter"] = $this->counter;
        }
        return json_encode($ret);
    }

    function from_json($json) {
        $data = json_decode($json, true);
        // XXX: don't die when stuff like L/N/gindex/etc. aren't there
        $this->L = $data["L"];
        $this->N = $data["N"];
        $this->p = gmp_init($data["p"]);
        $this->q = gmp_init($data["q"]);
        $this->g = gmp_init($data["g"]);
        $this->y = gmp_init($data["y"]);
        $this->gindex = $data["gindex"];
        $this->domain_parameter_seed = gmp_init($data["domain_parameter_seed"]);
        $this->counter = $data["counter"];
        if (isset($data["x"])) {
            $this->x = gmp_init($data["x"]);
        }
    }

    function generatePQ($seedlen=null, $outlen=null) {
        global $N_hashalgos;
        // TODO: 1. Check that the (L,N) pair is in the list of acceptable (L, N pairs) (see Section 4.2). If the pair is not in the list, then return INVALID.
        // XXX: 2. If (seedlen < N), then return INVALID. <-- slight difference here, we just say that seedlen = N if it's smaller
        //$progress = new Number_Progress();
        $progress = new $this->progress_class;
        if (!$seedlen || $seedlen < $this->N) {
            $seedlen = $this->N;
        }
        if (!$outlen || $outlen < $this->N) {
            $outlen = $this->N;
        }
        $n = ceil($this->L/$outlen)-1;
        $b = $this->L-1-($n * $outlen);
        $q = 0;
        $p = 0;
        while (!gmp_prob_prime($p)) {
            $q = 0;
            $progress->start("q");
            while (!gmp_prob_prime($q)) {
                $progress->disp(".");
                $dps = gmp_init(0);
                $min = gmp_pow(2, $seedlen-1);
                while (!(gmp_cmp($dps, $min) > 0)) {
                    global $bytesInLimb;
                    $dps = gmp_random($seedlen/8/$bytesInLimb);
                }
                $raw_dps_data = gmp_to_bin($dps);
                //echo gmp_strval($dps, 16)."\n";
                //echo bin2hex($raw_dps_data)."\n";
                $U = gmp_mod(gmp_init(hash($N_hashalgos[$this->N], $raw_dps_data), 16), gmp_pow(2, $this->N));
                $q = gmp_or(gmp_or($U, gmp_pow(2, $this->N-1)), 1);
                //echo "q: ".gmp_strval($q)." ".gmp_prob_prime($q)."\n";
            }
            $progress->done();
            $progress->start("p");
            $offset = gmp_init(1);
            for ($counter=0;$counter <= 4095;$counter++) {
                $progress->disp(".");
                $V = array();
                for ($j=0;$j <= $n;$j++) {
                    $V[] = gmp_strval(gmp_init(hash($N_hashalgos[$this->N], gmp_to_bin(gmp_mod(gmp_add(gmp_add($dps, $offset), $j), gmp_pow(2, $seedlen)))), 16));
                }
                //print_r($V);
                $W = gmp_init($V[0]);
                for ($j=1;$j < $n;$j++) {
                    $W = gmp_add($W, gmp_mul($V[$j], gmp_pow(2, gmp_strval(gmp_mul($j, $outlen)))));
                }
                //echo gmp_strval($W)."\n";
                //echo "b: $b\n";
                $W = gmp_add($W, gmp_mul(gmp_mod($V[$n], gmp_pow(2, $b)), gmp_pow(2, gmp_strval(gmp_mul(intval($n), $outlen)))));
                //echo gmp_strval($W)."\n";
                //echo gmp_strval($W)."\n";
                $X = gmp_add($W, gmp_pow(2, $this->L-1));
                $c = gmp_mod($X, gmp_mul(2, $q));
                $p = gmp_sub($X, gmp_sub($c, 1));
                $pprime = gmp_prob_prime($p);
                //echo "p: ".gmp_strval($p)." ".$pprime."\n";
                if ($pprime && gmp_cmp($p, gmp_pow(2, $this->L-1)) >= 0) {
                    $progress->disp("+");
                    break;
                }
                $offset = gmp_add(gmp_add($offset, intval($n)), 1);
            }
            $progress->done("");
        }
        $this->counter = $counter;
        $this->domain_parameter_seed = $dps;
        $this->p = $p;
        $this->q = $q;
        //$raw_dps_data = gmp_to_bin($this->domain_parameter_seed);
        //echo gmp_strval($this->domain_parameter_seed, 16)."\n";
        //echo bin2hex($raw_dps_data)."\n";
        //$U = gmp_mod(gmp_init(hash($N_hashalgos[$this->N], $raw_dps_data), 16), gmp_pow(2, $this->N));
        //echo gmp_strval($U)."\n";
        //$q = gmp_or(gmp_or($U, gmp_pow(2, $this->N-1)), 1);
        //echo gmp_strval($q)." ".gmp_prob_prime($q)."\n";
        //if (!gmp_prob_prime($q)) {
        //    return $this->generatePQ($regenerate_dps=TRUE);
        //}
    }

    function generateG() {
        // TODO: 1. If (index is incorrect), then return INVALID.
        global $N_hashalgos;
        $progress = new $this->progress_class;
        $g = gmp_init(0);
        $e = gmp_div(gmp_sub($this->p, 1), $this->q);
        $count = 0;
        $progress->start("g");
        while (gmp_cmp($g, 2) < 0) {
            $progress->disp(".");
            $count = $count + 1;
            $U = gmp_to_bin($this->domain_parameter_seed)."ggen".$this->gindex.$count;
            $W = gmp_init(hash($N_hashalgos[$this->N], $U), 16);
            $g = gmp_powm($W, $e, $this->p);
        }
        $progress->done();
        $this->g = $g;
    }

    function generate() {
        $this->generatePQ();
        $this->generateG();
        $progress = new $this->progress_class;
        // Generate x, y: this uses a weak version of the Using Extra Random Bits method (B.1.1)
        global $bytesInLimb;
        $c = gmp_init(0);
        $min = gmp_pow(2, $this->N+64-1);
        $progress->start("x");
        while (!(gmp_cmp($c, $min) > 0)) {
            $progress->disp(".");
            $c = gmp_random($this->N+64/8/$bytesInLimb);
        }
        //echo "c: ".gmp_strval($c)."\n";
        $x = gmp_add(gmp_mod($c, gmp_sub($this->q, 1)), 1);
        $progress->done();
        //echo "x: ".gmp_strval($x)."\n";
        $progress->start("y");
        $y = gmp_powm($this->g, $x, $this->p);
        $progress->done();
        //echo "y: ".gmp_strval($y)."\n";
        $this->x = $x;
        $this->y = $y;
    }

    function sign($M, $k=null, $hash=TRUE) {
        global $bytesInLimb;
        global $N_hashalgos;
        $kinverse = FALSE;
        if (!$k) {
            // generate k, this is done with a weak version of the Using Extra Random Bits method (B.2.1)
            $c = gmp_init(0);
            $min = gmp_pow(2, $this->N+64-1);
            while (!(gmp_cmp($c, $min) > 0) && !$kinverse) {
                $c = gmp_random($this->N+64/8/$bytesInLimb);
                $k = gmp_add(gmp_mod($c, gmp_sub($this->q, 1)), 1);
                $kinverse = gmp_invert($k, $this->q);
                //echo "k, kinverse: ".gmp_strval($k).", ".gmp_strval($kinverse)."\n";
            }
        } else {
            $kinverse = gmp_invert($k, $this->q);
        }
        $r = gmp_mod(gmp_powm($this->g, $k, $this->p), $this->q);
        if ($hash) {
            $z = substr(hash($N_hashalgos[$this->N], $M), 0, $this->N/8*2); // (multiply by 2 because it returns hex, 2 hex chars in a byte)
        } else {
            $z = bin2hex($M);
        }
        $z = gmp_init($z, 16);
        //echo "r: ".gmp_strval($r)."\n";
        //echo "z: ".gmp_strval($z)."\n";
        $s = gmp_mod(gmp_mul($kinverse, gmp_add($z, gmp_mul($this->x, $r))), $this->q);
        //echo "s: ".gmp_strval($s)."\n";
        return new Signature($M, array($r, $s));
    }

    function verify_raw($M, $sig, $hash=TRUE) {
        global $N_hashalgos;
        $r = $sig[0];
        $s = $sig[1];
        $w = gmp_invert($s, $this->q);
        if ($hash) {
            $z = substr(hash($N_hashalgos[$this->N], $M), 0, $this->N/8*2); // (multiply by 2 because it returns hex, 2 hex chars in a byte)
        } else {
            $z = bin2hex($M);
        }
        $z = gmp_init($z, 16);
        $u1 = gmp_mod(gmp_mul($z, $w), $this->q);
        $u2 = gmp_mod(gmp_mul($r, $w), $this->q);
        //echo "\n";
        //echo "z: ".gmp_strval($z)."\n";
        //echo "w: ".gmp_strval($w)."\n";
        //echo "u1: ".gmp_strval($u1)."\n";
        //echo "u2: ".gmp_strval($u2)."\n";
        // XXX: doing the same thing as pycrypto here and doing it mod'ed, not sure if it's correct or not, but otherwise this is trying to allocate 800 or so MB of RAM
        $v1 = gmp_powm($this->g, $u1, $this->p);
        $v2 = gmp_powm($this->y, $u2, $this->p);
        $v = gmp_mod(gmp_mod(gmp_mul($v1, $v2), $this->p), $this->q);
        if (gmp_cmp($v, $r) == 0) {
            return TRUE;
        } else {
            return FALSE;
        }
    }

    function verify($signature, $hash=TRUE) {
        return $this->verify_raw($signature->text, $signature->sig, $hash);
    }
}

$action = "generate";
if (isset($_GET["action"])) {
    $action = $_GET["action"];
}

function gpc_magicless($data) {
    if (get_magic_quotes_gpc()) {
        $data = stripslashes($data);
    }
    return $data;
}

function load_key_from_post() {
    $keydata = gpc_magicless($_POST["keydata"]);
    $k = new DSA;
    $k->from_json($keydata);
    return $k;
}

if ($action == "generate") {
    header("Content-Type: text/plain");
    header("Cache-Control: no-cache");
    $k = new DSA;
    $k->progress_class = "Ajax_Progress";
    //$k->N = 160;
    //$k->L = 165;
    $k->generate();
    echo $k->to_json();
} else if ($action == "sign") {
    header("Content-Type: text/plain");
    // Get the Key from the POST data
    $k = load_key_from_post();
    $text = gpc_magicless($_POST["text"]);
    $signature = $k->sign($text);
    echo $signature->to_json();
} else if ($action == "verify") {
    header("Content-Type: text/plain");
    $k = load_key_from_post();
    $text = gpc_magicless($_POST["text"]);
    $sig = array_map("gmp_init", json_decode(gpc_magicless($_POST["sig"])));
    echo json_encode(array($k->verify_raw($text, $sig)));
}
/*var_dump($k);
printf("p: %s\nq: %s\ng: %s\ny: %s\nx: %s\ndps: %s\ncounter: %d\n", gmp_strval($k->p), gmp_strval($k->q), gmp_strval($k->g), gmp_strval($k->y), gmp_strval($k->x), gmp_strval($k->domain_parameter_seed), $k->counter);
$sig = $k->sign("foobar");
echo "r: ".gmp_strval($sig->sig[0])."\n"."s: ".gmp_strval($sig->sig[1])."\n";
echo "signature valid: ".$k->verify($sig)."\n";
echo "modified message valid: ".$k->verify_raw("foobarage", $sig->sig)."\n";
$sig->sig[0] = gmp_sub($sig->sig[0], 1);
echo "modified signature valid: ".$k->verify($sig)."\n";
echo "non-hashed signature valid: ".$k->sign("foobarage", null, FALSE)->verify($k, FALSE)."\n";
echo "non-hashed long signature valid: ".$k->sign("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", null, FALSE)->verify($k, FALSE)."\n";
echo 'k->generate exists: '.method_exists($k, 'generate')."\n";
$extk = new DSA;
$extk->p = gmp_init("89884656743115795410265110986801177865684965127520044992489492373859555576407155667268345633510946794974853896005884453717148935560982746883325013611220027966095533738214535185986856910517348252087210308810582893145174508529426136636831467455362348037826511891543118901909376160894886408058460103030709807459");
$extk->q = gmp_init("1003548540460414332259913982385683507603792054877");
$extk->g = gmp_init("6688461843956439718836782240647689670711700967273102728815480179516883089811588887714901101153878141278159216006749886213379664527090903557082589771768378082899939375273766380518318445576012771033089530897360921746015667607651750683592467515502539864142153270737042969323062519970035254186860216347331896434");
$extk->y = gmp_init("78012114235226754380488055999287343169352472804297685772688581768633732502143515632870108315020190921377343787161449558920930169165743722263235940558321588015210341568420663335267520768814209756732116590819689232914042631198246527838276253772881417457074105911409378316405749690293765027289048039035777186244");
echo "extenal signature valid: ".$extk->verify_raw("foo", array(gmp_init("536603820403594545889515425214952020647203860001"), gmp_init("437430210711275471822501469177388674662147762435")), FALSE)."\n";
/*echo $k->counter."\n";
echo gmp_strval($k->domain_parameter_seed)."\n";
echo gmp_strval($k->q)."\n";
echo gmp_strval($k->p)."\n";
echo gmp_strval($k->g)."\n";*/

?>