suwako / LittleBeast

master
ブランチ master
LittleBeast / src / Std / Lib / Crypto / Ec.php
17.4 KB、443行 生 Blame 履歴
1<?php
2/*************************************************************
3# 076 License
4
5Copyright (c) テクニカル諏訪子
6
7Permission is hereby granted to any person obtaining a copy of the software
8Little Beast (the "Software") to use, modify, merge, copy, publish, distribute,
9sublicense, and/or sell copies of the Software, subject to the following conditions:
10
11 1. **Origin Attribution**:
12 - You must not misrepresent the origin of the Software; you must not claim
13 you created the original Software.
14 - If the Software is used in a product, you must either:
15 a. Provide clear attribution in the product's documentation, user interface,
16 or other visible areas, **OR**
17 b. Pay the original developers a fee they specify in writing.
18 2. **Usage Restriction**:
19 - The Software, or any derivative works, dependencies, or libraries
20 incorporating it, must not be used for censorship or to suppress freedom of
21 speech, expression, or creativity. Prohibited uses include, but are not
22 limited to:
23 - Censorship of so-called "hate speech", visuals, non-mainstream opinions,
24 ideas, or objective reality.
25 - Tools or systems designed to restrict access to information or
26 artistic works.
27 3. **Notice Preservation**:
28 - This license and the above copyright notice must remain intact in all copies
29 of the source code.
30
31THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
32INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
33PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
34HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
35CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
36OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 */
38namespace Std\Lib\Crypto;
39
40/**
41 * 楕円曲線（NISTのP-256・P-384・P-521）：ECDH、ECDSA（RFC 6979の決定的な署名）、PEM
42 *
43 * 例：
44 * $key = Ec::generate('P-256');
45 * $shared = $key->ecdh($peerPoint); // 相手の公開鍵（04||x||y）
46 * $sig = $key->sign($data, 'sha256'); // DER
47 * $ok = Ec::fromPem($pub)->verify($data, $sig, 'sha256');
48 */
49class Ec {
50 public const OID = '1.2.840.10045.2.1';
51
52 /** 曲線：p、a（=-3）、b、n、Gx、Gy、OID、バイト数 */
53 private const CURVES = [
54 'P-256' => [
55 'p' => 'ffffffff00000001000000000000000000000000ffffffffffffffffffffffff',
56 'b' => '5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b',
57 'n' => 'ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551',
58 'x' => '6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296',
59 'y' => '4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5',
60 'oid' => '1.2.840.10045.3.1.7',
61 'len' => 32,
62 ],
63 'P-384' => [
64 'p' => 'fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff',
65 'b' => 'b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef',
66 'n' => 'ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973',
67 'x' => 'aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7',
68 'y' => '3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f',
69 'oid' => '1.3.132.0.34',
70 'len' => 48,
71 ],
72 'P-521' => [
73 'p' => '01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff',
74 'b' => '0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00',
75 'n' => '01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409',
76 'x' => '00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66',
77 'y' => '011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650',
78 'oid' => '1.3.132.0.35',
79 'len' => 66,
80 ],
81 ];
82
83 private static array $cache = [];
84
85 public readonly string $curve;
86 /** 公開鍵の点 [x, y] */
87 public readonly array $q;
88 private ?\GMP $d = null;
89 private array $c;
90
91 private function __construct(string $curve, array $q, ?\GMP $d = null) {
92 $this->curve = $curve;
93 $this->c = self::params($curve);
94 $this->q = $q;
95 $this->d = $d;
96 }
97
98 /** 曲線のパラメータ（GMP） */
99 private static function params(string $curve): array {
100 if (isset(self::$cache[$curve])) return self::$cache[$curve];
101 $c = self::CURVES[$curve] ?? throw new \InvalidArgumentException("EC：未対応の曲線：{$curve}");
102 $p = gmp_init($c['p'], 16);
103 return self::$cache[$curve] = [
104 'p' => $p,
105 'a' => gmp_sub($p, 3),
106 'b' => gmp_init($c['b'], 16),
107 'n' => gmp_init($c['n'], 16),
108 'g' => [gmp_init($c['x'], 16), gmp_init($c['y'], 16)],
109 'oid' => $c['oid'],
110 'len' => $c['len'],
111 ];
112 }
113
114 /** 対応している曲線 */
115 public static function curves(): array {
116 return array_keys(self::CURVES);
117 }
118
119 /**
120 * 新しい鍵を作る
121 *
122 * @param string $curve P-256、P-384、P-521
123 * @return self
124 */
125 public static function generate(string $curve = 'P-256'): self {
126 $c = self::params($curve);
127 do {
128 $d = gmp_import(random_bytes($c['len']));
129 } while (gmp_sign($d) === 0 || gmp_cmp($d, $c['n']) >= 0);
130 return new self($curve, self::mul($c, $d, $c['g']), $d);
131 }
132
133 /**
134 * 公開鍵の点から作る
135 *
136 * @param string $curve 曲線
137 * @param string $point 圧縮しない点（04||x||y）
138 * @return self
139 * @throws \InvalidArgumentException 曲線上の点ではない場合
140 */
141 public static function fromPublic(string $curve, string $point): self {
142 $c = self::params($curve);
143 $l = $c['len'];
144 if (strlen($point) !== 1 + 2 * $l || $point[0] !== "\x04") throw new \InvalidArgumentException('EC：未対応の点の形式');
145 $q = [gmp_import(substr($point, 1, $l)), gmp_import(substr($point, 1 + $l, $l))];
146 if (!self::onCurve($c, $q)) throw new \InvalidArgumentException('EC：曲線上の点ではない');
147 return new self($curve, $q);
148 }
149
150 /**
151 * PEMから読む（PRIVATE KEY、EC PRIVATE KEY、PUBLIC KEY）
152 *
153 * @throws \InvalidArgumentException
154 */
155 public static function fromPem(string $pem): self {
156 foreach (Asn1::unpem($pem) as $b) {
157 if (in_array($b['label'], ['PRIVATE KEY', 'EC PRIVATE KEY', 'PUBLIC KEY'], true) && empty($b['encrypted'])) {
158 return self::fromDer($b['der']);
159 }
160 }
161 throw new \InvalidArgumentException('EC：鍵が見つからない');
162 }
163
164 /**
165 * DERから読む（PKCS#8、SEC 1、SubjectPublicKeyInfo）
166 *
167 * @throws \InvalidArgumentException
168 */
169 public static function fromDer(string $der, ?string $curve = null): self {
170 try {
171 $c = Asn1::expect(Asn1::parse($der), Asn1::SEQUENCE, 2);
172
173 // SubjectPublicKeyInfo
174 if ($c[0]['tag'] === Asn1::SEQUENCE && $c[1]['tag'] === Asn1::BIT_STRING) {
175 return self::fromPublic(self::curveOf($c[0]), Asn1::toBits($c[1]));
176 }
177
178 // PKCS#8
179 if ($c[0]['tag'] === Asn1::INTEGER && $c[1]['tag'] === Asn1::SEQUENCE && ($c[2]['tag'] ?? 0) === Asn1::OCTET_STRING) {
180 return self::fromDer($c[2]['value'], self::curveOf($c[1]));
181 }
182
183 // SEC 1：SEQUENCE { 1, OCTET STRING d, [0] OID, [1] BIT STRING }
184 if ($c[0]['tag'] === Asn1::INTEGER && $c[1]['tag'] === Asn1::OCTET_STRING) {
185 foreach (array_slice($c, 2) as $x) {
186 if ($x['tag'] === 0xA0) $curve = self::curveName(Asn1::toOid(Asn1::children($x)[0]));
187 }
188 if ($curve === null) throw new \InvalidArgumentException('EC：曲線が分からない');
189 $p = self::params($curve);
190 $d = gmp_import($c[1]['value']);
191 if (gmp_sign($d) === 0 || gmp_cmp($d, $p['n']) >= 0) throw new \InvalidArgumentException('EC：不正な秘密鍵');
192 return new self($curve, self::mul($p, $d, $p['g']), $d);
193 }
194 } catch (\UnexpectedValueException $ex) {
195 throw new \InvalidArgumentException('EC：壊れた鍵（'.$ex->getMessage().'）');
196 }
197 throw new \InvalidArgumentException('EC：未対応の鍵の形式');
198 }
199
200 /** AlgorithmIdentifier { ecPublicKey, 曲線のOID } から曲線名 */
201 private static function curveOf(array $alg): string {
202 $a = Asn1::children($alg);
203 if (Asn1::toOid($a[0]) !== self::OID || !isset($a[1]) || $a[1]['tag'] !== Asn1::OID) {
204 throw new \InvalidArgumentException('EC：ECの鍵ではない');
205 }
206 return self::curveName(Asn1::toOid($a[1]));
207 }
208
209 /** OIDから曲線名 */
210 public static function curveName(string $oid): string {
211 foreach (self::CURVES as $name => $c) if ($c['oid'] === $oid) return $name;
212 throw new \InvalidArgumentException("EC：未対応の曲線：{$oid}");
213 }
214
215 public function isPrivate(): bool {
216 return $this->d !== null;
217 }
218
219 /** 公開鍵の点（04||x||y） */
220 public function publicPoint(): string {
221 $l = $this->c['len'];
222 return "\x04".self::pad($this->q[0], $l).self::pad($this->q[1], $l);
223 }
224
225 /** 公開鍵（SubjectPublicKeyInfoのDER） */
226 public function publicDer(): string {
227 return Asn1::seq(Asn1::seq(Asn1::oid(self::OID), Asn1::oid($this->c['oid'])), Asn1::bits($this->publicPoint()));
228 }
229
230 public function publicPem(): string {
231 return Asn1::pem($this->publicDer(), 'PUBLIC KEY');
232 }
233
234 /** 秘密鍵（PKCS#8のPEM） */
235 public function toPem(): string {
236 if ($this->d === null) throw new \LogicException('EC：秘密鍵ではない');
237 $sec1 = Asn1::seq(Asn1::int(1), Asn1::octets(self::pad($this->d, $this->c['len'])), Asn1::explicit(1, Asn1::bits($this->publicPoint())));
238 return Asn1::pem(Asn1::seq(Asn1::int(0), Asn1::seq(Asn1::oid(self::OID), Asn1::oid($this->c['oid'])), Asn1::octets($sec1)), 'PRIVATE KEY');
239 }
240
241 /**
242 * 共有の秘密を計算する（ECDH）
243 *
244 * @param string $peerPoint 相手の公開鍵（04||x||y）
245 * @return string 共有の秘密のx座標
246 * @throws \InvalidArgumentException 不正な点の場合
247 */
248 public function ecdh(string $peerPoint): string {
249 if ($this->d === null) throw new \LogicException('EC：秘密鍵ではない');
250 $peer = self::fromPublic($this->curve, $peerPoint);
251 $s = self::mul($this->c, $this->d, $peer->q);
252 if ($s === null) throw new \InvalidArgumentException('EC：共有の秘密が無限遠点');
253 return self::pad($s[0], $this->c['len']);
254 }
255
256 /**
257 * 署名する（ECDSA、RFC 6979）
258 *
259 * @param string $msg メッセージ
260 * @param string $hash ハッシュ
261 * @return string DER（SEQUENCE { r, s }）
262 */
263 public function sign(string $msg, string $hash = 'sha256'): string {
264 if ($this->d === null) throw new \LogicException('EC：秘密鍵ではない');
265 [$r, $s] = $this->signRaw(hash($hash, $msg, true), $hash);
266 return Asn1::seq(Asn1::int($r), Asn1::int($s));
267 }
268
269 /** 署名のrとs */
270 private function signRaw(string $h1, string $hash): array {
271 $n = $this->c['n'];
272 $l = $this->c['len'];
273 $z = $this->bits2int($h1);
274 $x = self::pad($this->d, $l);
275 $h = self::pad(gmp_mod($z, $n), $l);
276
277 // RFC 6979 3.2
278 $hl = strlen(hash($hash, '', true));
279 $v = str_repeat("\x01", $hl);
280 $k = str_repeat("\x00", $hl);
281 $k = hash_hmac($hash, $v."\x00".$x.$h, $k, true);
282 $v = hash_hmac($hash, $v, $k, true);
283 $k = hash_hmac($hash, $v."\x01".$x.$h, $k, true);
284 $v = hash_hmac($hash, $v, $k, true);
285
286 while (true) {
287 $t = '';
288 while (strlen($t) < $l) {
289 $v = hash_hmac($hash, $v, $k, true);
290 $t .= $v;
291 }
292 $kk = $this->bits2int($t);
293 if (gmp_sign($kk) > 0 && gmp_cmp($kk, $n) < 0) {
294 $p = self::mul($this->c, $kk, $this->c['g']);
295 $r = gmp_mod($p[0], $n);
296 if (gmp_sign($r) > 0) {
297 $s = gmp_mod(gmp_mul(gmp_invert($kk, $n), gmp_add($z, gmp_mul($r, $this->d))), $n);
298 if (gmp_sign($s) > 0) return [$r, $s];
299 }
300 }
301 $k = hash_hmac($hash, $v."\x00", $k, true);
302 $v = hash_hmac($hash, $v, $k, true);
303 }
304 }
305
306 /**
307 * 署名を確認する（ECDSA）
308 *
309 * @param string $msg メッセージ
310 * @param string $sig DER（SEQUENCE { r, s }）
311 * @param string $hash ハッシュ
312 * @return bool
313 */
314 public function verify(string $msg, string $sig, string $hash = 'sha256'): bool {
315 try {
316 $rs = Asn1::expect(Asn1::parse($sig), Asn1::SEQUENCE, 2);
317 if (count($rs) !== 2) return false;
318 $r = Asn1::toInt($rs[0]);
319 $s = Asn1::toInt($rs[1]);
320 } catch (\UnexpectedValueException $e) {
321 return false;
322 }
323 // DERの形が正しい事（BERの別の書き方を拒否する）
324 if (Asn1::seq(Asn1::int($r), Asn1::int($s)) !== $sig) return false;
325
326 $n = $this->c['n'];
327 if (gmp_sign($r) <= 0 || gmp_sign($s) <= 0 || gmp_cmp($r, $n) >= 0 || gmp_cmp($s, $n) >= 0) return false;
328
329 $z = $this->bits2int(hash($hash, $msg, true));
330 $w = gmp_invert($s, $n);
331 $u1 = gmp_mod(gmp_mul($z, $w), $n);
332 $u2 = gmp_mod(gmp_mul($r, $w), $n);
333 $p = self::mul2($this->c, $u1, $this->c['g'], $u2, $this->q);
334 return $p !== null && gmp_cmp(gmp_mod($p[0], $n), $r) === 0;
335 }
336
337 /** ハッシュを整数にする（曲線のビット数に切り詰める） */
338 private function bits2int(string $h): \GMP {
339 $nbits = strlen(gmp_strval($this->c['n'], 2));
340 $z = gmp_import($h);
341 $hbits = 8 * strlen($h);
342 return $hbits > $nbits ? gmp_div_q($z, gmp_pow(2, $hbits - $nbits)) : $z;
343 }
344
345 ///////////////
346 // 点の計算（ヤコビアン座標、a = -3）
347
348 private static function onCurve(array $c, array $q): bool {
349 [$x, $y] = $q;
350 $p = $c['p'];
351 if (gmp_sign($x) < 0 || gmp_sign($y) < 0 || gmp_cmp($x, $p) >= 0 || gmp_cmp($y, $p) >= 0) return false;
352 $l = gmp_mod(gmp_mul($y, $y), $p);
353 $r = gmp_mod(gmp_add(gmp_add(gmp_mul(gmp_mul($x, $x), $x), gmp_mul($c['a'], $x)), $c['b']), $p);
354 return gmp_cmp($l, $r) === 0;
355 }
356
357 /** k * P（アフィン座標で返す、無限遠点はnull） */
358 private static function mul(array $c, \GMP $k, array $pt): ?array {
359 $bits = gmp_strval($k, 2);
360 $jp = [$pt[0], $pt[1], gmp_init(1)];
361 $r = null;
362 for ($i = 0; $i < strlen($bits); $i++) {
363 $r = self::dbl($c, $r);
364 if ($bits[$i] === '1') $r = self::add($c, $r, $jp);
365 }
366 return self::affine($c, $r);
367 }
368
369 /** u1 * P + u2 * Q（シャミアのトリック） */
370 private static function mul2(array $c, \GMP $u1, array $p1, \GMP $u2, array $p2): ?array {
371 $a = [$p1[0], $p1[1], gmp_init(1)];
372 $b = [$p2[0], $p2[1], gmp_init(1)];
373 $ab = self::add($c, $a, $b);
374 $s1 = gmp_strval($u1, 2);
375 $s2 = gmp_strval($u2, 2);
376 $len = max(strlen($s1), strlen($s2));
377 $s1 = str_pad($s1, $len, '0', STR_PAD_LEFT);
378 $s2 = str_pad($s2, $len, '0', STR_PAD_LEFT);
379 $r = null;
380 for ($i = 0; $i < $len; $i++) {
381 $r = self::dbl($c, $r);
382 $bit = ($s1[$i] === '1' ? 1 : 0) | ($s2[$i] === '1' ? 2 : 0);
383 if ($bit === 1) $r = self::add($c, $r, $a);
384 else if ($bit === 2) $r = self::add($c, $r, $b);
385 else if ($bit === 3) $r = self::add($c, $r, $ab);
386 }
387 return self::affine($c, $r);
388 }
389
390 private static function dbl(array $c, ?array $P): ?array {
391 if ($P === null) return null;
392 [$x, $y, $z] = $P;
393 if (gmp_sign($y) === 0) return null;
394 $p = $c['p'];
395 // a = -3：M = 3(X - Z²)(X + Z²)
396 $zz = gmp_mod(gmp_mul($z, $z), $p);
397 $m = gmp_mod(gmp_mul(3, gmp_mul(gmp_sub($x, $zz), gmp_add($x, $zz))), $p);
398 $yy = gmp_mod(gmp_mul($y, $y), $p);
399 $s = gmp_mod(gmp_mul(4, gmp_mul($x, $yy)), $p);
400 $x3 = gmp_mod(gmp_sub(gmp_mul($m, $m), gmp_mul(2, $s)), $p);
401 $y3 = gmp_mod(gmp_sub(gmp_mul($m, gmp_sub($s, $x3)), gmp_mul(8, gmp_mul($yy, $yy))), $p);
402 $z3 = gmp_mod(gmp_mul(2, gmp_mul($y, $z)), $p);
403 return [$x3, $y3, $z3];
404 }
405
406 private static function add(array $c, ?array $P, ?array $Q): ?array {
407 if ($P === null) return $Q;
408 if ($Q === null) return $P;
409 $p = $c['p'];
410 [$x1, $y1, $z1] = $P;
411 [$x2, $y2, $z2] = $Q;
412 $z1z1 = gmp_mod(gmp_mul($z1, $z1), $p);
413 $z2z2 = gmp_mod(gmp_mul($z2, $z2), $p);
414 $u1 = gmp_mod(gmp_mul($x1, $z2z2), $p);
415 $u2 = gmp_mod(gmp_mul($x2, $z1z1), $p);
416 $s1 = gmp_mod(gmp_mul($y1, gmp_mul($z2, $z2z2)), $p);
417 $s2 = gmp_mod(gmp_mul($y2, gmp_mul($z1, $z1z1)), $p);
418 $h = gmp_mod(gmp_sub($u2, $u1), $p);
419 $r = gmp_mod(gmp_sub($s2, $s1), $p);
420 if (gmp_sign($h) === 0) {
421 return gmp_sign($r) === 0 ? self::dbl($c, $P) : null;
422 }
423 $hh = gmp_mod(gmp_mul($h, $h), $p);
424 $hhh = gmp_mod(gmp_mul($h, $hh), $p);
425 $v = gmp_mod(gmp_mul($u1, $hh), $p);
426 $x3 = gmp_mod(gmp_sub(gmp_sub(gmp_mul($r, $r), $hhh), gmp_mul(2, $v)), $p);
427 $y3 = gmp_mod(gmp_sub(gmp_mul($r, gmp_sub($v, $x3)), gmp_mul($s1, $hhh)), $p);
428 $z3 = gmp_mod(gmp_mul($h, gmp_mul($z1, $z2)), $p);
429 return [$x3, $y3, $z3];
430 }
431
432 private static function affine(array $c, ?array $P): ?array {
433 if ($P === null || gmp_sign($P[2]) === 0) return null;
434 $p = $c['p'];
435 $zi = gmp_invert($P[2], $p);
436 $zi2 = gmp_mod(gmp_mul($zi, $zi), $p);
437 return [gmp_mod(gmp_mul($P[0], $zi2), $p), gmp_mod(gmp_mul($P[1], gmp_mul($zi2, $zi)), $p)];
438 }
439
440 private static function pad(\GMP $n, int $len): string {
441 return str_pad(gmp_export($n), $len, "\0", STR_PAD_LEFT);
442 }
443}