suwako / LittleBeast

master
ブランチ master
LittleBeast / src / Std / Lib / Crypto / Rsa.php
17 KB、439行 生 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 * RSA（鍵の作成、PEM、PKCS#1 v1.5・PSSの署名、OAEPの暗号化）
42 *
43 * 例：
44 * $key = Rsa::generate(2048);
45 * file_put_contents('priv.pem', $key->toPem());
46 * $sig = Rsa::fromPem($priv)->sign($data); // RSASSA-PKCS1-v1_5、SHA-256
47 * $ok = Rsa::fromPem($pub)->verify($data, $sig);
48 * $ct = Rsa::fromPem($pub)->encrypt($secret, 'sha1'); // RSAES-OAEP
49 *
50 * 秘密鍵の計算はCRTとブラインディングを使い、結果を公開鍵で確認する。
51 */
52class Rsa {
53 public const OID = '1.2.840.113549.1.1.1';
54 public const OID_PSS = '1.2.840.113549.1.1.10';
55
56 // DigestInfoの先頭（RFC 8017 9.2）
57 private const DIGEST_INFO = [
58 'sha1' => "\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14",
59 'sha224' => "\x30\x2d\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x04\x05\x00\x04\x1c",
60 'sha256' => "\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20",
61 'sha384' => "\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30",
62 'sha512' => "\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40",
63 ];
64
65 public readonly \GMP $n;
66 public readonly \GMP $e;
67 /** 法の大きさ（ビット、バイト） */
68 public readonly int $bits;
69 public readonly int $bytes;
70
71 private ?\GMP $d = null;
72 private ?\GMP $p = null;
73 private ?\GMP $q = null;
74 private ?\GMP $dp = null;
75 private ?\GMP $dq = null;
76 private ?\GMP $qi = null;
77
78 private function __construct(\GMP $n, \GMP $e) {
79 if (gmp_cmp($n, 0) <= 0 || gmp_cmp($e, 1) <= 0) throw new \InvalidArgumentException('RSA：不正な鍵');
80 $this->n = $n;
81 $this->e = $e;
82 $this->bits = strlen(gmp_strval($n, 2));
83 $this->bytes = intdiv($this->bits + 7, 8);
84 }
85
86 /**
87 * 新しい鍵を作る
88 *
89 * @param int $bits 法の大きさ（1024以上、普通は2048か4096）
90 * @param int $e 公開指数
91 * @return self
92 */
93 public static function generate(int $bits = 2048, int $e = 65537): self {
94 if ($bits < 1024 || $bits % 2) throw new \InvalidArgumentException('RSA：鍵の大きさは1024以上の偶数');
95 $E = gmp_init($e);
96
97 while (true) {
98 $p = self::prime(intdiv($bits, 2), $E);
99 $q = self::prime(intdiv($bits, 2), $E);
100 // pとqが近過ぎない事（FIPS 186-4 B.3.1）
101 if (strlen(gmp_strval(gmp_abs(gmp_sub($p, $q)), 2)) <= intdiv($bits, 2) - 100) continue;
102 $n = gmp_mul($p, $q);
103 if (strlen(gmp_strval($n, 2)) !== $bits) continue;
104 return self::fromParts($n, $E, null, $p, $q);
105 }
106 }
107
108 /** 最上位の2ビットを立てた、p-1がeと互いに素な素数 */
109 private static function prime(int $bits, \GMP $e): \GMP {
110 while (true) {
111 $b = random_bytes(intdiv($bits + 7, 8));
112 $b[0] = chr(ord($b[0]) | 0xC0);
113 $c = gmp_nextprime(gmp_import($b));
114 if (strlen(gmp_strval($c, 2)) !== $bits) continue;
115 if (gmp_cmp(gmp_gcd(gmp_sub($c, 1), $e), 1) !== 0) continue;
116 if (gmp_prob_prime($c, 40) === 0) continue;
117 return $c;
118 }
119 }
120
121 /** n、e、（d、p、q）から作る */
122 private static function fromParts(\GMP $n, \GMP $e, ?\GMP $d = null, ?\GMP $p = null, ?\GMP $q = null): self {
123 $key = new self($n, $e);
124 if ($p !== null && $q !== null) {
125 if (gmp_cmp(gmp_mul($p, $q), $n) !== 0) throw new \InvalidArgumentException('RSA：p・qとnが合わない');
126 $phi = gmp_lcm(gmp_sub($p, 1), gmp_sub($q, 1));
127 $d ??= gmp_invert($e, $phi) ?: null;
128 if ($d === null) throw new \InvalidArgumentException('RSA：dを計算出来ない');
129 $key->p = $p;
130 $key->q = $q;
131 $key->dp = gmp_mod($d, gmp_sub($p, 1));
132 $key->dq = gmp_mod($d, gmp_sub($q, 1));
133 $key->qi = gmp_invert($q, $p) ?: null;
134 }
135 $key->d = $d;
136 return $key;
137 }
138
139 ///////////////
140 // 読み込み・書き出し
141
142 /**
143 * PEMから読む（PRIVATE KEY、RSA PRIVATE KEY、PUBLIC KEY、RSA PUBLIC KEY）
144 *
145 * @param string $pem
146 * @return self
147 * @throws \InvalidArgumentException RSAの鍵ではない、又は暗号化されている場合
148 */
149 public static function fromPem(string $pem): self {
150 foreach (Asn1::unpem($pem) as $b) {
151 if (!empty($b['encrypted']) || $b['label'] === 'ENCRYPTED PRIVATE KEY') {
152 throw new \InvalidArgumentException('RSA：暗号化された鍵は未対応');
153 }
154 switch ($b['label']) {
155 case 'PRIVATE KEY':
156 case 'PUBLIC KEY':
157 case 'RSA PRIVATE KEY':
158 case 'RSA PUBLIC KEY':
159 return self::fromDer($b['der']);
160 }
161 }
162 throw new \InvalidArgumentException('RSA：鍵が見つからない');
163 }
164
165 /**
166 * DERから読む（PKCS#8、SubjectPublicKeyInfo、PKCS#1の秘密鍵・公開鍵）
167 *
168 * @param string $der
169 * @return self
170 * @throws \InvalidArgumentException
171 */
172 public static function fromDer(string $der): self {
173 try {
174 $c = Asn1::expect(Asn1::parse($der), Asn1::SEQUENCE, 2);
175
176 // SubjectPublicKeyInfo：SEQUENCE { AlgorithmIdentifier, BIT STRING }
177 if ($c[0]['tag'] === Asn1::SEQUENCE && $c[1]['tag'] === Asn1::BIT_STRING) {
178 self::checkAlgorithm($c[0]);
179 return self::fromDer(Asn1::toBits($c[1]));
180 }
181
182 // PKCS#8：SEQUENCE { version, AlgorithmIdentifier, OCTET STRING, … }
183 if ($c[0]['tag'] === Asn1::INTEGER && $c[1]['tag'] === Asn1::SEQUENCE && ($c[2]['tag'] ?? 0) === Asn1::OCTET_STRING) {
184 self::checkAlgorithm($c[1]);
185 return self::fromDer($c[2]['value']);
186 }
187
188 // PKCS#1の公開鍵：SEQUENCE { n, e }
189 if (count($c) === 2) return new self(Asn1::toInt($c[0]), Asn1::toInt($c[1]));
190
191 // PKCS#1の秘密鍵：SEQUENCE { version, n, e, d, p, q, dp, dq, qi }
192 if (count($c) >= 9 && gmp_sign(Asn1::toInt($c[0])) === 0) {
193 [$n, $e, $d, $p, $q] = array_map([Asn1::class, 'toInt'], array_slice($c, 1, 5));
194 return self::fromParts($n, $e, $d, $p, $q);
195 }
196 } catch (\UnexpectedValueException $ex) {
197 throw new \InvalidArgumentException('RSA：壊れた鍵（'.$ex->getMessage().'）');
198 }
199
200 throw new \InvalidArgumentException('RSA：未対応の鍵の形式');
201 }
202
203 /**
204 * SubjectPublicKeyInfoのアルゴリズムを確認する
205 *
206 * @throws \InvalidArgumentException RSA（又はRSA-PSS）ではない場合
207 */
208 private static function checkAlgorithm(array $alg): void {
209 $oid = Asn1::toOid(Asn1::children($alg)[0]);
210 if ($oid !== self::OID && $oid !== self::OID_PSS) throw new \InvalidArgumentException("RSA：RSAの鍵ではない（{$oid}）");
211 }
212
213 public function isPrivate(): bool {
214 return $this->d !== null;
215 }
216
217 /** 公開鍵（SubjectPublicKeyInfoのDER） */
218 public function publicDer(): string {
219 return Asn1::seq(
220 Asn1::seq(Asn1::oid(self::OID), Asn1::null()),
221 Asn1::bits(Asn1::seq(Asn1::int($this->n), Asn1::int($this->e))),
222 );
223 }
224
225 /** 公開鍵（「BEGIN PUBLIC KEY」のPEM） */
226 public function publicPem(): string {
227 return Asn1::pem($this->publicDer(), 'PUBLIC KEY');
228 }
229
230 /**
231 * 秘密鍵（PKCS#8、「BEGIN PRIVATE KEY」のPEM）
232 *
233 * @throws \LogicException 公開鍵の場合
234 */
235 public function toPem(): string {
236 if ($this->p === null) throw new \LogicException('RSA：秘密鍵ではない');
237 $pkcs1 = Asn1::seq(Asn1::int(0), Asn1::int($this->n), Asn1::int($this->e), Asn1::int($this->d),
238 Asn1::int($this->p), Asn1::int($this->q), Asn1::int($this->dp), Asn1::int($this->dq), Asn1::int($this->qi));
239 return Asn1::pem(Asn1::seq(Asn1::int(0), Asn1::seq(Asn1::oid(self::OID), Asn1::null()), Asn1::octets($pkcs1)), 'PRIVATE KEY');
240 }
241
242 ///////////////
243 // 署名
244
245 /**
246 * 署名する（RSASSA-PKCS1-v1_5）
247 *
248 * @param string $msg メッセージ
249 * @param string $hash sha1、sha256、sha384、sha512等
250 * @return string 署名（$this->bytesバイト）
251 */
252 public function sign(string $msg, string $hash = 'sha256'): string {
253 return $this->private($this->pkcs1Encode($msg, $hash));
254 }
255
256 /**
257 * 署名を確認する（RSASSA-PKCS1-v1_5）
258 *
259 * @param string $msg メッセージ
260 * @param string $sig 署名
261 * @param string $hash ハッシュ
262 * @return bool
263 */
264 public function verify(string $msg, string $sig, string $hash = 'sha256'): bool {
265 $em = $this->public($sig);
266 return $em !== null && hash_equals($this->pkcs1Encode($msg, $hash), $em);
267 }
268
269 private function pkcs1Encode(string $msg, string $hash): string {
270 if (!isset(self::DIGEST_INFO[$hash])) throw new \InvalidArgumentException("RSA：未対応のハッシュ：{$hash}");
271 $t = self::DIGEST_INFO[$hash].hash($hash, $msg, true);
272 if ($this->bytes < strlen($t) + 11) throw new \InvalidArgumentException('RSA：鍵が小さ過ぎる');
273 return "\x00\x01".str_repeat("\xFF", $this->bytes - strlen($t) - 3)."\x00".$t;
274 }
275
276 /**
277 * 署名する（RSASSA-PSS、MGF1は同じハッシュ）
278 *
279 * @param string $msg メッセージ
280 * @param string $hash ハッシュ
281 * @param int|null $saltLen ソルトの長さ（null＝ハッシュの長さ）
282 * @return string
283 */
284 public function signPss(string $msg, string $hash = 'sha256', ?int $saltLen = null): string {
285 $mHash = hash($hash, $msg, true);
286 $hLen = strlen($mHash);
287 $saltLen ??= $hLen;
288 $emBits = $this->bits - 1;
289 $emLen = intdiv($emBits + 7, 8);
290 if ($emLen < $hLen + $saltLen + 2) throw new \InvalidArgumentException('RSA：鍵が小さ過ぎる');
291
292 $salt = $saltLen > 0 ? random_bytes($saltLen) : '';
293 $h = hash($hash, str_repeat("\0", 8).$mHash.$salt, true);
294 $db = str_repeat("\0", $emLen - $saltLen - $hLen - 2)."\x01".$salt;
295 $masked = $db ^ self::mgf1($h, $emLen - $hLen - 1, $hash);
296 $masked[0] = chr(ord($masked[0]) & (0xFF >> (8 * $emLen - $emBits)));
297 return $this->private(str_pad($masked.$h."\xBC", $this->bytes, "\0", STR_PAD_LEFT));
298 }
299
300 /**
301 * 署名を確認する（RSASSA-PSS）
302 *
303 * @param string $msg メッセージ
304 * @param string $sig 署名
305 * @param string $hash ハッシュ（MGF1も同じ）
306 * @param int|null $saltLen ソルトの長さ（null＝ハッシュの長さ、-1＝何でも）
307 * @return bool
308 */
309 public function verifyPss(string $msg, string $sig, string $hash = 'sha256', ?int $saltLen = null): bool {
310 $em = $this->public($sig);
311 if ($em === null) return false;
312
313 $mHash = hash($hash, $msg, true);
314 $hLen = strlen($mHash);
315 $emBits = $this->bits - 1;
316 $emLen = intdiv($emBits + 7, 8);
317 $em = substr($em, -$emLen);
318 if (strlen($em) !== $emLen || $emLen < $hLen + 2 || substr($em, -1) !== "\xBC") return false;
319 if ($this->bytes > $emLen && ltrim(substr($this->public($sig), 0, $this->bytes - $emLen), "\0") !== '') return false;
320
321 $masked = substr($em, 0, $emLen - $hLen - 1);
322 $h = substr($em, $emLen - $hLen - 1, $hLen);
323 $topMask = 0xFF >> (8 * $emLen - $emBits);
324 if (ord($masked[0]) & ~$topMask & 0xFF) return false;
325
326 $db = $masked ^ self::mgf1($h, strlen($masked), $hash);
327 $db[0] = chr(ord($db[0]) & $topMask);
328 $one = strpos($db, "\x01");
329 if ($one === false || ltrim(substr($db, 0, $one), "\0") !== '') return false;
330 $salt = substr($db, $one + 1);
331 if ($saltLen !== null && $saltLen >= 0 && strlen($salt) !== $saltLen) return false;
332 if ($saltLen === null && strlen($salt) !== $hLen) return false;
333
334 return hash_equals($h, hash($hash, str_repeat("\0", 8).$mHash.$salt, true));
335 }
336
337 ///////////////
338 // 暗号化
339
340 /**
341 * 暗号化する（RSAES-OAEP、MGF1は同じハッシュ）
342 *
343 * @param string $msg 平文
344 * @param string $hash ハッシュ（OpenSSLのOPENSSL_PKCS1_OAEP_PADDINGはsha1）
345 * @param string $label ラベル
346 * @return string
347 */
348 public function encrypt(string $msg, string $hash = 'sha1', string $label = ''): string {
349 $lHash = hash($hash, $label, true);
350 $hLen = strlen($lHash);
351 $k = $this->bytes;
352 if (strlen($msg) > $k - 2 * $hLen - 2) throw new \InvalidArgumentException('RSA：メッセージが長過ぎる');
353
354 $db = $lHash.str_repeat("\0", $k - strlen($msg) - 2 * $hLen - 2)."\x01".$msg;
355 $seed = random_bytes($hLen);
356 $maskedDb = $db ^ self::mgf1($seed, $k - $hLen - 1, $hash);
357 $maskedSeed = $seed ^ self::mgf1($maskedDb, $hLen, $hash);
358 return $this->public("\x00".$maskedSeed.$maskedDb, false);
359 }
360
361 /**
362 * 復号する（RSAES-OAEP）
363 *
364 * @param string $ct 暗号文
365 * @param string $hash ハッシュ
366 * @param string $label ラベル
367 * @return string|null 平文、失敗したらnull
368 */
369 public function decrypt(string $ct, string $hash = 'sha1', string $label = ''): ?string {
370 if (strlen($ct) !== $this->bytes) return null;
371 $em = $this->private($ct);
372 $lHash = hash($hash, $label, true);
373 $hLen = strlen($lHash);
374 if ($this->bytes < 2 * $hLen + 2) return null;
375
376 $maskedSeed = substr($em, 1, $hLen);
377 $maskedDb = substr($em, 1 + $hLen);
378 $seed = $maskedSeed ^ self::mgf1($maskedDb, $hLen, $hash);
379 $db = $maskedDb ^ self::mgf1($seed, strlen($maskedDb), $hash);
380
381 $one = strpos($db, "\x01", $hLen);
382 $bad = ($em[0] !== "\0") | !hash_equals($lHash, substr($db, 0, $hLen)) | ($one === false);
383 if ($bad || ltrim(substr($db, $hLen, $one - $hLen), "\0") !== '') return null;
384 return substr($db, $one + 1);
385 }
386
387 ///////////////
388 // 計算
389
390 /** MGF1（RFC 8017 B.2.1） */
391 private static function mgf1(string $seed, int $len, string $hash): string {
392 $out = '';
393 for ($i = 0; strlen($out) < $len; $i++) $out .= hash($hash, $seed.pack('N', $i), true);
394 return substr($out, 0, $len);
395 }
396
397 /** 公開鍵の計算（m^e mod n） */
398 private function public(string $data, bool $check = true): ?string {
399 if (strlen($data) !== $this->bytes) {
400 if ($check) return null;
401 throw new \InvalidArgumentException('RSA：長さが違う');
402 }
403 $m = gmp_import($data);
404 if (gmp_cmp($m, $this->n) >= 0) return null;
405 return $this->i2osp(gmp_powm($m, $this->e, $this->n));
406 }
407
408 /** 秘密鍵の計算（CRT、ブラインディング、結果の確認） */
409 private function private(string $data): string {
410 if ($this->d === null) throw new \LogicException('RSA：秘密鍵ではない');
411 $c = gmp_import($data);
412 if (gmp_cmp($c, $this->n) >= 0) throw new \InvalidArgumentException('RSA：値が大き過ぎる');
413
414 // ブラインディング：c' = c * r^e
415 do {
416 $r = gmp_mod(gmp_import(random_bytes($this->bytes + 8)), $this->n);
417 $ri = gmp_invert($r, $this->n);
418 } while ($ri === false || gmp_sign($r) === 0);
419 $cb = gmp_mod(gmp_mul($c, gmp_powm($r, $this->e, $this->n)), $this->n);
420
421 if ($this->p !== null && $this->qi !== null) {
422 $m1 = gmp_powm($cb, $this->dp, $this->p);
423 $m2 = gmp_powm($cb, $this->dq, $this->q);
424 $h = gmp_mod(gmp_mul($this->qi, gmp_sub($m1, $m2)), $this->p);
425 $mb = gmp_add($m2, gmp_mul($h, $this->q));
426 } else {
427 $mb = gmp_powm($cb, $this->d, $this->n);
428 }
429 $m = gmp_mod(gmp_mul($mb, $ri), $this->n);
430
431 // 計算の誤り（故障攻撃）を防ぐ
432 if (gmp_cmp(gmp_powm($m, $this->e, $this->n), $c) !== 0) throw new \RuntimeException('RSA：計算に失敗');
433 return $this->i2osp($m);
434 }
435
436 private function i2osp(\GMP $x): string {
437 return str_pad(gmp_export($x), $this->bytes, "\0", STR_PAD_LEFT);
438 }
439}