RSA公開鍵のファイル形式とfingerprint


### 概要

SSHの公開鍵にはfingerprintが表示されるが、何なのかわからなかったので調べた。2048bitのRSAの公開鍵を想定している。

### fingerprintとは

鍵を識別するための情報。いわゆる電子指紋。
ハッシュ関数を使うので、値がわずかでも異なっていると、全く違う値が出力される。
そのため、視認性がよく、鍵の全ての情報で比較しなくてもすむ。
十分に良いハッシュ関数を使えば、たまたまfingerprintが一致することはまずない。
SHA-256でハッシュ値を計算し、その値をBase64エンコードしたSHA-256/base64形式が使われることが多い。(以前はMD5/hexが多かったが、安全ではないため使われなくなった)

### OpenSSH形式

公開鍵のファイル形式には何種類かある。SSH用の鍵を作るとき、たいていは以下のようにして作る。

```bash
$ ssh-keygen -t rsa -b 2048
```

これにより、秘密鍵ファイルと、ssh-rsaではじまる公開鍵ファイルが作成される。これはおおむねRFC4716の形式と同じだが、ヘッダは含まず改行もされていない。OpenSSH独自の形式らしい。Base64の中身は同じなので、

```
---- BEGIN SSH2 PUBLIC KEY ----
Base64でエンコードされたAAAAではじまる部分を76文字以内に改行したもの
---- END SSH2 PUBLIC KEY ----

```

のようにするとRFC4716のフォーマットになる。
Base64の中身(バイナリ部分)は、RFC4253で規定されている。
バイナリの部分はbig endianで記録されており、例えば以下のようになる。(先頭の7桁の数値はオフセット)

```
0000000 00 00 00 07 73 73 68 2d 72 73 61 00 00 00 03 01
0000010 00 01 00 00 01 01 00 ef 3d a8 c9 e3 ed e6 f3 5b
0000020 1f b3 db 89 e8 b0 04 e8 11 9c 25 32 c9 4b d4 a3
0000030 a5 a2 fa ea 94 5a f3 31 ae 38 b5 bc 7d b5 56 24
0000040 d9 60 b8 e0 e3 44 6b ba 54 82 18 5c 23 cf 09 c8
0000050 e0 03 2d 11 d2 19 ee e3 a8 97 5d 84 df 13 99 60
0000060 d8 30 4c 16 83 34 24 fd a7 42 18 62 e1 55 19 f4
0000070 32 c6 56 af af ba 12 21 a6 8d 9a 54 91 cb ed 28
0000080 b3 5c 62 ec 88 88 3c 21 c4 ff b9 df 89 f0 d0 8a
0000090 a1 ad 6f a6 fa 4c 13 b0 3f 74 17 83 92 1d ad 78
00000a0 aa 40 90 25 93 ef 12 d1 73 e1 6e 7c 30 cd 63 a1
00000b0 96 b4 77 59 fb 6a 8f 29 41 3d 21 92 0c 94 28 17
00000c0 47 c9 e6 1d 9c 03 6c 89 88 6a 93 57 7e d8 45 34
00000d0 e1 3d 69 90 12 ec fc 36 3c 78 6d 36 84 69 3b a5
00000e0 e7 f5 0d 85 27 a5 b3 b9 21 77 f2 2f 1d 5f 68 37
00000f0 a4 f6 a3 85 7f fd f0 2c ca 34 59 95 82 84 50 79
0000100 5d 6f 73 0b fd 01 f1 5a ce fe 86 a5 92 6b d3 42
0000110 c3 05 d9 1a 11 25 c3                           
```

先頭から、次のような意味である。

| binary             | 意味 |
|:-------------------|:------------|
| 00 00 00 07          |  文字列 "ssh-rsa"の長さ |
| 73 73 68 2d 72 73 61 | "ssh-rsa" |
| 00 00 00 03          | 数値のバイト数(3) |
| 01 00 01             | eの値(0x10001) |
| 00 00 01 01          | 数値のバイト数(0x101) |
| 00 ef 3d a8...       | nの値(0xEF3DA8...) |

これ以外の情報は入っておらず、かなりシンプルなフォーマットである。
nの先頭が00だが、最上位ビットが立っている場合はゼロを追加するようになっていて、負の値と見なされないようにするためではないかと思われる。
fingerprintは、このバイナリ部分のハッシュ値である。MD5/hexの場合は16バイトをHEX表示、SHA-256/base64の場合は32バイトをBase64エンコードしたものになる。Base64の末尾のpaddingの`=`は消すようである。

