1<?php 2 3/** 4 * Ed448 5 * 6 * PHP version 5 and 7 7 * 8 * @category Crypt 9 * @package EC 10 * @author Jim Wigginton <terrafrost@php.net> 11 * @copyright 2017 Jim Wigginton 12 * @license http://www.opensource.org/licenses/mit-license.html MIT License 13 */ 14 15namespace phpseclib3\Crypt\EC\Curves; 16 17use phpseclib3\Crypt\EC\BaseCurves\TwistedEdwards; 18use phpseclib3\Crypt\Hash; 19use phpseclib3\Crypt\Random; 20use phpseclib3\Math\BigInteger; 21 22class Ed448 extends TwistedEdwards 23{ 24 const HASH = 'shake256-912'; 25 const SIZE = 57; 26 27 public function __construct() 28 { 29 // 2^448 - 2^224 - 1 30 $this->setModulo(new BigInteger( 31 'FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE' . 32 'FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF', 33 16 34 )); 35 $this->setCoefficients( 36 new BigInteger(1), 37 // -39081 38 new BigInteger('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE' . 39 'FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6756', 16) 40 ); 41 $this->setBasePoint( 42 new BigInteger('4F1970C66BED0DED221D15A622BF36DA9E146570470F1767EA6DE324' . 43 'A3D3A46412AE1AF72AB66511433B80E18B00938E2626A82BC70CC05E', 16), 44 new BigInteger('693F46716EB6BC248876203756C9C7624BEA73736CA3984087789C1E' . 45 '05A0C2D73AD3FF1CE67C39C4FDBD132C4ED7C8AD9808795BF230FA14', 16) 46 ); 47 $this->setOrder(new BigInteger( 48 '3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF' . 49 '7CCA23E9C44EDB49AED63690216CC2728DC58F552378C292AB5844F3', 50 16 51 )); 52 } 53 54 /** 55 * Recover X from Y 56 * 57 * Implements steps 2-4 at https://tools.ietf.org/html/rfc8032#section-5.2.3 58 * 59 * Used by EC\Keys\Common.php 60 * 61 * @param BigInteger $y 62 * @param boolean $sign 63 * @return object[] 64 */ 65 public function recoverX(BigInteger $y, $sign) 66 { 67 $y = $this->factory->newInteger($y); 68 69 $y2 = $y->multiply($y); 70 $u = $y2->subtract($this->one); 71 $v = $this->d->multiply($y2)->subtract($this->one); 72 $x2 = $u->divide($v); 73 if ($x2->equals($this->zero)) { 74 if ($sign) { 75 throw new \RuntimeException('Unable to recover X coordinate (x2 = 0)'); 76 } 77 return clone $this->zero; 78 } 79 // find the square root 80 $exp = $this->getModulo()->add(new BigInteger(1)); 81 $exp = $exp->bitwise_rightShift(2); 82 $x = $x2->pow($exp); 83 84 if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) { 85 throw new \RuntimeException('Unable to recover X coordinate'); 86 } 87 if ($x->isOdd() != $sign) { 88 $x = $x->negate(); 89 } 90 91 return [$x, $y]; 92 } 93 94 /** 95 * Extract Secret Scalar 96 * 97 * Implements steps 1-3 at https://tools.ietf.org/html/rfc8032#section-5.2.5 98 * 99 * Used by the various key handlers 100 * 101 * @param string $str 102 * @return \phpseclib3\Math\PrimeField\Integer 103 */ 104 public function extractSecret($str) 105 { 106 if (strlen($str) != 57) { 107 throw new \LengthException('Private Key should be 57-bytes long'); 108 } 109 // 1. Hash the 57-byte private key using SHAKE256(x, 114), storing the 110 // digest in a 114-octet large buffer, denoted h. Only the lower 57 111 // bytes are used for generating the public key. 112 $hash = new Hash('shake256-912'); 113 $h = $hash->hash($str); 114 $h = substr($h, 0, 57); 115 // 2. Prune the buffer: The two least significant bits of the first 116 // octet are cleared, all eight bits the last octet are cleared, and 117 // the highest bit of the second to last octet is set. 118 $h[0] = $h[0] & chr(0xFC); 119 $h = strrev($h); 120 $h[0] = "\0"; 121 $h[1] = $h[1] | chr(0x80); 122 // 3. Interpret the buffer as the little-endian integer, forming a 123 // secret scalar s. 124 $dA = new BigInteger($h, 256); 125 126 $dA->secret = $str; 127 return $dA; 128 } 129 130 /** 131 * Encode a point as a string 132 * 133 * @param array $point 134 * @return string 135 */ 136 public function encodePoint($point) 137 { 138 list($x, $y) = $point; 139 $y = "\0" . $y->toBytes(); 140 if ($x->isOdd()) { 141 $y[0] = $y[0] | chr(0x80); 142 } 143 $y = strrev($y); 144 145 return $y; 146 } 147 148 /** 149 * Creates a random scalar multiplier 150 * 151 * @return \phpseclib3\Math\PrimeField\Integer 152 */ 153 public function createRandomMultiplier() 154 { 155 return $this->extractSecret(Random::string(57)); 156 } 157 158 /** 159 * Converts an affine point to an extended homogeneous coordinate 160 * 161 * From https://tools.ietf.org/html/rfc8032#section-5.2.4 : 162 * 163 * A point (x,y) is represented in extended homogeneous coordinates (X, Y, Z, T), 164 * with x = X/Z, y = Y/Z, x * y = T/Z. 165 * 166 * @return \phpseclib3\Math\PrimeField\Integer[] 167 */ 168 public function convertToInternal(array $p) 169 { 170 if (empty($p)) { 171 return [clone $this->zero, clone $this->one, clone $this->one]; 172 } 173 174 if (isset($p[2])) { 175 return $p; 176 } 177 178 $p[2] = clone $this->one; 179 180 return $p; 181 } 182 183 /** 184 * Doubles a point on a curve 185 * 186 * @return FiniteField[] 187 */ 188 public function doublePoint(array $p) 189 { 190 if (!isset($this->factory)) { 191 throw new \RuntimeException('setModulo needs to be called before this method'); 192 } 193 194 if (!count($p)) { 195 return []; 196 } 197 198 if (!isset($p[2])) { 199 throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa'); 200 } 201 202 // from https://tools.ietf.org/html/rfc8032#page-18 203 204 list($x1, $y1, $z1) = $p; 205 206 $b = $x1->add($y1); 207 $b = $b->multiply($b); 208 $c = $x1->multiply($x1); 209 $d = $y1->multiply($y1); 210 $e = $c->add($d); 211 $h = $z1->multiply($z1); 212 $j = $e->subtract($this->two->multiply($h)); 213 214 $x3 = $b->subtract($e)->multiply($j); 215 $y3 = $c->subtract($d)->multiply($e); 216 $z3 = $e->multiply($j); 217 218 return [$x3, $y3, $z3]; 219 } 220 221 /** 222 * Adds two points on the curve 223 * 224 * @return FiniteField[] 225 */ 226 public function addPoint(array $p, array $q) 227 { 228 if (!isset($this->factory)) { 229 throw new \RuntimeException('setModulo needs to be called before this method'); 230 } 231 232 if (!count($p) || !count($q)) { 233 if (count($q)) { 234 return $q; 235 } 236 if (count($p)) { 237 return $p; 238 } 239 return []; 240 } 241 242 if (!isset($p[2]) || !isset($q[2])) { 243 throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa'); 244 } 245 246 if ($p[0]->equals($q[0])) { 247 return !$p[1]->equals($q[1]) ? [] : $this->doublePoint($p); 248 } 249 250 // from https://tools.ietf.org/html/rfc8032#page-17 251 252 list($x1, $y1, $z1) = $p; 253 list($x2, $y2, $z2) = $q; 254 255 $a = $z1->multiply($z2); 256 $b = $a->multiply($a); 257 $c = $x1->multiply($x2); 258 $d = $y1->multiply($y2); 259 $e = $this->d->multiply($c)->multiply($d); 260 $f = $b->subtract($e); 261 $g = $b->add($e); 262 $h = $x1->add($y1)->multiply($x2->add($y2)); 263 264 $x3 = $a->multiply($f)->multiply($h->subtract($c)->subtract($d)); 265 $y3 = $a->multiply($g)->multiply($d->subtract($c)); 266 $z3 = $f->multiply($g); 267 268 return [$x3, $y3, $z3]; 269 } 270} 271