RSA加密解密原理（二）

PKCS

PKCS（Public Key Cryptography Standards, PKCS）公钥加密标准，是美国RSA信息安全公司旗下的RSA实验室开发的一系列编译标准，非对称密钥一般都包含其他信息，所以PKCS通过ASN.1的格式标准定义密钥展示

一个PKCS#1 公钥用asn.1表示格式如下:

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

modulus就是n，publicExponent就是e，n和e就代表了公钥。上面asn.1格式的标准
一个PKCS#1私钥用asn.1表示格式如下：

      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
        otherPrimeInfos   OtherPrimeInfos OPTIONAL
      }

openssl默认使用的是PKCS#1，但这个已经非常旧了，openssl主要是为了兼容，推进使用PKCS#8
PKCS#8是一个专门用于编码私钥的标准，可用于编码 DSA/RSA/ECC 私钥。它通常被编码成 PEM 格式存储。相比较PKCS#1，它比较安全可以兼容任何格式的私钥，因此建议用PKCS#8来代替

X.509

X.509是密码学里公钥证书的格式标准。比如ssl用的就是它

x.509是公钥标准，基本上现在的库公钥都使用x.509，私钥标准符合pkcs。pkcs#8相比较在pkcs#1的标准上增加了一些头部信息，比pkcs#1安全性高
X.509的RSA公钥格式：

      RSAPublicKey ::= SEQUENCE {
         algorithm AlgorithmIdentifier , // 这就是增加的头信息
         publicKey RSAPublicKey  // 这就是PKCS#1的RSA公钥的内容
      }

PKCS#8的RSA私钥格式：

      PrivateKey ::= SEQUENCE {
          version Version ,  // 这就是增加的头信息
          privateKeyAlgorithm PrivateKeyAlgorithmIdentifier , // 这也是增加的头信息，表示使用的什么算法，可以是 RSA，也可以是其它的算法，比如 DES、AES 等对称加密算法等。
          privateKey RSAPrivateKey // 这就是PKCS#1的RSA私钥的内容
      }

上面的公钥用der编码得到二进制格式，而为了方便看再用base64编码就是pem格式的字符串了。

PEM 和 DER编码

ASN.1通过DER编码把公钥和私钥编码成二进制格式以便于网络上传输而PEM则是为了方便，对DER进行base64编码同时在头和尾处加上一行字符串进行标记PEM格式，这样字符串就比较方便复制查看

pkcs#1的例子用pem编码后的格式如下:

      // 公钥
      -----BEGIN RSA PUBLIC KEY-----
      BASE64编码的DER密钥文本
      -----END RSA PUBLIC KEY-----
      
      // 私钥
      -----BEGIN RSA PRIVATE KEY-----
      BASE64编码的DER密钥文本
      -----END RSA PRIVATE KEY-----

pkcs#8编码后的未加密的私钥格式:

      -----BEGIN PRIVATE KEY-----
      BASE64编码的DER密钥文本
      -----END PRIVATE KEY-----
      
      -----BEGIN ENCRYPTED PRIVATE KEY-----
      BASE64编码的DER密钥文本
      -----END ENCRYPTED PRIVATE KEY-----

x.509的公钥编码后的格式：

      -----BEGIN PUBLIC KEY-----
      BASE64编码的DER密钥文本
      -----END PUBLIC KEY-----

相比较pkcs#1，就少了个rsa字符
通常以DER格式存储的证书，大都使用 .cer .crt .der 拓展名，在 Windows 系统比较常见，而PEM 格式的数据通常以 .pem .key .crt .cer 等拓展名存储，打开查看就是一堆字符串，openssl 默认使用的就是pem格式。

pkcs填充规则

在rsa加密的过程中，密文的长度不能大于密钥的长度，也就是必须满足0 < m < n，如果长了则需要对数据进行分段加密，但是如果m太短则需要对m进行填充

