<?php
/*************************************************************
# 076 License

Copyright (c) テクニカル諏訪子

Permission is hereby granted to any person obtaining a copy of the software
Little Beast (the "Software") to use, modify, merge, copy, publish, distribute,
sublicense, and/or sell copies of the Software, subject to the following conditions:

    1. **Origin Attribution**:
       - You must not misrepresent the origin of the Software; you must not claim
         you created the original Software.
       - If the Software is used in a product, you must either:
         a. Provide clear attribution in the product's documentation, user interface,
            or other visible areas, **OR**
         b. Pay the original developers a fee they specify in writing.
    2. **Usage Restriction**:
       - The Software, or any derivative works, dependencies, or libraries
         incorporating it, must not be used for censorship or to suppress freedom of
         speech, expression, or creativity. Prohibited uses include, but are not
         limited to:
         - Censorship of so-called "hate speech", visuals, non-mainstream opinions,
           ideas, or objective reality.
         - Tools or systems designed to restrict access to information or
           artistic works.
    3. **Notice Preservation**:
       - This license and the above copyright notice must remain intact in all copies
         of the source code.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
namespace Std\Lib\Crypto;

/**
 * 楕円曲線（NISTのP-256・P-384・P-521）：ECDH、ECDSA（RFC 6979の決定的な署名）、PEM
 *
 * 例：
 *   $key = Ec::generate('P-256');
 *   $shared = $key->ecdh($peerPoint);          // 相手の公開鍵（04||x||y）
 *   $sig = $key->sign($data, 'sha256');        // DER
 *   $ok = Ec::fromPem($pub)->verify($data, $sig, 'sha256');
 */
class Ec {
  public const OID = '1.2.840.10045.2.1';

  /** 曲線：p、a（=-3）、b、n、Gx、Gy、OID、バイト数 */
  private const CURVES = [
    'P-256' => [
      'p' => 'ffffffff00000001000000000000000000000000ffffffffffffffffffffffff',
      'b' => '5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b',
      'n' => 'ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551',
      'x' => '6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296',
      'y' => '4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5',
      'oid' => '1.2.840.10045.3.1.7',
      'len' => 32,
    ],
    'P-384' => [
      'p' => 'fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff',
      'b' => 'b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef',
      'n' => 'ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973',
      'x' => 'aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7',
      'y' => '3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f',
      'oid' => '1.3.132.0.34',
      'len' => 48,
    ],
    'P-521' => [
      'p' => '01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff',
      'b' => '0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00',
      'n' => '01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409',
      'x' => '00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66',
      'y' => '011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650',
      'oid' => '1.3.132.0.35',
      'len' => 66,
    ],
  ];

  private static array $cache = [];

  public readonly string $curve;
  /** 公開鍵の点 [x, y] */
  public readonly array $q;
  private ?\GMP $d = null;
  private array $c;

  private function __construct(string $curve, array $q, ?\GMP $d = null) {
    $this->curve = $curve;
    $this->c = self::params($curve);
    $this->q = $q;
    $this->d = $d;
  }

  /** 曲線のパラメータ（GMP） */
  private static function params(string $curve): array {
    if (isset(self::$cache[$curve])) return self::$cache[$curve];
    $c = self::CURVES[$curve] ?? throw new \InvalidArgumentException("EC：未対応の曲線：{$curve}");
    $p = gmp_init($c['p'], 16);
    return self::$cache[$curve] = [
      'p' => $p,
      'a' => gmp_sub($p, 3),
      'b' => gmp_init($c['b'], 16),
      'n' => gmp_init($c['n'], 16),
      'g' => [gmp_init($c['x'], 16), gmp_init($c['y'], 16)],
      'oid' => $c['oid'],
      'len' => $c['len'],
    ];
  }

  /** 対応している曲線 */
  public static function curves(): array {
    return array_keys(self::CURVES);
  }

