curve25519-donna for PHP

Curve25519Donna.php

<?php
/**
 * PHP port of https://github.com/agl/curve25519-donna
 *
 * curve25519-donna is copyrighted by Google Inc.
 * 
 * 
 * Usage:
 *  - Generate secret key:
 *      dd if=/dev/urandom bs=32 count=1 of="/path/to/keyfile"
 *
 *  - Load secret key:
 *      $my_secret = Curve25519::load_keyfile("/path/to/keyfile");
 * 
 *  - Generate public key:
 *      $my_public = Curve25519::donna($sk);
 * 
 *  - Generate shared secret:
 *      $shared = Curve25519:donna($my_secret, $somebody_else_public_key);
 *
 * 
 *  Caveat:
 *    There's no exception handler.
 *    Just make sure secret key/public key length is 32 (and countable).
 */
class Curve25519 {

	public static function donna($secret, $base = null) {
		if ($base === null) {
			$base = new SplFixedArray(32);
			$base[0] = 9;
		}
		$c = new Curve25519();
		$bp = new SplFixedArray(10);
		$x = new SplFixedArray(10);
		$z = new SplFixedArray(11);
		$zmone = new SplFixedArray(10);
		$e = new SplFixedArray(32);
		$output = $e;

		for ($i = 0; $i < 32; ++$i) $e[$i] = $secret[$i];
		$e[0] &= 248;
		$e[31] &= 127;
		$e[31] |= 64;

		$c->fexpand($bp, $base);
		$c->cmult($x, $z, $e, $bp);
		$c->crecip($zmone, $z);
		$c->fmul($z, $x, $zmone);
		$c->freduce_coefficients($z);
		$c->fcontract($output, $z);
		return $output;
	}

	public static function load_keyfile($path) {
		if (!is_file($path) || !is_readable($path)) return false;
		$f = file_get_contents($path);
		return SplFixedArray::fromArray(unpack("C*", $f), false);
	}

	protected function feCopy($dst, $src, $offset = null) {
		for ($i = 0; $i < $offset; ++$i) $dst[$i] = $src[$i];
	}

	protected function fsum($output, $in) {
		for ($i = 0; $i < 10; $i += 2) {
			$output[0+$i] += $in[0+$i];
			$output[1+$i] += $in[1+$i];
		}
	}

	protected function fdifference($output, $in) {
		for ($i = 0; $i < 10; ++$i) {
			$output[$i] = ($in[$i] - $output[$i]);
		}
	}

	protected function fscalar_product($output, $in, $scalar) {
		for ($i = 0; $i < 10; ++$i) {
			$output[$i] = ($in[$i] * $scalar);
		}
	}