rsa加密的密文m是不能超过密钥的长度的，如果m>n，该公式就不能成立 m=pow(y, d) % n 无法解密，运算就会出错。
填充规则常用的标准有NoPPadding，OAEPPadding，PKCS1Padding这几种，go 在crypto/rsa库中用的是PKCS #1 v1.5 padding，PKCS1Padding的填充总共占用11个字节，对于1024位长度的密钥占用128个字节，减去11个字节，那明文最长的长度就是128-11=117个字节。1024长度的被破解过已经不建议使用了，至少使用2048或以上长度的密钥比较安全。PKCS1Padding 8.1 Encryption-block formatting填充规则如下：

      // M为明文
      // BT 代表block type块类型，有0x00，0x01，0x02, 如是是私钥则BT=00x0或01x0。如果是公钥操作，BT=0x02。
      // PS为填充的字节，BT=0x00则PS=0x00，BT=0x01则PS=0xFF，BT=0x02则PS=非0伪随机数
      EM = 0x00 || BT || PS || 0x00 || M
      
      // 假设密钥长度是2048，也就是256个字节，BT=0x02，M = 100个字节，则PS = 256 - 100 - 3 字节，填充的结构如下：
      em = 0x00 + 0x02 + (256 - 100 - 3)字节的随机数 + 0x00 + m

go 在crypto/rsa中的公钥填充加密代码示例

      // https://pkg.go.dev/crypto/rsa#EncryptPKCS1v15
      func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) ([]byte, error) {
        randutil.MaybeReadByte(rand)
      
        if err := checkPub(pub); err != nil {
            return nil, err
        }
        k := pub.Size()
        if len(msg) > k-11 {
            return nil, ErrMessageTooLong
        }
      
        // EM = 0x00 || 0x02 || PS || 0x00 || M
        em := make([]byte, k)
        em[1] = 2
        ps, mm := em[2:len(em)-len(msg)-1], em[len(em)-len(msg):]
        err := nonZeroRandomBytes(ps, rand)
        if err != nil {
            return nil, err
        }
        em[len(em)-len(msg)-1] = 0
        copy(mm, msg)
      
        m := new(big.Int).SetBytes(em)
        c := encrypt(new(big.Int), pub, m)
      
        return c.FillBytes(em), nil
      }
      
      func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
        e := big.NewInt(int64(pub.E))
          // 这里就是加密的过程了，就是上面我们说的公式pow(m,e)%n，不写第三个参数，可以单独调用Mod取模算出最终加密结果
        c.Exp(m, e, pub.N)
        return c
      }
      
      func (x *Int) FillBytes(buf []byte) []byte {
        // Clear whole buffer. (This gets optimized into a memclr.)
        for i := range buf {
            buf[i] = 0
        }
        x.abs.bytes(buf)
        return buf
      }

签名

签名就是用私钥加密，而验签是用公钥解密。签名的目的是为了证明发出消息的人以及消息是否完整，拥有私有签名的数据，则只有持有公钥的人才可以解开

签名分为以下几步：

1. 对数据进行哈希运算得到一个短的哈希值，因为rsa加密有长度限制。h= hash(m)
2. 对哈希值和摘要算法标识符OID进行asn.1编码

             DigestInfo ::= SEQUENCE {
                  digestAlgorithm DigestAlgorithmIdentifier, // 消息摘要算法
                  digest Digest  // 就是哈希运算的结果 h
             }
   

3. der编码后对数据进行填充然后利用私钥进行加密，和上面加密的填充过程一样，区别是这次是用私钥，填充的块类型BT和PS有些区别

             EM = 0x00 || 0x01 || PS || 0x00 || T
             
             // 以上面的例子为参考，2048长度的密钥，密文的长度最多256个字节，假设len(m)=100,m为der编码后的数据
             em = 0x00 + 0x01 + (256 - 100 - 3)字节的0xff + 0x00 + m
   

