RSA暗号とPEM/DERの構造

(2017-10-01)

RSA暗号とは

  • 暗号化: c ≡ m^e (mod n)
  • 複合: m ≡ c^d (mod n)

公開鍵がe,nで秘密鍵がd。nはとても大きく近くない素数p,qの積で、 これを公開しても素因数分解できないのがこの暗号の前提になっている。 768bit(10進数で232桁)では既に解読されているので、少なくとも1024bit以上にする。

eはEuler totient function(1~nまでの整数でnと互いに素なものの個数。今回の場合はφ(n)=(p-1)(q-1))未満で互いに素な正の整数で、小さすぎても大きすぎてもだめ。2^16 + 1 = 65537がよく使われる。

dはed ≡ 1 (mod φ(n))を満たすd。

例として(p,q)=(193,709)とするとこんな感じ。

  • n = p * q = 136837
  • φ(n) = (p-1)(q-1) = 135936
  • e = 65537 < φ(n)

秘密鍵dは65537*d ≡ 1 (mod 135936)の式を変形した 65537*d - 135936*x = gcd(65537,135936) = 1を、拡張されたユークリッドの互除法で解く。 以下のように135936と65537を残しながら展開していく。

135936 = 65537 * 2 + 4862 
=> 4862 = 135936 * 1 + 65537 * -2

65537 = 4862 * 13 + 2331 
=> 2331 = 65537 - (135936 * 1 + 65537 * -2) * 13
        = 135936 * -13 + 65537 * 27

4862 = 2331 * 2 + 200 
=> 200 = (135936 * 1 + 65537 * -2) - (135936 * -13 + 65537 * 27) * 2
       = 135936 * 27 + 65537 * -56

2331 = 200 * 11 + 131 
=> 131 = (135936 * -13 + 65537 * 27) - (135936 * 27 + 65537 * -56) * 11
       = 135936 * -310 + 65537 * 643 
...

これをコードに表したのがこれ。

const d = (phi,e) => {
    let history = {[phi]: [1,0], [e]:[0,1]} // [x,y] => φ * x + e * y
    let x = phi
    let y = e
    while(y > 1){
        const nextY = x % y
        history[x % y] = history[x].map((vx,index) => vx - history[y][index] * Math.floor(x/y))
        x = y
        y = nextY;
    }
    return history;
}

const phi = (193-1) * (709-1)
const e = 65537
const result = d(phi,e);
console.log(result);
console.log(`1 = ${phi}*${result[1][0]} + ${e}*${result[1][1]}`);
{ '1': [ 9503, -19711 ],
  '6': [ -8519, 17670 ],
  '7': [ 984, -2041 ],
  '62': [ -647, 1342 ],
  '69': [ 337, -699 ],
  '131': [ -310, 643 ],
  '200': [ 27, -56 ],
  '2331': [ -13, 27 ],
  '4862': [ 1, -2 ],
  '65537': [ 0, 1 ],
  '135936': [ 1, 0 ] }
1 = 135936*9503 + 65537*-19711

135936*-65537 + 65537*135936 = 0より 1 = 135936*(9503-65537) + 65537*(-19711 + 135936)なので d=116225。実際(65537*116225) % 135936 = 1が成り立つ。

平文が12345とすると、公開鍵で暗号化したのが(12345 ** 65537) % 136837 = 6964。 これを秘密鍵で複合すると(6964 ** 116225) % 136837 = 12345のように平文が得られる。

鍵ファイルの生成

ssh-keygenで生成されるようなPEMファイルを作る。

用語

DER(Distinguished Encoding Rules)は ASN.1(Abstract Syntax Notation One)記法で定義されたデータを エンコードするルールの一つ。 1a(INTEGER) 0b(byte) 68 65 6c 6c 6f 20 77 6f 72 6c 64("hello world")) のようなtype-length-valueで表す。

PEM(Privacy-enhanced Electronic Mail)は 公開鍵のフォーマットの定義X.509で 定められている拡張子で、Base64でエンコードされたDER。

PKCS(Public-Key Cryptography Standards)は公開鍵暗号における標準仕様を定めたもの。PKCS#1(RFC2313)にはRSA暗号の方式やASN.1表現などが含まれている。

RFC2313に書かれているASN.1を見ながらPEMの内容を確認する。

RSAPrivateKey

n,e,dに加えて生成に使った素数まで含んでいる。

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 }

   Version ::= INTEGER

pemを生成し、Base64デコードしてDERにする。