	protected function fproduct($output, $in2, $in) {
		$output[0] =    $in2[0] * $in[0];
		$output[1] =    $in2[0] * $in[1] +
						$in2[1] * $in[0];
		$output[2] =  2 *  $in2[1] * $in[1] +
						$in2[0] * $in[2] +
						$in2[2] * $in[0];
		$output[3] =    $in2[1] * $in[2] +
						$in2[2] * $in[1] +
						$in2[0] * $in[3] +
						$in2[3] * $in[0];
		$output[4] =    $in2[2] * $in[2] +
					 2 * ($in2[1] * $in[3] +
						$in2[3] * $in[1]) +
						$in2[0] * $in[4] +
						$in2[4] * $in[0];
		$output[5] =    $in2[2] * $in[3] +
						$in2[3] * $in[2] +
						$in2[1] * $in[4] +
						$in2[4] * $in[1] +
						$in2[0] * $in[5] +
						$in2[5] * $in[0];
		$output[6] =  2 * ($in2[3] * $in[3] +
						$in2[1] * $in[5] +
						$in2[5] * $in[1]) +
						$in2[2] * $in[4] +
						$in2[4] * $in[2] +
						$in2[0] * $in[6] +
						$in2[6] * $in[0];
		$output[7] =    $in2[3] * $in[4] +
						$in2[4] * $in[3] +
						$in2[2] * $in[5] +
						$in2[5] * $in[2] +
						$in2[1] * $in[6] +
						$in2[6] * $in[1] +
						$in2[0] * $in[7] +
						$in2[7] * $in[0];
		$output[8] =    $in2[4] * $in[4] +
					 2 * ($in2[3] * $in[5] +
						$in2[5] * $in[3] +
						$in2[1] * $in[7] +
						$in2[7] * $in[1]) +
						$in2[2] * $in[6] +
						$in2[6] * $in[2] +
						$in2[0] * $in[8] +
						$in2[8] * $in[0];
		$output[9] =    $in2[4] * $in[5] +
						$in2[5] * $in[4] +
						$in2[3] * $in[6] +
						$in2[6] * $in[3] +
						$in2[2] * $in[7] +
						$in2[7] * $in[2] +
						$in2[1] * $in[8] +
						$in2[8] * $in[1] +
						$in2[0] * $in[9] +
						$in2[9] * $in[0];
		$output[10] = 2 * ($in2[5] * $in[5] +
						$in2[3] * $in[7] +
						$in2[7] * $in[3] +
						$in2[1] * $in[9] +
						$in2[9] * $in[1]) +
						$in2[4] * $in[6] +
						$in2[6] * $in[4] +
						$in2[2] * $in[8] +
						$in2[8] * $in[2];
		$output[11] =   $in2[5] * $in[6] +
						$in2[6] * $in[5] +
						$in2[4] * $in[7] +
						$in2[7] * $in[4] +
						$in2[3] * $in[8] +
						$in2[8] * $in[3] +
						$in2[2] * $in[9] +
						$in2[9] * $in[2];
		$output[12] =   $in2[6] * $in[6] +
					 2 * ($in2[5] * $in[7] +
						$in2[7] * $in[5] +
						$in2[3] * $in[9] +
						$in2[9] * $in[3]) +
						$in2[4] * $in[8] +
						$in2[8] * $in[4];
		$output[13] =   $in2[6] * $in[7] +
						$in2[7] * $in[6] +
						$in2[5] * $in[8] +
						$in2[8] * $in[5] +
						$in2[4] * $in[9] +
						$in2[9] * $in[4];
		$output[14] = 2 * ($in2[7] * $in[7] +
						$in2[5] * $in[9] +
						$in2[9] * $in[5]) +
						$in2[6] * $in[8] +
						$in2[8] * $in[6];
		$output[15] =   $in2[7] * $in[8] +
						$in2[8] * $in[7] +
						$in2[6] * $in[9] +
						$in2[9] * $in[6];
		$output[16] =   $in2[8] * $in[8] +
					 2 * ($in2[7] * $in[9] +
						$in2[9] * $in[7]);
		$output[17] =   $in2[8] * $in[9] +
						$in2[9] * $in[8];
		$output[18] = 2 *  $in2[9] * $in[9];
	}

	protected function freduce_degree($output) {
		$output[8] += $output[18] << 4;
		$output[8] += $output[18] << 1;
		$output[8] += $output[18];
		$output[7] += $output[17] << 4;
		$output[7] += $output[17] << 1;
		$output[7] += $output[17];
		$output[6] += $output[16] << 4;
		$output[6] += $output[16] << 1;
		$output[6] += $output[16];
		$output[5] += $output[15] << 4;
		$output[5] += $output[15] << 1;
		$output[5] += $output[15];
		$output[4] += $output[14] << 4;
		$output[4] += $output[14] << 1;
		$output[4] += $output[14];
		$output[3] += $output[13] << 4;
		$output[3] += $output[13] << 1;
		$output[3] += $output[13];
		$output[2] += $output[12] << 4;
		$output[2] += $output[12] << 1;
		$output[2] += $output[12];
		$output[1] += $output[11] << 4;
		$output[1] += $output[11] << 1;
		$output[1] += $output[11];
		$output[0] += $output[10] << 4;
		$output[0] += $output[10] << 1;
		$output[0] += $output[10];
	}