4. 私钥加密
   go 在crypto/rsa中的签名，验签代码示例

      // 签名
      func SignPKCS1v15(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []byte) ([]byte, error) {
        hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
        if err != nil {
            return nil, err
        }
      
        tLen := len(prefix) + hashLen
        k := priv.Size()
        if k < tLen+11 {
            return nil, ErrMessageTooLong
        }
      
        // EM = 0x00 || 0x01 || PS || 0x00 || T
        em := make([]byte, k)
        em[1] = 1
        for i := 2; i < k-tLen-1; i++ {
            em[i] = 0xff
        }
        copy(em[k-tLen:k-hashLen], prefix)
        copy(em[k-hashLen:k], hashed)
      
        m := new(big.Int).SetBytes(em)
        c, err := decryptAndCheck(rand, priv, m)
        if err != nil {
            return nil, err
        }
      
        return c.FillBytes(em), nil
      }
      
      // 验签
      // VerifyPKCS1v15 verifies an RSA PKCS #1 v1.5 signature.
      // hashed is the result of hashing the input message using the given hash
      // function and sig is the signature. A valid signature is indicated by
      // returning a nil error. If hash is zero then hashed is used directly. This
      // isn't advisable except for interoperability.
      func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte) error {
        hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
        if err != nil {
            return err
        }
      
        tLen := len(prefix) + hashLen
        k := pub.Size()
        if k < tLen+11 {
            return ErrVerification
        }
      
        // RFC 8017 Section 8.2.2: If the length of the signature S is not k
        // octets (where k is the length in octets of the RSA modulus n), output
        // "invalid signature" and stop.
        if k != len(sig) {
            return ErrVerification
        }
      
        c := new(big.Int).SetBytes(sig)
        m := encrypt(new(big.Int), pub, c)
        em := m.FillBytes(make([]byte, k))
        // EM = 0x00 || 0x01 || PS || 0x00 || T
      
        ok := subtle.ConstantTimeByteEq(em[0], 0)
        ok &= subtle.ConstantTimeByteEq(em[1], 1)
        ok &= subtle.ConstantTimeCompare(em[k-hashLen:k], hashed)
        ok &= subtle.ConstantTimeCompare(em[k-tLen:k-hashLen], prefix)
        ok &= subtle.ConstantTimeByteEq(em[k-tLen-1], 0)
      
        for i := 2; i < k-tLen-1; i++ {
            ok &= subtle.ConstantTimeByteEq(em[i], 0xff)
        }
      
        if ok != 1 {
            return ErrVerification
        }
      
        return nil
      }
      
      func pkcs1v15HashInfo(hash crypto.Hash, inLen int) (hashLen int, prefix []byte, err error) {
        // Special case: crypto.Hash(0) is used to indicate that the data is
        // signed directly.
        if hash == 0 {
            return inLen, nil, nil
        }
      
        hashLen = hash.Size()
        if inLen != hashLen {
            return 0, nil, errors.New("crypto/rsa: input must be hashed message")
        }
        prefix, ok := hashPrefixes[hash]
        if !ok {
            return 0, nil, errors.New("crypto/rsa: unsupported hash function")
        }
        return
      }
      
      // For performance, we don't use the generic ASN1 encoder. Rather, we
      // precompute a prefix of the digest value that makes a valid ASN1 DER string
      // with the correct contents.
      
      var hashPrefixes = map[crypto.Hash][]byte{
        crypto.MD5:       {0x30, 0x20, 0x30, 0x0c, 0x06, 0x08, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x02, 0x05, 0x05, 0x00, 0x04, 0x10},
        crypto.SHA1:      {0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14},
        crypto.SHA224:    {0x30, 0x2d, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x04, 0x05, 0x00, 0x04, 0x1c},
        crypto.SHA256:    {0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20},
        crypto.SHA384:    {0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05, 0x00, 0x04, 0x30},
        crypto.SHA512:    {0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05, 0x00, 0x04, 0x40},
        crypto.MD5SHA1:   {}, // A special TLS case which doesn't use an ASN1 prefix.
        crypto.RIPEMD160: {0x30, 0x20, 0x30, 0x08, 0x06, 0x06, 0x28, 0xcf, 0x06, 0x03, 0x00, 0x31, 0x04, 0x14},
      }