  /**
   * 新しい鍵を作る
   *
   * @param string $curve  P-256、P-384、P-521
   * @return self
   */
  public static function generate(string $curve = 'P-256'): self {
    $c = self::params($curve);
    do {
      $d = gmp_import(random_bytes($c['len']));
    } while (gmp_sign($d) === 0 || gmp_cmp($d, $c['n']) >= 0);
    return new self($curve, self::mul($c, $d, $c['g']), $d);
  }

  /**
   * 公開鍵の点から作る
   *
   * @param string $curve  曲線
   * @param string $point  圧縮しない点（04||x||y）
   * @return self
   * @throws \InvalidArgumentException  曲線上の点ではない場合
   */
  public static function fromPublic(string $curve, string $point): self {
    $c = self::params($curve);
    $l = $c['len'];
    if (strlen($point) !== 1 + 2 * $l || $point[0] !== "\x04") throw new \InvalidArgumentException('EC：未対応の点の形式');
    $q = [gmp_import(substr($point, 1, $l)), gmp_import(substr($point, 1 + $l, $l))];
    if (!self::onCurve($c, $q)) throw new \InvalidArgumentException('EC：曲線上の点ではない');
    return new self($curve, $q);
  }

  /**
   * PEMから読む（PRIVATE KEY、EC PRIVATE KEY、PUBLIC KEY）
   *
   * @throws \InvalidArgumentException
   */
  public static function fromPem(string $pem): self {
    foreach (Asn1::unpem($pem) as $b) {
      if (in_array($b['label'], ['PRIVATE KEY', 'EC PRIVATE KEY', 'PUBLIC KEY'], true) && empty($b['encrypted'])) {
        return self::fromDer($b['der']);
      }
    }
    throw new \InvalidArgumentException('EC：鍵が見つからない');
  }

  /**
   * DERから読む（PKCS#8、SEC 1、SubjectPublicKeyInfo）
   *
   * @throws \InvalidArgumentException
   */
  public static function fromDer(string $der, ?string $curve = null): self {
    try {
      $c = Asn1::expect(Asn1::parse($der), Asn1::SEQUENCE, 2);

      // SubjectPublicKeyInfo
      if ($c[0]['tag'] === Asn1::SEQUENCE && $c[1]['tag'] === Asn1::BIT_STRING) {
        return self::fromPublic(self::curveOf($c[0]), Asn1::toBits($c[1]));
      }

      // PKCS#8
      if ($c[0]['tag'] === Asn1::INTEGER && $c[1]['tag'] === Asn1::SEQUENCE && ($c[2]['tag'] ?? 0) === Asn1::OCTET_STRING) {
        return self::fromDer($c[2]['value'], self::curveOf($c[1]));
      }

      // SEC 1：SEQUENCE { 1, OCTET STRING d, [0] OID, [1] BIT STRING }
      if ($c[0]['tag'] === Asn1::INTEGER && $c[1]['tag'] === Asn1::OCTET_STRING) {
        foreach (array_slice($c, 2) as $x) {
          if ($x['tag'] === 0xA0) $curve = self::curveName(Asn1::toOid(Asn1::children($x)[0]));
        }
        if ($curve === null) throw new \InvalidArgumentException('EC：曲線が分からない');
        $p = self::params($curve);
        $d = gmp_import($c[1]['value']);
        if (gmp_sign($d) === 0 || gmp_cmp($d, $p['n']) >= 0) throw new \InvalidArgumentException('EC：不正な秘密鍵');
        return new self($curve, self::mul($p, $d, $p['g']), $d);
      }
    } catch (\UnexpectedValueException $ex) {
      throw new \InvalidArgumentException('EC：壊れた鍵（'.$ex->getMessage().'）');
    }
    throw new \InvalidArgumentException('EC：未対応の鍵の形式');
  }

  /** AlgorithmIdentifier { ecPublicKey, 曲線のOID } から曲線名 */
  private static function curveOf(array $alg): string {
    $a = Asn1::children($alg);
    if (Asn1::toOid($a[0]) !== self::OID || !isset($a[1]) || $a[1]['tag'] !== Asn1::OID) {
      throw new \InvalidArgumentException('EC：ECの鍵ではない');
    }
    return self::curveName(Asn1::toOid($a[1]));
  }