	protected function div_by_2_26($v) {
		$highword = $v >> 32;
		$sign = $highword >> 31;
		$roundoff = $sign >> 6;
		return ($v + $roundoff) >> 26;
	}

	protected function div_by_2_25($v) {
		$highword = $v > 32;
		$sign = $highword >> 31;
		$roundoff = $sign >> 7;
		return ($v + $roundoff) >> 25;
	}

	protected function div_s32_by_2_25($v) {
		$roundoff = ($v >> 31) >> 7;
		return ($v + $roundoff) >> 25;
	}

	protected function freduce_coefficients($output) {
		$output[10] = 0;

		for ($i = 0; $i < 10; $i += 2) {
			$over = $this->div_by_2_26($output[$i]);
			$output[$i] -= $over << 26;
			$output[$i+1] += $over;
			$over = $this->div_by_2_25($output[$i+1]);
			$output[$i+1] -= $over << 25;
			$output[$i+2] += $over;
		}

		$output[0] += $output[10] << 4;
		$output[0] += $output[10] << 1;
		$output[0] += $output[10];

		$output[10] = 0;

		$over = $this->div_by_2_26($output[0]);
		$output[0] -= $over << 26;
		$output[1] += $over;

		$over32 = $this->div_s32_by_2_25($output[1]);
		$output[1] -= $over32 << 25;
		$output[2] += $over32;
	}

	protected function fmul($output, $in, $in2) {
		$t = new SplFixedArray(19);
		$this->fproduct($t, $in, $in2);
		$this->freduce_degree($t);
		$this->freduce_coefficients($t);
		$this->feCopy($output, $t, 10);
	}

	protected function fsquare_inner($output, $in) {
		$output[0] =       $in[0] * $in[0];
		$output[1] =  2 *  $in[0] * $in[1];
		$output[2] =  2 * ($in[1] * $in[1] +
						   $in[0] * $in[2]);
		$output[3] =  2 * ($in[1] * $in[2] +
						   $in[0] * $in[3]);
		$output[4] =       $in[2] * $in[2] +
					  4 *  $in[1] * $in[3] +
					  2 *  $in[0] * $in[4];
		$output[5] =  2 * ($in[2] * $in[3] +
						   $in[1] * $in[4] +
						   $in[0] * $in[5]);
		$output[6] =  2 * ($in[3] * $in[3] +
						   $in[2] * $in[4] +
						   $in[0] * $in[6] +
					  2 *  $in[1] * $in[5]);
		$output[7] =  2 * ($in[3] * $in[4] +
						   $in[2] * $in[5] +
						   $in[1] * $in[6] +
						   $in[0] * $in[7]);
		$output[8] =       $in[4] * $in[4] +
					  2 * ($in[2] * $in[6] +
						   $in[0] * $in[8] +
					  2 * ($in[1] * $in[7] +
						   $in[3] * $in[5]));
		$output[9] =  2 * ($in[4] * $in[5] +
						   $in[3] * $in[6] +
						   $in[2] * $in[7] +
						   $in[1] * $in[8] +
						   $in[0] * $in[9]);
		$output[10] = 2 * ($in[5] * $in[5] +
						   $in[4] * $in[6] +
						   $in[2] * $in[8] +
					  2 * ($in[3] * $in[7] +
						   $in[1] * $in[9]));
		$output[11] = 2 * ($in[5] * $in[6] +
						   $in[4] * $in[7] +
						   $in[3] * $in[8] +
						   $in[2] * $in[9]);
		$output[12] =      $in[6] * $in[6] +
					  2 * ($in[4] * $in[8] +
					  2 * ($in[5] * $in[7] +
						   $in[3] * $in[9]));
		$output[13] = 2 * ($in[6] * $in[7] +
						   $in[5] * $in[8] +
						   $in[4] * $in[9]);
		$output[14] = 2 * ($in[7] * $in[7] +
						   $in[6] * $in[8] +
					  2 *  $in[5] * $in[9]);
		$output[15] = 2 * ($in[7] * $in[8] +
						   $in[6] * $in[9]);
		$output[16] =      $in[8] * $in[8] +
					  4 *  $in[7] * $in[9];
		$output[17] = 2 *  $in[8] * $in[9];
		$output[18] = 2 *  $in[9] * $in[9];
	}

