Ed448.php — JetBackup – Backup, Restore & Migrate trunk

backup / src / JetBackup / 3rdparty / phpseclib3 / Crypt / EC / Curves / Ed448.php

backup / src / JetBackup / 3rdparty / phpseclib3 / Crypt / EC / Curves Last commit date

Ed448.php

269 lines

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