  /** OIDから曲線名 */
  public static function curveName(string $oid): string {
    foreach (self::CURVES as $name => $c) if ($c['oid'] === $oid) return $name;
    throw new \InvalidArgumentException("EC：未対応の曲線：{$oid}");
  }

  public function isPrivate(): bool {
    return $this->d !== null;
  }

  /** 公開鍵の点（04||x||y） */
  public function publicPoint(): string {
    $l = $this->c['len'];
    return "\x04".self::pad($this->q[0], $l).self::pad($this->q[1], $l);
  }

  /** 公開鍵（SubjectPublicKeyInfoのDER） */
  public function publicDer(): string {
    return Asn1::seq(Asn1::seq(Asn1::oid(self::OID), Asn1::oid($this->c['oid'])), Asn1::bits($this->publicPoint()));
  }

  public function publicPem(): string {
    return Asn1::pem($this->publicDer(), 'PUBLIC KEY');
  }

  /** 秘密鍵（PKCS#8のPEM） */
  public function toPem(): string {
    if ($this->d === null) throw new \LogicException('EC：秘密鍵ではない');
    $sec1 = Asn1::seq(Asn1::int(1), Asn1::octets(self::pad($this->d, $this->c['len'])), Asn1::explicit(1, Asn1::bits($this->publicPoint())));
    return Asn1::pem(Asn1::seq(Asn1::int(0), Asn1::seq(Asn1::oid(self::OID), Asn1::oid($this->c['oid'])), Asn1::octets($sec1)), 'PRIVATE KEY');
  }

  /**
   * 共有の秘密を計算する（ECDH）
   *
   * @param string $peerPoint  相手の公開鍵（04||x||y）
   * @return string  共有の秘密のx座標
   * @throws \InvalidArgumentException  不正な点の場合
   */
  public function ecdh(string $peerPoint): string {
    if ($this->d === null) throw new \LogicException('EC：秘密鍵ではない');
    $peer = self::fromPublic($this->curve, $peerPoint);
    $s = self::mul($this->c, $this->d, $peer->q);
    if ($s === null) throw new \InvalidArgumentException('EC：共有の秘密が無限遠点');
    return self::pad($s[0], $this->c['len']);
  }

  /**
   * 署名する（ECDSA、RFC 6979）
   *
   * @param string $msg  メッセージ
   * @param string $hash  ハッシュ
   * @return string  DER（SEQUENCE { r, s }）
   */
  public function sign(string $msg, string $hash = 'sha256'): string {
    if ($this->d === null) throw new \LogicException('EC：秘密鍵ではない');
    [$r, $s] = $this->signRaw(hash($hash, $msg, true), $hash);
    return Asn1::seq(Asn1::int($r), Asn1::int($s));
  }

  /** 署名のrとs */
  private function signRaw(string $h1, string $hash): array {
    $n = $this->c['n'];
    $l = $this->c['len'];
    $z = $this->bits2int($h1);
    $x = self::pad($this->d, $l);
    $h = self::pad(gmp_mod($z, $n), $l);

    // RFC 6979 3.2
    $hl = strlen(hash($hash, '', true));
    $v = str_repeat("\x01", $hl);
    $k = str_repeat("\x00", $hl);
    $k = hash_hmac($hash, $v."\x00".$x.$h, $k, true);
    $v = hash_hmac($hash, $v, $k, true);
    $k = hash_hmac($hash, $v."\x01".$x.$h, $k, true);
    $v = hash_hmac($hash, $v, $k, true);

    while (true) {
      $t = '';
      while (strlen($t) < $l) {
        $v = hash_hmac($hash, $v, $k, true);
        $t .= $v;
      }
      $kk = $this->bits2int($t);
      if (gmp_sign($kk) > 0 && gmp_cmp($kk, $n) < 0) {
        $p = self::mul($this->c, $kk, $this->c['g']);
        $r = gmp_mod($p[0], $n);
        if (gmp_sign($r) > 0) {
          $s = gmp_mod(gmp_mul(gmp_invert($kk, $n), gmp_add($z, gmp_mul($r, $this->d))), $n);
          if (gmp_sign($s) > 0) return [$r, $s];
        }
      }
      $k = hash_hmac($hash, $v."\x00", $k, true);
      $v = hash_hmac($hash, $v, $k, true);
    }
  }