### PKCS#1形式

SSH以外の用途で公開鍵をやりとりするときは、ヘッダつきのPEM形式を使うことが多いと思う。OpenSSH形式からは以下のようにすると変換可能である。

```
$ ssh-keygen -f hoge.pub -e -m pem
```

※ ssh-keygenのバージョンによってはこれは失敗する。最新版のOpenSSHをインストールするか、または、以下のコマンドでRFC4716形式の秘密鍵から出力できる。

```
$ openssl rsa -in hoge -RSAPublicKey_out
```

前掲のファイルと同じものが以下の形式になる。

```
-----BEGIN RSA PUBLIC KEY-----
MIIBCgKCAQEA7z2oyePt5vNbH7PbieiwBOgRnCUyyUvUo6Wi+uqUWvMxrji1vH21
ViTZYLjg40RrulSCGFwjzwnI4AMtEdIZ7uOol12E3xOZYNgwTBaDNCT9p0IYYuFV
GfQyxlavr7oSIaaNmlSRy+0os1xi7IiIPCHE/7nfifDQiqGtb6b6TBOwP3QXg5Id
rXiqQJAlk+8S0XPhbnwwzWOhlrR3WftqjylBPSGSDJQoF0fJ5h2cA2yJiGqTV37Y
RTThPWmQEuz8Njx4bTaEaTul5/UNhSels7khd/IvHV9oN6T2o4V//fAsyjRZlYKE
UHldb3ML/QHxWs7+hqWSa9NCwwXZGhElwwIDAQAB
-----END RSA PUBLIC KEY-----
```

これはPKCS#1形式で、中身はDERエンコードされた数値(いわゆるASN.1バイナリ)である。
なおDERエンコードしてBase64にかけたフォーマットをPEMと呼ぶようで、様々なPEMファイルがある。

```
0000000 30 82 01 0a 02 82 01 01 00 ef 3d a8 c9 e3 ed e6
0000010 f3 5b 1f b3 db 89 e8 b0 04 e8 11 9c 25 32 c9 4b
0000020 d4 a3 a5 a2 fa ea 94 5a f3 31 ae 38 b5 bc 7d b5
0000030 56 24 d9 60 b8 e0 e3 44 6b ba 54 82 18 5c 23 cf
0000040 09 c8 e0 03 2d 11 d2 19 ee e3 a8 97 5d 84 df 13
0000050 99 60 d8 30 4c 16 83 34 24 fd a7 42 18 62 e1 55
0000060 19 f4 32 c6 56 af af ba 12 21 a6 8d 9a 54 91 cb
0000070 ed 28 b3 5c 62 ec 88 88 3c 21 c4 ff b9 df 89 f0
0000080 d0 8a a1 ad 6f a6 fa 4c 13 b0 3f 74 17 83 92 1d
0000090 ad 78 aa 40 90 25 93 ef 12 d1 73 e1 6e 7c 30 cd
00000a0 63 a1 96 b4 77 59 fb 6a 8f 29 41 3d 21 92 0c 94
00000b0 28 17 47 c9 e6 1d 9c 03 6c 89 88 6a 93 57 7e d8
00000c0 45 34 e1 3d 69 90 12 ec fc 36 3c 78 6d 36 84 69
00000d0 3b a5 e7 f5 0d 85 27 a5 b3 b9 21 77 f2 2f 1d 5f
00000e0 68 37 a4 f6 a3 85 7f fd f0 2c ca 34 59 95 82 84
00000f0 50 79 5d 6f 73 0b fd 01 f1 5a ce fe 86 a5 92 6b
0000100 d3 42 c3 05 d9 1a 11 25 c3 02 03 01 00 01      
```

意味は以下の通り。

| binary             | 意味 |
|:-------------------|:------------|
| 30 　　　         | SEQUENCE |
| 82       | 次の2バイトがSEQUENCEの長さ |
| 01 0a           | 0x10Aバイト |
| 02              | INTEGER |
| 82       | 次の2バイトがINTEGERの長さ |
| 01 01    | nの長さ(0x101バイト) |
| 00 ef 3d a8...   | nの値(0xEF3DA8...) |
| 02              | INTEGER |
| 03       | INTEGERの長さ(3バイト) |
| 01 00 01      | eの値(0x10001) |

