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

利用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_rsaid_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 01en的具体含义,见前面定义。

私钥文件格式

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

-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAAAlwAAAAdzc2gtcn
NhAAAAAwEAAQAAAIEAzEmdMVU/tc2uGTuRNlhPNihenlHIokzOwfTTrp7z0Mfz+tLmRmt2
hfo+I1/nAnqIWkyb/SpzoBzhaQqJOBdJjSjwMyiWpKPJhHqyNcYxwOP8CQ18NDOKiuj+s/
WRikZ42rKN40WiQ5N6/P7gIk7jfjItvxaNvA2dQV0+gOZYfuUAAAIAOa0QqjmtEKoAAAAH
c3NoLXJzYQAAAIEAzEmdMVU/tc2uGTuRNlhPNihenlHIokzOwfTTrp7z0Mfz+tLmRmt2hf
o+I1/nAnqIWkyb/SpzoBzhaQqJOBdJjSjwMyiWpKPJhHqyNcYxwOP8CQ18NDOKiuj+s/WR
ikZ42rKN40WiQ5N6/P7gIk7jfjItvxaNvA2dQV0+gOZYfuUAAAADAQABAAAAgCIewXR16p
gw7D0mp9BN250ODQ+gVURWU8otXBW0UsCyRNvF0dQ9KqSh8TLzV6AgWxnJ5dvY9Urux+9F
ZTnLGet/Ll1zeiG3iz4SN7QnrYUCYHg8fBdp0ED0qoBJg5Mu6Maab4LUW5Kq5biZU6J2Ru
aWIuG8lmHe8/LURTFbE6AZAAAAQQDIBLDz6mH2S++kMt5j4HXH2eRmrtr/eF7KjE7k8HH3
Dm+G3KtRnQkxL4c6mSJj19Fbe7FMlqt43o/6Ew7vJxvkAAAAQQD1ry7c1knKHw68TlYAzR
dlwwtfz6C1smr/Jn8MjIMygAR/GTuhdH3rvI2/pXyAag+TCRmwIod9hmm4GG6eZYavAAAA
QQDU3Xbx//DpjASzczUmaY6xgBMgN/ffhLTq1uvk3CFCv4B7EM6noXg7Q22J4GxqY/0q91
7sJVwCgVq0KbqGUvirAAAACm5hbWVAZW1haWw=
-----END OPENSSH PRIVATE KEY-----

首行与末行固定,中间则是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位。 从nq的含义,见前面定义。 其中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;

相关笔记