Scala生成SSH形式的RSA公私钥文件

2020-08-06 20:27:24 +08 字数：2382 标签： Scala

利用ssh-keygen生成公私钥是比较简单的，但环境中必须包含openssh-client。如果不确定环境的状态，通过纯Scala，也可以生成RSA公私钥，并保存为SSH的格式。

本文从RSA的原理与相关定义出发，介绍SSH的公私钥格式，并给出Scala的生成样例代码。

RSA相关定义 ¶

假定明文数字是 $x$ ，密文数字是 $y$ 。

符号	解释	关系
p	质数
q	质数
n	合数	$n=p\cdot{q}$
e	公钥乘方数（常用`65537`）	$y=x^e \mod{n}$
d	私钥乘方数（exponent）	$x=y^d \mod{n}$
$q_{\mathrm{inv}}$	（CRT Coefficient）	$q_{\mathrm{inv}} = q^{-1} \pmod{p}$

RSA解释 ¶

非对称加密RSA的公钥是 $(n, e)$ ，私钥是 $(n, d)$ 。通过公钥加密，然后仅可通过私钥解密。

假定明文数字是 $x$ ，密文数字是 $y$ 。

从明文到密文：

$$ y=x^e \mod{n} $$

从密文到明文：

$$ x=y^d \mod{n} $$

而 $e$ 和 $d$ 则通过大素数 $p$ 和 $q$ 计算得到。在通常 $e=65537$ 的情况下， $d$ 通过以下公式计算得出。

$$ d=e^{-1} \pmod{\lambda(n)} $$

也即最终确保 $d$ 与 $e$ 的乘积，除 $\lambda(n)$ 时余数是 $1$ 。

$$ d\cdot{e}\mod{\lambda(n)}=1 $$

其中，$\lambda(n)$是：

$$ \lambda(n)=lcm(p-1, q-1) $$

$lcm$是求最大公倍数。

因此，如果知道了 $p$ 和 $q$ ，就比较容易求得 $d$ ，进而从公钥 $(n, e)$ 知道私钥 $(n, d)$ 。但由于大素数分解 $n=p\cdot{q}$ 的困难，因此在 $p$ 、 $q$ 和 $d$ 都比较大的情况下，RSA具有保密性。

例子可参考：RSA (cryptosystem) - Wikipedia

SSH ¶

虽然密钥对是通过openssl生成的，但id_rsa和id_rsa.pub两个文件的格式，却是openssh自定义的。

openssh支持多种加密方式，以下仅介绍RSA，示例基于1024位秘钥。

公钥文件格式 ¶

SSH的公钥文件格式相对简单，大概形式如下：

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAAAgQDMSZ0xVT+1za4ZO5E2WE82KF6eUciiTM7B9NOunvPQx/P60uZGa3aF+j4jX+cCeohaTJv9KnOgHOFpCok4F0mNKPAzKJako8mEerI1xjHA4/wJDXw0M4qK6P6z9ZGKRnjaso3jRaJDk3r8/uAiTuN+Mi2/Fo28DZ1BXT6A5lh+5Q== name@email

前缀ssh-rsa是编码类型，对RSA来说是固定的。后缀name@email是无关紧要但确定的comment，通常是电子邮件形式。中间的是BASE64编码，其对应的字节内容如下：

len "ssh-rsa"
len e
len n

其中，len是32位（4 bytes）的一个int数字，代表后面内容的长度。 ssh-rsa是类型名称，在这里是固定的。第一项内容的字节形式为00 00 00 07 73 73 68 2d 72 73 61，其中00 00 00 07是32位的数字7；而后面7位73 73 68 2d 72 73 61则是ssh-rsa。

e通常是65537，即0x010001，需要三位。所以第二项长度是7，字节形式是00 00 00 03 01 00 01。 e、n的具体含义，见前面定义。

私钥文件格式 ¶

SSH的私钥文件格式比较复杂，大概形式如下：

首行与末行固定，中间则是BASE64编码的内容，按70字符一行排列。内容如下：

"openssh-key-v1\u0000"
len cipher
len kdfname
len kdfoptions
1
len pub
len prv

其中，第一项是magic字符串。由于是C语言实现的，所以最后还带了一个\0。第二、三项，通常都是字符串none。第四项通常长度为0，kdfoptions没有内容。第五项是密钥数量，目前不支持多个，固定为32位的1。

第六项pub是公钥，即前面公钥的字节内容，内含三项，每项包括长度与内容。 len是公钥三项的总长，私钥的规则相同。

第七项prv最复杂，是私钥的全部信息。内容如下：

rnd rnd
len "ssh-rsa"
len n
len e
len d
len iqmp
len p
len q
len comment
padding