	protected function fsquare($output, $in) {
		$t = new SplFixedArray(19);
		$this->fsquare_inner($t, $in);
		$this->freduce_degree($t);
		$this->freduce_coefficients($t);
		$this->feCopy($output, $t, 10);
	}

	protected function load_element($out, $in, $offset, $start, $shift, $mask) {
		$out[$offset] = ((
				$in[$start+0] |
				$in[$start+1] << 8 |
				$in[$start+2] << 16 |
				$in[$start+3] << 24) >> $shift) & $mask;
	}

	protected function fexpand($output, $input) {
		$this->load_element($output, $input, 0, 0, 0, 0x3ffffff);
		$this->load_element($output, $input, 1, 3, 2, 0x1ffffff);
		$this->load_element($output, $input, 2, 6, 3, 0x3ffffff);
		$this->load_element($output, $input, 3, 9, 5, 0x1ffffff);
		$this->load_element($output, $input, 4, 12, 6, 0x3ffffff);
		$this->load_element($output, $input, 5, 16, 0, 0x1ffffff);
		$this->load_element($output, $input, 6, 19, 1, 0x3ffffff);
		$this->load_element($output, $input, 7, 22, 3, 0x1ffffff);
		$this->load_element($output, $input, 8, 25, 4, 0x3ffffff);
		$this->load_element($output, $input, 9, 28, 6, 0x3ffffff);
	}

	protected function store_element($out, $in, $i, $s) {
		$out[$s+0] |= $in[$i] & 0xff;
		$out[$s+1] = ($in[$i] >> 8) & 0xff;
		$out[$s+2] = ($in[$i] >> 16) & 0xff;
		$out[$s+3] = ($in[$i] >> 24) & 0xff;
	}

	protected function fcontract($output, $input) {
		for ($j = 0; $j < 2; ++$j) {
			for ($i = 0; $i < 9; ++$i) {
				if (($i & 1) === 1) {
					$mask = $input[$i] >> 31;
					$carry = -(($input[$i] & $mask) >> 25);
					$input[$i] += $carry << 25;
					$input[$i+1] -= $carry;
				} else {
					$mask = $input[$i] >> 31;
					$carry = -(($input[$i] & $mask) >> 26);
					$input[$i] += $carry << 26;
					$input[$i+1] -= $carry;
				}
			}
			$mask = $input[9] >> 31;
			$carry = -(($input[9] & $mask) >> 25);
			$input[9] += $carry << 25;
			$input[0] -= $carry * 19;
		}

		$mask = $input[0] >> 31;
		$carry = -(($input[0] & $mask) >> 26);
		$input[0] += $carry << 26;
		$input[1] -= $carry;

		$input[1] <<= 2;
		$input[2] <<= 3;
		$input[3] <<= 5;
		$input[4] <<= 6;
		$input[6] <<= 1;
		$input[7] <<= 3;
		$input[8] <<= 4;
		$input[9] <<= 6;

		$output[0] = 0;
		$output[16] = 0;

		$this->store_element($output, $input, 0,0);
		$this->store_element($output, $input, 1,3);
		$this->store_element($output, $input, 2,6);
		$this->store_element($output, $input, 3,9);
		$this->store_element($output, $input, 4,12);
		$this->store_element($output, $input, 5,16);
		$this->store_element($output, $input, 6,19);
		$this->store_element($output, $input, 7,22);
		$this->store_element($output, $input, 8,25);
		$this->store_element($output, $input, 9,28);
	}

