Ed25519.php — JetBackup – Backup, Restore & Migrate 3.1.13.4

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

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

Ed25519.php

331 lines

1	<?php
2
3	/**
4	* Ed25519
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
24	class Ed25519 extends TwistedEdwards
25	{
26	public const HASH = 'sha512';
27	/*
28	Per https://tools.ietf.org/html/rfc8032#page-6 EdDSA has several parameters, one of which is b:
29
30	2. An integer b with 2^(b-1) > p. EdDSA public keys have exactly b
31	bits, and EdDSA signatures have exactly 2*b bits. b is
32	recommended to be a multiple of 8, so public key and signature
33	lengths are an integral number of octets.
34
35	SIZE corresponds to b
36	*/
37	public const SIZE = 32;
38
39	public function __construct()
40	{
41	// 2^255 - 19
42	$this->setModulo(new BigInteger('7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED', 16));
43	$this->setCoefficients(
44	// -1
45	new BigInteger('7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC', 16), // a
46	// -121665/121666
47	new BigInteger('52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3', 16) // d
48	);
49	$this->setBasePoint(
50	new BigInteger('216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A', 16),
51	new BigInteger('6666666666666666666666666666666666666666666666666666666666666658', 16)
52	);
53	$this->setOrder(new BigInteger('1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED', 16));
54	// algorithm 14.47 from http://cacr.uwaterloo.ca/hac/about/chap14.pdf#page=16
55	/*
56	$this->setReduction(function($x) {
57	$parts = $x->bitwise_split(255);
58	$className = $this->className;
59
60	if (count($parts) > 2) {
61	list(, $r) = $x->divide($className::$modulo);
62	return $r;
63	}
64
65	$zero = new BigInteger();
66	$c = new BigInteger(19);
67
68	switch (count($parts)) {
69	case 2:
70	list($qi, $ri) = $parts;
71	break;
72	case 1:
73	$qi = $zero;
74	list($ri) = $parts;
75	break;
76	case 0:
77	return $zero;
78	}
79	$r = $ri;
80
81	while ($qi->compare($zero) > 0) {
82	$temp = $qi->multiply($c)->bitwise_split(255);
83	if (count($temp) == 2) {
84	list($qi, $ri) = $temp;
85	} else {
86	$qi = $zero;
87	list($ri) = $temp;
88	}
89	$r = $r->add($ri);
90	}
91
92	while ($r->compare($className::$modulo) > 0) {
93	$r = $r->subtract($className::$modulo);
94	}
95	return $r;
96	});
97	*/
98	}
99
100	/**
101	* Recover X from Y
102	*
103	* Implements steps 2-4 at https://tools.ietf.org/html/rfc8032#section-5.1.3
104	*
105	* Used by EC\Keys\Common.php
106	*
107	* @param boolean $sign
108	* @return object[]
109	*/
110	public function recoverX(BigInteger $y, bool $sign): array
111	{
112	$y = $this->factory->newInteger($y);
113
114	$y2 = $y->multiply($y);
115	$u = $y2->subtract($this->one);
116	$v = $this->d->multiply($y2)->add($this->one);
117	$x2 = $u->divide($v);
118	if ($x2->equals($this->zero)) {
119	if ($sign) {
120	throw new RuntimeException('Unable to recover X coordinate (x2 = 0)');
121	}
122	return clone $this->zero;
123	}
124	// find the square root
125	/* we don't do $x2->squareRoot() because, quoting from
126	https://tools.ietf.org/html/rfc8032#section-5.1.1:
127
128	"For point decoding or "decompression", square roots modulo p are
129	needed. They can be computed using the Tonelli-Shanks algorithm or
130	the special case for p = 5 (mod 8). To find a square root of a,
131	first compute the candidate root x = a^((p+3)/8) (mod p)."
132	*/
133	$exp = $this->getModulo()->add(new BigInteger(3));
134	$exp = $exp->bitwise_rightShift(3);
135	$x = $x2->pow($exp);
136
137	// If v x^2 = -u (mod p), set x <-- x * 2^((p-1)/4), which is a square root.
138	if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) {
139	$temp = $this->getModulo()->subtract(new BigInteger(1));
140	$temp = $temp->bitwise_rightShift(2);
141	$temp = $this->two->pow($temp);
142	$x = $x->multiply($temp);
143	if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) {
144	throw new RuntimeException('Unable to recover X coordinate');
145	}
146	}
147	if ($x->isOdd() != $sign) {
148	$x = $x->negate();
149	}
150
151	return [$x, $y];
152	}
153
154	/**
155	* Extract Secret Scalar
156	*
157	* Implements steps 1-3 at https://tools.ietf.org/html/rfc8032#section-5.1.5
158	*
159	* Used by the various key handlers
160	*
161	* @return array
162	*/
163	public function extractSecret(string $str)
164	{
165	if (strlen($str) != 32) {
166	throw new LengthException('Private Key should be 32-bytes long');
167	}
168	// 1. Hash the 32-byte private key using SHA-512, storing the digest in
169	// a 64-octet large buffer, denoted h. Only the lower 32 bytes are
170	// used for generating the public key.
171	$hash = new Hash('sha512');
172	$h = $hash->hash($str);
173	$h = substr($h, 0, 32);
174	// 2. Prune the buffer: The lowest three bits of the first octet are
175	// cleared, the highest bit of the last octet is cleared, and the
176	// second highest bit of the last octet is set.
177	$h[0] = $h[0] & chr(0xF8);
178	$h = strrev($h);
179	$h[0] = ($h[0] & chr(0x3F)) \| chr(0x40);
180	// 3. Interpret the buffer as the little-endian integer, forming a
181	// secret scalar s.
182	$dA = new BigInteger($h, 256);
183
184	return [
185	'dA' => $dA,
186	'secret' => $str,
187	];
188	}
189
190	/**
191	* Encode a point as a string
192	*/
193	public function encodePoint(array $point): string
194	{
195	[$x, $y] = $point;
196	$y = $y->toBytes();
197	$y[0] = $y[0] & chr(0x7F);
198	if ($x->isOdd()) {
199	$y[0] = $y[0] \| chr(0x80);
200	}
201	$y = strrev($y);
202
203	return $y;
204	}
205
206	/**
207	* Creates a random scalar multiplier
208	*/
209	public function createRandomMultiplier(): BigInteger
210	{
211	return $this->extractSecret(Random::string(32))['dA'];
212	}
213
214	/**
215	* Converts an affine point to an extended homogeneous coordinate
216	*
217	* From https://tools.ietf.org/html/rfc8032#section-5.1.4 :
218	*
219	* A point (x,y) is represented in extended homogeneous coordinates (X, Y, Z, T),
220	* with x = X/Z, y = Y/Z, x * y = T/Z.
221	*
222	* @return Integer[]
223	*/
224	public function convertToInternal(array $p): array
225	{
226	if (empty($p)) {
227	return [clone $this->zero, clone $this->one, clone $this->one, clone $this->zero];
228	}
229
230	if (isset($p[2])) {
231	return $p;
232	}
233
234	$p[2] = clone $this->one;
235	$p[3] = $p[0]->multiply($p[1]);
236
237	return $p;
238	}
239
240	/**
241	* Doubles a point on a curve
242	*
243	* @return FiniteField[]
244	*/
245	public function doublePoint(array $p): array
246	{
247	if (!isset($this->factory)) {
248	throw new RuntimeException('setModulo needs to be called before this method');
249	}
250
251	if (!count($p)) {
252	return [];
253	}
254
255	if (!isset($p[2])) {
256	throw new RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
257	}
258
259	// from https://tools.ietf.org/html/rfc8032#page-12
260
261	[$x1, $y1, $z1, $t1] = $p;
262
263	$a = $x1->multiply($x1);
264	$b = $y1->multiply($y1);
265	$c = $this->two->multiply($z1)->multiply($z1);
266	$h = $a->add($b);
267	$temp = $x1->add($y1);
268	$e = $h->subtract($temp->multiply($temp));
269	$g = $a->subtract($b);
270	$f = $c->add($g);
271
272	$x3 = $e->multiply($f);
273	$y3 = $g->multiply($h);
274	$t3 = $e->multiply($h);
275	$z3 = $f->multiply($g);
276
277	return [$x3, $y3, $z3, $t3];
278	}
279
280	/**
281	* Adds two points on the curve
282	*
283	* @return FiniteField[]
284	*/
285	public function addPoint(array $p, array $q): array
286	{
287	if (!isset($this->factory)) {
288	throw new RuntimeException('setModulo needs to be called before this method');
289	}
290
291	if (!count($p) \|\| !count($q)) {
292	if (count($q)) {
293	return $q;
294	}
295	if (count($p)) {
296	return $p;
297	}
298	return [];
299	}
300
301	if (!isset($p[2]) \|\| !isset($q[2])) {
302	throw new RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
303	}
304
305	if ($p[0]->equals($q[0])) {
306	return !$p[1]->equals($q[1]) ? [] : $this->doublePoint($p);
307	}
308
309	// from https://tools.ietf.org/html/rfc8032#page-12
310
311	[$x1, $y1, $z1, $t1] = $p;
312	[$x2, $y2, $z2, $t2] = $q;
313
314	$a = $y1->subtract($x1)->multiply($y2->subtract($x2));
315	$b = $y1->add($x1)->multiply($y2->add($x2));
316	$c = $t1->multiply($this->two)->multiply($this->d)->multiply($t2);
317	$d = $z1->multiply($this->two)->multiply($z2);
318	$e = $b->subtract($a);
319	$f = $d->subtract($c);
320	$g = $d->add($c);
321	$h = $b->add($a);
322
323	$x3 = $e->multiply($f);
324	$y3 = $g->multiply($h);
325	$t3 = $e->multiply($h);
326	$z3 = $f->multiply($g);
327
328	return [$x3, $y3, $z3, $t3];
329	}
330	}
331