<?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;

/**
 * RSA（鍵の作成、PEM、PKCS#1 v1.5・PSSの署名、OAEPの暗号化）
 *
 * 例：
 *   $key = Rsa::generate(2048);
 *   file_put_contents('priv.pem', $key->toPem());
 *   $sig = Rsa::fromPem($priv)->sign($data);              // RSASSA-PKCS1-v1_5、SHA-256
 *   $ok = Rsa::fromPem($pub)->verify($data, $sig);
 *   $ct = Rsa::fromPem($pub)->encrypt($secret, 'sha1');    // RSAES-OAEP
 *
 * 秘密鍵の計算はCRTとブラインディングを使い、結果を公開鍵で確認する。
 */
class Rsa {
  public const OID = '1.2.840.113549.1.1.1';
  public const OID_PSS = '1.2.840.113549.1.1.10';

  // DigestInfoの先頭（RFC 8017 9.2）
  private const DIGEST_INFO = [
    'sha1' => "\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14",
    'sha224' => "\x30\x2d\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x04\x05\x00\x04\x1c",
    'sha256' => "\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20",
    'sha384' => "\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30",
    'sha512' => "\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40",
  ];

  public readonly \GMP $n;
  public readonly \GMP $e;
  /** 法の大きさ（ビット、バイト） */
  public readonly int $bits;
  public readonly int $bytes;

  private ?\GMP $d = null;
  private ?\GMP $p = null;
  private ?\GMP $q = null;
  private ?\GMP $dp = null;
  private ?\GMP $dq = null;
  private ?\GMP $qi = null;

  private function __construct(\GMP $n, \GMP $e) {
    if (gmp_cmp($n, 0) <= 0 || gmp_cmp($e, 1) <= 0) throw new \InvalidArgumentException('RSA：不正な鍵');
    $this->n = $n;
    $this->e = $e;
    $this->bits = strlen(gmp_strval($n, 2));
    $this->bytes = intdiv($this->bits + 7, 8);
  }

  /**
   * 新しい鍵を作る
   *
   * @param int $bits  法の大きさ（1024以上、普通は2048か4096）
   * @param int $e  公開指数
   * @return self
   */
  public static function generate(int $bits = 2048, int $e = 65537): self {
    if ($bits < 1024 || $bits % 2) throw new \InvalidArgumentException('RSA：鍵の大きさは1024以上の偶数');
    $E = gmp_init($e);

    while (true) {
      $p = self::prime(intdiv($bits, 2), $E);
      $q = self::prime(intdiv($bits, 2), $E);
      // pとqが近過ぎない事（FIPS 186-4 B.3.1）
      if (strlen(gmp_strval(gmp_abs(gmp_sub($p, $q)), 2)) <= intdiv($bits, 2) - 100) continue;
      $n = gmp_mul($p, $q);
      if (strlen(gmp_strval($n, 2)) !== $bits) continue;
      return self::fromParts($n, $E, null, $p, $q);
    }
  }

  /** 最上位の2ビットを立てた、p-1がeと互いに素な素数 */
  private static function prime(int $bits, \GMP $e): \GMP {
    while (true) {
      $b = random_bytes(intdiv($bits + 7, 8));
      $b[0] = chr(ord($b[0]) | 0xC0);
      $c = gmp_nextprime(gmp_import($b));
      if (strlen(gmp_strval($c, 2)) !== $bits) continue;
      if (gmp_cmp(gmp_gcd(gmp_sub($c, 1), $e), 1) !== 0) continue;
      if (gmp_prob_prime($c, 40) === 0) continue;
      return $c;
    }
  }

  /** n、e、（d、p、q）から作る */
  private static function fromParts(\GMP $n, \GMP $e, ?\GMP $d = null, ?\GMP $p = null, ?\GMP $q = null): self {
    $key = new self($n, $e);
    if ($p !== null && $q !== null) {
      if (gmp_cmp(gmp_mul($p, $q), $n) !== 0) throw new \InvalidArgumentException('RSA：p・qとnが合わない');
      $phi = gmp_lcm(gmp_sub($p, 1), gmp_sub($q, 1));
      $d ??= gmp_invert($e, $phi) ?: null;
      if ($d === null) throw new \InvalidArgumentException('RSA：dを計算出来ない');
      $key->p = $p;
      $key->q = $q;
      $key->dp = gmp_mod($d, gmp_sub($p, 1));
      $key->dq = gmp_mod($d, gmp_sub($q, 1));
      $key->qi = gmp_invert($q, $p) ?: null;
    }
    $key->d = $d;
    return $key;
  }