go在hashPrefixes里提前计算好了没个哈希算法标识符的der编码后的值，注释里说是为了提升性能。我以sha256为例，实现如下，发现除了首尾4个字节，中间部分一致:

      package main
      
      import (
        "crypto/x509/pkix"
        "encoding/asn1"
        "encoding/hex"
        "fmt"
      )
      
      func main() {
        // hash256算法标识oid
        oidSHA256 := asn1.ObjectIdentifier{2, 16, 840, 1, 101, 3, 4, 2, 1}
      
        mgf1Params := pkix.AlgorithmIdentifier{
            Algorithm:  oidSHA256,
            Parameters: asn1.NullRawValue,
        }
        d, err := asn1.Marshal(mgf1Params)
        if err != nil {
            fmt.Println(err)
        }
        oid := hex.EncodeToString(d)
        fmt.Println(oid) 
          // 输出如下：
          // 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00
          // {0x30, 0x31, 0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20}
      }

可以看到输出的和上面hashPrefixes里sha256的值除了首尾4个字节不同，首部2个字节分别是0x30，0x31，尾部2个字节分别是 0x04, 0x20，至于这4个分别代表什么暂时不清楚，🤷♂️。

经查阅文档发现是我构造的签名数据结构问题，然后我们加上签名的数据m，按照文档定义数据结构(参考RFC 2313 10.1.2)，发现得到的der编码前半部分刚好与hashPrefixes里sha256的值是一样的，后半部分刚好是哈希值编码后的值，如果对编码后的数据进行填充，然后私钥加密，其实就是实现了一次签名的完整过程。

        /* ASN1 DER structures
        DigestInfo ::= SEQUENCE {
            digestAlgorithm AlgorithmIdentifier,
            digest OCTET STRING
        }
        */

            // 算法标识符
        type AlgorithmIdentifier struct {
            Algorithm  asn1.ObjectIdentifier
            Parameters asn1.RawValue `asn1:"optional"`
        }

        // 签名的数据结构
        type DigestInfo struct {
            DigestAlgorithm AlgorithmIdentifier
            Digest          []byte
        }

        sha := sha256.New()
        m := []byte{50}
        sha.Write(m)
        h := sha.Sum(nil)

        var digestInfo = DigestInfo{
            DigestAlgorithm: AlgorithmIdentifier{
                Algorithm: oidSHA256,
                Parameters: asn1.RawValue{
                    Tag: asn1.TagNull,
                },
            },
            Digest: h,
        }

        d, err := asn1.Marshal(digestInfo)
        if err != nil {
            fmt.Println(err)
            return
        }
        oid := hex.EncodeToString(d)
        fmt.Println(oid)

          // 输出
          // 3031300d060960864801650304020105000420 d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35

但是上面代码如果我们去掉生成哈希值的部分，然后 Digest 字段的值定义为空或者不填写则生成的值和hashPrefixes[sha256]是不一样，这种区别刚好区分在首部2个字节，那么问题来了这2个字节分别代表什么意思呢？这里牵扯到ans.1的der编码规则，不是很懂，后边这块的知识需要再补补，简单来说0x30指的是类型，代表着一个sequence结构，0x31指的是后边数据的长度。

asn.1的der编码规则是遵循了type-length-value 规则，由几个部分组成

Identifier octets Type	Length octets	Contents octets	End-of-Contents octets
Type	Length	Value	(only if indefinite form)

Type用高2位表示Tag class，高位第3位表示是否是复合数据类型P/C，后边则是 TagNumber

0x30就指的是Type，0x30转换成二进制 0011 0000，可以看到前面2个位是0。可以看到 00是tag class，代表asn.1的原生数据类型，1是 P/C C指的是复合数据类型，由于签名是 SEQUENCE 结构体所以这里是复合数据类型，所以是1，后边的 1 0000 转换成10进制是16，而16所在的tagNumber刚好代表 SEQUENCE，参考x.690 BER encoding Identifier octets
0x31指的是数据长度，长度又分定长和不定长等，说起来就比较多了，详细的另写一篇记录。