	protected function fmonty($x2, $z2,
					$x3, $z3,
					$x, $z,
					$xprime, $zprime,
					$qmqp) {
		$origx = new SplFixedArray(10);
		$origxprime = new SplFixedArray(10);
		$zzz = new SplFixedArray(19);
		$xx = new SplFixedArray(19);
		$zz = new SplFixedArray(19);
		$xxprime = new SplFixedArray(19);
		$zzprime = new SplFixedArray(19);
		$zzzprime = new SplFixedArray(19);
		$xxxprime = new SplFixedArray(19);

		$this->feCopy($origx, $x, 10);
		$this->fsum($x, $z);
		$this->fdifference($z, $origx);
		$this->feCopy($origxprime, $xprime, 10);
		$this->fsum($xprime, $zprime);
		$this->fdifference($zprime, $origxprime);
		$this->fproduct($xxprime, $xprime, $z);
		$this->fproduct($zzprime, $x, $zprime);
		$this->freduce_degree($xxprime);
		$this->freduce_coefficients($xxprime);
		$this->freduce_degree($zzprime);
		$this->freduce_coefficients($zzprime);
		$this->feCopy($origxprime, $xxprime, 10);
		$this->fsum($xxprime, $zzprime);
		$this->fdifference($zzprime, $origxprime);
		$this->fsquare($xxxprime, $xxprime);
		$this->fsquare($zzzprime, $zzprime);
		$this->fproduct($zzprime, $zzzprime, $qmqp);
		$this->freduce_degree($zzprime);
		$this->freduce_coefficients($zzprime);
		$this->feCopy($x3, $xxxprime, 10);
		$this->feCopy($z3, $zzprime, 10);
		$this->fsquare($xx, $x);
		$this->fsquare($zz, $z);
		$this->fproduct($x2, $xx, $zz);
		$this->freduce_degree($x2);
		$this->freduce_coefficients($x2);
		$this->fdifference($zz, $xx);
		$this->fscalar_product($zzz, $zz, 121665);
		$this->freduce_coefficients($zzz);
		$this->fsum($zzz, $xx);
		$this->fproduct($z2, $zz, $zzz);
		$this->freduce_degree($z2);
		$this->freduce_coefficients($z2);
	}

	protected function swap_conditional($a, $b, $iswap) {
		$swap = -$iswap;
		for ($i = 0; $i < 10; ++$i) {
			$x = $swap & ($a[$i] ^ $b[$i]);
			$a[$i] = $a[$i] ^ $x;
			$b[$i] = $b[$i] ^ $x;
		}
	}

	protected function cmult($resultx, $resultz, $n, $q) {
		$a = new SplFixedArray(19);
		$b = new SplFixedArray(19); $b[0] = 1;
		$c = new SplFixedArray(19); $c[0] = 1;
		$d = new SplFixedArray(19);
		$nqpqx = $a;
		$nqpqz = $b;
		$nqx = $c;
		$nqz = $d;
		$t = new SplFixedArray(19);
		$e = new SplFixedArray(19);
		$f = new SplFixedArray(19); $f[0] = 1;
		$g = new SplFixedArray(19);
		$h = new SplFixedArray(19); $h[0] = 1;
		$nqpqx2 = $e;
		$nqpqz2 = $f;
		$nqx2 = $g;
		$nqz2 = $h;

		$this->feCopy($nqpqx, $q, 10);

		for ($i = 0; $i < 32; ++$i) {
			$byte = $n[31 - $i];
			for ($j = 0; $j < 8; ++$j) {
				$bit = $byte >> 7;
				$bit &= 1;

				$this->swap_conditional($nqx, $nqpqx, $bit);
				$this->swap_conditional($nqz, $nqpqz, $bit);
				$this->fmonty($nqx2, $nqz2,
					$nqpqx2, $nqpqz2,
					$nqx, $nqz,
					$nqpqx, $nqpqz,
					$q);
				$this->swap_conditional($nqx2, $nqpqx2, $bit);
				$this->swap_conditional($nqz2, $nqpqz2, $bit);

				$t = $nqx;
				$nqx = $nqx2;
				$nqx2 = $t;
				$t = $nqz;
				$nqz = $nqz2;
				$nqz2 = $t;
				$t = $nqpqx;
				$nqpqx = $nqpqx2;
				$nqpqx2 = $t;
				$t = $nqpqz;
				$nqpqz = $nqpqz2;
				$nqpqz2 = $t;

				$byte <<= 1;
			}
		}

		$this->feCopy($resultx, $nqx, 10);
		$this->feCopy($resultz, $nqz, 10);
	}