このフォーマットでは、複合型で数値が2つ入っているということしか言っていない。これも比較的シンプルな形式である。

### PKCS#8形式

別の形式もある。OpenSSLで

```
$ openssl genrsa -out hoge.key 2048
$ openssl rsa -pubout -in hoge.key 
```

のようにすると生成できる。
もしくは、ssh-keygenで作成した鍵から、

```
$ openssl rsa -in hoge -pubout
```

でも出力できる。

これはPKCS#8形式の公開鍵であり、以下のような内容である。

```
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA7z2oyePt5vNbH7Pbieiw
BOgRnCUyyUvUo6Wi+uqUWvMxrji1vH21ViTZYLjg40RrulSCGFwjzwnI4AMtEdIZ
7uOol12E3xOZYNgwTBaDNCT9p0IYYuFVGfQyxlavr7oSIaaNmlSRy+0os1xi7IiI
PCHE/7nfifDQiqGtb6b6TBOwP3QXg5IdrXiqQJAlk+8S0XPhbnwwzWOhlrR3Wftq
jylBPSGSDJQoF0fJ5h2cA2yJiGqTV37YRTThPWmQEuz8Njx4bTaEaTul5/UNhSel
s7khd/IvHV9oN6T2o4V//fAsyjRZlYKEUHldb3ML/QHxWs7+hqWSa9NCwwXZGhEl
wwIDAQAB
-----END PUBLIC KEY-----
```

バイナリは以下の通り。

```
0000000 30 82 01 22 30 0d 06 09 2a 86 48 86 f7 0d 01 01
0000010 01 05 00 03 82 01 0f 00 30 82 01 0a 02 82 01 01
0000020 00 ef 3d a8 c9 e3 ed e6 f3 5b 1f b3 db 89 e8 b0
0000030 04 e8 11 9c 25 32 c9 4b d4 a3 a5 a2 fa ea 94 5a
0000040 f3 31 ae 38 b5 bc 7d b5 56 24 d9 60 b8 e0 e3 44
0000050 6b ba 54 82 18 5c 23 cf 09 c8 e0 03 2d 11 d2 19
0000060 ee e3 a8 97 5d 84 df 13 99 60 d8 30 4c 16 83 34
0000070 24 fd a7 42 18 62 e1 55 19 f4 32 c6 56 af af ba
0000080 12 21 a6 8d 9a 54 91 cb ed 28 b3 5c 62 ec 88 88
0000090 3c 21 c4 ff b9 df 89 f0 d0 8a a1 ad 6f a6 fa 4c
00000a0 13 b0 3f 74 17 83 92 1d ad 78 aa 40 90 25 93 ef
00000b0 12 d1 73 e1 6e 7c 30 cd 63 a1 96 b4 77 59 fb 6a
00000c0 8f 29 41 3d 21 92 0c 94 28 17 47 c9 e6 1d 9c 03
00000d0 6c 89 88 6a 93 57 7e d8 45 34 e1 3d 69 90 12 ec
00000e0 fc 36 3c 78 6d 36 84 69 3b a5 e7 f5 0d 85 27 a5
00000f0 b3 b9 21 77 f2 2f 1d 5f 68 37 a4 f6 a3 85 7f fd
0000100 f0 2c ca 34 59 95 82 84 50 79 5d 6f 73 0b fd 01
0000110 f1 5a ce fe 86 a5 92 6b d3 42 c3 05 d9 1a 11 25
0000120 c3 02 03 01 00 01                              
0000126
```

| binary             | 意味 |
|:-------------------|:------------|
| 30 　　　         | SEQUENCE |
| 82       | 次の2バイトがSEQUENCEの長さ |
| 01 22           | 0x122バイト |
| 30 　　　         | SEQUENCE |
| 0d 　　　         | OBJECT (AlgorithmIdentifier) |
| 06 　　　         | OBJECT IDENTIFIER (algorithm) |
| 09 　　　         | OBJECT IDENTIFIERの長さ(9バイト) |
| 2a 86 48 86 f7 0d 01 01 01 | PKCS#1 rsaEncryption |
| 05 　　　         | NULL (parameters) |
| 00 　　　         | NULLの長さ(0バイト) |
| 03 　　　         | BIT STRING  |
| 82       | 次の2バイトがBIT STRINGの長さ |
| 01 0f 　　　      | BIT STRINGの長さ(0x10Fバイト) |
| 00 　　　         | 未使用ビットの長さ(0ビット) |
| 30 82 01 0a... | PKCS#1 公開鍵 |