rnd是两个相同的随机数，各32位。从n到q的含义，见前面定义。其中iqmp就是 $q_{\mathrm{inv}}$ 。倒数第二项comment，就是前面公钥的name@email。

最后这个padding是补齐内容。目的是让整个prv部分的总长，是8的整数倍，缺几个补几个，不缺则不补。比如，缺1个，则补01；最大缺7个，补01 02 03 04 05 06 07。

Scala生成公私钥 ¶

import java.security.KeyPairGenerator
import java.security.interfaces.{RSAPublicKey, RSAPrivateCrtKey}
import java.util.Base64
import java.nio.ByteBuffer
import java.io.{ByteArrayOutputStream, DataOutputStream}

import scala.util.Random

object SshKeyGen {
  private val prefix = "ssh-rsa"
  private val comment = "name@email"

  def main(args: Array[String]): Unit = {
    val gen = KeyPairGenerator.getInstance("RSA")
    gen.initialize(4096)
    val pair = gen.genKeyPair()
    val publicKey = pair.getPublic.asInstanceOf[RSAPublicKey]
    val privateKey = pair.getPrivate.asInstanceOf[RSAPrivateCrtKey]
    val encoder = Base64.getEncoder
    val pubArr = calcSshPublicKey(publicKey)
    val sshPub = s"${prefix} ${encoder.encodeToString(pubArr)} ${comment}"
    val pvtArr = calcSshPrivateKey(privateKey, pubArr)
    val sshPvt = shapeSshPrivateKey(encoder.encodeToString(pvtArr))
    println(sshPvt)
    System.err.println(sshPub)
  }

  def calcSshPublicKey(publicKey: RSAPublicKey): Array[Byte] = {
    val baos = new ByteArrayOutputStream()
    val stream = new DataOutputStream(baos)
    Array(
      this.prefix.getBytes,
      publicKey.getPublicExponent.toByteArray, // e
      publicKey.getModulus.toByteArray         // n
    ) foreach (x => this.writeWithLength(stream, x))
    stream.close()
    return baos.toByteArray
  }

  def calcSshPrivateKey(privateKey: RSAPrivateCrtKey, pubArr: Array[Byte]): Array[Byte] = {
    val baos = new ByteArrayOutputStream()
    val stream = new DataOutputStream(baos)

    val magic = "openssh-key-v1\u0000".getBytes
    stream.write(magic)
    val cipher = "none".getBytes
    val kdfname = "none".getBytes
    Array(cipher, kdfname) foreach (x => this.writeWithLength(stream, x))
    stream.writeInt(0) // kdfoptions
    stream.writeInt(1) // number of keys

    val pvtArr = this.genPrivateSection(privateKey)
    Array(pubArr, pvtArr) foreach (x => this.writeWithLength(stream, x))

    stream.close()
    return baos.toByteArray
  }

  def genPrivateSection(privateKey: RSAPrivateCrtKey): Array[Byte] = {
    val baos = new ByteArrayOutputStream()
    val stream = new DataOutputStream(baos)
    val checksum = Random.nextInt

    stream.writeInt(checksum)
    stream.writeInt(checksum)
    Array(
      this.prefix.getBytes,
      privateKey.getModulus.toByteArray,         // n
      privateKey.getPublicExponent.toByteArray,  // e
      privateKey.getPrivateExponent.toByteArray, // d
      privateKey.getCrtCoefficient.toByteArray,  // iqmp
      privateKey.getPrimeP.toByteArray,          // p
      privateKey.getPrimeQ.toByteArray,          // q
      this.comment.getBytes
    ) foreach (x => this.writeWithLength(stream, x))

    stream.flush
    val mod = baos.size % 8
    if (mod > 0) {
      val padding = 8 - mod
      1 to padding foreach (i => stream.write(i))
    }

    stream.close()
    return baos.toByteArray
  }

  def writeWithLength(stream: DataOutputStream, bytes: Array[Byte]): Unit = {
    stream.writeInt(bytes.length)
    stream.write(bytes)
  }

  def shapeSshPrivateKey(pvt: String): String = {
    val builder = new StringBuilder("-----BEGIN OPENSSH PRIVATE KEY-----\n")
    var start = 0
    val len = 70
    while (start < pvt.length) {
      val end = math.min(start + len, pvt.length)
      builder ++= pvt.substring(start, end)
      builder += '\n'
      start += len
    }
    builder ++= "-----END OPENSSH PRIVATE KEY-----"
    return builder.toString
  }
}

以上内容，写入SshKeyGen.scala文件。运行后，可在stdout和stderr分别得到私钥和公钥。

