PKCS #1(RFC8017)のRSA鍵フォーマット日本語訳

PKCS #1 / PKCS #8に準拠した，.NET向けRSA暗号鍵エンコーダ・デコーダライブラリをNuGetに公開しました．ソースコードや使い方はGitHubにあります．

この記事では，PKCS #1での鍵フォーマットについて説明します．

PKCS #1 (RFC8017)

RFC 8017 - PKCS #1: RSA Cryptography Specifications Version 2.2

公開鍵暗号標準であるPKCSのドキュメントのひとつ PKCS #1(RFC8017) は，RSA暗号の仕様を定めたものです．暗号化や署名のアルゴリズムはもちろんですが，鍵の表現方法についてもAppendixに記載があります．

鍵の表現方法を定めた部分を訳してみます．

RFC8017 Appendix A. ASN.1 Syntax

付録 A. ASN.1 構文

A.1. RSA鍵表現

  この章では，RSA公開鍵・秘密鍵のASN.1オブジェクト識別子を定義するとともに， RSAPublicKey と RSAPrivateKey の型を定義します．  
  定義の対象用途には，X.509証明書，PKCS #8(RFC5958)，PKCS #12(RFC7292)を含みます．

  オブジェクト識別子 rsaEncryption は， A.1.1 と A.1.2 で定義されるRSA公開鍵・秘密鍵を識別するものです．このオブジェクト識別子(OID)に関連付けられているAlgorithmIdentifier型のパラメタフィールドは，NULL型の値を持つものとします(SHALL)．

      rsaEncryption    OBJECT IDENTIFIER ::= { pkcs-1 1 }

  この定義は，multi-prime RSAをサポートするよう拡張されていますが，過去のバージョンと下位互換性があります．

A.1.1. RSA公開鍵構文

  RSA公開鍵は，ASN.1のRSAPublicKey型により表現されます:

      RSAPublicKey ::= SEQUENCE {
          modulus           INTEGER,  -- n
          publicExponent    INTEGER   -- e
      }

  各フィールドは次のような意味を持ちます:

  - modulus: RSA の modulus n
  - publicExponent: RSA の public exponent e

A.1.2. RSA秘密鍵構文

  RSA秘密鍵は，ASN.1のRSAPrivateKey型により表現されます:

      RSAPrivateKey ::= SEQUENCE {
          version           Version,
          modulus           INTEGER,  -- n
          publicExponent    INTEGER,  -- e
          privateExponent   INTEGER,  -- d
          prime1            INTEGER,  -- p
          prime2            INTEGER,  -- q
          exponent1         INTEGER,  -- d mod (p-1)
          exponent2         INTEGER,  -- d mod (q-1)
          coefficient       INTEGER,  -- (inverse of q) mod p
          otherPrimeInfos   OtherPrimeInfos OPTIONAL
      }

  各フィールドは次のような意味を持ちます:

  - version: 将来の改訂を考慮するためのバージョン番号．0とします(SHALL)．ただし，multi-primeを使用する場合は1とします(SHALL)．
            Version ::= INTEGER { two-prime(0), multi(1) }
               (CONSTRAINED BY
               {-- otherPrimesInfosを含む場合，versionは必ず multi(1) とすべきです --})
  
  - modulus: RSA の modulus n
  - publicExponent: RSA の public exponent e
  - privateExponent: RSA の private exponent d
  - prime1: n の素因数 p
  - prime2: n の素因数 q
  - exponent1: d mod (p - 1)
  - exponent2: d mod (q - 1)
  - coefficient: CRT(中国剰余定理) の coefficient q^(-1) mod p
  - otherPrimeInfos: 追加の素数を r_3, ..., r_u, の順に含みます．version 0の場合は省略する(SHALL)．version 1の場合は1つ以上のOtherPrimeInfoを含みます．
            OtherPrimeInfos ::= SEQUENCE SIZE(1..MAX) OF OtherPrimeInfo

            OtherPrimeInfo ::= SEQUENCE {
                prime             INTEGER,  -- ri
                exponent          INTEGER,  -- di
                coefficient       INTEGER   -- ti
            }
  
    OtherPrimeInfoのフィールドは次のような意味を持ちます:
      - prime: n の素因数 r_i (i >= 3)
      - exponent: d_i = d mod (r_i - 1)
      - coefficient: CRT(中国剰余定理)の coefficient t_i = (r_1 * r_2 * ... * r_(i-1))^(-1) mod r_i

  注意: RSA秘密鍵は，流出や改ざんからの保護が重要です．保護方法についてはこの文書の範囲外です．秘密鍵やその他の暗号データを保存・配布する方法については，PKCS #12やPKCS #15で記述しています．

読み解くポイント: RSA, ASN.1, CRT