この形式ではPKCS#1の公開鍵であるという情報が入っている。

### 読み込み

OpenSSLでPKCS#1形式のPEMファイルを読み込むにはPEM_read_RSAPublicKeyを使用する。
PKCS#8形式のPEMファイルを読み込むにはPEM_read_RSA_PUBKEYを使用する。
これにより構造体RSAのオブジェクトが得られる。
なお楕円曲線暗号の公開鍵のPEMファイルを読み込むにはPEM_read_EC_PUBKEYを使用する。こちらは構造体EC_KEYのオブジェクトが得られる。

### fingerprintの生成

OpenSSH形式のファイルの場合、Base64のデコードを行うだけでよい。Base64のデコードはOpenSSLのBIO_f_base64などで行える。
PEMファイルからFingerprintを生成するには、公開鍵をRSA構造体に読み込んだあと、BN_bn2binで整数(eとn)をバイナリに書き出せばよい。
楕円曲線暗号の場合はEC_POINT_point2octにより公開鍵の座標のバイナリを得る。

最終的に完成したプログラムはこれ。
https://github.com/firewood/test/blob/master/fingerprint.cc

### Ruby版

Rubyですでに同じことをしている方がいた。

Calculating RSA Key Fingerprints in Ruby
https://stelfox.net/blog/2014/04/calculating-rsa-key-fingerprints-in-ruby/

これをもとに、三つのフォーマット対応版を書いてみた。
https://github.com/firewood/test/blob/master/fingerprint.rb

```ruby:fingerprint.rb
#!/usr/bin/env ruby

require 'openssl'
require 'base64'

def decode_pubkey(content)
  key = OpenSSL::PKey::RSA.new(content)
  key && [key.public_key.e, key.public_key.n] || nil
end

def decode_ssh_pubkey(content)
  s = content.split(' ')
  return nil unless s.size >= 2 && s[0] == 'ssh-rsa' && s[1].slice(0, 4) == 'AAAA'
  bin = Base64.decode64(s[1])
  prefix = [7].pack('N') + 'ssh-rsa'
  return nil unless bin.slice!(0, prefix.length) == prefix

  data = []
  until bin.empty?
    header = bin.slice!(0, 4)
    return nil unless header.length == 4
    bytes = header.unpack('N').first
    number = bin.slice!(0, bytes)
    return nil unless number.length == bytes
    data << OpenSSL::BN.new(number, 2)
  end
  data.size >= 2 && data || nil
end

def fingerprint(filename)
  content = File.read(filename)
  e, n = decode_ssh_pubkey(content) || decode_pubkey(content)
  return nil unless n
  data_string = [7].pack('N') + 'ssh-rsa' + e.to_s(0) + n.to_s(0)
  OpenSSL::Digest::MD5.hexdigest(data_string).scan(/../).join(':')
end

puts fingerprint(ARGV[0] || 'pubkey')
```

### 参考記事

* RSA公開鍵から素数の積を取り出す方法
http://d.hatena.ne.jp/hnw/20140517

* RSA 秘密鍵/公開鍵ファイルのフォーマット
http://bearmini.hatenablog.com/entry/2014/02/05/143510

* Converting OpenSSH public keys
http://blog.oddbit.com/2011/05/08/converting-openssh-public-keys/

* Howto base64 decode with C/C++ and OpenSSL
http://www.ioncannon.net/programming/122/howto-base64-decode-with-cc-and-openssl/

* A Layman's Guide to a Subset of ASN.1, BER, and DER
http://luca.ntop.org/Teaching/Appunti/asn1.html

* ASN.1 バイナリ変換規則 (BER)
http://www.geocities.co.jp/SiliconValley-SanJose/3377/asn1Body.html#BITSTRING

* ASN.1 key structures in DER and PEM
https://tls.mbed.org/kb/cryptography/asn1-key-structures-in-der-and-pem

* dumpasn1の使い方メモ
https://qiita.com/hnw/items/8dcfb1befd5f8a15112c

### 更新履歴

- 2019-09-01 SHA-256/base64について追記。fingerprint.ccをecdsa-sha2-nistp256対応にした。