$ scala SshKeyGen.scala 1> id_rsa 2> id_rsa.pub

参考 ¶

这几天，我再次感受到被数论支配的恐惧！

文章 ¶

代码 ¶

以下代码见sshkey.c#L3870，是私钥写入的部分。

if (strcmp(kdfname, "bcrypt") == 0) {
    arc4random_buf(salt, SALT_LEN);
    if (bcrypt_pbkdf(passphrase, strlen(passphrase),
        salt, SALT_LEN, key, keylen + ivlen, rounds) < 0) {
        r = SSH_ERR_INVALID_ARGUMENT;
        goto out;
    }
    if ((r = sshbuf_put_string(kdf, salt, SALT_LEN)) != 0 ||
        (r = sshbuf_put_u32(kdf, rounds)) != 0)
        goto out;
} else if (strcmp(kdfname, "none") != 0) {
    /* Unsupported KDF type */
    r = SSH_ERR_KEY_UNKNOWN_CIPHER;
    goto out;
}
if ((r = cipher_init(&ciphercontext, cipher, key, keylen,
    key + keylen, ivlen, 1)) != 0)
    goto out;

if ((r = sshbuf_put(encoded, AUTH_MAGIC, sizeof(AUTH_MAGIC))) != 0 ||
    (r = sshbuf_put_cstring(encoded, ciphername)) != 0 ||
    (r = sshbuf_put_cstring(encoded, kdfname)) != 0 ||
    (r = sshbuf_put_stringb(encoded, kdf)) != 0 ||
    (r = sshbuf_put_u32(encoded, 1)) != 0 ||    /* number of keys */
    (r = sshkey_to_blob(prv, &pubkeyblob, &pubkeylen)) != 0 ||
    (r = sshbuf_put_string(encoded, pubkeyblob, pubkeylen)) != 0)
    goto out;

/* set up the buffer that will be encrypted */

/* Random check bytes */
check = arc4random();
if ((r = sshbuf_put_u32(encrypted, check)) != 0 ||
    (r = sshbuf_put_u32(encrypted, check)) != 0)
    goto out;

/* append private key and comment*/
if ((r = sshkey_private_serialize_opt(prv, encrypted,
        SSHKEY_SERIALIZE_FULL)) != 0 ||
    (r = sshbuf_put_cstring(encrypted, comment)) != 0)
    goto out;

/* padding */
i = 0;
while (sshbuf_len(encrypted) % blocksize) {
    if ((r = sshbuf_put_u8(encrypted, ++i & 0xff)) != 0)
        goto out;
}

/* length in destination buffer */
if ((r = sshbuf_put_u32(encoded, sshbuf_len(encrypted))) != 0)
    goto out;

/* encrypt */
if ((r = sshbuf_reserve(encoded,
    sshbuf_len(encrypted) + authlen, &cp)) != 0)
    goto out;
if ((r = cipher_crypt(ciphercontext, 0, cp,
    sshbuf_ptr(encrypted), sshbuf_len(encrypted), 0, authlen)) != 0)
    goto out;

sshbuf_reset(blob);

/* assemble uuencoded key */
if ((r = sshbuf_put(blob, MARK_BEGIN, MARK_BEGIN_LEN)) != 0 ||
    (r = sshbuf_dtob64(encoded, blob, 1)) != 0 ||
    (r = sshbuf_put(blob, MARK_END, MARK_END_LEN)) != 0)
    goto out;

以下代码见sshkey.c#L3189，是sshkey_private_serialize_opt中RSA私钥写入的部分。

case KEY_RSA:
    RSA_get0_key(key->rsa, &rsa_n, &rsa_e, &rsa_d);
    RSA_get0_factors(key->rsa, &rsa_p, &rsa_q);
    RSA_get0_crt_params(key->rsa, NULL, NULL, &rsa_iqmp);
    if ((r = sshbuf_put_bignum2(b, rsa_n)) != 0 ||
            (r = sshbuf_put_bignum2(b, rsa_e)) != 0 ||
            (r = sshbuf_put_bignum2(b, rsa_d)) != 0 ||
            (r = sshbuf_put_bignum2(b, rsa_iqmp)) != 0 ||
            (r = sshbuf_put_bignum2(b, rsa_p)) != 0 ||
            (r = sshbuf_put_bignum2(b, rsa_q)) != 0)
        goto out;
    break;

其中，rsa_iqmp的含义，见rsa_sp800_56b_gen.c#L279。

/* (Step 5c) qInv = (inverse of q) mod p */
BN_free(rsa->iqmp);
rsa->iqmp = BN_secure_new();
if (rsa->iqmp == NULL)
    goto err;
BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
    goto err;