  /**
   * 署名を確認する（ECDSA）
   *
   * @param string $msg  メッセージ
   * @param string $sig  DER（SEQUENCE { r, s }）
   * @param string $hash  ハッシュ
   * @return bool
   */
  public function verify(string $msg, string $sig, string $hash = 'sha256'): bool {
    try {
      $rs = Asn1::expect(Asn1::parse($sig), Asn1::SEQUENCE, 2);
      if (count($rs) !== 2) return false;
      $r = Asn1::toInt($rs[0]);
      $s = Asn1::toInt($rs[1]);
    } catch (\UnexpectedValueException $e) {
      return false;
    }
    // DERの形が正しい事（BERの別の書き方を拒否する）
    if (Asn1::seq(Asn1::int($r), Asn1::int($s)) !== $sig) return false;

    $n = $this->c['n'];
    if (gmp_sign($r) <= 0 || gmp_sign($s) <= 0 || gmp_cmp($r, $n) >= 0 || gmp_cmp($s, $n) >= 0) return false;

    $z = $this->bits2int(hash($hash, $msg, true));
    $w = gmp_invert($s, $n);
    $u1 = gmp_mod(gmp_mul($z, $w), $n);
    $u2 = gmp_mod(gmp_mul($r, $w), $n);
    $p = self::mul2($this->c, $u1, $this->c['g'], $u2, $this->q);
    return $p !== null && gmp_cmp(gmp_mod($p[0], $n), $r) === 0;
  }

  /** ハッシュを整数にする（曲線のビット数に切り詰める） */
  private function bits2int(string $h): \GMP {
    $nbits = strlen(gmp_strval($this->c['n'], 2));
    $z = gmp_import($h);
    $hbits = 8 * strlen($h);
    return $hbits > $nbits ? gmp_div_q($z, gmp_pow(2, $hbits - $nbits)) : $z;
  }

  ///////////////
  // 点の計算（ヤコビアン座標、a = -3）

  private static function onCurve(array $c, array $q): bool {
    [$x, $y] = $q;
    $p = $c['p'];
    if (gmp_sign($x) < 0 || gmp_sign($y) < 0 || gmp_cmp($x, $p) >= 0 || gmp_cmp($y, $p) >= 0) return false;
    $l = gmp_mod(gmp_mul($y, $y), $p);
    $r = gmp_mod(gmp_add(gmp_add(gmp_mul(gmp_mul($x, $x), $x), gmp_mul($c['a'], $x)), $c['b']), $p);
    return gmp_cmp($l, $r) === 0;
  }

  /** k * P（アフィン座標で返す、無限遠点はnull） */
  private static function mul(array $c, \GMP $k, array $pt): ?array {
    $bits = gmp_strval($k, 2);
    $jp = [$pt[0], $pt[1], gmp_init(1)];
    $r = null;
    for ($i = 0; $i < strlen($bits); $i++) {
      $r = self::dbl($c, $r);
      if ($bits[$i] === '1') $r = self::add($c, $r, $jp);
    }
    return self::affine($c, $r);
  }

  /** u1 * P + u2 * Q（シャミアのトリック） */
  private static function mul2(array $c, \GMP $u1, array $p1, \GMP $u2, array $p2): ?array {
    $a = [$p1[0], $p1[1], gmp_init(1)];
    $b = [$p2[0], $p2[1], gmp_init(1)];
    $ab = self::add($c, $a, $b);
    $s1 = gmp_strval($u1, 2);
    $s2 = gmp_strval($u2, 2);
    $len = max(strlen($s1), strlen($s2));
    $s1 = str_pad($s1, $len, '0', STR_PAD_LEFT);
    $s2 = str_pad($s2, $len, '0', STR_PAD_LEFT);
    $r = null;
    for ($i = 0; $i < $len; $i++) {
      $r = self::dbl($c, $r);
      $bit = ($s1[$i] === '1' ? 1 : 0) | ($s2[$i] === '1' ? 2 : 0);
      if ($bit === 1) $r = self::add($c, $r, $a);
      else if ($bit === 2) $r = self::add($c, $r, $b);
      else if ($bit === 3) $r = self::add($c, $r, $ab);
    }
    return self::affine($c, $r);
  }