  ///////////////
  // 読み込み・書き出し

  /**
   * PEMから読む（PRIVATE KEY、RSA PRIVATE KEY、PUBLIC KEY、RSA PUBLIC KEY）
   *
   * @param string $pem
   * @return self
   * @throws \InvalidArgumentException  RSAの鍵ではない、又は暗号化されている場合
   */
  public static function fromPem(string $pem): self {
    foreach (Asn1::unpem($pem) as $b) {
      if (!empty($b['encrypted']) || $b['label'] === 'ENCRYPTED PRIVATE KEY') {
        throw new \InvalidArgumentException('RSA：暗号化された鍵は未対応');
      }
      switch ($b['label']) {
        case 'PRIVATE KEY':
        case 'PUBLIC KEY':
        case 'RSA PRIVATE KEY':
        case 'RSA PUBLIC KEY':
          return self::fromDer($b['der']);
      }
    }
    throw new \InvalidArgumentException('RSA：鍵が見つからない');
  }

  /**
   * DERから読む（PKCS#8、SubjectPublicKeyInfo、PKCS#1の秘密鍵・公開鍵）
   *
   * @param string $der
   * @return self
   * @throws \InvalidArgumentException
   */
  public static function fromDer(string $der): self {
    try {
      $c = Asn1::expect(Asn1::parse($der), Asn1::SEQUENCE, 2);

      // SubjectPublicKeyInfo：SEQUENCE { AlgorithmIdentifier, BIT STRING }
      if ($c[0]['tag'] === Asn1::SEQUENCE && $c[1]['tag'] === Asn1::BIT_STRING) {
        self::checkAlgorithm($c[0]);
        return self::fromDer(Asn1::toBits($c[1]));
      }

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

      // PKCS#1の公開鍵：SEQUENCE { n, e }
      if (count($c) === 2) return new self(Asn1::toInt($c[0]), Asn1::toInt($c[1]));

      // PKCS#1の秘密鍵：SEQUENCE { version, n, e, d, p, q, dp, dq, qi }
      if (count($c) >= 9 && gmp_sign(Asn1::toInt($c[0])) === 0) {
        [$n, $e, $d, $p, $q] = array_map([Asn1::class, 'toInt'], array_slice($c, 1, 5));
        return self::fromParts($n, $e, $d, $p, $q);
      }
    } catch (\UnexpectedValueException $ex) {
      throw new \InvalidArgumentException('RSA：壊れた鍵（'.$ex->getMessage().'）');
    }

    throw new \InvalidArgumentException('RSA：未対応の鍵の形式');
  }

  /**
   * SubjectPublicKeyInfoのアルゴリズムを確認する
   *
   * @throws \InvalidArgumentException  RSA（又はRSA-PSS）ではない場合
   */
  private static function checkAlgorithm(array $alg): void {
    $oid = Asn1::toOid(Asn1::children($alg)[0]);
    if ($oid !== self::OID && $oid !== self::OID_PSS) throw new \InvalidArgumentException("RSA：RSAの鍵ではない（{$oid}）");
  }

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

  /** 公開鍵（SubjectPublicKeyInfoのDER） */
  public function publicDer(): string {
    return Asn1::seq(
      Asn1::seq(Asn1::oid(self::OID), Asn1::null()),
      Asn1::bits(Asn1::seq(Asn1::int($this->n), Asn1::int($this->e))),
    );
  }

  /** 公開鍵（「BEGIN PUBLIC KEY」のPEM） */
  public function publicPem(): string {
    return Asn1::pem($this->publicDer(), 'PUBLIC KEY');
  }

  /**
   * 秘密鍵（PKCS#8、「BEGIN PRIVATE KEY」のPEM）
   *
   * @throws \LogicException  公開鍵の場合
   */
  public function toPem(): string {
    if ($this->p === null) throw new \LogicException('RSA：秘密鍵ではない');
    $pkcs1 = Asn1::seq(Asn1::int(0), Asn1::int($this->n), Asn1::int($this->e), Asn1::int($this->d),
      Asn1::int($this->p), Asn1::int($this->q), Asn1::int($this->dp), Asn1::int($this->dq), Asn1::int($this->qi));
    return Asn1::pem(Asn1::seq(Asn1::int(0), Asn1::seq(Asn1::oid(self::OID), Asn1::null()), Asn1::octets($pkcs1)), 'PRIVATE KEY');
  }

  ///////////////
  // 署名

  /**
   * 署名する（RSASSA-PKCS1-v1_5）
   *
   * @param string $msg  メッセージ
   * @param string $hash  sha1、sha256、sha384、sha512等
   * @return string  署名（$this->bytesバイト）
   */
  public function sign(string $msg, string $hash = 'sha256'): string {
    return $this->private($this->pkcs1Encode($msg, $hash));
  }