	protected function crecip($out, $z) {
		$z2 = new SplFixedArray(10);
		$z9 = new SplFixedArray(10);
		$z11 = new SplFixedArray(10);
		$z2_5_0 = new SplFixedArray(10);
		$z2_10_0 = new SplFixedArray(10);
		$z2_20_0 = new SplFixedArray(10);
		$z2_50_0 = new SplFixedArray(10);
		$z2_100_0 = new SplFixedArray(10);
		$t0 = new SplFixedArray(10);
		$t1 = new SplFixedArray(10);

		$this->fsquare($z2,$z);
		$this->fsquare($t1,$z2);
		$this->fsquare($t0,$t1);
		$this->fmul($z9,$t0,$z);
		$this->fmul($z11,$z9,$z2);
		$this->fsquare($t0,$z11);
		$this->fmul($z2_5_0,$t0,$z9);

		$this->fsquare($t0,$z2_5_0);
		$this->fsquare($t1,$t0);
		$this->fsquare($t0,$t1);
		$this->fsquare($t1,$t0);
		$this->fsquare($t0,$t1);
		$this->fmul($z2_10_0,$t0,$z2_5_0);

		$this->fsquare($t0,$z2_10_0);
		$this->fsquare($t1,$t0);
		for ($i = 2;$i < 10;$i += 2) {
			$this->fsquare($t0,$t1);
			$this->fsquare($t1,$t0);
		}
		$this->fmul($z2_20_0,$t1,$z2_10_0);

		$this->fsquare($t0,$z2_20_0);
		$this->fsquare($t1,$t0);
		for ($i = 2;$i < 20;$i += 2) {
			$this->fsquare($t0,$t1);
			$this->fsquare($t1,$t0);
		}
		$this->fmul($t0,$t1,$z2_20_0);

		$this->fsquare($t1,$t0);
		$this->fsquare($t0,$t1);
		for ($i = 2;$i < 10;$i += 2) {
			$this->fsquare($t1,$t0);
			$this->fsquare($t0,$t1);
		}
		$this->fmul($z2_50_0,$t0,$z2_10_0);

		$this->fsquare($t0,$z2_50_0);
		$this->fsquare($t1,$t0);
		for ($i = 2;$i < 50;$i += 2) {
			$this->fsquare($t0,$t1);
			$this->fsquare($t1,$t0);
		}
		$this->fmul($z2_100_0,$t1,$z2_50_0);

		$this->fsquare($t1,$z2_100_0);
		$this->fsquare($t0,$t1);
		for ($i = 2;$i < 100;$i += 2) {
			$this->fsquare($t1,$t0);
			$this->fsquare($t0,$t1);
		}
		$this->fmul($t1,$t0,$z2_100_0);

		$this->fsquare($t0,$t1);
		$this->fsquare($t1,$t0);
		for ($i = 2;$i < 50;$i += 2) {
			$this->fsquare($t0,$t1);
			$this->fsquare($t1,$t0);
		}
		$this->fmul($t0,$t1,$z2_50_0);

		$this->fsquare($t1,$t0);
		$this->fsquare($t0,$t1);
		$this->fsquare($t1,$t0);
		$this->fsquare($t0,$t1);
		$this->fsquare($t1,$t0);
		$this->fmul($out,$t1,$z11);
	}

}