  private static function dbl(array $c, ?array $P): ?array {
    if ($P === null) return null;
    [$x, $y, $z] = $P;
    if (gmp_sign($y) === 0) return null;
    $p = $c['p'];
    // a = -3：M = 3(X - Z²)(X + Z²)
    $zz = gmp_mod(gmp_mul($z, $z), $p);
    $m = gmp_mod(gmp_mul(3, gmp_mul(gmp_sub($x, $zz), gmp_add($x, $zz))), $p);
    $yy = gmp_mod(gmp_mul($y, $y), $p);
    $s = gmp_mod(gmp_mul(4, gmp_mul($x, $yy)), $p);
    $x3 = gmp_mod(gmp_sub(gmp_mul($m, $m), gmp_mul(2, $s)), $p);
    $y3 = gmp_mod(gmp_sub(gmp_mul($m, gmp_sub($s, $x3)), gmp_mul(8, gmp_mul($yy, $yy))), $p);
    $z3 = gmp_mod(gmp_mul(2, gmp_mul($y, $z)), $p);
    return [$x3, $y3, $z3];
  }

  private static function add(array $c, ?array $P, ?array $Q): ?array {
    if ($P === null) return $Q;
    if ($Q === null) return $P;
    $p = $c['p'];
    [$x1, $y1, $z1] = $P;
    [$x2, $y2, $z2] = $Q;
    $z1z1 = gmp_mod(gmp_mul($z1, $z1), $p);
    $z2z2 = gmp_mod(gmp_mul($z2, $z2), $p);
    $u1 = gmp_mod(gmp_mul($x1, $z2z2), $p);
    $u2 = gmp_mod(gmp_mul($x2, $z1z1), $p);
    $s1 = gmp_mod(gmp_mul($y1, gmp_mul($z2, $z2z2)), $p);
    $s2 = gmp_mod(gmp_mul($y2, gmp_mul($z1, $z1z1)), $p);
    $h = gmp_mod(gmp_sub($u2, $u1), $p);
    $r = gmp_mod(gmp_sub($s2, $s1), $p);
    if (gmp_sign($h) === 0) {
      return gmp_sign($r) === 0 ? self::dbl($c, $P) : null;
    }
    $hh = gmp_mod(gmp_mul($h, $h), $p);
    $hhh = gmp_mod(gmp_mul($h, $hh), $p);
    $v = gmp_mod(gmp_mul($u1, $hh), $p);
    $x3 = gmp_mod(gmp_sub(gmp_sub(gmp_mul($r, $r), $hhh), gmp_mul(2, $v)), $p);
    $y3 = gmp_mod(gmp_sub(gmp_mul($r, gmp_sub($v, $x3)), gmp_mul($s1, $hhh)), $p);
    $z3 = gmp_mod(gmp_mul($h, gmp_mul($z1, $z2)), $p);
    return [$x3, $y3, $z3];
  }

  private static function affine(array $c, ?array $P): ?array {
    if ($P === null || gmp_sign($P[2]) === 0) return null;
    $p = $c['p'];
    $zi = gmp_invert($P[2], $p);
    $zi2 = gmp_mod(gmp_mul($zi, $zi), $p);
    return [gmp_mod(gmp_mul($P[0], $zi2), $p), gmp_mod(gmp_mul($P[1], gmp_mul($zi2, $zi)), $p)];
  }

  private static function pad(\GMP $n, int $len): string {
    return str_pad(gmp_export($n), $len, "\0", STR_PAD_LEFT);
  }
}