"sha1",
256 => "sha256",
);
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 DSA_Insecure_Rand extends Exception {
public $varname = null;
function __construct($varname, $reason) {
$this->varname = $varname;
$message = "Can't generate strong random value for $varname, giving up";
parent::__construct($message);
}
}
function dsa_urandom($bytecount, $varname, $need_strong=FALSE) {
// TODO: port back to gmp if non-limb-based random bindings get merged
$x = openssl_random_pseudo_bytes($bytecount, $cstrong);
if ($need_strong && !$cstrong) {
throw new DSA_Insecure_Rand($varname);
}
return $x;
}
function dsa_randomBits($bitcount, $varname, $need_strong=FALSE) {
// Doesn't ensure the upper most bit is set, don't think that's completely needed
$ret = dsa_urandom(floor($bitcount/8), $varname, $need_strong);
$odd_bits = ($bitcount % 8);
if ($odd_bits) {
$c = ord(dsa_urandom(1, $varname, $need_strong)) >> (8-$odd_bits);
$ret = chr($c).$ret;
}
return bin_to_gmp($ret);
}
// echo gmp_size(dsa_randomBits(6, "foo"))."\n";
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 Json_Line_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"; //"\n";
flush();
}
function done($c="+") {
$var = $this->current;
parent::done($c);
echo json_encode(array("event" => "done", "value" => $var))."\n"; //"$var\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_Invalid extends Exception {
public $part = null;
public $value = null;
public $reason = null;
function __construct($part, $value, $reason) {
$this->part = $part;
$this->value = $value;
$this->reason = $reason;
# XXX: will the name for gmp resources ever change?
if (is_resource($value) && get_resource_type($value) == "GMP integer") {
$value = gmp_strval($value);
}
$message = "Invalid Value for '$part' ($value): $reason";
parent::__construct($message);
}
}
class DSA_CantValidate extends Exception {
public $parts = null;
function __construct($parts) {
$this->parts = $parts;
$message = "Can't Validate, missing key parts: (".implode(", ", $parts).")";
parent::__construct($message);
}
}
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 = intval(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)) {
$dps = dsa_randomBits($seedlen, "domain_parameter_seed");
}
$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-1));
$q = gmp_sub(gmp_add(gmp_pow(2, $this->N-1), gmp_add($U, 1)), gmp_mod($U, 2));
//echo "q: ".gmp_strval($q)." ".gmp_prob_prime($q)."\n";
}
$progress->done();
$progress->start("p");
$offset = gmp_init(1);
for ($counter=0;$counter <= (4*$this->L - 1);$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($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, $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 validatePQ() {
# Uses the algorithm from A.1.1.3 in FIPS 186-3.
global $N_hashalgos;
$missing = array();
$needed = array("p", "q", "domain_parameter_seed", "counter");
foreach ($needed as $needs) {
if (!$this->$needs) {
$missing[] = $needs;
}
}
if ($missing) {
throw new DSA_CantValidate($missing);
}
$L = $this->L;
if (!$L) {
$L = gmp_size($this->p);
}
$N = $this->N;
if (!$N) {
$N = gmp_size($this->q);
}
$outlen = $N;
$min_L = gmp_pow(2, $L-1);
# XXX: 3. 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, return INVALID.
if ($this->counter > (4*$L - 1)) {
$flo = 4*$L - 1;
throw new DSA_Invalid("counter", $this->counter, "larger than 4*L - 1 ($flo)");
}
$seedlen = gmp_size($this->domain_parameter_seed);
//echo $seedlen."\n";
if ($seedlen < $N) {
throw new DSA_Invalid("seed length", $seedlen, "smaller than N ($N)");
}
$raw_dps_data = gmp_to_bin($this->domain_parameter_seed);
$U = gmp_mod(gmp_init(hash($N_hashalgos[$N], $raw_dps_data), 16), gmp_pow(2, $N-1));
$computed_q = gmp_sub(gmp_add(gmp_pow(2, $this->N-1), gmp_add($U, 1)), gmp_mod($U, 2));
if (gmp_cmp($computed_q, $this->q) != 0) {
$cq_s = gmp_strval($computed_q);
throw new DSA_Invalid("q", $this->q, "not the same as the computed value for q ($cq_s)");
}
if (!gmp_prob_prime($computed_q)) {
throw new DSA_Invalid("q", $computed_q, "not prime");
}
$n = intval(ceil($L/$outlen))-1;
$b = $L - 1 - ($n * $outlen);
$offset = gmp_init(1);
for ($i=0; $i <= $this->counter;$i++) {
$V = array();
for ($j = 0; $j <= $n; $j++) {
$V[] = gmp_strval(gmp_init(hash($N_hashalgos[$N], gmp_to_bin(gmp_mod(gmp_add(gmp_add($this->domain_parameter_seed, $offset), $j), gmp_pow(2, $seedlen)))), 16));
}
$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)))));
}
$W = gmp_add($W, gmp_mul(gmp_mod($V[$n], gmp_pow(2, $b)), gmp_pow(2, gmp_strval(gmp_mul($n, $outlen)))));
$X = gmp_add($W, gmp_pow(2, $L-1));
$c = gmp_mod($X, gmp_mul(2, $this->q));
$computed_p = gmp_sub($X, gmp_sub($c, 1));
$pprime = gmp_prob_prime($computed_p);
if ($pprime && gmp_cmp($computed_p, $min_L) >= 0) {
break;
}
$offset = gmp_add(gmp_add($offset, $n), 1);
}
if ($i != $this->counter) {
throw new DSA_Invalid("counter", $this->counter, "not the same as the computed counter value ($i)");
}
if (gmp_cmp($computed_p, $this->p) != 0) {
$cp_s = gmp_strval($computed_p);
throw new DSA_Invalid("p", $this->p, "not the same as the computed value for p ($cp_s)");
}
if (!gmp_prob_prime($computed_p)) {
throw new DSA_Invalid("p", $computed_p, "not prime");
}
return 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;
$count_too_high = pow(2, 16);
$progress->start("g");
while (gmp_cmp($g, 2) < 0) {
$progress->disp(".");
$count = $count + 1;
// XXX/TODO: maybe this should internally cause dps/p/q to be regenerated, otoh the spec says to return Invalid
if ($count >= $count_too_high) {
// XXX: not sure if the primary target here should be gcount or dps
$dps_s = gmp_strval($this->domain_parameter_seed);
throw new DSA_Invalid("gcount", $count, "can't find an appropriate g for the domain_parameter_seed ($dps_s)");
}
/*
XXX: The proper behaviour seems to be:
* index'es single byte binary representation is used
* count's 2 bytes are serialized as big endian[1] and used.
The test vectors at prove the old code was wrong.
[1]: afaict anyway, the test vectors all seem to use big endian and "Bit string: [...] The leftmost bit is the most significant bit of the string." Seems to indicate it as well.
*/
$U = gmp_to_bin($this->domain_parameter_seed)."ggen".pack("Cn", $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 validateG() {
# Uses the algorithm from A.2.4 in FIPS 186-3.
global $N_hashalgos;
$missing = array();
$needed = array("p", "q", "domain_parameter_seed", "gindex", "g");
foreach ($needed as $needs) {
if (!$this->$needs) {
$missing[] = $needs;
}
}
if ($missing) {
throw new DSA_CantValidate($missing);
}
if ($this->gindex >= 256) {
throw new DSA_Invalid("gindex", $this->gindex, "larger than 255");
}
if (gmp_cmp(2, $this->g) > 0) {
throw new DSA_Invalid("g", $this->g, "smaller than 2");
}
// XXX: next line is Verify that 2 ≤ g ≤ (p-1)., I'm just checking that g is smaller than p, not if it's <= p-1
if (gmp_cmp($this->g, $this->p) >= 0) {
$p_s = gmp_strval($this->p);
throw new DSA_Invalid("g", $this->g, "larger or equal to p ($p_s)");
}
if (gmp_cmp(gmp_powm($this->g, $this->q, $this->p), 1) != 0) {
$q_s = gmp_strval($this->q);
$p_s = gmp_strval($this->p);
throw new DSA_Invalid("g", $this->g, "g**q mod p (q == $q_s, p == $p_s) != 1");
}
$N = $this->N;
if (!$N) {
$N = gmp_size($this->q);
}
$e = gmp_div(gmp_sub($this->p, 1), $this->q);
$count = 0;
$count_too_high = pow(2, 16);
$computed_g = 0;
while (gmp_cmp($computed_g, 2) < 0) {
$count = $count + 1;
if ($count >= $count_too_high) {
// XXX: not sure if the primary target here should be gcount or dps
$dps_s = gmp_strval($this->domain_parameter_seed);
throw new DSA_Invalid("gcount", $count, "can't find an appropriate g for the domain_parameter_seed ($dps_s)");
}
// see the note in .generateG for the next line
$U = gmp_to_bin($this->domain_parameter_seed)."ggen".pack("Cn", $this->gindex, $count);
$W = gmp_init(hash($N_hashalgos[$N], $U), 16);
$computed_g = gmp_powm($W, $e, $this->p);
}
if (gmp_cmp($computed_g, $this->g) != 0) {
$cg_s = gmp_strval($computed_g);
throw new DSA_Invalid("g", $this->g, "not the same as the computed value for g ($cg_s)");
}
return TRUE;
}
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)
$c = gmp_init(0);
$min = gmp_pow(2, $this->N+64-1);
$progress->start("x");
while (!(gmp_cmp($c, $min) > 0)) {
$progress->disp(".");
$c = dsa_randomBits($this->N+64, "x", TRUE);
}
//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 $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 = dsa_randomBits($this->N+64, "k", TRUE);
$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";
# TODO: The values of r and s shall be checked to determine if r = 0 or s = 0. If either r = 0 or s = 0, a new value of k shall be generated, and the signature shall be recalculated. It is extremely unlikely that r = 0 or s = 0 if signatures are generated properly.
return new Signature($M, array($r, $s));
}
function verify_raw($M, $sig, $hash=TRUE) {
global $N_hashalgos;
$r = $sig[0];
$s = $sig[1];
if (gmp_cmp(0, $r) >= 0 || gmp_cmp($r, $this->q) >= 0) {
return FALSE;
}
if (gmp_cmp(0, $s) >= 0 || gmp_cmp($s, $this->q) >= 0) {
return FALSE;
}
$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);
}
function validate() {
$pqv = $this->validatePQ();
$gv = $this->validateG();
return ($pqv && $gv);
}
}
?>