$ openssl genrsa 1024 > secret.pem
$ cat secret.pem 
-----BEGIN RSA PRIVATE KEY-----
(内容)
-----END RSA PRIVATE KEY-----

$ echo (内容) | base64 -D | xxd
00000000: 3082 025c 0201 0002 8181 .... .... .... 
00000080: .... .... .... .... .... ..02 0301 0001
00000090: 0281 80..
00000110: .... ..02 41.. 
00000150: .... .... .... 0241 ....
00000190: .... .... .... .... ..02 40.. 
000001d0: .... .... .... .... .... ..02 41.. ....  
00000210: .... .... .... .... .... .... .... 0240 

整理するとこんな感じ。

[0000] 30 82 02 5c       
(30->Type=SEQUENCE 82->先頭bitが1なのでlengthに使うバイト数(2bytes) 025c->Length=605bytes)

  [0000] 02 01 00
  (version: 02->Type=INTEGER, 01->先頭が0なのでそのままLength=3bytes, Value=0)

  [0000] 02 81 81 .. 
  (modulus: Type=INTEGER, Length=129bytes)

  [0080] 02 03 01 00 01 
  (publicExponent: Type=INTEGER, Length=3bytes, Value=65537)

  [0090] 02 81 80 ..
  (privateExponent: Type=INTEGER, Length=128bytes)

  [0110] 02 41 ..
  (prime1: Type=INTEGER, Length=65bytes)

  [0150] 02 41 .. 
  (prime2: Type=INTEGER, Length=65bytes)

  [0190] 02 40 ..
  (exponent1: Type=INTEGER, Length=64bytes)

  [01d0] 02 41 ..
  (exponent2: Type=INTEGER, Length=65bytes)

  [0210] 02 40 ..
  (coefficient: Type=INTEGER, Length=64bytes)

RSAPublicKey

nとeだけ。

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

秘密鍵から公開鍵を生成して同様にDERにする。

$ openssl rsa -pubout < secret.pem > public.pem
$ cat public.pem 
-----BEGIN PUBLIC KEY-----
(内容)
-----END PUBLIC KEY-----

$ echo (内容) | base64 -D | xxd
00000000: 3081 9f30 0d06 092a 8648 86f7 0d01 0101
00000010: 0500 0381 8d00 3081 8902 8181 .... ....
00000090: .... .... .... .... .... .... ..02 0301 
000000a0: 0001
[0000] 30 81 9f
(Type=SEQUENCE, Length=159bytes)
  [0000] 30 0d
  (Type=SEQUENCE, Length=13bytes)
    [0000] 06 09 2a 86 48 86 f7 0d 01 01 01
    (Type=OBJECT IDENTIFIER, Length=9bytes, 
    value=http://www.oid-info.com/get/1.2.840.113549.1.1.1
          最上位ビットは区切りのサイン
          2a ((0)010 1010) => 40 * 1 + 2 => 1(iso) 2(member-body)
          86 48 ((1)000 0110 (0)100 1000) => 840(us)
          86 f7 0d ((1)000 0110 (1)111 0111 (0)000 1101) => 113549(rsadsi)
          01 ((0)000 0001) => 1(pkcs)
          01 ((0)000 0001) => 1(pcks-1)
          01 ((0)000 0001) => 1(rsaEncryption)

    [0010] 05 00
    (アルゴリズムパラメータ: Type=Null 0byte)

    [0010] 03 81 8d 00 
    (Type=BIT STRING, 141bytes, 最終byteの切り捨て0bit)

      [0010] 30 81 89
      (Type=SEQUENCE, 137bytes)

        [0010] 02 81 81 ..
        (modulus: Type=INTEGER, Length=129bytes)

        [0090] 02 03 01 00 01
        (publicExponent: Type=INTEGER, Length=3bytes, Value=65537)

digestInfo

署名に使う。

digestInfo ::= SEQUENCE {
     digestAlgorithm DigestAlgorithmIdentifier,
     digest Digest 
}

Digest ::= OCTET STRING

digestAlgorithmでデータをハッシュ化したものをdigestInfoに詰め、秘密鍵で暗号化したものを署名とし、 公開鍵で複合してdigestと実際のハッシュ値が一致することを確認する。 RSASSA-PKCS1-v1_5では暗号化の前に00 01 ff ff ff .. 00のパディングを加える。

参考

A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

自堕落な技術者の日記 : 図説RSA署名の巻

RSA 秘密鍵/公開鍵ファイルのフォーマット - bearmini’s blog

openssl - How is OID 2a 86 48 86 f7 0d parsed as 1.2.840.113549? - Cryptography Stack Exchange