定義は明確ですが，いくつか前提知識を必要とします．

modulus n, publicExponent eなどは，RSA暗号の鍵パラメタです．「パラメタだ」という理解で留めておくのが無難ですが，アルゴリズムを理解したい方は"サルにも分かる"から読み始めると良いかもしれません．
- RSA暗号の世界 – まいとう情報通信研究会
SEQUENCE, INTEGER ほか，特殊な構文っぽい表記は ASN.1 という記法で記述されたものです．記法そのものは環境に依存しません．これを符号化（データ化）するアルゴリズムとして DER などが存在します．
- Abstract Syntax Notation One - Wikipedia
- ASN.1 バイナリ変換規則 (BER, CER, DER)
CRT(中国剰余定理)は，秘密鍵による復号（署名生成）を高速化するために使われています．こちらも「そのためのパラメタだ」という理解で留めておくのが無難ですが…
- 中国の剰余定理 - Wikipedia

PKCS #1の鍵表現の使われどころ

-----BEGIN RSA PUBLIC KEY-----で始まる文字列を見たことはあるでしょうか？あれは，PKCS #1形式によってRSA公開鍵が表現されています．

（※BEGIN PUBLIC KEYで始まるのはPKCS #8形式です．そちらはまた別途．）

$ ssh-keygen -f .ssh/id_rsa.pub -e -m pem
-----BEGIN RSA PUBLIC KEY-----
MIIBCgKCAQEAtH53M23IIXvXnM6d4nrZ9Q3BCU/HSMoYnZHlU6ytPXWZ5Y9oGAdX
4S2cMNOt7ZbiXXT9aRFyQwv80MCd6yMfrkHgFG0V2Oim59R1zypVXm7pvQmNApx3
Qvp+YMeEyLveFvn+wdwkeUSW1ag9D4ZIRwIE3kTqVxEj5BXElaaTW0HxYRDWVbrA
MU9RSekhTq2bHRSKIfMcbqtu/tFj9SS/46XiCPd05wolorAYTY3y2ntPVc9hbepf
IbxoiADm75pjxM1wg8ESOOmxSTQJO4hmdOEFRkMfRFFB65o2anN89Ubd1WJARwP5
+MYnliqPN3PO7eSqBw7qEzj+wqmRoX2YQwIDAQAB
-----END RSA PUBLIC KEY-----

この公開鍵は，PKCS #1で定める RSAPublicKey を，DERとBASE64で符号化したものです．

これを，Asn1PKCSでデコードしてみましょう．

var key = "MIIBCgKCAQEAtH53M23IIXvXnM6d4nrZ9Q3BCU/HSMoYnZHlU6ytPXWZ5Y9oGAdX4S2cMNOt7ZbiXXT9aRFyQwv80MCd6yMfrkHgFG0V2Oim59R1zypVXm7pvQmNApx3Qvp+YMeEyLveFvn+wdwkeUSW1ag9D4ZIRwIE3kTqVxEj5BXElaaTW0HxYRDWVbrAMU9RSekhTq2bHRSKIfMcbqtu/tFj9SS/46XiCPd05wolorAYTY3y2ntPVc9hbepfIbxoiADm75pjxM1wg8ESOOmxSTQJO4hmdOEFRkMfRFFB65o2anN89Ubd1WJARwP5+MYnliqPN3PO7eSqBw7qEzj+wqmRoX2YQwIDAQAB";
var rsaParams = PKCS1DERDecoder.DecodePublicKey(key);

Console.WriteLine("n(modulus)       : 0x" + BitConverter.ToString(rsaParams.Modulus).Replace("-", string.Empty));
Console.WriteLine("e(publicExponent): 0x" + BitConverter.ToString(rsaParams.Exponent).Replace("-", string.Empty));

n(modulus)       : 0xB47E77336DC8217BD79CCE9DE27AD9F50DC1094FC748CA189D91E553ACAD3D7599E58F68180757E12D9C30D3ADED96E25D74FD691172430BFCD0C09DEB231FAE41E0146D15D8E8A6E7D475CF2A555E6EE9BD098D029C7742FA7E60C784C8BBDE16F9FEC1DC24794496D5A83D0F8648470204DE44EA571123E415C495A6935B41F16110D655BAC0314F5149E9214EAD9B1D148A21F31C6EAB6EFED163F524BFE3A5E208F774E70A25A2B0184D8DF2DA7B4F55CF616DEA5F21BC688800E6EF9A63C4CD7083C11238E9B14934093B886674E10546431F445141EB9A366A737CF546DDD562404703F9F8C627962A8F3773CEEDE4AA070EEA1338FEC2A991A17D9843
e(publicExponent): 0x010001

できました．