[memo] SSH用RSA鍵ペアをJavaで生成する

## はじめに

* Java で SSH の鍵ペアを生成する方法をメモする
  * 基本的に独自実装などせずに ssh-keygen を使うべきだと思うけど、ssh-keygen が使えない環境で動かすアプリ上から生成しなくてはならない場合などを想定してみた
* SSH の鍵のフォーマットにもいろいろあるみたいだけど（製品 SSH の SECSH 形式とか、Putty 形式とか）、今回は OpenSSH 形式を想定
  * 参考: Qiita - [RSA鍵のフォーマットを作って見て変換して体験実習しみた](https://qiita.com/ponsuke0531/items/7b34347213660c80bc95#_reference-7e77b7cd21163457038e)
  * 参考: Qiita - [RSA公開鍵のファイル形式とfingerprint](https://qiita.com/hotpepsi/items/128f3a660cee8b5467c6)
* OpenSSH 形式の秘密鍵フォーマットには、昔からの PEM フォーマットと、OpenSSH 独自フォーマットがあるみたいですが、今回は PEM フォーマットを想定。またパスフレーズは設定していない想定です。
  * 参考: DevelopersIO - [【OpenSSH 7.8】秘密鍵を生成する形式が変更になった件について](https://dev.classmethod.jp/server-side/network/openssh78_potentially_incompatible_changes/)

ちなみに、普通に `ssh-keygen` を使うなら以下のような感じ。

```shell-session
ssh-keygen -t rsa -b 4096
```

## RSA の復習 「RSA鍵ペアの概要」

以下の Qiita 記事から説明をお借りします。

* 参考: Qiita - [OpenSSH秘密鍵の中身](https://qiita.com/r-tamura/items/d33f54f94279ddcc71f0) の「RSA鍵ペアの概要」

（ここから借用）

大きな２つの素数を$p$,$q$とした場合、

```math
N = pq \tag{1}
```

以下(2)を満たす変数を$L$とする。

```math
L = lcm(p-1, q-1) \tag{2}
```

さらに、次の式(3)を満たす変数を$E$とする。

```math
gcd(E, L) = 1 \tag{3}
```
最後に、式(4)を満たす変数を$D$とする。

```math
ED≡1 (mod L) \tag{4}
```

※ lcm(x,y)はx,yの最小公倍数(Least Common Multiple)
※ gcd(x,y)はx,yの最大公約数(Greatest Common Divisor)

ここまでで求めた$(E, N)$のペアが*公開鍵*, $(D, N)$のペアが*秘密鍵*になります。

（ここまで借用）

## OpenSSH の 秘密鍵ファイルフォーマット

最初に書いたように、PEM フォーマットかつパスフレーズ無しを想定しています。

基本的には、PKCS#8 を PEM フォーマットにしたもののようです。

詳細は、前述の「RSA公開鍵のファイル形式とfingerprint」の「PKCS#8形式」が詳しいです。

ちなみに、Java の RSAPrivateKey インスタンスの場合、`getEncoded()` メソッドでバイナリデータが入手できるので、MIME 風の Base64 エンコードをすればよいはずです。

```java
    public Optional<String> encodePrivateKey(final PrivateKey privateKey) {

        final String keyType;
        if (privateKey instanceof RSAPrivateKey) {
            keyType = "RSA";
        } else if (privateKey instanceof DSAPrivateKey) {
            keyType = "DSA";
        } else if (privateKey instanceof ECPrivateKey) {
            keyType = "EC";
        } else {
            return Optional.empty();
        }

        final byte[] privateBytes = privateKey.getEncoded();
        final String privateBase64 = Base64.getMimeEncoder()
                .encodeToString(privateBytes);

        final String encodedPrivateKey = "-----BEGIN " + keyType + " PRIVATE KEY-----\n"
                + privateBase64 + "\n"
                + "-----END " + keyType + " PRIVATE KEY-----";
        return Optional.of(encodedPrivateKey);
    }
```

## OpenSSH の RSA 公開鍵ファイルフォーマット

[RFC4716](https://tools.ietf.org/html/rfc4716) に記載の書式とは異なり、OpenSSH 形式の場合には前後に "BEGIN" / "END" のデリミタはない代わりに、先頭に "ssh-rsa" というシグネチャが付きます。

その後のデータは、RFC4716 の形式と同じようです（前述の「RSA公開鍵のファイル形式とfingerprint」の記事より）。

この形式の詳細は [RFC4253](https://tools.ietf.org/html/rfc4253) の「6.6.  Public Key Algorithms」に記載があります

> string    "ssh-rsa"
> mpint     e
> mpint     n

この「string」や「mpint」の形式は [RFC4251](https://tools.ietf.org/html/rfc4251) の「5.  Data Type Representations Used in the SSH Protocols」に記載があります。
簡単に言えば、4バイトの big endian の長さ＋バイト列みたいな感じですね。

これを、Base64 でエンコードすればよいみたい。OpenSSH 形式の場合には Base64 は行を折り返さず１行で出力すればよいようです。

$e$ や $n$ は前述の「RSA鍵ペアの概要」の中の説明の $E$ と $N$ にあたります。

ちなみに $e$ と $n$ の値は、 Java の RSAPublicKey インスタンスの場合、それぞれ `getPublicExponent()` メソッドと `getModulus()` メソッドで取得できます。

（公開鍵の最後にメールアドレス風なものがついていることがありますが、これはコメントのはずです）

※ちなみに "ssh-rsa" というシグネチャは、base64 されているデータの中にも含まれているし（それが上記の `string "ssh-rsa"` の部分）、それとは別に base64 の前にも付きます（冒頭で言った「デリミタはない代わりに、先頭に "ssh-rsa" というシグネチャが付きます」の部分）。以下のソースを見てもらったほうが分かりやすいと思いますが。

```java
    public String encodeRsaPublicKey(final RSAPublicKey publicKey) {

        final String sig = "ssh-rsa";
        final byte[] sigBytes = sig.getBytes(StandardCharsets.US_ASCII);
        final byte[] eBytes = publicKey.getPublicExponent().toByteArray();
        final byte[] nBytes = publicKey.getModulus().toByteArray();

        final int size = 4 + sigBytes.length
                + 4 + eBytes.length
                + 4 + nBytes.length;

        final byte[] publicKeyBytes = ByteBuffer.allocate(size)
                .order(ByteOrder.BIG_ENDIAN)
                .putInt(sigBytes.length).put(sigBytes)
                .putInt(eBytes.length).put(eBytes)
                .putInt(nBytes.length).put(nBytes)
                .array();

        final String publicKeyBase64 = Base64.getEncoder()
                .encodeToString(publicKeyBytes);

        final String publicKeyEncoded = sig + " " + publicKeyBase64;
        return publicKeyEncoded;
    }
```

## OpenSSH の DSA 公開鍵ファイルフォーマット（おまけ）

DSA は RSA と同様に [RFC4253](https://tools.ietf.org/html/rfc4253) に記載あり。

> string    "ssh-dss"
> mpint     p
> mpint     q
> mpint     g
> mpint     y

```java
    public String encodeDsaPublicKey(final DSAPublicKey publicKey) {

        final String sig = "ssh-dss";
        final byte[] sigBytes = sig.getBytes(StandardCharsets.US_ASCII);
        final DSAParams params = publicKey.getParams();
        final byte[] pBytes = params.getP().toByteArray();
        final byte[] qBytes = params.getQ().toByteArray();
        final byte[] gBytes = params.getG().toByteArray();
        final byte[] yBytes = publicKey.getY().toByteArray();

        final int size = 4 + sigBytes.length
                + 4 + pBytes.length
                + 4 + qBytes.length
                + 4 + gBytes.length
                + 4 + yBytes.length;

        final byte[] publicKeyBytes = ByteBuffer.allocate(size)
                .order(ByteOrder.BIG_ENDIAN)
                .putInt(sigBytes.length).put(sigBytes)
                .putInt(pBytes.length).put(pBytes)
                .putInt(qBytes.length).put(qBytes)
                .putInt(gBytes.length).put(gBytes)
                .putInt(yBytes.length).put(yBytes)
                .array();

        final String publicKeyBase64 = Base64.getEncoder()
                .encodeToString(publicKeyBytes);

        final String publicKeyEncoded = sig + " " + publicKeyBase64;
        return publicKeyEncoded;
    }
```

## OpenSSH の ECDSA （楕円曲線暗号）公開鍵ファイルフォーマット（おまけ）

楕円曲線暗号の公開鍵のフォーマットは [RFC5656](https://tools.ietf.org/html/rfc5656) で定義しているみたい。

```
string   "ecdsa-sha2-[identifier]"
byte[n]  ecc_key_blob
```

`ecc_key_blob` の中身は

```
string   [identifier]
string   Q
```

`identifier` は、楕円曲線の種類から求められるようです。
以下の表の NIST の部分が `identifier` になります。

|   NIST   |    SEC    |         OID         |
|----------|-----------|---------------------|
| nistp256 | secp256r1 | 1.2.840.10045.3.1.7 |
| nistp384 | secp384r1 |     1.3.132.0.34    |
| nistp521 | secp521r1 |     1.3.132.0.35    |

ちなみに、この3種類は【必須】の曲線のようです（SSH のサーバ・クライアントでECDSAをサポートする場合には、必ず実装する楕円曲線）。

他に【推奨】の楕円曲線もあるみたいですが、数が多いので割愛します。
ちなみに、推奨の曲線の `identifier` は NIST の列ではなく OID の列を使うとのこと（例： `ecdsa-sha2-1.3.132.0.38` みたいなシグネチャになるはず）。詳細は RFC 参照。

また、`Q` は「楕円曲線上の点をオクテット文字列にエンコードしたもの」だそうですが、仕様の詳細は `http://www.secg.org/download/aid-780/sec1-v2.pdf` に記載されているとあります。
実際に探してみたら [https://www.secg.org/sec1-v2.pdf](https://www.secg.org/sec1-v2.pdf) に移動しているみたいですが。
このドキュメントの 2.3.3 に詳細な記載があります。
「ポイント圧縮」という機能を使うか、使わないかでフォーマットが異なるようですが、使わない場合には、比較的単純な構造のようです。

とりあえず `identifier` が決まった前提だと以下のような感じ。

```java
    public String encodeEcPublicKey(
            final String identifier,
            final ECPublicKey publicKey) {

        final String sig = "ecdsa-sha2-" + identifier;
        final BigInteger x = publicKey.getW().getAffineX();
        final BigInteger y = publicKey.getW().getAffineY();

        final byte[] sigBytes = sig.getBytes(StandardCharsets.US_ASCII);
        final byte[] identifierBytes = identifier.getBytes(StandardCharsets.US_ASCII);
        final byte[] xBytes = x.toByteArray();
        final byte[] yBytes = y.toByteArray();

        final int size = 4 + sigBytes.length
                + 4 + identifierBytes.length
                + 4 + 1 + xBytes.length + yBytes.length;

        final byte[] publicKeyBytes = ByteBuffer.allocate(size)
                .order(ByteOrder.BIG_ENDIAN)
                .putInt(sigBytes.length).put(sigBytes)
                .putInt(identifierBytes.length).put(identifierBytes)
                .putInt(1 + xBytes.length + yBytes.length)
                .put((byte) 0x04)
                .put(xBytes)
                .put(yBytes)
                .array();

        final String publicKeyBase64 = Base64.getEncoder()
                .encodeToString(publicKeyBytes);

        final String publicKeyEncoded = sig + " " + publicKeyBase64;
        return publicKeyEncoded;

    }
```

そして `identifier` は楕円曲線の種類を示すもので、秘密鍵や公開鍵から取得できる `ECParameterSpec` の中身で判断がつくようです。

具体的なパラメタは、楕円曲線の仕様書を見る必要があるみたい。

仕様の詳細は `http://www.secg.org/download/aid-386/sec2_final.pdf` に記載されているとあります。
実際に探してみたらこれも移動していて [https://www.secg.org/SEC2-Ver-1.0.pdf](https://www.secg.org/SEC2-Ver-1.0.pdf) にありました。

とりあえず `ECParameterSpec` をもとに必須の曲線の `identifier` を決定するには以下のような感じ。

```java
    private Optional<String> decideEcIdentifier(final ECParameterSpec params) {

        if (!(params.getCurve().getField() instanceof ECFieldFp)) {
            return Optional.empty();
        }
        final ECFieldFp field = (ECFieldFp) params.getCurve().getField();
        final BigInteger p = field.getP();
        final BigInteger a = params.getCurve().getA();
        final BigInteger b = params.getCurve().getB();
        final BigInteger g1 = params.getGenerator().getAffineX();
        final BigInteger g2 = params.getGenerator().getAffineY();
        final BigInteger n = params.getOrder();
        final int h = params.getCofactor();

        final List<Number> tuple = Arrays.asList(p, a, b, g1, g2, n, h);
        final String identifier = identifierMap.get(tuple);
        return Optional.ofNullable(identifier);
    }

    private static final Map<List<Number>, String> identifierMap;
    static {
        final Map<List<Number>, String> map = new LinkedHashMap<>();

        map.put(Arrays.asList(
                new BigInteger("115792089210356248762697446949407573530086143415290314195533631308867097853951"),
                new BigInteger("115792089210356248762697446949407573530086143415290314195533631308867097853948"),
                new BigInteger("41058363725152142129326129780047268409114441015993725554835256314039467401291"),
                new BigInteger("48439561293906451759052585252797914202762949526041747995844080717082404635286"),
                new BigInteger("36134250956749795798585127919587881956611106672985015071877198253568414405109"),
                new BigInteger("115792089210356248762697446949407573529996955224135760342422259061068512044369"),
                1), "nistp256");
        map.put(Arrays.asList(
                new BigInteger(
                        "39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319"),
                new BigInteger(
                        "39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112316"),
                new BigInteger(
                        "27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575"),
                new BigInteger(
                        "26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087"),
                new BigInteger(
                        "8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871"),
                new BigInteger(
                        "39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643"),
                1), "nistp384");
        map.put(Arrays.asList(
                new BigInteger(
                        "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151"),
                new BigInteger(
                        "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057148"),
                new BigInteger(
                        "1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984"),
                new BigInteger(
                        "2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846"),
                new BigInteger(
                        "3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784"),
                new BigInteger(
                        "6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449"),
                1), "nistp521");
        identifierMap = Collections.unmodifiableMap(map);
    }

```

## OpenSSH の 公開鍵ファイルフォーマット

上記3種類のフォーマットをエンコードする例です。

```java
    public Optional<String> encodePublicKey(final PublicKey publicKey) {

        if (publicKey instanceof RSAPublicKey) {
            final RSAPublicKey rsaPublicKey = (RSAPublicKey) publicKey;
            return Optional.of(encodeRsaPublicKey(rsaPublicKey));

        } else if (publicKey instanceof DSAPublicKey) {
            final DSAPublicKey dsaPublicKey = (DSAPublicKey) publicKey;
            return Optional.of(encodeDsaPublicKey(dsaPublicKey));

        } else if (publicKey instanceof ECPublicKey) {
            final ECPublicKey ecPublicKey = (ECPublicKey) publicKey;
            return decideEcIdentifier(ecPublicKey.getParams())
                    .map(identifier -> encodeEcPublicKey(identifier, ecPublicKey));
        }
        return Optional.empty();
    }
```

## おまけで RSA 秘密鍵から公開鍵を生成

`ssh-keygen` を使うなら以下のような感じですが

```shell-session
ssh-keygen -yf id_rsa > id_rsa.pub
```

Java でやるならこんな感じ。

```Java
    KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA");
    generator.initialize(4096);
    KeyPair keyPair = generator.genKeyPair();
    RSAPrivateCrtKey privateKey = (RSAPrivateCrtKey) keyPair.getPrivate();
    BigInteger publicExponent = privateKey.getPublicExponent();
    BigInteger modulus = privateKey.getModulus();
    KeyFactory factory = KeyFactory.getInstance("RSA");
    RSAPublicKeySpec spec = new RSAPublicKeySpec(
            modulus,
            publicExponent);
    RSAPublicKey publicKey = (RSAPublicKey) factory.generatePublic(spec);
```

ポイントは、普通に生成した RSA の秘密鍵は `RSAPrivateCrtKey` も実装している点。

## さらにおまけ

ED25519 は RFC はまだ発行されていないのかな？

インターネットドラフトの [https://tools.ietf.org/html/draft-ietf-curdle-ssh-ed25519-ed448-08](https://tools.ietf.org/html/draft-ietf-curdle-ssh-ed25519-ed448-08) を見ると以下のような感じ。

> string    "ssh-ed25519"
> string    key


同様に ED448 は以下のような感じ。

> string    "ssh-ed448"
> string    key