  /**
   * 署名を確認する（RSASSA-PKCS1-v1_5）
   *
   * @param string $msg  メッセージ
   * @param string $sig  署名
   * @param string $hash  ハッシュ
   * @return bool
   */
  public function verify(string $msg, string $sig, string $hash = 'sha256'): bool {
    $em = $this->public($sig);
    return $em !== null && hash_equals($this->pkcs1Encode($msg, $hash), $em);
  }

  private function pkcs1Encode(string $msg, string $hash): string {
    if (!isset(self::DIGEST_INFO[$hash])) throw new \InvalidArgumentException("RSA：未対応のハッシュ：{$hash}");
    $t = self::DIGEST_INFO[$hash].hash($hash, $msg, true);
    if ($this->bytes < strlen($t) + 11) throw new \InvalidArgumentException('RSA：鍵が小さ過ぎる');
    return "\x00\x01".str_repeat("\xFF", $this->bytes - strlen($t) - 3)."\x00".$t;
  }

  /**
   * 署名する（RSASSA-PSS、MGF1は同じハッシュ）
   *
   * @param string $msg  メッセージ
   * @param string $hash  ハッシュ
   * @param int|null $saltLen  ソルトの長さ（null＝ハッシュの長さ）
   * @return string
   */
  public function signPss(string $msg, string $hash = 'sha256', ?int $saltLen = null): string {
    $mHash = hash($hash, $msg, true);
    $hLen = strlen($mHash);
    $saltLen ??= $hLen;
    $emBits = $this->bits - 1;
    $emLen = intdiv($emBits + 7, 8);
    if ($emLen < $hLen + $saltLen + 2) throw new \InvalidArgumentException('RSA：鍵が小さ過ぎる');

    $salt = $saltLen > 0 ? random_bytes($saltLen) : '';
    $h = hash($hash, str_repeat("\0", 8).$mHash.$salt, true);
    $db = str_repeat("\0", $emLen - $saltLen - $hLen - 2)."\x01".$salt;
    $masked = $db ^ self::mgf1($h, $emLen - $hLen - 1, $hash);
    $masked[0] = chr(ord($masked[0]) & (0xFF >> (8 * $emLen - $emBits)));
    return $this->private(str_pad($masked.$h."\xBC", $this->bytes, "\0", STR_PAD_LEFT));
  }

  /**
   * 署名を確認する（RSASSA-PSS）
   *
   * @param string $msg  メッセージ
   * @param string $sig  署名
   * @param string $hash  ハッシュ（MGF1も同じ）
   * @param int|null $saltLen  ソルトの長さ（null＝ハッシュの長さ、-1＝何でも）
   * @return bool
   */
  public function verifyPss(string $msg, string $sig, string $hash = 'sha256', ?int $saltLen = null): bool {
    $em = $this->public($sig);
    if ($em === null) return false;

    $mHash = hash($hash, $msg, true);
    $hLen = strlen($mHash);
    $emBits = $this->bits - 1;
    $emLen = intdiv($emBits + 7, 8);
    $em = substr($em, -$emLen);
    if (strlen($em) !== $emLen || $emLen < $hLen + 2 || substr($em, -1) !== "\xBC") return false;
    if ($this->bytes > $emLen && ltrim(substr($this->public($sig), 0, $this->bytes - $emLen), "\0") !== '') return false;

    $masked = substr($em, 0, $emLen - $hLen - 1);
    $h = substr($em, $emLen - $hLen - 1, $hLen);
    $topMask = 0xFF >> (8 * $emLen - $emBits);
    if (ord($masked[0]) & ~$topMask & 0xFF) return false;

    $db = $masked ^ self::mgf1($h, strlen($masked), $hash);
    $db[0] = chr(ord($db[0]) & $topMask);
    $one = strpos($db, "\x01");
    if ($one === false || ltrim(substr($db, 0, $one), "\0") !== '') return false;
    $salt = substr($db, $one + 1);
    if ($saltLen !== null && $saltLen >= 0 && strlen($salt) !== $saltLen) return false;
    if ($saltLen === null && strlen($salt) !== $hLen) return false;

    return hash_equals($h, hash($hash, str_repeat("\0", 8).$mHash.$salt, true));
  }

  ///////////////
  // 暗号化

  /**
   * 暗号化する（RSAES-OAEP、MGF1は同じハッシュ）
   *
   * @param string $msg  平文
   * @param string $hash  ハッシュ（OpenSSLのOPENSSL_PKCS1_OAEP_PADDINGはsha1）
   * @param string $label  ラベル
   * @return string
   */
  public function encrypt(string $msg, string $hash = 'sha1', string $label = ''): string {
    $lHash = hash($hash, $label, true);
    $hLen = strlen($lHash);
    $k = $this->bytes;
    if (strlen($msg) > $k - 2 * $hLen - 2) throw new \InvalidArgumentException('RSA：メッセージが長過ぎる');

    $db = $lHash.str_repeat("\0", $k - strlen($msg) - 2 * $hLen - 2)."\x01".$msg;
    $seed = random_bytes($hLen);
    $maskedDb = $db ^ self::mgf1($seed, $k - $hLen - 1, $hash);
    $maskedSeed = $seed ^ self::mgf1($maskedDb, $hLen, $hash);
    return $this->public("\x00".$maskedSeed.$maskedDb, false);
  }

  /**
   * 復号する（RSAES-OAEP）
   *
   * @param string $ct  暗号文
   * @param string $hash  ハッシュ
   * @param string $label  ラベル
   * @return string|null  平文、失敗したらnull
   */
  public function decrypt(string $ct, string $hash = 'sha1', string $label = ''): ?string {
    if (strlen($ct) !== $this->bytes) return null;
    $em = $this->private($ct);
    $lHash = hash($hash, $label, true);
    $hLen = strlen($lHash);
    if ($this->bytes < 2 * $hLen + 2) return null;

    $maskedSeed = substr($em, 1, $hLen);
    $maskedDb = substr($em, 1 + $hLen);
    $seed = $maskedSeed ^ self::mgf1($maskedDb, $hLen, $hash);
    $db = $maskedDb ^ self::mgf1($seed, strlen($maskedDb), $hash);

    $one = strpos($db, "\x01", $hLen);
    $bad = ($em[0] !== "\0") | !hash_equals($lHash, substr($db, 0, $hLen)) | ($one === false);
    if ($bad || ltrim(substr($db, $hLen, $one - $hLen), "\0") !== '') return null;
    return substr($db, $one + 1);
  }

  ///////////////
  // 計算

  /** MGF1（RFC 8017 B.2.1） */
  private static function mgf1(string $seed, int $len, string $hash): string {
    $out = '';
    for ($i = 0; strlen($out) < $len; $i++) $out .= hash($hash, $seed.pack('N', $i), true);
    return substr($out, 0, $len);
  }

  /** 公開鍵の計算（m^e mod n） */
  private function public(string $data, bool $check = true): ?string {
    if (strlen($data) !== $this->bytes) {
      if ($check) return null;
      throw new \InvalidArgumentException('RSA：長さが違う');
    }
    $m = gmp_import($data);
    if (gmp_cmp($m, $this->n) >= 0) return null;
    return $this->i2osp(gmp_powm($m, $this->e, $this->n));
  }

  /** 秘密鍵の計算（CRT、ブラインディング、結果の確認） */
  private function private(string $data): string {
    if ($this->d === null) throw new \LogicException('RSA：秘密鍵ではない');
    $c = gmp_import($data);
    if (gmp_cmp($c, $this->n) >= 0) throw new \InvalidArgumentException('RSA：値が大き過ぎる');

    // ブラインディング：c' = c * r^e
    do {
      $r = gmp_mod(gmp_import(random_bytes($this->bytes + 8)), $this->n);
      $ri = gmp_invert($r, $this->n);
    } while ($ri === false || gmp_sign($r) === 0);
    $cb = gmp_mod(gmp_mul($c, gmp_powm($r, $this->e, $this->n)), $this->n);

    if ($this->p !== null && $this->qi !== null) {
      $m1 = gmp_powm($cb, $this->dp, $this->p);
      $m2 = gmp_powm($cb, $this->dq, $this->q);
      $h = gmp_mod(gmp_mul($this->qi, gmp_sub($m1, $m2)), $this->p);
      $mb = gmp_add($m2, gmp_mul($h, $this->q));
    } else {
      $mb = gmp_powm($cb, $this->d, $this->n);
    }
    $m = gmp_mod(gmp_mul($mb, $ri), $this->n);

    // 計算の誤り（故障攻撃）を防ぐ
    if (gmp_cmp(gmp_powm($m, $this->e, $this->n), $c) !== 0) throw new \RuntimeException('RSA：計算に失敗');
    return $this->i2osp($m);
  }

  private function i2osp(\GMP $x): string {
    return str_pad(gmp_export($x), $this->bytes, "\0", STR_PAD_LEFT);
  }
}